聚类的有效性指标

聚类

---

聚类性能度量大致有两类. 一类是将聚类结果与某个"参考模型" (reference model)进行比较，称为"外部指标" (external index); 另一类是直接考察聚类结果而不利用任何参考模型，称为"内部指标" (internal index)

外部指标

对数据集$D =\{x_1 , x_2 ,...， x _m\}$，假定通过聚类给出的簇划分为$C = \{C_1 , C_2 ， … ， C_k\}$， 参考模型给出的簇划分为$C^* = \{C_1^* , C_2^*, … ， C_k^*\}$. 相应地，令$\lambda$与$\lambda ^*$ 分别表示与$C$ 和$C^*$对应的簇标记向量.我们将样本两两配对考虑，定义

$$a= |SS|, SS = \{(x_i, x_j)| \lambda _i = \lambda_j , \lambda _i ^* = \lambda_j ^*, i< j \}$$

$$b= |SD|, SD = \{(x_i, x_j)| \lambda _i = \lambda_j , \lambda _i ^* \neq \lambda_j ^*, i< j \}$$

$$c= |DS|, DS = \{(x_i, x_j)| \lambda _i \neq \lambda_j , \lambda _i ^* = \lambda_j ^*, i< j \}$$

$$d= |DD|, DD = \{(x_i, x_j)| \lambda _i \neq \lambda_j , \lambda _i ^* \neq\lambda_j ^*, i< j \}$$

其中集合$SS$包含了在$C$ 中隶属于相同簇且在$C^*$中也隶属于相同簇的样本对，因为每个样本对仅能出现在一个集合中，因此有

$$a+b+c+d = m(m-1)/2$$

Jaccard系数(Jaccard Cofficient,JC)

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

FM 指数(Fowlkes and Mallows lndex，FMI)

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

Rand 指数(Rand Index，简称RI)

$$RI = \frac{a+d}{a+b+c+d} = \frac{TP+TN}{TP+FP+FN+TN}$$
其中TP是指被聚在一类的两个文档被正确分类了，TN是只不应该被聚在一类的两个文档被正确分开了，FP只不应该放在一类的文档被错误的放在了一类，FN只不应该分开的文档被错误的分开了

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

纯度purity

正确聚类的比例。有点准确率(Accuracy)的意思。
purity方法的优势是方便计算，值在0～1之间，完全错误的聚类方法值为0，完全正确的方法值为1。同时，purity方法的缺点也很明显它无法对退化的聚类方法给出正确的评价，设想如果聚类算法把每篇文档单独聚成一类，那么算法认为所有文档都被正确分类，那么purity值为1！而这显然不是想要的结果。

熵 entropy

一个聚类的熵可以表示为

$$e_i = - \sum _{j = 1}^L P_{ij} log_2 P_{ij}$$

其中L是类的个数，可能不等于聚类数，$P_{ij}$是聚类 i中的成员（member）属于类（class）j 的概率

整个聚类的信息熵可以表示为

$$e = \sum _{i=1} ^K \frac{m_i}{m}e_i$$

其中$m_i$表示在聚类i中所有成员的个数，m是整个聚类的总数。

参考文献是第二个链接。提供了Python代码。

互信息

互信息（Normalized Mutual Information）是用来衡量两个数据分布的吻合程度。也是一有用的信息度量，它是指两个事件集合之间的相关性。互信息越大，词条和类别的相关程度也越大。得到词条和类别之间的相关程度后，选取一定比例的，排名靠前的词条作为最能代表此种类别的特征。

参考链接是第三个，链接上有代码。链接表示dengcai的NMI计算可能存在问题。

Adjusted Rand Index (ARI)

衡量两个划分之间的一致性，一般其中一种划分固定为真实划分。$ARI =1$表示完全一致的划分，$ARI=0$表示完全不一致的划分。

MATLAB代码

function adjrand = adjrandindex(u,v)
%function adjrand=adjrand(u,v)
%
% Computes the adjusted Rand index to assess the quality of a clustering.
% Perfectly random clustering returns the minimum score of 0, perfect
% clustering returns the maximum score of 1.
%
%INPUTS
% u = the labeling as predicted by a clustering algorithm
% v = the true labeling
%
%OUTPUTS
% adjrand = the adjusted Rand index
%
%Author: Tijl De Bie, february 2003.
n=length(u);
ku=max(u);
kv=max(v);
m=zeros(ku,kv);
for i=1:n
    m(u(i),v(i))=m(u(i),v(i))+1;
end
mu=sum(m,2);
mv=sum(m,1);
a=0;
for i=1:ku
    for j=1:kv
        if m(i,j)>1
            a=a+nchoosek(m(i,j),2);
        end
    end
end
b1=0;
b2=0;
for i=1:ku
    if mu(i)>1
        b1=b1+nchoosek(mu(i),2);
    end
end
for i=1:kv
    if mv(i)>1
        b2=b2+nchoosek(mv(i),2);
    end
end
c=nchoosek(n,2);
adjrand=(a-b1*b2/c)/(0.5*(b1+b2)-b1*b2/c);

F-measure

$F = \frac{2·Precision · Recall}{Precision+Recall}$

Probabilistic Rand Index (PRI)

比较和真实划分之间的一致性，越大越好。

内部指标

考虑聚类结果的簇划分为$C = \{C_1 ,C_2 ， … ， C_k\}$,

$$avg(C)= \frac{2}{|C|(|C|-1)}\sum _{1 \leq i < j \leq|C|} dist(x_i,x_j)$$

$$diam(C)= max_{1 \leq i < j \leq|C|} dist(x_i,x_j)$$

$$d_{min}(C_i, C_j)= 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$ 代表簇$C$的中心点，$avg(C)$对应于簇$C$样本间的平均距离， $diam(C)$ 对应于簇C 内样本间的最远距离， $d_ {min}(C_i, C_j)$ 对应于簇$C_i$与簇$C_j$ 最近样本间的距离， $dcen(C_i ， C_j )$ 对应于簇$C_i$ 与簇$C_j$中心点间的距离.

DB 指数(Davies-Bouldin Index，简称DBI)

衡量同一簇中数据的紧密性,WikiPedia有比较详细的说明

$$DBI＝　\frac{1}{k} \sum _{i = 1} ^k max _{j \neq i}(\frac{avg(C_i)+avg(C_j)}{d_{cen}(\mu _i , \mu _j)})$$

Dunn 指数(Dunn Index 简称DI)

$$DI = min _{1\leq i \leq k}\{min_{j \neq i}(\frac{d_{min}(C_i, C_j)}{max_{1\leq l \leq k} diam(C_l)})\}$$

DBI越小越好， DI越大越好。网络上提供了相应的[工具箱]中有可供调用的函数。(http://www.cis.hut.fi/projects/somtoolbox/download/)。

function [DB, Dunn] = valid_DbDunn(cintra, cinter, k)
% Davies-Bouldin index
  R = zeros(k);
  dbs=zeros(1,k);
  for i = 1:k
    for j = i+1:k
      if cinter(i,j) == 0 
         R(i,j) = 0;
      else
         R(i,j) = (cintra(i) + cintra(j))/cinter(i,j);
      end
    end
    dbs(i) = max(R(i,:));
  end
  DB = mean(dbs(1:k-1));
  % Dunn index
  dbs = max(cintra);
  R = cinter/dbs;
  for i = 1:k-1
     S = R(i,i+1:k);
     dbs(i) = min(S);
  end
  Dunn = min(dbs); 

Silouette

衡量同一簇中数据的紧密性。越大越好。
Matlab中提供了这个函数的调用。S= silhouette(X, CLUST)其中X表示$N \times M$的数据，CLUST是类别，S是$N \times 1$的silhouette向量。

Modurity

衡量模块性，越大越好。Modularity-based model selection for kernel spectral clustering有相关说明。

$$Q={1 \over 2m}\sum_{ij}(S_{ij}-F_{ij})\delta_{ij}$$

matlab代码

function Q = modularity(W,clu)
% Calculate the modularity function Q of a clustering result.
% 
% modularity(W,clu) calculates the modularity of a clustering result
% represented by vector clu on the graph with adjacency matrix W.
% 
% Author: Kevin Xu
% add wyx 
% Q = 1/ 2m sum(S_ij -(d_i d_j)/2m) delta_ij
% sum_all_edges = 2m
k = max(clu);
Q = 0;
sum_all_edges = full(sum(sum(W)));
for clust = 1:k
    clu_nodes = (clu == clust);
    assoc = full(sum(sum(W(clu_nodes,clu_nodes))));
    deg = full(sum(sum(W(clu_nodes,:))));
    Q = Q + assoc/sum_all_edges - (deg/sum_all_edges)^2;
end

conductance

cond = cutcond(A,s) returns the sum of degrees of vertices in A

参考文献

• 机器学习[M]. 清华大学出版社, 2016.
• http://blog.csdn.net/vernice/article/details/46467449
• http://www.cnblogs.com/ziqiao/archive/2011/12/13/2286273.html
+