Skip to content

聚类

聚类任务

  • 目标：将数据样本划分为若干个通常不相交的“簇”(cluster)。即寻找数据内在的分布结构，也作为分类学习任务重提取特征判断类别的重要支撑
  • 不相交的簇=硬聚类；可相交的簇=软聚类

性能度量（有效性指标valid index）⭐

  • 基本想法：簇内相似度（intra-cluster）高，簇间相似度（inter-cluster）低
  • 外部指标：将聚类结果与某个"参考模型" (reference model) 进行比较
  • 内部指标：直接考察聚类结果而不利用任何参考模型

alt text

外部距离

  • Jaccard系数
\[ JC=\frac{a}{a+b+c} \]
  • FM指数
\[ FMI = \sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}} \]
  • Rand指数
\[ RI = \frac{2(a+d)}{m(m-1)} \]

上述性能度量结果在[0,1]区间，值越大越好

内部距离

alt text

  • DB指数（DBI）
\[ DBI = \frac{1}{k}\sum_{i=1}^k max_{j\neq i}(\frac{\text{avg}(C_i) + \text{avg}(C_j)}{d_{cen(\mu_i,\mu_j)}}) \]
  • Dunn指数（DI）
\[ DI=min_{1\leq i \leq k}\{min_{j\leq i}(\frac{d_{min}(C_i,C_j)}{\text{max}_{1\leq l \leq k}\text{diam}(C_l)})\} \]

DBI越小越好，DI越大越好

距离计算

“距离度量”需满足

  • 非负性
  • 同一性
  • 对称性
  • 三角不等式

Minkowski distance（\(L_p\)范数）：

\[ \text{dist}_{mk}(x_i,x_j)=(\sum_{u=1}^n|x_{iu}-x_{ju}|^p)^{\frac{1}{p}} \]

p=1时为Manhattan distance，p=2时为欧式距离

  • 无序属性(不能直接在属性值上计算距离)：采用VDM距离（Value Difference Metric）：

令 \(m_{u,a}\) 表示在属性u上取值为a的样本数，\(m_{u,a,i}\) 表示在第i个样本簇中在属性u上取值为a的样本数，k为样本簇数，则属性u上两个离散值a,b间的VDM距离为

\[ \text{VDM}_p(a,b) = \sum_{i=1}^k|\frac{m_{u,a,i}}{m_{u,a}} - \frac{m_{u,b,i}}{m_{u,b}}|^p \]

原型聚类（prototype-based clustering）

  • 此类算法假设聚类结构能通过一组原型刻画
  • 原型=簇中心，有簇中心的聚类方法

k均值聚类算法（K-means）

  1. 随机选k个样本点作为簇中心
  2. 将其他样本点根据其与簇中心的距离，划分给最近的簇
  3. 更新各簇的均值向量，将其作为新的簇中心

  4. 若所有簇中心未发生改变，则停止；否则执行 Step 2

  5. 随机选择的优化：k-means++

a. 随机选择第一个中心点。 b. 对于每个数据点，计算其与已选中心点的最短距离（即离已选中心点多远）。 c. 依据“距离越远，被选中的概率越大”的规则，随机选择下一个中心点。 d. 重复步骤b和c，直到选满K个中心点。

  • 如何确定K：
    1. 绘制不同K值对应的总类内距离和（WCSS，或称Inertia） 的曲线图。WCSS会随着K增大而减小。
    2. 判断：寻找曲线上的“拐点”或“肘部”，即WCSS下降速度突然变缓的点，该点对应的K值通常是一个好选择。

学习向量量化

学习向量量化" (Learning Vector Quantization，简LVQ) 也是试图找到一组原型向量来刻画聚类结构，但与一般聚类算法不同的是， LVQ 假设数据样本带有类别标记，学习过程利用样本的这些监督信息辅助聚类

高斯混合聚类⭐

  • 思想：采用高斯概率分布来表达聚类原型，簇中心=均值，簇半径=方差

高斯分布函数：

\[ p(x)=\frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}} e^{-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)} \]

假设样本由下面高斯混合分布函数生成：

\[ p_M(x) = \sum_{i=1}^k\alpha_i p(x|\mu_i,\Sigma_i) \]
  • 首先根据 \(\alpha_1,\alpha_2,\dots,\alpha_k\) 定义的先验分布选择高斯混合成分，其中 \(\alpha_i\) 为选择第i个混合成分的概率
  • 然后根据被选择的混合成分的概率密度函数进行采样，从而生成相应的样本

样本 \(x_j\) 由第i个高斯混合成分生成的后验概率为：

\[ p_M(z_j = i|x_j) = \frac{P(z_j=i)\dot p_M(x_j|z_j=i)}{p_M(x_j)} = \frac{\alpha_i\dot p(x_j|\mu_i,\Sigma_i)}{\sum_{l=1}^{k}\dot \alpha_l p(x_j|\mu_l,\Sigma_l)} \]

记为 \(\gamma_{ji}(i=1,2,\dots,k)\)

参数 \(\{(\alpha_i,\mu_i,\Sigma_i)|1 \leq i \leq k\}\) 估计可采用极大似然法，考虑极大化对数似然

\[ LL(D)=\text{ln}(\Pi_{j=1}^m p_M(x_j)) = \sum_{j=1}^{m}\text{ln}(\sum_{i=1}^k\alpha_i \dot p(x_j|\mu_i,\Sigma_i)) \]

由 \(\frac{\partial LL(D)}{\partial \mu_i}=0\)，

\[ \mu_i=\frac{\sum_{j=1}^m \gamma_{ji}x_j}{\sum_{j=1}^m\gamma_{ji}} \]

即各混合成分的均值可通过样本加权平均来估计，样本权重是每个样本属于该成分的后验概率

同理，

\[ \Sigma_i = \frac{\sum_{j=1}^m\gamma_{ji}(x_j-\mu_i)(x_j-\mu_i)^T}{\sum_{j=1}^m\gamma_{ji}} \]
\[ \alpha_i = \frac{1}{m}\sum_{j=1}^m\gamma_{ji} \]

即每个高斯成分的混合系数由样本属于该成分的平均后验概率确定

  • E步：根据当前参数计算每个样本属于每个高斯成分的后验概率 \(\gamma_{ji}\)
  • M步：更新模型参数\(\{(\alpha_i,\mu_i,\Sigma_i)|1 \leq i \leq k\}\)

guassian

思考：高斯->离散

  • 核心思想总结：假设数据是由K个不同的高斯分布“混合”生成的。每个高斯分布代表一个潜在的簇，它有自己的均值（中心点）和方差（形状）。聚类的任务是找出这K个分布，并判断每个数据点最可能来自哪一个分布。

密度聚类✍

  • 划成多个等价类，未必有簇中心
  • 假设：聚类结构能通过样本分布的紧密程度确定
  • 过程：从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇

DBSCAN

  • 通过邻域建立样本的可达路径，形成等价类（连通分支）

alt text

层次聚类（hierarchical clustering）

  • 聚类效果跟抽象的粒度有关，形成多层次聚类
  • 假设：能够产生不同粒度的聚类结果·
  • 过程：在不同层次对数据集进行划分，从而形成树形的聚类结构

AGNES

  • 从最细的粒度开始（一个样本一个簇），逐渐合并相似的簇，直到最粗的粒度（所有样本一个簇）

过程：

  1. 将每个样本点作为一个簇
  2. 合并最近的两个簇
  3. 若所有样本点都存在与一个簇中，则停止；否则转到 Step2

Comments