6.10.2.2. Алгоритм (/.дальний сосед»

Когда для измерения расстояния между группами используются с!п,ах> возникновение вытянутых групп является нежелательным ^). Применение процедуры можно рассматривать как получение графа, в котором ребра соединяют все вершины в группу. Пользуясь терминологией теории графов, можно сказать, что каждая группа образует полный подграф. Расстояние между двумя группами определяется наиболее удаленными вершинами в этих двух группах. Когда

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