Принятие решений на примере задачи распознавания образов с использованием алгоритма «Дискриминантная функция»

Введение 3 Теоретическая часть 4 Метод решения задачи. 4 Линейный дискриминантный анализ. 4 Квадратичный дискриминантный анализ. 6 Распознавание с отказами. 6 Практическая часть 8 Постановка задачи. 8 Исходные данные 8 Решение 12 Заключение 20 Список литературы 21

Введение

Дискриминантный анализ — это раздел математической статистики, содержанием которого является разработка методов решения задач различения (дискриминации) объектов наблюдения по определенным признакам. Методы дискриминантного анализа находят применение в различных областях: медицине, социологии, психологии, экономике и т.д. При наблюдении больших статистических совокупностей часто появляется необходимость разделить неоднородную совокупность на однородные группы (классы). Такое расчленение в дальнейшем при проведении статистического анализа дает лучшие результаты моделирования зависимостей между отдельными признаками. Дискриминантный анализ оказывается очень удобным и при обработке результатов тестирования отдельных лиц. Например, при выборе кандидатов на определенную должность можно всех опрашиваемых претендентов разделить на две группы: «подходит» и «не подходит». Можно привести еще один пример применения дискриминантного анализа в экономике. Для оценки финансового состояния своих клиентов при выдаче им кредита банк классифицирует их на надежных и ненадежных по ряду признаков. Таким образом, в тех случаях, когда возникает необходимость отнесения того или иного объекта к одному из реально существующих или выделенных определенным способом классов, можно воспользоваться дискриминантным анализом.

Теоретическая часть

Дискриминантный анализ используется для решение задач распознавания в ситуациях, когда в материале обучения (МО) представлены объекты K образов (K=2,3,…), распределенные нормально.

Метод решения задачи.

Дискриминантный анализ основан на предположении, что объекты, составляющие каждый из образов, многомерно нормально распределены. Мы опираемся на эталонные объекты. Теоретически разделяются: — линейный дискриминантный анализ, когда матрицы ковариации для разных образов равны; — квадратичный дискриминантный анализ, когда матрицы ковариации для разных объектов различны.

Линейный дискриминантный анализ.

Рассмотрим случай, когда в МО имеется два образа. Оказывается, что при равных ковариационных матрицах поверхность с одной стороны, от которой больше вероятность принадлежности к одному из образов, а с другой к другому (критерий Байеса), является гиперплоскость, т.е. линейная поверхность размерности n-1 (n – размерность пространства). Уравнение гиперплоскости в общем виде можно записать следующим образом: . В данном случае эта поверхность вычисляется следующим образом: (1), где – n-мерный вектор столбец в пространстве свойств ; – математическое ожидание (среднее) объектов 1-го образа; – математическое ожидание (среднее) объектов 2-го образа; – транспонирование; – матрица коэффициентов ковариации. Формула (1) называется уравнением линейной дискриминантной функции. Коэффициенты ковариации вычисляются следующим образом: , где M – знак математического ожидания. Коэффициенты ковариации тесно связан с коэффициентом корреляции: , где — среднее квадратичное отклонение ( ) i-го свойства; — среднее квадратичное отклонение ( ) j-го свойства; Дисперсия . Дискриминантная плоскость разбивает все пространство на две части. При этом точки пространства, относимые к 1-му образу, при подстановки своих координат в дискриминантную функцию дадут , а точки 2-го образа — . Таким образом, подставляя координаты, интересующих нас объектов выборки, мы по дискриминантной функции определим, к какому из двух образов принадлежит объект (понятно, что с определенной долей вероятности). На рисунке (рис. 1) для двумерного случая это выглядит следующим образом: Значение матриц ковариации вычисляются по формулам: ; . Есть параметр, говорящий о качестве разбиения с помощью дискриминантной функции – это расстояние Махаланобиса: . Разбиение тем лучше, чем больше .

Квадратичный дискриминантный анализ.

Был рассмотрен случай, когда матрицы ковариации для разных образов равны, и для распознавания использовалась линейная дискиминантная функция. Теперь рассмотрим ситуацию, когда матрицы ковариаций разных образов не совпадают. Для различных ковариационных матриц байесовский критерий предлагает строить квадратичную дискриминантную функцию. Однако, на практике ее строят чрезвычайно редко, поскольку никогда нельзя с точностью сказать равны или нет ковариационные матрицы. Мы ведь имеем только оценки, так как работаем не со всей генеральной совокупностью объектов, а только с выборкой из нее. Поэтому обычно вычисляют усредненную ковариационную матрицу для двух образов: , где – число объектов в 1-ой выборке; – число объектов во 2-ой выборке; – ковариационная матрица для 1-го образа; – ковариационная матрица для 2-го образа. После этого применяется линейный дискриминантный анализ.

Распознавание с отказами.

Пусть имеется образов, где (т.е. известны эталоны для этих образов). Тогда можно построить линейную дискриминантную функцию для любой пары образов: , где i, j – образы. относится к i-му образу, если для всех j, или к области отказа, если такового i – нет. Посмотрим как это выглядит на графике (рис. 2), где D – гиперплоскости; 1, 2, 3 – образы; 4 – область отказа. В область отказа попадают такие точки, для которых невозможно определить принадлежность к одному из образов. Другими словами точка отказа – это такая точка, координаты которой при подстановке в дискриминантную функцию дают следующие значения: ; ; ; . Дискриминантный анализ эффективно использовать при достаточно близком расположении образов и даже при небольшом их наложении. Практика показала, что дискриминантный анализ хорошо работает и для случая, когда нет многомерного нормального распределения. При этом необходимо, чтобы распределение по каждому образу было все таки симметрично и унимодально. Правда, при этом алгоритм уже нельзя рассматривать как статистический, а можно говорить об эвристическом алгоритме распознавания образов.

Практическая часть

Постановка задачи.

Исследуем, какие свойства относят квартиру к одной из трех категорий: (1) 1-комнатной, (2) 2-комнатной или (3) 3-комнатной. В данной задаче имеются 3 образа: 1 – 1-комнатная квартира, 2 – 2-комнатная квартира и 3 – 3-комнатная квартира и 3 свойства: общая площадь, жилая площадь и цена квартиры. Известна часть представителей каждого образа и значения их свойств (табл. 1). Требуется отнести квартиры (МЭ) к каждому из образов (табл. 2).

Исходные данные

Таблица 1

Материал обучения
общ. площадь (кв.м.)	цена (тысяч $)	кол-во комнат	жилая площадь
44	50	1	32
29	50	1	22
31	58	1	20
28	55	1	23
40	54	1	31
48	49	1	40
44	48	1	37
36	51	1	28
26	60	1	18
29	57	1	19
41	56	1	36
27	59	1	18
47	61	1	39
34	53	1	20
47	49	1	36
28	40	1	15
49	54	1	32
54	62	1	42
52	59	1	43
34	47	1	23
46	59	1	35
41	54	1	26
36	56	1	27
32	49	1	23
28	51	1	16
39	58	1	27
30	54	1	20
48	63	1	39
44	51	1	31
29	45	1	21
52	57	1	44
47	56	1	39
46	58	1	38
39	59	1	24
47	60	1	35
43	61	1	30
42	51	1	29
32	50	1	18
36	57	1	22
44	66	1	35
56	72	2	40
57	79	2	41
59	80	2	43
58	85	2	42
69	83	2	53
60	77	2	50
64	88	2	52
73	91	2	60
56	90	2	42
60	100	2	49
60	89	2	50
68	94	2	54
64	97	2	51
66	81	2	53
57	75	2	55
67	89	2	56
65	96	2	50
71	94	2	59
68	91	2	58
65	94	2	49
72	86	2	60
77	89	2	61
60	88	2	48
64	99	2	51
70	91	2	58
79	96	2	62
67	98	2	56
64	93	2	51
58	94	2	43
63	101	2	45
57	94	2	42
74	110	2	62
60	118	2	42
73	112	2	57
69	120	2	47
71	93	2	57
70	99	2	56
60	89	2	51
79	94	2	65
69	123	2	50
100	130	3	80
120	149	3	101
88	150	3	62
93	145	3	73
87	173	3	63
101	165	3	81
87	127	3	61
94	189	3	74
84	156	3	70
118	191	3	99
100	183	3	84
97	179	3	74
118	178	3	100
115	184	3	95
123	187	3	106
93	182	3	74
92	167	3	73
99	154	3	78
109	185	3	95
103	132	3	96

Таблица 2 На рис. 1 изображены объекты материала обучения и материала экзамена. Рис. 1и 2 и между 2 и 3 образами.

Решение

1. Вычисляем математическое ожидание для каждого свойства, каждого образа: Мi – математическое ожидание для i-ого образа. 2. Построим матрицы ковариации: Матрица ковариации для 1 образа: Матрица ковариации для 2 образа: Матрица ковариации для 3 образа: 3. Вычислим среднюю и обратную матрицы ковариации: Средняя матрица ковариации для 1 и 2 образов Обратная матрица ковариации 1 и 2 образов Средняя матрица ковариации для 2 и 3 образов Обратная матрица ковариации 2 и 3 образов Средняя матрица ковариации для 1 и 3 образов Обратная матрица ковариации 1 и 3 образов 4. Вычислим коэффициенты b и p Для образов 1 и 2: b12 = 2,190385893 -0,742470522 -2,192958018 p12 = -1351,05946 Для образов 2 и 3: b23 = 4,157512047 -0,617354197 -3,531577574 p23 = -1527,631272 Для образов 1 и 3: b13 = -1,536574503 -0,593353629 1,069478346 p13 = 113,7887413 5. Вычисляем дискриминантную функцию и проводим распознавание. В табл. 3 приведены результаты вычислений. Таблица 3. 1св-во (рис.2) 1 2 x y z 26 -2,887527939 40 79 153,4694571 40 2 3 x y z 56 99,46503296 40 123 550,6700441 40 1 3 x y z 26 196,5386786 40 123 -246,4289809 40 Рис.2. 2св-во (рис.3) 1 2 x y z 40 38,41431716 40 123 283,275256 40 2 3 x y z 72 207,2154834 40 191 1008,609458 40 1 3 x y z 40 160,2836664 40 191 -230,7525366 40 Рис.3 3св-во (рис.4) 1 2 x y z 15 -35,33897766 40 65 112,167612 40 2 3 x y z 40 -8,285417474 40 106 436,1851906 40 1 3 x y z 15 225,0247596 40 106 -10,63281965 40 Рис.4.

Заключение

Дискриминантный анализ эффективно использовать при достаточно близком расположении образов и даже при небольшом их наложении и когда в материале обучения присутствует 2 и более образов. Для решения данной задачи использовался алгоритм «Дискриминантная функция», т.к. в материале обучения присутствует 3 образа и объекты обучения имеют нормальное распределение, т.е. образы компактны. В результате для данной задачи распознавание с помощью алгоритма «Дискриминантная функция» дало ошибку 1-го и 2-го рода и область отказа. Объекты материала экзамены были полностью распознаны.

Список литературы

1. Вапник В.Н., Червоненскис А.Я. Теория распознавания образов. – М. 1974. 2. Васотев В.И. Распознавательные системы. – Киев. 1969. 3. Горелик А.Л., Скрипкин В.А. Методы распознавания образов. – М. 1977. 4. Добрынин В.Н., Черемисина Е.Н., Булякова И.А и др. Математические методы системного анализа и теория принятия решений. – Дубна. 2002. 5. Черемисина Е.Н. Конспект лекций по ТПР.