·308 智能系统学报 第11卷 两类进行对比)。为了让聚类质量有层次的差距， 表6ECP与ECP1效率对比 对k-means的聚类结果进行不同程度的破坏。破坏 Table 6 The comparison of ECP and ECPI 的程度越大，聚类的质量越差。实验结果如表5。 算法 iris wine yeast 从实验看SigClust与ECP都能够区别出很好和很差 ECP1 18s 50s 56s 的聚类。但是可以很明显地看出，SigClust对聚类质 ECP 1109s 734÷ 280m 量的区分度不够大。比如对于iis数据集计算的f 为2和1.8，SigClust算出的p-value都是0，没有区分 5 结束语 开这2个不同划分的质量。同样地iis数据集f为 本文提出了一种新的基于置换检验的聚类结果 1.36和1.15865，SigClust算出的p-value都为1。实 评估方法ECP。为了增大抽样的数目，利用DB-n- 验可以看出ECP能很好地区分聚类质量的差距。 dex的计算特点减小了对样本函数值计算的复杂 因此，与SigClust相比，ECP不仅能处理k>2的情 度。为了得到更精确的p-value,根据聚类划分的特 况，而且能更好地评估聚类质量。 点，假设了DB-Index的函数值是符合高斯分布的， 表4ECP与最大熵方法对比 Table 4 The comparison of ECP and maximum entropy 进而可以用较少的抽样估出更为准确的p-value。 method 从实验的结果来看，ECP对评估聚类结果有很好的 算法 iris 效果，并且具有很强的实用性。 wine yeast 最大嫡 0.001 0.001 0.001 最大嫡 参考文献： 4.891817e-050.37003520.002626655 拟合正态 [1]TAN Pangning,STEINBACH M,KUMAR V.Introduction ECP 0.042742131.988773e-056.937873e-05 to data mining[M.Boston:Addison-Wesley,2005. [2]HAN Jiawei,KAMBER M,PEI Jian.Data mining:con- 表5ECP与Sigclust对比 cepts and techniques[M].3rd ed.Burlington,MA,USA: Table 5 The comparison of ECP and Sigclust Elsevier,2012:1-33. [3]尹宏伟，李凡长.谱机器学习研究综述[J].计算机科学 p-value/Sigclust 数据p-value/ECP f-score accuracy 与探索，2015,9(12)：1409-1419. Sigclust YIN Hongwei,LI Fanzhang.Survey on spectral machine 0.1145728 0 2 1 learning[]].Journal of frontiers of computer science and 0.1216881 0 1.8 0.9 Iris technolog,2015,9(12):1409-1419. 0.1571689 1.36 0.68 0.2282965 [4]JAIN A K,MURTY M N,FLYNN P J.Data clustering:a 1.15865 0.58 0.001534783 0 1.876810.938462 review[J].ACM computing surveys,1999,31(3):264- 0.002878496 0.1992 1.673660.838462 323 wine 0.006082356 1 1.430740.715385 [5]WU Xindong,KUMAR V,QUINLAN J R,et al.Top 10 al- 0.221656 1.011640.546154 gorithms in data mining[J].Knowledge and information sys- 0.006761993 0 1.130050.567265 tems,2008,14(1):1-37. 0.0107751 1.077860.539238 [6]HALKIDI M,BATISTAKIS Y,VAZIRGIANNIS M.On yeast 0.01254987 1 1.073480.536996 clustering validation techniques[J].Journal of intelligent 0.2564062 1.044030.522422 information systems,2001,17(2-3):107-145. 4.3.3 ECP与ECP1对比 [7]HANDL J,KNOWLES J,KELL D B.Computational cluster 这一部分说明ECP比加速的ECP1在效率上 validation in post-genomic data analysis[J].Bioinformatics. 有很大提高。ECP1是未加速的ECP算法。本文将 2005,21(15):3201-3212. 这两种算法进行了效率上的对比。实验结果如表 8]KONTONASIOS K N.VREEKEN J,DE BIE T.Maximum 6。实验分别用两种算法抽样100000次并得到对 entropy modelling for assessing results on real-valued data [C]//Proceedings of the 11th international conference on 应的统计值。可以看出，对于iis数据集，ECP比 data mining.Vancouver,BC,Canada,2011:350-359. ECP1快了60倍。可见ECP在效率上有质的提升。两类进行对比）。 为了让聚类质量有层次的差距， 对 ｋ⁃ｍｅａｎｓ 的聚类结果进行不同程度的破坏。 破坏 的程度越大，聚类的质量越差。 实验结果如表 ５。 从实验看 ＳｉｇＣｌｕｓｔ 与 ＥＣＰ 都能够区别出很好和很差 的聚类。 但是可以很明显地看出，ＳｉｇＣｌｕｓｔ 对聚类质 量的区分度不够大。 比如对于 ｉｒｉｓ 数据集计算的 ｆ １ 为 ２ 和 １．８，ＳｉｇＣｌｕｓｔ 算出的 ｐ⁃ｖａｌｕｅ 都是 ０，没有区分 开这 ２ 个不同划分的质量。 同样地 ｉｒｉｓ 数据集 ｆ １ 为 １．３６ 和１．１５８ ６５，ＳｉｇＣｌｕｓｔ 算出的 ｐ⁃ｖａｌｕｅ 都为 １。 实 验可以看出 ＥＣＰ 能很好地区分聚类质量的差距。 因此，与 ＳｉｇＣｌｕｓｔ 相比，ＥＣＰ 不仅能处理 ｋ ＞ ２ 的情 况，而且能更好地评估聚类质量。 表 ４ ＥＣＰ 与最大熵方法对比 Ｔａｂｌｅ ４ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＥＣＰ ａｎｄ ｍａｘｉｍｕｍ ｅｎｔｒｏｐｙ ｍｅｔｈｏｄ 算法 ｉｒｉｓ ｗｉｎｅ ｙｅａｓｔ 最大熵 ０．００１ ０．００１ ０．００１ 最大熵 拟合正态 ４．８９１ ８１７ｅ⁃０５ ０．３７０ ０３５ ２ ０．００２ ６２６ ６５５ ＥＣＰ ０．０４２ ７４２ １３ １．９８８ ７７３ｅ⁃０５ ６．９３７ ８７３ｅ⁃０５ 表 ５ ＥＣＰ 与 Ｓｉｇｃｌｕｓｔ 对比 Ｔａｂｌｅ ５ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＥＣＰ ａｎｄ Ｓｉｇｃｌｕｓｔ 数据 ｐ⁃ｖａｌｕｅ ／ ＥＣＰ ｐ⁃ｖａｌｕｅ ／ Ｓｉｇｃｌｕｓｔ Ｓｉｇｃｌｕｓｔ ｆ⁃ｓｃｏｒｅ ａｃｃｕｒａｃｙ Ｉｒｉｓ ０．１１４ ５７２ ８ ０ ２ １ ０．１２１ ６８８ １ ０ １．８ ０．９ ０．１５７ １６８ ９ １ １．３６ ０．６８ ０．２２８ ２９６ ５ １ １．１５８ ６５ ０．５８ ｗｉｎｅ ０．００１ ５３４ ７８３ ０ １．８７６ ８１ ０．９３８ ４６２ ０．００２ ８７８ ４９６ ０．１９９ ２ １．６７３ ６６ ０．８３８ ４６２ ０．００６ ０８２ ３５６ １ １．４３０ ７４ ０．７１５ ３８５ ０．２２１ ６５６ １ １．０１１ ６４ ０．５４６ １５４ ｙｅａｓｔ ０．００６ ７６１ ９９３ ０ １．１３０ ０５ ０．５６７ ２６５ ０．０１０ ７７５ １ １ １．０７７ ８６ ０．５３９ ２３８ ０．０１２ ５４９ ８７ １ １．０７３ ４８ ０．５３６ ９９６ ０．２５６ ４０６ ２ １ １．０４４ ０３ ０．５２２ ４２２ ４．３．３ ＥＣＰ 与 ＥＣＰ１ 对比 这一部分说明 ＥＣＰ 比加速的 ＥＣＰ１ 在效率上 有很大提高。 ＥＣＰ１ 是未加速的 ＥＣＰ 算法。 本文将 这两种算法进行了效率上的对比。 实验结果如表 ６。 实验分别用两种算法抽样 １００ ０００ 次并得到对 应的统计值。 可以看出，对于 ｉｒｉｓ 数据集，ＥＣＰ 比 ＥＣＰ１ 快了 ６０ 倍。 可见 ＥＣＰ 在效率上有质的提升。 表 ６ ＥＣＰ 与 ＥＣＰ１ 效率对比 Ｔａｂｌｅ ６ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＥＣＰ ａｎｄ ＥＣＰ１ 算法 ｉｒｉｓ ｗｉｎｅ ｙｅａｓｔ ＥＣＰ１ １８ ｓ ５０ ｓ ５６ｓ ＥＣＰ １１０９ ｓ ７３４ ｓ ２８０ ｍ ５ 结束语 本文提出了一种新的基于置换检验的聚类结果 评估方法 ＥＣＰ。 为了增大抽样的数目，利用 ＤＢ⁃Ｉｎ⁃ ｄｅｘ 的计算特点减小了对样本函数值计算的复杂 度。 为了得到更精确的 ｐ ⁃ｖａｌｕｅ，根据聚类划分的特 点，假设了 ＤＢ⁃Ｉｎｄｅｘ 的函数值是符合高斯分布的， 进而可以用较少的抽样估出更为准确的 ｐ ⁃ｖａｌｕｅ。 从实验的结果来看，ＥＣＰ 对评估聚类结果有很好的 效果，并且具有很强的实用性。 参考文献： ［１］ＴＡＮ Ｐａｎｇｎｉｎｇ， ＳＴＥＩＮＢＡＣＨ Ｍ， ＫＵＭＡＲ Ｖ． Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｄａｔａ ｍｉｎｉｎｇ［Ｍ］． Ｂｏｓｔｏｎ： Ａｄｄｉｓｏｎ⁃Ｗｅｓｌｅｙ， ２００５． ［ ２］ ＨＡＮ Ｊｉａｗｅｉ， ＫＡＭＢＥＲ Ｍ， ＰＥＩ Ｊｉａｎ． Ｄａｔａ ｍｉｎｉｎｇ： ｃｏｎ⁃ ｃｅｐｔｓ ａｎｄ ｔｅｃｈｎｉｑｕｅｓ［Ｍ］． ３ｒｄ ｅｄ． Ｂｕｒｌｉｎｇｔｏｎ， ＭＡ， ＵＳＡ： Ｅｌｓｅｖｉｅｒ， ２０１２： １⁃３３． ［３］尹宏伟， 李凡长． 谱机器学习研究综述［ Ｊ］． 计算机科学 与探索， ２０１５， ９（１２）： １４０９⁃１４１９． ＹＩＮ Ｈｏｎｇｗｅｉ， ＬＩ Ｆａｎｚｈａｎｇ． Ｓｕｒｖｅｙ ｏｎ ｓｐｅｃｔｒａｌ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｆｒｏｎｔｉｅｒｓ ｏｆ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ， ２０１５， ９（１２）： １４０９⁃１４１９． ［４］ＪＡＩＮ Ａ Ｋ， ＭＵＲＴＹ Ｍ Ｎ， ＦＬＹＮＮ Ｐ Ｊ． Ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ： ａ ｒｅｖｉｅｗ［Ｊ］． ＡＣＭ ｃｏｍｐｕｔｉｎｇ ｓｕｒｖｅｙｓ， １９９９， ３１（ ３）： ２６４⁃ ３２３． ［５］ＷＵ Ｘｉｎｄｏｎｇ， ＫＵＭＡＲ Ｖ， ＱＵＩＮＬＡＮ Ｊ Ｒ， ｅｔ ａｌ． Ｔｏｐ １０ ａｌ⁃ ｇｏｒｉｔｈｍｓ ｉｎ ｄａｔａ ｍｉｎｉｎｇ［Ｊ］． Ｋｎｏｗｌｅｄｇｅ ａｎｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓ⁃ ｔｅｍｓ， ２００８， １４（１）： １⁃３７． ［６］ ＨＡＬＫＩＤＩ Ｍ， ＢＡＴＩＳＴＡＫＩＳ Ｙ， ＶＡＺＩＲＧＩＡＮＮＩＳ Ｍ． Ｏｎ ｃｌｕｓｔｅｒｉｎｇ ｖａｌｉｄａｔｉｏｎ ｔｅｃｈｎｉｑｕｅｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｉｎｔｅｌｌｉｇｅｎｔ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ， ２００１， １７（２⁃３）： １０７⁃１４５． ［７］ＨＡＮＤＬ Ｊ， ＫＮＯＷＬＥＳ Ｊ， ＫＥＬＬ Ｄ Ｂ． Ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｌｕｓｔｅｒ ｖａｌｉｄａｔｉｏｎ ｉｎ ｐｏｓｔ⁃ｇｅｎｏｍｉｃ ｄａｔａ ａｎａｌｙｓｉｓ［Ｊ］． Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ， ２００５， ２１（１５）： ３２０１⁃３２１２． ［８］ＫＯＮＴＯＮＡＳＩＯＳ Ｋ Ｎ， ＶＲＥＥＫＥＮ Ｊ， ＤＥ ＢＩＥ Ｔ． Ｍａｘｉｍｕｍ ｅｎｔｒｏｐｙ ｍｏｄｅｌｌｉｎｇ ｆｏｒ ａｓｓｅｓｓｉｎｇ ｒｅｓｕｌｔｓ ｏｎ ｒｅａｌ⁃ｖａｌｕｅｄ ｄａｔａ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １１ｔｈ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｄａｔａ ｍｉｎｉｎｇ． Ｖａｎｃｏｕｖｅｒ， ＢＣ， Ｃａｎａｄａ， ２０１１： ３５０⁃３５９． ·３０８· 智 能 系 统 学 报 第 １１ 卷