4.5. Частотные алгоритмы распознавания образов в пространстве дискретных признаков

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

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

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

, .

Если предположить, что компоненты вектора независимы, то частота встречаемости признаков новой ситуации среди элементов первого класса определяется в виде

,

где

,

(4.19)

– количество элементов выборки, принадлежащих к первому классу .

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

,

где

,

– количество элементов выборки, принадлежащих ко второму классу .

Построим решающее правило принадлежности ситуации к одному из классов

(4.20)

где

– оценка решающей функции.

Для многоальтернативного случая частота встречаемости признаков новой ситуации расчитывается по формуле

,

где

, .

В этом случае решающее правило будет сводиться к выбору максимальной оценки частоты при конкретной ситуации

.

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

,

,

где - множество номеров признаков входящих в -ю группу.

По аналогии рассчитываем частоты для второго класса

,

,

Используя решающее правило (4.20) определяем принадлежность к одному из дух классов , .

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

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

Рассмотрим применение непараметрического алгоритма на примере двуальтернативной задачи распознавания образов в условиях, когда компоненты - бинарные переменные. Для простоты восприятия разобъём исходную обучающую выборку на две подвыборки, соответствующих классам

, .

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

Сформируем обучающую выборку

.

Если компоненты вектора независимы, то частота встречаемости ситуации для элементов первого класса определяется в виде

,

где

;

;

- единичная функция типа (4.19).

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

;

;

- единичная функция типа (4.19).

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

, (4.21)

, (4.22)

где – множество номеров точек, принадлежащих к -му классу .

При этом решающее правило будет иметь вид

.

Оптимизация решающего правила по коэффициентам размытости осуществляется из минимума эмпирической ошибки распознавания образов (4.5) по выборке методом «скользящего экзамена».