Задача распознавания образов

1.1. Предмет распознавания образов

Распознавание образов – это научная дисциплина, целью которой является классификация объектов по нескольким категориям или классам. Объекты называются образами.

Классификация основывается на прецедентах.

Прецедент – это образ, правильная классификация которого известна.

Прецедент – ранее классифицированный объект, принимаемый как образец при решении задач классификации. Идея принятия решений на основе прецедентности – основополагающая в естественно-научном мировоззрении.

Будем считать, что все объекты или явления разбиты на конечное число классов. Для каждого класса известно и изучено конечное число объектов – прецедентов. Задача распознавания образов состоит в том, чтобы отнести новый распознаваемый объект к какому-либо классу.

Задача распознавания образов является основной в большинстве интеллектуальных систем. Рассмотрим примеры интеллектуальных компьютерных систем.

1.2. Признаки и классификаторы

Измерения, используемые для классификации образов, называются признаками. Признак – это некоторое количественное измерение объекта произвольной природы. Совокупность признаков, относящихся к одному образу, называется вектором признаков. Вектора признаков принимают значения в пространстве признаков. В рамках задачи распознавания считается, что каждому образу ставится в соответствие единственное значение вектора признаков и наоборот: каждому значению вектора признаков соответствует единственный образ.

Классификатором или решающим правилом называется правило отнесения образа к одному из классов на основании его вектора признаков.

Пример 1. Иллюстрация понятий признаков и классификатора и идеи распознавания (классификации). Рассмотрим задачу диагностики печени по результатам инструментального исследования (рис.1.1). Доброкачественные (левый рисунок – класс A) и злокачественные (правый рисунок – класс B) изменения дают разную картину. Предположим, что имеется несколько препаратов в базе данных, про которые известна их принадлежность к классам A и B (правильная классификация). Очевидно, что образцы отличаются интенсивностью точек изображения. В качестве вектора признаков выберем пару: среднее значение ( $$\mu$$ ) и среднеквадратичное отклонение ( $$\sigma$$ ) интенсивности в изображении.

На рис.1.2 представлены изображения этих образов в пространстве признаков. Точки, соответствующие прецедентам разных классов, разделяются прямой линией. Классификация неизвестного образа (соответствующая точка изображена звездочкой) состоит в проверке положения точки относительно этой разделяющей прямой.

Практическая разработка системы классификации осуществляется по следующей схеме (рис.1.3). В процессе разработки необходимо решить следующие вопросы.

1.3. Классификация с обучением и без обучения

В зависимости от наличия или отсутствия прецедентной информации различают задачи распознавания с обучением и без обучения. Задача распознавания на основе имеющегося множества прецедентов называется классификацией с обучением (или с учителем).

В том случае, если имеется множество векторов признаков, полученных для некоторого набора образов, но правильная классификация этих образов неизвестна, возникает задача разделения этих образов на классы по сходству соответствующих векторов признаков. Эта задача называется кластеризацией или распознаванием без обучения.

Пример 2. Рассмотрим съемку со спутника и классификацию поверхности по отраженной энергии (рис.1.4). На рисунке изображены снимок из космоса (слева) и результат кластеризации векторов признаков, рассчитанных для различных элементов изображения (справа). Распределение образов, изображенных точками ( $$x_1,x_2$$ ) по классам осуществляется на основе анализа "скоплений" этих точек в пространстве признаков.

Пример 3. Рассмотрим другой пример распознавания образов – в общественных (социальных) науках. Целью задачи является построение системы классификации государств для определения необходимости гуманитарной поддержки со стороны международных организаций. Необходимо выявить закономерности связей между различными, объективно измеряемыми параметрами, например, связь между ВНП, уровнем грамотности и уровнем детской смертности. В данном случае страны можно представить трехмерными векторами, а задача заключается в построении меры сходства этих векторов и дальнейшем построении схемы кластеризации (выбора групп) по этой мере.

1.4. Формальная постановка задачи классификации

Будем использовать следующую модель задачи классификации.

$$\Omega$$ - множество объектов распознавания (пространство образов).

$$\omega:\varpi\in\Omega$$ - объект распознавания (образ).

$$g(\omega):\Omega\rightarrow M, \; M\{1,2,\ldots m\}$$ - индикаторная функция, разбивающая пространство образов $$\Omega$$ на $$m$$ непересекающихся классов $$\Omega^1,\Omega^2,\ldots,\Omega^m$$. Индикаторная функция неизвестна наблюдателю.

$$X$$ – пространство наблюдений, воспринимаемых наблюдателем (пространство признаков).

$$x(\omega):\Omega\rightarrow X$$ - функция, ставящая в соответствие каждому объекту $$\omega$$ точку $$x(\omega)$$ в пространстве признаков. Вектор $$x(\omega)$$ - это образ объекта, воспринимаемый наблюдателем. В пространстве признаков определены непересекающиеся множества точек $$K_i\subset X, \; i=1,2,\ldots,m$$, соответствующих образам одного класса.

$$\widehat{g}(x):X\rightarrow M$$ - решающее правило – оценка для $$g(\omega)$$ на основании $$x(\omega)$$, т.е. $$\widehat{g}(x)=\widehat{g}(x(\omega))$$.

Пусть $$x_j=x(\omega_j), \; j=1,2,\ldots,N$$ – доступная наблюдателю информация о функциях $$g(\omega)$$ и $$x(\omega)$$, но сами эти функции наблюдателю неизвестны. Тогда $$(g_j,x_j), \; j=1,2,\ldots,N$$ – есть множество прецедентов.

Задача заключается в построении такого решающего правила $$\widehat{g}(x)$$, чтобы распознавание проводилось с минимальным числом ошибок.

Обычный случай – считать пространство признаков евклидовым, т.е. $$X=R^l$$. Качество решающего правила измеряют частотой появления правильных решений. Обычно его оценивают, наделяя множество объектов $$\Omega$$ некоторой вероятностной мерой. Тогда задача записывается в виде $$\min P\{\widehat{g}(x(\omega))\neq g(\omega)\}$$.