聚类（性能度量）

聚类（性能度量）

对数据集 D={x1,x2,...,xm}D=\{x_1,x_2,...,x_m\}D={x1​,x2​,...,xm​} ，假定通过聚类给出的簇划分为 C={C1,C2,...,Ck}C=\{C_1,C_2,...,C_k\}C={C1​,C2​,...,Ck​} ，参考模型给出的簇划分为 C∗={C1∗,C2∗,...,Cs∗}C^*=\{C_1^*,C_2^*,...,C_s^*\}C∗={C1∗​,C2∗​,...,Cs∗​} ，相应的，令 $\lambda$ 与 ${\lambda }^{\ast }$ 分别表示与 $C$ 和 $C^{\ast }$ 对应的簇标记向量。我们将样本两两配对考虑，定义：
$$\begin{gathered} a=|SS|,SS=\{(x_i,x_j)|{\lambda }_i={\lambda }_j,{\lambda }_i^{\ast }={\lambda }_j^{\ast },i<j\} \\ b=|SD|,SS=\{(x_i,x_j)|{\lambda }_i={\lambda }_j,{\lambda }_i^{\ast }\ne {\lambda }_j^{\ast },i<j\} \\ c=|DS|,SS=\{(x_i,x_j)|{\lambda }_i\ne {\lambda }_j,{\lambda }_i^{\ast }={\lambda }_j^{\ast },i<j\} \\ d=|DD|,SS=\{(x_i,x_j)|{\lambda }_i\ne {\lambda }_j,{\lambda }_i^{\ast }\ne {\lambda }_j^{\ast },i<j\} \end{gathered}$$

其中，集合 $SS$ 包含了在 $C$ 中隶属于相同簇且在 $C^{\ast }$ 中也隶属于相同簇的样本对，…

由于每个样本对 $(x_i,x_j)(i<j)$ 仅能出现在一个集合中，因此有下列式子成立：
$$a+b+c+d=\frac{m(m-1)}{2}$$

外部指标

基于以上式子可导出下面这些常用的聚类性能度量外部指标：

• Jaccard系数（Jaccard Coefficient，简称 JC）

$$JC=\frac{a}{a+b+c}$$

• FM指数（Fowlkes and Mallows Index，简称 FMI）

$$FMI=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}}$$

• Rand指数（Rand Index，简称 RI）

$$RI=\frac{a(a+d)}{m(m-1)}$$

显然，上述性能度量的结果值均在 $[0,1]$ 区间，值越大越好。

例1

聚类 $C$	参考 $C^{\ast }$
$C_1:x_1,x_2,x_3$	$C_1^{\ast }:x_1,x_2,x_4$
$C_2:x_4,x_5$	$C_2^{\ast }:x_3,x_5$

$$\begin{array}{rl}a& =|SS|=1(x_1,x_2)\\ b& =|SD|=3(x_1,x_3),(x_2,x_3),(x_4,x_5)\\ c& =|DS|=3(x_1,x_4),(x_2,x_4),(x_3,x_5)\\ d& =|DD|=3(x_1,x_5),(x_2,x_5),(x_3,x_4)\end{array}$$

$$\begin{array}{rl}JC& =\frac{a}{a+b+c}=\frac{1}{1+3+3}=\frac{1}{7}\\ FMI& =\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}}=\sqrt{\frac{1}{1+3}\cdot \frac{1}{1+3}}=\frac{1}{4}\\ RI& =\frac{a(a+d)}{m(m-1)}=RI=\frac{2(1+3)}{5(5-1)}=\frac{2}{5}\end{array}$$

内部指标

考虑聚类结果的簇划分为 C={C1,C2,...,Ck}C = \{C_1,C_2,...,C_k\}C={C1​,C2​,...,Ck​} ，定义
$$avg(C)=\frac{2}{|C|(|C|-1)}\sum _{1\le i<j\le |C|}dist(x_i,x_j)$$

其中，$avg(C)$ 对应于簇 $C$ 内样本间的平均距离，$dist(\cdot ,\cdot )$ 用于计算两个样本之间的距离。

$$diam(C)=ma{x}_{1\le i<j\le |C|}dist(x_i,x_j)$$

$diam(C)$ 对应于簇 $C$ 内样本间的最远距离。

$$d_{min}(C_i,C_j)=mi{n}_{x_i\in C_i,x_j\in C_j}dist(x_i,x_j)$$

$d_{min}(C_i,C_j)$ 对应于簇 $C_i$ 和簇 $C_j$ 最近样本间的距离。

$$d_{cen}(C_i,C_j)=dist({\mu }_i,{\mu }_j)$$

$d_{cen}(C_i,C_j)$ 对应于簇 $C_i$ 和簇 $C_j$ 中心点间的距离，$\mu$ 代表簇 $C$ 的中心点 $\mu =\frac{1}{|C|}{\sum }_{1\le i\le |C|}{x}_i$ 。

基于以上式子可导出下面这些常用的聚类性能度量内部指标：

• DB指数（Davies-Bouldin Index，简称 DBI）

$$DBI=\frac{1}{k}\sum _{i=1}^k\underset{j\ne i}{\max }(\frac{avg(C_i)+avg(C_j)}{d_{cen}(C_i,C_j)})$$

• Dunn指数（Dunn Index，简称DI）

$$DI=\underset{1\le i\le k}{\min }\underset{j\ne i}{\min }(\frac{d_{min}(C_i,C_j)}{ma{x}_{1\le l\le k}diam(C_l)})$$

显然，$DBI$ 的值越小越好，而 $DI$ 则相反，值越大越好。

例2

$$\begin{array}{rl}avg(C_1)& =\frac{2}{3(3-1)}\cdot (|x_1-x_2|+|x_1-x_3|+|x_2-x_3|)\\ avg(C_2)& =\frac{2}{2(2-1)}\cdot (|x_4-x_5|)\\ avg(C_3)& =\frac{2}{2(2-1)}\cdot (|x_6-x_7|)\end{array}$$

$$\begin{gathered} diam(C_1)=|x_1-x_3| \\ diam(C_2)=|x_4-x_5| \\ diam(C_3)=|x_6-x_7| \end{gathered}$$

$$\begin{gathered} d_{min}(C_1,C_2)=|x_3-x_4| \\ {d}_{min}(C_2,C_3)=|x_5-x_6| \\ {d}_{min}(C_1,C_3)=|x_3-x_6| \end{gathered}$$

$${\mu }_1=\frac{x_1+x_2+x_3}{3}{\mu }_2=\frac{x_4+x_5}{2}{\mu }_3=\frac{x_6+x_7}{2}$$

$$\begin{gathered} d_{cen}(C_1,C_2)=|{\mu }_1-{\mu }_2| \\ {d}_{cen}(C_2,C_3)=|{\mu }_2-{\mu }_3| \\ {d}_{cen}(C_1,C_3)=|{\mu }_1-{\mu }_3| \end{gathered}$$