2.4.1. Иерархическое дерево

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

Рис. 2.2. Горизонтальный график-дендрограмма

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

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

2.4.2. Меры расстояния

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

Наиболее прямой путь вычисления расстояний между объектами в многомерном пространстве состоит в вычислении евклидовых расстояний. Если имеется двух- или трёхмерное пространство, то эта мера является реальным геометрическим расстоянием между объектами в пространстве (так, если бы расстояния между объектами были измерены рулеткой). Задачей исследователей при использовании алгоритма объединения является подобрать правильный метод с учетом специфики применений.

Евклидово расстояние. Это наиболее общий тип расстояния представляющий собой геометрическое расстояние в многомерном пространстве. Евклидово расстояние вычисляется следующим образом:

расстояние (х,у) = {i (хi - yi)² }^1/2 (2.1).

Следует отметить, что евклидово расстояние (и его квадрат) вычисляется по исходным, а не по стандартизованным данным. (Поэтому, например, в психологии, он является наиболее используемым.) Это обычный способ его вычисления, который имеет определенные преимущества (например, расстояние между двумя объектами не изменяется при введении в анализ нового объекта, который может оказаться выбросом). Тем не менее, на расстояния могут сильно влиять различия между осями, по координатам которых вычисляются эти расстояния. К примеру, если одна из осей измерена в сантиметрах, то при переводе ее в миллиметры (умножая значения на 10), окончательное евклидово расстояние (или квадрат евклидова расстояния), вычисляемое по координатам, сильно изменится, и, как следствие, результаты кластерного анализа могут сильно отличаться от предыдущих.

Квадрат евклидова расстояния. Используется, когда возникает необходимость возвести в квадрат стандартное евклидово расстояние, чтобы придать большие веса более отдаленным друг от друга объектам. Это расстояние вычисляется следующим образом:

расстояние (х,у) = i (x_i - y_i)² (2.2).

Расстояние «городских кварталов» (манхэттенское расстояние). Является просто средним разностей по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако, для этой меры влияние отдельных больших разностей (выбросов) уменьшается (так как они не возводятся в квадрат). Манхэттенское расстояние вычисляется по формуле:

расстояние (х,у) = i |(x_i - y_i)| (2.3).

Расстояние Чебышева. Расстояние используется в том случае, когда два объекта необходимо определить как «различные», если они отличаются по какой-либо одной координате (каким-либо одним измерением). Расстояние Чебышева вычисляется по формуле:

расстояние (х,у) = Максимум |(x_i - y_i)| (2.4).

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

расстояние (х,у) = (i |(x_i - y_i)| ^р)^1/r (2.5).

где r и р — параметры, определяемые исследователем. Например, параметр р может отвечать за постепенное взвешивание разностей по отдельным координатам, параметр r — за прогрессивное взвешивание больших расстояний между объектами. Если оба параметра — r и р, равны двум, то это расстояние совпадает с расстоянием Евклида.

Процент несогласия. Эта мера используется в тех случаях, когда данные являются категориальными. Расстояние вычисляется по формуле:

расстояние (х,у) = (Количествоx_i y_i)/i (2.6).

Результатом вычисления расстояний между объектами в многомерном пространстве является матрица расстояний, которая может быть получена с помощью разнообразных метрик: евклидовой, Чебышева, «городских кварталов» и т.д. Выбор метрики, как указывалось выше, производится самим исследователем. После вычисления матрицы расстояний начинается процесс агломерации (от латинского agglomero — присоединяю, накапливаю), проходящий последовательно шаг за шагом. На первом шаге этого процесса два исходных наблюдения (монокластера), между которыми самое минимальное расстояние, объединяются в один кластер, состоящий уже из двух объектов (наблюдений). Таким образом, вместо бывших N монокластеров (кластеров, состоящих из одного объекта) после первого шага останется N-1 кластеров, из которых один кластер будет содержать два объекта (наблюдения), а N-2 кластеров будут по-прежнему состоять всего лишь из одного объекта. Следует отметить, что на втором шаге возможны различные методы объединения между собой N-2 кластеров. Это объясняется тем, что один из этих кластеров уже содержит два объекта. По этой причине возникает два основных вопроса: 

1. как вычислять координаты такого кластера из двух (а далее и более двух) объектов; 

2. как вычислять расстояние до таких "полиобъектных" кластеров от "монокластеров" и между "полиобъектными" кластерами.

Эти вопросы, как указывает В.П.Леонов, в конечном счете, и определяют окончательную структуру итоговых кластеров (под структурой кластеров подразумевается состав отдельных кластеров и их взаимное расположение в многомерном пространстве). Разнообразные комбинации метрик и методов вычисления координат и взаимных расстояний кластеров и порождают то многообразие методов кластерного анализа, о котором было сказано выше. На втором шаге в зависимости от выбранных методов вычисления координат кластера состоящего из нескольких объектов и способа вычисления межкластерных расстояний возможно либо повторное объединение двух отдельных наблюдений в новый кластер, либо присоединение одного нового наблюдения к кластеру, состоящему из двух объектов. Большинство системных программ (например, SPSS, STATISTICA и др.) агломеративно-иерархических методов по окончании работы могут предоставить для просмотра два основных графика. Первый график называется дендрограммой (от греческого dendron — дерево), отражающий процесс агломерации, слияния отдельных наблюдений в единый окончательный кластер. Этот график схематично напоминает дерево, за что и получил такое название.

Ниже приводится пример предложенный В.П.Леоновым, в котором исследуются 5 наблюдений по двум переменным. Результаты кластеризации отражены на дендрограмме (рис. 2.3).

Рис. 2.3. График-дендрограмма

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