Анализ способов выбора эффективного набора признаков для систем автоматического распознавания



Одним из важнейших и весьма сложных этапов на пути создания системы распознавания является построение словаря признаков, по которым будет производиться распознавание. При решении указанной задачи приходится сталкиваться со следующими ограничениями:

1) в словарь включают только те признаки, для которых может быть получена априорная информация, необходимая для описания классов на языке этих признаков;

2) некоторые из признаков нецелесообразно включать в словарь ввиду того, что они малоинформативны;

3) некоторые из признаков, как правило, наиболее информативные, не могут быть определены ввиду отсутствия соответствующих измерителей (вычислителей), а ресурсы, выделенные на создание системы распознавания, ограничены [1];

4) измерения (вычисления) некоторых признаков не укладываются во временные рамки, отведенные на эту операцию.

Следует отметить, что удовлетворительного решения, определяющего порядок автоматического выбора признаков путем обработки информации, получаемой на уровне абсолютного описания сигнала, пока не найдено [2]. Поэтому основным решением по-прежнему остается выбор наиболее информативных признаков из некоторого исходного множества, задаваемого эвристически.

Задача формирования исходного множества признаков (из которого в дальнейшем выбираются наиболее эффективные), заключается в том, чтобы определить полный перечень признаков (параметров), характеризующих объекты, подлежащие распознаванию [1]. Такое множество называют априорным словарем (набором) признаков.

Из априорного словаря необходимо выбрать те признаки, которые, с одной стороны, удовлетворяют используемому критерию эффективности признаков и, с другой стороны, могут быть получены (измерены) в реальной обстановке с минимальными временными, вычислительными и другими затратами.

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

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

К способам выбора эффективного набора признаков также известно множество подходов, оценивающих эффективность признаков по тем или иным критериям. С теоретической точки зрения наилучшим показателем качества признаков является вероятность ошибочного распознавания (Р_ош). Однако недостатком этого критерия является то, что за исключением очень небольшого числа частных случаев для него не существует явного математического выражения. Даже для нормальных распределений вычисление Р_ош требует численного интегрирования. Поэтому были предприняты попытки ввести другие критерии эффективности признаков — критерии разделимости, приближенно отражающие Р_ош и не требующие численного интегрирования.

В [3] описаны условия, которым должны удовлетворять критерии разделимости двух классов:

1. Монотонная связь с вероятностью ошибки.
2. Монотонная связь с верхней и нижней границами Р_ош.
3. Инвариантность относительно взаимно однозначных отображений.
4. Аддитивность по отношению к независимым признакам.
5. Метрические свойства критерия разделимости:

где — критерий,

— распознаваемые классы (гипотезы),

–вектор признаков размерности S.

Рассмотрим наиболее распространенные критерии разделимости.

1. Критерии разделимости для случая двух классов с использованием матриц рассеяния внутри классов и матриц рассеяния между классами .

где R_i — ковариационная матрица рассеяния признаков i-го класса,

х — вектор признаков,

— априорная вероятность появления класса .

Наиболее часто используются критерии вида:

(1)

где — усредненное на множестве классов математическое ожидание вектора признаков;

— матрица рассеяния смеси.

(2)

где

Часто критерий (2) записывают в виде . Логарифмирование проводится, чтобы получить аддитивность для независимых признаков.

Наиболее эффективным будет такой набор признаков, который доставляет максимум критерию разделимости.

2. Критерии, формируемые на основе теории информации.

Такие критерии базируются на понятиях энтропии и дивергенции. Энтропия представляет собой статистическую меру неопределенности:

(3)

где х — вектор признаков,

— плотность распределения значений признаков, соответствующая классу .

Наиболее эффективным для описания класса является набор признаков, доставляющий минимум величине [4].

Дивергенция представляет собой меру расстояния или несходства между двумя классами. Если плотность распределения вектора признаков класса есть , тогда средняя различающая информация для по отношению к классу определяется выражением [4]

Средняя различающая информация для класса по отношению к :

Полную среднюю информацию для различения классов и часто называют дивергенцией и задают в виде:

(4)

Наиболее эффективным для описания объектов и является набор признаков, доставляющий максимум величине J_ij.

На теории информации основан и критерий вида:

(5)

Наиболее эффективным для описания объектов и является набор признаков, доставляющий максимум величине J.

3. Критерий, учитывающий вероятность определения признаков и затраты на построение системы [1].

В качестве критерия качества системы распознавания используется математическое ожидание квадрата среднеквадратического расстояния между объектами классов

где — анализируемые признаки;

C_j — затраты на создание технического средства T_j для определения j-го признака;

P_j(C_j) — вероятность определения j-го признака с помощью средства T_j;

— значение j-го признака у k-го объекта р — класса;

— значение j-го признака у l-го объекта q — класса;

k_pи k_q — количество объектов в p-ом и q-м классах соответственно.

Величина характеризует разделительные свойства j-го признака для r-ой пары классов.

Критерий качества функционирования системы:

(6)

где — вектор затрат ресурсов на создание каждого технического средства T_j.

Задача заключается в нахождении вектора затрат С₀, обеспечивающего

где С₀ — ресурсы, выделенные на создание технических средств измерения признаков.

4. Игровой подход к выбору признаков используют, когда предпринимаются какие-либо мероприятия, связанные с противодействием распознаванию объектов или явлений. Данный подход, основанный на теории конфликтов, в качестве критерия эффективности системы распознавания использует, например, минимум квадрата расстояния между возможными парами объектов:

где r — номер пары классов, п — число пар классов;

— характеризует информативность j-го признака при классификации объектов, принадлежащих r –ой паре классов.

В условиях заданной информированности сторон оптимальная стратегия такова, что

(7)

где

— соответственно выделенные ресурсы и затраты на построение системы распознавания;

— соответственно выделенные ресурсы и затраты противоборствующей стороны на противодействие распознаванию;

– принимают значения 0 или 1 в зависимости от того, используется/не используется признак для распознавания или противодействует/не противодействует «противник» определению соответствующего признака.

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

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

Таблица 1

Ограничения способов выбора признаков

Критерий	Ограничения
(1),(2)	1.Не связаны непосредственно с вероятностью ошибки распознавания. 2.Требуют обширной априорной информации о признаках и объектах, получение которой требует больших временных и материальных затрат. 3.Не учитывают ограничения, накладываемые на разработку технических средств измерений.
(3), (4), (5)	1.Не связаны непосредственно с вероятностью ошибки распознавания. 2.Требуют обширной априорной информации о признаках и объектах, получение которой больших временных и материальных затрат. 3.Не учитывают ограничения, накладываемые на разработку технических средств измерений. 4.Информативность признаков не является ни постоянной, ни безусловной величиной, зависит от того, какие признаки были определены ранее и какие значения они приняли. Причем это относится и к статистически независимым признакам.
(6)	1.Не связаны непосредственно с вероятностью ошибки распознавания. 2.Требуют обширной априорной информации о признаках и объектах, получение которой больших временных и материальных затрат.
(7)	1.Высокая вычислительная сложность не позволяет использовать в реальном времени. 2. Требуют обширной априорной информации о признаках и объектах, получение которой требует больших временных и материальных затрат. 3.Требует точной априорной информации о мерах «противника» по противодействию распознаванию.

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

Наилучшими признаками являются те признаки, которые с одной стороны не требуют разработки новых технических средств для их определения, а с другой стороны, являются достаточно информативными для успешного распознавания.

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

1. Не требует полной априорной информации о признаках и объектах.
2. Определение признаков может быть реализовано в автоматическом режиме.
3. Является адаптивным к изменению условий наблюдения.
4. Позволяет получить инвариантные признаки.

Выводы:

1) Задача выбора наиболее эффективного набора признаков чрезвычайно сложна и не имеет строгой методики решения.

2) Множество признаков и способов их выбора имеют ряд ограничений, затрудняющих их практическое применение.

3) С точки зрения применения в гематологическом анализаторе, наиболее подходящими являются признаки, во-первых, не требующие разработки новых технических средств для их измерения и, во-вторых, задача выбора которых не требовала большой априорной информации о признаках и объектах. Такими признаками могут являться признаки, полученные в результате анализа главных компонент сигналов, которые необходимо классифицировать.

Литература:

1. Горелик А. Л., Скрипкин В. А. Методы распознавания. — М.: Высш. шк., 1989.-232 с.
2. Техническое зрение роботов/В. И. Мошкин, А. А. Петров, В. С. Титов, Ю. Г. Якушенков; Под. ред. Ю. Г. Якушенкова. — М.:Машиностроение,1990. — 272 с.
3. Быстрые алгоритмы в цифровой обработке изображений / Под ред. Т. С. Хуанга. М.: Радио и связь, 1984. — 224 с.
4. Чулюк С. Г. Обзор способов выбора эффективного набора признаков для автоматических систем распознавания// Цифровая обработка изображений в задачах распознавания и определения местоположения объектов/ Под ред. И. Н. Белоглазова.–М.: ВВИА им. Н. Е. Жуковского, 1992.–С. 104–111.