Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ
Посмотреть оригинал

Иерархическая кластеризация

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

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

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

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

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

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

Пример дендрограммы

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

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

  • [1] См.: Маннинг К. Д., Рагхаван П. Введение в информационный поиск.
 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы