Агломеративная кластеризация с и без структуры

Этот пример демонстрирует влияние наложения графа связности для захвата локальной структуры в данных. Граф представляет собой просто граф 20 ближайших соседей.

Существует два преимущества наложения связности. Во-первых, кластеризация с разреженными матрицами связности, как правило, быстрее.

Во-вторых, при использовании матрицы связности одиночная, средняя и полная связи неустойчивы и склонны создавать несколько кластеров, которые очень быстро растут. Действительно, средняя и полная связи борются с этим поведением перколяции, учитывая все расстояния между двумя кластерами при их объединении (в то время как одиночная связь усиливает это поведение, учитывая только кратчайшее расстояние между кластерами). Граф связности нарушает этот механизм для средней и полной связи, делая их похожими на более хрупкую одиночную связь. Этот эффект более выражен для очень разреженных графов (попробуйте уменьшить количество соседей в kneighbors_graph) и при полной связи. В частности, наличие очень малого числа соседей в графе накладывает геометрию, близкую к геометрии одиночной связи, которая, как известно, имеет эту неустойчивость перколяции.

# Authors: The scikit-learn developers
# SPDX-License-Identifier: BSD-3-Clause

import time

import matplotlib.pyplot as plt
import numpy as np

from sklearn.cluster import AgglomerativeClustering
from sklearn.neighbors import kneighbors_graph

# Generate sample data
n_samples = 1500
np.random.seed(0)
t = 1.5 * np.pi * (1 + 3 * np.random.rand(1, n_samples))
x = t * np.cos(t)
y = t * np.sin(t)


X = np.concatenate((x, y))
X += 0.7 * np.random.randn(2, n_samples)
X = X.T

# Create a graph capturing local connectivity. Larger number of neighbors
# will give more homogeneous clusters to the cost of computation
# time. A very large number of neighbors gives more evenly distributed
# cluster sizes, but may not impose the local manifold structure of
# the data
knn_graph = kneighbors_graph(X, 30, include_self=False)

for connectivity in (None, knn_graph):
    for n_clusters in (30, 3):
        plt.figure(figsize=(10, 4))
        for index, linkage in enumerate(("average", "complete", "ward", "single")):
            plt.subplot(1, 4, index + 1)
            model = AgglomerativeClustering(
                linkage=linkage, connectivity=connectivity, n_clusters=n_clusters
            )
            t0 = time.time()
            model.fit(X)
            elapsed_time = time.time() - t0
            plt.scatter(X[:, 0], X[:, 1], c=model.labels_, cmap=plt.cm.nipy_spectral)
            plt.title(
                "linkage=%s\n(time %.2fs)" % (linkage, elapsed_time),
                fontdict=dict(verticalalignment="top"),
            )
            plt.axis("equal")
            plt.axis("off")

            plt.subplots_adjust(bottom=0, top=0.83, wspace=0, left=0, right=1)
            plt.suptitle(
                "n_cluster=%i, connectivity=%r"
                % (n_clusters, connectivity is not None),
                size=17,
            )


plt.show()

Общее время выполнения скрипта: (0 минут 1,959 секунды)

Download Jupyter notebook: plot_agglomerative_clustering.ipynb

Download Python source code: plot_agglomerative_clustering.py

Download zipped: plot_agglomerative_clustering.zip

Связанные примеры

Сравнение различных иерархических методов связи на наборах данных-игрушках

Различные агломеративные кластеризации на 2D встраивании цифр

Иерархическая кластеризация: структурированный против неструктурированного Ward

Демонстрация структурированной иерархической кластеризации Ward на изображении монет