聚类算法

1. 聚类问题概述

聚类是将数据集划分为若干组（簇），使得同组内样本相似度高，不同组间相似度低。

1.1 聚类类型

2. K-Means算法

2.1 算法流程

1. 随机选择K个初始质心 μ1, μ2, ..., μK
2. 重复:
   a. 分配: 将每个样本分配到最近质心
      c_i = argmin_k ||x_i - μ_k||²
   b. 更新: 重新计算每个簇的质心
      μ_k = (1/|C_k|) Σ_{x_i ∈ C_k} x_i
3. 直到质心不再变化或达到最大迭代次数

2.2 目标函数

最小化簇内平方和（WCSS）：

$J={\sum }_{k=1}^K{\sum }_{{\mathbf{x}}_i\in C_k}\Vert {\mathbf{x}}_i-{\mathbf{\mu }}_k{\Vert }^2$

2.3 K值选择

肘部法则（Elbow Method）：

绘制 $K$ vs $J$，选择拐点处的 $K$。

轮廓系数（Silhouette Score）：

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

其中 $a(i)$ 为样本 $i$ 到同簇其他样本的平均距离，$b(i)$ 为样本 $i$ 到最近其他簇的平均距离。

• $s(i)\in [-1,1]$
• $s(i)\to 1$：聚类效果好
• $s(i)\to 0$：簇边界重叠
• $s(i)<0$：样本可能被分错簇

Gap Statistic：

$\text{Gap}(K)={\mathbb{E}}^{\ast }[\log W_K]-\log W_K$

选择使 Gap 统计量最大的 $K$。

2.4 K-Means++初始化

1. 随机选择第一个质心
2. 对于每个后续质心，以概率 $P(\mathbf{x})\propto D(\mathbf{x}{)}^2$ 选择
   • $D(\mathbf{x})$ 为 $\mathbf{x}$ 到最近已选质心的距离
3. 重复直到选出 $K$ 个质心

效果：避免初始质心过于集中，加速收敛。

2.5 K-Means变体

3. DBSCAN算法

3.1 核心概念

| 概念 | 定义 | | :------- | :---------------------------------------------------------------------------------- | ----------------------- | ------------------- | | ε-邻域 | $N_{ϵ}(\mathbf{x})=\{\mathbf{y}:d(\mathbf{x},\mathbf{y})\le ϵ\}$ | | 核心点 | $|N\_ϵ(\mathbf{x})|\ge \text{MinPts}$ | | 边界点 | 非核心点但在某核心点的ε-邻域内 | | 噪声点 | 既非核心点也非边界点 | | 密度直达 | 核心点p的ε-邻域内包含q | | 密度可达 | 通过核心点链可达 | | 密度相连 | 存在点o使p和q都从o密度可达 |

3.2 算法流程

1. 对每个未访问点p:
   a. 标记p为已访问
   b. 找到p的ε-邻域 N
   c. 如果 |N| < MinPts:
      - 标记p为噪声点
   d. 否则:
      - 创建新簇C
      - 扩展簇: 将N中所有点加入C
      - 对N中每个未访问点q:
        · 标记q为已访问
        · 找到q的ε-邻域N'
        · 如果 |N'| ≥ MinPts: 将N'加入N
        · 如果q未属于任何簇: 将q加入C

3.3 参数选择

ε选择：k-distance图

• 计算每个点到其第k近邻的距离（$k=\text{MinPts}-1$）
• 按距离排序绘图
• 选择”拐点”对应的距离作为ε

MinPts选择：

$\text{MinPts}\ge d+1$

通常取 $\text{MinPts}=2d$，$d$ 为数据维度。

3.4 DBSCAN优缺点

4. 层次聚类

4.1 凝聚层次聚类

自底向上，逐步合并最近的簇：

初始: 每个样本一个簇
  │
  ├── 合并最近的两个簇
  ├── 合并最近的两个簇
  ├── ...
  └── 所有样本合并为一个簇

4.2 簇间距离

Ward方法：

$\Delta J=\frac{|C_i||C_j|}{|C_i|+|C_j|}\Vert {\mathbf{\mu }}_i-{\mathbf{\mu }}_j{\Vert }^2$

4.3 树状图（Dendrogram）

          ┌───────┐
      ┌───┤       │
  ┌───┤   │       │
──┤   │   │       │
  A   B   C   D   E

• 横轴：样本
• 纵轴：合并距离
• 在指定高度水平切割，得到对应数量的簇

5. 聚类评估

5.1 内部指标（无标签）

5.2 外部指标（有标签）