11.2.2. Сходимость процедуры, основанной на правиле ближайшего среднего.

Полученные выше результаты приводят к следующей процедуре автоматической классификации [Фукунага, 1970 г].

1. Применить совместную нормировку.

2. Классифицировать объекты, используя правило ближайшего среднего.

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

Нормальные распределения с равными ковариационными матрицами.

Если два нормальных распределения имеют одинаковые ковариационные матрицы байесовская оптимальная разделяющая поверхность при условии совместной нормировки представляет собой гиперплоскость вида

Действуя так же, как в (4.68), можно привести (11.36) к виду

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

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

Рис. 11.2. Разделение двух распределений.

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

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

где

(если находится в области то используется положительный знак; если находится в то — отрицательный знак) и

Здесь — это центр масс — центр масс и . Следовательно, можно вычислить следующим образом:

Подставляя выражения (11.38) — (11.43) в (11.45) и (11.46), имеем

В случае равных ковариационных матриц

Далее, пользуясь условиями совместной нормировки (11.23) и (11.24) (или (4.62) и (4.63)), матрицы можно выразить в виде функции от Таким образом, (11.47) принимает вид

где

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

и условие сходимости принимает вид

Легко видеть, что для некоторых сочетаний параметров неравенство (11.53) не выполняется.

Рис. 11.3. Области сходимости [Фукунага,

Можно, однако, вычислить границы области значений параметров, где оно выполняется. Результат приведен на рис. 11.3. Неравенство (11.53) содержит три параметра или

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

Сходимость в случае неравных ковариационных матриц.

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

Предположим, что гиперплоскость проходит через точку, в которой

Тогда, подставляя (11.23) и (11.24) в (11.47), получим

Рассуждая так же, как мы это делали выше, получим следующее условие сходимости:

которое, используя (11.52) и (11.55), можно представить в виде

или

Это неравенство выполняется для всех

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

Пример 11.1. В дополнение к теоретическим исследованиям, рассмотрим результаты численных экспериментов.

Таблица 11.1 (см. скан) Результаты классификации для стандартных данных

В этих экспериментах объекты генерировались в соответствии с нормальными распределениями с заданными математическими ожиданиями и ковариационными матрицами. Математические ожидания и ковариации брались из стандартных данных.

Таблица 11.2 (см. скан) Результаты классификации для стандартных данных

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

ближайшего среднего. Затем производилась «совместная нормировка» объектов и они снова классифицировались.

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

Рис. 11.4. График разброса экспериментальных объектов, а) Исходное распределение; 6) после совместной нормировки [Фукунага. 1970 г].

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

Три класса. В этом эксперименте генерировалось по 100 объектов каждого класса в соответствии со стандартными данными . Далее применялась та же самая процедура. Результаты приведены в табл. 11.2. На рис. 11.4 показаны проекции данных на плоскость в исходной и нормированной системах координат.