聚类算法

1. 概述

聚类（Clustering）是将数据集划分为若干**簇（Cluster）**的无监督学习任务，使得：

同一簇内的样本相似度高
不同簇之间的样本相似度低

1.1 聚类 vs 分类

方面	聚类	分类
学习方式	无监督	有监督
标签	不需要	需要
目标	发现数据内在结构	预测已知类别
评估方式	内部/外部指标	准确率等

1.2 距离度量

聚类算法中常用的距离度量包括：

距离	公式	适用场景
欧氏距离	$d (x, y) = \sum_{i} (x_{i} - y_{i})^{2}$	连续特征
曼哈顿距离	$d(x, y) = \sum_i	x_i - y_i
余弦相似度	$\frac{x \cdot y}{∥ x ∥∥ y ∥}$	文本向量
马氏距离	$(x - y)^{T} Σ^{- 1} (x - y)$	相关特征

2. K-Means算法

2.1 算法描述

K-Means将数据划分为 $K$ 个簇，目标是最小化簇内平方和（Within-Cluster Sum of Squares, WCSS）：

C_{1}, \dots, C_{K} min k = 1 \sum K x \in C_{k} \sum ∥ x - μ_{k} ∥^{2}

其中 $μ_{k}$ 是簇 $C_{k}$ 的质心（均值）。

2.2 算法流程

输入：数据集 X，聚类数 K
输出：K 个簇

1. 随机选择 K 个样本作为初始质心 μ_1, ..., μ_K
2. 重复直到收敛：
   a. 分配阶段：对于每个样本 x_i，将其分配给最近的质心
      C_k = {x_i : ||x_i - μ_k|| ≤ ||x_i - μ_j||, ∀j ≠ k}
   b. 更新阶段：重新计算每个簇的质心
      μ_k = (1/|C_k|) * Σ_{x ∈ C_k} x
3. 返回簇划分

2.3 算法图示

初始状态:                    迭代1:
   ·   ·                      ● ● ●
      K1   ·                  ● ● ● ●
   ·        · K2      →        ● ● ●
      ·   ·                  ● ● ●
         ·                   K1  K2  K3
   K3    ·   ·
                       
迭代2:                      收敛:
   ● ● ●                      ●●●●●
   ● ● ● ●                   ●●●●●
   ● ● ●                      ●●●●●
   K1  K2  K3                 K1  K2  K3

2.4 K-Means++初始化

K-Means++通过智能初始化改善聚类质量：

1. 随机选择第一个质心 μ_1
2. 对于每个样本 x，计算 D(x) = min_j ||x - μ_j||²
3. 以概率 P(x) = D(x) / Σ D(x) 选择下一个质心
4. 重复直到选择 K 个质心

K-Means++的优势：

质心更分散，减少陷入局部最优的可能
理论上，K-Means++的期望误差是O(log K)倍的OPT

2.5 Mini-Batch K-Means

对于大规模数据集，使用**小批量（Mini-Batch）**进行优化：

from sklearn.cluster import MiniBatchKMeans
import numpy as np
 
# 生成大规模数据
X = np.random.rand(100000, 10)
 
# Mini-Batch K-Means
mbkm = MiniBatchKMeans(n_clusters=100, batch_size=1000, random_state=42)
mbkm.fit(X)

2.6 K值选择

肘部法（Elbow Method）

绘制WCSS随K变化的曲线，选择”肘部”位置：

import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
 
wcss = []
K_range = range(1, 11)
 
for k in K_range:
    kmeans = KMeans(n_clusters=k, random_state=42)
    kmeans.fit(X)
    wcss.append(kmeans.inertia_)
 
plt.plot(K_range, wcss, 'bo-')
plt.xlabel('Number of clusters (K)')
plt.ylabel('WCSS')
plt.title('Elbow Method')
plt.show()

轮廓系数（Silhouette Score）

s = \frac{b - a}{max ( a , b )}

其中 $a$ 是样本与同簇其他样本的平均距离， $b$ 是样本与最近邻簇的平均距离。轮廓系数范围为[-1, 1]，越接近1越好。

from sklearn.metrics import silhouette_score
 
silhouette_scores = []
for k in range(2, 11):
    kmeans = KMeans(n_clusters=k, random_state=42)
    labels = kmeans.fit_predict(X)
    score = silhouette_score(X, labels)
    silhouette_scores.append(score)
 
print(f"Best K: {range(2, 11)[np.argmax(silhouette_scores)]}")

3. 层次聚类

3.1 算法类型

类型	策略	特点
凝聚式（Agglomerative）	自底向上	从N个单点簇开始，逐步合并
分裂式（Divisive）	自顶向下	从1个包含所有点的簇开始，逐步分裂

3.2 簇间距离度量

方法	公式	特点
最近邻（Single Linkage）	$min_{x \in C_{i}, y \in C_{j}} d (x, y)$	容易产生链式效应
最远邻（Complete Linkage）	$max_{x \in C_{i}, y \in C_{j}} d (x, y)$	趋向于形成紧凑簇
平均距离（Average Linkage）	$\frac{1}{	C_i
Ward距离	$\Delta(C_i, C_j) = \frac{	C_i

3.3 算法流程

输入：数据集 X，距离阈值 d
输出：层次聚类树（树状图）

1. 每个样本作为一个初始簇
2. 计算所有簇对之间的距离
3. 合并距离最近的两个簇
4. 更新距离矩阵
5. 重复步骤3-4，直到只剩一个簇或达到阈值

3.4 树状图（Dendrogram）

from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt
 
# 生成数据
from sklearn.datasets import make_blobs
X, _ = make_blobs(n_samples=50, centers=3, random_state=42)
 
# 层次聚类
Z = linkage(X, method='ward')
 
# 绘制树状图
plt.figure(figsize=(10, 6))
dendrogram(Z)
plt.title('Hierarchical Clustering Dendrogram')
plt.xlabel('Sample Index')
plt.ylabel('Distance')
plt.show()

4. DBSCAN

4.1 算法思想

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）基于密度进行聚类，可以发现任意形状的簇，并自动识别噪声点。

4.2 核心概念

$ε$ -邻域：样本 $x$ 的 $ε$ 邻域是距离 $x$ 不超过 $ε$ 的样本集合
核心点（Core Point）：邻域内样本数不少于 MinPts 的点
边界点（Border Point）：在某个核心点的邻域内，但自身不是核心点
噪声点（Noise Point）：既不是核心点也不是边界点

        ●                    ●
    ●   ●                ●   ●
        ●       →           ●  ← 核心点 (MinPts=4)
    ●   ●                ●   ●
    ●       ●           ●       ← 边界点
                        ○  ← 噪声点

4.3 算法流程

输入：数据集 X，邻域半径 ε，密度阈值 MinPts
输出：簇标签

1. 将所有点标记为未访问
2. 随机选择一个未访问点 p
3. 标记 p 为已访问
4. 如果 p 的 ε-邻域至少有 MinPts 个点：
   a. 创建一个新簇 C，将 p 加入 C
   b. 创建一个种子集合 N，包含 p 的 ε-邻域中的所有点
   c. 对 N 中的每个点 q：
      - 如果 q 未被访问，标记为已访问
      - 如果 q 的 ε-邻域至少有 MinPts 个点，将这些点加入 N
      - 如果 q 不属于任何簇，将 q 加入簇 C
5. 否则，标记 p 为噪声点
6. 重复直到所有点都被访问

4.4 参数选择

$ε$ 的选择

使用K-距离图：计算每个点到第k个最近邻的距离，绘制排序后的距离图，选择”肘部”对应的距离。

from sklearn.neighbors import NearestNeighbors
import numpy as np
 
X = np.random.rand(500, 2)
 
# 计算k-距离
k = 5
nbrs = NearestNeighbors(n_neighbors=k).fit(X)
distances, indices = nbrs.kneighbors(X)
 
# 排序并绘图
k_distances = np.sort(distances[:, k-1])
plt.plot(k_distances)
plt.xlabel('Points sorted by distance')
plt.ylabel(f'{k}-th Nearest Neighbor Distance')
plt.show()

MinPts 的选择

数据集维度 d：通常取 $M in Pt s \geq d + 1$
经验法则： $M in Pt s = 2 \times d$
或者使用领域知识确定

4.5 DBSCAN的优缺点

优点	缺点
可以发现任意形状的簇	对参数敏感
可以识别噪声点	在密度不均匀的数据集上效果差
不需要指定簇数	高维数据上距离度量可能失效
对异常值鲁棒	计算复杂度较高

5. 谱聚类

5.1 算法思想

谱聚类（Spectral Clustering）使用数据的图表示，通过拉普拉斯矩阵的特征向量进行降维，然后使用K-Means进行聚类。

5.2 相似图构建

ε-邻域图：连接距离小于ε的点
K近邻图：只连接每个点的K个最近邻
全连接图：使用高斯核 $W_{ij} = exp (- ∥ x_{i} - x_{j} ∥^{2} / (2 σ^{2}))$

5.3 拉普拉斯矩阵

非归一化拉普拉斯矩阵： $L = D - W$
归一化拉普拉斯矩阵： $L_{sy m} = D^{- 1/2} L D^{- 1/2} = I - D^{- 1/2} W D^{- 1/2}$

其中 $D$ 是度矩阵， $W$ 是相似度矩阵。

5.4 算法流程

输入：数据集 X，聚类数 K
输出：K 个簇

1. 构建相似度矩阵 W
2. 计算度矩阵 D 和拉普拉斯矩阵 L
3. 计算 L 的前 K 个最小特征值对应的特征向量
4. 将特征向量组成矩阵 U (N × K)
5. 对 U 的行进行归一化得到 Z
6. 使用 K-Means 对 Z 进行聚类

5.5 代码实现

import numpy as np
from sklearn.cluster import KMeans
 
def spectral_clustering(X, n_clusters, sigma=1.0):
    # 构建相似度矩阵
    n = X.shape[0]
    W = np.zeros((n, n))
    for i in range(n):
        diff = X - X[i]
        W[i] = np.exp(-np.sum(diff**2, axis=1) / (2 * sigma**2))
    
    # 度矩阵
    D = np.diag(W.sum(axis=1))
    
    # 归一化拉普拉斯矩阵
    D_inv_sqrt = np.diag(1.0 / np.sqrt(np.diag(D)))
    L = np.eye(n) - D_inv_sqrt @ W @ D_inv_sqrt
    
    # 特征向量
    eigvals, eigvecs = np.linalg.eigh(L)
    U = eigvecs[:, :n_clusters]
    
    # 归一化
    Z = U / np.linalg.norm(U, axis=1, keepdims=True)
    
    # K-Means聚类
    kmeans = KMeans(n_clusters=n_clusters, random_state=42)
    return kmeans.fit_predict(Z)

6. 高斯混合模型（GMM）

6.1 模型定义

高斯混合模型假设数据由 $K$ 个高斯分布混合而成：

p (x) = k = 1 \sum K π_{k} N (x ∣ μ_{k}, Σ_{k})

其中 $π_{k}$ 是混合系数， $N$ 是高斯分布。

6.2 EM算法求解

E步：计算每个样本属于各簇的后验概率：

γ_{ik} = \frac{π _{k} N ( x _{i} ∣ μ _{k} , Σ _{k} )}{\sum _{j} π _{j} N ( x _{i} ∣ μ _{j} , Σ _{j} )}

M步：更新参数：

μ_{k} = \frac{\sum _{i} γ _{ik} x _{i}}{\sum _{i} γ _{ik}}, Σ_{k} = \frac{\sum _{i} γ _{ik} ( x _{i} - μ _{k} ) ( x _{i} - μ _{k} ) ^{T}}{\sum _{i} γ _{ik}}, π_{k} = \frac{\sum _{i} γ _{ik}}{N}

6.3 代码实现

from sklearn.mixture import GaussianMixture
import numpy as np
 
# 生成数据
from sklearn.datasets import make_blobs
X, _ = make_blobs(n_samples=500, centers=3, random_state=42)
 
# GMM聚类
gmm = GaussianMixture(n_components=3, covariance_type='full', random_state=42)
labels = gmm.fit_predict(X)
 
# 预测概率
probs = gmm.predict_proba(X)
print(f"Cluster probabilities for first sample: {probs[0]}")

7. 聚类评估指标

7.1 内部指标

指标	定义	范围	方向
轮廓系数	$\frac{b - a}{m a x ( a , b )}$	[-1, 1]	越大越好
CH指数	$\frac{BSS / ( K - 1 )}{W SS / ( N - K )}$	[0, +∞)	越大越好
DB指数	$\frac{1}{K} \sum_{i} max_{j} \frac{S _{i} + S _{j}}{d ( c _{i} , c _{j} )}$	[0, +∞)	越小越好

其中 $BSS$ 是簇间平方和， $W SS$ 是簇内平方和。

7.2 外部指标（当有真实标签时）

指标	说明
调整兰德指数 (ARI)	范围[-1,1]，1表示完美匹配
归一化互信息 (NMI)	范围[0,1]，1表示完美匹配
Fowlkes-Mallows Index	精确率和召回率的几何平均

from sklearn.metrics import adjusted_rand_score, normalized_mutual_info_score
 
# 真实标签
y_true = np.array([0, 0, 1, 1, 2, 2])
 
# 聚类结果
y_pred = np.array([0, 0, 1, 1, 2, 1])
 
print(f"ARI: {adjusted_rand_score(y_true, y_pred):.4f}")
print(f"NMI: {normalized_mutual_info_score(y_true, y_pred):.4f}")

8. 算法选择指南

数据特点	推荐算法
大规模数据	Mini-Batch K-Means
簇大小不均	DBSCAN, 谱聚类
任意形状簇	DBSCAN, 谱聚类, GMM
高维数据	HDBSCAN, 谱聚类
只需少量超参数	K-Means++
需要层次结构	层次聚类
概率簇成员	GMM

Metaphor

探索