6.11. Методы использующие теорию графов

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

Мы начнем наш краткий обзор методов теории графов, вернув­шись к рассмотрению простой процедуры, которая строила графы, показанные на рис. 6.8. Здесь было выбрано пороговое расстоянии d₀ и считалось, что две точки находятся в той же группе, если расстояние между ними меньше d_0. Эту процедуру легко обобщить для применения к произвольным мерам подобия. Предположим, что мы выбрали пороговое значение s₀, и будем говорить, что x подобен x', если s(x, x')> s₀. Это определяет матрицу подобия S=[s_ij] размера nХп.

Эта матрица определяет граф подобия, в котором вершины соот­ветствуют точкам и ребро соединяет вершины i и j тогда и только тогда, когда s_ij =l.

Группировка, полученная при помощи алгоритма единственной связи и модифицированного алгоритма полной связи, легко описывается при помощи этого графа.

Рис. 6.19.Группы, образованные удалением несовместимых ребер (Цань, 1971). а —множество точек, б —минимальное покрывающее дерево,в —группы.

В случае алгоритма единственной связи две выборки х и х' находятся в одной группе тогда и только тогда, когда существует цепь x₁, x₂, . . ., х_k, такая, что х подобен x₁, x₁ подобен x₂ и т. д. для всей цепи. Следовательно, такая группи­ровка соответствует связанным компонентам в графе подобия. В слу­чае алгоритма полной связи все выборки в данной группе должны быть подобны друг другу, и ни одна выборка не должна находиться более чем в одной группе. Если мы опускаем второе требование, то тогда такая группировка соответствует максимальным полным под­графам в графе подобия, причем в «наибольших» подграфах ребра объединяют все пары вершин. (В общем случае группы, полученные с помощью алгоритма полной связи, можно найти среди максималь­ных полных подграфов, но их нельзя определить, не зная степени подобия.)

В предыдущем разделе мы заметили, что алгоритм ближайшего соседа можно рассматривать как алгоритм нахождения минималь­ного покрывающего дерева. Обратно, при данном минимальном покрывающем дереве можно найти группировки, полученные по алгоритму ближайшего соседа. Удаление самого длинного ребра вызывает разделение на две группы, удаление следующего по длине ребра — разделение на три группы' и т. д. Это дает способ получения делимой иерархической процедуры и предлагает другие возможности деления графа на подграфы. Например, при выборе ребра — кандидата на удаление мы можем сравнить его длину с длинами других ребер, прилегающих к его вершинам. Назовем ребро несовместимым, если его длина l значительно больше l (с чертой) — средней длины всех других ребер, прилегающих к его вершинам. На рис. 6.19 показаны минимальное покрывающее дерево для двумерного множества точек и группы, полученные систематическим удалением всех ребер, чья длина l больше 2l(с чертой). Отметим чувствительность этого критерия к локальным условиям, дающую результаты, которые значительно отличаются от простого удаления двух самых длинных ребер.

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

Рис. 6.20.Минимальное покрывающее дерево с бимодальным распределением длин ребер

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