22.2. АДАПТИВНЫЕ АЛГОРИТМЫ КЛАССИФИКАЦИИ НОРМАЛЬНЫХ СОВОКУПНОСТЕЙ

22.2.1. Постановка задачи и общее решение.

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

Рассмотрим два класса которые характеризуются двумя -мерными нормальными распределениями вероятностей с векторными средними и общей ковариационной матрицей К. Если известны, то оптимальное байесовское правило классификации наблюдаемого вектора размерностью N предписывает сравнение с порогом логарифма отношения правдоподобия, т. е. статистики [см. (13.124)]

Статистика (22.1) подчиняется нормальному распределению с параметрами (среднее и дисперсия)

(22.2 а)

где [см. (13.127)]

— квадрат «расстояния» между классами

Вероятность ошибки классификации при использовании указанного байесовского правила

где — априорные вероятности появления классов, с — порог, с которым сравнивается статистика V [см. (13.15)], -интеграл Лапласа.

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

Подставляя в (22.1) вместо неизвестных получаем классифицирующую статистику

При фиксированной размерности N и неограниченном увеличении размеров обучающих выборок статистика V сходится по вероятности к статистике V.

Исследуем более подробно свойства классифицирующей статистики (22.7) при ограниченных размерах обучающих выборок (см. также [81]).

22.2.2. Одномерный случай.

Начнем с простейшего случая когда классы характеризуются одномерными нормальными распределениями с неизвестными средними и известными дисперсиями При обучении «с учителем» получены классифицированные обучающие независимые выборки из класса из класса Примем за оценки неизвестных средних оценки максимального правдоподобия по этим классифицированным обучающим выборкам

При этом можно сформулировать следующее правило классификации: наблюдение относится к классу если

и к классу в противном случае.

Статистика V представляет произведение коррелированных гауссовских случайных величин:

(22.10)

Среднее и дисперсия случайной величины у

(22.12)

а условные средние, дисперсии случайной величины z и коэффициент корреляции случайных величин

(22.14)

Заметим, что при случайные величины у и z независимы.

Условные средние значения статистики :

(22.17)

Если

(22.19)

Из (22.17) и (22.18), а также из (22.1) при следует

и при Если то при любом Далее и при

22.2.3. Многомерный случай (ковариационная матрица известна).

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

Пусть в результате обучения «с учителем» получена классифицированная обучающая выборка: из первого распределения и из второго . Каждый элемент указанных выборок представляет М-мерный вектор. В качестве оценок неизвестных векторов средних принимаются оценки максимального правдоподобия (22.5). Алгоритм классификации сводится к сравнению с порогом статистики [см. (22.7)]

(22.21)

Обозначим

(22.22)

Тогда для рассматриваемого случая классифицирующая статистика (22.21) (см. [69])

(22.24 а)

где — независимые случайные величины, подчиняющиеся нецентральному -распределению с N степенями свободы и параметрами нецентральности

(22.246)

где определяется согласно (22.3) и

(22.25)

Заметим, что параметр нецентральности зависит как от размеров обучающих выборок, так и от корреляционной матрицы К (через «расстояние» ).

При распределение статистики V приближается к нормальному с параметрами если и с параметрами если

22.2.4. Многомерный случай (ковариационная матрица неизвестна).

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

(22.26)

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

Можно показать (см., например, [70]), что при выполнении неравенства (22.26) классифицирующая статистика (22.7) представима в виде

(22.27)

где — независимые случайные величины распределенные соответственно по законам Стьюдента и центрального — элементы случайной матрицы, распределенные по нецентральному закону Уишарта с N степенями свободы и параметрами нецентральности:

(22.28 а)

параметр определяется согласно (22.3) [см. также (22.25)].

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

(22.30 а)

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

(22.31)

Заменяя , где матрица f определяется из соотношения , а — диагональная матрица, элементы которой являются корнями уравнения можно неравенство (22.31) привести к виду

(22.32)

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

(22.33)

где определяются согласно (22.5).

22.2.5. Алгоритм классификации с самообучением.

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

(22.34)

Среднее значение случайной величины, подчиняющейся распределению (22.34),

(22.35)

неизвестно, так как неизвестны

Выборочное среднее, полученное по неклассифицированной обучающей выборке

(22.36)

является несмещенной оценкой среднего значения а распределения (22.34).

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

(22.37)

и к классу в противном случае.

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

(22.38)

или

где

(22.40)

Вектор а является вектором средних значений распределения (22.39), а элементы ковариационной матрицы К этого распределения

(22,41)

где — символ Кронекера; компоненты вектора — компоненты вектора b.

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

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

а оценки компонент вектора b можно найти из системы уравнений [см. (21.41)] , где — элемент выборочной ковариационной матрицы