1 概述和性能度量
聚类：没有标记，是无监督学习
将数据集中的样本划分为若干个通常是不相交的子集，每个子集成为一个簇（Cluster）
即：样本 D=\{x_1,...,x_m\}\Rightarrow k 个不相交簇 \{C_1,...,C_k\}
用 \lambda_j\in \text{range}(1,k)，表示样本 x_j 被分到了哪个簇（簇标记），即 x_j\in C_{\lambda_j}
聚类结果可用簇标记向量 \lambda=(\lambda_1;...;\lambda_m) 来表示
性能度量
聚类性能度量，亦称聚类 “有效性指标”，用来评估聚类好坏
我们希望簇内相似度高、簇间相似度低
聚类性能度量大致有两种
- 将结果与某个 “参考模型” 进行比较 —— 外部指标
- 直接考察聚类结果 —— 内部指标
外部指标
假设我们的聚类做到了：样本 D=\{x_1,...,x_m\}\Rightarrow k 个不相交簇 \mathcal{C}=\{C_1,...,C_k\}
参考模型给出来的划分是 \mathcal{C}^*=\{C^*_1,...,C_k^*\}
令 \lambda 和 \lambda^* 分别表示两种聚类的簇标记向量
将样本两两配对：
- SS=\{(x_i,x_j)|\lambda_i=\lambda_j,\lambda_i^*=\lambda_j^*,i<j\}，a=|SS|
- SD=\{(x_i,x_j)|\lambda_i=\lambda_j,\lambda_i^*\not=\lambda_j^*,i<j\}，b=|SD|
- DS=\{(x_i,x_j)|\lambda_i\not=\lambda_j,\lambda_i^*=\lambda_j^*,i<j\}，c=|DS|
- DD=\{(x_i,x_j)|\lambda_i\not=\lambda_j,\lambda_i^*\not=\lambda_j^*,i<j\}，d=|DD|
有一些常用的外部指标，值均在 [0,1] 内，值越大越好
- Jaccard 系数，\displaystyle JC=\frac{a}{a+b+c}
- FM 指数，\displaystyle FMI=\sqrt{\frac{a}{a+b}·\frac{a}{a+c}}
- Rand 指数，RI=\displaystyle\frac{a+d}{\text{C}_m^2}
内部指标
对于某个簇 C：
- avg(C)=\displaystyle\frac{1}{\text{C}_{|C|}^2}\sum_{1\le i<j\le |C|} dist(x_i,x_j)，即簇内样本的平均距离
- diam(C)=\displaystyle \max_{1\le i<j\le |C|}dist(x_i,x_j)，即簇内样本的最远距离
对于两个簇 C_i,C_j：
- d_\min(C_i,C_j)=\displaystyle\min_{x_i\in C_i,x_j\in C_j}dist(x_i,x_j)，即两个簇间样本最近距离
- d_{cen}(C_i,C_j)=dist(\mu_i,\mu_j)，这里 \mu_i=\displaystyle\frac{1}{|C_i|}\sum_{x\in C_i}x，即两个簇中心点的距离
基于上面的定义，有如下常用内部指标：
- DB 指数，DBI=\displaystyle\frac{1}{k}\sum_{i=1}^k\max_{j\neq i}\left[\frac{avg(i)+avg(j)}{d_{cen}(i,j)}\right]，值越小越好
对每一个簇 i 计算与其他类的最大相似度值，也就是取出最差结果，然后对所有类的最大相似度取均值
- Dunn 指数，DI=\displaystyle\min_{1\le i\le k}\left\{\min_{j\neq i}\left(\frac{d_\min(i,j)}{\max_{1\le l\le k}diam(l)}\right)\right\}，值越大越好