Глава 12. АДАПТИВНЫЕ РАССТОЯНИЯ

12.1. ВВЕДЕНИЕ

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

12.2. МЕТОД АДАПТИВНЫХ РАССТОЯНИЙ

12.2.1. Пространство представительств

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

Мера сходства между подмножеством состоящим из конечного числа элементов, и задается соотношением

Если квадрат расстояния от точки а и элементы множества В имеют массу 1, то инерция множества В относительно точки а.

12.2.2. Алгоритм

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

12.2.2.1. Функция назначения

Следуя 1.2.4, определим функцию назначения как отображение

Если то является разбиением где

Поскольку можно записать так:

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

12.2.2.2. Функция представительства

Следуя 1.2.3, определим функцию представительства как отображение

Если некоторое разбиение на классов, то где такое, что

Ниже будет раскрыт смысл пары

Предложение. Если В — конечное подмножество то пара определяемая из условия

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

Это утверждение является следствием двух классических результатов.

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

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

12.2.2.3. Свойства алгоритма

Сходимость доказана для общего случая (см. 1.3.6).

Критерий имеет вид

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

Очевидно, что метрика не выбрана раз и навсегда, а определяется для каждого класса заново.

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

Предложение 1. Критерий (2) может быть записан в виде

где ковариационная матрица класса

Доказательство. Критерий (2) является суммой инерций, а каждая инерция в метрике Махаланобиса равна (см. [6]).

Предложение 2. С помощью описанной процедуры определяются такие классы, для каждого из которых произведение дисперсий по главным осям инерции минимально.

Доказательство. Можно заменить матрицы в выражении (3) на полученные диагонализацией так как Каждый элемент матрицы равен дисперсии класса относительно главной оси инерции, т. е. (см. приложение 2). Следовательно,

Свойство инвариантности

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

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

12.2.3. Случай необратимой ковариационной матрицы

12.2.3.1. Постановка задачи

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

Пусть на некотором шаге имеется разбиение и требуется вычислить Если то где — центр тяжести класса а расстояние определяется матрицей Критерий может быть записан в виде

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

Предложение 4. Если нельзя обратить, то такое, что

Доказательство. Обозначим через X и вектор-столбцы пространства соответствующие Пусть тогда имеем

где матрица, определяющая По определению

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

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

Из равенства следует а значит, Отсюда вытекает (4).

Следствие. Если матрица не является обратимой, то не существует расстояния, минимизирующего

12.2.3.2. Решение

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

На предыдущем шаге вклад класса в критерий был равен Везде будем полагать равным центру тяжести класса Таким образом,

Достаточно выбрать такое чтобы

и вклад класса в критерий будет улучшен. Имеем

Будем действовать как при доказательстве предложения 4: заменяя на воспользуемся таким преобразованием базиса, при котором будет определяться матрицей представимой в виде

Обозначим через — -мерный вектор, состоящий только из первых координат — X (оставшиеся координат равны нулю):

Будем искать матрицу минимизирующую выражение (6). Согласно приложению 1 имеем

где

Матрица обратима, поскольку линейная оболочка векторов совпадает с

Определим расстояние такой матрицей что

где

Тогда

Таким образом, расстояние улучшает вклад класса в критерий.

12.2.4. Пример применения метода адаптивных расстояний

12.2.4.1. Исходные данные

Мы будем использовать данные из [4] и [8] для решения задачи оценивания смеси распределений. Имеется 150 точек, взятых из 3 двумерных нормальных распределений, определяемых средними

и ковариационными матрицами

На рис. 12.2 представлено геометрическое изображение данных, на рис. 12.1 приводятся координаты элементов выборки. Первые 50 точек принадлежат первому распределению, точки с номерами 51—100 имеют распределение со средним и второй ковариационной матрицей, а последние 50 точек принадлежат третьему классу.

(кликните для просмотра скана)

12.2.4.2. Результаты

Использовался алгоритм адаптивных расстояний, причем число классов задавалось равным 2, 3, 4, 5, 7, 9. Для каждого случая производилось 20 классификаций и выбиралась та, которой соответствовало наименьшее значение критерия. На рис. 12.3 (а)-(е) представлены соответствующие результаты классификации и значения критерия

Рис. 12.3(a). Два класса

Рис. 12.3(6). Три класса

Рис. 12.3(b). Четыре класса

Рис. 12.3(г). Пять классов

Рис. 12.3(д). Семь классов

Рис. 12.3(e). Девять классов

12.2.4.3. Результаты, полученные методом динамических сгущений с использованием единого расстояния

Число классов было взято равным трем. Каждое представительство состояло из трех точек исходного множества. Использовалось евклидово расстояние. На рис. 12.4 приводится наилучшая из 20 классификаций.

Рис. 12.4. Метод динамических сгущений (расстояние фиксировано)

12.2.4.4. Заключение

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

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

Заметим, что метод разделения смеси распределений [8] дает примерно те же результаты, что и метод адаптивных расстояний. В самом Деле, разница между двумя алгоритмами невелика и заключается только в вычислении расстояний: водном случае в качестве расстояния между точкой и парой берется а в другом —

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