🎲 02-机器学习 · 推导笔记 3:朴素贝叶斯 + K-Means + GMM/DBSCAN(生成式与聚类)¶
朴素贝叶斯是生成式模型的典型(建模联合分布),K-Means 是聚类的入门(EM 的雏形),本篇把它们一路推演到 GMM/EM、DBSCAN 与聚类评估指标。 核心实现全部手写(numpy 数值原语);sklearn 仅用于对照验证(对照 cell 会显式标注)。
💡 一句话类比:K-Means 像班主任按成绩硬性分组,每人只属一组;GMM 是「模糊分组」——每个学生可在各组间按概率"分摊",EM 就是反复修正这个分摊比例的算法(§6 全量推导)。
运行环境:Python 3.8+,仅依赖 numpy(对照 cell 需要 sklearn)。
核心概念¶
(a) 🗂️ 朴素贝叶斯与聚类:生成式模型、K-Means、GMM/EM 与 DBSCAN¶
朴素贝叶斯是生成式模型的典型(建模联合分布),K-Means 是聚类的入门(EM 雏形)。本篇把它们一路推演到 GMM/EM、DBSCAN 与聚类评估指标。
flowchart TB
N1["🎲 判别式 vs 生成式"] --> N2["高斯朴素贝叶斯:MLE 推导"]
N2 --> N3["多项式朴素贝叶斯 + 拉普拉斯平滑"]
N1 --> N4["K-Means:E 步/M 步"]
N4 --> N5["GMM 与 EM 全量推导"]
N5 --> N6["DBSCAN:密度聚类"]
N6 --> N7["层次聚类:凝聚式简述"]
N7 --> N8["聚类评估:纯度/NMI/ARI"]
N8 --> N9["自测清单"]
- N1 · 判别式 vs 生成式:判别式模型直接学 P(y|x)(LR、SVM);生成式模型先学联合分布 P(x,y) 再用贝叶斯推 P(y|x)(朴素贝叶斯)。面试必问两者区别与优缺点。
- N2 · 高斯朴素贝叶斯:假设"特征给定类别后相互独立、且每个类别下特征服从高斯分布",用最大似然估计(MLE)估计各类的均值和方差。
- N3 · 多项式朴素贝叶斯:文本分类按词频建模,加拉普拉斯平滑防止"没见过的词概率为 0"——0 概率会让整个乘积变 0,必须处理。
- N4 · K-Means:随机选 K 个中心 → E 步把每个点分给最近的中心 → M 步把中心移到簇均值,反复迭代到收敛。它其实是最简化的 EM。
- N5 · GMM 与 EM:GMM 是 K-Means 的概率升级:每个点不是硬分给某个簇,而是"软分配"责任值(后验概率);E 步算责任值、M 步带权重做 MLE,全量推导是 P0 高频。
- N6 · DBSCAN:密度聚类:核心点、边界点、噪声点三类点,靠"半径内最少点数"两个超参找簇,不用预先指定 K,能发现任意形状的簇。
- N7 · 层次聚类:凝聚式从每个点一个簇开始,按距离不断合并最近的两个簇,最后画出一棵聚类树(树状图)。
- N8 · 聚类评估:纯度(简单粗暴)、NMI(归一化互信息)、ARI(调整兰德指数,随机情况有基准)——有真实标签时用外部指标。
- N9 · 自测清单:能推高斯 NB 的 MLE、能手写 K-Means、能讲清 EM 的两步、能对比 K-Means/GMM/DBSCAN 的适用场景。
📖 本章导读¶
这一章讲什么(全书第 3 + 10 章):先用生成式视角讲朴素贝叶斯(贝叶斯定理 + 条件独立),再用 EM 视角理解聚类三兄弟(K-Means 硬聚类 / GMM 软聚类 / DBSCAN 密度聚类)。
学完本章,你应该能:
- 推出 $\hat y=\arg\max_y P(y)\prod_j P(x_j|y)$,说清「朴素」假设在哪;
- 解释拉普拉斯平滑为什么必要(没见过的事件 → 概率连乘为 0);
- 讲清 K-Means「分配 → 更新质心」两步迭代与局部最优问题;
- 对比硬聚类(K-Means)与软聚类(GMM),并说清 K-Means 是 EM 的特例。
📌 阅读路径:本章导读 → 贝叶斯半章 → 聚类半章 → 自测清单 → 本章小结。
§1 判别式 vs 生成式(面试基础题)¶
- 判别式:直接建模 $P(y \mid x)$(LR、SVM、决策树)——只关心边界
- 生成式:建模联合分布 $P(x, y) = P(y)P(x \mid y)$,再用贝叶斯定理求后验(NB、GMM、HMM)
贝叶斯定理:
$$P(C_k \mid x) = \frac{P(C_k)P(x \mid C_k)}{P(x)} \propto P(C_k)P(x \mid C_k)$$
朴素假设(条件独立):给定类别,特征之间相互独立:
$$P(x \mid C_k) = \prod_{j=1}^{d} P(x_j \mid C_k)$$
为什么叫「朴素」:现实中特征很少独立(词共现、像素相关),但该假设让参数数量从指数级降到线性:$O(d \cdot K)$ 个参数。
§2 高斯朴素贝叶斯:参数 MLE 推导¶
连续特征假设类别内服从高斯分布:
$$P(x_j \mid C_k) = \frac{1}{\sqrt{2\pi \sigma_{jk}^2}} \exp\left( -\frac{(x_j - \mu_{jk})^2}{2\sigma_{jk}^2} \right)$$
类先验(MLE):
$$P(C_k) = \frac{N_k}{N}$$
条件均值/方差(MLE):
$$\mu_{jk} = \frac{1}{N_k}\sum_{i \in C_k} x_{ij}, \qquad \sigma_{jk}^2 = \frac{1}{N_k}\sum_{i \in C_k} (x_{ij} - \mu_{jk})^2$$
预测:取后验最大(MAP 分类):
$$\hat{y} = \arg\max_k \left( \log P(C_k) + \sum_j \log P(x_j \mid C_k) \right)$$
(对数化防下溢——连乘极小概率会变 0。)
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
import numpy as np
class GaussianNB:
def __init__(self, eps=1e-6):
self.eps = eps
self.prior = None # [K]
self.mu = None # [K, d]
self.var = None # [K, d]
def fit(self, X, y):
K = int(y.max()) + 1
n, d = X.shape
self.prior = np.zeros(K)
self.mu = np.zeros((K, d))
self.var = np.zeros((K, d))
for k in range(K):
Xk = X[y == k]
self.prior[k] = len(Xk) / n # 类先验 MLE
self.mu[k] = Xk.mean(axis=0) # 条件均值 MLE
self.var[k] = Xk.var(axis=0) + self.eps # 条件方差 MLE + 防零
return self
def _log_likelihood(self, X):
# log P(x_j | C_k) = -0.5*log(2*pi*var) - (x-mu)^2/(2*var)
K, d = self.mu.shape
n = len(X)
log_lik = np.zeros((n, K))
for k in range(K):
diff = X - self.mu[k] # [n, d]
log_lik[:, k] = -0.5 * np.sum(
np.log(2 * np.pi * self.var[k]) + diff ** 2 / self.var[k],
axis=1)
return log_lik
def predict(self, X):
log_post = self._log_likelihood(X) + np.log(self.prior) # 加类先验
return log_post.argmax(axis=1)
# 两类高斯数据(与推导笔记 2 同构)
rng = np.random.default_rng(0)
X = np.vstack([rng.normal([1, 1], 0.7, (100, 2)),
rng.normal([-1, -1], 0.7, (100, 2))])
y = np.concatenate([np.zeros(100), np.ones(100)])
nb = GaussianNB().fit(X, y)
pred = nb.predict(X)
acc = np.mean(pred == y)
print('手写高斯NB训练准确率 =', round(acc, 4)) # 期望约 0.98+
print('类先验 =', np.round(nb.prior, 3)) # 期望约 [0.5, 0.5]
print('类0均值 =', np.round(nb.mu[0], 3), ' 类1均值 =', np.round(nb.mu[1], 3))
print('新样本[0,0]预测类别 =', int(nb.predict([[0.0, 0.0]])[0]))
§3 多项式朴素贝叶斯 + 拉普拉斯平滑(文本分类)¶
多项式模型:特征 $x_j$ = 词 $j$ 在文档中的词频计数,条件概率:
$$P(x_j \mid C_k) = \frac{\text{count}(w_j, C_k) + \alpha}{\sum_{v} \text{count}(w_v, C_k) + \alpha V}$$
- $\alpha = 1$ 即拉普拉斯平滑(Laplace smoothing)
- $V$ 为词表大小;分母加 $\alpha V$ 保证概率和为 1
为什么平滑:训练集没出现的词概率为 0 会把整条连乘变 0——平滑给零频词一个小概率。
预测:
$$\hat{y} = \arg\max_k \Big[ \log P(C_k) + \sum_j x_j \log P(w_j \mid C_k) \Big]$$
class MultinomialNB:
def __init__(self, alpha=1.0):
self.alpha = alpha
self.log_prior = None
self.log_cond = None
def fit(self, X, y):
# X: 词频矩阵 [n, V]
K = int(y.max()) + 1
n, V = X.shape
self.log_prior = np.zeros(K)
self.log_cond = np.zeros((K, V))
for k in range(K):
Xk = X[y == k]
self.log_prior[k] = np.log(len(Xk) / n)
cnt = Xk.sum(axis=0) + self.alpha # 平滑计数
self.log_cond[k] = np.log(cnt / cnt.sum()) # 对数条件概率
return self
def predict(self, X):
scores = X @ self.log_cond.T + self.log_prior # 对数后验
return scores.argmax(axis=1)
# 微型文本:3 词词表 ['爱', '猫', '狗']
# 类0=喜欢宠物, 类1=喜欢猫(示例数据)
X = np.array([
[3, 2, 0], # 爱爱爱 猫猫 -> 0
[2, 3, 0], # 爱爱 猫猫猫 -> 0
[4, 0, 1], # 爱爱爱爱 狗 -> 1
[5, 0, 2], # 爱*5 狗狗 -> 1
])
y = np.array([0, 0, 1, 1])
mnb = MultinomialNB(alpha=1).fit(X, y)
print('手写多项式NB预测:', mnb.predict(X)) # 期望 [0 0 1 1]
print('未见词测试[1,1,1](混合词):', int(mnb.predict([[1, 1, 1]])[0]))
print('拉普拉斯平滑保证所有词概率>0(无零概率):', bool((mnb.log_cond > -np.inf).all()))
§4 K-Means:目标函数与 E/M 步¶
目标:把 $n$ 个样本分成 $K$ 簇,最小化簇内平方和(WCSS):
$$\min_{C, \mu} \sum_{k=1}^{K} \sum_{i \in C_k} \|x_i - \mu_k\|^2$$
两步迭代(坐标下降):
- E 步(分配):每个样本归属最近的质心
$$C_k = \{ i : \|x_i - \mu_k\|^2 \le \|x_i - \mu_{k'}\|^2,\ \forall k' \}$$
- M 步(更新):质心 = 簇内均值
$$\mu_k = \frac{1}{|C_k|} \sum_{i \in C_k} x_i$$
收敛性:每步 WCSS 单调不增(分配步减少、更新步也减少),有限次内收敛到局部最优——与全局最优的差距依赖初始化。
k-means++ 初始化:第一个质心随机,后续质心以「距已有质心距离平方」为权重采样——显著提升效果。
def kmeans_pp(X, K, seed=0):
rng = np.random.default_rng(seed)
n = len(X)
centers = [X[rng.integers(n)]]
while len(centers) < K:
d2 = np.min([((X - c) ** 2).sum(axis=1) for c in centers], axis=0)
probs = d2 / d2.sum()
centers.append(X[rng.choice(n, p=probs)])
return np.array(centers)
def kmeans(X, K, max_iter=100, seed=0, use_pp=True):
centers = kmeans_pp(X, K, seed) if use_pp else X[np.random.default_rng(seed).choice(len(X), K, replace=False)]
labels = np.zeros(len(X), dtype=int)
for _ in range(max_iter):
# E 步:最近质心
dist = np.array([((X - c) ** 2).sum(axis=1) for c in centers]).T # [n, K]
new_labels = dist.argmin(axis=1)
# M 步:更新质心
new_centers = np.array([X[new_labels == k].mean(axis=0) if np.any(new_labels == k)
else centers[k] for k in range(K)])
if np.array_equal(new_labels, labels):
break
labels, centers = new_labels, new_centers
return labels, centers
rng = np.random.default_rng(2)
true_c = np.array([[0, 0], [8, 8], [0, 8]])
Xk = np.vstack([rng.normal(c, 0.8, (50, 2)) for c in true_c])
labels, centers = kmeans(Xk, 3, seed=0)
print('K-Means 簇中心:')
for c in np.round(centers, 2):
print(' ', c)
print('(真实质心: [0,0], [8,8], [0,8])')
print('簇大小分布:', np.bincount(labels))
# 轮廓系数手写(简版):衡量簇内紧凑 vs 簇间分离
def silhouette(X, labels):
from collections import defaultdict
groups = defaultdict(list)
for i, l in enumerate(labels):
groups[l].append(i)
vals = []
for i, x in enumerate(X):
own = groups[labels[i]]
a = np.mean([np.linalg.norm(x - X[j]) for j in own if j != i]) if len(own) > 1 else 0.0
b = min(np.mean([np.linalg.norm(x - X[j]) for j in g])
for l, g in groups.items() if l != labels[i])
vals.append((b - a) / max(a, b))
return float(np.mean(vals))
print('轮廓系数 =', round(silhouette(Xk, labels), 3), '(越接近1越好,期望 >0.6)')
§5 K-Means 的局限与 EM 的关系(GMM 预告)¶
局限¶
- K 需指定:用肘部法则(WCSS vs K 拐点)或轮廓系数选
- 球形假设:对椭圆/流形簇效果差
- 对异常值敏感:均值被拉偏
- 局部最优:多跑几次随机初始化取最优 WCSS
与 EM 的关系¶
K-Means 是**高斯混合模型(GMM)**的特例:
- GMM 用「软分配」:$E[z_{ik}] = P(C_k \mid x_i)$(责任值)
- K-Means 用「硬分配」:$z_{ik} \in \{0,1\}$
- GMM 方差协方差自由;K-Means 假设各向同性方差 $\sigma^2 I$
- 当 $\sigma \to 0$ 时 GMM 退化为 K-Means
一句话:K-Means = 方差趋于 0 的硬分配 GMM = EM 的极限情况。
➡️ 下一节 §6 给出 GMM 的完整似然、E 步 / M 步公式推导与手写 EM 代码(P0 高频考点)。
§6 高斯混合模型(GMM)与 EM 全量推导(P0 高频)¶
6.1 模型:K 个高斯的加权混合¶
数据由 K 个高斯分量生成:每个样本先按混合系数 $\pi_k$ 选第 k 个分量,再从 $\mathcal{N}(x \mid \mu_k, \Sigma_k)$ 采样:
$$p(x) = \sum_{k=1}^{K} \pi_k \, \mathcal{N}(x \mid \mu_k, \Sigma_k), \qquad \sum_k \pi_k = 1, \ \pi_k \ge 0$$
引入隐变量 $z_i \in \{1,\dots,K\}$ 表示样本 $x_i$ 来自哪个分量——这就是「隐变量」:观测不到,只能用后验去估计。完整数据对数似然:
$$\log p(X, Z \mid \theta) = \sum_i \log \pi_{z_i} + \sum_i \log \mathcal{N}(x_i \mid \mu_{z_i}, \Sigma_{z_i})$$
而直接对边缘似然 $\log \sum_Z p(X, Z \mid \theta)$ 求导会被「$\log$ 里套 $\sum$」卡住——这正是 EM 要解决的问题。
6.2 E 步:软分配(后验 / 责任值)¶
固定参数,用贝叶斯定理算每个样本属于每个分量的后验:
$$\gamma_{ik} = P(z_i = k \mid x_i) = \frac{\pi_k \, \mathcal{N}(x_i \mid \mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j \, \mathcal{N}(x_i \mid \mu_j, \Sigma_j)}$$
$\gamma_{ik}$ 叫责任值(responsibility):样本 i 对分量 k 的软归属。分母是归一化常数,保证 $\sum_k \gamma_{ik} = 1$。
6.3 M 步:带权重的 MLE¶
把 $\gamma_{ik}$ 当「软计数」,用带权重的高斯 MLE 更新参数($N_k = \sum_i \gamma_{ik}$ 是第 k 个分量的有效样本数):
$$\pi_k = \frac{N_k}{n}, \qquad \mu_k = \frac{\sum_i \gamma_{ik} x_i}{N_k}, \qquad \Sigma_k = \frac{\sum_i \gamma_{ik} (x_i - \mu_k)(x_i - \mu_k)^{\top}}{N_k}$$
直觉:E 步与 M 步交替执行,每一步都使 log-likelihood 单调不减(Jensen 不等式保证),最终收敛到(局部)极大值——EM 是「坐标上升」在含隐变量模型上的推广,GMM 是 EM 最经典的载体。
6.4 与 K-Means 的关系(面试必答)¶
- K-Means 的 E 步是硬分配(最近质心,等价于 $\gamma$ 退化为 one-hot 的极限),GMM 是软分配
- K-Means 假设各向同性方差 $\sigma^2 I$ 且 $\sigma \to 0$;GMM 协方差自由,能拟合椭圆簇、能给出密度估计(生成式)
💡 直觉:K-Means 像「绝对站队」,GMM/EM 像「按比例站位」——先按当前站位估每队的身高分布,再按新分布重新站位,反复迭代直到队形稳定。
⚠️ 数值要点:概率连乘会下溢,代码用 log 空间计算($\log \pi_k + \log \mathcal{N}$),归一化前减行最大值;协方差加微小对角项(如 $10^{-6}I$)防奇异。
# ---- GMM 手写:EM 迭代 + log-likelihood 收敛判断 ----
def log_gaussian(X, mu, Sigma):
# log N(x | mu, Sigma) = -0.5*(d*log(2π) + log|Sigma| + 马氏距离²)
d = len(mu)
diff = X - mu
inv = np.linalg.inv(Sigma)
_, logdet = np.linalg.slogdet(Sigma)
mah = np.sum((diff @ inv) * diff, axis=1)
return -0.5 * (d * np.log(2 * np.pi) + logdet + mah)
def gmm_em(X, K, max_iter=200, tol=1e-4, seed=0):
"""手写 GMM 的 EM 求解。返回 (pi, mu, Sigma, gamma, history)。"""
rng = np.random.default_rng(seed)
n, d = X.shape
# 初始化:随机取 K 个样本作中心、单位协方差、均匀混合系数
idx = rng.choice(n, K, replace=False)
mu = X[idx].astype(float)
Sigma = np.tile(np.eye(d), (K, 1, 1))
pi = np.full(K, 1.0 / K)
def log_likelihood():
ll = np.zeros((n, K))
for k in range(K):
ll[:, k] = np.log(pi[k]) + log_gaussian(X, mu[k], Sigma[k])
return np.logaddexp.reduce(ll, axis=1).sum() # Σ_i log Σ_k exp(...)
ll = log_likelihood()
history = [ll]
for it in range(max_iter):
# ---- E 步:后验 γ_ik = π_k N(x_i) / Σ_j π_j N(x_i)(log 空间防下溢)----
log_w = np.zeros((n, K))
for k in range(K):
log_w[:, k] = np.log(pi[k]) + log_gaussian(X, mu[k], Sigma[k])
log_w -= log_w.max(axis=1, keepdims=True) # 每行减最大值,数值稳定
gamma = np.exp(log_w)
gamma /= gamma.sum(axis=1, keepdims=True) # 归一化 → 责任值 γ
# ---- M 步:带权重的 MLE ----
Nk = gamma.sum(axis=0) # 每分量有效样本数
pi = Nk / n
for k in range(K):
mu[k] = gamma[:, k] @ X / Nk[k]
diff = X - mu[k]
Sigma[k] = (gamma[:, k, None] * diff).T @ diff / Nk[k]
Sigma[k] += 1e-6 * np.eye(d) # 防奇异
# ---- 收敛判断:log-likelihood 增量 < tol ----
ll_new = log_likelihood()
history.append(ll_new)
if abs(ll_new - ll) < tol:
ll = ll_new
break
ll = ll_new
return pi, mu, Sigma, gamma, np.array(history)
# 3 个高斯混合(每簇 80 点),真实均值已知用于评估
rng = np.random.default_rng(5)
true_mu = np.array([[0, 0], [6, 0], [3, 6]])
Xg = np.vstack([rng.normal(m, 1.0, (80, 2)) for m in true_mu])
y_true_g = np.repeat(np.arange(3), 80) # 真实分量标签(仅用于评估)
pi, mu, Sigma, gamma, history = gmm_em(Xg, K=3, seed=0)
pred = gamma.argmax(axis=1)
# 聚类标签编号是任意的:与真实类别做排列对齐后算准确率
from itertools import permutations
def aligned_acc(labels_pred, y_true_):
K = len(np.unique(y_true_))
best = 0.0
for perm in permutations(range(K)):
best = max(best, np.mean([perm[c] for c in labels_pred] == y_true_))
return best
print('EM 迭代次数 =', len(history), ' 最终 log-likelihood =', round(history[-1], 2))
print('log-likelihood 曲线(前 8 个):', np.round(history[:8], 1), '(单调不减)')
print('混合系数 π =', np.round(pi, 3))
print('估计均值 μ =', np.round(mu, 2).tolist())
print('真实均值 =', true_mu.tolist())
print('对齐后聚类准确率 =', round(aligned_acc(pred, y_true_g), 4))
# sklearn 对照:ARI(调整兰德指数,对标签编号不敏感)
try:
from sklearn.metrics import adjusted_rand_score
print('sklearn ARI =', round(adjusted_rand_score(pred, y_true_g), 4))
except ImportError:
print('sklearn 未安装,跳过 ARI 对照')
# 可视化:聚类结果 + 拟合的高斯椭圆(协方差特征分解 → 椭圆长短轴)
try:
import matplotlib.pyplot as plt
from matplotlib.patches import Ellipse
fig, ax = plt.subplots(figsize=(5, 4.5))
colors = ['tab:blue', 'tab:orange', 'tab:green']
for k in range(3):
mask = pred == k
ax.scatter(Xg[mask, 0], Xg[mask, 1], s=12, c=colors[k], label=f'cluster {k}')
for k in range(3):
w, V = np.linalg.eigh(Sigma[k]) # 特征值 → 椭圆长短轴
ang = np.degrees(np.arctan2(V[1, 0], V[0, 0]))
ell = Ellipse(mu[k], 2 * np.sqrt(w[0]), 2 * np.sqrt(w[1]),
angle=ang, fill=False, edgecolor='black', ls='--')
ax.add_patch(ell)
ax.scatter(mu[k, 0], mu[k, 1], marker='x', s=90, color='black')
ax.legend(); ax.set_title('GMM 聚类结果(虚线=拟合椭圆)')
plt.tight_layout(); plt.show()
print('(已绘制 GMM 拟合可视化)')
except ImportError:
print('未安装 matplotlib,跳过可视化')
§7 DBSCAN:密度聚类(高频考点)¶
7.1 三类点¶
- 核心点(core):半径 eps 邻域内的样本数 ≥ min_samples
- 边界点(border):不是核心点,但落在某个核心点的 eps 邻域内
- 噪声点(noise):两者都不是
7.2 三个"密度"概念¶
- 密度直达(directly density-reachable):q 在 p 的 eps 邻域内,且 p 是核心点
- 密度可达(density-reachable):存在一条链路 p → ⋯ → q,每相邻两步都是密度直达(中间点必须都是核心点)
- 密度相连(density-connected):存在一个 o,使 p、q 都从 o 密度可达——这是两个簇合并的判据
7.3 两个超参¶
- eps(邻域半径):太小 → 簇碎裂成很多块、噪声变多;太大 → 簇互相桥接合并、噪声消失
- min_samples:太小 → 噪声被吸进簇(出现"毛刺");太大 → 核心点变少、更多点沦为噪声
算法流程:任取一个未访问的核心点开新簇,BFS 扩展所有密度可达的点;被扩展到但不是核心点的成为边界点,全程没被任何簇吸收的成为噪声。
7.4 与 K-Means 对比¶
| 算法 | 簇形状 | 需指定 K | 主要超参 | 复杂度 |
|---|---|---|---|---|
| K-Means | 球形 | 是 | K | $O(n \cdot K \cdot d \cdot T)$ |
| DBSCAN | 任意形状 | 否 | eps, min_samples | $O(n^2)$(朴素)/ $O(n\log n)$(空间索引) |
💡 直觉:DBSCAN 像"传话游戏"——核心点是"话多的人",能把消息传遍整个社团;边界点是"只和某个核心点说过话的人";噪声是"谁都不认识的人"。
⚠️ 高维下欧氏距离失效(维度灾难),DBSCAN 常用于 2D/低维数据或先降维再用。
# ---- DBSCAN 手写:核心点/边界点/噪声 + BFS 扩展 ----
def dbscan(X, eps, min_samples):
"""手写 DBSCAN。返回 labels:-1=噪声,0..K-1=簇。"""
n = len(X)
labels = np.full(n, -1)
# 预计算邻域:欧氏距离 <= eps 的索引集合
neigh = [set(np.where(((X - X[i]) ** 2).sum(axis=1) <= eps ** 2)[0].tolist())
for i in range(n)]
cluster_id = 0
for i in range(n):
if labels[i] != -1:
continue
if len(neigh[i]) < min_samples:
labels[i] = -1 # 暂定噪声(后续可能被核心点吸收)
continue
# i 是核心点:开新簇,BFS 扩展所有密度可达的点
labels[i] = cluster_id
frontier = list(neigh[i])
while frontier:
j = frontier.pop()
if labels[j] != -1:
continue
labels[j] = cluster_id # 边界点或核心点,一律吸收进本簇
if len(neigh[j]) >= min_samples:
# j 也是核心点:继续向外扩展
frontier.extend(nb for nb in neigh[j] if labels[nb] == -1)
cluster_id += 1
return labels
# 数据:两个月牙形簇(非线性形状,K-Means 处理不了)+ 10 个随机噪声点
rng = np.random.default_rng(3)
t = rng.uniform(0, np.pi, 60)
Xdb1 = np.c_[np.cos(t), np.sin(t)] * 4 + rng.normal(0, 0.15, (60, 2))
Xdb2 = np.c_[np.cos(t + np.pi), np.sin(t + np.pi)] * 4 + np.array([4.0, 2.0]) + rng.normal(0, 0.15, (60, 2))
Xnoise = rng.uniform(-2, 7, (10, 2))
Xdb = np.vstack([Xdb1, Xdb2, Xnoise])
y_db = np.concatenate([np.zeros(60), np.ones(60), np.full(10, -1)]) # 真实标注(-1=噪声)
try:
from sklearn.cluster import DBSCAN as SkDBSCAN
HAS_SK = True
except ImportError:
HAS_SK = False
labels_hand = dbscan(Xdb, eps=1.2, min_samples=5)
print('eps=1.2, min_samples=5(合适参数):')
print(' 手写: 簇数 =', len(set(labels_hand) - {-1}), ' 噪声数 =', int((labels_hand == -1).sum()))
if HAS_SK:
from sklearn.metrics import adjusted_rand_score
labels_sk = SkDBSCAN(eps=1.2, min_samples=5).fit_predict(Xdb)
print(' sklearn: 簇数 =', len(set(labels_sk) - {-1}), ' 噪声数 =', int((labels_sk == -1).sum()))
print(' 手写 vs sklearn ARI =', round(adjusted_rand_score(labels_hand, labels_sk), 4))
print(' 手写 vs 真实标签 ARI =', round(adjusted_rand_score(labels_hand, y_db), 4))
# 不同 eps 的效果(同一数据、同一 min_samples)——解释配合下方可视化
print('\neps 灵敏度演示:')
for eps in [0.6, 1.2, 3.0]:
lab = dbscan(Xdb, eps=eps, min_samples=5)
print(' eps=%.1f -> 簇数=%d, 噪声数=%d' % (eps, len(set(lab) - {-1}), (lab == -1).sum()))
# 可视化:三种 eps 的聚类效果
try:
import matplotlib.pyplot as plt
fig, axes = plt.subplots(1, 3, figsize=(12, 3.6))
for ax, eps in zip(axes, [0.6, 1.2, 3.0]):
lab = dbscan(Xdb, eps=eps, min_samples=5)
ax.scatter(Xdb[lab == -1, 0], Xdb[lab == -1, 1], c='black', s=10, marker='x', label='noise')
for k in np.unique(lab[lab != -1]):
ax.scatter(Xdb[lab == k, 0], Xdb[lab == k, 1], s=10)
ax.set_title(f'eps={eps}\n簇数={len(set(lab) - {-1})}, 噪声={(lab == -1).sum()}')
ax.set_aspect('equal')
plt.tight_layout(); plt.show()
print('解释:eps 过小 → 碎片簇 + 噪声多;eps=1.2 合适 → 2 个完整月牙;eps 过大 → 两簇被桥接合并成 1 簇')
except ImportError:
print('未安装 matplotlib,跳过可视化')
§8 层次聚类:凝聚式(agglomerative)简述¶
思想:自底向上合并。初始每个样本自成一簇,每次把「距离最近」的两簇合并,直到只剩 K 簇(或 1 簇)。
三种簇间距离(linkage):
- 单连接(single):两簇最近点的距离 → 能发现任意形状簇,但对噪声/桥接敏感(链式效应)
- 全连接(complete):两簇最远点的距离 → 偏向紧凑球形簇
- 平均连接(average):两簇所有点对距离的平均 → 折中方案
树状图(dendrogram):合并历史画成一棵树,在任意高度"一刀切"就得到对应 K 的聚类——不用预先指定 K 是层次聚类最大的卖点。
复杂度:朴素实现 $O(n^3)$,优先队列可优化到 $O(n^2 \log n)$——n 大时不划算。
vs K-Means:层次聚类结果确定(无初始化随机性、不依赖初始质心);但慢、对噪声敏感、合并不可撤销(一步合并错了无法回退)。
💡 直觉:像"拼班级"——先每人单独一组,每天把最"聊得来"(距离最近)的两个组合并,直到人数合适;树状图就是这份"合并族谱"。
# ---- 凝聚式层次聚类(单连接)手写 + sklearn 对照 ----
def agglomerative_single(X, K):
"""手写凝聚式层次聚类(单连接):反复合并最近簇对直到剩 K 簇。"""
n = len(X)
clusters = [[i] for i in range(n)] # 初始:每样本一簇
while len(clusters) > K:
best_d, best_a, best_b = np.inf, -1, -1
for a in range(len(clusters)):
for b in range(a + 1, len(clusters)):
diff = X[clusters[a]][:, None] - X[clusters[b]][None, :] # [|a|, |b|, d]
d = np.sqrt((diff ** 2).sum(-1).min()) # 单连接:最近点对
if d < best_d:
best_d, best_a, best_b = d, a, b
clusters[best_a] += clusters[best_b] # 合并(吸收进 a 号簇)
del clusters[best_b]
labels = np.empty(n, dtype=int)
for k, c in enumerate(clusters):
for i in c:
labels[i] = k
return labels
# 3 个紧致高斯簇
rng = np.random.default_rng(9)
centers = np.array([[0, 0], [5, 0], [2, 4]])
Xh = np.vstack([rng.normal(c, 0.5, (30, 2)) for c in centers])
yh = np.repeat(np.arange(3), 30)
lab_h = agglomerative_single(Xh, 3)
print('手写单连接 对齐后准确率 =', round(aligned_acc(lab_h, yh), 4))
try:
from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import adjusted_rand_score
lab_sk = AgglomerativeClustering(n_clusters=3, linkage='single').fit_predict(Xh)
print('手写 vs sklearn 凝聚式: ARI =', round(adjusted_rand_score(lab_h, lab_sk), 4))
print('sklearn vs 真实标签: ARI =', round(adjusted_rand_score(lab_sk, yh), 4))
except ImportError:
print('sklearn 未安装,跳过层次聚类对照')
§9 聚类外部指标:纯度 / NMI / ARI¶
有真实标签时,用「外部指标」评价聚类好坏(聚类是监督式评估:聚类划分越接近真实划分越好)。
纯度(purity)¶
每个簇用占比最大的真实类别命名,统计被"押中"的样本占比:
$$\text{purity} = \frac{1}{n} \sum_{k=1}^{K} \max_j \left| C_k \cap T_j \right|$$
缺点:K 越大纯度越高(每个点一簇 → purity=1),不能惩罚簇数。
NMI(归一化互信息)¶
互信息度量「聚类划分 C 与真实划分 T 共享的信息量」,用熵归一化到 $[0,1]$:
$$\text{NMI}(C, T) = \frac{2 \, I(C; T)}{H(C) + H(T)}, \qquad I(C;T) = \sum_{c}\sum_{t} \frac{n_{ct}}{n} \log \frac{n \cdot n_{ct}}{n_c \, n_t}$$
ARI(调整兰德指数)¶
把样本两两配对,按「是否同簇、是否同类」分成四类(a=同簇同真、b=异簇同真、c=同簇异真、d=异簇异真),兰德指数 $\text{RI} = (a+b)/(a+b+c+d)$。ARI 在 RI 上减去「随机划分的期望」再归一化:
$$\text{ARI} = \frac{\text{RI} - E[\text{RI}]}{\max(\text{RI}) - E[\text{RI}]}$$
ARI ≈ 1 完美一致,≈ 0 等于随机,可为负。三者中 ARI 对随机划分的惩罚最合理,论文中最常用。
💡 直觉:纯度数"队名押中的队员数",NMI 数"两个分组透露了多少公共信息",ARI 数"样本对的配对关系押中多少、再扣掉运气"。
⚠️ 内部指标(如轮廓系数)不需要标签,外部指标(以上三者)必须有标签——面试别混淆。
# ---- 聚类外部指标:手写纯度 + sklearn 对照 ----
def purity(y_pred, y_true_):
"""手写纯度:每个簇取与其交叠最多的真实类别计数之和 / n。"""
n = len(y_true_)
total = 0
for k in np.unique(y_pred):
mask = y_pred == k
counts = np.bincount(y_true_[mask].astype(int), minlength=int(y_true_.max()) + 1)
total += counts.max() # 该簇"押中"最多的真实类别
return total / n
# 复用 §4 K-Means 的聚类结果(labels)与真实标签对比
y_true_k = np.repeat(np.arange(3), 50) # §4 数据 Xk:3 簇各 50 个,簇中心 [0,0],[8,8],[0,8]
print('手写纯度 =', round(purity(labels, y_true_k), 4))
try:
from sklearn.metrics import adjusted_rand_score, normalized_mutual_info_score
print('sklearn NMI =', round(normalized_mutual_info_score(labels, y_true_k), 4))
print('sklearn ARI =', round(adjusted_rand_score(labels, y_true_k), 4))
# 手写 ARI(面试手推版:基于配对计数公式)
from math import comb
def ari_manual(l1, l2):
n = len(l1)
agree = sum(comb(int(np.sum((l1 == a) & (l2 == b))), 2)
for a in np.unique(l1) for b in np.unique(l2)) # Σ_ij C(n_ij, 2)
S1 = sum(comb(int(np.sum(l1 == a)), 2) for a in np.unique(l1))
S2 = sum(comb(int(np.sum(l2 == b)), 2) for b in np.unique(l2))
exp = S1 * S2 / comb(n, 2) # 随机划分期望
maxim = (S1 + S2) / 2.0
return (agree - exp) / (maxim - exp)
print('手写 ARI =', round(ari_manual(labels, y_true_k), 4), '(与 sklearn 对照一致)')
except ImportError:
print('sklearn 未安装,跳过 NMI/ARI 对照')
§10 常见 bug 与边界(面试踩坑区)¶
- 高斯 NB 方差为 0:某类某特征常量 → 除零/NaN → 加
eps - 概率连乘下溢:用 log 求和而非直接连乘
- 多项式 NB 零频词:不平滑会概率 0 抹杀整条——必须拉普拉斯平滑
- K-Means 空簇:某簇无样本 →
mean空数组报错 → 保留原质心或重新初始化 - K-Means 不收敛检测:labels 不变就 break(节省迭代)
- 随机初始化差:直接均匀随机容易陷局部最优——用 k-means++
- 距离计算维度爆炸:循环逐点算 $\|x-c\|^2$ 用广播,别写三层 for
- K 与类别数混淆:无监督聚类 K 不是监督标签数
- GMM 协方差奇异:某分量有效样本数 $N_k$ 很小时协方差不可逆 → 加微小对角项 $10^{-6}I$
- GMM/DBSCAN 不归一化:聚类对特征尺度敏感,先标准化再跑
- DBSCAN eps 拍脑袋:eps 过小碎片化、过大桥接合并——用 k-距离图(k-distance plot)选拐点
§11 面试追问与扩展(加分项)¶
11.1 朴素贝叶斯 vs 逻辑回归(生成 vs 判别经典对比)¶
- 数据充足时判别式(LR)通常误差更低(Ng & Jordan 2001 理论+实验)
- 数据少 / 缺失值多时生成式(NB)更稳(先验可注入)
- NB 训练快(闭式 MLE)、可解释(概率参数)
11.2 K-Means 复杂度¶
每次迭代 $O(n \cdot K \cdot d)$(算 n×K 个距离),迭代次数一般 < 100;总 $O(T \cdot n \cdot K \cdot d)$。
11.3 实际工程¶
- 文本分类:先 TF-IDF 再多项式 NB / LR
- 聚类:K-Means 做用户分群 → 再监督建模(两段式)
- 图像:K-Means 颜色量化(每个像素归到 K 个代表色)
- 异常检测:DBSCAN 的噪声点天然是"离群点"
11.4 GMM/EM 的高频追问¶
- 为什么用 EM 而不是直接对 $p(x)=\sum_k\pi_k\mathcal{N}(x)$ 梯度上升:$\log$ 套 $\sum$ 求导展开项太多、无闭式解;EM 每次迭代有解析更新且保证 log-likelihood 单调不减
- EM 收敛到全局最优吗:不保证,只保证局部极大——多跑几个初始化取最大 log-likelihood
- GMM vs K-Means 选型:数据近似球形找 K-Means;要密度估计 / 椭圆簇 / soft 归属找 GMM
§12 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(10 问)¶
- 1. 写出贝叶斯定理与朴素假设公式
- 2. 解释为什么叫「朴素」及代价
- 3. 手写高斯 NB(numpy)
- 4. 推导类先验与条件均值/方差 MLE
- 5. 为什么预测取 log 求和(下溢)
- 6. 拉普拉斯平滑公式与动机
- 7. 手写多项式 NB(词频矩阵)
- 8. 写出 K-Means 目标函数
- 9. 描述 K-Means 的 E 步 / M 步
- 10. 手写 K-Means(含 k-means++)
L2 进阶(13 问)¶
- 11. 证明 K-Means 每步 WCSS 不增(收敛性)
- 12. 手写轮廓系数
- 13. 肘部法则手算(WCSS vs K)
- 14. 生成式 vs 判别式各举两例
- 15. K-Means 与 GMM 的关系
- 16. 手写 GMM(EM 全量:E 步后验 γ、M 步三个更新式、log-likelihood 收敛判断)
- 17. 手写 DBSCAN(核心点/边界点/噪声 + BFS 扩展)
- 18. 手写纯度,并对比 sklearn 的 NMI/ARI
- 19. 凝聚式层次聚类手写(单连接)与 sklearn 对照
- 20. NB 处理缺失值(忽略该特征列)
- 21. 文本分类完整流程(分词→词频→NB)手写
- 22. K-Means 对异常值鲁棒变体(K-Medoids)概念
- 23. 手写 mini-batch K-Means
L3 挑战(7 问)¶
- 24. 从似然出发完整推导 GMM 的 E 步 / M 步更新式
- 25. 谱聚类 / 层次聚类概念对比
- 26. 贝叶斯最优分类器与 0-1 损失
- 27. 朴素贝叶斯在大规模垃圾邮件/文本分类的工程细节
- 28. 推导 K-Means 的 Lloyd 算法收敛性(两步都降目标)
- 29. 用 Jensen 不等式证明 EM 的 log-likelihood 单调不减
- 30. DBSCAN 的 eps/min_samples 灵敏度分析(能画出不同参数效果)
自测要点¶
- 10 分钟内盲写:高斯 NB + K-Means(numpy)
- 能白板写出 GMM 的似然、E 步 γ 公式、M 步三个更新式
- 讲清 NB vs LR(生成 vs 判别)、K-Means vs GMM vs DBSCAN 的选型
🏁 本章小结¶
- 原理一句话:朴素贝叶斯 = 贝叶斯定理 + 条件独立;K-Means = 「分组 → 更新质心」循环到收敛。
- 必会公式:$\hat y=\arg\max_y P(y)\prod_j P(x_j|y)$;平滑 $\frac{count+\alpha}{N+\alpha K}$;K-Means 目标 $\min\sum_k\sum_{i\in C_k}\|x_i-\mu_k\|^2$。
- 面试怎么考:「朴素」假设在哪;没见过的事件为什么炸(连乘为 0)→ 平滑;K-Means 局部最优、k 用肘部法;K-Means 是 EM 的特例(硬 vs 软)。
- 易错点:连续特征用高斯分布而不是计数;K-Means 结果依赖初始化 → KMeans++。
自测清单没把握的条目,回到对应小节重读后再打勾。