Введение в алгоритм иерархической кластеризации
Алгоритм иерархической кластеризации является неконтролируемой техникой машинного обучения. Он направлен на поиск естественной группировки на основе характеристик данных.
Алгоритм иерархической кластеризации направлен на поиск вложенных групп данных путем построения иерархии. Это похоже на биологическую таксономию растительного или животного мира. Иерархические кластеры обычно представлены с использованием иерархического дерева, известного как дендрограмма.
Типы алгоритма иерархической кластеризации
Алгоритмы иерархической кластеризации бывают двух типов:
- разделяющий
- агломерационных
1. Разделительный
Это нисходящий подход, при котором изначально все данные рассматриваются как одна группа, а затем итеративно разбиваются данные на подгруппы. Если известен номер алгоритма иерархической кластеризации, то процесс разделения останавливается, как только достигается количество кластеров. Иначе, процесс останавливается, когда данные больше не могут быть разделены, что означает, что подгруппа, полученная из текущей итерации, такая же, как и полученная из предыдущей итерации (можно также считать, что деление останавливается, когда каждая точка данных является кластером ).
2. Агломерационный
Это восходящий подход, основанный на объединении кластеров. Первоначально данные разбиваются на m одноэлементных кластеров (где значение m - это количество выборок / точек данных). Два кластера объединяются в один итеративно, что сокращает количество кластеров в каждой итерации. Этот процесс объединения кластеров останавливается, когда все кластеры объединяются в одно или достигается желаемое количество кластеров.
На уровне 1 есть m кластеров, которые уменьшаются до 1 кластера на уровне m. Те точки данных, которые объединяются в кластер на более низком уровне, остаются в том же кластере на более высоких уровнях. Например, предположим, что есть 8 точек x1..x8, поэтому изначально на уровне 1 есть 8 кластеров. Предположим, точки x1 и x2 объединяются в кластер на уровне 2, затем до уровня 8 они остаются в том же кластере.
На приведенном выше рисунке показано дендрограммное представление подхода агломерационной кластеризации для 8 точек данных, а также шкала сходства, соответствующая каждому уровню.
Уровни кластеров дают нам представление о том, насколько похожи точки данных в кластерах. Как показано на рис. 1, ранее точки данных объединялись в кластер, как и они. Таким образом, точки данных в кластере на уровне 2 (например, x2 и x3) более похожи, чем точки данных в кластере на уровне 6 (например, x1 и x2).
На приведенном выше рисунке показано представление набора или диаграммы Венна агломеративного кластерного подхода вышеупомянутых 8 точек данных. И дендрограммы, и представления множеств могут использоваться для кластеризации. Тем не менее, дендрограмма обычно является предпочтительным представлением активов не может количественно представлять сходства кластеров.
Шаги для алгоритма иерархической кластеризации
Давайте рассмотрим следующие шаги для алгоритма иерархической кластеризации, которые приведены ниже:
1. Алгоритм
Алгоритм агломерационной иерархической кластеризации
- Начните инициализацию c, c1 = n, Di = (xi), i = 1, …, n '
- Do c1 = c1 - 1
- Найти ближайшие кластеры, скажем, Di и Dj
- Объединить ди и диджея
- Пока с = с1
- Возврат с кластеров
- Конец
Этот алгоритм начинается с n кластеров, где каждая точка данных является кластером. С каждой итерацией количество кластеров уменьшается на 1 по мере объединения двух ближайших кластеров. Этот процесс продолжается до тех пор, пока количество кластеров не уменьшится до предварительно определенного значения c.
Как решить, какие кластеры рядом?
Это определяется с использованием нескольких метрик расстояния, которые следующие:
- Минимальное расстояние между кластерами dmin (Di, Dj). Полезно для одного.
- Максимальное расстояние между кластерами dmax (Di, Dj). Полезно для завершения.
- Среднее расстояние между кластерами davg (Di, Dj).
Что такое одиночная связь и полная связь?
- Когда dmin (di, dj) используется для нахождения расстояния между двумя кластерами, и алгоритм завершается, если расстояние между ближайшими кластерами превышает пороговое значение, тогда алгоритм называется алгоритмом единой связи.
- Когда dmax (Di, Dj) используется для нахождения расстояния между двумя кластерами, и алгоритм завершается, если расстояние между ближайшими кластерами превышает пороговое значение, тогда алгоритм называется полным алгоритмом связи.
- Рассмотрим каждую точку данных как узел графа. Между двумя точками данных есть грань, если они принадлежат одному кластеру. Когда два ближайших кластера объединены, ребро добавляется. Это называется одиночной связью, потому что существует уникальный путь от одного узла к другому.
- Алгоритм полного сцепления объединяет два кластера, минимизируя расстояние между двумя самыми дальними точками.
- Алгоритм единой связи генерирует остовное дерево. Однако этот алгоритм чувствителен к шуму. Полный алгоритм связывания генерирует полный граф.
Что такое временная сложность алгоритма?
Предположим, у нас есть n шаблонов в d-мерном пространстве, и мы используем dmin (Di, Dj) для формирования c кластеров. Нам нужно вычислить n (n - 1) междурядийных расстояний - каждое из которых является расчетом O (d 2 ) - и поместить результаты в таблицу междисциплинарных расстояний. Пространственная сложность O (n 2 ). Поиск пары минимальных расстояний (для первого слияния) требует, чтобы мы пошагово прошли по всему списку, сохранив индекс наименьшего расстояния.
Таким образом, для первого этапа агломерации сложность O (n (n - 1) (d 2 + 1)) = O (n 2 d 2 ). Для другого произвольного шага агломерации (т. Е. От c1 до c1 - 1) мы просто перебираем n (n - 1) - c1 «неиспользуемые» расстояния в списке и находим наименьшее, для которого x и x 'лежат в разных кластерах., Это опять-таки O (n (n − 1) −c1). Таким образом, общая сложность времени составляет O (cn 2 d 2 ), а в типичных условиях n >> c.
2. Визуализация
Когда данные разбиты на кластеры, рекомендуется визуализировать кластеры, чтобы получить представление о том, как выглядит группировка. Но визуализировать эти многомерные данные сложно. Следовательно, мы используем анализ основных компонентов (PCA) для визуализации. После PCA мы получаем точки данных в низкоразмерном пространстве (обычно 2D или 3D), которые мы можем построить, чтобы увидеть группировку.
Примечание. Высокое измерение означает большое количество объектов, а не количество точек данных.3. Оценка
Одним из методов оценки кластеров является то, что расстояние между точками между кластерами (межкластерное расстояние) должно быть намного больше, чем расстояние между точками в пределах кластера (внутрикластерное расстояние).
Вывод
Ниже приведены некоторые ключевые выводы:
- Алгоритм иерархической кластеризации используется для поиска вложенных шаблонов в данных
- Иерархическая кластеризация бывает двух типов - делительная и агломерационная.
- Дендрограмма и сет / диаграмма Венна могут быть использованы для представления
- Одиночная связь объединяет два кластера, минимизируя минимальное расстояние между ними. Образует остов
- Полная связь объединяет два кластера, минимизируя максимальное расстояние между ними, образуя полный граф.
- Общая временная сложность алгоритма иерархической кластеризации составляет O (cn 2 d 2 ), где c - это предварительно определенное количество кластеров, n - это количество шаблонов, а d - это d-мерное пространство из n шаблонов.
Рекомендуемые статьи
Это руководство по алгоритму иерархической кластеризации. Здесь мы обсуждаем типы и этапы алгоритмов иерархической кластеризации. Вы также можете посмотреть следующие статьи, чтобы узнать больше
- Иерархический кластерный анализ
- Иерархическая кластеризация в R '
- Алгоритм кластеризации
- Что такое кластеризация в интеллектуальном анализе данных?
- Иерархическая кластеризация | Агломерационная и разделительная кластеризация
- С ++ Алгоритм | Примеры алгоритма C ++