close

Вход

Забыли?

вход по аккаунту

?

Vorobjev Osipov

код для вставкиСкачать
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение
высшего профессионального образования
САНКТПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
С. Н. Воробьев, С. С. Осипов
ПАРАМЕТРИЧЕСКОЕ ОБУЧЕНИЕ
В ТЕОРИИ РАСПОЗНАВАНИЯ ОБРАЗОВ
Учебное пособие
СанктПетербург
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
Документ
Категория
Без категории
Просмотров
0
Размер файла
736 Кб
Теги
osipov, vorobjev
1/--страниц
Пожаловаться на содержимое документа