聚类之性能度量详解

概念简述

聚类是什么呢？我们都听说过“物以类聚”，即把“志同道合”的 数据分到一起归为一类，不同类之间在”志向“上具有较大分歧。举个栗子，茫茫人生中，我们普通大众会被God根据缘分进行聚类，缘分好的话，会成为朋友，甚至成为了可以互诉衷肠，”余生请指教“的男女盘友，那缘分不好的应该是一生从未谋面或者一面之缘或者是如《再见前任3》中那样成为了最熟悉的陌生人…好像扯远了。
言归正传，用标准的普通话来说，聚类是将数据集中的样本划分为若干个通常是不相交的子集，每个子集成为一个“簇”，用正规的外星人语言来说，对于样本D={x1,x2,...,xm}$D=\left\{x_1,x_2,...,x_m\right\}$包含m$m$个无标记样本，每个样本xi={xi1;xi2;...;xin}$x_i=\left\{x_{i1};x_{i2};...;x_{in}\right\}$是一个n$n$维特征向量，则聚类算法将样本集D$D$划分为k$k$个不相交的簇{Cl|l=1,2,...,k}$\left\{C_l|l=1,2,...,k\right\}$，其中Cl′∩l′≠lCl=∅$C_{l^{{}^{\prime }}}{\cap }_{l^{{}^{\prime }}\ne l}{C}_l=\varnothing$且D=∪kl=1Cl$D={\cup }_{l=1}^k{C}_l$，相应地，用λj∈{1,2,...,k}${\lambda }_j\in \left\{1,2,...,k\right\}$表示样本xj$x_j$的“簇标记”，即xj∈Cλj$x_j\in C_{{\lambda }_j}$。于是聚类的结果可用包含m个元素的簇标记，记向量λ=(λ1;λ2;...;λm)$\lambda =\left({\lambda }_1;{\lambda }_2;...;{\lambda }_m\right)$。举个栗子，对于具有10$10$个样本的数据集D$D$，其中每个样本xi$x_i$含有2$2$维特征，分成2$2$类的结果如下：

聚类通常用来对无标记训练样本的学习来揭示数据内在性质及规律，为进一步的数据分析提供基础，是“无监督学习”中应用最广的研究方法。那么问题来了，如何衡量聚类结果的好坏呢？按照什么样的“缘分”分类呢？官方的话来说聚类有哪些性能度量以及距离计算方法。

性能度量

我们通常按照一个标准来分析聚类之后的结果，简单来说这个标准是“簇内相似度高，簇间相似度低”，下面我们用一堆“指数”，“系数”来数学化引号里面的内容，权当填补那些好奇心强盛的孩纸们…

性能度量分类：

聚类性能度量的主要分为两类，一类是将聚类结果与某个“参考模型”进行比较，成为“外部指标”；另一类是直接考察聚类结果而不用任何参考模型，成为“内部指标”。

1. 外部指标

“外部指标”通常有Jaccard系数(Jaccard Coefficient，简称JC)、FM系数(Fowlkes and Mallows Index，简称FMI)、Rand指数(Rand Index，简称RI)。

• JC:
  
  JC=aa+b+c(1.1)$$\begin{array}{}\text{(1.1)}& \mathrm{J}\mathrm{C}=\frac{a}{a+b+c}\end{array}$$
• FMI:
  
  FMI=aa+b⋅aa+c−−−−−−−−−−−√(1.2)$$\begin{array}{}\text{(1.2)}& \mathrm{F}\mathrm{M}\mathrm{I}=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}}\end{array}$$
• RI
  
  RI=2(a+d))m(m−1)(1.3)$$\begin{array}{}\text{(1.3)}& \text{RI}=\frac{2(a+d))}{m(m-1)}\end{array}$$
  
  假设，数据集D={x1,x2,...,xm}$D=\left\{x_1,x_2,...,x_m\right\}$，经过聚类后得到的簇划分为C={C1,C2,...,Cs}$C=\left\{C_1,C_2,...,C_s\right\}$，参考模型给出的簇划分C∗={C∗1,C∗2,...,C∗s}$C^{\ast }=\left\{C_1^{\ast },C_2^{\ast },...,C_s^{\ast }\right\}$，相应的，令λ$\lambda$和λ∗${\lambda }^{\ast }$分别表示与C$C$和C∗$C^{\ast }$对应的簇标记向量，于是a、b、c、d$a、b、c、d$定义如下：
  
  a=|SS|,SS={(xi,xj)|λi=λj,λ∗i=λ∗j,i<j}(1.4)$$\begin{array}{}\text{(1.4)}& a=\left|SS\right|,SS=\left\{(x_i,x_j)|{\lambda }_i={\lambda }_j,{\lambda }_i^{\ast }={\lambda }_j^{\ast },i<j\right\}\end{array}$$
  
  
  b=|SD|,SD={(xi,xj)|λi=λj,λ∗i≠λ∗j,i<j}(1.5)$$\begin{array}{}\text{(1.5)}& b=\left|SD\right|,SD=\left\{(x_i,x_j)|{\lambda }_i={\lambda }_j,{\lambda }_i^{\ast }\ne {\lambda }_j^{\ast },i<j\right\}\end{array}$$
  
  
  c=|DS|,DS={(xi,xj)|λi≠λj,λ∗i=λ∗j,i<j}(1.6)$$\begin{array}{}\text{(1.6)}& c=\left|DS\right|,DS=\left\{(x_i,x_j)|{\lambda }_i\ne {\lambda }_j,{\lambda }_i^{\ast }={\lambda }_j^{\ast },i<j\right\}\end{array}$$
  
  
  d=|DD|,DD={(xi,xj)|λi≠λj,λ∗i≠λ∗j,i<j}(1.7)$$\begin{array}{}\text{(1.7)}& d=\left|DD\right|,DD=\left\{(x_i,x_j)|{\lambda }_i\ne {\lambda }_j,{\lambda }_i^{\ast }\ne {\lambda }_j^{\ast },i<j\right\}\end{array}$$
  
  从上述表达式可知，集合SS$SS$包含了在C$C$中隶属于相同簇且在C∗$C^{\ast }$中也隶属于相同簇的样本对，集合SD$SD$包含了在C$C$中隶属于相同簇但在C∗$C^{\ast }$中隶属于不同簇的样本，集合DS$DS$包含了在C$C$中隶属于不同簇但在C∗$C^{\ast }$中隶属于相同簇的样本，集合DD$DD$包含了在C$C$中隶属于不同簇且在C∗$C^{\ast }$中隶属不同簇的样本，由于每个样本对(xi,xj)(i<j)$\left(x_i,x_j\right)(i<j)$仅能出现在一个集合中，因此有a+b+c+d=m(m−1)/2$a+b+c+d=m(m-1)/2$成立。显然，上述性能度量的结果值均在[0,1]$\left[0,1\right]$区间，值越大越好。
  2.内部指标
  常用的内部指标有DB指数(Davies-Bouldin Index，简称DBI)和Dunn指数(Dunn Index，简称DI)。
  
  • DB:
    
    DBI=1k∑i=1kmaxj≠i(avg(Ci)+avg(Cj)dcen(μi,μj))(2.1)$$\begin{array}{}\text{(2.1)}& \mathrm{D}\mathrm{B}\mathrm{I}=\frac{1}{k}\sum _{i=1}^{k}ma{x}_{j\ne i}\left(\frac{avg\left(C_i\right)+avg\left(C_j\right)}{d_{cen}\left({\mu }_i,{\mu }_j\right)}\right)\end{array}$$
  • DI:
    
    DI=min1≤i≤k{minj≠i(dmin(Ci,Cj)max1≤l≤kdiam(Cl))}(2.2)$$\begin{array}{}\text{(2.2)}& \mathrm{D}\mathrm{I}=mi{n}_{1\le i\le k}\left\{mi{n}_{j\ne i}\left(\frac{d_{min}\left(C_i,C_j\right)}{ma{x}_{1\le l\le k}diam\left(C_l\right)}\right)\right\}\end{array}$$
    
    其中：
    
    avg(C)=2|C|(|C|−1)∑1≤i<j≤|C|dist(xi,xj)(2.3)$$\begin{array}{}\text{(2.3)}& avg\left(C\right)=\frac{2}{\left|C\right|\left(\left|C\right|-1\right)}\sum _{1\le i<j\le \left|C\right|}dist\left(x_i,x_j\right)\end{array}$$
    
    
    diam(C)=maxx1≤i<j≤|C|dist(xi,xj)(2.4)$$\begin{array}{}\text{(2.4)}& diam\left(C\right)=ma{x}_{x_1\le i<j\le \left|C\right|}dist\left(x_i,x_j\right)\end{array}$$
    
    
    dmin(Ci,Cj)=minxi∈Ci,xj∈Cjdist(xi,xj)(2.5)$$\begin{array}{}\text{(2.5)}& d_{min}\left(C_i,C_j\right)=mi{n}_{x_i\in C_i,x_j\in C_j}dist\left(x_i,x_j\right)\end{array}$$
    
    
    dcen(Ci,Cj)=dist(μi,μj)(2.6)$$\begin{array}{}\text{(2.6)}& d_{cen}\left(C_i,C_j\right)=dist\left({\mu }_i,{\mu }_j\right)\end{array}$$
    
    注意：dist(⋅,⋅)$dist\left(\cdot ,\cdot \right)$用于计算两个样本之间的距离；μ$\mu$代表簇C$C$的中心点μ=1|C|∑1≤i≤|C|xi$\mu =\frac{1}{\left|C\right|}\sum _{1\le i\le \left|C\right|}{x}_i$，avg(C)$avg(C)$对应于簇C$C$内样本间的平均距离，diam(C)$diam(C)$对应于簇内最远距离，dmin(Ci,Cj)$d_{min}(C_i,C_j)$代表簇Ci$C_i$与簇Cj$C_j$内最近样本间的距离，dcen(Ci,Cj)$d_{cen}\left(C_i,C_j\right)$代表簇Ci$C_i$与簇Cj$C_j$中心点的距离。显然DBI$\mathrm{D}\mathrm{B}\mathrm{I}$的值越小越好，而DI$\mathrm{D}\mathrm{I}$则相反，值越大越好。

更多机器学习干货、最新论文解读、AI资讯热点等欢迎关注”AI学院(FAICULTY)”
欢迎加入faiculty机器学习交流qq群：451429116 点此进群
版权声明：可以任意转载，转载时请务必标明文章原始出处和作者信息.

参考文献

[1]. 周志华，机器学习，清华大学出版社，2016