第12卷第6期 智能系统学报 Vol.12 No.6 2017年12月 CAAI Transactions on Intelligent Systems Dec.2017 D0:10.11992/tis.201706029 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20171109.1250.006.html 聚类有效性评价新指标 谢娟英，周颖，王明钊，姜炜亮 (陕西师范大学计算算计科学学院，陕西西安710062)】 摘要：聚类有效性评价指标分为外部评价指标和内部评价指标两大类。现有外部评价指标没有考虑聚类结果类偏 斜现象：现有内部评价指标的聚类有效性检验效果难以得到最佳类簇数。针对现有内外部聚类评价指标的缺陷，提 出同时考虑正负类信息的分别基于相依表和样本对的外部评价指标，用于评价任意分布数据集的聚类结果；提出采 用方差度量类内紧密度和类间分离度，以类间分离度与类内紧密度之比作为度量指标的内部评价指标。UCI数据集 和人工模拟数据集实验测试表明，提出的新内部评价指标能有效发现数据集的真实类簇数：提出的基于相依表和样 本对的外部评价指标，可有效评价存在类偏斜与噪音数据的聚类结果。 关键词：聚类：聚类有效性：评价指标：外部指标：内部指标：F-measure:Adjusted Rand Index:STDI:S2:PS2 中图分类号：TP108文献标志码：A文章编号：1673-4785(2017)06-0873-10 中文引用格式：谢娟英，周颖，王明钊，等.聚类有效性评价新指标.智能系统学报，2017,12(6)：873-882. 英文引用格式：XIE Juanying,.ZHOU Ying,VANG Mingzhao,etal.New criteria for evaluating the validity of clustering Jl..CAAI transactions on intelligent systems,2017,12(6):873-882. New criteria for evaluating the validity of clustering XIE Juanying,ZHOU Ying,WANG Mingzhao,JIANG Weiliang (School of Computer Science,Shaanxi Normal University,Xi'an 710062,China) Abstract:There are two kinds of criteria for evaluating the clustering ability of a clustering algorithm,internal and ex- ternal.The current external evaluation indexes fails to consider the skewed clustering result,it is difficult to get optim- um cluster numbers from the clustering validity inspection results from the internal evaluation indexes.Considering the defects in the present internal and external clustering evaluation indices,we propose two external evaluation indexes, which consider both positive and negative information and which are respectively based on the contingency table and sample pairs for the evaluation of clustering results from a dataset with arbitrary distribution.The variance is proposed to measure the tightness of a cluster and the separability between clusters,and the ratio of these parameters is used as an internal evaluation index for the measurement index.Experiments on the datesets from UCI (University of California in Iven)machine learning repository and artificially simulated datasets show that the proposed new internal index can be used to effectively find the truenumber of clusters in a dataset.The proposed external indexes based on the contingency table and sample pairs are a very effective external evaluation indexes and can be used to evaluate the clustering results from existing types of skewed and noisy data. Keywords:clustering;validity of clustering;evaluation index;external criteria;internal criteria;F-measure;Adjusted Rand Index:STDI:S2:PS2 收稿日期：2017-06-08.网络出版日期：2017-11-09 随着人工智能技术如火如茶地发展，机器学习 基金项目：国家自然科学基金项目(61673251)：陕西省科技攻关项 目(2013K12-03-24):陕西师范大学研究生创新基金项 在各行业得到了空前的重视和应用，并取得了前所 目(2015CXS028,2016CSY009):中央高校基本科研业 未有的成功。聚类分析作为无监督学习方法，是 务费重点项目(GK201701006). 通信作者：谢娟英.E-mail:xiejuany@snnu.edu.cn 各行业数据分析的主要工具之一，其旨在发现数据
DOI: 10.11992/tis.201706029 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20171109.1250.006.html 聚类有效性评价新指标 谢娟英，周颖，王明钊，姜炜亮 （陕西师范大学 计算算计科学学院，陕西 西安 710062） 摘 要：聚类有效性评价指标分为外部评价指标和内部评价指标两大类。现有外部评价指标没有考虑聚类结果类偏 斜现象；现有内部评价指标的聚类有效性检验效果难以得到最佳类簇数。针对现有内外部聚类评价指标的缺陷，提 出同时考虑正负类信息的分别基于相依表和样本对的外部评价指标，用于评价任意分布数据集的聚类结果； 提出采 用方差度量类内紧密度和类间分离度，以类间分离度与类内紧密度之比作为度量指标的内部评价指标。UCI 数据集 和人工模拟数据集实验测试表明，提出的新内部评价指标能有效发现数据集的真实类簇数；提出的基于相依表和样 本对的外部评价指标，可有效评价存在类偏斜与噪音数据的聚类结果。 关键词：聚类；聚类有效性；评价指标；外部指标；内部指标；F-measure；Adjusted Rand Index；STDI；S2；PS2 中图分类号：TP108 文献标志码：A 文章编号：1673−4785(2017)06−0873−10 中文引用格式：谢娟英, 周颖, 王明钊, 等. 聚类有效性评价新指标[J]. 智能系统学报, 2017, 12(6): 873–882. 英文引用格式：XIE Juanying, ZHOU Ying, WANG Mingzhao, et al. New criteria for evaluating the validity of clustering[J]. CAAI transactions on intelligent systems, 2017, 12(6): 873–882. New criteria for evaluating the validity of clustering XIE Juanying，ZHOU Ying，WANG Mingzhao，JIANG Weiliang (School of Computer Science, Shaanxi Normal University, Xi’an 710062, China) Abstract: There are two kinds of criteria for evaluating the clustering ability of a clustering algorithm, internal and external. The current external evaluation indexes fails to consider the skewed clustering result; it is difficult to get optimum cluster numbers from the clustering validity inspection results from the internal evaluation indexes. Considering the defects in the present internal and external clustering evaluation indices, we propose two external evaluation indexes, which consider both positive and negative information and which are respectively based on the contingency table and sample pairs for the evaluation of clustering results from a dataset with arbitrary distribution. The variance is proposed to measure the tightness of a cluster and the separability between clusters, and the ratio of these parameters is used as an internal evaluation index for the measurement index. Experiments on the datesets from UCI (University of California in Iven) machine learning repository and artificially simulated datasets show that the proposed new internal index can be used to effectively find the truenumber of clusters in a dataset. The proposed external indexes based on the contingency table and sample pairs are a very effective external evaluation indexes and can be used to evaluate the clustering results from existing types of skewed and noisy data. Keywords: clustering; validity of clustering; evaluation index; external criteria; internal criteria; F-measure; Adjusted Rand Index; STDI; S2; PS2 随着人工智能技术如火如荼地发展，机器学习 在各行业得到了空前的重视和应用，并取得了前所 未有的成功[1-5]。聚类分析作为无监督学习方法，是 各行业数据分析的主要工具之一，其旨在发现数据 收稿日期：2017−06−08. 网络出版日期：2017−11−09. 基金项目：国家自然科学基金项目 (61673251)；陕西省科技攻关项 目 (2013K12-03-24)；陕西师范大学研究生创新基金项 目 (2015CXS028，2016CSY009)；中央高校基本科研业 务费重点项目 (GK201701006). 通信作者：谢娟英. E-mail：xiejuany@snnu.edu.cn. 第 12 卷第 6 期 智 能 系 统 学 报 Vol.12 No.6 2017 年 12 月 CAAI Transactions on Intelligent Systems Dec. 2017
·874· 智能系统学报 第12卷 集样本的潜在分布模式与内在结构，发现数据集样 簇结构难以判别，聚类有效性检验效果不理想，很 本中所隐藏的知识。聚类分析使得同类簇的样本尽 难得到正确的聚类结果和发现最佳类簇数。针对现 可能相似，不同类簇的样本尽可能不相似s”。聚类 有内部评价指标的上述问题，本文利用方差的性 评价指标是度量聚类结果有效性的客观指标，也是 质，定义类内距离和类间距离，以表达类簇间的分 衡量聚类算法性能的客观依据，设计一个全面的聚 离性与类簇内的紧促性，提出基于类间分离性与类 类结果评价指标是一个困难而复杂的问题8)。 内紧密性之比的新内部评价指标STDI(standard de- 根据是否利用数据集样本真实类标信息（真实 viation based index),以期发现数据集的真实类簇分 的样本分布信息)，聚类有效性评价指标分为外部评 布结构。 价指标和内部评价指标。外部评价指标通过比较聚 UCI机器学习数据库真实数据集和人工模拟的 类结果与真实分布的匹配程度，对聚类结果进行评 带有刁难性的及带有噪音与类偏斜的人工模拟数据 价。现有外部评价指标分为基于相依表的，基于样 集实验测试表明，提出的内部评价新指标STDI能 本对的和基于信息熵的指标&1-w。F-measure-1阁 发现更合理的数据集类簇数；提出的分别基于相依 是最先提出的外部评价指标，是针对两类问题的评 表和样本对的外部评价指标S2和PS2可以有效评 价指标，是精度和召回率的调和平均，后来被推广 价有类偏斜现象的聚类结果。 到多类问题。常用的外部评价指标还有Jaccard系 1外部指标 数、Rand index参数、ARI(adjusted rand index)参 数、标准化互信息NMI(normalized mutual informa- 聚类分析中可能遇到如表1所示的极端情况。 tion)和调整互信息AMl(adjusted mutual informa- 此时，若用F-measure指标评价表1所示极端聚类 tion),以及B3(bcubed index)等，-1。不同外部评 结果的有效性，将失去意义。因为，此时的F-meas- 价指标侧重点不同，Amigo等20提出4个形式化约 ure指标值是0.67，但实际聚类结果毫无意义。导 (cluster homogeneity,cluster completeness,rag 致这种现象的原因是：F-measure是精度和召回率的 bag和clusters size vs.quantity)对现有外部评价指 调和平均。对于两类问题，F-measure只强调了聚类 标进行比较。Vih等2指出ARI指标是目前最好 算法对正类的聚类效果，而未考虑聚类算法对负类 的聚类评价指标。聚类结果类偏斜是现实世界 的聚类效果。 数据，特别是生物医学数据聚类分析中的普遍现 表1极端聚类结果示例 象221。尽管已经出现针对不平衡数据和不同类簇 Table 1 Rare case of clustering 密度的聚类评价指标研究2刘，但还没有考虑聚类 聚类前/ 真实分布相依表 聚类算法得到的相依表 结果偏斜的外部评价指标。鉴于此，本文利用聚类 聚类后 聚类后正类聚类后负类聚类后正类聚类后负类 结果的相依表和样本对信息，同时考虑聚类结果的 聚类前 50 50 正负类信息，提出分别基于相依表和基于样本对的 正类 0 外部评价指标S2(harmonic mean of sensitivity and 聚类前 0 50 50 0 specificity)PS2(harmonic mean of sensitivity and 负类 specificity based on pairwise),以期有效评价偏斜聚 为了避免此类问题，本文提出一种基于相依表 类结果。 的、同时考虑正负类聚类结果的评价指标S2。S2 内部评价指标没有使用原始数据分布的先验信 指标调和了聚类算法对于正负类的聚类效果，是灵 息，常通过评价聚类结果优劣来发现数据集的内部 敏度和特异度的调和平均。如同F-measure可推广 结构和分布状态，是发现数据集最佳类簇数的常用 于多类问题一样，S2同样适用于作为多类问题的聚 办法。内部指标有基于统计信息和基于样本几何 类评价指标。 结构的指标。IGP指标2(in-group proportion)是基 设聚类结果类簇数为K,原始类簇数为C,则聚 于统计信息的指标，通过度量在某一类簇中，距离 类结果相依表是表2所示的C×K矩阵，U是真实分 某个样本最近的样本是否和该样本在同一类簇，来 布，V是聚类算法所得聚类结果，则任意类簇c的 评价聚类结果的优劣。常用的基于数据集样本几何 TP、FNc、FP、TN。分别定义如式(1)所示。其中， 结构的内部指标有DB指标(davies-bouldin).2 l为原始类标信息，L为聚类所得类标信息，n为样 XB指标(xie-beni)2、Sil指标(silhouettes)3o1、 本数。以类簇c为正类的sensitivity和specificity BWP指标(between-within proportion)等。这些聚 定义如式(2)所示。则新聚类指标$2如式(3)定 类有效性评价内部指标自身的缺陷，使得其对于类 义。当类簇数K=2时，式(3)的S2指标退化为式
集样本的潜在分布模式与内在结构，发现数据集样 本中所隐藏的知识。聚类分析使得同类簇的样本尽 可能相似，不同类簇的样本尽可能不相似[6-7]。聚类 评价指标是度量聚类结果有效性的客观指标，也是 衡量聚类算法性能的客观依据，设计一个全面的聚 类结果评价指标是一个困难而复杂的问题[8-13]。 根据是否利用数据集样本真实类标信息 (真实 的样本分布信息)，聚类有效性评价指标分为外部评 价指标和内部评价指标。外部评价指标通过比较聚 类结果与真实分布的匹配程度，对聚类结果进行评 价。现有外部评价指标分为基于相依表的，基于样 本对的和基于信息熵的指标[8, 13-14]。F-measure[17-18] 是最先提出的外部评价指标，是针对两类问题的评 价指标，是精度和召回率的调和平均，后来被推广 到多类问题。常用的外部评价指标还有 Jaccard 系 数、Rand index 参数、ARI (adjusted rand index) 参 数、标准化互信息 NMI (normalized mutual information) 和调整互信息 AMI (adjusted mutual information)，以及 B3(bcubed index) 等 [8, 17-19]。不同外部评 价指标侧重点不同，Amigó等 [20]提出 4 个形式化约 束 (cluster homogeneity, cluster completeness, rag bag 和 clusters size vs. quantity) 对现有外部评价指 标进行比较。Vinh 等 [21]指出 ARI 指标是目前最好 的聚类评价指标。聚类结果类偏斜是现实世界 数据，特别是生物医学数据聚类分析中的普遍现 象 [22-23]。尽管已经出现针对不平衡数据和不同类簇 密度的聚类评价指标研究[8, 24] ，但还没有考虑聚类 结果偏斜的外部评价指标。鉴于此，本文利用聚类 结果的相依表和样本对信息，同时考虑聚类结果的 正负类信息，提出分别基于相依表和基于样本对的 外部评价指标 S2(harmonic mean of sensitivity and specificity) 和 PS2(harmonic mean of sensitivity and specificity based on pairwise)，以期有效评价偏斜聚 类结果。 内部评价指标没有使用原始数据分布的先验信 息，常通过评价聚类结果优劣来发现数据集的内部 结构和分布状态，是发现数据集最佳类簇数的常用 办法[25]。内部指标有基于统计信息和基于样本几何 结构的指标。IGP 指标[26] (in-group proportion) 是基 于统计信息的指标，通过度量在某一类簇中，距离 某个样本最近的样本是否和该样本在同一类簇，来 评价聚类结果的优劣。常用的基于数据集样本几何 结构的内部指标有 DB 指标 (davies-bouldin)[27-28] 、 XB 指标 (xie-beni)[29] 、Sil 指标 (silhouettes)[30] 、 BWP 指标 (between-within proportion)[31]等。这些聚 类有效性评价内部指标自身的缺陷，使得其对于类 簇结构难以判别，聚类有效性检验效果不理想，很 难得到正确的聚类结果和发现最佳类簇数。针对现 有内部评价指标的上述问题，本文利用方差的性 质，定义类内距离和类间距离，以表达类簇间的分 离性与类簇内的紧促性，提出基于类间分离性与类 内紧密性之比的新内部评价指标 STDI(standard deviation based index)，以期发现数据集的真实类簇分 布结构。 UCI 机器学习数据库真实数据集和人工模拟的 带有刁难性的及带有噪音与类偏斜的人工模拟数据 集实验测试表明，提出的内部评价新指标 STDI 能 发现更合理的数据集类簇数；提出的分别基于相依 表和样本对的外部评价指标 S2 和 PS2 可以有效评 价有类偏斜现象的聚类结果。 1 外部指标 聚类分析中可能遇到如表 1 所示的极端情况。 此时，若用 F-measure 指标评价表 1 所示极端聚类 结果的有效性，将失去意义。因为，此时的 F-measure 指标值是 0.67，但实际聚类结果毫无意义。导 致这种现象的原因是：F-measure 是精度和召回率的 调和平均。对于两类问题，F-measure 只强调了聚类 算法对正类的聚类效果，而未考虑聚类算法对负类 的聚类效果。 为了避免此类问题，本文提出一种基于相依表 的、同时考虑正负类聚类结果的评价指标 S2。S2 指标调和了聚类算法对于正负类的聚类效果，是灵 敏度和特异度的调和平均。如同 F-measure 可推广 于多类问题一样，S2 同样适用于作为多类问题的聚 类评价指标。 设聚类结果类簇数为 K，原始类簇数为 C，则聚 类结果相依表是表 2 所示的 C×K 矩阵，U 是真实分 布，V 是聚类算法所得聚类结果，则任意类簇 c 的 TPc、FNc、FPc、TNc 分别定义如式 (1) 所示。其中， l 为原始类标信息，L 为聚类所得类标信息，n 为样 本数。以类簇 c 为正类的 sensitivity 和 specificity 定义如式 (2) 所示。则新聚类指标 S2 如式 (3) 定 义。当类簇数 K=2 时，式 (3) 的 S2 指标退化为式 表 1 极端聚类结果示例 Table 1 Rare case of clustering 聚类前/ 聚类后 真实分布相依表 聚类算法得到的相依表 聚类后正类 聚类后负类 聚类后正类 聚类后负类 聚类前 正类 50 0 50 0 聚类前 负类 0 50 50 0 ·874· 智 能 系 统 学 报 第 12 卷
第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) 所示。基于样本对的 sensitivity，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·
·876· 智能系统学报 第12卷 类簇k的第i个样本，.是类簇k的样本数，K是数 外部指标S2与PS2对带有噪音以及类别分布不平 据集的类簇数。STDI指标的分子表示各类簇间方 衡数据聚类结果的判断能力。测试外部指标的人工 差，分母表示各类簇方差之和。显然簇内方差越 模拟数据集如图2所示，表4是图2各数据集的详 小，则分母越小，表示类簇内部分布越紧密，簇间方 细信息，测试外部指标的UCI机器学习数据库的真 差越大，则分子越大，表示各类簇的分离性越好。 实数据集如表5所示。 因此，STDI的值越大越好。 1.0m 0.9 3实验分析 0.8 0.7 本节将分别测试提出的内部指标和外部指标的 05g 0.61 性能。因为篇幅所限，内部指标只使用图1所示的 0. 猴 具有挑战性的人工模拟数据集进行测试，该数据集 0.3 0.2 经常被识别为3个类簇。外部评价指标将使用来 0.1 自UCI机器学习数据库的真实数据集和人工模 0 010.20.30.40.50.60.70.80.91.0 拟数据集两大类数据进行测试。其中的人工模拟数 据包括：类簇样本分布不平衡的偏斜数据，以及类 图1测试内部指标STDI的人工数据集原始分布 簇样本分布平衡但各类簇间存在部分交叠的数据。 Fig.1 The synthetic data set to test the new internal criter- 这样设计人工模拟数据集的目的在于：检测提出的 ia STDI 40 30 2 15 10 0 5 -10 20 -10 -30 -15 0 -20 50-40-30-20-1001020304050 10 0 10 20 3040 (a)2类平衡数据集Ec2 (b)2类不平衡数据集UEc2 14 10 8 6 6 2 0 -2 0 2 681012 2.53.03.54.04.55.05.56.06.57.07.5 (c)3类平衡数据集Ec3 (d3类不平衡数据集UEc3 10 -10 3 468 10 0 5 10 1520 (e)4类平衡数据集Ec4 (①4类不平衡数据集UEc4
类簇 k 的第 i 个样本，nk 是类簇 k 的样本数，K 是数 据集的类簇数。STDI 指标的分子表示各类簇间方 差，分母表示各类簇方差之和。显然簇内方差越 小，则分母越小，表示类簇内部分布越紧密，簇间方 差越大，则分子越大，表示各类簇的分离性越好。 因此，STDI 的值越大越好。 3 实验分析 本节将分别测试提出的内部指标和外部指标的 性能。因为篇幅所限，内部指标只使用图 1 所示的 具有挑战性的人工模拟数据集进行测试，该数据集 经常被识别为 3 个类簇。外部评价指标将使用来 自 UCI 机器学习数据库[33]的真实数据集和人工模 拟数据集两大类数据进行测试。其中的人工模拟数 据包括：类簇样本分布不平衡的偏斜数据，以及类 簇样本分布平衡但各类簇间存在部分交叠的数据。 这样设计人工模拟数据集的目的在于：检测提出的 外部指标 S2 与 PS2 对带有噪音以及类别分布不平 衡数据聚类结果的判断能力。测试外部指标的人工 模拟数据集如图 2 所示，表 4 是图 2 各数据集的详 细信息，测试外部指标的 UCI 机器学习数据库的真 实数据集如表 5 所示。 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 X Y 图 1 测试内部指标 STDI 的人工数据集原始分布 Fig. 1 The synthetic data set to test the new internal criteria STDI −4 −2 0 2 4 6 8 10 12 −4 −2 0 2 4 6 8 10 12 14 X Y 2.5 3.0 3.5 4.0 4.5 5.0 5.5 6.0 6.5 7.0 7.5 1 2 3 4 5 6 7 8 X Y −4 −2 0 2 4 6 8 10 −4 −2 0 2 4 6 8 10 X X Y −10 −5 0 5 10 15 20 −10 −5 0 5 10 15 20 Y −50 −40 −30 −20 −10 0 10 20 30 40 50 −40 −30 −20 −10 0 10 20 30 40 X Y −20 −10 0 10 20 30 40 −20 −15 −10 −5 0 5 10 15 20 25 30 X Y (a) 2 ㆧ㶍ᢚ䯲 Ec2 (b) 2 ㆧ̹㶍ᢚ䯲 UEc2 (c) 3 ㆧ㶍ᢚ䯲 Ec3 (d) 3 ㆧ̹㶍ᢚ䯲 UEc3 (e) 4 ㆧ㶍ᢚ䯲 Ec4 (f) 4 ㆧ̹㶍ᢚ䯲 UEc4 ·876· 智 能 系 统 学 报 第 12 卷
第6期 谢娟英，等：聚类有效性评价新指标 ·877· 30 30 20 20 10 20 -20 -30 -30 20 -10 0 1020 30 30 -20-100102030 (g)5类平衡数据集Ec5 (h)5类不平衡数据集UEc5 30 25 20 20 15 10 -10 20 -15 -3 -2 -40-30-20-10010203040 -30 -20-100102030 (①6类平衡数据集Ec6 G)6类不平衡数据集UEc6 图2测试外部指标S2和PS2的人工数据集原始分布 Fig.2 The synthetic data sets to test the new external criteria S2 and PS2 表4测试新外部指标S2和PS2的人工模拟数据集信息 表5测试新外部指标S2和PS2的UCI数据集 Table 4 The detail information of synthetic data sets to Table 5 The data sets from UCI machine learning reposit- test the proposed external criteria S2 and PS2 ory to test the proposed external criteria S2 and PS2 数据集样本数类簇数 各类簇样本数 数据集 样本数类簇数 各类簇样本数 Ec2 2000 10001000 Iris 150 3505050 Ec3 1200 3 400 400400 Seeds 210 3707070 Ec4 800 4 200 200200200 Segmentation 210 730303030303030 Ec5 3000 5 600600600600600 Soybean 47 410101017 Ec6 2400 6 400400400400400400 wine 178 3 597148 UEc2 2000 5001500 wdbc 569 2357212 UEc3 1200 3 200 400600 Bupa 345 2145200 UEc4 800 50 150200400 pima-indians-diabetes 768 2500268 UEc5 3000 5 10008006001400200 Balance scale 625 349288288 UEc62400 6100200300400600800 New_thyroid 215 31503530 3.1内部指标有效性测试实验 Ionosphere 351 238313 内部指标不需要任何先验知识，通过评价聚类 Haberman 306 222581 结果，发现数据集样本的潜在分布与内在结构，常 用于发现数据集的类簇数。因此，我们以能否准确 从图3各指标的实验结果可以看出，只有图 发现数据集的真实类簇数来测试提出的内部指标 3(a)展示的STDI指标的实验结果可以发现图1 STDI指标的有效性，并与现有内部指标DB、XB、 所示人工数据集的真实类簇数9，其余5个指标均 IGP、Sil和BWP的性能进行比较。图3给出了各 在类簇数为3时最佳，即其余指标发现的该数据集 内部指标对图1所示人工模拟数据集的实验结果。 类簇数是3。因此，只有用本文提出内部聚类指标 这里的聚类算法使用的是SD算法B。 STDI可以得到该人工模拟数据集的正确类簇数
3.1 内部指标有效性测试实验 内部指标不需要任何先验知识，通过评价聚类 结果，发现数据集样本的潜在分布与内在结构，常 用于发现数据集的类簇数。因此，我们以能否准确 发现数据集的真实类簇数来测试提出的内部指标 STDI 指标的有效性，并与现有内部指标 DB、XB、 IGP、Sil 和 BWP 的性能进行比较。图 3 给出了各 内部指标对图 1 所示人工模拟数据集的实验结果。 这里的聚类算法使用的是 SD 算法[35]。 从图 3 各指标的实验结果可以看出，只有图 3(a) 展示的 STDI 指标的实验结果可以发现图 1 所示人工数据集的真实类簇数 9，其余 5 个指标均 在类簇数为 3 时最佳，即其余指标发现的该数据集 类簇数是 3。因此，只有用本文提出内部聚类指标 STDI 可以得到该人工模拟数据集的正确类簇数。 表 4 测试新外部指标 S2 和 PS2 的人工模拟数据集信息 Table 4 The detail information of synthetic data sets to test the proposed external criteria S2 and PS2 数据集 样本数 类簇数 各类簇样本数 Ec2 2 000 2 1 000 1 000 Ec3 1 200 3 400 400 400 Ec4 800 4 200 200 200 200 Ec5 3 000 5 600 600 600 600 600 Ec6 2 400 6 400 400 400 400 400 400 UEc2 2 000 2 500 1 500 UEc3 1 200 3 200 400 600 UEc4 800 4 50 150 200 400 UEc5 3 000 5 1 000 800 600 1 400 200 UEc6 2 400 6 100 200 300 400 600 800 表 5 测试新外部指标 S2 和 PS2 的 UCI 数据集 Table 5 The data sets from UCI machine learning repository to test the proposed external criteria S2 and PS2 数据集 样本数类簇数 各类簇样本数 Iris 150 3 50 50 50 Seeds 210 3 70 70 70 Segmentation 210 7 30 30 30 30 30 30 30 Soybean 47 4 10 10 10 17 wine 178 3 59 71 48 wdbc 569 2 357 212 Bupa 345 2 145 200 pima-indians-diabetes 768 2 500 268 Balance_scale 625 3 49 288 288 New_thyroid 215 3 150 35 30 Ionosphere 351 2 38 313 Haberman 306 2 225 81 −30 −10 0 10 20 30 −20 −20 −30 −10 0 10 20 30 X X Y −30 −10 0 10 20 30 −20 −15 −20 −10 −5 0 10 5 20 15 25 X X Y −30 −10 0 10 20 30 −20 −20 −30 −10 0 10 20 30 Y −40 −10 0 10 20 40 −30 −20 30 −20 −30 −10 0 10 20 30 Y (g) 5 ㊫ᒣ㺑ᮠᦞ䳶 Ec5 (h) 5 ㊫нᒣ㺑ᮠᦞ䳶 UEc5 (i) 6 ㊫ᒣ㺑ᮠᦞ䳶 Ec6 (j) 6 ㊫нᒣ㺑ᮠᦞ䳶 UEc6 图 2 测试外部指标 S2 和 PS2 的人工数据集原始分布 Fig. 2 The synthetic data sets to test the new external criteria S2 and PS2 第 6 期 谢娟英，等：聚类有效性评价新指标 ·877·