2.2. Расстояние между кластерами

Как понимать расстояние между кластерами и как его вычислять? В отличие от точек кластеры занимают определенный объем многомерного пространства и состоят из многих точек. Как, например, можно определить расстояние от Минска до Москвы, от Москвы до Владивостока, или от Минска до Санкт-Петербурга? Можно принять за это расстояние протяженность прямой линии соединяющей главпочтамты этих городов. А можно измерить расстояние между главпочтамтами по автомобильной дороге, по железной дороге или вычислив протяженность авиалиний. Но эти методы не единственные из возможных. Учитывая протяженность самих объектов, можно понять, что эти расстояния будут различаться, если их измерять между ближними окраинами этих городов, или между дальними окраинами. Можно также произвести измерение расстояния между геометрическими центрами этих городов. Однако в этом случае надо знать, что будет считаться геометрическим центром города?

Аналогично описанным вариантам в кластерном анализе широко используются межкластерные расстояния, вычисляемые по принципу ближайшего соседа (nearest neighbour) (расстояния между ближними домами двух городов), центра тяжести, дальнего соседа (furthest neighbour), медиан. Наиболее широко используются четыре метода: (1) одиночной связи; (2) полной связи; (3) средней связи и (4) метод Варда (во многих источниках этот метод называется метод Уорда).

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

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

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

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

2.4. Объединение (древовидная кластеризация)

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