Иерархическая кластеризация. 
Интеллектуальные системы

Постановка задачи иерархической кластеризации

Плоские алгоритмы кластеризации (именно к ним относится алгоритм кластеризации ^-средними) выполняют только разбиение исходного множества объектов на кластеры, каждый кластер которого представляется неструктурированным множеством объектов. Более того, в сил}' рандомизирующей инициализации алгоритм^{-средних} может давать различные ответы при разных запусках на одном и том же наборе данных, т. е. данный алгоритм является недетерминированным. Иерархические алгоритмы кластеризации лишены недостатка малой информативности — за счет дополнительных временных затрат на выходе таких алгоритмов все множество объектов представляется в виде иерархии вложенных друг в друга кластеров, что может дать исследователю данных дополнительную полезную информацию о структуре данных. Также большинство алгоритмов иерархической кластеризации являются детерминированными, что в некоторых случаях представляет собой ценность.

Алгоритмы иерархической кластеризации можно поделить на две большие группы^[1]:

• 1) алгоритмы восходящей иерархической кластеризации;
• 2) алгоритмы нисходящей кластеризации.

Первая группа алгоритмов работает по принципу первоначального объединения отдельно стоящих объектов в близкие друг друг}' пары объектов, затем пары объединяются с другими по тому же принципу и т. д., пока не останется всего один кластер, содержащий в себе все точки исходного множества объектов. Алгоритмы нисходящей иерархической кластеризации действуют по обратному принципу — сначала выбирается максимально большой кластер, содержащий все объекты выборки, который затем постепенно разбивается на множество кластеров-потомков.

Объекты выборки представляются в виде иерархии кластеров, называемой также дендрограммой (dendrogram) (рис. 6.2).

Рис. 6.2. Пример дендрограммы.

Как видно из рис. 6.2, для входной выборки может быть построено любое количество кластеров — на самом нижнем уровне содержатся только объекты в качестве кластеров, далее они по одному присоединяются к ближайшим кластерам, и если задать правило, по которому можно произвести сечение дендрограммы, т. е. «отрезать» нижние ветви, то такой алгоритм кластеризации сам сможет определить число кластеров для минимизации целевой функции.

• [1] См.: Маннинг К. Д., Рагхаван П.

  Введение

  в информационный поиск.