第11卷第3期 智能系统学报 Vol.11 No.3 2016年6月 CAAI Transactions on Intelligent Systems Jun.2016 D0I:10.11992/is.201603038 网络出版地址：http://www.enki..net/kcms/detail/23.1538.TP.20160513.0925.028.html 基于置换检验的聚类结果评估 谷飞洋，田博，张思萌，陈征，何增有 (大连理工大学软件学院，辽宁大连116621) 摘要：对聚类结果，传统的评估方法不能从统计意义上对结果评估。ECP是一种新颖的基于置换检验的评估算 法。ECP直接对聚类结果进行置换检验从而计算出p-value。为了测试ECP的效果，利用了UCI中的iris,wine, yest数据集对算法进行评测。实验结果表明，ECP可以在能够接受的时间内运算出比较准确的实验结果。 关键词：聚类：聚类评估；统计检验：置换检验 中图分类号：TP393文献标志码：A文章编号：1673-4785(2016)03-0301-09 中文引用格式：谷飞洋，田博，张思萌，等.基于置换检验的聚类结果评估[J].智能系统学报，2016,11(3)：301-309. 英文引用格式：GU Feiyang,.TIAN Bo,.ZHANG Simeng,etal.Statistical evaluation of the clustering results based on permutation test[J].CAAI transactions on intelligent systems,2016,11(3):301-309. Statistical evaluation of the clustering results based on permutation test GU Feiyang,TIAN Bo,ZHANG Simeng,CHEN Zheng,HE Zengyou (Software School,Dalian University of Technology,Dalian 116621,China) Abstract:For the result of clustering,tranditional methods of evalution couldn't assess the result in statistics.We propose a new algorithm called ECP(Statistical evaluation of Clustering based on Permutation test)which uses per- mutation test to evaluate the result of clustering.To evaluate the performance of the algorithm,we use the data sets, iris,wine,yeast,from UCI datasets.Experimental results show that the performance of the algorithm is good. Keywords:clustering;clustering evaluation;statistical test;permutation test 随着获得的数据越来越多，利用机器学习、数据 houette-ndex,Dunn-ndex等。这些函数能够评估 挖掘[1]等手段从数据中获取潜在的知识变得越来 聚类结果，但是这些函数评估出来的结果往往没有 越重要。然而如何评估挖掘出来的信息，即评估数 一个比较好的可以参考的值。即一个评估值计算出 据挖掘结果的质量是一个十分重要的问题。只有一 来之后得到的只是一个评估值，至于这个值达到什 个好的评估方法，才能保证挖掘算法发现高质量的 么标准能够接受并不能确定。利用统计方法评估聚 信息。聚类41是数据挖掘领域一个很重要的分 类结果的算法很少，其主要原因是聚类的特殊性与 支。同时，聚类的应用也越来越广泛。随着聚类的 复杂性使传统的统计方法很难用到聚类质量评估 广泛应用，如何有效地评估聚类结果的质量[6]成 上。近年来有一些利用随机方法来评估聚类结果的 为一个重要的研究课题。虽然评估聚类结果的重要 研究，但也存在一定的问题。本文根据存在的问题 性一点不亚于挖掘算法本身，但是评估方面却没有 提出了一种基于置换检验的评估方法。 受到它应有的重视。 针对聚类，现有的方法主要是用评价函数对聚 1相关研究 类结果评估。这种函数一般分3种类型：紧密型、分 1.1利用簇结构评估聚类质量 散型和连接型。常见的评估函数有DB-Index,Si- 该方法先对原始数据聚类，然后将原始数据集 按照一定的约束随机置换抽样构造新的数据集。抽 收稿日期：2016-03-19.网络出版日期：2016-05-13 基金项目：国家自然科学基金项目(61572094). 样之后用同样的聚类算法对样本数据集进行聚类。 通信作者：何增有.E-mail:zyhc@dlut.cdu.cm.第 １１ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．３ ２０１６ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０３０３８ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０５１３．０９２５．０２８．ｈｔｍｌ 基于置换检验的聚类结果评估 谷飞洋，田博，张思萌，陈征，何增有 （大连理工大学 软件学院， 辽宁 大连 １１６６２１） 摘 要：对聚类结果，传统的评估方法不能从统计意义上对结果评估。 ＥＣＰ 是一种新颖的基于置换检验的评估算 法。 ＥＣＰ 直接对聚类结果进行置换检验从而计算出 ｐ ⁃ｖａｌｕｅ。 为了测试 ＥＣＰ 的效果，利用了 ＵＣＩ 中的 ｉｒｉｓ， ｗｉｎｅ， ｙｅａｓｔ 数据集对算法进行评测。 实验结果表明，ＥＣＰ 可以在能够接受的时间内运算出比较准确的实验结果。 关键词：聚类；聚类评估； 统计检验；置换检验 中图分类号：ＴＰ３９３ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０３⁃０３０１⁃０９ 中文引用格式：谷飞洋，田博，张思萌，等．基于置换检验的聚类结果评估［Ｊ］． 智能系统学报， ２０１６， １１（３）： ３０１⁃３０９． 英文引用格式：ＧＵ Ｆｅｉｙａｎｇ， ＴＩＡＮ Ｂｏ， ＺＨＡＮＧ Ｓｉｍｅｎｇ， ｅｔ ａｌ． Ｓｔａｔｉｓｔｉｃａｌ ｅｖａｌｕａｔｉｏｎ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｂａｓｅｄ ｏｎ ｐｅｒｍｕｔａｔｉｏｎ ｔｅｓｔ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（３）： ３０１⁃３０９． Ｓｔａｔｉｓｔｉｃａｌ ｅｖａｌｕａｔｉｏｎ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｂａｓｅｄ ｏｎ ｐｅｒｍｕｔａｔｉｏｎ ｔｅｓｔ ＧＵ Ｆｅｉｙａｎｇ， ＴＩＡＮ Ｂｏ， ＺＨＡＮＧ Ｓｉｍｅｎｇ， ＣＨＥＮ Ｚｈｅｎｇ， ＨＥ Ｚｅｎｇｙｏｕ （Ｓｏｆｔｗａｒｅ Ｓｃｈｏｏｌ， Ｄａｌｉａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｄａｌｉａｎ １１６６２１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｆｏｒ ｔｈｅ ｒｅｓｕｌｔ ｏｆ ｃｌｕｓｔｅｒｉｎｇ， ｔｒａｎｄｉｔｉｏｎａｌ ｍｅｔｈｏｄｓ ｏｆ ｅｖａｌｕｔｉｏｎ ｃｏｕｌｄｎ＇ｔ ａｓｓｅｓｓ ｔｈｅ ｒｅｓｕｌｔ ｉｎ ｓｔａｔｉｓｔｉｃｓ． Ｗｅ ｐｒｏｐｏｓｅ ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｃａｌｌｅｄ ＥＣＰ（Ｓｔａｔｉｓｔｉｃａｌ ｅｖａｌｕａｔｉｏｎ ｏｆ Ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ｏｎ Ｐｅｒｍｕｔａｔｉｏｎ ｔｅｓｔ） ｗｈｉｃｈ ｕｓｅｓ ｐｅｒ⁃ ｍｕｔａｔｉｏｎ ｔｅｓｔ ｔｏ ｅｖａｌｕａｔｅ ｔｈｅ ｒｅｓｕｌｔ ｏｆ ｃｌｕｓｔｅｒｉｎｇ． Ｔｏ ｅｖａｌｕａｔｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ， ｗｅ ｕｓｅ ｔｈｅ ｄａｔａ ｓｅｔｓ， ｉｒｉｓ， ｗｉｎｅ， ｙｅａｓｔ， ｆｒｏｍ ＵＣＩ ｄａｔａｓｅｔｓ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｇｏｏｄ． Ｋｅｙｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ； ｃｌｕｓｔｅｒｉｎｇ ｅｖａｌｕａｔｉｏｎ； ｓｔａｔｉｓｔｉｃａｌ ｔｅｓｔ； ｐｅｒｍｕｔａｔｉｏｎ ｔｅｓｔ 收稿日期：２０１６⁃０３⁃１９． 网络出版日期：２０１６⁃０５⁃１３． 基金项目：国家自然科学基金项目（６１５７２０９４）． 通信作者：何增有． Ｅ⁃ｍａｉｌ：ｚｙｈｅ＠ ｄｌｕｔ．ｅｄｕ．ｃｎ． 随着获得的数据越来越多，利用机器学习、数据 挖掘［１⁃３］等手段从数据中获取潜在的知识变得越来 越重要。 然而如何评估挖掘出来的信息，即评估数 据挖掘结果的质量是一个十分重要的问题。 只有一 个好的评估方法，才能保证挖掘算法发现高质量的 信息。 聚类［４⁃５］ 是数据挖掘领域一个很重要的分 支。 同时，聚类的应用也越来越广泛。 随着聚类的 广泛应用，如何有效地评估聚类结果的质量［６⁃７］ 成 为一个重要的研究课题。 虽然评估聚类结果的重要 性一点不亚于挖掘算法本身，但是评估方面却没有 受到它应有的重视。 针对聚类，现有的方法主要是用评价函数对聚 类结果评估。 这种函数一般分 ３ 种类型：紧密型、分 散型和连接型。 常见的评估函数有 ＤＢ⁃Ｉｎｄｅｘ， Ｓｉ⁃ ｈｏｕｅｔｔｅ⁃Ｉｎｄｅｘ， Ｄｕｎｎ⁃Ｉｎｄｅｘ 等。 这些函数能够评估 聚类结果，但是这些函数评估出来的结果往往没有 一个比较好的可以参考的值。 即一个评估值计算出 来之后得到的只是一个评估值，至于这个值达到什 么标准能够接受并不能确定。 利用统计方法评估聚 类结果的算法很少，其主要原因是聚类的特殊性与 复杂性使传统的统计方法很难用到聚类质量评估 上。 近年来有一些利用随机方法来评估聚类结果的 研究，但也存在一定的问题。 本文根据存在的问题 提出了一种基于置换检验的评估方法。 １ 相关研究 １．１ 利用簇结构评估聚类质量 该方法先对原始数据聚类，然后将原始数据集 按照一定的约束随机置换抽样构造新的数据集。 抽 样之后用同样的聚类算法对样本数据集进行聚类