ГЛАВА 2. ОТБОР И УПОРЯДОЧЕНИЕ ПРИЗНАКОВ

2.1. Отбор и упорядочение признаков (теоретико-информационный подход)

Как указывалось в § 1.1, отбор признаков является важной задачей в распознавании образов, существенно связанной с качеством классификации. Кроме того, в системах последовательного распознавания образов при последовательных измерениях важное значение имеет упорядочение признаков. Цель упорядочения признаков заключается в том, чтобы при следующих друг за другом шагах последовательного процесса классификации для каждого следующего измерения избирался наиболее «информативный» признак, и тем самым процесс мог быть завершен раньше.

Задачу упорядочения признаков можно рассматривать как задачу отбора признаков, если на каждом шаге последовательного процесса классификации отбираемое подмножество признаков содержит лишь один признак. Оценка «добротности» признаков может быть сделана с точки зрения теории информации. В качестве критерия «добротности» признака предлагались как расхождение, так и средняя информация о классах образов, определяемых признаками Концепция расхождения тесно связана с мощностью критерия различения между двумя классами образов с гауссовым распределением вектора признаков X, Использование меры информации и расхождения в качестве критерия для отбора признаков или их упорядочения также подразумевается при сравнении средних рисков, когда для классификации используется байесово решающее правило.

Люисом [I] в качестве критерия для отбора и упорядочения признаков была предложена функция в виде энтропии или средней информации. Положим, что

каждый признак может принимать возможных значений. Частное значение обозначим Соответствующее каждому некоторое число являющееся мерой «добротности» , должно быть определено экспериментально. Число в общем случае является статистикой, которая определена оценкой на большой выборке распознаваемых образов.

Для выбора были предложены следующие соотношения, связывающие и процент правильного распознавания.

(1) Если то процент правильного распознавания при использовании только должен быть больше процента правильного распознавания при использовании только

(2) Если то для любого множества признаков процент правильного распознавания при использовании должен быть больше процента правильного распознавания при использовании

(3) Процент правильного распознавания при использовании является линейной функцией суммы значений для признаков в

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

Логарифмическая функция выбрана, чтобы удовлетворить требованию (2) аддитивности Учитывая требование (1), должно быть мерой корреляции между Предположим, что имеет следующий вид:

Таким образом,

Согласно можно трактовать как взаимную информацию признака и классов образов

Применение расхождения в качестве критерия для отбора признаков и их упорядочения предложили Мэрилл и Грин [2]. Пусть для распределение X соответствует многомерной гауссовой функции плотности со средним вектором и ковариационной матрицей К, т. е.

Пусть отношение правдоподобия равно

и пусть

Подставляя (2.4) в (2.6), получим

и

Согласно [3] определим расхождение между и следующим образом:

Тогда из (2.8) и (2.9)

Из (2.10) следует, что если К равно единичной матрице , то представляет собой квадрат расстояния

между и При использовании в классификаторе решающего правила с выборкой постоянного объема или байесова правила при из (1.27) следует

или

Вероятность ложного распознавания

Из (2.7), (2.8) и (2.10) следует, что является гауссовой функцией плотности со средним значением и дисперсией , где Аналогично также является гауссовой функцией плотности со средним значением — и дисперсией Таким образом,

Пусть

Тогда

Из (2.14) видно, что представляет собой монотонно убывающую функцию Поэтому отбор и упорядочение признаков по величине будет соответствовать мощности различения между

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

образов Среднее расхождение между двумя любыми классами определяется следующим выражением:

Для распределений, данных в (2.4),

Пусть

Тогда

следовательно,

Ближайшая верхняя граница соответствует максимуму Этот максимум равен что дает

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

При применении п. к. о. в. или о. п. к. о. в. знание, какие классы образов обладают большей вероятностью быть истинными (на входе системы распознавания), используется для определения «добротности» признаков. Пусть где имеющееся число признаков на любом из шагов последовательного процесса, и есть признак. Согласно Люису критерий выбора признака для следующего измерения представляет собой статистику в виде одного числа, которая является средним функции, описывающей корреляцию между классами образов, предыдущими замерами признаков и каждым из оставшихся признаков. Такая статистика, осносящаяся к после того как сделано измерений (в присутствии шумов) признаков может быть выражена следующим образом:

Так как

то (2.21) можно записать в виде

Следует отметить, что представляет собой апостериорное распределение для класса после получения Величина является условной энтропией или взаимной информацией после выполнения измерений признаков

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

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