ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования СА...
5 downloads
128 Views
736KB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования САНКТПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
С. Н. Воробьев, С. С. Осипов
ПАРАМЕТРИЧЕСКОЕ ОБУЧЕНИЕ В ТЕОРИИ РАСПОЗНАВАНИЯ ОБРАЗОВ
Учебное пособие
СанктПетербург 2005 1
УДК 519.7 ББК 22.18 В75 Воробьев С. Н., Осипов С. С. В75 Параметрическое обучение в теории распознавания образов: учеб. пособие / ГУАП. СПб., 2005. 46 с.: ил. Рассматривается проблема распознавания образов в радиоэлектрони ке, которая является ключевой при обнаружении и классификации сиг налов с неизвестными характеристиками и параметрами. Задача распоз навания формулируется как поиск однозначного отображения совокупно сти наблюдений на множество классов объектов. Теоретическая база рас познавания – математическая статистика. Наблюдения преобразуются в более удобные признаки распознаваемых классов, к которым применяют ся методы проверки статистических гипотез и оценивания. В учебном пособии представлены многомерное нормальное распределение, сингу лярное разложение корреляционной матрицы, декорреляция, вопросы создания эталонных признаков классов. Классификация по правилу ми нимума расстояния между наблюдаемыми и эталонными признаками ин терпретируется как синтез разделяющих функций. Рецензенты: кафедра информационных управляющих систем СПбГУТ; доктор технических наук, профессор С. А. Яковлев Утверждено редакционноиздательским советом университета в качестве учебного пособия
Учебное издание
Воробьев Станислав Николаевич Осипов Сергей Семенович
ПАРАМЕТРИЧЕСКОЕ ОБУЧЕНИЕ В ТЕОРИИ РАСПОЗНАВАНИЯ ОБРАЗОВ
Учебное пособие Редактор А. В. Семенчук Компьютерная верстка О. И. Бурдиной Сдано в набор 05.10.05. Подписано к печати 23.11.05. Формат 60´84 1/16. Бумага офсетная. Печать офсетная.
Усл. печ. л. 2,75. Уч.изд. л. 3,08. Тираж 150 экз. Заказ № 584.
Редакционноиздательский отдел Отдел электронных публикаций и библиографии библиотеки Отдел оперативной полиграфии ГУАП 190000, СанктПетербург, ул. Б. Морская, 67
© ГОУ ВПО СПбГУАП,2005
2
ВВЕДЕНИЕ Распознавание образов используется во многих областях науки и техники и лежит в основе управления голосом оператора, в автомати зации информационносправочных служб. В медицине распознавание образов составляет основу экспрессдиагностики заболеваний. В кри миналистике и охране важных объектов на основе распознавания обра зов идентифицируется личность. Научнопрактическое применение рас познавания образов нашло в метеорологии, геофизике, геохимии, гео логии, геодезии и картографии и т. д. Распознавание можно определить как классификацию – отнесение исследуемого объекта, задаваемого в виде совокупности наблюдений, к одному из взаимоисключающих классов. Задачу распознавания можно сформулировать как задачу поиска однозначного отображения сово купности наблюдений X на множество классов K 3 1K1, K2,..., KM 2 . Класс Ki можно заменить его номером i, и тогда отображение X 3 11,2,...,M2 записывается как целочисленная функция m 3 4 1 X 2 . Пример – обнаружение цели в радиолокации: при гипотезах H0 и H1 сигнал на входе (наблюдения) X 1 N , X 1 N 2 S ( N,S – векторы отсче тов шума и зондирующего сигнала, отраженного от цели); задача – ана лизируя наблюдения, принять одну из двух гипотез. Задача обнаруже ния по сути классификационная, так как гипотезы в терминологии математической статистики являются классами в терминологии рас познавания образов. Теоретические вопросы классификации изучаются в разделе «Про верка статистических гипотез» математической статистики. Оптималь ное решение задачи обнаружения включает два этапа: преобразование наблюдений X в случайное число 1 , называемое статистикой проверки гипотез; сравнение статистики с критическим значением 1 0 – гипотеза H1 принимается (цель обнаруживается) при условии 1 2 1 0 . Подобная последовательность характерна для решения задач рас познавания образов. Прежде всего, наблюдения X преобразуются в при знаки Y распознаваемых классов
Y 3 41X2 , более удобные для распознавания, чем наблюдения. Общей процедуры выделения признаков не существует, признаки соответствуют конкрет ной задаче. Пусть, например, X – отсчеты сигнала телевизионной каме ры при наблюдении геометрических фигур разного цвета. В зависимос ти от того, классифицировать ли их по цветам или типу фигуры (прямо 3
угольники, треугольники, овалы), признаками могут быть интенсив ности базисных цветов (сигналы красного, зеленого и синего цвета) или результаты измерения длительности импульсных сигналов по строкам телевизионного растра. Часто стараются минимизировать число при знаков, доводя его, если это возможно, до единицы. Разумеется, инфор мативность множества признаков I 1 Y 2 3 I 1 X 2 должна быть достаточ ной для успешной классификации при условии достаточности I 1 X 2 . Распознавание затрудняется наличием случайной шумовой состав ляющей наблюдений, так что вероятность правильной классификации меньше единицы. Наиболее благоприятным является случай нормаль ного распределения шума, позволяющего в ряде случаев получить стро гое решение. Многомерное нормальное распределение, в том числе син гулярное разложение корреляционной матрицы и процедура декорре ляции, рассматривается в разд. 1. Вопросы создания эталонных признаков классов на базе оптималь ных методов оценивания параметров распределений изложены в разд. 2. Математические трудности оценивания корреляционных матриц, свя занные с распределением Уишарта, преодолеваются декорреляцией век тора признаков. Методика расчета вероятностей правильной класси фикации и ошибок – в разд. 3. Классификация по правилу минимума расстояния между наблюдае мыми и эталонными признаками интерпретируется как синтез разде ляющих функций (разд. 4). Введение разделяющих функций приводит к наглядным геометрическим моделям с линейными или нелинейными границами между классами и позволяет численным интегрированием рассчитывать вероятности ошибок. Использование правила максималь ной апостериорной вероятности связывает процедуры распознавания и проверки статистических гипотез. Создание эталонных признаков классов при непомеченных выбор ках (обучение без учителя) с использованием метода моментов рассмот рено в разд. 5. Учебное пособие содержит примеры расчетов и моделирования в сис теме MATLAB 6.
4
1. МНОГОМЕРНОЕ НОРМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ Запись
X 3 4 1 5, B 2
означает, что вектор случайных значений XT 3 1 x1 x2 ,..., xn 2 описыва ется плотностью многомерного нормального распределения [1] 1n /2
1 det B 211/2 exp
3
4
1 1 X 6 7 2T B11 1 X 6 7 2 , (1) 2 где B – n 1 n матрица корреляционных моментов (корреляционная мат рица); MT= [m1 m2, ..., mn] – вектор математических ожиданий. Если X – отсчеты стационарного процесса x 1 t 2 , взятые с интервалом дискретизации 1t , корреляционная матрица симметрична ( bij 1 bji ) и положительно определена. Корреляционные моменты
f 1 X 2 3 1 25 2
6
bij 1 R i 1 j
есть значения функции корреляции R 1 3 2 процесса x 1 t 2 :
R i 1 j 3 R 1 i 4 j 5t 2 .
Корреляционная матрица имеет сингулярное разложение [2] (2) B 1 U2UT , где U 3 1U1 U2 ,..., Un 2 – n 1 n матрица собственных векторов Ui ; 1 – диагональная матрица собственных значений 1i матрицы B. Все собственные значения 1i 2 0 – следствие положительной опреде ленности корреляционной матрицы. Обратно: если хотя бы одно собственное значение отрицательно, матрица отрицательно определена (не является корреляционной). Дру n
гие свойства собственных значений:
n
1i 2 trB ; tr – след 3 1i 2 det B ; 3 i 11 i 11
матрицы (сумма диагональных элементов). Собственные векторы Ui ортонормированы UTU 1 I , ò. å. 21, если i 1 j; UT i Uj 1 3 50, если i 4 j.
Ортонормированность собственных векторов означает, что они за дают nмерную декартову систему координат.
5
Пример 1 Функция корреляции R 1 3 2 4 52 exp 1 623 2 cos273 , интервал дискрети зации 12 3 1/2 , число отсчетов n = 5. Значения функции корреляции в узлах дискретизации R 1 k 2 5 62 31.0000 70.6065 0.3679 70.2231 0.13534.
Корреляционная матрица 2 1.0000 10.6065 0.3679 10.2231 0.1353 3 4 10.6065 1.0000 10.6065 0.3679 10.22315 24 B67 0.3679 10.6065 1.0000 10.6065 0.3679 5 4 5 4 10.2231 0.3679 10.6065 1.0000 10.60655 84 0.1353 10.2231 0.3679 10.6065 1.0000 95
имеет собственные векторы и собственные значения, рассчитываемые в системе MATLAB функцией EIG [3]: 10.2254 0.4212 0.5534 10.5679 0.3781 10.5092 0.5679 0.1180 0.4212 10.4762 U 2 10.6162 0.0000 10.5998 0.0000 0.5104 ; 10.5092 10.5679 0.1180 10.4212 10.4762 10.2254 10.4212 0.5534 0.5679 0.3781 0.2667 0 0 0 0 0 0.3477 0 0 0 12 0 0 0.5597 0 0 ; 0 0 0 1.1490 0 0 0 0 0 2.6768 n
n
3 1i 2 det B 2 0.1597 ; 3 1i 2 trB 2 5 ; i 11
i 11
U U 1I; T
произведение B1 1 U2UT воспроизводит матрицу B с погрешностью 1.0e – 0151 0.2220 0.1110 0.0833 0.0278 0 0 0.1110 –0.1110 –0.2220 0.1388 , 1 2B 3 B 1 B1 3 0.1110 –0.1110 10.6661 0.2220 –0.2220 0.1388 0.2220 –0.2220 0.4441 10.2776 0 –0.1665 0.3331 0.2220 10.1388
меньшей 10115 , что соответствует машинной точности.
6
Уравнение линии постоянной плотности (1)
125 21n /2 1 det B 211/2 exp
3
6
4
1 1 X 6 7 2T B 11 1 X 6 7 2 8 c; 2
1 X 3 4 2T B 11 1 X 3 4 2 5 r 2; r 2 3 2ln 1 c 2 4 n ln 1 25 2 4 ln 1 det B 2,
описывает эллипсоид с центром в точке M, оси которого задаются соб ственными векторами матрицы B. Величина r2 называется квадратич ным махаланобисовым расстоянием от X до M (Mahalanobis – индийс кий математик). Линии постоянной плотности, таким образом, есть эллипсоиды постоянного махаланобисова расстояния до M. Пример 2 Двумерная плотность может быть изображена на плоскости. Пусть корреляционная матрица 1.0000 –0.7000 , B1 –0.7000 1.0000 112 а вектор математических ожиданий 3 4 5 6 . Плотность распределения 718 показана на рис. 1.
0.25 0.2 0.15 0.1 0.05 0 4 2
4 2
0 –2
0 –2
Рис. 1. Двумерная нормальная плотность
Матрица собственных векторов –0.7071 –0.7000 U1 –0.7071 0.7071 7
задает главные оси рассеивания (оси эллипсов рассеивания), которые показаны на рис. 2. y 1 x 2 0 , y 1 x 1 2 2 0. y 4
2
x
0
–2
–4 –4
–2
0
2
4
Рис. 2. Эллипсы рассеивания: c = 0.001, c = 0.01, c = 0.1
Эллипсы уточняют положение и ориентацию плотности, показан ной на рис. 1, так как в двумерном случае являются сечениями плотно сти на уровнях c. Пример 3 Эталонные признаки трех равновероятных классов – нормальные 1 двумерные плотности с математическими ожиданиями 31 4 15 26 , 718 2 13 3 2 12 3 42 5 6 7 , 43 5 6 , единичной дисперсией и корреляционными мо 80.579 8 119 ментами R1 1 20.7 , R2 1 20.7 , R3 1 0.5 (рис. 3)
3
1
24
1 1 exp 6 1 x 6 122 7 1.4 1 x 6 121 y 6 12 7 1 y 6 122 7 1.02 68 0.51 1 1 exp 6 7 1 x 7 222 6 1.4 1 x 7 221 y 7 12 7 1 y 7 122 7 1.02 68 0.51 1 1 exp 6 7 1 x 7 322 6 1 x 7 321 y 6 0.5 2 7 1 y 6 0.522 . (3) 1.5 68 0.75
f 1 x, y 2 5
3 1 3 1
24 24
Программа вывода [4]: [x,y]=meshgrid([5:0.1:3]); z=1/3/2/pi/sqrt(0.51)*exp(1/2/0.51*((x1).^2+1.4*(x1).*(y1)+(y1).^2))+... 1/3/2/pi/sqrt(0.51)*exp(1/2/0.51*((x+2).^21.4*(x+2).*(y+1)+(y+1).^2))+...
8
1/3/2/pi/sqrt(0.75)*exp(1/2/0.75*((x+3).^2(x+3).*(y0.5)+(y0.5).^2)); surf(x,y,z) colormap(white) xlim([5,4]) ylim([5,4])
0.08 0.06 0.04 0.02 0 4 2
4 0 –2 –4
–2
–4
–6 –6
2
0
Рис. 3. Совместная плотность признаков
Кластеры, изображенные на рис. 4 для уровня c = 0.01, не только характеризуют ориентацию плотностей классов, но и показывают, что минимальная вероятность ошибки классификации достижима для пер вого и третьего классов, вероятность ошибки при сравнении второго и третьего классов максимальна. y 6 4
1
3 2
x
0 –2
2
–4 –6 –6
–4
–2
0
2
4
6
Рис. 4. Эллипсы рассеивания: c = 0.01
9
0.06
0.04
0.02 0 5 0 –5
–6
–4
–2
4
2
0
Рис. 5. Совместная плотность признаков y 6 1
3 4 2
x
0 –2 2 –4 –8
–6
–4
–2
0
2
4
6
Рис. 6. Эллипсы рассеивания: c = 0.004
Для упрощения расчетов часто применяют процедуру декорреляции (выбеливания) – канонического преобразования нормального вектора наблюдений (признаков) X 3 4 1 5 X , B 2 , приводящего корреляционную матрицу к единичной, кластер – к nмерной сфере. Оператор [2] A 1 U2 11/2UT декоррелирует наблюдения Y 1 AX , Y 3 4 1 5 Y ,I 2 , вектор математических ожиданий изменяется 1 Y 2 A1 X .
10
(4)
(5)
Пример 4 Корреляционные матрицы признаков в примере 3:
B1 1
1.0000 –0.7000 1.0000 0.7000 1.0000 0.5000 , B2 1 , B3 1 , –0.7000 1.0000 0.7000 1.0000 0.5000 1.0000
операторы (4) А1 1
1.2964 0.5294 1.2964 –0.5294 1.1154 –0.2989 , А2 1 , А3 1 , 0.5294 1.2964 –0.5294 1.2964 –0.2989 1.1154
математические ожидания (5) М1 1
1.8257 –2.0633 –3.4955 , М2 1 , М3 1 . 1.8257 –0.2376 1.4543
Совместная плотность (3), показанная на рис.3, преобразуется в плотность распределения (рис.5)
3 1
24
2 2 1 1 exp 6 1 x 6 1.8257 2 7 1 y 6 1.8257 2 7 68 2 2 2 1 1 7 exp 6 1 x 7 2.0633 2 7 1 y 7 0.2376 2 7 68 2 2 2 1 1 7 exp 6 1 x 7 3.4955 2 7 1 y 6 1.4543 2 , 68 2
f 1 x, y 2 5
3 1 3 1
24 24
составляющие плотности имеют круговые рассеяния (рис. 6), эллипсы вырождаются в окружности с центрами в точках 1i .
11
2. ПАРАМЕТРИЧЕСКОЕ ОБУЧЕНИЕ С УЧИТЕЛЕМ В теории распознавания образов предполагается априорное незна ние эталонных распределений признаков [5, 6]. Это означает, что рабо чему этапу классификации (непосредственному распознаванию) пред шествует этап обучения – создания эталонов классов. Как подчеркива ется в [6], распределение признаков, отличное от нормального, остав ляет немного шансов на успешное теоретическое решение задачи рас познавания. Если ограничиться рамками нормального распределения, обучение сводится к оценке параметров (векторов математических ожи даний и корреляционных матриц). Такое обучение называется пара метрическим. Если оценивание производится по классифицированным выборкам, имеет место обучение с учителем, если используются неклас сифицированные выборки – обучение без учителя. Параметрическое обучение может применяться и при других конкретных распределени ях признаков, таких, которые описываются небольшим числом пара метров. Если же неизвестен вид распределения, необходимо его оценить; такое обучение называется непараметрическим. Непараметрическое обучение также может реализоваться как обучение с учителем или без учителя. 2.1. Неизвестные средние При нормальном распределении признаков простейшим можно счи тать случай неизвестных векторов математических ожиданий 1i при известных корреляционных матрицах B j , j 1 1,...,k . Для любого из k классов обучение с учителем сводится к поиску оценки центра кластера 1 i по обучающей выборке размерностью N векторов, поэтому индекс 1 i класса j можно опустить. Обучающая выборка – множество независи мых векторов с плотностями вида (1), так что ее плотность записывается f 1 X, 7 2 8 1 29 2
1nN /2
3
N
1 det B 21 N /2 exp 55 1 1 X j 7 2 2 j 21
T
4 B 11 1 X j 7 2 6. 6
Оценка максимального правдоподобия [7] (асимптотически несме щенная, эффективная, нормальная) определяется уравнением N
T 3 1 3 ln f 1 X; 4 2 5 6 X j 6 4 2 B 11 1 X j 6 4 2 5 0 ; 1 34 2 j 21 34
7
12
(6)
1 5 0; 2 6 B11 1 X j 3 4 N
j 21
его решение N
12 1 1 Xj N j 11
3
(7)
– выборочное среднее, чего и следовало ожидать для нормального случая. 1 4 N 1 3, 1 B 2 . Оценка (7) – линейна, 3 5 6 7 N 8
2.2. Неизвестные средние и корреляционные матрицы К уравнению (6) добавляется уравнение 1 12 3 N 1 11 B 7 ln f 1 X; 4 2 5 6 B 3B 2 2
N
81 Xj 6 4 2 1Xj 6 4 2
T
5 0,
j 21
решение которого
61
21
N
13 1 1 X 45 1 B Xj 4 5 j N j 11
2
T
иногда называют выборочной корреляционной матрицей [7]. Она дает смещенную оценку корреляционной матрицы. Как и выборочная дис персия в одномерном случае, несмещенная оценка записывается 13 B
61 N
21
1 1 X 45 1 Xj 4 5 j N 4 1 j 11
2
T
.
(8)
Выборочная корреляционная матрица имеет распределение Уишар та, с которым расчеты вероятностей затруднительны. И в этом случае упрощение достигается применением декоррелирующего преобразова ния (4): матрица оценок (8) – симметричная, преобразование 12 1 11/2 U 1T , Y 1 AX ; A 1 U
(9)
1, 1 1 – собственные векторы и собственные значения матри в котором U цы (8), дает круговое рассеивание с 1. B 1 I , 1 2 A1 Y
Y
Пример 5 Пусть в условиях примера 3 используются обучающие выборки ( B1,11 ; B2,12 ; B3,13 ) с размерами N1 1 100 , N2 1 50 , N3 1 20 векто ров. Моделирование обучающих выборок окрашиванием и оценивание (7) и (8) реализуется программой вида 13
b1=[10.7 0.7 1] [u1,v1]=eig(b1) x1=randn(2,100); a1=u1*v1^(1/2)*u1' y1=a1*x1 for j=1:100 y1(1,j)=y1(1,j)+1; y1(2,j)=y1(2,j)+1; end M=mean(y1') r1=cov(y1')
% коррелЯционнаЯ матрица
% оператор окрашиваниЯ
% математические ожиданиЯ
% сумма (7) % сумма (8)
В одном из экспериментов получены 1 1 1 0.8862 –0.6223, B 1 2 1 1.1979 0.8703, B 1 3 1 1.0666 0.6698 , B –0.6223 1.1161 0.8703 1.1782 0.6698 1.4834 1 1 1 0.9899, М 1 2 1 –2.0866, М 1 2 1 –3.2481 , М 1.0546 –1.1083 0.2734
На рис. 7 показаны истинные (см. рис. 4) и полученные при обуче нии эллипсы рассеивания. Полученные эталоны классов тем больше отличаются от истинных, чем меньше размер обучающей выборки. y 6 4 3
1
2 x
0 –2 2 –4 –6 –6
–4
–2
0
2
4
6
Рис. 7. Эллипсы рассеивания: c = 0.01
14
y 6 3
1
4 2
x
0 –2 2 –4 –8
–6
–4
–2
0
2
4
6
Рис. 8. Эллипсы рассеивания: c = 0.004
На рис. 8 показаны сечения круговых (декоррелированных) рассеи ваний, полученных преобразованиями (9), истинные окружности – на рис. 6. Как и исходные плотности (рис. 7), в большей степени пересека ются плотности второго и третьего классов.
15
3. ВЕРОЯТНОСТЬ ПОПАДАНИЯ В ЗАДАННУЮ ОБЛАСТЬ В распознавании образов стандартная задача – рассчитать вероят ность p попадания случайного вектора X в заданную область W. Если плотность распределения f 1 X 2 известна, вероятность p 5 p 1X 6 72 5 f 3 X 4 dX
8
1
рассчитывается nкратным интегрированием плотности. В общем слу чае это трудоемкая задача, решаемая численным интегрированием. Относительно простой случай – двумерное нормальное распределе ние декоррелированного вектора: X 3 4 1 5,I 2 . Область W ограничивает ся, как правило, двумя прямыми. На рис. 9 показаны области H1, H2, H3 с границами y1 1 25x 2 1 , y2 1 2x 3 1 , y3 1 x 2 2 , пересекающимися в точке x0 1 21/2 , y0 1 3/2 . Вектор X имеет плотность 24 2 3 6 1 x 5 mx 2 1 y 5 my 2 6 1 f 1 x, y 2 7 5 exp 85 9, 2
2 2 6 6 mx 1 21 , my 1 1 .
y 6
y1 H3
4
H1
2
y0
0
x
x0 y3
–2
y2
–4
H2
–6 –6
–4
–2
0
2
4
6
Рис. 9. Области попадания
Условия принадлежности вектора [точки 1 x, y 2 ] области Hi : x 1 x0 X 1 H1, если x 2 x 0
16
и y 1 y2, и y 1 y1;
x 1 x0 и y 2 y2, X 1 H2, если x 2 x и y 2 y ; 0 3 X 1 H3, если x 1 x0 и y 1 y1, Вероятности выполнения этих неравенств
p1 5 p1X 6 H12 5
11
88
f 3 x, y 4 dxdy 7
x0 y2
9
x0
y 2 y3 .
1
8 8 f 3 x, y 4 dxdy 5
21 y1
1 58 1 x 7 122 68 1 1 1 x 24 exp
3
dx 7 2 8 2 x 8
(10)
0
x0 58 1 x 7 122 68 1 7 31 9 1 95x 9 224 exp 9 2 dx ; 2 12 8 8
p2 5 p1X 6 H22 5
7
1
y2
88
x0 21
f 3 x, y 4 dxdy 7
(11)
x0 y3
8 8 f 3 x, y 4 dxdy 5
21 21
x0 1 36 1 x 5 122 46 36 1 x 5 122 46 1 1 8 1 9x 2 exp 9 5 8 5 dx x 1 exp 1 2
9 dx; (12) 2 6 2 6 2 x 2 6 6 2
0
p3 5 p1X 6 H32 5 9
x0 y1
88
21 21
f 3 x, y 4 dxdy 7
x0
1
8 8 f 3 x,y 4 dxdy 5
21 y3
x0 58 1 x 7 122 68 1 1 7 1 5x 2 2 1 x 7 124 exp 3
dx 2 8 , 2 12 8
51x2 6
x
3 t2 4 3 x 4 1 1 1 exp 9 7 dt 6 8 erf 9
2 2 2 12 2 2
(13)
– интеграл вероятности,
erf 1 x 2 3
x
1 2
2 exp 4t2 dt 5 60
– функция ошибок [3]. Программа расчета подынтегрального выражения (10), показанно го на рис. 10,
17
x=0.5:0.01:4; f=1/sqrt(2*pi)*exp((x+1).^2/2).*(1/21/2*erf(x/sqrt(2))); p1=trapz(f)*0.01 f 0.1
0.05
x
0 x0 0
1
2
3
4
Рис. 10. Подынтегральное выражение (10)
Интегрирование выражения (10) от x0 до 1 имитируется интегриро ванием до x = 4 (рис. 10) по формуле трапециий. Результат: p11 1 0.1675 . Подынтегральное выражение (11) показано на рис. 11. Интегриро вание от 12 до x0 имитируется интегрированием от –1.5 до x0: x1=1.5:0.01:0.5; f1=1/sqrt(2*pi)*exp((x1+1).^2/2).*(1/21/2*erf((5*x12)/sqrt(2))); p2=trapz(f1)*0.01 p=p1+p2 f 0.1
0.05
0 –1.5
–1
x x0
Рис. 11. Подынтегральное выражение (11)
Результат: p12 1 0.0145 ; вероятность попадания в область H1 p1 1 p11 2 p12 1 0.1820 . Так же рассчитываются интегралы (12) и (13): p2 1 p21 2 p22 1 0.1411 2 0.2391 1 0.3801 , p3 1 0.4379 . Сумма вероятностей попаданий в области H1 , H2 , H3 p 1 p1 2 p2 2 p3 1 1 .
18
4. РАЗДЕЛЯЮЩИЕ ФУНКЦИИ Система распознавания (классификатор) описывается разделяющи ми функциями (РФ) g j 1 X 2 , j 1 1,...,k . Пространство признаков разби вается на k областей 1 j , j 1 1,...,k ; если наблюдения X 12i , класси фикатор относит их к iму классу. Этой процедуре соответствует вычис ление k РФ (рис. 12), нахождение максимальной из них и классифика ция по правилу: если gi 1 X 2 3 g j 1 X 2 для всех i 1 j , принимается реше ние в пользу Hi ( i го класса).
X
12
415
11
415
123
415
11
Рис. 12. Классификация по РФ
В качестве РФ естественно использовать апостериорную вероятность g j 1 X 2 3 p 1 Hj | X 2 3
или ее модификации
p 1 X | Hj 2 p 1 Hj 2 k
4 p 1 X | Hj 2 p 1 Hj 2
(14)
j 11
g j 1 X 2 3 p 1 X | Hj 2 p 1 Hj 2 ,
g j 1 X 2 3 log p 1 X | Hj 2 4 log p 1 Hj 2. (15) 1 Соприкасающиеся области 1i , j имеют границу, описывающую ся уравнением gi 1 X 2 3 g j 1 X 2 , (16) общим для любого из перечисленных заданий РФ. В случае двух классов используют одну РФ
g 1 X 2 3 g1 1 X 2 4 g2 1 X 2 . g X 3 0 Если 1 2 , принимается решение в пользу H1 . В многомерном случае РФ (15) T n 1 1 g j 1 X 2 3 4 ln 1 25 2 4 ln 1 det B j 2 4 1 X 4 6 j 2 B 1j 1 1 X 4 6 j 2 7 ln p 1 Hj 2 . 2 2 2 19
4.1. Некоррелированные признаки Пусть признаки некоррелированы и имеют одинаковые диспер 1 сии 12j 2 12 . Корреляционные матрицы B j 1 22I , B 1j 1 1 2 I , det B j 1 22N . 2 Кластерыгиперсферы с центрами 1 j . Для всех индексов j слагаемые n 1 3 ln 1 24 2 и 3 ln 1 det B j 2 одинаковы, поэтому 2 2 2 X 3 4j T 11 1 g j 1 X 2 3 4 1 X 3 4 j 2 B j 1 X 3 4 j 2 5 ln p 1 Hj 2 6 3 5 ln p 1 Hj 2 6 2 272 2
N
1 3 4 2 1 Xi 4 5ij 2 6 ln p 1 Hj 2 , 27 i 11
8
2
X 1 2 j – квадрат расстояния между точками X и 1 j в nмерном евк лидовом пространстве. Если классы равновероятны ( p 1 Hj 2 3 1/ k ), мак симальному значению РФ соответствует минимальное значение функции N
2
1 1 Xi 3 4ij 2 . 252 i 11 Таким образом, измеряются евклидовы расстояния от вектора призна ков Xi до каждого из векторов средних 1 j и принимается решение в пользу ближайшего. Векторы 1 j – эталоны классов. Метод классифи кации называется распознаванием по минимуму расстояния. На практике нет необходимости вычислять расстояния:
gj 1 X 2 3
X 3 4j
2
5 1X 3 4j 2
T
6
1 X 3 4 j 2 5 XT X 3 XT4 j 3 4Tj X 6 4Tj 4 j 5
1 XT X 2 23Tj X 4 3Tj 3 j ;
слагаемое XTX одинаково для всех j , поэтому g j 1 X 2 3 WjT X 4 Wj0 ,
(17)
где Wj 1 12 2 j , Wj 0 3 4 1 2 5Tj 5 j 6 ln p 1 Hj 2 . Функция (16) – линейная, 27 3 граница между кластерами находится из уравнения (17): WiT X 1 WjT X 2 Wi0 1 Wj0 3 0 ; p 1 Hi 2 1 1 4 3Tj X 4 3Ti 3i 5 3Tj 3 j 5 62 ln 70. 2 2 p 1 Hj 2 Это уравнение приводится к виду
13
T i
2
W 20
T
1 X 3 X0 2 4 0 ,
(18)
W 1 2i 3 2 j , X 0 6
32 1 4i 5 4 j 2 p 1 Hi 2 1 4 7 4 5 ln 1 i j2 . 2 2 p 1 Hj 2 4i 5 4 j
Уравнение (18) описывает гиперплоскость (nмерную плоскость), ортогональную вектору W, проходящую через точку X0 . Вектор W – прямая, соединяющая центры кластеров 1i и 1 j . Если p 1 Hi 2 3 p 1 Hj 2 , точка X0 находится посередине отрезка; если p 1 Hi 2 3 p 1 Hj 2 , точка X0 смещается к 1 j . Пример 6 Декоррелированные плотности распределения признаков трех рав новероятных ( p 1 Hi 2 3 1/3 ) классов из примера 4 (рис. 5 и 6) имеют оди наковую дисперсию 12 2 1 и различаются центрами кластеров 3Tj 4 15mjx
mjy 26 . Вследствие равновероятности классов точки
1 1 4i 5 4 j 2 , 2 –0.1188 –0.8349 –2.7794 X0 1 H1, H2 2 3 , X0 1 H1, H3 2 3 , X0 1 H2, H3 2 3 . 0.7941 1.6400 0.6083 X0 3
Уравнения (18) границ между областями классов 1j (рис. 13) 3.8890x 1 2.0633y 2 1.1765 3 0 (между H1 и H2 ), 5.3212x 1 0.3714y 1 3.8336 2 0 (между H1 и H3 ), 1.4322x 1 1.6919y 2 5.0098 3 0 (между H2 и H3 ), (19) записываются с учетом расчетных коэффициентов и свободных членов 13.8890 2 15.3212 2 W12 3 41 5 42 3 6 , W13 3 41 5 43 3 60.3714 7 , 82.0633 79 8 9
1 1.4322 2 W23 3 42 5 43 3 6 , 8 51.691979 4 30.1188 5 T W12 X0 6 13.8890 2.06332 7 6 1.1765 , 9 0.7941 8
4 30.83495 T W13 X0 6 15.3212 0.37142 7 6 33.8336 , 9 1.6400 8
4 32.7794 5 T W23 X0 6 11.4322 31.69192 7 6 35.0098 . 9 0.6083 8
На рис. 13 выделены линейные границы областей классификации, перпендикулярные отрезкам, соединяющим центры кластеров Mj, про ходящие посередине отрезков. 21
y 6 H3 4 H1 M1
2 M3 0
x
M2
–2
y2
–4
H2
–6 –6
–4
–2
0
2
4
6
Рис. 13. Эллипсы рассеивания: c = 0.003; области классификации y 6 H3 4 H1
2
x
0 –2
y2
–4
H2
–6 –6
–4
–2
0
2
4
6
Рис. 14. Эллипсы рассеивания: c = 0.003; области классификации
Если классы неравновероятны, границы сдвигаются в сторону цент ров менее вероятных кластеров за счет сдвига точки X0 в (18). Напри мер, на рис. 14 показаны границы при изменении вероятностей с p 1 Hi 2 3 1/3 до p 1 H1 2 3 1/2 , p 1 H1 2 3 1/3 , p 1 H1 2 3 1/6 . Их уравнения отличаются от уравнений (19) свободными членами: 3.8890x 1 2.0633y 2 0.7708 3 0 (между H1 и H2 ), 5.3212x 1 0.3714y 1 4.9324 2 0 (между H1 и H3 ), 1.4322x 1 1.6919y 2 5.7030 3 0 (между H2 и H3 ).
22
0.08 0.06 0.04 0.02 0 5 0 –5
–6
–4
–2
0
2
4
Рис. 15. Совместная плотность признаков
Совместная плотность показана на рис. 15 (сравните с плотностью на рис. 5). 4.2. Коррелированные признаки Случай одинаковых корреляционных матриц и различных матема тических ожиданий: РФ (15) записываются T n 1 1 g j 1 X 2 3 4 ln 1 25 2 4 ln 1 det B 2 4 1 X 4 6 j 2 B 11 1 X 4 6 j 2 7 ln p 1 Hj 2 . 2 2 2 Если p 1 Hj 2 3 1/ k , то существенная часть РФ имеет вид T 1 X 4 5 j 2 B 11 1 X 4 5 j 2 3 rj2 . 1 (20) 2 Процедура классификации формально сводится к нахождению мини мального квадратичного махаланобисова ri2 расстояния от вектора признаков до центров кластеров 1 j . Слагаемое XB 11XT в квадратичной форме rj2 не зависит от j , поэтому
gj 1 X 2 3 4
rj2 1 223Tj B 11X 4 3Tj B 113 j .
Уравнение РФ приводится к виду g j 1 X 2 3 WjT X 4 Wj0 ,
(21)
Wj 1 B 112 j , Wj0 3 4 1 5Tj B 115 j 6 ln p 1 Hj 2 . Граница между кластерами 2 (рис. 16) WT 1 X 3 X0 2 4 0 ,
23
где W 3 B 11 1 4i 5 4 j 2 ; X0 5
3i 4 3 j p 1 Hi 2 1 . 3i 6 3 j 2 4 ln 1 T 11 2 p H 1 2 j 1 3 i 4 3 j 2 B 1 3i 4 3 j 2 y
6 4 H2 2
M1
H1
x
0 –2
M2
–4 –6 –6
–4
–2
0
2
4
6
Рис. 16. Эллипсы рассеивания, области классификации; p(H1) = p(H2)
Вектор W не совпадает с отрезком, соединяющим центры кластеров, поэтому граница не ортогональна ему. 4.3. Произвольные корреляционные матрицы Если Bi 1 B j , 1i 2 1 j , кластеры различаются центрами, ориентаци ей и объемом. Разделяющие функции T n 1 1 g j 1 X 2 3 4 ln 1 25 2 4 ln 1 det B j 2 4 1 X 4 6 j 2 B 1j 1 1 X 4 6 j 2 7 ln p 1 Hj 2 2 2 2 могут быть приведены к виду
1 g j 1 X 2 3 4 XT B 1j 1X 5 B 1j 16 jX 5 Wj0 , 2
(22)
1 1 где Wj 0 3 4 5Tj B 1j 15 j 4 lndet B j 6 ln p 1 Hj 2 . Уравнение (22) описывает 2 2 nмерную поверхность второго порядка – эллипсоид, параболоид, ги перболоид.
24
4.4. Вероятности ошибок Качество системы распознавания можно оценить вероятностями правильной классификации p 1 Hi | Hi 2 и вероятностями ошибок клас сификации p 1 Hi | Hj 2 , i 1 j , i, j 1 1,...,k . В общем случае вероятности должны рассчитываться интегрированием плотности распределения признаков f 1 X | Hj 2 по соответствующим областям классификации 1i . Строгое интегрирование, как правило, затруднительно: например, n мерную нормальную плотность вида (1) не удается проинтегрировать по гиперплоскости, тем более – по поверхности второго порядка. Как и во многих других случаях, задача упрощается декорреляцией вектора признаков. Декоррелирующее преобразование приводит РФ (20) и (22) к виду (17) с дисперсией 12 2 1 g j 1 X 2 4 53jT X 6 Wj0 , (23)
1 где Wj0 4 5 63jT 63j 7 ln p 1 Hj 2; 21j – вектор средних, преобразованный 2 при декорреляции. Расчет вероятностей базируется на правиле мини мума расстояния от вектора X до центров кластеров 1 j . Реальная альтернатива расчетам – статистическое моделирование системы распознавания. Пример 7 Уравнения (15) границ между областями классов 11 , 12 , 13 в при мере 6 (рис. 13) 3.8890x 1 2.0633y 2 1.1765 3 0 (между H1 и H2 ), 5.3212x 1 0.3714y 1 3.8336 2 0 (между H1 и H3 ), 1.4322x 1 1.6919y 2 5.0098 3 0 (между H2 и H3 ). Векторы признаков имеют круговое рассеивание с единичной дисперси ей и средними (пример 4) М1 1
1.8257 , –2.0633 , –3.4955 . М2 1 М3 1 1.8257 –0.2376 1.4543
Пусть моделируется вектор признаков класса H1 (рис. 17): n=1000 x=randn(1,n)+1.8257; % координата точки по оси x y=randn(1,n)+1.8257; % координата точки по оси y Условия принадлежности точки x 1 i 2 , y 1 i 2 , i 1 1,...,n , области 11 3.8890x 1 2.0633y 2 1.1765 , 5.3212x 1 0.3714y 1 3.8336 2 0 ;
25
области 12 1.4322x 1 1.6919y 2 15.0098 , 3.8890x 1 2.0633y 2 1.1765 ; области 13 1.4322x 1 1.6919y 2 15.0098 , 3.8890x 1 2.0633y 2 1.1765 В одном из экспериментов результаты работы программы syms x y ezplot(‘1.1765+3.8890*x+2.0633*y=0’) hold on ezplot(‘3.8336+5.3212*x+0.3714*y=0’) ezplot(‘5.0098+1.4322*x1.6919*y=0’) n=10000 x=randn(1,n)+1.8257; y=randn(1,n)+1.8257; plot(x,y) pause
p1=0;p2=0;p3=0 for i=1:n if 3.8890*x(i)+2.0633*y(i)>1.1765 if 5.3212*x(i)+0.3714*y(i)>3.8336 p1=p1+1; end end if 3.8890*x(i)+2.0633*y(i)<1.1765 if 1.4322*x(i)1.6919*y(i)>5.0098 p2=p2+1; end end if 3.8890*x(i)+2.0633*y(i)<1.1765 if 1.4322*x(i)1.6919*y(i)<5.0098 p3=p3+1; end end end p1=p1/n p2=p2/n p3=p3/n
26
показаны на рис. 17; оценки вероятностей классификации 1p 1 H | H 2 3 0.985 , 1p 1 H | H 2 3 0.013 , 1p 1 H | H 2 3 0.001 . 1 1 2 1 3 1 Множество точек наблюдений (оператор PLOT) показано отрезками, соединяющими n точек. Можно заметить, что сумма оценок вероятнос тей не равна единице. Погрешность оценивания объясняется, повиди мому, тем, что коэффициенты уравнений (19) записаны с точностью четыре десятичных знака, что может оказаться недостаточным для точ ного задания границ. y 6 H1
H3
4 2
x
0 –2 H2 –4 –6 –6
–4
–2
0
2
4
6
Рис. 17. Массив наблюдений, границы областей классов; n = 1000
Аналогичное моделирование векторов признаков классов H2 и H3 дает оценки 1p 1 H1 | H2 2 3 0.014 , 1p 1 H2 | H2 2 3 0.852 , 1p 1 H3 | H2 2 3 0.134 ; 1p 1 H | H 2 3 0.002 , 1p 1 H | H 2 3 0.128 , 1p 1 H | H 2 3 0.868 . 1 3 2 3 3 3 Вероятности ошибок: 1p 1 H2 | H1 2 3 1p 1 H1 | H2 2 , 1p 1 H3 | H1 2 3 1p 1 H1 | H3 2 , 1p 1 H | H 2 3 1p 1 H | H 2 . 3
2
2
3
Наибольшая вероятность ошибки классификации наблюдается при сопоставлении классов H2 и H3 . Рассчитать вероятности при сопоставлении классов Hi , Hj можно следующим образом. Расстояние между центрами 1i , 1 j двух сферических кластеров n
rij 3
5 1 xik 4 xjk 2
k 11
2
,
(24)
xk – одна из координат в nмерном декартовом пространстве. Граница между областями 1i , 1j ортогональна отрезку mimj , соединяющему
27
центры, и проходит посередине отрезка. Если ввести новую декартову систему с началом в точке 1i , такую, чтобы ось 0X1 совпала с отрез ком mimj , то по оси 0X1 точка 1 j сместится в точку r 1 rij , граница станет гиперплоскостью, пересекающей отрезок в точке r /2 . На рис. 18 показан двумерный случай: новые оси x , y ; точки 0 , r – новые центры кластеров; окружности – эллипсоиды рассеивания; AA – граница, раз деляющая области 11 , 12 (в двумерном случае гиперплоскость вырож дается в прямую). y
A
H1
H2
x 0
r
r/2
A Рис. 18. Двумерный случай
Исходная nмерная плотность преобразуется в плотность f 1 X 2 5 1 26 2
1n /2
3
48 exp37 1 x 7 m 2 /24 .
exp 7 1 x1 7 rij 2 /2 2
n
2
k
k
k 22
Вероятность правильного распознавания класса Hi теперь рассчиты вается как вероятность того, что значение x1 не превзойдет величину rij /2 независимо от значений других признаков: 1 1 n r p 1 Hi | Hi 2 3 f 1 x1 2 dx1 ... f 1 xk 2dx2...dxn 3 3 14 ij 25 , 2x1 3rij 41 41 k22 627
5
5 54
3 rij 4 p 1 Hj | Hi 2 5 1 6 7 8 9 . (25)
2 В паре Hi , Hj классы перестановочны. Пример 8 В примере 7 при сопоставлении H1 и H2 получены следующие рас стояние (24) и расчетные вероятности (25):
28
r 3 r12 3
11.8257 4 2.063322 4 11.8257 4 0.2376 22 3 4.4024 ,
p 1 H1 | H1 2 3 p 1 H2 | H2 2 3 4 1 2.2012 2 3 0.9861 ,
p 1 H2 | H1 2 3 p 1 H1 | H2 2 3 1 4 5 1 2.20122 3 0.0139 ; при сопоставлении H1 и H3 r 3 r13 3
11.8257 4 3.495522 4 11.8257 5 1.454322 3 5.3342 ,
p 1 H1 | H1 2 3 p 1 H3 | H3 2 3 4 1 2.66712 3 0.9962 , p 1 H3 | H1 2 3 p 1 H1 | H3 2 3 1 4 5 1 2.66712 3 0.0038 ;
при сопоставлении H2 и H3 r 3 r13 3
1 42.0633 5 3.495522 5 1 40.2376 4 1.454322 3 2.2166 , p 1 H2 | H2 2 3 p 1 H3 | H3 2 3 4 11.1083 2 3 0.8661 ,
p 1 H3 | H2 2 3 p 1 H2 | H3 2 3 1 4 5 11.1083 2 3 0.1339 .
Экспериментальные результаты, полученные в примере 7, не проти воречат расчетным. Значения расчетных вероятностей P 1 Hi | Hi 2 зави сят от рассматриваемых сочетаний классов. 1j и В процессе обучения получаются оценки (7) центров кластеров 1 1 1 1 j и B j – оценки (8) корреляционных матриц. Последующая декор 1 j трансформирует в единичные, векто реляция признаков все матрицы B 1 1 ры 1 j – в векторы 1 j (рис. 8). Закон распределения случайного смещения рассчитать сложно [6], поэтому часто ограничиваются экспериментом. 4.5. Распознавание как проверка гипотез Уравнения РФ (20), (22), (23) содержат статистики вида 1 2 3Tj X ,
(26)
где X – случайный вектор наблюдаемых значений; Mj – эталон класса Hj . Такие статистики появляются в задачах проверки статистических гипотез, в статистической радиотехнике они описывают согласованную фильтрацию или корреляционный прием [2,7]. В статистической ра диотехнике статистика (26) при использовании модели белого шума записывается 1 2 ST X 2 XTS ,
29
где S – вектор отсчетов (неслучайного) сигнала; X – вектор отсчетов 2 случайного сигнала на входе; статистика 3 4 5 S, 6 I . Если отсчеты сигнала s1, s2,..., sn трактовать как его признаки, а вектор S – как его эталон, то задача проверки гипотез трансформируется в задачу распоз навания сигналов. Поиску максимальной РФ при распознавании соот ветствует поиск максимальной статистики при проверке гипотез: про цедуры следуют из правила максимума апостериорной вероятности. Пусть проверяются гипотезы
1
2
Hi : Z 1 X 2 Si , Hj : Z 1 X 2 Sj , X – белый шум с единичной дисперсией. Логарифм отношения правдоподобия
35 1 n 4 exp 76 1 zk 6 sik 22 58 f 1 Z | Hi 2 95 2 k 11
5 ln 1 Z 2 ln ln 35 1 n f 1 Z | Hj 2 24 5 zk 6 sjk 2 8 exp 7 6 1 2 95 k11
5
3
n
n
n
k 11
k 11
k 11
6 zk 1 sik 4 sjk 2 4 12 6 sik2 5 12 6 sjk2 3 ZTGij 5 12 STj Sj 4 12 STi Si
содержит статистику проверки гипотез 1 ij 2 ZT Gij ,
в которой Gij 1 Si 2 Sj . Математическое ожидание статистики:
m | Hi 1 STi Gij , m | Hj 1 STj Gij ,
дисперсия: 12 2 G T ij Gij . Отношение сигналшум по мощности: 2 GTij Gij 2 m | Hi 3 m | Hj 2 1 1 2 d 4 4 ij
52
GTijGij
2
4 GTij G ij .
Отношение сигналшум dij , записанное в виде n
dij 3
5 1 sik 4 sjk 2
k 11
30
2
,
(27)
есть расстояние rij между сигналами Si и Sj в декартовой системе. Со поставление расстояний (27) и (24) показывает их равенство, если ко ординаты центров кластеров xik считать значениями сигналов sik . Пример 9 В двумерном случае при проверке гипотез H1 и H2 и белом шуме с единичной дисперсией отсчеты сигналов
z1 | H1 3 4 1 s11,12 , z2 | H1 3 4 1 s21,12 ; z1 | H2 3 4 1 s12,12 , z2 | H2 3 4 1 s22,12 ; 1s 2 1s 2 1z 2 Z 3 4 1 5 , S1 3 S | H1 3 4 11 5 , S2 3 S | H2 3 4 12 5 . 6s21 7 6s22 7 6 z2 7 Логарифм отношения правдоподобия ln 3 1 Z 2 4 ln 2 2 2 2 ; E1 , E2 1 E1 2 s21 3 s22 1 s11 1 s12
f 1 Z | H2 2 f 1 Z | H1 2 E2
4 ZTG 5 E2 6 E1 ,
– мощность сигналов S1 , S2 ;
2s 1 s 3 G 4 5 21 11 6 – вектор согласованной фильтрации. Статистика: 7 s22 1 s21 8
3 4 ZTG 5 6 1 m, 7 2 ,
где m | H1 1 S1TG , m | H2 1 ST2 G ; 12 2 GT B 1Z1G 2 GT G . Отношение сигнал шум d2 4
1 m | H2 3 m | H1 22 52
определяет вероятность правильного решения
d p 1 H1 | H1 2 5 p 1 H2 | H2 2 5 6 37 48 . 92
В примере 7 центры кластеров классов H1 , H2 , H3 11 2
1.8257 –2.0633 –3.4955 12 2 13 2 1.8257 , –0.2376 , 1.4543 .
При проверке трех пар гипотез о сигналах – центрах кластеров получа ются значения отношения сигналшум (27) H1 и H2 : d 1 4.4024 , H1 и H3 : d 1 5.3342 , H2 и H3 : d 1 2.2166 , совпадающие со значениями расстояний (24) в примере 8.
31
5. ПАРАМЕТРИЧЕСКОЕ ОБУЧЕНИЕ БЕЗ УЧИТЕЛЯ При обучении без учителя (самообучении) используются непомечен ные (неклассифицированные) выборки признаков с плотностью распре деления f 1X2 3
k
5 p 1 Hj 2 f 1 X j | Hj ;4 j 2 .
(28)
j 11
Анализируя множество векторов Xi , i 1 1,..., K , необходимо оценить k векторов параметров, т. е. получить классифицированные векторы 1 j , j 1 1,...,k . Такая задача принципиально сложнее, чем обучение с 1 учителем. Ее решение может оказаться полезным при разработке адап тивных систем распознавания, в которых признаки нестационарны. Пусть вероятностная структура задачи известна [5]: – заданы априорные вероятности p 1 Hj 2 и плотности f 1 Xj ; 3 j 2 для всех k классов; – неизвестны k векторов 1 j . Плотность смеси (28) называется идентифицируемой, если из нера венства 1 2 11 следует f 1 X | 3 2 4 f 1 X | 31 2 . Неидентифицируемая плот ность оказывается одной и той же при различных параметрах 1 , что может сделать обучение невозможным. Например, при равенстве апри орных вероятностей математические ожидания в плотности 2 36 1 x 5 m 22 64 p 1 H 2 63 1 x 5 m2 2 64 1 2 f 1 x; 7 2 8 exp 5 exp 5 9 2 2 2 2 6 6 6 6 не могут быть идентифицированы, так как при взаимной замене m1 и m2 плотность не изменяется. Пусть имеется множество непомеченных обучающих векторов
p 1 H1 2
XT 5 16 X1 X2
1 x11 x12 3x x22 ... Xk 27 5 3 21 ... ... 3 x x k2 63 k1 T
... x1N 2 ... x2N 4 4 ... ... 4 , ... xkN 74
извлеченных из идентифицируемой по неизвестным векторам средних 1 j смеси с плотностью (1)
f 1 X 2 3 1 25 2
32
1n /2
1 det B 211/2 exp
3
6
4
1 1 X 6 7 2T B11 1 X 6 7 2 . 2
1 , пос В общем случае неизвестная матрица B заменяется ее оценкой B ле чего применяется декоррелирующее преобразование (4), приводящее корреляционную матрицу преобразованных наблюдений к виду B=I. Независимость наблюдений позволяет для оценивания новых векторов 21j применить метод моментов [6,7]. Суть метода состоит в приравнивании начальных моментов mn и 1 n порядков n 1 1,...,k . Для каждого признака выборочных моментов m составляется система нелинейных уравнений с k неизвестными. Погреш 1 иm 1 n. ности метода обусловливаются погрешностями оценивания B Для несмещенных состоятельных оценок погрешности уменьшаются с увеличением размера выборки. Центральные моменты нормальной случайной величины x с плот ностью f 1 x 2 3 4 1 m;12 равны 340 при нечетном n, 5n 6 7 491 n 8 12 !! при четном n. При n 1 1 , n 1 2 , n 1 3 , n 1 4 , n 1 5 начальные моменты 2 m1 3 4 1 x 2 3 m, m2 5 6 3 x2 4 5 6 391 x1 7 m 2 4 5 6 3 x1 27 2mx1 7 m2 4 5 827 m2, 3 m3 5 6 3 x3 4 5 6 931 x1 7 m 2 4 5 6 3 x1 3 7 3mx1 2 7 3m2x1 7 m3 4 5 3m82 7 m3 , 4 m4 5 6 3 x4 4 5 6 381 x1 7 m 2 49 5 6 3 x1 4 7 4mx1 3 7 6m2x1 2 7 4m3x1 7 m4 4 5
1 324 3 6m222 3 m4 , 5 m5 5 6 3 x5 4 5 6 381 x1 7 m 2 49 5 6 3 x1 57 5mx1 4 7 10m2x1 37 10m3x1 27 5m4x1 7 m5 4 5
1 15m24 3 10m322 3 m5 . Пример 10 Пусть наблюдения есть смесь независимых нормальных случайных величин x1 3 4 1 52;12 , x2 3 4 1 2;12 , x3 3 4 15;12 с вероятностями p1 1 p2 1 1/4 , p3 1 1/2 . Пусть три первых выборочных момента получе ны без погрешностей: 1 1 1 2 1 2 3 1 2 3 1 5 1 2.5, m 4 4 2
1 2 1 1 4 2 1 4 2 1 25 1 14.5, m 4 4 2 1 3 1 2 1 8 3 1 8 3 1 125 1 62.5. m 4 4 2 33
Система уравнений относительно средних mi
1 1 1 m1 1 m2 1 m3 2 2.5 , 4 4 2 1 2 1 2 1 2 m 1 1 m2 1 m3 2 14.5 , 4 4 2 1 3 1 3 1 3 m 1 1 m2 1 m3 2 62.5 4 4 2 в пакете SYMBOLIC TOOLBOX имеет следующие шесть реше ний 1 m1;m2;m3 2 , полученных программой syms m1 m2 m3 [m1,m2,m3]=solve(‘1/4*m1+1/4*m2+1/2*m3=2.5’, . . . ‘1/4*m1^2+1/4*m2^2+1/2*m3^2=14.5’,’1/4*m1^3+1/4*m2^3+1/ 2*m3^3=62.5'):
1 32;2;52, 12; 32;52, 15.8233; 32.0982;3.13752, 1 32.0982;5.8233;3.13752,
15.6375 3 1.7853j;5.6375 4 1.7853j;40.6375 4 3.101 j 2 , 15.6375 3 1.7853j;5.6375 3 1.7853j;40.6375 3 3.101 j 2 . 35
35
Кроме первого истинного решения (–2; 2; 5), существуют еще три дей ствительных решения системы. Этот пример показывает, что при обу чении без учителя необходимы дополнительные априорные сведения, на основании которых можно выбрать наиболее подходящее решение. Пример 11 В примере 3 рассматриваются двумерные признаки X трех классов с
112 2 12 3 2 13 3 X 3 4 1 5i, Bi 2 , 31 4 516 , 42 5 6 117 , 43 5 60.57 , единичной дисперсией 8 9 7 8 8 9 и корреляционными моментами R1 1 20.7 , R2 1 20.7 , R3 1 0.5 . Обуча ющие выборки Yi с размерами N1 1 100 , N2 1 50 , N3 1 20 генерируются программами вида N1=100 b1=[10.7 0.7 1] for j=1:N1 m1(1,j)=1; m1(2,j)=1; end [u1,v1]=eig(b1) a1=u1*v1^(1/2)*u1' 34
x1=randn(2,N1); y1=a1*x1+m1; Декорреляция векторов Yi : M1=mean(y1') b1=cov(y1') [u1,v1]=eig(b1) a1=u1*v1^(1/2)*u1' z1=a1*y1; M1=mean(z1') приводит их (в одном из экспериментов) к векторам Zi 4 5 1 63i ,I 2 ,
12.1068 2 2 12.87523 2 13.60323 413 5 6 , 542 6 7 11.93318 , 543 6 7 1.7800 8 . 9
82.1518 79 9
(29)
Непомеченная двумерная обучающая выборка с плотностью (28)
f 1 x, y 2
5
3 4 1 x 6 2.1068 22 7 1 y 6 2.1518 22 5 1 810 96
7 exp 9
2 817 2
3 1 x 5 2.8752 22 5 1 y 5 1.933122 4 5 75 exp 6 8 6 7 17 2 9
4 1 x 6 3.6032 22 6 1 y 7 1.7800 22 5 38 2
exp 9 7 9
8 17 2
генерируется конкатенцией выборок: for j=1:N1 Z1(j)=randn(1,1)+2.1068; end for j=1:N2 Z2(j)=randn(1,1)2.8752; end for j=1:N3 Z3(j)=randn(1,1)3.6032; end Z=cat(2,Z1,Z2,Z3); Оценки начальных моментов первых трех порядков: MM1=mean(Z) MM2=mean(Z.^2) MM3=mean(Z.^3) 6
35
равны
10.9770 2 2 10.4755 3 66 X 7 4 6.8356 5 , 55 Y 6 3 4.98014 . 37.6361 4 4 115.7244 5 7 8 8 9 Системы уравнений относительно координат xi , yi центров кластеров
10 5 2 x1 1 x2 1 x3 2 30.4755 , 17 17 17
10 5 2 y1 1 y2 1 y3 2 0.9770 , 17 17 17
10 2 5 2 2 2 x 1 1 x2 1 x3 2 6.8356 , 17 17 17
10 2 5 2 2 2 y 1 1 y2 1 y3 2 4.9801 , 17 17 17
10 3 5 3 2 3 10 3 5 3 2 3 x 11 x2 1 m3 2 315.7244 ; y 11 y2 1 y3 2 7.6361 ; 17 17x 17 17 17x 17 решаются программами вида syms x1 x2 x3 [x1,x2,x3]=solve(’10/17*x1+5/17*x2+2/17*x3=0.04755',… ’10/ 17*x1^2+5/17*x2^2+2/17*x3^2=6.8356',… ’10/17*x1^3+5/17*x2^3+2/17*x3^3=15.7244')
Из действительных решений систем: x1=
.55569627289507491293869995623197 1.6734354280953904823684037609110 1.6735185400632595264989719755815 1.0834825175452003582288425182343 x2 = 4.1723654051358556249646481942974 3.6554533720132137139695974895332 3.4377567498330963220818834290076 2.8236190815070341637283003659847 x3 = 3.6106821483642644977181207045835 3.2702937104439181269180250807221 3.8149508257335568272901513053885 5.6833851160415836181765383237902 y1= .61304317490893704236937737483281 1.9370035202658337614943273253214 2.5552110823885979653409128184909 2.5856054560092363240554784280777 y2 = 3.4274113988433781022904449272598 2.0166512811932466141502058370366 1.9513849744152902363433673229979 .75569053266038402298277233822051 36
y3 = 3.3292443716531304675729991923135 3.6611106016539477279038779659846 .40690702409523576415385421504007 2.7343009483952215628204612948371 наиболее близки к центрам (29) следующие:
11.6735;1.9370 2 , 1 33.4378; 32.0167 2 , 1 33.8150;3.66112 .
(30)
Выбрать именно эти оценки центров, не имея априорных данных, невозможно. Кластеры в виде эллипсов (окружностей) рассеивания с центрами (29) показаны на рис. 16 (окружности 2), с центрами (30) – окружности 3. Окружностями 1 показаны кластеры с центрами 11.82571.8257 2 , 1 32.0633; 30.2376 2 , 1 33.4955;1.45432 , рассчитанными в примере 4 для точной декорреляции исходных выборок (рис. 6). Сравнение окружно стей 1 и 2 на рис. 19 демонстрирует погрешности за счет ограниченнос ти размера выборки: смещение оценки центра кластера может быть су щественным, как для H2 . Преимущества обучения с учителем видны из сопоставления окружностей 2 и 3, а также окружностей на рис. 19 и 8. y 6
3
2
1 3
4
1
2
2 0
x 1
–2
2
–4 3 –6 –6
–4
–2
0
2
4
6
Рис. 19. Обучение без учителя. Эллипсы рассеивания
Пример 12 Вследствие смещения центров кластеров (рис. 19) сместятся грани цы областей классов 1i , что приведет к дополнительным ошибкам клас сификации. Методика расчета границ приведена в примере 6. В предыдущем примере исходные центры кластеров (окружностей 2) и их оценки при обучении без учителя 37
2 12.87523 12.0464 2 1 12.1068 2 2 12.9487 3 4 ; 31 4 5 , 31 4 5 , 12 5 6 ; 42 5 6 6 7 6 8 11.933179 8 12.3705 9 71.8788 8 72.1518 8 2 13.2398 3 1 13.60323 43 5 6 , 43 5 2 . 7 6 1.2084 8 9 8 1.7800 79 Уравнения границ между областями 1 j классов (рис. 20): исходные (рис. 20–22): 4.9951x 1 4.2493y 1 3.9914 2 0 (между H1 и H2 ), 5.2862x 1 0.6704y 1 3.7287 2 0 (между H1 и H3 ), 0.2911x 1 3.5789y 1 0.2625 2 0 (между H2 и H3 ); построенные по оценкам при обучении без учителя (рис. 20–23) 4.9820x 1 4.0849y 1 2.1607 2 0 (между H1 и H2 ), 5.7100x 1 0.3718y 1 5.1509 2 0 (между H1 и H3 ),
(31)
0.6545x 1 3.7131y 2 2.7762 3 0 (между H2 и H3 ). Точные границы (рис. 20–21) построены для центров кластеров
11.8257 2 2 12.06333 2 13.49553 31 4 5 , 42 5 6 10.2376 7 , 43 5 6 1.4543 7 . 6 1.8257 8 9 7 8 8 9 y 6 H3 3
H1
4
3 3
2 0
x
–2 –4
1 2
3
3 1
H2
–6 –6
–4
–2
0
2
4
6
Рис. 20. Обучение без учителя. Эллипсы рассеивания. Границы областей
Пример 13 Значительное смещение отрезков между центрами кластеров и гра ниц 1 и 3, особенно между областями 12 и 13 (рис. 20), приведет к погрешностям классификации. Характерный случай – наблюдения 38
признаков класса H2 : границы (31) проведены на основании оценок 1 1, 1 1 2, 1 1 3 центров кластеров, тогда как истинный центр 1
2 12.0633 3 1 2 5 2 12.87523 . 42 5 6 далек от 4 7 68 11.933179 1 0.2376 8 9 Методика расчета вероятности попадания вектора признаков в об ласть 1 изложена в разд. 3. Координаты точки пересечения границ находятся решением системы уравнений (31): a=[4.9820 4.0849 5.7100 0.3718] b=[2.1607;5.1509] x=inv(a)*b с результатом x0 1 20.9425 , y0 1 0.6205 . В дальнейшем используется координата x0 1 20.9425 . Уравнения (31) переписываются в явном виде y1 1 21.2196x 2 0.5289 (граница между H1 и H2 ), y2 1 215.3577x 2 13.8540 (граница между H1 и H3 ), y3 1 0.1763x 2 0.7477 (граница между H2 и H3 ). Вероятность попадания вектора признаков X | H2 (класса H2 ) в об ласть 11 , выделенную для класса H1 , равна
p1 | H2 3
11
55
x0 y1
f 1 x, y 2 dxdy 4
x0
1
5 5 f(x,y)dxdy 3
21 y2
9
1 58 1 x 7 2.0633 22 68 1 1 1 1.2196x 0.5289 7 0.2376 24 exp
3
dx 7 2 2 20.9425 8 8
7
1 2
10.9425
5
12
8 31 9 1 915.3577x 9 13.8540 7 0.237624exp 89
1 x 7 2.063322 68dx. 2
8
Подынтегральные выражения (рис.21) и численное интегрирование x=0.94:0.01:3; f=1/sqrt(2*pi)*exp((x+2.0633).^2/2).*(1/21/2*erf((1.2196*x 0.5289+0.2376)/sqrt(2))); p1=trapz(f)*0.01 subplot(1,2,1),plot(x,f) pause x1=1.2:0.01:0.94;
39
f1=1/sqrt(2*pi)*exp((x1+2.0633).^2/2).*(1/21/2*erf((15.3577*x1 13.8540+0.2376)/sqrt(2))); p2=trapz(f1)*0.01 p=p1+p2 subplot(1,2,2),plot(x1,f1) дают вероятность ошибки p1 | H2 1 0.0547 . Другие вероятности: x0 y3 1 y1 p2 | H2 3 f 1 x, y 2 dxdy 4 f (x, y)dxdy 3 x0 21 21 21
55
55
1 36 1 x 5 2.0633 22 64 1 7 8 1 91.2196x 9 0.5289 5 0.2376 2 exp 9 dx5 2 2 20.9425 6 6
36 1 x 5 2.0633 22 64 7 1 0.1763 5 0.7477 5 0.2376 2 exp 9 8
dx 2 6 6 12 – вероятность правильной классификации (подынтегральные функции – на рис. 22); 5
1 2
10.9425
x0 y2
p3 | H2 3
5
1 29
4 4 f 1 x, y 2 dxdy 3
12 y3
10.9425
36 1 715.3577x 7 13.8540 8 0.2376 2 7
12
76 1 0.1763x 8 0.7477 8 0.2376 24
1 x 8 2.0633 22
exp 7 dx 2 – вероятность ошибки (подынтегральная функция – на рис. 23). Вероятности ошибок классификации признаков класса H2 , пови димому, слишком велики: p1 | H2 1 0.0547 , p3 | H2 1 0.2447 . Вероят ность правильной классификации p2 | H2 1 0.7006 – на уровне резуль татов подбрасывания монеты. Действительно, в 1000 экспериментов, каждый из которых состоит в имитации пятидесяти подбрасываний монеты: X=1:49 for j=1:1000
40
x=rand(1,50) s=0 for i=1:50 if x(i)>0.5 s=s+1; end end S(j)=s; еnd k=find(S>35) hist(S,X)
% равномерная плотность
% имитация выпадения “герба”
% число “гербов” в эксперименте % число результатов m>35
в 999 случаях число выпавших “гербов” оказалось меньше 36 (рис. 24). Утверждение “в пятидесяти подбрасываниях монеты число вы павших “гербов” может быть равно 35” оказывается ошибочным с веро ятностью p=0.001. Но число m=35 соответствует вероятности pг=0.7. f
f 0.04
0.04
p = 0.0530
p = 0.0017
0.03
0.03
0.02
0.02
0.01
0.01 0
x
–2 x 0 0
2
4
0 –1.2
–1 x 0
x –0.8
Рис. 21. Подынтегральные функции f
f
0.15
0.3
p = 0.0776
0.1
0.2
0.05
0.1
0 x0
x 0
1
2
p = 0.6230
0 –10
–5
x x0 0
Рис. 22. Подынтегральные функции
41
f 0.1
p = 0.2447
0.08 0.06 0.04 0.02 0
x –7
–6
–5
–4
–3
–2
–1
0
Рис. 23. Подынтегральная функция h 120
p (m < 36) = 0.999
100 80 60 40 20 0
m 0
5 10 15 20 25 30 35 40 45
Рис. 24. Гистограмма числа выпавших “гербов”
Таким образом, вероятность p 1 0.7 слишком мала для принятия уверенного решения, так как элементарные события с вероятностями p 1 0.7 и p 1 0.5 при небольших выборках могут дать одинаковые ре зультаты.
42
ЗАКЛЮЧЕНИЕ В учебном пособии приведены основные результаты обучения в клас сическом случае нормального распределения признаков. Хорошо изу ченные в математической статистике оценки параметров нормальных распределений приводят к понятным геометрическим моделям этало нов и разделяющих функций, а также позволяют рассчитывать вероят ности решений. Отличия распределения от нормального, как правило, существенно усложняют модели классов. Повидимому, универсальным приемом практического решения задач распознавания в таких случаях является моделирование в системах класса MATLAB.
Библиографический список 1. Чистяков В. П. Курс теории вероятностей. М.: Наука, 2002. 255 с. 2. Воробьев С. Н., Осипов Л. А. Линейные системы. Расчет и модели рование. СПб.: Политехника, 2004. 125 с. 3. Дьяконов В., Круглов В. Математические пакеты расширения MATLAB. СПб.: Питер, 2001. 480 с. 4. Мартынов Н. Н., Иванов А. П. MATLAB 5.x. Вычисления, визу ализация, программирование. М.: Кудицобраз, 2000. 336 с. 5. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976. 511 с. 6. Фомин Я. А., Тарловский Г. Р. Статистическая теория распозна вания образов. М.: Радио и связь, 1986. 264 с. 7. Ивченко Г. И., Медведев Ю. И. Математическая статистика. М.: Высш. шк, 1984. 248 с.
43
Îãëàâëåíèå Введение ............................................................................... 3 1. Многомерное нормальное распределение ................................. 5 2. Параметрическое обучение с учителем .................................... 12 2.1. Неизвестные средние ..................................................... 12 2.2. Неизвестные средние и корреляционные матрицы ............... 13 3. Вероятность попадания в заданную область ............................. 16 4. Разделяющие функции ......................................................... 19 4.1. Некоррелированные признаки ......................................... 20 4.2. Коррелированные признаки ............................................ 23 4.3. Произвольные корреляционные матрицы .......................... 24 4.4. Вероятности ошибок ...................................................... 25 4.5. Распознавание как проверка гипотез ................................ 29 5. Параметрическое обучение без учителя ................................... 32 Заключение ........................................................................... 43 Библиографический список ...................................................... 43
44