外部评价法

        外部评价方法意味着评判聚类算法的结果是基于一种预先指定的结构。这种结构反映了人们对数据集聚类结构的直观认识。每个数据项的分类标记已知。下面介绍两种常用的两种

 F-measure

它组合了信息检索中查准率( precision) 与查全率( recall) 的思想来进行聚类评价。一个聚类j 及与此相关的分类i 的precision 与recall 定义为
\[P = precision( i, j) = N_{ij} /N_{i}\]
\[R = recall( i, j) = N_{ij} /N_j \]
其中: \(N_{ij}\)是在聚类j 中分类i 的数目;\( N_j\)是聚类j 中所有对象的数目; \( N_i\) 是分类i 中所有对象的数目。分类i 的F-measure 定义为
\[F( i) = \frac{2PR}{( P + R) }\]
对分类i 而言, 哪个聚类的F-measure 值高, 就认为该聚类代表分类i 的映射。换句话说, F-measure 可看成分类i 的评判分值。对聚类结果来说, 其总F-measure 可由每个分类i 的F-measure加权平均得到:
\[ F=\frac{\sum_i{|i| \cdot F(i)}}{\sum_i{|i|}} \]
其中: |i|为分类i 中所有对象的数目。

Rand 指数( index) 和Jaccard 系数( coefficient)

设数据集X 的一个聚类结构为C ={C1 , C2 , ⋯, Cm} , 数据集已知的划分为P ={ P1 , P2 , ⋯, Ps } , 可通过比较C 和P 以及邻近矩阵与P 来评价聚类的质量。对数据集中任一对点( Xv, Xu) 计算下列项 :

SS———如果两个点属于C 中同一簇, 且P 中同一组;
SD———如果两个点属于C 中同一簇, 但P 中不同组;
DS———如果两个点不属于C 中同一簇, 而P 中属同一组;
DD———如果两个点不属于C 中同一簇, 且P 中不同组。

设a、b、c、d 分别表示SS、SD、DS、DD 的数目, 则\(a +b + c +d=M\)为数据集中所有对的最大数, 即\(M=N( N- 1) /2\)。其中:N为数据集中点的总数。C 与P 之间的相似程度可由如下有效性指数定义:
Rand 指数 \[R = ( a + d) /M \]
Jaccard 系数\[ J = a/( a + b + c) \]
上述两指数取值均为[ 0, 1] 。当m = s 时, 有最大值。其余指数定义以及邻近矩阵与划分P 的比较方法可以参考文献 。

内部评价法

内部评价方法是利用数据集的固有特征和量值来评价一个聚类算法的结果, 数据集的结构未知 。

Cophenetic 相关系数

对层次聚类算法来说, 其产生的层次图可用Cophenetic 矩阵Pc表示, 矩阵中元素Pc ( i, j 表示数据xi和xj首次在同一个簇中出现的邻近层, 则可以定义一个Cophenetic 相关系数来度量Pc与邻近矩阵P 的相似程度:

\[ CPCC =\frac{ 1}{ \sqrt{ \frac{ 1}{M}\sum^{N- 1}_{i =1}{\sum^{N}_{j= i +1}{d_{ij}^2- \mu^2_p  }}}}\cdot \frac{\frac{1}{M} \sum^{N- 1}_{i = 1}{\sum^N_{j= i +1}{d_{ij} c_{ij} – \mu_P \mu_C}}}{\sqrt{  \frac{ 1}{M} \sum^{N- 1}_{i = 1} {\sum^N_{j= i +1}{c^2_{ij} – \mu^2_C}}}}\] \[ – 1≤ CPCC≤1 \]
其中: \(M= N( N- 1) /2\); N为数据集中点的总数; μP 和μc 分别是矩阵Pc 与P 的均值; dij 和cij分别是矩阵Pc 与P 中元素( i,j) 。CPCC 的取值为[ – 1, 1] , 其接近于0 时说明两个矩阵具有较大的相似性。

Huberts  \(\Gamma\)统计

对包含k 个簇的单个聚类结果C, 其质量评价可通过比较C 与邻近矩阵P 之间的一致性程度进行。这个方法定义的指数为Huberts \(\Gamma\)统计。

\[\Gamma= \frac{ 1}{M}\sum^{N- 1}_{i =1}{\sum^N_{j =i + 1}{X( i, j) Y( i, j) }}\]
其中: X 为数据集矩阵; 矩阵Y 定义为

\[ Y( i, j) =\begin{cases} 1, & \mbox{if }  x_i \mbox{ and } x_j \mbox{ belong to different clusters; }i, j =1, …, N \\0 , & \mbox{otherwise}\end{cases} \]
\(\Gamma\)的值越大, 表明X 与Y 之间的相似性越大。