biscuitの博客

误差平方和准则（SSE , $J_e$）#

定义：每个样本到其所属聚类中心（均值）的欧氏距离平方和。

类内越紧凑（距离中心越近），误差平方和越小，聚类效果越好。K-means算法就是基于该准则的。

散布矩阵准则#

参考特征选择中的散布矩阵定义，类内散布矩阵$S_w$衡量同一类别内部样本的聚集程度，类间散布矩阵$S_b$衡量不同类别中心之间的分散程度。由此衍生出以下准则：

• 类内散布与类间散布之比：$J_1 = \text{tr}(S_w^{-1}S_b)$。该指标越大，说明类内越紧凑，类间越分散，聚类效果越好。
• 行列式准则：$J_d = |S_w|$。该指标越小，说明类内越紧凑，聚类效果越好。

大间隔准则#

其核心思想类似于SVM，希望不同聚类之间能有较大的“间隔”（Margin）。

层次聚类#

自底向上（凝聚式）或自顶向下（分裂式）。不需要预先指定聚类数，但对噪声敏感，且无法修正早期的错误合并/分割。

算法步骤：

输入：样本集合 $\{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\}$，距离度量（如欧氏距离），目标聚类数 $c$。

1. 初始时每个样本自成一类,当前类别数 $c' = n$。
2. 每次合并最相似的两个类 $c' \leftarrow c' - 1$，判断“最接近”的标准
   • 两个类中最近样本的距离最小
   • 或两个类中心（均值）的欧氏距离最小。

优点

• 不需要初始化聚类中心，结果具有确定性（不受初始值影响），且可以生成树状图（Dendrogram）便于观察层次结构。

缺点

• 计算量较大（特别是每轮寻找最近两类的过程），且本质上是贪心优化，一旦合并无法撤销。

K-means#

直接对误差平方和准则 $J_e$ 进行迭代贪心搜索。

算法步骤（两步迭代直至收敛）：

输入：样本集合 $\{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\}$，目标聚类数 $c$。

1. 先初始化 $c$ 个聚类中心 $\{\boldsymbol{\mu}_1, \boldsymbol{\mu}_2, \ldots, \boldsymbol{\mu}_c\}$（如随机选择样本点或使用K-means++算法）。

2. 分配（E步思想）：固定当前的 c 个聚类中心 $\boldsymbol{\mu}_i$，依次计算每个样本到各聚类中心的距离，并将其分配给最近的聚类。

3. 更新（M步思想）：固定当前的划分，对于每一个聚类 $C_i$，重新计算该类内样本的均值，作为新的聚类中心 $\boldsymbol{\mu}_i$。

4. 收敛判断：新旧聚类中心的变化小于某个阈值，或达到最大迭代次数。

缺点

• 聚类结果高度依赖初始聚类中心的选择。不同的初始中心会收敛到不同的局部最优解

EM算法+GMM(Gaussian Mixture Model)#

基于概率分布的软聚类（每个样本以一定概率属于某个类）。

GMM: 假设数据 $\mathbf{x}$ 由多个(M个)高斯分布混合生成，每个高斯分布对应一个聚类。每个样本属于每个聚类的概率由该样本在对应高斯分布下的概率密度函数值决定。

引入隐变量 $Y=\{y_1, y_2, \ldots, y_n\},y_i=1\dotsb,M$，其中 $y_j$ 表示样本 $\mathbf{x}_j$ 属于哪个聚类，先猜一组参数 $\theta^{(0)}=\{a_i, \boldsymbol{\mu}_i, \Sigma_i\},i=1,\ldots,M$，用$\theta^{(j)}_k$表示第j轮迭代的，属于第k个聚类的参数，然后迭代优化：

EM算法步骤(针对GMM):

1. E步：利用上一轮的旧参数，计算每个样本 $\mathbf{x}_j$ 属于每个聚类的后验概率（责任度）：

   $$P(m|\mathbf{x_t},\theta^{(i)}) = \frac{a_m^{(i)} \mathcal{N}(\mathbf{x}_t | \theta_m^{(i)})}{\sum_{j=1}^M a_j^{(i)} \mathcal{N}(\mathbf{x}_t | \theta_j^{(i)})}$$

2. M步：根据责任度更新参数:

   • 更新混合系数 $a_m^{(i+1)}$：
   $$a_m^{(i+1)} = \frac{1}{n} \sum_{t=1}^n P(m|\mathbf{x}_t, \theta^{(i)})$$
   • 更新均值(各类中心) $\boldsymbol{\mu}_m^{(i+1)}$：
   $$\boldsymbol{\mu}_m^{(i+1)} = \frac{\sum_{t=1}^n P(m|\mathbf{x}_t, \theta^{(i)}) \mathbf{x}_t}{\sum_{t=1}^n P(m|\mathbf{x}_t, \theta^{(i)})}$$
   • 更新协方差矩阵 $\Sigma_m^{(i+1)}$：
   $$\Sigma_m^{(i+1)} = \frac{\sum_{t=1}^n P(m|\mathbf{x}_t, \theta^{(i)}) (\mathbf{x}_t - \boldsymbol{\mu}_m^{(i+1)})(\mathbf{x}_t - \boldsymbol{\mu}_m^{(i+1)})^T}{\sum_{t=1}^n P(m|\mathbf{x}_t, \theta^{(i)})}$$

可以把 K-means 看作是 GMM + EM 的一个极端特例：