第6期 谢娟英，等：聚类有效性评价新指标 ·875· (4),其中的sensitivity和specificity同F-measure指 TP、FN、FP和TN也可根据表2所示的相依表计算 标在两类问题中的定义一致。由此可见，我们定义 得到。计算公式如式(6)所示。基于样本对的sensi- 的新指标S2适用于任意类的聚类问题。 tivity,specificity定义如式(7)所示，则基于样本对 表2聚类结果相依表 的新聚类评价指标PS2定义为式(8)。 Table 2 The contingency table of a clustering 表3聚类结果混淆矩阵 UIV V Ve SUM Table 3 Confusion matrix of a clustering U 聚类前/聚类后 T F 11 112 nle nik n TP FN Uz 21 122 ne n2K n2. ◇ FP TN TP=((x.)I(x)=I(x )L(x )L(x) Ue ncl ne nck ne FN={(x,x)Ilx）=Ix,L(x)≠L(x)川 (5) FP=I(x,x)Il(x)≠Ix,L(c)=L(x)川 Uc nCI nc. TN=x,x)Ilx)≠l(x),L(x)≠L(x)川 SUM n.I -2 ne n.K P=( TPe={il(x)=L(x)=c,1≤i≤nl=nc 2 FNe=HiHZ()=c}A{L(x)≠c,l≤i≤nl=ne-nc p (6) FP.=l{ill(x)≠cA{L(x)=ch,1≤i≤n‖=ne-n TNe=l{ill(x)≠c,L(x)≠c,1≤i≤n川=n-ne.-ne+ne m-2 -TP (1) TN=N-(TP+FN+FP) sensitivity= TP:=" TP TPe+FNe ne sensitivity TN。=n-n-ne+ne (2) TP+FN specificity=TN+FP. (7) TN n-ne. specificity=TN+FP 1 S2= 2xsensitivityXspecificity (3) 2×sensitivity×specificity min(C,K] PS2= sensitivity.specificity. sensitivity +specificity (8) S2= 2×sensitivity×specificity 2XTP×TN sensitivity+specificity (4) TP FP+TN)+TN(TP+FN) 外部评价指标中的Rand index、Adjusted rand index、Jaccard系数，AM等均是基于样本对的聚类 2内部指标 评价指标。因此，本文类似地提出基于样本对的聚 方差作为一种度量样本分布情况的概率统计 类结果外部评价指标PS2,调和聚类结果的正类识 量，通常用来描述样本的离散程度。样本方差越 别率和负类识别率，以评价聚类结果的有效性。 小，样本分布越密集，反之则越分散。方差的性质 任意两样本点x、x,若I(x)=1(x),且Lx)= 可以用于计算类内距离和类间距离，同一类簇中样 L(x,即聚类前后属于同一类，则称为正事件T;反 本分布越密集，方差越小，因此将同一类簇中样本 之，如果I(x)=1(x),但L(x,)≠L(x,),即聚类前属于 的方差作为类内距离，度量类簇内部的紧促性。 同类簇，但聚类后不属于同一类，称之为负事件F。 基于“类内尽可能紧密，类间尽可能分离”原则， 依据正负事件，可得表3所示混淆矩阵。其中，TP、 利用方差思想定义度量类内距离和类间距离测度， FN、FP和TN分别表示聚类前后都在同一类簇的 类间距离越大越好，类内距离越小越好，提出将类 样本对数；聚类前在同一类簇，聚类后不在同一类 间距离与类内距离之比作为聚类效果的内部评价指 簇的样本对数：聚类前不在同一类簇，聚类后在于 标STDI(standard deviation based index),如式(9)所 同一类簇的样本对数；和聚类前后都不在同一类簇 示。从式(9)STDI的定义可知，其值越大，表明聚类 的样本对数。其形式化定义如式（⑤）所示。由定义 结果越好。 可知，TP和TN统计了聚类所得划分与原始分布的 -致性，FN和FP统计了聚类所得划分与原始分布 STDI= 9 的差异性。设N表示规模为n的数据集的所有样 本对数，则w= 2 ）=",即，AeP=NP4TN 式中：c是类簇k的质心，是所有样本的质心，七是(4)，其中的 sensitivity 和 specificity 同 F-measure 指 标在两类问题中的定义一致。由此可见，我们定义 的新指标 S2 适用于任意类的聚类问题。    TPc = |{i|l(xi) = L(xi) = c,1 ⩽ i ⩽ n}| = ncc FNc = |{i|{l(xi) = c}∧{L(xi) , c},1 ⩽ i ⩽ n}| = nc· −ncc FPc = |{i|{l(xi) , c}∧{L(xi) = c},1 ⩽ i ⩽ n}| = n·c −ncc TNc = |{i|l(xi) , c, L(xi),c,1 ⩽ i ⩽ n}|=n−nc· −n·c+ncc (1) sensitivityc = TPc TPc +FNc = ncc nc· specificityc = TNc TNc +FPc = n−nc· −n·c +ncc n−nc· (2) S 2 = 1 min{C,K} min∑ {C,K} c=1 2×sensitivityc ×specificityc sensitivityc +specificityc (3) S 2 = 2×sensitivity×specificity sensitivity+specificity (4) 外部评价指标中的 Rand index、Adjusted rand index、Jaccard 系数，AMI 等均是基于样本对的聚类 评价指标。因此，本文类似地提出基于样本对的聚 类结果外部评价指标 PS2，调和聚类结果的正类识 别率和负类识别率，以评价聚类结果的有效性。 l(xi) = l ( xj ) L(xi) = L ( xj ) l(xi) = l ( xj ) L(xi) , L ( xj ) N = ( n 2 ) = n(n−1) 2 任意两样本点 xi、xj，若 ，且 ，即聚类前后属于同一类，则称为正事件 T；反 之，如果 ，但 ，即聚类前属于 同类簇，但聚类后不属于同一类，称之为负事件 F。 依据正负事件，可得表 3 所示混淆矩阵。其中，TP、 FN、FP 和 TN 分别表示聚类前后都在同一类簇的 样本对数；聚类前在同一类簇，聚类后不在同一类 簇的样本对数；聚类前不在同一类簇，聚类后在于 同一类簇的样本对数；和聚类前后都不在同一类簇 的样本对数。其形式化定义如式 (5) 所示。由定义 可知，TP 和 TN 统计了聚类所得划分与原始分布的 一致性，FN 和 FP 统计了聚类所得划分与原始分布 的差异性。设 N 表示规模为 n 的数据集的所有样 本对数，则 ，即，N=TP+FN+FP+TN。 TP、FN、FP 和 TN 也可根据表 2 所示的相依表计算 得到。计算公式如式 (6) 所示。基于样本对的 sensi￾tivity，specificity 定义如式 (7) 所示，则基于样本对 的新聚类评价指标 PS2 定义为式 (8)。    TP =    {(xi , xj ) |l(xi) = l(xj), L(xi) = L(xj) }    FN=    {(xi , xj ) |l(xi) = l(xj), L(xi) , L(xj) }    FP =    {(xi , xj ) |l(xi) , l(xj), L(xi) = L(xj) }    TN=    {(xi , xj ) |l(xi) , l(xj), L(xi) , L(xj) }    (5)    TP = ∑C i=1 ∑K j=1 ( ni j 2 ) FN = ∑C i=1 ( ni· 2 ) −TP FP = ∑K j=1 ( n· j 2 ) −TP TN = N −(TP+FN+FP) (6)    sensitivity = TP TP+FN specificity = TN TN+FP (7)    PS2 = 2×sensitivity×specificity sensitivity+specificity = 2×TP×TN TP(FP+TN)+TN(TP+FN) (8) 2 内部指标 方差作为一种度量样本分布情况的概率统计 量，通常用来描述样本的离散程度[32]。样本方差越 小，样本分布越密集，反之则越分散。方差的性质 可以用于计算类内距离和类间距离，同一类簇中样 本分布越密集，方差越小，因此将同一类簇中样本 的方差作为类内距离，度量类簇内部的紧促性。 基于“类内尽可能紧密，类间尽可能分离”原则， 利用方差思想定义度量类内距离和类间距离测度， 类间距离越大越好，类内距离越小越好，提出将类 间距离与类内距离之比作为聚类效果的内部评价指 标 STDI(standard deviation based index)，如式 (9) 所 示。从式 (9)STDI 的定义可知，其值越大，表明聚类 结果越好。 STDI = 1 K ( ∑K k=1 ∥ck − x¯∥ 2 ) ∑K k=1 1 nk ( ∑nk i=1 ∥xi − ck∥ 2 ) (9) 式中：c x¯ k 是类簇 k 的质心， 是所有样本的质心，xi 是 表 2 聚类结果相依表 Table 2 The contingency table of a clustering U/V V1 V2 ··· Vc VK SUM U1 n11 n12 ··· n1c n1K n1· U2 n21 n22 ··· n2c n2K n2· . . . . . . . . . . . . . . . . . . Uc nc1 nc2 ··· ncc ncK nc· . . . . . . . . . . . . . . . . . . UC nC1 nC2 ··· nCc nCK nC· SUM n·1 n·2 ··· n·c n·K n 表 3 聚类结果混淆矩阵 Table 3 Confusion matrix of a clustering 聚类前/聚类后 T' F' T TP FN F FP TN 第 6 期 谢娟英，等：聚类有效性评价新指标 ·875·