Основные определения курса «Распознавание Образов»

Цели науки распознавания образов:
1) замена человеческого эксперта или сложной экспертной системы более простой системой (автоматизация деятельности человека или упрощение сложных систем).
2) построение обучающихся систем, которые умеют принимать решения без указания четких правил, а именно, систем, которые умеют сами синтезировать правила принятия решений на основе некоторого конечного количества «продемонстрированных» системе примеров правильных решений.
Множество объектов задачи распознавания – множество всех объектов, которые могут теоретически встретиться в конкретной задаче их распознавания.
Образ (также pattern, shape, объект) – любой объект, для которого можно измерить набор определенных числовых признаков. Пример образа: буква, изображение, кардиограмма, и т.п.
Числовой признак (или просто признак ). Формула или иное описание способа сопоставления объекту некоторой числовой характеристики, которое действует в рамках конкретной задачи распознавания образов. Для каждого объекта может быть определено несколько различных признаков , то есть несколько числовых характеристик.
При этом считается, что если все числовые значения всех признаков двух объектов совпадают, то такие объекты считаются идентичными, несмотря на то, что по сути объекты могут различаться. Например, если в какой-то задаче распознавания образов для шаров определен один только признак – радиус, то при этом красный шар с радиусом 10 в данной постановке задачи будет считаться идентичным синему шару с радиусом 10, поскольку значения их единственного признака совпадают.
Пространство признаков . N-мерное пространство, определенное для данной задачи распознавание, где N – фиксированное число измеряемых признаков для любых объектов. Вектор из пространства признаков, соответствующий объекту задачи распознавания это N-мерный вектор с компонентами (х1,х2, …, хN), которые являются значениями признаков данного объекта.
ОБЪЕКТ->N признаков->N-мерный вектор признаков
Класс . Неформализируемое (как правило) представление о возможности отнесения произвольного объекта из множества объектов задачи распознавания к определенной группе объектов. Для объектов одного класса предполагается наличие «схожести» . Для задачи распознавания образов может быть определено произвольное количество классов, большее 1. Количество классов обозначается числом S.
Гипотеза о схожести : Если для объекта А, характеризуемого вектором признаков х1 и для объекта Б, характеризуемого вектором признаков х2 выполняется следующее:
|x1-x2| -> 0, то вероятность что объекты А и Б принадлежат одному и тому же классу тоже стремится к единице.
Обучающая выборка . Неформальное определение классов данной задачи распознавания при помощи примеров объектов, отношение которых к тому или иному классу заранее определено (известно). Математически обучающая выборка – это две сущности:
- последовательность N-мерных векторов x(k), где индекс k = 1..K пробегает по всем номерам примеров.
- последовательность чисел D*(k), значения которых равны номеру класса для объекта, характеризуемого вектором х(k).
Обучающая выборка может быть представлена в виде таблицы вида
k
I
1
2
…
K
i=1
x11
x21
xK1
i=2
x21
x22
xK2
..
x31
x23
xK3
i=N
xN1
xN3
xKN
D*(k)
D*(1)
D*(2)
…
D*(K)
т.е. по горизонтали идет итерирование по номеру объекта-примера, а по вертикали по признакам и значению номера класса.
Значения классов примеров D*(1)…D*(K) называют указаниями учителя .
Обучающая выборка должна содержать примеры каждого класса из задачи распознавания.
Истинная классификация объекта. Классификация объекта, которая была бы сделана человеком или сложной экспертной системой, которые имели бы неограниченное количество примеров представителей классов данной задачи распознавания.
Задача распознавания образов формулируется следующим образом:
ДАНО:
Определено множество объектов распознавания
Определено K классов
Сформулированы N признаков объектов
Имеется обучающая выборка из M примеров, т.е. M объектов для каждого из которых известны
значения N признаков
указана принадлежность к классу
Имеется объект, про который известны его N признаков (задан вектор х из N-мерного пространства признаков)
НАЙТИ: для объекта, характеризуемого вектором признаков х , определить номер класса, по возможности, наиболее соответствующему истинному .
Классификатор . Функция (алгоритм) вида Ф(x ,w ), которая возвращает предполагаемый номер класса объекта, характеризуемого вектором признаков x . Работа функции также зависит от набора параметров, задаваемых вектором состояния классификатора w .
Например, для персептрона данная функция может иметь вид Ф(x ,w ) = sign(x *w ), где *-скалярное умножение векторов. Очевидно, что для персептрона в таком случае размерность вектора w должна совпадать с размерностью вектора признаков х. Для классификатора методом построения эталонов (для задачи с S классами) классификатор может быть задан функцией
Ф(x,w) = arg min [ |x-x1| , |x-x2| , …, |x-xS| ], где под вектором w подразумевается следующий составной вектор, состоящий из вертикально «склеенной» цепочки из векторов x1…xS.
приставка arg означает, что ищется не минимальное значение, а НОМЕР минимального аргумента функции min (соответствующий, очевидно, номеру класса).
Структуру вектора w можно описать следующей диаграммой:
w =
x1
x1[1]
w1
x1[2]
w2
…
…
x1[N]
x2
x2[1]
x2[2]
…
x2[N]
…
…
xS
xS[1]
xS[2]
…
xS[N]
wS*N
Соответственно, количество параметров классификатора (размерность вектора w ) для метода построения эталона = S*N.
Для метода ближайшего соседа:
Ф(x,w) = D*(arg min [ |x-x1| , |x-x2|, …, |x-xK| ]), где K – количество примеров в обучающей последовательности. x1…xK – вектора признаков примеров, D*(1)…D*(K) – указания учителя. Очевидно структура вектора w состояния классификатора аналогична для случая метода построения эталонов и размерность вектора w равна N*K+K (К параметров прибавляется за счет необходимости хранить К значений указаний учителя). То есть вектор w хранит ВСЮ обучающую последовательность, которая может оказаться очень большой.
Среднеквадратичная ошибка обучения. Функция вида
E(w) =
[Ф(x1,w)-D*(1)]^2 +
[Ф(х2,w)-D*(2)]^2 +
…
[Ф(хK,w)-D*(K)]^2,
где x1…xK, D*(1)…D*(K) – обучающая последовательность.
Задача обучения классфикатора .
Дано: постановка задачи распознавания.
Найти: arg min E(w), т.е. такое значение вектора w, при котором значение ошибки будет минимальным.
Способ обучения классификатора . Определенный математически, метод (алгоритм) решения задачи обучения классфикатора.
Применение обученного (настроенного) классификатора . Описание работы формулы Ф(x,w).
Неитеративные методы обучения . Методы для которых можно определить формулу
w = F(x1..xK,D*(1)…D*(K)),
такую, что найденное значение соответствует некоторму локальному минимуму функции ошибки.
Итеративные методы обучения . Методы для которых задается итеративная формула
w(n+1) = F(w(n)), которая служит поиску минимума функции ошибки.
Обобщающее свойство классификатора . Способность классификатора выдавать истинные значения классов для объектов, не входивших в обучающую выборку.
Типовые достоинства методов: простота, хорошие обобщающие свойства, низкие требования к памяти (маленький размер вектора состояния w), потребность в короткой обучающей последовательности, устойчивость к ошибкам в указаниях учителя.
Типовые недостатки методов: сложность, большая потребность в памяти для хранения вектора 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)
то есть это можно считать выводом формулы Баеса для распознавания образов, если вместо 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.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию