6.11. МЕТОДЫ, ИСПОЛЬЗУЮЩИЕ ТЕОРИЮ ГРАФОВ

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

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

где

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

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

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

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

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

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

(см. скан)

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

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

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

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