周志华《Machine Learning》学习笔记--第九章--聚类

机器学习聚类技术深度剖析：从基础原理到经典算法实现

1 什么是聚类？——给数据找朋友的艺术

想象你走进一家超市，货架上的牛奶、面包、蔬菜会被分门别类摆放；图书馆里的书籍会按照文学、科技、历史分区收纳。这种将相似事物自动归为一类的过程，在机器学习中就叫做聚类。

聚类是典型的无监督学习任务，和我们熟悉的分类有本质区别：

• 分类：老师提前告诉你"这是猫、那是狗"，模型学习后给新样本打标签（有监督）
• 聚类：没人告诉你答案，模型自己把"长得像、脾气相投"的样本凑成一堆（无监督）

聚类的核心目标可以用一句话概括：簇内相似度尽可能高，簇间相似度尽可能低。每一堆相似的样本叫做一个"簇"（cluster）。

1.1 聚类的应用场景

• 用户分群：电商平台将用户分为"价格敏感型"“品质追求型”“冲动消费型”，实现精准推荐
• 图像分割：将图像中的前景和背景、不同物体分割开
• 异常检测：从交易数据中找出和正常行为差异极大的欺诈交易
• 文本聚类：将海量新闻自动分为"科技"“体育”"娱乐"等主题

2 聚类好不好？——性能度量的两把尺子

怎么判断一个聚类算法的效果？我们有两把尺子：外部指标（和标准答案比）和内部指标（自己和自己比）。

2.1 外部指标：老师给你打分

如果我们有样本的真实类别标签（参考模型），就可以用外部指标衡量聚类结果和标准答案的匹配程度。假设聚类结果给出的簇划分为$C$，参考模型给出的簇划分为$C^{\ast }$，我们定义四个统计量：

• $a$：在$C$和$C^{\ast }$中都属于同一簇的样本对数量
• $b$：在$C$中属于同一簇但在$C^{\ast }$中不属于的样本对数量
• $c$：在$C^{\ast }$中属于同一簇但在$C$中不属于的样本对数量
• $d$：在$C$和$C^{\ast }$中都不属于同一簇的样本对数量

显然$a+b+c+d=m(m-1)/2$（$m$是样本总数）。常用的外部指标有三个：

Jaccard系数

$$J=\frac{a}{a+b+c}$$
衡量两个集合的交集占并集的比例，取值范围$[0,1]$，越大说明聚类效果越好。

FM指数

$$FMI=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}}$$
综合了精确率和召回率，同样越大越好。

Rand指数

$$RI=\frac{a+d}{a+b+c+d}$$
衡量所有样本对中被正确划分的比例，取值范围$[0,1]$。

2.2 内部指标：自我评估

如果没有真实标签，我们只能从聚类本身的特性评估：簇内越紧凑越好，簇间越远越好。

DBI指数（Davies-Bouldin Index）

$$DBI=\frac{1}{k}\sum _{i=1}^k\underset{j\ne i}{\max }\left(\frac{avg(C_i)+avg(C_j)}{d_{cen}({\mu }_i,{\mu }_j)}\right)$$

• $k$：簇的个数
• $avg(C_i)$：簇$C_i$内所有样本到簇中心${\mu }_i$的平均距离
• $d_{cen}({\mu }_i,{\mu }_j)$：簇$C_i$和$C_j$的中心之间的距离

DBI越小，说明簇内越紧凑、簇间越分离，聚类效果越好。

Dunn指数

$$DI=\underset{1\le i\le k}{\min }\left\{\underset{j\ne i}{\min }\left(\frac{d_{min}(C_i,C_j)}{{\max }_{1\le l\le k}diam(C_l)}\right)\right\}$$

• $d_{min}(C_i,C_j)$：簇$C_i$和$C_j$之间最近样本的距离
• $diam(C_l)$：簇$C_l$内最远两个样本的距离（簇的直径）

DI越大，说明簇间距离越大、簇内直径越小，效果越好。

3 怎么算"长得像"？——距离计算的学问

聚类的核心是"相似性"，而相似性最常用的量化方式就是距离。两个样本距离越近，相似度越高。

3.1 连续属性的距离：闵可夫斯基家族

对于两个$n$维样本$x_i=(x_{i1},x_{i2},\dots ,x_{in})$和$x_j=(x_{j1},x_{j2},\dots ,x_{jn})$，闵可夫斯基距离是最通用的距离定义：
$$dis{t}_{mk}(x_i,x_j)={\left(\sum _{u=1}^n|x_{iu}-x_{ju}{|}^p\right)}^{1/p}$$

• $p$：距离的阶数，取不同值对应不同的距离
  • $p=1$：曼哈顿距离（城市距离），相当于在网格中从一点走到另一点的最短路径
  • $p=2$：欧氏距离，我们最熟悉的直线距离
  • $p\to \infty$：切比雪夫距离，两个样本在所有属性上的最大差值

3.2 离散属性的距离：VDM距离

闵可夫斯基距离只适用于有序属性（比如身高、体重、密度），对于无序属性（比如颜色、品种、产地）不能直接使用。比如"红色=1，绿色=2，蓝色=3"，不能说"红色和蓝色的距离是2"。

此时我们使用VDM距离（Value Difference Metric），它通过属性取值在各个簇中的分布差异来计算距离：
VDMp(u,v)=∑i=1k∣mu,a,imu,a−mv,a,imv,a∣pVDM_p(u,v) = \\sum_{i=1}^k \\left| \\frac{m_{u,a,i}}{m_{u,a}} – \\frac{m_{v,a,i}}{m_{v,a}} \\right|^pVDMp​(u,v)=i=1∑k​​mu,a​mu,a,i​​−mv,a​mv,a,i​​​p

• $u,v$：离散属性$a$的两个取值
• $m_{u,a}$：数据集中属性$a$取值为$u$的样本总数
• $m_{u,a,i}$：簇$C_i$中属性$a$取值为$u$的样本数
• $p$：和闵可夫斯基距离的阶数一致

3.3 距离度量的基本性质

一个合法的距离度量必须满足四个条件：

4 原型聚类：找个代表当组长

原型聚类是最经典的聚类算法，核心思想是：每个簇用一个"原型"（代表点）来表示，样本被分配到距离最近的原型所在的簇。

4.1 k均值算法（k-means）：最流行的聚类算法

k均值算法简单高效，是工业界最常用的聚类算法，没有之一。

算法流程

簇中心的更新公式：
$${\mu }_i=\frac{1}{|C_i|}\sum _{x\in C_i}x$$

• ${\mu }_i$：第$i$个簇的中心
• $|C_i|$：第$i$个簇的样本数量
• $x$：簇$C_i$中的样本

西瓜数据集实战

我们用周志华老师《机器学习》中的西瓜数据集4.0（30个西瓜的密度和含糖率数据）来演示k均值的迭代过程。

图1 西瓜数据集4.0上k均值算法(k=3)第1轮迭代结果

第1轮随机选取3个样本作为初始中心，根据欧氏距离将所有样本分配到最近的簇。此时簇的划分还比较混乱，中心位置也不准确。

图2 西瓜数据集4.0上k均值算法(k=3)第2轮迭代结果

第2轮更新簇中心后，重新分配样本，簇的划分开始变得清晰。

图3 西瓜数据集4.0上k均值算法(k=3)第3轮迭代结果

第3轮继续更新中心和分配样本，簇的划分基本稳定。

图4 西瓜数据集4.0上k均值算法(k=3)第4轮迭代结果

第4轮后簇中心不再变化，算法收敛。最终得到3个簇，分别对应"好瓜"“中等瓜”“差瓜”。

优缺点

• ✅ 优点：简单易实现、时间复杂度低（$O(tknm)$，$t$为迭代轮数）、适合大规模数据
• ❌ 缺点：对初始中心敏感（不同初始中心可能得到不同结果）、只能处理球状簇、对噪声和离群点敏感、需要预先指定$k$值

4.2 学习向量量化（LVQ）：带标签的原型聚类

LVQ是一种半监督的原型聚类算法，它利用少量有标签样本初始化原型向量，然后通过迭代调整原型来优化聚类结果。

核心思想

原型更新公式：
$$p_i^{\prime }=p_i+\eta (x-p_i)\text{标签相同}$$
$$p_i^{\prime }=p_i-\eta (x-p_i)\text{标签不同}$$

• $\eta$：学习率（0<η<1），控制原型移动的步长

4.3 高斯混合聚类：用概率说话

k均值是"硬聚类"（一个样本只能属于一个簇），而高斯混合聚类是"软聚类"（一个样本可以以不同概率属于多个簇）。

高斯混合模型（GMM）假设数据是由$k$个高斯分布混合生成的，每个高斯分布对应一个簇：
$$p(x)=\sum _{i=1}^k{\alpha }_i\mathcal{N}(x|{\mu }_i,{\Sigma }_i)$$

• ${\alpha }_i$：混合系数，满足${\sum }_{i=1}^k{\alpha }_i=1$，表示第$i$个高斯分布的权重
• $\mathcal{N}(x|{\mu }_i,{\Sigma }_i)$：第$i$个高斯分布，均值为${\mu }_i$，协方差为${\Sigma }_i$

我们使用EM算法来求解模型参数：

样本$x_j$属于第$i$个簇的后验概率：
$${\gamma }_{ji}=\frac{{\alpha }_i\mathcal{N}(x_j|{\mu }_i,{\Sigma }_i)}{{\sum }_{l=1}^k{\alpha }_l\mathcal{N}(x_j|{\mu }_l,{\Sigma }_l)}$$

5 密度聚类：哪里人多哪里凑

k均值只能处理球状簇，对于非球状的簇（比如月牙形、环形）效果很差。密度聚类的核心思想是：只要某个区域的样本密度足够高，就把它划分为一个簇。

5.1 DBSCAN算法：最经典的密度聚类

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是最具代表性的密度聚类算法，它不需要预先指定簇的数量，还能自动检测噪声点。

核心概念

• $ϵ$-邻域：样本$x$周围半径为$ϵ$的区域内的所有样本
• 核心对象：如果一个样本的$ϵ$-邻域内至少包含$min\_samples$个样本，那么它就是核心对象
• 密度直达：如果样本$y$在核心对象$x$的$ϵ$-邻域内，那么$y$从$x$密度直达
• 密度可达：如果存在样本序列$x_1,x_2,\dots ,x_n$，其中$x_{i+1}$从$x_i$密度直达，那么$x_n$从$x_1$密度可达
• 密度相连：如果存在核心对象$z$，使得$x$和$y$都从$z$密度可达，那么$x$和$y$密度相连

通俗来说：核心对象就是"人气王"，周围有很多朋友；密度直达就是"直接认识"；密度可达就是"朋友的朋友"；密度相连就是"有共同的朋友"。所有互相密度相连的样本构成一个簇，没有朋友的孤家寡人就是噪声点。

算法流程

实战效果

DBSCAN可以轻松处理非球状簇，这是k均值做不到的。比如对于月牙形数据，k均值会错误地将其划分为两个球状簇，而DBSCAN能正确识别出两个月牙形簇。

6 层次聚类：从个体到家族的合并

层次聚类的核心思想是：将数据组织成一棵层次化的树，要么从下往上合并（自底向上），要么从上往下分裂（自顶向下）。

6.1 AGNES算法：自底向上合并

AGNES（Agglomerative Nesting）是最经典的自底向上层次聚类算法。

算法流程

簇间距离的计算方式

• 单链接：两个簇中最近样本的距离
• 全链接：两个簇中最远样本的距离
• 均链接：两个簇中所有样本对距离的平均值

不同的距离计算方式会得到不同的聚类结果。单链接容易产生"链式效应"（一个长条形的簇），全链接对离群点敏感，均链接是两者的折中。

图5 西瓜数据集4.0上AGNES算法(k=3)的聚类过程

图5展示了AGNES算法的合并过程，从30个单样本簇开始，不断合并最近的簇，最终得到3个簇。

6.2 DIANA算法：自顶向下分裂

DIANA（Divisive Analysis）是自顶向下的层次聚类算法，流程和AGNES相反：

DIANA的计算复杂度比AGNES更高，实际应用中较少使用。

7 核心代码实现

7.1 手写k均值算法

import numpy as np
import matplotlib.pyplot as plt

def kmeans(X, k, max_iter=100):
"""
手写k均值算法实现
参数：
X: 样本数据，形状为(n_samples, n_features)
k: 簇的个数
max_iter: 最大迭代次数
返回：
labels: 每个样本的簇标签
centers: 簇中心
"""
n_samples, n_features = X.shape
# 随机初始化k个簇中心
centers = X[np.random.choice(n_samples, k, replace=False)]

for _ in range(max_iter):
# 计算每个样本到所有簇中心的欧氏距离
distances = np.sqrt(((X – centers[:, np.newaxis])**2).sum(axis=2))
# 分配样本到最近的簇
labels = np.argmin(distances, axis=0)
# 更新簇中心
new_centers = np.array([X[labels == i].mean(axis=0) for i in range(k)])
# 簇中心不再变化则收敛
if np.all(centers == new_centers):
break
centers = new_centers

return labels, centers

# 西瓜数据集4.0（密度和含糖率）
watermelon = np.array([
[0.697, 0.460], [0.774, 0.376], [0.634, 0.264], [0.608, 0.318], [0.556, 0.215],
[0.403, 0.237], [0.481, 0.149], [0.437, 0.211], [0.666, 0.091], [0.243, 0.267],
[0.245, 0.057], [0.343, 0.099], [0.639, 0.161], [0.657, 0.198], [0.360, 0.370],
[0.593, 0.042], [0.719, 0.103], [0.359, 0.188], [0.339, 0.241], [0.282, 0.257],
[0.748, 0.232], [0.714, 0.346], [0.483, 0.312], [0.478, 0.437], [0.525, 0.369],
[0.751, 0.489], [0.532, 0.472], [0.473, 0.376], [0.725, 0.445], [0.446, 0.459]
])

# 运行k均值聚类
labels, centers = kmeans(watermelon, k=3)

# 可视化聚类结果
plt.figure(figsize=(8,6))
plt.scatter(watermelon[:,0], watermelon[:,1], c=labels, cmap='viridis', s=50)
plt.scatter(centers[:,0], centers[:,1], marker='+', s=200, c='red', label='簇中心')
plt.xlabel('密度')
plt.ylabel('含糖率')
plt.title('西瓜数据集4.0 k均值聚类结果(k=3)')
plt.legend()
plt.show()

7.2 sklearn实现DBSCAN

from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import davies_bouldin_score

# 标准化数据（DBSCAN对距离敏感，需要标准化）
scaler = StandardScaler()
X_scaled = scaler.fit_transform(watermelon)

# DBSCAN聚类
dbscan = DBSCAN(eps=0.3, min_samples=3)
labels_db = dbscan.fit_predict(X_scaled)

# 计算DBI指数评估效果
dbi_db = davies_bouldin_score(watermelon, labels_db)
print(f"DBSCAN的DBI指数：{dbi_db:.2f}")

# 可视化结果
plt.figure(figsize=(8,6))
plt.scatter(watermelon[:,0], watermelon[:,1], c=labels_db, cmap='viridis', s=50)
plt.xlabel('密度')
plt.ylabel('含糖率')
plt.title('西瓜数据集4.0 DBSCAN聚类结果')
plt.show()

7.3 不同k值的性能对比

我们测试k=2、3、4时k均值的DBI指数，选择最优k值：

k_list = [2,3,4]
dbi_scores = []

for k in k_list:
labels, _ = kmeans(watermelon, k)
dbi = davies_bouldin_score(watermelon, labels)
dbi_scores.append(dbi)

# 输出结果表格
print("表1 不同k值下的DBI指数")
print("| k值 | DBI指数 |")
print("|—–|———|")
for k, dbi in zip(k_list, dbi_scores):
print(f"| {k} | {dbi:.2f} |")

输出结果：
表1 不同k值下的DBI指数

从表中可以看出，当k=3时DBI指数最小，说明此时聚类效果最好，这与西瓜数据集4.0本身包含3个真实簇的情况一致。

8 总结与拓展

8.1 各类聚类算法适用场景对比

8.2 聚类的挑战与未来

• 维度灾难：高维数据中距离度量失效，需要先通过PCA等方法降维
• 大规模数据：传统聚类算法无法处理TB级数据，需要分布式聚类（如Spark MLlib中的k均值）
• 任意形状和密度：现有算法对密度差异大的簇处理效果不佳，需要更鲁棒的密度聚类算法
• 可解释性：复杂聚类算法的结果难以解释，需要结合领域知识进行分析

聚类作为无监督学习的核心技术，是探索数据内在结构的有力工具。掌握聚类算法，你就能在没有标签的情况下，从海量数据中发现隐藏的规律和价值。