§ 1. Способы представления информации

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

Оба способа представления информации имеют как свои сильные, так и слабые стороны.

Сильной стороной непрерывного способа является точность задания значений координат. Каждая координата вектора здесь равна тому значению параметра, которое было замерено. Однако при таком способе представления информации для хранения значения каждого параметра требуется одна ячейка памяти вычислительной машины. А так как в задачах распознавания ситуация описывается большим числом параметров (вектор  имеет размерность порядка десятков и сотен), то хранение одной ситуации в памяти машины требует слишком большого объема памяти. Кроме того, часто, например в задачах медицинской диагностики, ситуации описываются признаками, которые не имеют точного количественного выражения (например, надо отразить, что у данного больного повышена «бледность кожных покровов»). В этом случае принят следующий способ записи такой информации. Договариваются, что единица означает наличие данного признака, нуль – его отсутствие.

Возможен способ записи информации, при котором кодируется не только наличие или отсутствие некоторого признака, но и степень проявления признака. Например, следующие характеристики: «бледность кожного покрова не выражена», «бледность кожного покрова выражена слабо», «бледность кожного покрова сильно выражена» – могут иметь соответствующие коды 100, 010, 001.

Таким образом, наличие качественных признаков описания объекта предопределяет дискретный способ представления информации.

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

Весь диапазон значений параметра разбивается на ряд градаций. Единицей кодируется -й разряд кода признака, если значение параметра принадлежит -й градации; если же значение параметра не принадлежит -й градации, то в -м разряде проставляется нуль.

Пример. Пусть значение параметра  принадлежит отрезку  и этот отрезок разбивается на пять градаций:

; ; ; ; .

Кодом 10000 обозначаются величины , 01000 – величины , 00100 – величины , 00010 – величины , 00001 – величины .

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

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

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

Итак, пусть признак  может принимать значения из интервала  и пусть вектор, обладающий этим признаком, принадлежит одному из  классов. Будем считать, что существуют условные вероятности принадлежности к каждому классу

.

Для каждого фиксированного значения признака  может быть определена мера неопределенности (энтропия) принадлежности к тому или иному классу. Она равна

.

Среднее значение по мере  энтропии вычисляется так:

.

Пусть теперь параметр  разбит на  градаций. Тогда средняя энтропия может быть записана в виде

.                       (15.1)

Воспользуемся теперь формулой Байеса

.                 (15.2)

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

.

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

,                  (15.3)

где  – число векторов -гo класса в обучающей выборке,  – число векторов -гo класса, у которых ;  – длина выборки.

Формула (15.3) получена в предположении, что априорные значения ,  равновероятно распределены на симплексах:

,                     ;

,                .        (15.4)

В более общем случае целесообразно рассмотреть формулу

,                   (15.5)

где параметр  определяется характером априорной информации.

Реализация сформулированного принципа состоит в таком подборе разбивки на градации, чтобы обеспечить минимум (15.5).

Алгоритм удобно реализовать в следующей форме: сначала разбить параметр на большое число градации, а затем, «склеивая» соседние градации, добиваться минимизации значения .

Можно оценить и количество информации  о принадлежности объекта к тому или иному классу, которое несет сведение о значении параметра

,

где

.

Часто разумно продолжать «склеивать» градации и после достижения минимума по  функции , но лишь до тех пор, пока величина  не уменьшится в  раз (, так же как и , – параметры алгоритма).