Алгоритм иерархической кластеризации для машинного обучения

Краткое руководство по машинному обучению

Алгоритмы иерархической кластеризации стремятся построить иерархию кластеров. Он хорошо работает для набора данных с вложенными кластерами, например. геометрические данные.

Он начинается с некоторых начальных кластеров и постепенно сходится к решению. Иерархическая кластеризация подразделяется на две категории: агломеративные и вызывающие разногласия.

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

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

Как работает алгоритм иерархической кластеризации?

Алгоритм агломеративной иерархической кластеризации включает следующие шаги:

1. В качестве начального шага алгоритм принимает каждую точку данных как единый кластер, и мы выбираем конкретную матрицу близости для определения расстояния между кластерами.
2. Для матрицы близости доступны четыре функции расстояния: одиночное звено (мин.), Среднее звено, полное звено и опора (макс.). Одиночная связь означает, что расстояние между двумя кластерами определяется как минимальное расстояние между одной точкой первого кластера и другой точкой второго кластера. Полная связь занимает максимальное расстояние, равное двум значениям точек данных, как расстояние между двумя кластерами.
3. Среднее связывание вычисляет расстояние между всеми точками данных от первого кластера со всеми остальными от второго кластера и принимает среднее расстояние как расстояние между кластерами. Уорд похож на среднее сцепление, за исключением того, что он использует сумму квадратов для вычисления расстояния между точками. В этом исследовании мы используем ward как функцию расстояния.
4. Чтобы найти ближайшую пару кластеров, он вычисляет сходство (расстояние) между каждым из кластеров.
5. Затем похожие кластеры объединяются, чтобы сформировать кластер в соответствии с функцией расстояния.
6. Итерация шагов 4 и 5 продолжается до тех пор, пока все точки данных не будут объединены в один последний кластер.

В общем, иерархическая кластеризация формирует единое дерево кластеров, где каждый узел представляет кластеры, а каждая точка данных начинается как лист дерева. Корень дерева - это последний кластер, содержащий все точки данных. На этом рисунке показано, как иерархическая кластеризация вырезает k кластеров из последнего кластера (полного дерева). На рисунке алгоритм последовательно формирует единое дерево кластеров, а затем разрезает на определенном уровне k, в результате чего получается 4 кластера.

Пример

import numpy as np

from matplotlib import pyplot as plt
from scipy.cluster.hierarchy import dendrogram
from sklearn.datasets import load_iris
from sklearn.cluster import AgglomerativeClustering


def plot_dendrogram(model, **kwargs):
    # Create linkage matrix and then plot the dendrogram

    # create the counts of samples under each node
    counts = np.zeros(model.children_.shape[0])
    n_samples = len(model.labels_)
    for i, merge in enumerate(model.children_):
        current_count = 0
        for child_idx in merge:
            if child_idx < n_samples:
                current_count += 1  # leaf node
            else:
                current_count += counts[child_idx - n_samples]
        counts[i] = current_count

    linkage_matrix = np.column_stack([model.children_, model.distances_,
                                      counts]).astype(float)

    # Plot the corresponding dendrogram
    dendrogram(linkage_matrix, **kwargs)


iris = load_iris()
X = iris.data

# setting distance_threshold=0 ensures we compute the full tree.
model = AgglomerativeClustering(distance_threshold=0, n_clusters=None)

model = model.fit(X)
plt.title('Hierarchical Clustering Dendrogram')
# plot the top three levels of the dendrogram
plot_dendrogram(model, truncate_mode='level', p=3)
plt.xlabel("Number of points in node (or index of point if no parenthesis).")
plt.show()

Демо

Преимущества

• Количество кластеров указывать не обязательно.
• Подобно k-средним, алгоритмы иерархической кластеризации легко реализовать.
• Он может выводить иерархическую структуру дерева кластеров (дендрограмму), которая может помочь в определении количества кластеров.

Недостатки

• Главный недостаток иерархической кластеризации - ее временная сложность. По сравнению с другими алгоритмами, он имеет относительно более высокую сложность O (n² logn), где n - количество точек данных.
• Нет никакого обратного отслеживания, что означает, что после создания одного кластера точки данных членства не могут быть перемещены.
• В зависимости от выбора матрицы расстояний она может быть чувствительной к шумам и выбросам. Кроме того, он может столкнуться с трудностями при работе с кластерами разного размера и выпуклой формы.

использованная литература