Основные определения курса Распознавание Образов (стр. 2 из 3)
Алгоритм состоит из 3х этапов.
1ый этап. Составление М последовательных разбиений пространства на сферы радиусов R1…RM, где Ri +1 = Ri – dR, где dR = Rmax/G. G – параметр, запрашиваемый пользователем (например 20). R0=Rmax – это сфера в центре обучающей последовательности, с радиусом таким, чтобы все элементы обучающей последовательности в нее умещались. На псевдокоде алгоритм можно записать следующим образом:
- Считать из файла обучающую последовательность в массив X[j], Y[j] j = 1..K (для случая если размерность пространства признаков = 2)
- Зарезервировать массив меток точек обучающей последовательности T[j], j = 1..K
- Запросить у пользователя G
- Посчитать центр обучающей последовательности и Rmax
- dR = Rmax/G
- i = 0
- R[i] = Rmax
- Цикл А (разбиение на классы с заданным размером гиперсферы)
- количество обнаруженных классов M = 0
- обнулить отметки точек обучающей последовательности
- Цикл Б (поиск всех кластеров с заданным размером гиперсфер)
i. Выбор первой непомеченной точки из обучающей последовательности = х, если непомеченных точек не осталось, выход из цикла Б.
ii. M = M + 1
iii. Цикл В (поиск оптимального центра гиперсферы)
1. r = центр всех непомеченных точек, попавших в гиперсферу радиуса R[i], c центром х
2. Померить расстояние между r и х = d,
3. x = r
4. если d меньше установленного порога (например, 0.1) – конец цикла B
iv. Записать в файл i,х,R[i], M
v. Пометить все точки, которые попали в гиперсферу с центром в х и радиусом R[i]
- Конец Цикла Б
- i = i+1
- R[i] = R[i-1] – dR
- Если R[i] < 0 конец цикла А
2й этап. Построение графика количества найденных классов от размера гиперсферы и поиск участка, где изменение радиуса «долго» не приводило к изменению количества классов.
Подобный участок графика как раз показывает, что было найдено разбиение на гиперсферы такое, что размер сфер не сильно влияет на разбиение, то есть между кластерами достаточно пустого места. Поскольку центры кластеров согласно первому этапу выбираются в местах максимального скопления элементов обучающей последовательности – выбор именно такого разбиения соответствует определению кластера.3й этап. Считывание радиуса и центров гиперсфер соответсвующих варианту выбранному на предыдущем шаге из файла созданного на 1ом шаге.
Статистические методы распознавания образов
P(a) – вероятность наступления события а
P(a,b) – вероятность того, что события а и b наступают одновременно. Если а и b – статистически независимые переменные, то P(a,b) = P(a)P(b)
если события зависимые, то P(a,b) = P(b,a) = P(a)*P(b|a) = P(b)*P(a|b)
отметим, что из этого равенства следует формула Баеса:
P(a|b) = P(b|a)*P(a)/P(b)
то есть это можно считать выводом формулы Баеса для распознавания образов, если вместо a и b подставить соответствующие события, описанные ниже.
P(a|b) – условная вероятность. Вероятность наступления события a, при условии что событие b наступило
P(Ck,x) = P(x, Ck). Вероятность того что объект имеет признаки, заданные вектором х и при этом принадлежит классу Сk
P(Ck|x) - вероятность того, что объект относится к классу Сk, при условии, что его признаки описываются вектором х. Также называется «апостериорная вероятность класса Ck», т.е. иными словами, вероятность после измерения величины х.
P(x|Сk) - вероятность того, что объект имеет признаки, описываемые вектором х, при условии что объект относится к классу Ck
P(Ck) – вероятность того, что данный объект относится к классу Ck. Также называется «априорная вероятность класса Ck»
P(x) – вероятность того, что признаки произвольного объекта из множества объектов задачи распознавания будут иметь вектор признаков х
p(x) – функция плотности распределения случайной величины х.
формула Баеса для дискретных распределений
P(Ck|x) = P(x|Ck)*P(Ck)/P(x)
P(C1|x) + P(C2|x) + … P(CM|x) = 1 (где М- число классов в задаче распознавания. Это очевидно, так как объект всегда принадлежит одному из классов в задаче распознавания)
Подставляя в эту формулу формулу Баеса получаем:
P(x|C1)*P(C1)/P(x) + P(x|C2)*P(C2)/P(x) + … + P(x|CM)*P(CM)/P(x) = 1
домножаем на P(x), эта вероятность очевидно не нулевая
получаем
P(x|C1)*P(C1) + P(x|C2)*P(C2) + … + P(x|CM)*P(CM) = P(x)
поэтому формулу Баеса можно записать и без P(x):
P(Ck|x) = P(x|Ck)*P(Ck) /
[P(x|C1)*P(C1) + P(x|C2)*P(C2) + … + P(x|CM)*P(CM)]
Формула Баеса для непрерывных распределений:
P(Ck|x) = p(x|Ck)*P(Ck) /
[p(x|C1)*P(C1) + p(x|C2)*P(C2) + … + p(x|CM)*P(CM)]
Вывод для одномерного случая:
Последнее равенство возможно, так как получается, что выражение не зависит от dx.
Матрица потерь:
Uij - диагональные элементы означают бонус, который мы получаем за правильное распознавание, остальные элементы означают потери, которые мы понесем, если объект j распознаем как i.
Пример матрицы потерь:
Задача – построить матрицу потерь для системы «банк купюр». Система распознает денежные купюры достоинством 10 100 и 1000 единиц и раскладывает по соответствующим полкам. Хранение каждой распознанной купюры обходится в 50 единиц. Поэтому после распознавания, все купюры достоинством 10 единиц уничтожаются. Купюры достоинством 1000 единиц нужно проверить на подлинность, что стоит 100 единиц. Несовпадение номиналов при провеке вызывает перепроверку всех купюр, которая стоит 1000
| истиное значение класса | ||||
| значение класса выдаваемое классификатором | 10 | 100 | 1000 | |
| 10 | 0, десятку как и положено уничтожили, мы ничего не получили в копилку, но и ничего не потеряли на хранении | «сотку» приняли за «десятку», значит ее уничтожат, и на самом деле мы получим убыток в 100-50 = 50 (не 100, так как 50 не придется платить за хранение) | тысячу приняли за десятку и уничтожили – убыток 1000-50 = 950, но не стали проверять на подлинность, так что на самом деле убыток меньше, 850 | |
| 100 | десятку приняли за сотку, значит ее сохранят, но 50 придется отдать за хранение, убыток = 1000(за ошибку)+40 | 50 (сто минус 50 за хранение) | тысячу приняли за сотку, ее сохранят, и не будут проверять на подлинность, но заплатят за перепроверку, убыток = 1000-950 = 50 | |
| 1000 | десятку приняли за 1000, значит ее сохранят, но придется отдать 50 за хранение, и еще проверить на подлинность и еще заплатить потом за перепроверку, убыток = 50+100+1000-10 = 1140 | сотку приняли за тысячу. ее сохранят, и будут проверять на подлинность, и еще заплатят потом за перепроверку убыток = 1050 | 850 (1000 минус 50 за хранение, минус 100 за проверку) | |
итоговая матрица:
| 0 | -50 | -850 |
| -1040 | 50 | -50 |
| -1140 | -1050 | 850 |
Предположим система выдает равные вероятности на все три купюры (по 1/3). Какое нужно принять решение чтобы минимизировать риск потерь (максимизировать выгоду)?
Если примем решение, что это «10», то средний риск потерь (через мат. ожидание) =
0*1/3 + (-50)*1/3 + (-850)*1/3 = -900/3 = -300
Если примем решение, что это «100», то средний риск потерь (через мат. ожидание) =
-1040*1/3 + 50*1/3 + (-50)*1/3 = ~ - 347
Если примем решение, что это «1000», то средний риск потерь (через мат. ожидание) =
-1140*1/3 + (-1050)*1/3 + 850*1/3 = ~ - 447
Т.е. если классификатор «не уверен», то выбирать нужно «10», в основном по причине того, что такая купюра выбрасывается и не может сложиться ситуации в необходимости перепровеки всех купюр при нахождении несовпадающих номиналов.
Итак, решающее правило с учетом матрицы потерь можно записать так:
arg max [U*p],
где U – матрица потерь, p – вектор решений классфикатора [P(C1|x)…P(CM|x)]T, *-умножение матрицы на вектор
Заметим, что если матрица диагональная
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
То arg max [U*p] = arg max p, т.е. выбирается решение, соответствующее максимальному выходу классификатора.
Рандомизированное решающее правило. Определение см. в Metogy_r.doc, стр 38.
Отказ от гипотезы о компактности. В статистических методах мы имеем дело с вероятностями событий (условными вероятностями принадлежности объектов к определенным классам при условии, что их признаки принимают определенные значения) и абстрагируемся от истинных причин принадлежности объектов к тем или иным классам. Мы не говорим о «расстоянии» между векторами признаков объектов в пространстве признаков.
Если детерминистические методы основаны на понятии «схожести» и расстоянии между объектами классов, то статистические методы основаны на построении функций распределения.
Детерминистические методы имеют погрешность в том, что расстояние до объекта из обучающей выборки зависит от количества элементов в обучающей выборке. Т.е. например, расстояние до ближайшего элемента может меняться с ростом числа примеров.
Статистические методы имеют погрешность в том, что по обучающей выборке мы можем лишь оценить распределение с некоторой точностью, и не можем узнать его истинную структуру. Чем больше различных элементов обучающей выборки мы имеем, тем более точно мы сможем оценить распределение. В этом прослеживается связь между статистическими и детерминистическими методами распознавания.
2 способа распознавания по формуле Байеса. В первом случае моделируются распределения и с учетом априорных вероятностей вычисляются апостериорные вероятности. Во втором случае просто пространство признаков делится на области принятия решений.