无监督学习与聚类
定义
无监督学习(unsupervised learning)指只给定样本集 、不给定标签,要求估计其生成分布或发现其中结构的学习范式;聚类(clustering)是在给定样本间距离或相似度的前提下,把样本划分为若干互不相交的子集,使同一子集内样本彼此接近、不同子集间样本彼此远离的过程。
- :样本矩阵, 为样本数, 为特征维数。
- :簇的数量,需预先给定(DBSCAN 除外)。
- :第 个簇的样本下标集合, 为其样本数。
- :第 个簇的中心(码字)。
- :硬指派指示变量, 表示 属于簇 ,且 。
- :K-Means 的目标函数(簇内平方和,也称失真度)。
- :高斯混合模型中第 个分量的混合权重,。
- :第 个高斯分量的均值与协方差矩阵。
- :样本 的隐变量,表示其来源分量。
- :责任度(responsibility),即样本 由分量 生成的后验概率。
- 、:DBSCAN 的邻域半径与核心点的最小邻居数。
- :样本 的轮廓系数;、:聚类结果与真实划分之间的一致性指标。
为什么重要
- 解决的问题:真实数据中带标签样本稀少,而无标签数据可以大量获得;聚类在没有标签的条件下给出分组、压缩码本与数据结构假设,是探索性分析的第一步。
- 没有它会怎样:无法在无标签条件下评估样本间的结构相似性;K-Means 与 GMM 还是 EM 算法、向量量化与混合模型的原型,缺失它们会使后续的概率建模与表示学习失去基础。
- 与监督学习的差别:监督学习的目标由标签给出,评估指标与目标函数一致;聚类没有唯一正确答案,目标函数的选择(簇内平方和、似然、密度连通)直接决定了划分的形状,因此「算法 + 评估」必须成对讨论。
- 在全书中的位置:前置为 PCA与降维 的降维与方差分析、概率与统计 的极大似然;本篇的 K-Means 与 GMM 是 异常检测 中基于距离与密度方法的直接基础;聚类结果的稳定性检验纳入 模型评估与交叉验证 的思路。
- 对应能力目标:懂原理要求能证明 Lloyd 算法的单调下降、完成 GMM 的 EM 推导;能复现要求能用 NumPy 实现 K-Means 与 EM;会评估要求能区分内部指标与外部指标,并解释二者结论冲突的原因。
原理与推导
flowchart TD
I["初始化:中心或混合参数"] --> E["E 步:计算指派或责任度"]
E --> M["M 步:更新中心或参数"]
M --> C{"目标函数是否不再变化"}
C -->|"否"| E
C -->|"是"| O["输出划分或后验概率"]
1. 无监督问题的设定
设 独立同分布于未知分布 。无监督学习的三类典型目标:
- 密度估计:构造 近似 ,用于采样、异常评分与似然比较。
- 降维:寻找低维表示 ,保留主要变异,见 PCA与降维。
- 聚类:把样本划分为 个组,使组内差异小、组间差异大。
聚类没有唯一的数学定义,必须先固定准则。常见的三种准则对应不同的簇形状假设:
| 准则 | 目标函数 | 隐含的簇形状 |
|---|---|---|
| 簇内平方和 | 各向同性、尺寸相近的凸簇 | |
| 混合模型似然 | 椭圆、可重叠的凸簇 | |
| 密度连通 | 邻域内样本数不低于阈值 | 任意形状、可含噪声 |
选择准则即选择归纳偏置。准则与数据结构不匹配时,算法仍会返回划分,但该划分不再具有解释力。
混合模型还存在可辨识性问题:交换两个分量的编号不改变似然,因此参数估计只能确定到置换意义下;聚类结果同样只能确定到簇编号的置换。评估指标必须对置换不变,这是 ARI 与 NMI 的设计前提。
2. K-Means 的目标函数与 Lloyd 算法
K-Means 求解
变量分两组:指派 与中心 。Lloyd 算法交替固定一组、优化另一组。
指派步:固定中心,每个样本独立选择最近中心,
更新步:固定指派,目标对 可分离。对第 个簇,
即中心是该簇样本的算术平均。若某簇为空,需重新指定中心或删除该簇,否则更新式分母为零。
单调下降的证明思路。记第 次迭代后的目标值为 。指派步在中心固定时对每个样本取最优,故 不增;更新步在指派固定时对每个中心取最优,故 不增。两步交替得到
有下界 ;划分的总数是有限的(至多 种),若算法不停机则必有两次迭代落在同一划分上,而确定性算法在同一划分上产生相同的中心与目标值,于是循环重复。因此算法在有限步内停在某个划分上,该划分满足「指派不再变化」,即目标函数的坐标下降不动点。
该不动点只是局部最优。-Means 的全局最优求解是 NP 难的,实践中用多次随机初始化取最优目标值来近似。
单次迭代复杂度为 :计算 个距离,每个距离 ; 次迭代为 。中心初始化与空簇处理是主要的实现差异来源。
一个常用的等价形式把目标写成簇内两两距离:
它说明簇内平方和只依赖簇内样本的两两距离,因此在核空间中把距离替换为 即可得到核 K-Means。
3. 初始化:k-means++
随机选取 个样本作为初始中心时,若两个初始中心落在同一个真实簇内,该簇会被永久拆分,算法只能收敛到较差的局部最优。k-means++ 按距离加权采样,使初始中心尽量分散:
- 以均匀分布选取第一个中心。
- 对每个样本计算 ,即以已选中心为参照的最近距离。
- 以正比于 的概率选取下一个中心,重复直到选满 个。
平方使远离已有中心的样本被显著放大。该策略的期望近似比为 ,即期望目标值不超过最优值的 倍。实践中仍会运行多次(n_init),取目标值最小的一次,因为近似比只是期望意义下的界。
4. 簇数 K 的选择
随 单调不增, 时 ,因此不能直接最小化 。常用两种启发式。
肘部法:绘制 曲线,选择下降速率明显变缓的拐点。拐点没有严格定义,曲线平滑时判断困难。
轮廓系数:对样本 ,记 为其到同簇其他样本的平均距离, 为其到其他各簇平均距离的最小值,定义
整体轮廓系数为 。 接近 表示样本与同簇更近、与最近的其他簇更远;接近 表示位于两簇边界;为负表示可能被分错。簇大小为 时约定 。
两种方法的适用条件不同:肘部法只反映簇内紧致度,轮廓系数同时考虑簇间分离度,但对非凸簇与密度差异大的数据会给出误导性结果。后文代码中,双月数据上 DBSCAN 的 ARI 达到 ,轮廓系数却只有 ,说明内部指标不能替代外部验证。
5. GMM:混合模型与隐变量
高斯混合模型假设样本由 个高斯分量按权重混合生成:
参数为 。对数似然为
对数内部有求和,直接求导会得到耦合方程,没有闭式解。引入隐变量 表示样本来源分量,完全数据似然为 ,但 不可观测。
下界构造。对每个样本引入任意分布 ,由 Jensen 不等式,
对 求和得到证据下界(ELBO):
不等式取等的条件是 与 无关,即 正比于该乘积。这也给出 的最优形式。
E 步:固定 ,取 为后验,得到责任度
满足 ,可解释为样本 由各分量生成的概率。
M 步:固定 ,对 最大化 ELBO。记 为第 个分量的有效样本数。
对 求导:
对 求导。利用 与 ,令导数为零:
左右乘 得
对 求导需处理约束 ,引入乘子 :
由 得 ,故
单调性。记 为第 轮参数。E 步取 为后验,此时 KL 散度为零,有
M 步最大化下界,故 。又由 Jensen 不等式 。合并得
即每一轮对数似然不降。EM 收敛到驻点,可能是局部极大或鞍点,不保证全局最优。
退化与正则化。若某个分量的协方差退化、均值收敛到单个样本,该样本处的密度趋于无穷,似然无上界。实现中通过对角加载 、限制协方差类型(对角、共享、球面)或设置最小簇样本数来避免。
6. GMM 与 K-Means 的关系
取各分量协方差相同且为各向同性 、权重相同 ,则责任度为
当 时,最近中心对应的指数项占主导,,其余趋于 ,责任度退化为硬指派;此时 M 步的加权均值退化为簇内算术平均,正是 Lloyd 的更新步。因此 K-Means 是「各向同性、等权重、方差趋于零」的 GMM 的极限情形。
两者的差别来自三处:GMM 允许各分量有不同协方差,因而能表达椭圆簇与不同尺寸的簇;GMM 给出软指派,样本可以同时以不同概率属于多个分量;GMM 优化似然而非簇内平方和,对离群点的惩罚是对数尺度而非平方尺度。
7. DBSCAN
DBSCAN 基于密度连通性定义簇,不需要预先给定 。
- -邻域:。
- 核心点:。
- 边界点:非核心点,但落在某个核心点的 -邻域内。
- 噪声点:既非核心点也不在任何核心点邻域内的点。
- 直接密度可达: 且 为核心点,称 从 直接密度可达。
- 密度可达:存在点列 ,使 从 直接密度可达。
- 密度连通:存在点 ,使 与 都从 密度可达。
簇定义为密度连通关系下的极大集合。算法流程:
对每个未访问样本 p:
标记 p 已访问
若 |N_eps(p)| < minPts:暂标记为噪声
否则:
新建簇 C,把 p 加入 C,队列 Q = N_eps(p)
当 Q 非空:
取出 q
若 q 未访问:
标记 q 已访问
若 |N_eps(q)| >= minPts:把 N_eps(q) 并入 Q
若 q 尚未属于任何簇:把 q 加入 C
复杂度取决于邻域查询:使用 KD 树或球树时为 ,无索引时为 。 过小会使大量样本成为噪声、簇被拆碎; 过大则不同簇被合并。常用 -距离图选择参数:对每个点计算到第 近邻的距离并排序,拐点处取 。
优点:能发现任意形状的簇、显式标记噪声、不需要 。缺点:对密度差异大的数据无统一参数;高维下距离集中使 难以选择;边界点可能同时邻近两个簇,结果依赖处理顺序。
8. 层次聚类与连接准则
凝聚式层次聚类从每个样本自成一簇开始,每步合并距离最近的两个簇,得到一棵树(树状图),在所需高度切割即得划分。
簇间距离的定义决定结果:
| 连接准则 | 定义 | 性质 |
|---|---|---|
| 单连接 | 能发现长条形簇,易发生链式效应 | |
| 全连接 | 倾向紧凑的等直径簇,对离群点敏感 | |
| 平均连接 | 折中,计算量较大 | |
| Ward | 最小化合并带来的簇内平方和增量,要求欧氏距离 |
Ward 的增量公式:合并前两簇的簇内平方和之和为 ,合并后为 ,二者之差恰为 。因此每步按该增量最小者合并,等价于最小化整体簇内平方和的增长。
合并后新簇与其他簇的距离可用 Lance-Williams 公式递推,无需重算全部两两距离。以平均连接为例, 与 合并为 后
朴素实现每次合并后重算距离矩阵,总代价 ;使用优先队列与 Lance-Williams 递推可降至 ,但距离矩阵需要 内存,因此不适合 超过 的数据。
连接准则与 K-Means 的差别在于:层次聚类不假设簇为凸集,且一次运行给出整棵合并树,可通过切割高度控制簇数。代价是无法回溯,早期错误合并不会撤销。
9. 聚类评估
内部指标只使用样本与划分,不使用真实标签。
轮廓系数已在第 4 节定义。另有簇内平方和、Calinski-Harabasz 指数(簇间平方和与簇内平方和之比)与 Davies-Bouldin 指数(各簇到最相似簇的散度平均值)。
外部指标使用真实划分 与预测划分 计算一致性。设列联表 ,,。
调整兰德指数(Adjusted Rand Index, ARI)先定义兰德指数
再用随机划分的期望做校正:
表示划分完全一致, 表示与随机划分的期望相当,负值表示比随机更差。
归一化互信息(Normalized Mutual Information, NMI)先计算互信息
再除以两划分熵的均值(scikit-learn 默认使用算术平均):
NMI 对簇数不惩罚,簇数增加时倾向于上升;ARI 有随机划分的期望校正,更常用于比较不同簇数的结果。
两种指标的用途不同:内部指标用于没有标签时的模型选择,但它编码了几何假设,对非凸簇会失效;外部指标用于有标签的基准数据,反映划分与真实类别的吻合程度,不反映该划分在下游任务中的价值。
关键直觉
机制性直觉
K-Means 是交替优化指派与中心的坐标下降:固定中心时样本独立取最近中心,固定指派时中心取簇内均值,两步都使目标不增,因此收敛到坐标下降的不动点。GMM 的 EM 是同一结构在概率模型上的版本:E 步用责任度代替硬指派,M 步用加权矩估计代替算术平均,每一步都提高对数似然的下界。当协方差趋于零时责任度退化为指示函数,GMM 退化为 K-Means,这一极限关系把两种算法的定义与推导连接起来。
例子与代码
手算:6 个样本的 K-Means 两轮迭代
取 、、、、、,,初始中心 、。
| 轮次 | 指派 / | 更新后中心 | 目标函数 |
|---|---|---|---|
| 初始指派 | / | — | |
| 第 1 次更新 | 同上 | / | |
| 第 2 次指派 | / | — | |
| 第 2 次更新 | 同上 | / |
第 2 次更新后再执行指派: 到 的距离平方为 ,到 为 ,仍归入 ;其余样本的归属不变。指派不再变化,算法停止,。
过程中 从 降到 ,再降到 ,最后降到 ,每次下降都由指派步或更新步之一完成,验证了第 2 节的单调性。 在第 2 次指派中由 转入 ,说明更新后的中心会改变样本归属。
代码一:NumPy 实现 K-Means 与 k-means++
# 依赖:Python 3.12、NumPy 2.3.5、scikit-learn 1.9.1
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score, adjusted_rand_score
def kmeans_pp(X, k, rng):
centers = [X[rng.integers(len(X))]]
for _ in range(1, k):
# 到最近已选中心的距离平方,作为采样权重
d2 = np.min(((X[:, None, :] - np.array(centers)[None]) ** 2).sum(-1), axis=1)
centers.append(X[rng.choice(len(X), p=d2 / d2.sum())])
return np.array(centers)
def lloyd(X, C, max_iter=100):
history = []
for _ in range(max_iter):
d2 = ((X[:, None, :] - C[None]) ** 2).sum(-1)
r = d2.argmin(1) # 指派步
history.append(float(((X - C[r]) ** 2).sum()))
C_new = np.array([X[r == j].mean(0) if np.any(r == j) else C[j] for j in range(len(C))])
if np.allclose(C_new, C): # 中心不变即到达不动点
break
C = C_new # 更新步
return C, r, history
X, y = make_blobs(n_samples=300, centers=3, cluster_std=0.9, random_state=1)
C0 = kmeans_pp(X, 3, np.random.default_rng(0))
C, r, history = lloyd(X, C0)
print("每轮目标函数值:", [round(v, 4) for v in history])
print("最终中心:\n", np.round(C, 2))
print("轮廓系数:", round(float(silhouette_score(X, r)), 4),
" ARI:", round(float(adjusted_rand_score(y, r)), 4))
预期输出:
每轮目标函数值: [1387.0199, 500.1221, 466.8247]
最终中心:
[[ -7.03 -8.03]
[ -1.47 4.41]
[-10.06 -3.91]]
轮廓系数: 0.748 ARI: 0.99
解读:
- 目标函数值单调下降并在第 3 次计算后稳定,与第 2 节的单调性结论一致。由于只有 3 个中心与 300 个样本,2 次迭代即到达不动点。
- 轮廓系数 与 ARI 都表明划分与真实簇高度一致,但 ARI 使用了标签,轮廓系数没有;两者同时偏高说明该数据满足 K-Means 的凸簇假设。
- 若删去
kmeans_pp改为随机取 个样本,部分随机种子会使两个初始中心落在同一簇内,最终 明显偏大,这是需要n_init多次重启的原因。 - 若删去空簇保护(
np.any(r == j)分支),当某中心失去全部样本时mean会产生nan,后续距离计算全部失效。
代码二:K-Means、GMM、DBSCAN 的对比
import numpy as np
from sklearn.datasets import make_blobs, make_moons
from sklearn.cluster import KMeans, DBSCAN
from sklearn.mixture import GaussianMixture
from sklearn.metrics import silhouette_score, adjusted_rand_score, normalized_mutual_info_score
def report(name, labels, X, truth):
mask = labels >= 0 # DBSCAN 的噪声点标签为 -1
k = len(set(labels[mask]))
sil = silhouette_score(X[mask], labels[mask]) if k > 1 else float("nan")
print(f"{name:8s} 簇数 {k} 噪声 {int((labels < 0).sum()):3d} 轮廓系数 {sil:.4f} "
f"ARI {adjusted_rand_score(truth, labels):.4f} NMI {normalized_mutual_info_score(truth, labels):.4f}")
X, y = make_blobs(n_samples=300, centers=3, cluster_std=0.9, random_state=1)
report("K-Means", KMeans(3, n_init=10, random_state=0).fit_predict(X), X, y)
report("GMM", GaussianMixture(3, covariance_type="full", random_state=0).fit_predict(X), X, y)
report("DBSCAN", DBSCAN(eps=0.6, min_samples=5).fit_predict(X), X, y)
Xm, ym = make_moons(n_samples=300, noise=0.05, random_state=0)
report("K-Means", KMeans(2, n_init=10, random_state=0).fit_predict(Xm), Xm, ym)
report("GMM", GaussianMixture(2, covariance_type="full", random_state=0).fit_predict(Xm), Xm, ym)
report("DBSCAN", DBSCAN(eps=0.2, min_samples=5).fit_predict(Xm), Xm, ym)
预期输出:
K-Means 簇数 3 噪声 0 轮廓系数 0.7480 ARI 0.9900 NMI 0.9830
GMM 簇数 3 噪声 0 轮廓系数 0.7480 ARI 0.9900 NMI 0.9830
DBSCAN 簇数 3 噪声 26 轮廓系数 0.7736 ARI 0.8552 NMI 0.8233
K-Means 簇数 2 噪声 0 轮廓系数 0.4887 ARI 0.2408 NMI 0.1835
GMM 簇数 2 噪声 0 轮廓系数 0.4692 ARI 0.4697 NMI 0.3738
DBSCAN 簇数 2 噪声 0 轮廓系数 0.3285 ARI 1.0000 NMI 1.0000
解读:
- 三簇高斯数据上 K-Means 与 GMM 给出几乎相同的划分(轮廓 、ARI ),因为三个簇近似各向同性且尺寸接近,GMM 的协方差没有带来额外收益。
- DBSCAN 在该数据上把 26 个点判为噪声,ARI 降到 。 相对于簇的标准差 偏小,簇边缘的稀疏区域无法连成核心点。
- 双月数据上 K-Means 的 ARI 仅 ,GMM 为 ,二者都假设凸簇;DBSCAN 在 时 ARI 为 ,因为密度连通性与数据的真实结构一致。
- DBSCAN 在双月数据上的轮廓系数只有 ,低于 K-Means 的 ,但外部指标完全相反。这说明内部指标衡量的是簇的紧致与分离,不衡量形状是否正确;无标签场景下不能只用轮廓系数判断聚类质量。
代码三:NumPy 实现 GMM 的 EM
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.mixture import GaussianMixture
def log_gauss(X, mu, cov):
# 多元高斯的对数密度;用 slogdet 求 log|Sigma|,避免行列式下溢或上溢
d = X.shape[1]
diff = X - mu
inv = np.linalg.inv(cov)
_, logdet = np.linalg.slogdet(cov)
maha = np.einsum("ni,ij,nj->n", diff, inv, diff)
return -0.5 * (d * np.log(2 * np.pi) + logdet + maha)
def em_gmm(X, K, n_iter=60, seed=3):
n, d = X.shape
rng = np.random.default_rng(seed)
pi = np.full(K, 1.0 / K)
mu = X[rng.choice(n, K, replace=False)]
cov = np.array([np.cov(X.T) + 1e-6 * np.eye(d) for _ in range(K)])
history = []
for _ in range(n_iter):
# E 步:计算责任度
logp = np.column_stack([np.log(pi[k]) + log_gauss(X, mu[k], cov[k]) for k in range(K)])
mx = logp.max(1, keepdims=True)
w = np.exp(logp - mx)
s = w.sum(1, keepdims=True)
gam = w / s
history.append(float(np.mean(mx[:, 0] + np.log(s[:, 0]))))
# M 步:加权矩估计
Nk = gam.sum(0)
pi = Nk / n
mu = (gam.T @ X) / Nk[:, None]
for k in range(K):
diff = X - mu[k]
cov[k] = (gam[:, k][:, None] * diff).T @ diff / Nk[k] + 1e-6 * np.eye(d)
return pi, mu, cov, gam, history
X, _ = make_blobs(n_samples=300, centers=3, cluster_std=0.9, random_state=1)
pi, mu, cov, gam, history = em_gmm(X, 3)
print("前 8 次对数似然:", [round(v, 4) for v in history[:8]])
print("末次对数似然:", round(history[-1], 4))
print("单调不减:", all(history[i + 1] >= history[i] - 1e-12 for i in range(len(history) - 1)))
print("混合权重:", np.round(pi, 4))
print("均值:\n", np.round(mu, 3))
print("平均最大责任度:", round(float(gam.max(1).mean()), 4))
gm = GaussianMixture(3, covariance_type="full", random_state=0).fit(X)
print("sklearn 均值:\n", np.round(gm.means_, 3))
print("sklearn 对数似然:", round(float(gm.lower_bound_), 4), " sklearn 权重:", np.round(gm.weights_, 4))
预期输出:
前 8 次对数似然: [-5.9063, -4.9356, -4.3809, -4.1484, -3.7978, -3.7709, -3.739, -3.7016]
末次对数似然: -3.6682
单调不减: True
混合权重: [0.3355 0.3312 0.3333]
均值:
[[-10.063 -3.901]
[ -7.039 -8.021]
[ -1.474 4.407]]
平均最大责任度: 0.9987
sklearn 均值:
[[ -1.474 4.407]
[-10.062 -3.901]
[ -7.039 -8.021]]
sklearn 对数似然: -3.6682 sklearn 权重: [0.3333 0.3356 0.3311]
解读:
- 对数似然逐轮上升,运行 60 轮后的末次值为 ,与 scikit-learn 的结果一致(分量的排列不同,即第 1 节所述的可辨识性)。
- 平均最大责任度 接近 ,说明该数据的簇高度分离,责任度近似退化为硬指派,GMM 与 K-Means 得到相同划分与第 6 节的极限关系相符。
- 若删去协方差中的 对角加载,某个分量在迭代中可能塌缩到单个样本,协方差奇异,
slogdet返回 ,对数似然发散。 - 若 M 步忘记除以 而直接累加 ,均值会被放大 倍,下一次 E 步的距离全部失效。
易错点
常见错误
- 用簇内平方和 选择 。 随 单调不增, 时为 ,必须配合肘部法、轮廓系数或外部指标使用。
- 认为 Lloyd 算法收敛到全局最优。它只保证目标不增并停在坐标下降的不动点;不同初始化可能给出不同的局部最优,k-means++ 也只提供期望近似比。
- 把责任度与硬指派混用。 是后验概率,样本可以同时以非零概率属于多个分量;用
predict取 argmax 会丢失该信息,评估软聚类时应使用后验或对数似然。- 在非凸簇上使用 K-Means 或 GMM,并用轮廓系数证明结果「更好」。轮廓系数编码了凸、紧致的几何假设;双月数据上 DBSCAN 的 ARI 为 而轮廓系数低于 K-Means,就是反例。
- 混淆 DBSCAN 的核心点与边界点。核心点要求 ;边界点只在核心点邻域内、自身邻居不足,噪声点两者都不是。把边界点当作新的扩展源会错误地合并相邻簇。
- 用 ARI 比较不同 的结果而不说明基线。ARI 已对随机划分做期望校正,但不同 的划分空间大小不同,跨 比较仍需固定评估协议。
关联笔记
- 前置:PCA与降维 —— 高维数据常先降维再聚类,且 PCA 的方差最大化与 K-Means 的簇内平方和最小化共享平方误差的结构。
- 前置:概率与统计 —— GMM 的极大似然、协方差估计与后验概率是 EM 推导的基础。
- 后续:异常检测 —— 基于距离、密度与似然的方法直接复用本篇的 -邻域、责任度与马氏距离。
- 对照:树模型与集成学习 —— 树模型的分裂准则同样以不纯度下降为目标,但使用标签;聚类的不纯度没有标签可依,必须由几何假设替代。
- 应用:Embedding与向量检索 —— 对嵌入做聚类可得到语义分组,聚类中心可作为倒排索引的粗量化码字。
达标检测
- [ ] 写出 K-Means 的目标函数与两步更新公式,说明每一步都不使目标增大,并解释算法为何在有限步内停在坐标下降不动点而非全局最优。
- [ ] 写出 k-means++ 的采样概率,并解释为什么使用距离的平方而不是距离。
- [ ] 从 Jensen 不等式构造 ELBO,完成 GMM 的 E 步责任度与 M 步三个参数更新公式的推导。
- [ ] 证明 EM 每轮对数似然不降,并说明该结论为什么不能推出收敛到全局最优。
- [ ] 说明 K-Means 是 GMM 在何种参数限制与极限下的特例,并写出对应的责任度表达式。
- [ ] 运行代码二,把 DBSCAN 的
eps改为 与 ,记录簇数、噪声数与 ARI,解释参数敏感性。 - [ ] 给定两个划分的列联表,手算 ARI 并判断该值是否优于随机划分。
参考来源
- Hastie, Tibshirani, Friedman, The Elements of Statistical Learning, 2009, 第 14 章 无监督学习 —— 对应本篇 K-Means 的簇内平方和目标、GMM 的 EM 推导与层次聚类的连接准则。
- Stanford CS229 课程讲义(Andrew Ng),EM 算法与高斯混合模型部分 —— 对应本篇 ELBO 的构造、责任度公式与 M 步的闭式解。
- d2l.ai《动手学深度学习》,附录 22.7 最大似然与 22.10 统计 —— 对应本篇对数似然、协方差估计与多元高斯密度的计算细节。
- Hastie, Tibshirani, Friedman, The Elements of Statistical Learning, 2009, 第 8 章 模型推断与平均(EM 算法一节)—— 对应本篇 EM 的单调性与收敛性讨论。