Параметрическое обучение в теории распознавания образов: Учебное пособие

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования САНКТПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

С. Н. Воробьев, С. С. Осипов

ПАРАМЕТРИЧЕСКОЕ ОБУЧЕНИЕ В ТЕОРИИ РАСПОЗНАВАНИЯ ОБРАЗОВ

Учебное пособие

СанктПетербург 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