11.3. Алгоритмы классификации с адаптивной метрикой

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

11.3.1. Адаптивная махаланобисова метрика.

Квадрат расстояния между точками задается в этом случае (см. гл. 5) как

где V — некоторая положительно-определенная симметричная матрица. Для определенности положим, что определитель V равен .

Докажем следующую лемму.

Лемма 11.1. Пусть расстояние между точками задано в виде (11 7); точки распадаются на k непересекающихся кластеров — матрица полного рассеивания (ковариационная матрица для X).

Пусть теперь W — величина внутриклассового рассеивания, вычисленная на основе расстояния (11.7),

Минимальное значение достигается на множестве положительно-определенных матриц V с единичным определителем тогда, когда матрица — матрица внутриклассового разброса

а множитель а выбран таким, чтобы

Доказательство. Величину внутриклассового разброса можно представить в виде

(11.10)

Дальше доказательство аналогично доказательству теоремы в приложении 1 [106, гл. 12].

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

Фаза 1. При фиксированной метрике (t — номер шага итерации) проводим разделение выборки X с помощью алгоритма -средних (Мак-Кина). Число классов k задается пользователем при начале работы алгоритма и дальше не меняется.

Фаза 2. По полученной классификации вычисляем матрицу внутриклассового разброса согласно формуле (11.9). Вводим новую метрику с матрицей

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

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

либо

Сходимость алгоритма (в вычислительном отношении) следует из того, что на каждой фазе работы алгоритма значение критерия W убывает.

11.3.2. Состоятельность алгоритма с адаптивной махаланобисовой метрикой.

Рассмотрим следующую вероятностную модель — смесь элипсоидально-симметричных распределений (см. гл. 19) с ограниченными непересекающимися носителями и одинаковой ковариационной матрицей

Рис. 11.1. Классификация даииых табл. 11.1

Тогда, если X — выборка из такого распределения, то верна следующая лемма.

Лемма 11.2. Алгоритм с адаптивной махаланобисовой метрикой есть ЕМ-алгоритм (см. гл. 6) решения уравнения правдоподобия для оценки параметров смеси: набора весов k), средних векторов компонент М, и матрицы ковариаций W. Соответствующими оценками будут величины titn, оцененные на последнем шаге работы алгоритма. Поскольку ЕМ-алгоритм дает оценку максимального правдоподобия, то состоятельность получаемых оценок (при ) следует из общей теории.

Пример 11.1. Рассмотрим набор двумерных данных из п. 12.5.2 (табл. 11.1).

Результаты применения алгоритма из п. 11.3.1 представлены на диаграмме рассеивания (рис. 11.1) («крестик» — точки, отнесенные в 1-й кластер, «квадрат» — точки, отнесенные во 2-й кластер). Состав кластеров: первые 20 точек из табл. 11.1 — первый кластер, точки с 21 по 40 — второй. Как можно судить по рисунку, обычная евклидова метрика здесь не дала бы успешной классификации.

Таблица 11.1

Исходная матрица

Матрица V пекле четырех итераций (конец работы алгоритма) практически совпала с результирующей матрицей, полученной в [106].

11.3.3. Адаптивная взвешенная евклидова метрика. Предположим, что матрица V в (11.7) диагональна: Тогда (11.7) соответствует взвешенной евклидовой метрике. Действуя так же, как в лемме 11.1, можно показать, что веса минимизирующие внутриклассовый разброс , определяются соотношениями

(11.11)

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

Состоятельность алгоритма, описанного в п. 11.3.1, будет теперь иметь место только в случае модели смеси распределений с диаюнальной внутрикомпонентной матрицей рассеивания (см. лемму 11.2). Поэтому на практике можно заменить (11.11) более простым выражением

(11.12)

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

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

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

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

11.3.4. Адаптивная взвешенная метрика типа «сити-блок».

Расстояние в этой метрике определяется как

Потребуем, чтобы состоит из двух фаз, как и в п. 11.3.1, но имеются следующие отличия:

1) центр класса определяется как вектор, компоненты которого суть медианные значения признаков в классе;

2) внутриклассовый разброс находится по формуле

(11.13)

На фазе 2 вектор весов V, минимизирующий , определяется (см. [106, п. 12.4.2.2]) из следующего выражения

Заметим, что в 1106] приведены выражения для , т. е. метрика считается разной в разных классах. Здесь приведен вариант весов, полученный в предположении одинаковости весов во всех классах.