Иерархическая кластеризация группирует (агломеративный или также называемый восходящим подходом) или делит (разделительный или также называемый нисходящим подходом) кластеры на основе показателей расстояния. В агломеративной кластеризации каждая точка данных сначала действует как кластер, а затем группирует кластеры один за другим.
Разделительный — это противоположность агломеративному, он начинается со всех точек в один кластер и разделяет их для создания большего количества кластеров. Эти алгоритмы создают матрицу расстояний всех существующих кластеров и выполняют связь между кластерами в зависимости от критериев связи. Кластеризация точек данных представлена с помощью дендрограммы. Существуют различные типы связей: –
o Одинарная связь: — При одиночной связи расстояние между двумя кластерами является кратчайшим расстоянием между точками в этих двух кластерах.
o Полная связь: — При полной связи расстояние между двумя кластерами является самым дальним расстоянием между точками в этих двух кластерах.
o Средняя связь: — В средней связи расстояние между двумя кластерами представляет собой среднее расстояние каждой точки в кластере с каждой точкой в другом кластере.
Оба этих алгоритма полностью обратны друг другу. Итак, мы подробно рассмотрим алгоритм агломерационной иерархической кластеризации.
Как работает алгоритм агломерационной иерархической кластеризации
Для кластеризации набора из N наблюдений:
- Начните назначать каждое наблюдение как кластер с одной точкой, так что если у нас есть N наблюдений, у нас будет N кластеров, каждый из которых содержит только одно наблюдение.
- Найдите ближайшую (наиболее похожую) пару кластеров и объедините их в один кластер, теперь у нас есть кластеры N-1.Это можно сделать различными способами, чтобы идентифицировать похожие и несходные меры.
- Найдите два ближайших кластера и объедините их в один кластер. Теперь у нас есть N-2 кластера. Это можно сделать с помощью методов агломеративной кластеризации.
- Повторяйте шаги 2 и 3, пока все наблюдения не будут сгруппированы в один кластер размера N.
Алгоритмы кластеризации используют различные меры расстояния или различия для создания различных кластеров. Меньшее/ближе расстояние указывает на то, что данные или наблюдения похожи и будут сгруппированы в один кластер. Помните, что чем выше сходство изображает наблюдение, тем похоже.
Шаг 2 можно выполнить различными способами, чтобы определить похожие и несходные показатели. А именно,
- Евклидово расстояние
- Манхэттен Расстояние
- Расстояние Минковского
- Коэффициент подобия Жаккара
- Косинус сходства
- Коэффициент подобия Гауэра