常见聚类介绍

常见聚类

这里我们借用一个示例数据集Zachary’s Karate Club来简单介绍常用的聚类。

from sklearn import cluster
import networkx as nx
from collections import defaultdict
import matplotlib.pyplot as plt
from matplotlib import cm
from matplotlib import colors
import seaborn as sns
import pandas as pd
import numpy as np
from sklearn.metrics.cluster import normalized_mutual_info_score
from sklearn.metrics.cluster import adjusted_rand_score

G = nx.karate_club_graph()

pos = nx.spring_layout(G)

一般，在无监督中，我们拿不到真实的标签，不过这个数据集给出了真实的分类结果（两类，如上图所示），我们可以用来比较下不同算法分类的效果。

K-means

K-means是一种常见的聚类算法，它的思想是将数据集分成K个簇，每个簇的中心是该簇内所有点的均值。它通过迭代的方式将数据点分配给最接近的聚类中心，然后更新聚类中心为当前分配给它们的数据点的平均值，直到达到收敛。由于它应用的简单性和高效性，K-means也是最常用的聚类算法之一。一般在进行聚类时，我们首先尝试K-means。K-means的缺点是需要提前设定K值，而且对初始值敏感。此外，其对特征的尺度也比较敏感，需要我们提前处理好特征。

Agglomerative Clustering

Agglomerative Clustering是一种自底向上的层次聚类方法，它通过逐步合并相邻的数据点或聚类来形成层次聚类。其工作原理是：开始时，将每个数据点视为一个单独的聚类，计算所有聚类之间的相似度或距离，将最相似/距离最近的两个聚类合并为一个新的聚类，直到收敛。优点：不需要预先指定聚类数量；可以生成层次结构，提供更多关于数据结构的信息。缺点：对于大型数据集可能计算复杂度较高。

Spectral Clustering

Spectral Clustering一种基于图论的聚类方法，它将数据点视为图上的节点，通过图的谱分解来找到聚类结构。它主要将相似度矩阵转换为拉普拉斯矩阵，然后对拉普拉斯矩阵进行特征分解，选择前K个特征向量，最后使用K-means等方法对特征向量进行聚类。Spectral Clustering对非凸形状的聚类效果较好，对高维数据和图数据也有较好的表现。但是，对参数的选择比较敏感，对大型数据集的计算代价高。

Affinity Propagation

Affinity Propagation是一种基于消息传递的聚类算法，它通过在数据点之间传递消息来识别聚类的样本。其工作原理是：每个数据点通过将消息发送给其他数据点来表示其“吸引力”（即成为代表点的可能性）和“可达性”（即选择其他点作为其代表点的可能性）。在多轮迭代中，数据点将消息传递给其他数据点，并根据传递的消息更新其代表点。优点：不需要指定聚类数量；可以识别数据中的离群点。缺点：对于大型数据集，计算复杂度高。

Mean Shift

Mean shift是一种基于密度估计的聚类算法，它通过在数据点密度最大化的方向上移动数据点来寻找聚类中心。工作原理：对每个数据点，以其为中心计算一个窗口内（核）的密度估计。将每个数据点移动到其密度梯度的方向上，直到收敛到局部密度最大化的位置。合并密度最大化的位置附近的数据点，形成聚类。优点：不需要预先指定聚类数量；对于非球形状的聚类效果较好。缺点：对于数据点的密度估计可能会受到窗口大小参数的影响。

DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 是一种基于密度的聚类算法，它将高密度区域视为聚类，并通过发现低密度区域来检测噪声。工作原理：从数据集中选择一个未访问的核心点，并以最小距离(ε)内的点密度来标记所有可达点。如果一个核心点的ε-邻域内包含足够数量的点，则将其与附近的核心点合并为一个聚类。对于噪声和边界点，它们不会被合并到任何聚类中。优点：可以识别任意形状的聚类；能够处理噪声数据。缺点：对于具有不同密度和尺寸的聚类效果可能不佳；对于高维数据，需要谨慎选择参数。

python实现

这里，由于知道最终是两类，对于需要指定聚类数量的算法，我们指定为2；其他算法我们保持默认参数。

k_clusters = 2
results = []
algorithms = {}

algorithms['kmeans'] = cluster.KMeans(n_clusters=k_clusters, n_init=200, random_state=42)

algorithms['agglom'] = cluster.AgglomerativeClustering(n_clusters=k_clusters, linkage="ward")

algorithms['spectral'] = cluster.SpectralClustering(n_clusters=k_clusters, affinity="precomputed", n_init=200)

algorithms['affinity'] = cluster.AffinityPropagation(damping=0.6)

algorithms['meanshift'] = cluster.MeanShift()

algorithms['dbscan'] = cluster.DBSCAN()

for model in algorithms.values():
    model.fit(edge_mat)
    results.append(list(model.labels_))

对于无监督聚类的评价，我们可以采用silhouette score、normalized mutual information (NMI)、adjusted rand score (ARS)等指标。这里我们采用NMI和ARI。

nmi_results = []
ars_results = []

y_true_val = pd.Series(y_true).values

# Append the results into lists
for y_pred in results:
    nmi_results.append(normalized_mutual_info_score(y_true_val, y_pred))
    ars_results.append(adjusted_rand_score(y_true_val, y_pred))

最后，我们可以将聚类结果可视化。

此外，由于这是个小数据集，我们可找到不同算法在哪些样本上出现了错误聚类，如下图。

代码已经放进了星球里。

Did you find this page helpful? Consider sharing it 🙌