Теоретические основы информатики. Распознавание образов

Распознавание образов как научная дисциплина Математические методы распознавания образов Теоретические основы информатики Тема №3. Распознавание образов Волков Владимир Викторович Технолого-педагогический факультет Кафедра естественнонаучных и общеобразовательных дисциплин Борисоглебский филиал Воронежского государственного университета 4 курс, 8 семестр, 2019/2020 учебный год ТОИ Распознавание образов 1 Распознавание образов как научная дисциплина Математические методы распознавания образов Основные понятия распознавания образов Системы распознавания образов Предмет распознавания образов (РО) Распознавание образов (Pattern recognition) — наука о методах и алгоритмах классификации объектов различной природы. Направления использования методов РО: распознавание символов и изображений; распознавание речи; медицинская диагностика; системы безопасности; классификация, кластеризация и поиск в базах данных и знаний. ТОИ Распознавание образов 2 Распознавание образов как научная дисциплина Математические методы распознавания образов Основные понятия распознавания образов Системы распознавания образов История дисциплины РО Предпосылки: 20-е годы XX в. — Р. Фишер, разделяющие функции в задаче классификации; 30-е годы XX в. — байесовская теория принятия решений; 40-е годы XX в. — работы А. Н. Колмогорова и А. Я. Хинчина; 50-е годы XX в. — первые нейросетевые модели распознавания (перцептрон Розенблатта). Конец 60-х годов XX в. — в рамках кибернетики разработаны и детально исследованы различные подходы распознавания образов. Середина 70-х годов XX в. — определился облик распознавания образов как самостоятельного научного направления. ТОИ Распознавание образов 3 Распознавание образов как научная дисциплина Математические методы распознавания образов Основные понятия распознавания образов Системы распознавания образов Понятия «образ»и «класс» Pattern (англ.) — образ, шаблон, образец, схема, модель, структура, пример, форма. Образ — некоторое структурированное приближенное описание изучаемого объекта, явления или процесса. Любой образ представляется набором признаков! Признак — характеристика (свойство) объекта, которую можно измерить. Класс — объединение объектов (явлений), отличающиеся общими свойствами, интересующими человека. Распознавание (классификация) — соотнесение объектов или явлений на основе анализа их характеристик, представляющих образы этих объектов, с одним из нескольких классов. ТОИ Распознавание образов 4 Распознавание образов как научная дисциплина Математические методы распознавания образов Основные понятия распознавания образов Системы распознавания образов Системы распознавания (СР) Словарь признаков — список всех возможных признаков, описывающих группу образов. Пространство признаков — оси которого являются осями признаков, а точки образуют области, являющиеся множествами образов соответствующих классов. Система распознавания — автоматическое вычислительное устройство, предназначенное для распознавания образов. Центральная задача распознавания образов Построение на основе систематических теоретических и экспериментальных исследований эффективных вычислительных средств (СР) для отнесения описаний объектов, явлений, процессов к соответствующим классам. ТОИ Распознавание образов 5 Распознавание образов как научная дисциплина Математические методы распознавания образов Основные понятия распознавания образов Системы распознавания образов Геометрическая интерпретация: одномерный случай x ТОИ Распознавание образов 6 Распознавание образов как научная дисциплина Математические методы распознавания образов Основные понятия распознавания образов Системы распознавания образов Геометрическая интерпретация: двумерный случай x2 x1 ТОИ Распознавание образов 7 Распознавание образов как научная дисциплина Математические методы распознавания образов Статистические методы Построение разделяющих поверхностей Математическая постановка задачи РО S — объект (ситуация, предмет, явление, процесс).   x = x(S) = x1 x2 . . . xn — вектор значений признаков (образ). y(S) — основное свойство (класс). Известны пары x(Si ) y(Si ) (прецеденты) для i = 1, 2, . . . , m — обучающая (эталонная) выборка. Задача распознавания по прецедентам (классификации с учителем) Определение свойства y(S) некоторого объекта S, заданного его образом x(S), по информации x(S1 ), x(S2 ), . . . , x(Sm ), y(S1 ), y(S2 ), . . . , y(Sm ) (обучающей выборке) ТОИ Распознавание образов 8 Распознавание образов как научная дисциплина Математические методы распознавания образов Статистические методы Построение разделяющих поверхностей Алгоритм распознавания A(S) = (α1 (S), α2 (S), . . . , αl (S)) αi (S) ∈ {0, 1, ∆}, i = 1, 2, . . . , l Методы распознавания образов: статистические; построение разделяющих поверхностей. ТОИ Распознавание образов 9 Распознавание образов как научная дисциплина Математические методы распознавания образов Статистические методы Построение разделяющих поверхностей Статистические алгоритмы распознавания Используется байесовское решающее правило (оптимальный байесовский классификатор). Оценивается условная вероятность принадлежности: P (Ki |x), где i = 1, 2, . . . , l. Объект S (образ x(S)) относится к тому классу, для которого P (Ki |x) максимальна. В подавляющем большинстве практических задач вероятностное распределение неизвестно. Однако можно оценить P (Ki |x), используя информацию обучающей выборки. ТОИ Распознавание образов 10 Распознавание образов как научная дисциплина Математические методы распознавания образов Статистические методы Построение разделяющих поверхностей Метод k-ближайших соседей Оценка условных вероятностей P (Ki |x) — по ближайшей окрестности Vk точки x(S) в признаковом пространстве: P (Ki |x) = ki k Важно: выбор числа k. Недостаток: снижение эффективности при малом объёме выборки и высокой размерности признакового пространства. ТОИ Распознавание образов 11 Распознавание образов как научная дисциплина Математические методы распознавания образов Статистические методы Построение разделяющих поверхностей Метод k-ближайших соседей. Пример x2 x1 k=5 ТОИ Распознавание образов 12 Распознавание образов как научная дисциплина Математические методы распознавания образов Статистические методы Построение разделяющих поверхностей Алгоритмы построения разделяющих поверхностей Используются геометрические модели классов. Множеству объектов каждого класса соответствует область в n-мерном признаковом пространстве. Если области имеют достаточно простую форму, их можно разделить «простой» поверхностью. В дальнейшем будем считать, что имеются лишь два класса объектов. Алгоритм распознавания для двух классов A(S) = α(S) α(S) ∈ {0, 1, ∆} ТОИ Распознавание образов 13 Распознавание образов как научная дисциплина Математические методы распознавания образов Статистические методы Построение разделяющих поверхностей Линейная разделяющая поверхность (гиперплоскость) Линейная функция относительно признаков: f (x) = a1 x1 + a2 x2 + . . . + an xn + an+1 Решающее правило:   1, если f (S) > 0, ∆, если f (S) = 0, α(S) =  0, если f (S) < 0. ТОИ Распознавание образов 14 Распознавание образов как научная дисциплина Математические методы распознавания образов Статистические методы Построение разделяющих поверхностей Разделяющая гиперплоскость. Пример x2 x1 ТОИ Распознавание образов 15 Распознавание образов как научная дисциплина Математические методы распознавания образов Статистические методы Построение разделяющих поверхностей Способы построения разделяющей гиперплоскости Чтобы построить гиперплоскость нужно определить значения коэффициентов a1 , a2 , . . . , an+1 . Как это сделать? в общем случае — решить систему неравенств для всех точек обучающей выборки; простейший случай — заменить классы центральными точками обучающей выборки. ТОИ Распознавание образов 16 Распознавание образов как научная дисциплина Математические методы распознавания образов Статистические методы Построение разделяющих поверхностей Решение системы неравенств  a1 x1 (S1 ) + a2 x2 (S1 ) + . . . + an xn (S1 ) + an+1 > 0     · ··    a1 x1 (Sm1 ) + a2 x2 (Sm1 ) + . . . + an xn (Sm1 ) + an+1 > 0 a1 x1 (Sm1 +1 ) + a2 x2 (Sm1 +1 ) + . . . + an xn (Sm1 +1 ) + an+1 < 0      ···   a1 x1 (Sm ) + a2 x2 (Sm ) + . . . + an xn (Sm ) + an+1 < 0 ТОИ Распознавание образов 17 Распознавание образов как научная дисциплина Математические методы распознавания образов Статистические методы Построение разделяющих поверхностей Замена классов центральной точкой Гиперплоскость строится на максимальном расстоянии до центров классов. Принцип компактности — векторы-образы одного класса должны быть «компактно» расположены в пространстве признаков. Построение разделяющей гиперплоскости: 1) определить центры классов; 2) построить серединный перпендикуляр к отрезку, соединяющему их. ТОИ Распознавание образов 18