[关闭]
@hainingwyx 2017-06-15T15:39:04.000000Z 字数 4394 阅读 4392

聚类的有效性指标

聚类


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

外部指标

对数据集,假定通过聚类给出的簇划分为, 参考模型给出的簇划分为. 相应地,令 分别表示与对应的簇标记向量.我们将样本两两配对考虑,定义

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

Jaccard系数(Jaccard Cofficient,JC)

FM 指数(Fowlkes and Mallows lndex,FMI)

Rand 指数(Rand Index,简称RI)


其中TP是指被聚在一类的两个文档被正确分类了,TN是只不应该被聚在一类的两个文档被正确分开了,FP只不应该放在一类的文档被错误的放在了一类,FN只不应该分开的文档被错误的分开了

上述性能度量的结果值均在 区间,值越大越好.

纯度purity

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

熵 entropy

一个聚类的熵可以表示为

其中L是类的个数,可能不等于聚类数,是聚类 i中的成员(member)属于类(class)j 的概率

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

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

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

互信息

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

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

Adjusted Rand Index (ARI)

衡量两个划分之间的一致性,一般其中一种划分固定为真实划分。表示完全一致的划分,表示完全不一致的划分。

MATLAB代码

  1. function adjrand = adjrandindex(u,v)
  2. %function adjrand=adjrand(u,v)
  3. %
  4. % Computes the adjusted Rand index to assess the quality of a clustering.
  5. % Perfectly random clustering returns the minimum score of 0, perfect
  6. % clustering returns the maximum score of 1.
  7. %
  8. %INPUTS
  9. % u = the labeling as predicted by a clustering algorithm
  10. % v = the true labeling
  11. %
  12. %OUTPUTS
  13. % adjrand = the adjusted Rand index
  14. %
  15. %Author: Tijl De Bie, february 2003.
  16. n=length(u);
  17. ku=max(u);
  18. kv=max(v);
  19. m=zeros(ku,kv);
  20. for i=1:n
  21. m(u(i),v(i))=m(u(i),v(i))+1;
  22. end
  23. mu=sum(m,2);
  24. mv=sum(m,1);
  25. a=0;
  26. for i=1:ku
  27. for j=1:kv
  28. if m(i,j)>1
  29. a=a+nchoosek(m(i,j),2);
  30. end
  31. end
  32. end
  33. b1=0;
  34. b2=0;
  35. for i=1:ku
  36. if mu(i)>1
  37. b1=b1+nchoosek(mu(i),2);
  38. end
  39. end
  40. for i=1:kv
  41. if mv(i)>1
  42. b2=b2+nchoosek(mv(i),2);
  43. end
  44. end
  45. c=nchoosek(n,2);
  46. adjrand=(a-b1*b2/c)/(0.5*(b1+b2)-b1*b2/c);

F-measure

Probabilistic Rand Index (PRI)

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

内部指标

考虑聚类结果的簇划分为,

代表簇的中心点,对应于簇样本间的平均距离, 对应于簇C 内样本间的最远距离, 对应于簇与簇 最近样本间的距离, 对应于簇 与簇中心点间的距离.

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

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

 

Dunn 指数(Dunn Index 简称DI)

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

  1. function [DB, Dunn] = valid_DbDunn(cintra, cinter, k)
  2. % Davies-Bouldin index
  3. R = zeros(k);
  4. dbs=zeros(1,k);
  5. for i = 1:k
  6. for j = i+1:k
  7. if cinter(i,j) == 0
  8. R(i,j) = 0;
  9. else
  10. R(i,j) = (cintra(i) + cintra(j))/cinter(i,j);
  11. end
  12. end
  13. dbs(i) = max(R(i,:));
  14. end
  15. DB = mean(dbs(1:k-1));
  16. % Dunn index
  17. dbs = max(cintra);
  18. R = cinter/dbs;
  19. for i = 1:k-1
  20. S = R(i,i+1:k);
  21. dbs(i) = min(S);
  22. end
  23. Dunn = min(dbs);

Silouette

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

Modurity

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

matlab代码

  1. function Q = modularity(W,clu)
  2. % Calculate the modularity function Q of a clustering result.
  3. %
  4. % modularity(W,clu) calculates the modularity of a clustering result
  5. % represented by vector clu on the graph with adjacency matrix W.
  6. %
  7. % Author: Kevin Xu
  8. % add wyx
  9. % Q = 1/ 2m sum(S_ij -(d_i d_j)/2m) delta_ij
  10. % sum_all_edges = 2m
  11. k = max(clu);
  12. Q = 0;
  13. sum_all_edges = full(sum(sum(W)));
  14. for clust = 1:k
  15. clu_nodes = (clu == clust);
  16. assoc = full(sum(sum(W(clu_nodes,clu_nodes))));
  17. deg = full(sum(sum(W(clu_nodes,:))));
  18. Q = Q + assoc/sum_all_edges - (deg/sum_all_edges)^2;
  19. end

conductance

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

参考文献

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注