§ 2. Критерии информативности признаков

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

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

где  — евклидово расстояние между математическими ожиданиями -го и -гo образов.

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

Рис. 22

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

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

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

Аналогично, компактность  точек , представляющих образ , имеет вид

Разнесенность образов в пространстве характеристик можно оценивать через среднее расстояние между всеми парами точек из разных образов:

 для

На основании сказанного информативность пространства признаков тем больше, чем больше величина .

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

Аналогично можно найти неоднородность состава второй градации . Величина  характеризует информативность признака  при пороге деления на две градации . Меняя порог , можно найти такое его положение, при котором  достигает минимального значения . Если исходную неопределенность оценивать через

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

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

В табл. 2 приведен пример обучающей выборки двух образов ( и ) в пространстве двух бинарных признаков  и . Проекции реализаций на каждую ось показывают, что оба признака по отдельности абсолютно неинформативны. Использование же этих признаков в системе позволяет найти простое правило для распознавания этих образов: признаки  и  у реализаций -го образа имеют одинаковые значения, а у -гo образа — разные.

Таблица 2.Пример выборки с зависимыми признаками

Зависимости могут носить и более сложный характер и проявляться на множестве из более чем двух признаков. Следовательно, для выбора  признаков из  нужно перебрать и испытать на информативность  их комбинаций. Однажды нам встретилась интересная и важная задача анализа сигналов, одновременно поступающих от 2500 датчиков. Нестационарные помехи искажали эти сигналы, и каждые 10 секунд нужно было отбирать 100 датчиков, наименее пораженных помехами. У нас хватило энтузиазма, чтобы определить, что число сочетаний из , что на 100 порядков больше числа атомов в видимой части вселенной. А менее экзотические случаи, например, когда нужно выбрать 25 признаков из 50 (для чего нужно просмотреть  комбинаций), встречаются регулярно. Поэтому естественно, что о нахождении оптимального решения таких задач речь идти не может. Разрабатываются эвристические алгоритмы направленного перебора, которые за приемлемое время давали бы решения, по возможности близкие к оптимальным.

Рассмотрим некоторые из таких алгоритмов.