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

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

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

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

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

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

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

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