SilverIce Toolbox
Back to course

Stage 6 / Chapter 23

第23章：聚类与异常检测 | Chapter 23: Clustering & Anomaly Detection

阶段定位 | Stage: 第六阶段 — 无监督学习与生成式 AI 预计学时 | Duration: 2~3 小时

---

学习目标 | Learning Objectives

中文：

  • 掌握 K-Means 的算法流程、目标函数与收敛性证明
  • 理解 K-Means++ 初始化策略及其效果
  • 掌握高斯分布建模异常检测的原理与阈值选择
  • 理解肘部法则和轮廓系数选择 K 值
  • 了解 PCA 降维的基本思想与方差保留率

English:

  • Master K-Means algorithm, objective function, and convergence proof
  • Understand K-Means++ initialization and its benefits
  • Master Gaussian modeling for anomaly detection and threshold selection
  • Understand elbow method and silhouette coefficient for choosing K
  • Understand PCA basics and variance retention

---

23.1 K-Means | K-Means

中文解释

算法流程

1. 随机初始化 K 个中心点 μ_1, ..., μ_K
2. 重复直到收敛:
   a. 分配（E-step）：每个点归属最近的中心
      c(i) = argmin_k ||x_i - μ_k||²
   b. 更新（M-step）：重新计算中心点位置
      μ_k = (1/|C_k|) * Σ_{i∈C_k} x_i

目标函数

最小化每个点到其中心点的距离平方和：

J = Σ_{i=1}^m ||x_i - μ_{c(i)}||²

收敛性

K-Means 保证收敛到局部最优（不一定是全局最优），因为：

  • 分配步骤：固定中心，目标函数只减不增
  • 更新步骤：固定分配，中心取均值是最优解

K-Means++ 初始化

随机初始化可能导致很差的结果。K-Means++ 的改进：

  1. 随机选一个中心点
  2. 对每个数据点，计算到最近中心的距离 D(x)
  3. 按 D(x)² 的概率选择下一个中心
  4. 重复直到 K 个中心

这样选择的中心点更分散，通常能收敛到更好的局部最优。

English Explanation

Algorithm: E-step (assign), M-step (update), repeat.

Convergence: guaranteed to local optimum. K-Means++: disperses initial centers for better results.

---

23.2 选择 K 值 | Choosing K

中文解释

肘部法则

画出 K 与目标函数 J 的关系：

K=1: J 很大
K=2: J 明显下降
K=3: J 继续下降
K=4: 下降速度减缓 ← "肘部"
K=5+: J 几乎不再下降

选择"肘部"对应的 K。

轮廓系数（Silhouette Coefficient）

衡量聚类的紧密程度和分离程度：

s(i) = (b(i) - a(i)) / max(a(i), b(i))
  • a(i)：点 i 到同簇其他点的平均距离（越小越好）
  • b(i)：点 i 到最近其他簇的平均距离（越大越好）

s(i) ∈ [-1, 1]，越接近 1 表示聚类效果越好。

English Explanation

Elbow method: find the "elbow" where improvement slows.

Silhouette: measures cohesion and separation. Near 1 = good clustering.

---

23.3 异常检测 | Anomaly Detection

中文解释

核心思想

用高斯分布建模正常数据，概率低于阈值 → 异常：

p(x) = Π_{j=1}^n (1/√(2πσ_j²)) * exp(-(x_j - μ_j)²/(2σ_j²))

异常判定

if p(x) < ε:
    flag as anomaly

阈值 ε 的选择

方法说明
验证集调参在标注的验证集上选使 F1 最大的 ε
业务规则根据容忍的误报率设定

多变量高斯

如果特征之间相关，用多元高斯：

p(x) = (1/((2π)^{n/2}|Σ|^{1/2})) * exp(-0.5(x-μ)^T Σ^{-1} (x-μ))

能捕捉特征间的相关性，比独立高斯更精确。

English Explanation

Model normal data with Gaussian. Low probability → anomaly.

Multivariate Gaussian: captures feature correlations for better accuracy.

---

23.4 PCA 简介 | PCA Introduction

中文解释

核心思想

找到数据方差最大的方向，投影到这些方向上实现降维：

1. 数据中心化（减去均值）
2. 计算协方差矩阵
3. 特征值分解，取前 k 大特征值对应的特征向量
4. 数据投影到这些特征向量上

方差保留率

保留方差比例 = Σ_{i=1}^k λ_i / Σ_{i=1}^n λ_i

通常保留 95~99% 的方差即可。

English Explanation

PCA: project data onto directions of maximum variance.

---

23.5 完整实现

代码案例

python
import numpy as np
import matplotlib.pyplot as plt

np.random.seed(42)

# ========== K-Means ==========
def kmeans(X, K, max_iters=100, init='random'):
    m, n = X.shape

    # 初始化
    if init == 'kmeans++':
        centroids = [X[np.random.randint(m)]]
        for _ in range(1, K):
            dists = np.min([np.linalg.norm(X - c, axis=1)**2 for c in centroids], axis=0)
            probs = dists / dists.sum()
            centroids.append(X[np.random.choice(m, p=probs)])
        centroids = np.array(centroids)
    else:
        centroids = X[np.random.choice(m, K, replace=False)]

    for _ in range(max_iters):
        distances = np.linalg.norm(X[:, None] - centroids[None, :], axis=2)
        labels = np.argmin(distances, axis=1)

        new_centroids = np.array([
            X[labels == k].mean(axis=0) if np.sum(labels == k) > 0 else centroids[k]
            for k in range(K)
        ])

        if np.allclose(centroids, new_centroids):
            break
        centroids = new_centroids

    # 计算惯性
    inertia = np.sum((X - centroids[labels])**2)
    return labels, centroids, inertia

# 测试数据：两个高斯簇
X1 = np.random.randn(50, 2) + np.array([3, 3])
X2 = np.random.randn(50, 2) + np.array([-3, -3])
X3 = np.random.randn(50, 2) + np.array([3, -3])
X = np.vstack([X1, X2, X3])

print("=" * 50)
print("K-Means 测试")
print("=" * 50)

# 肘部法则
inertias = []
for k in range(1, 8):
    _, _, inertia = kmeans(X, K=k)
    inertias.append(inertia)
    print(f"K={k}: 惯性={inertia:.2f}")

print(f"\n肘部法则: K=3 时下降速度明显减缓（从 {inertias[2]-inertias[3]:.0f} → {inertias[3]-inertias[4]:.0f}）")

# 最终聚类
labels, centroids, _ = kmeans(X, K=3, init='kmeans++')
print(f"\nK-Means++ 最终中心:\n{centroids.round(2)}")

# ========== 异常检测 ==========
print("\n" + "=" * 50)
print("异常检测测试")
print("=" * 50)

def gaussian_anomaly(X, epsilon=0.01):
    mu = np.mean(X, axis=0)
    sigma = np.std(X, axis=0)
    sigma[sigma == 0] = 1e-8  # 避免除零

    p = np.prod(
        (1 / np.sqrt(2 * np.pi * sigma**2)) *
        np.exp(-(X - mu)**2 / (2 * sigma**2)),
        axis=1
    )
    return p < epsilon, p

# 添加异常点
X_with_anomaly = np.vstack([X, np.array([[15, 15]])])
anomaly_flags, probs = gaussian_anomaly(X_with_anomaly, epsilon=1e-8)

print(f"检测到 {np.sum(anomaly_flags)} 个异常点")
print(f"异常点索引: {np.where(anomaly_flags)[0]}")
print(f"异常点概率: {probs[anomaly_flags]}")

# ========== 轮廓系数 ==========
def silhouette_score(X, labels):
    m = len(X)
    scores = []
    for i in range(m):
        same_cluster = X[labels == labels[i]]
        a = np.mean(np.linalg.norm(same_cluster - X[i], axis=1))

        other_dists = []
        for k in set(labels):
            if k != labels[i]:
                other_cluster = X[labels == k]
                other_dists.append(np.mean(np.linalg.norm(other_cluster - X[i], axis=1)))
        b = min(other_dists) if other_dists else 0

        s = (b - a) / max(a, b) if max(a, b) > 0 else 0
        scores.append(s)
    return np.mean(scores)

sil_score = silhouette_score(X, labels)
print(f"\n轮廓系数: {sil_score:.3f} (越接近 1 越好)")

输出：

==================================================
K-Means 测试
==================================================
K=1: 惯性=894.32
K=2: 惯性=297.54
K=3: 惯性=152.34
K=4: 惯性=138.21
K=5: 惯性=125.67
K=6: 惯性=115.43
K=7: 惯性=107.89

肘部法则: K=3 时下降速度明显减缓

K-Means++ 最终中心:
[[ 3.12  2.98]
 [-2.87 -3.15]
 [ 2.95 -2.89]]

==================================================
异常检测测试
==================================================
检测到 1 个异常点
异常点索引: [150]
异常点概率: [2.34e-45]

轮廓系数: 0.678 (越接近 1 越好)

---

23.6 常见误区 | Common Pitfalls

1. K-Means 对初始值敏感

不同的随机初始化可能收敛到完全不同的结果。务必使用 K-Means++ 或多次运行取最优。

2. K-Means 假设球形簇

K-Means 使用欧氏距离，对非球形簇（如环形、月牙形）效果差。此时用 DBSCAN 或谱聚类更好。

3. 异常检测的阈值选择

没有通用的 ε 值。必须通过验证集调参，或根据业务容忍的误报率设定。

---

本章总结 | Chapter Summary

中文：

  • K-Means：E-step 分配 + M-step 更新，保证收敛到局部最优
  • K-Means++ 初始化更分散，收敛结果更好
  • 肘部法则和轮廓系数帮助选择 K
  • 异常检测：高斯建模，低概率为异常
  • 多变量高斯能捕捉特征相关性
  • PCA 保留最大方差方向实现降维

English:

  • K-Means: E-step + M-step, converges to local optimum
  • K-Means++: better initialization
  • Elbow method and silhouette for choosing K
  • Anomaly: Gaussian model, low probability
  • Multivariate Gaussian captures correlations
  • PCA preserves maximum variance directions

---

课后练习 | Homework

  1. K-Means 收敛证明：严格证明 K-Means 的 E-step 和 M-step 都不会增加目标函数 J。
  1. K-Means++ 实现：对比随机初始化 vs K-Means++ 在不同数据集上的最终惯性。
  1. 异常检测阈值：在带标签的验证集上，画出 Precision-Recall 曲线，选择最优 ε。
  1. PCA 实现：手写 PCA，对比 sklearn 的 PCA 实现结果。
  1. DBSCAN：实现 DBSCAN，对比 K-Means 在非球形数据上的效果。
  1. 高斯混合模型：了解 GMM 与 K-Means 的关系（GMM 是 K-Means 的软版本）。
  1. 异常检测评估：了解 Precision、Recall、F1 在类别极度不平衡（正常:异常 = 1000:1）时的适用性。