Реферат: Основные определения курса Распознавание Образов
Типовые недостатки методов: сложность, большая потребность в памяти для хранения вектора w, большая потребность в памяти для хранения промежуточных переменных, большое количество вычислений, необходимость в длинной обучающей последовательности, неустойчивость к ошибкам в указаниях учителя, невозможность применения для решения произвольных задач распознавания (а только для частных), для итеративных алгоритмов – плохая (медленная или нестабильная) сходимость алгоритма.
Кластеризация (Таксономия, самообучение, обучение без учителя). Процесс выделения в пространстве признаков областей, которые могли бы быть объединены в группы человеком либо согласно гипотезе о компактности. Кластеризация применяется для поиска закономерностей в данных, например, выделения неизвестных признаков, поиск объектов среди шумов.
Типовая постановка задачи кластеризации:
Дано: обучающая последовательность без указаний учителя x1…xK.
Найти: число кластеров М, построить Ф(x,w) разбивающую пространство признаков на М связанных областей, таких что:
- в каждой области средняя плотность точек из обучающей последовательности максимальная
- области разделены между собой промежутками с минимальной средней плотностью точек
Пример алгоритма кластеризации .
Суть алгоритма заключается в попытке найти устойчивое разбиение обучающей выборки на гиперсферы одинакового радиуса.
Алгоритм состоит из 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)