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

Скрибцов  П.В., 13.03.2005 

Цели науки  распознавания образов:

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).

 

Обучающая выборка  может быть представлена в виде таблицы  вида

 
 

т.е. по горизонтали идет итерирование по номеру объекта-примера, а по вертикали по признакам и значению номера класса.

Значения классов  примеров D*(1)…D*(K) называют указаниями учителя.

Обучающая выборка  должна содержать примеры каждого  класса из задачи распознавания. 

Истинная  классификация объекта. Классификация объекта, которая была бы сделана человеком или сложной экспертной системой, которые имели бы неограниченное количество примеров представителей классов данной задачи распознавания.  

Задача  распознавания образов формулируется следующим образом:

ДАНО:

1. Определено множество объектов распознавания
2. Определено K классов
3. Сформулированы N признаков объектов
4. Имеется обучающая выборка из M примеров, т.е. M объектов для каждого из которых известны
1. значения N признаков
2. указана принадлежность к классу
5. Имеется объект, про который известны его 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) для метода построения эталона = 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 – это сфера в центре обучающей последовательности, с радиусом таким, чтобы все элементы обучающей последовательности в нее умещались. На псевдокоде алгоритм можно записать следующим образом: 

1. Считать из файла обучающую последовательность в массив X[j], Y[j] j = 1..K (для случая если размерность пространства признаков = 2)
2. Зарезервировать массив меток точек обучающей последовательности T[j], j = 1..K
3. Запросить у пользователя G
4. Посчитать центр обучающей последовательности и Rmax
5. dR = Rmax/G
6. i = 0
7. R[i] = Rmax
8. Цикл А (разбиение на классы с заданным размером гиперсферы)
1. количество обнаруженных классов M = 0
2. обнулить отметки точек обучающей последовательности
3. Цикл Б (поиск всех кластеров с заданным размером гиперсфер)
1. Выбор первой непомеченной точки из обучающей последовательности = х, если непомеченных точек не осталось, выход из цикла Б.
2. M = M + 1
3. Цикл В (поиск оптимального центра гиперсферы)
1. r  = центр всех непомеченных точек, попавших в гиперсферу радиуса R[i], c центром х
2. Померить расстояние между r и х = d,
3. x = r
4. если d меньше установленного порога (например, 0.1) – конец цикла B
4. Записать в файл i,х,R[i], M
5. Пометить все точки, которые попали в гиперсферу с центром в х и радиусом R[i]
4. Конец Цикла Б
5. i = i+1
6. R[i] = R[i-1] – dR
9. Если R[i] < 0 конец цикла А