6.10.2.1. Алгоритм <і.ближайший сосед»

Рассмотрим сначала случай, когда используется dmin*). Предположим, что мы рассматриваем точки данных как вершины графа, причем ребра графа образуют путь между вершинами в том же подмножестве Когда для измерения расстояния между подмножествами используется cfmin, ближайшие соседи определяют ближайшие подмножества. Слияние.^г- и соответствует добавлению ребра мевду двумя ближайшими вершинами в ^ и Sj. Поскольку ребра, соединяющ,ие группы, всегда проходят между различными группами, результирующий граф никогда не имеет замкнутых контуров или цепей; пользуясь терминологией теории графов, можно сказать, что эта процедура генерирует дерево. Если так продолжать, пока все подмножества не будут соединены, в результате получим покрываю- іцее дерево (остов) — дерево с путем от любой вершины к любой другой вершине. Более того, можно показать, что сумма длин ребер результирующего дерева не будет превышать суммы длин ребер для любого другого покрывающего дерева для данного множества выборок. Такйм образом, используя в качестве меры расстояния, агломеративная процедура группировки превращается в алгоритм для генерирования минимального покрывающего дерева.

Рис. 6.17 показывает результат применения этой процедуры к данным из рис. 6.16. Во всех случаях процедура заканчивалась при с=2. Минимальное покрывающее дерево можно получить, добавляя самое короткое ребро между двумя группами. В первом случае, где группы компактны и хорошо разделены, найдены явные группы. Во втором случае наличие некоторых точек, расположенных так, что между группами создан некоторый мост, приводит к довольно неожиданной группировке в одну большую продолговатую группу и в одну маленькую компактную группу. Такое поведение часто называют «цепным эффектом» и иногда относят к недостаткам этой меры расстояния. В случае, когда результаты очень чувствительны к шуму или к небольшим изменениям в положении точек данных, такая критика вполне законна. Однако, как иллюстрирует третий случай, та же тенденция формирования цепей может считаться преимуществом, если группы сами по себе вытянуты или имеют вытянутые отростки.