第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
第 １１ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．３ ２０１６ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０３０３８ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０５１３．０９２５．０２８．ｈｔｍｌ 基于置换检验的聚类结果评估 谷飞洋，田博，张思萌，陈征，何增有 （大连理工大学 软件学院， 辽宁 大连 １１６６２１） 摘 要：对聚类结果，传统的评估方法不能从统计意义上对结果评估。 ＥＣＰ 是一种新颖的基于置换检验的评估算 法。 ＥＣＰ 直接对聚类结果进行置换检验从而计算出 ｐ ⁃ｖａｌｕｅ。 为了测试 ＥＣＰ 的效果，利用了 ＵＣＩ 中的 ｉｒｉｓ， ｗｉｎｅ， ｙｅａｓｔ 数据集对算法进行评测。 实验结果表明，ＥＣＰ 可以在能够接受的时间内运算出比较准确的实验结果。 关键词：聚类；聚类评估； 统计检验；置换检验 中图分类号：ＴＰ３９３ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０３⁃０３０１⁃０９ 中文引用格式：谷飞洋，田博，张思萌，等．基于置换检验的聚类结果评估［Ｊ］． 智能系统学报， ２０１６， １１（３）： ３０１⁃３０９． 英文引用格式：ＧＵ Ｆｅｉｙａｎｇ， ＴＩＡＮ Ｂｏ， ＺＨＡＮＧ Ｓｉｍｅｎｇ， ｅｔ ａｌ． Ｓｔａｔｉｓｔｉｃａｌ ｅｖａｌｕａｔｉｏｎ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｂａｓｅｄ ｏｎ ｐｅｒｍｕｔａｔｉｏｎ ｔｅｓｔ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（３）： ３０１⁃３０９． Ｓｔａｔｉｓｔｉｃａｌ ｅｖａｌｕａｔｉｏｎ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｂａｓｅｄ ｏｎ ｐｅｒｍｕｔａｔｉｏｎ ｔｅｓｔ ＧＵ Ｆｅｉｙａｎｇ， ＴＩＡＮ Ｂｏ， ＺＨＡＮＧ Ｓｉｍｅｎｇ， ＣＨＥＮ Ｚｈｅｎｇ， ＨＥ Ｚｅｎｇｙｏｕ （Ｓｏｆｔｗａｒｅ Ｓｃｈｏｏｌ， Ｄａｌｉａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｄａｌｉａｎ １１６６２１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｆｏｒ ｔｈｅ ｒｅｓｕｌｔ ｏｆ ｃｌｕｓｔｅｒｉｎｇ， ｔｒａｎｄｉｔｉｏｎａｌ ｍｅｔｈｏｄｓ ｏｆ ｅｖａｌｕｔｉｏｎ ｃｏｕｌｄｎ＇ｔ ａｓｓｅｓｓ ｔｈｅ ｒｅｓｕｌｔ ｉｎ ｓｔａｔｉｓｔｉｃｓ． Ｗｅ ｐｒｏｐｏｓｅ ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｃａｌｌｅｄ ＥＣＰ（Ｓｔａｔｉｓｔｉｃａｌ ｅｖａｌｕａｔｉｏｎ ｏｆ Ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ｏｎ Ｐｅｒｍｕｔａｔｉｏｎ ｔｅｓｔ） ｗｈｉｃｈ ｕｓｅｓ ｐｅｒ⁃ ｍｕｔａｔｉｏｎ ｔｅｓｔ ｔｏ ｅｖａｌｕａｔｅ ｔｈｅ ｒｅｓｕｌｔ ｏｆ ｃｌｕｓｔｅｒｉｎｇ． Ｔｏ ｅｖａｌｕａｔｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ， ｗｅ ｕｓｅ ｔｈｅ ｄａｔａ ｓｅｔｓ， ｉｒｉｓ， ｗｉｎｅ， ｙｅａｓｔ， ｆｒｏｍ ＵＣＩ ｄａｔａｓｅｔｓ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｇｏｏｄ． Ｋｅｙｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ； ｃｌｕｓｔｅｒｉｎｇ ｅｖａｌｕａｔｉｏｎ； ｓｔａｔｉｓｔｉｃａｌ ｔｅｓｔ； ｐｅｒｍｕｔａｔｉｏｎ ｔｅｓｔ 收稿日期：２０１６⁃０３⁃１９． 网络出版日期：２０１６⁃０５⁃１３． 基金项目：国家自然科学基金项目（６１５７２０９４）． 通信作者：何增有． Ｅ⁃ｍａｉｌ：ｚｙｈｅ＠ ｄｌｕｔ．ｅｄｕ．ｃｎ． 随着获得的数据越来越多，利用机器学习、数据 挖掘［１⁃３］等手段从数据中获取潜在的知识变得越来 越重要。 然而如何评估挖掘出来的信息，即评估数 据挖掘结果的质量是一个十分重要的问题。 只有一 个好的评估方法，才能保证挖掘算法发现高质量的 信息。 聚类［４⁃５］ 是数据挖掘领域一个很重要的分 支。 同时，聚类的应用也越来越广泛。 随着聚类的 广泛应用，如何有效地评估聚类结果的质量［６⁃７］ 成 为一个重要的研究课题。 虽然评估聚类结果的重要 性一点不亚于挖掘算法本身，但是评估方面却没有 受到它应有的重视。 针对聚类，现有的方法主要是用评价函数对聚 类结果评估。 这种函数一般分 ３ 种类型：紧密型、分 散型和连接型。 常见的评估函数有 ＤＢ⁃Ｉｎｄｅｘ， Ｓｉ⁃ ｈｏｕｅｔｔｅ⁃Ｉｎｄｅｘ， Ｄｕｎｎ⁃Ｉｎｄｅｘ 等。 这些函数能够评估 聚类结果，但是这些函数评估出来的结果往往没有 一个比较好的可以参考的值。 即一个评估值计算出 来之后得到的只是一个评估值，至于这个值达到什 么标准能够接受并不能确定。 利用统计方法评估聚 类结果的算法很少，其主要原因是聚类的特殊性与 复杂性使传统的统计方法很难用到聚类质量评估 上。 近年来有一些利用随机方法来评估聚类结果的 研究，但也存在一定的问题。 本文根据存在的问题 提出了一种基于置换检验的评估方法。 １ 相关研究 １．１ 利用簇结构评估聚类质量 该方法先对原始数据聚类，然后将原始数据集 按照一定的约束随机置换抽样构造新的数据集。 抽 样之后用同样的聚类算法对样本数据集进行聚类
·302· 智能系统学报 第11卷 这样重复大量的次数后，再用评估函数（如DB-In- 量不同簇的两个最近成员的距离。全连接：度量不 dex)计算每个样本的函数值。如果原始数据集聚类 同簇的两个最远成员的距离。质心比较：度量不同 结果的函数值小于大部分随机构造的数据集聚类结 簇的中心点的距离。 果的函数值，那么说明挖掘出来的信息是可靠的，否 链接度链接度指簇中的元素成员至少要跟同 则说明聚类结果不可靠。更通俗一点，如果原来数 一个簇内的元素比较像。这个可以用来评估簇模型 据集没有好的簇结构，那么无论怎么聚类，结果都是 不是圆形或者球形的聚类结果，比如DBSCAN的聚 不好的。代表性的方法有最大熵模型抽样[】、矩阵 类结果。 元素交换9]等。利用数据集簇结构来评估聚类质 本文用一种无监督评估聚类质量的方法，Da- 量[]的方法能很好地评估出簇结构不好的聚类结 vies-Bouldin Index,DB_Index. 果。实验证实对不同数据集进行聚类，有明显簇结 构数据集的p-value会比没有明显簇结构的p-value DBI =1 、+s) max(D, =1 小很多。但是这种方法并不能准确评估聚类的质 式中：S表示第i个簇内的元素与质心的标准方差， 量。从某种意义上讲，这种方法更适合评估一个数 D,表示第i个簇与第j个簇质心间的欧几里德距 据集是否有好的簇结构。 离，k表示簇的数目。 1.2 SigClust DBI的思想是一个高质量的聚类结果需要满 SigClust!)认为如果一个数据集符合高斯分 足：同一个簇的各元素间相似度大，不同类之间的相 布，那么对这个数据集的任何分割都是不合理的。 似度小。在DBI中，分子越小意味着簇内元素相似 因此这个方法的前提假设是：一个单一的簇的元素 度越大，分母越大意味着簇间相似度越小。 符合高斯分布。SigClust主要是针对k=2的聚类评 2.2聚类评估的p-value 估。对于>2的情况，还没有比较好的解决办法。 给一个数据集X,用DB-ndex计算聚类结果的 l.3层次聚类的p-value计算 函数值为xox。数据集X所有可能的聚类结果的函 这种方法主要针对层次聚类的评估2，)。层 数值为x1,x,xN。置换检验的p-value定义为 次聚类后会形成一个二叉树。对二叉树上的每个节 点都进行置换检验，算出每个节点划分对应的p ∑a1(xn≤xo） value。这种算法的空假设为：当前节点的左子树和 N 右子树应该属于一个簇。如果算出p-value足够小 式中I是一个逻辑函数。当x.≤xo的情况下为1， 就说明空假设是一个小概率事件，应该拒绝。该方 否则为0。由于要枚举出所有的聚类方案的复杂度 法是将当前节点的左子树和右子树打乱，按照一定 是指数级别的，所以需要采取其他的策略。抽样出 的约束随机分配左子树和右子树的元素。抽样若干 所有情况的一个子集Y,并计算子集Y中所有元素 次后形成的随机样本集按照某种指标与原始划分对 的函数值为x1,x2,xw,其中N≤N。这时候置 比计算出p-value.。这个评估只能针对层次聚类，不 换检验的p-value被定义为 能对其他的聚类算法进行评估。另外这样计算出的 ∑N1(xn≤o） p-value只是每个节点上的p-value,并不是全局聚 N 类的p-value. 一些研究为了避免p-value为0的情况，将p-value 2基本概念 的定义修改为 2.1无监督聚类质量评估函数 1+1x≤w) 如果数据集中的元素没有类标签，聚类结果的 Ppeml N+1 评价就只能依赖数据集自身的特征和量值。在这种 这种方法把分子加1的理由是把x。也看作置 情况下，聚类的度量追求有3个目标：紧密度、分离 换检验一个样本的函数值。这就避免了得到p-vl- 度和链接度。 ue为0的试验结果。然而这种做法事实上是不太 紧密度簇中的每个元素应该彼此尽可能接 合理的。试想如果抽样999次没有发现比x。更小 近。紧密度的常用度量是方差，方差越小说明紧密 的统计值，这样草率地得出结论当前置换检验的结 度越大。 果为0.001显然太武断了。因为可能抽样99999次 分离度簇与簇之间应该充分分离。有3种常 依旧没有比x。更优的样本。那么依照这个计算公 用方法来度量两个不同簇之间的距离。单连接：度 式p-value又为0.000O1。而实际上p-value的值可
这样重复大量的次数后，再用评估函数（如 ＤＢ⁃Ｉｎ⁃ ｄｅｘ）计算每个样本的函数值。 如果原始数据集聚类 结果的函数值小于大部分随机构造的数据集聚类结 果的函数值，那么说明挖掘出来的信息是可靠的，否 则说明聚类结果不可靠。 更通俗一点，如果原来数 据集没有好的簇结构，那么无论怎么聚类，结果都是 不好的。 代表性的方法有最大熵模型抽样［８］ 、矩阵 元素交换［９ ］ 等。 利用数据集簇结构来评估聚类质 量［１０］的方法能很好地评估出簇结构不好的聚类结 果。 实验证实对不同数据集进行聚类，有明显簇结 构数据集的 ｐ⁃ｖａｌｕｅ 会比没有明显簇结构的 ｐ⁃ｖａｌｕｅ 小很多。 但是这种方法并不能准确评估聚类的质 量。 从某种意义上讲，这种方法更适合评估一个数 据集是否有好的簇结构。 １．２ ＳｉｇＣｌｕｓｔ ＳｉｇＣｌｕｓｔ ［１１］ 认为如果一个数据集符合高斯分 布，那么对这个数据集的任何分割都是不合理的。 因此这个方法的前提假设是：一个单一的簇的元素 符合高斯分布。 ＳｉｇＣｌｕｓｔ 主要是针对 ｋ ＝ ２ 的聚类评 估。 对于 ｋ＞２ 的情况，还没有比较好的解决办法。 １．３ 层次聚类的 ｐ ⁃ｖａｌｕｅ 计算 这种方法主要针对层次聚类的评估［１２，１３］ 。 层 次聚类后会形成一个二叉树。 对二叉树上的每个节 点都进行置换检验，算出每个节点划分对应的 ｐ ⁃ ｖａｌｕｅ。 这种算法的空假设为：当前节点的左子树和 右子树应该属于一个簇。 如果算出 ｐ ⁃ｖａｌｕｅ 足够小 就说明空假设是一个小概率事件，应该拒绝。 该方 法是将当前节点的左子树和右子树打乱，按照一定 的约束随机分配左子树和右子树的元素。 抽样若干 次后形成的随机样本集按照某种指标与原始划分对 比计算出 ｐ ⁃ｖａｌｕｅ。 这个评估只能针对层次聚类，不 能对其他的聚类算法进行评估。 另外这样计算出的 ｐ ⁃ｖａｌｕｅ 只是每个节点上的 ｐ ⁃ｖａｌｕｅ，并不是全局聚 类的 ｐ ⁃ｖａｌｕｅ。 ２ 基本概念 ２．１ 无监督聚类质量评估函数 如果数据集中的元素没有类标签，聚类结果的 评价就只能依赖数据集自身的特征和量值。 在这种 情况下，聚类的度量追求有 ３ 个目标：紧密度、分离 度和链接度。 紧密度 簇中的每个元素应该彼此尽可能接 近。 紧密度的常用度量是方差，方差越小说明紧密 度越大。 分离度 簇与簇之间应该充分分离。 有 ３ 种常 用方法来度量两个不同簇之间的距离。 单连接：度 量不同簇的两个最近成员的距离。 全连接：度量不 同簇的两个最远成员的距离。 质心比较：度量不同 簇的中心点的距离。 链接度 链接度指簇中的元素成员至少要跟同 一个簇内的元素比较像。 这个可以用来评估簇模型 不是圆形或者球形的聚类结果，比如 ＤＢＳＣＡＮ 的聚 类结果。 本文用一种无监督评估聚类质量的方法， Ｄａ⁃ ｖｉｅｓ⁃Ｂｏｕｌｄｉｎ Ｉｎｄｅｘ，即 ＤＢ＿Ｉｎｄｅｘ。 ＤＢＩ ＝ １ ｋ ∑ ｋ ｉ ＝ １ ｍａｘ（ Ｓｉ ＋ Ｓｊ Ｄｉｊ ）． 式中：Ｓｉ表示第 ｉ 个簇内的元素与质心的标准方差， Ｄｉｊ表示第 ｉ 个簇与第 ｊ 个簇质心间的欧几里德距 离，ｋ 表示簇的数目。 ＤＢＩ 的思想是一个高质量的聚类结果需要满 足：同一个簇的各元素间相似度大，不同类之间的相 似度小。 在 ＤＢＩ 中，分子越小意味着簇内元素相似 度越大，分母越大意味着簇间相似度越小。 ２．２ 聚类评估的 ｐ ⁃ｖａｌｕｅ 给一个数据集 Ｘ，用 ＤＢ⁃Ｉｎｄｅｘ 计算聚类结果的 函数值为 ｘ０ ｘ０ 。 数据集 Ｘ 所有可能的聚类结果的函 数值为 ｘ１ ，ｘ２ ，…ｘＮａｌｌ 。 置换检验的 ｐ ⁃ｖａｌｕｅ 定义为 Ｐｐｅｒｍ ＝ ∑ Ｎａｌｌ ｎ ＝ １ Ｉ（ｘｎ ≤ ｘ０ ） Ｎａｌｌ 式中 Ｉ 是一个逻辑函数。 当 ｘｎ≤ｘ０ 的情况下为 １， 否则为 ０。 由于要枚举出所有的聚类方案的复杂度 是指数级别的，所以需要采取其他的策略。 抽样出 所有情况的一个子集 Ｙ，并计算子集 Ｙ 中所有元素 的函数值为 ｘ１ ，ｘ２ ，…ｘＮ，其中 Ｎ≪ Ｎ ａｌｌ。 这时候置 换检验的 ｐ ⁃ｖａｌｕｅ 被定义为 Ｐｐｅｒｍ０ ＝ ∑ Ｎ ｎ ＝ １ Ｉ（ｘｎ ≤ ｘ０ ） Ｎ ． 一些研究为了避免 ｐ ⁃ｖａｌｕｅ 为 ０ 的情况，将 ｐ ⁃ｖａｌｕｅ 的定义修改为 Ｐｐｅｒｍ１ ＝ １ ＋ ∑ Ｎ ｎ ＝ １ １（ｘｎ ≤ ｘ０ ） Ｎ ＋ １ 这种方法把分子加 １ 的理由是把 ｘ０ 也看作置 换检验一个样本的函数值。 这就避免了得到 ｐ ⁃ｖａｌ⁃ ｕｅ 为 ０ 的试验结果。 然而这种做法事实上是不太 合理的。 试想如果抽样 ９９９ 次没有发现比 ｘ０ 更小 的统计值，这样草率地得出结论当前置换检验的结 果为 ０．００１ 显然太武断了。 因为可能抽样 ９９ ９９９ 次 依旧没有比 ｘ０ 更优的样本。 那么依照这个计算公 式 ｐ ⁃ｖａｌｕｅ 又为０．０００ ０１。 而实际上 ｐ ⁃ｖａｌｕｅ 的值可 ·３０２· 智 能 系 统 学 报 第 １１ 卷
第3期 谷飞洋，等：基于置换检验的聚类结果评估 ·303· 能更小。因此本文把p-value的定义为PpemoP 法。算法1描述了抽样的过程。 置换检验的准确性取决于抽样的数目，一般的 算法1 Shuffle(CI,n) 置换检验抽样的次数都在1000次以上。为了得到 fori←-0ton-ldo 更精确的p-value抽样的次数越多越好，理想的情 index +rand()mod (i+1) 况是置换所有的可能。然而对于不同的数据集合， swap(CI,Cline CI,CI) 甚至很难预测需要执行多少次置换才能够得到比较 可以用数学归纳法进行证明算法1保证了每个 好的结果。往往为了得到更精确的值就会增大抽样 元素获得同一簇标号的概率是一样的。抽样的复杂 次数，但是增加抽样次数的代价是增加计算的复杂 度为O(n)。这样进行抽样N次，就得到了N个样 性。对于普通的数据集往往抽样次数达到10000 本。然后利用样本对原始聚类结果进行评估。用 次之后就不太容易提高抽样次数。而这样做又产生 DB-Index算出原始聚类的函数值x。与样本的函数 出了一个问题。如果一个聚类结果真实的p-value 值x1,x2,…,xw。有了这些值就能计算p-value了。 为0.000001。而抽样的次数只有10000次的话，那 具体算法如下。 么p-value为就为0了。针对这些问题，本文提出 算法2ECP1 了一种新的聚类评估方法，ECP,该方法能比较好地 用DB-Index计算聚类结果的函数值xo。 解决上文提到的问题。 fori←-1 to N do 3 基于置换检验的聚类结果评估 Shuffle(CI,n) 用DB-Index计算样本的函数值x 3.1基本思想 计算p-value 本文提出的置换检验方法将关注点锁定在了聚 一般情况下kn,因此DB-ndex的复杂度为 类的结果上。评估聚类结果的本质是看聚类算法对 数据集中元素的划分质量。从这个角度出发，可以 O(n×d)。抽样一次的复杂度是O(n),容易算出总 体复杂度为O(N×n×d)。这个复杂度还是比较高 枚举对数据集的划分，然后用评估函数算出枚举划 的。所以需要想一些方法来降低复杂度。N是抽样 分的函数值。如果绝大部分划分都没有要评估的聚 次数，期望越大越好。可以看到DB-ndex是影响复 类结果质量好的话，那么就说明要评估的聚类结果 杂度的主要因素。如果降低DB-ndex计算的复杂 质量比较好。相反地，就说明要评估的聚类结果质 性，那么就可以在相同的时间内抽取更多的样本来 量并不好。 因此对于一个聚类结果，本文定义了零假0： 提高p-value的准确度。本文发现了DB-ndex公式 当前聚类结果不是一个高质量的聚类。然后计算这 的特点，对上文提到的算法做了改进。 个零假设的p-value。如果这个p-value非常小，就认 3.2加速技巧 为这个划分结果可以接受，可以拒绝0。否则认为 首先选取聚类结果作为初始状态。然后随机交 这个聚类结果不能接受。 换一对簇标号不同的元素的簇标号。交换后把此时 定义数据集X是一个包含n个元素的d维数 的划分作为一个样本，直接计算DB-ndex的函数 值型矩阵。首先对数据集聚类，聚成k簇后每个元 值。接下来继续交换一对簇标号不同的元素的簇标 素都会归属于一个簇。我们对每个簇进行标号。标 号，交换后计算DB-Index的值。这样迭代N次后就 号从0开始，往后依次是1,2，…，k-1。定义C1为 会得到N个样本的函数值。利用这N个值就可以 第i个元素所属的簇标号。比如C13=2表示第3个 计算出p-value。整个算法流程如下。 元素属于标号为2的簇。 算法3ECP2 接下来是抽样。抽样要满足一定约束。本文定 用DB-Index计算聚类结果的函数值xo 义的约束是：样本中簇包含元素的数目要与待评估 for i1 to N do 聚类结果中簇中元素的数目保持一致。举个例子， 随机交换一对簇标号不同元素的簇标号 假设数据集元素数目n为100。划分成3簇，划分 用DB-Index计算抽样结果的函数值x, 簇中的数目分别是40、33、27。那么抽样出来的样 计算p-value 本也要满足这些条件，也就是要划分成3簇，并且簇 对比ECP1,ECP2只是修改了第3步的抽样方 中元素的数目也必须是40、33、27。具体的抽样方 法。为什么修改了抽样方法就可以增大抽样次数？ 法：首先搜集所有元素的簇标号，然后将这些簇标 下面将仔细讨论DB-Index的计算过程。DB-ndex 号随机地分配给每个元素。其实这个过程是洗牌算 的计算公式为
能更小。 因此本文把 ｐ ⁃ｖａｌｕｅ 的定义为 Ｐｐｅｒｍ０Ｐｅｃｄｆ０ 。 置换检验的准确性取决于抽样的数目，一般的 置换检验抽样的次数都在 １ ０００ 次以上。 为了得到 更精确的 ｐ ⁃ｖａｌｕｅ 抽样的次数越多越好，理想的情 况是置换所有的可能。 然而对于不同的数据集合， 甚至很难预测需要执行多少次置换才能够得到比较 好的结果。 往往为了得到更精确的值就会增大抽样 次数，但是增加抽样次数的代价是增加计算的复杂 性。 对于普通的数据集往往抽样次数达到 １０ ０００ 次之后就不太容易提高抽样次数。 而这样做又产生 出了一个问题。 如果一个聚类结果真实的 ｐ ⁃ｖａｌｕｅ 为 ０．０００ ００１。 而抽样的次数只有 １０ ０００ 次的话，那 么 ｐ ⁃ｖａｌｕｅ 为就为 ０ 了。 针对这些问题，本文提出 了一种新的聚类评估方法，ＥＣＰ，该方法能比较好地 解决上文提到的问题。 ３ 基于置换检验的聚类结果评估 ３．１ 基本思想 本文提出的置换检验方法将关注点锁定在了聚 类的结果上。 评估聚类结果的本质是看聚类算法对 数据集中元素的划分质量。 从这个角度出发，可以 枚举对数据集的划分，然后用评估函数算出枚举划 分的函数值。 如果绝大部分划分都没有要评估的聚 类结果质量好的话，那么就说明要评估的聚类结果 质量比较好。 相反地，就说明要评估的聚类结果质 量并不好。 因此对于一个聚类结果，本文定义了零假 Ｈ０： 当前聚类结果不是一个高质量的聚类。 然后计算这 个零假设的 ｐ⁃ｖａｌｕｅ。 如果这个 ｐ⁃ｖａｌｕｅ 非常小，就认 为这个划分结果可以接受，可以拒绝 Ｈ０。 否则认为 这个聚类结果不能接受。 定义数据集 Ｘ 是一个包含 ｎ 个元素的 ｄ 维数 值型矩阵。 首先对数据集聚类，聚成 ｋ 簇后每个元 素都会归属于一个簇。 我们对每个簇进行标号。 标 号从 ０ 开始，往后依次是 １，２， …，ｋ－１。 定义ＣＩｉ 为 第 ｉ 个元素所属的簇标号。 比如ＣＩ３ ＝ ２ 表示第 ３ 个 元素属于标号为 ２ 的簇。 接下来是抽样。 抽样要满足一定约束。 本文定 义的约束是： 样本中簇包含元素的数目要与待评估 聚类结果中簇中元素的数目保持一致。 举个例子， 假设数据集元素数目 ｎ 为 １００。 划分成 ３ 簇，划分 簇中的数目分别是 ４０、３３、２７。 那么抽样出来的样 本也要满足这些条件，也就是要划分成 ３ 簇，并且簇 中元素的数目也必须是 ４０、３３、２７。 具体的抽样方 法： 首先搜集所有元素的簇标号，然后将这些簇标 号随机地分配给每个元素。 其实这个过程是洗牌算 法。 算法 １ 描述了抽样的过程。 算法 １ Ｓｈｕｆｆｌｅ（ＣＩ， ｎ） ｆｏｒ ｉ← ０ ｔｏ ｎ－１ ｄｏ ｉｎｄｅｘ ← ｒａｎｄ（） ｍｏｄ （ｉ ＋ １） ｓｗａｐ（ ＣＩｉ，ＣＩｉｎｄｅｘＣＩｉ，ＣＩｉｎｄｅｘ ） 可以用数学归纳法进行证明算法 １ 保证了每个 元素获得同一簇标号的概率是一样的。 抽样的复杂 度为 Ｏ（ｎ）。 这样进行抽样 Ｎ 次，就得到了 Ｎ 个样 本。 然后利用样本对原始聚类结果进行评估。 用 ＤＢ⁃Ｉｎｄｅｘ 算出原始聚类的函数值 ｘ０ 与样本的函数 值 ｘ１ ，ｘ２ ，…，ｘＮ。 有了这些值就能计算 ｐ ⁃ｖａｌｕｅ 了。 具体算法如下。 算法 ２ ＥＣＰ１ 用 ＤＢ⁃Ｉｎｄｅｘ 计算聚类结果的函数值 ｘ０ 。 ｆｏｒ ｉ ← １ ｔｏ Ｎ ｄｏ Ｓｈｕｆｆｌｅ（ＣＩ， ｎ） 用 ＤＢ⁃Ｉｎｄｅｘ 计算样本的函数值 ｘｉ 计算 ｐ ⁃ｖａｌｕｅ 一般情况下 ｋ≪ｎ，因此 ＤＢ⁃Ｉｎｄｅｘ 的复杂度为 Ｏ（ｎ×ｄ）。抽样一次的复杂度是 Ｏ（ ｎ），容易算出总 体复杂度为 Ｏ（Ｎ×ｎ×ｄ）。 这个复杂度还是比较高 的。 所以需要想一些方法来降低复杂度。 Ｎ 是抽样 次数，期望越大越好。 可以看到 ＤＢ⁃Ｉｎｄｅｘ 是影响复 杂度的主要因素。 如果降低 ＤＢ⁃Ｉｎｄｅｘ 计算的复杂 性，那么就可以在相同的时间内抽取更多的样本来 提高 ｐ ⁃ｖａｌｕｅ 的准确度。 本文发现了 ＤＢ⁃Ｉｎｄｅｘ 公式 的特点，对上文提到的算法做了改进。 ３．２ 加速技巧 首先选取聚类结果作为初始状态。 然后随机交 换一对簇标号不同的元素的簇标号。 交换后把此时 的划分作为一个样本，直接计算 ＤＢ⁃Ｉｎｄｅｘ 的函数 值。 接下来继续交换一对簇标号不同的元素的簇标 号，交换后计算 ＤＢ⁃Ｉｎｄｅｘ 的值。 这样迭代 Ｎ 次后就 会得到 Ｎ 个样本的函数值。 利用这 Ｎ 个值就可以 计算出 ｐ ⁃ｖａｌｕｅ。 整个算法流程如下。 算法 ３ ＥＣＰ２ 用 ＤＢ⁃Ｉｎｄｅｘ 计算聚类结果的函数值 ｘ０ ｆｏｒ ｉ← １ ｔｏ Ｎ ｄｏ 随机交换一对簇标号不同元素的簇标号 用 ＤＢ⁃Ｉｎｄｅｘ 计算抽样结果的函数值 ｘｉ 计算 ｐ ⁃ｖａｌｕｅ 对比 ＥＣＰ１，ＥＣＰ２ 只是修改了第 ３ 步的抽样方 法。 为什么修改了抽样方法就可以增大抽样次数？ 下面将仔细讨论 ＤＢ⁃Ｉｎｄｅｘ 的计算过程。 ＤＢ⁃Ｉｎｄｅｘ 的计算公式为 第 ３ 期 谷飞洋，等：基于置换检验的聚类结果评估 ·３０３·
·304. 智能系统学报 第11卷 如果知道了样本DB-Index函数值的概率分布 DBI= max( Di 就可以根据原始聚类结果的函数值算出精确的p 由S,的定义可以得出： value了。聚类是一种半监督的机器学习，其本 质对元素所属类别的划分。如果对元素随机划分无 S:= 13- 穷次。那么质量特别高的划分的比例会很小。同样 m 的，质量极端差的划分占的比例也会很小。很大比 式中m,是簇zi中元素的数目。z,是簇i中第j个元 重的划分都介于它们之间。而正态分布的特点是： 素的属性向量，z是簇i质心的属性向量。由于数据 极端概率很小，中间的概率很大。经过对数据的分 是d维的，所以3-乏‖2就是各个维度的平方和。 析，聚类划分的DB-Index函数值比较符合正态分 因此可以单独对每一维计算，然后再把所有维度的 布。因此可以假设抽样样本DB-ndex的函数值符 平方相加即可： 合正态分布。实际上正态分布符合很多自然概率分 ∑3-2=∑∑(4-a,)2, 布的指标。下面要做的就是得到正态分布的参数。 对于一维的正态分布均值和方差用式(1)和(2) 式中：aa是簇i中第j个元素的第t个属性值，a,是 得到： 簇i质心的第t个属性值。下面直接讨论第t维的 计算方法： i=1 u= (1) ∑3-2∑∑(a-a)2 N m m d= (2) ∑(4-a2 N-1 有了概率分布函数，就能将原始聚类结果x。代 入概率分布算出p-value了。 其中： 这样估出概率分布函数实现了在整体复杂度没 有增加的前提下用较少的抽样得到更为精确p-val m m: ue的目的了。 因此 立.>) ∑3-2 2 m=1 2 本文利用公式P perm 一计算p-val- mi =1 mi N ∑，4，是筷中所有元素中第！维的平方和， u实际上是利用了大数定律。大数定律的本质是 如果有无穷次试验，事件出现的频率就会无限趋近 a,是簇i中所有元素第t维的平均值。所以为了计 于事件发生的概率。而由于抽样次数有限，本文假 算S,每一维只需要维护两个值就可以了：平方和与 设了DB-Index的函数值符合正态分布。不过对于 平均值。当簇标号交换的话，能在O(1)复杂度内 抽样N次后发现，已经有足够的样本可以精确算出 修正这两个值。修改完每个维度的这两个值后，就 p-vaue的话，就不需要用正态分布计算了。然而如 可以用DB-Index算出函数值了。 果抽样N次后没有足够的样本可以用大数定律精 可以看出修改一个簇的平方和与平均值复杂度 确地计算p-value的话就要拟合正态概率分布函数 是O(d)的。因此DB-Index的计算复杂度就是 了。对于有多少个样本满足x:≤x。算是足够呢？ O(k×k×d)了。没有加速的DB-Index的计算复杂度 这是一个阈值问题。上边的过程总结起来如算 是O(n×d)。一般情况下，k≤n。所以这种方法的 法4。 效率有明显的提升。 算法4ECP 3.3更准确的p-vaue 抽样N次，算出每次的函数值x 上边提到计算DB-Index的方法的复杂度为 统计x:≤x。的数目M O(kx×d)。虽然相比于原先的计算方法已经优化 如果M≥Limit利用公式P,mo计算p-value 很多，但是对于p-value非常小的情况，可能依I旧由 否则，拟合正态概率分布算出p-value 于抽样数目有限而无法算出精确的p-value。这种 其中Limit是ECP的一个参数，是用Ppmo计算 情况下算出的p-value就会为O,然而这样的结果是 出p-value的最低数目限制。ECP不同于很多其他 不准确的。 的置换检验方法。这种方法实现了用较少的抽样计
ＤＢＩ ＝ １ ｋ ∑ ｋ ｉ ＝ １ ｍａｘ（ Ｓｉ ＋ Ｓｊ Ｄｉｊ ）． 由 Ｓｉ 的定义可以得出： Ｓｉ ＝ ∑ ｍｉ ｊ ＝ １‖ｚｊ － ｚ‖２ ｍｉ ． 式中 ｍｉ 是簇 ｚｉ 中元素的数目。 ｚｊ 是簇 ｉ 中第 ｊ 个元 素的属性向量，ｚ 是簇 ｉ 质心的属性向量。 由于数据 是 ｄ 维的，所以‖ｚｊ －ｚ‖２ 就是各个维度的平方和。 因此可以单独对每一维计算，然后再把所有维度的 平方相加即可： ∑ ｍｉ ｊ ＝ １‖ｚｊ － ｚ‖２ ＝ ∑ ｄ ｔ ＝ １∑ ｍｉ ｊ ＝ １ （ａｊｔ － ａｔ） ２ ， 式中：ａｊｔ是簇 ｉ 中第 ｊ 个元素的第 ｔ 个属性值， ａｔ 是 簇 ｉ 质心的第 ｔ 个属性值。 下面直接讨论第 ｔ 维的 计算方法： ∑ ｍｉ ｊ ＝ １‖ｚｊ － ｚ‖２ ｍｉ ＝ ∑ ｄ ｔ ＝ １∑ ｍｉ ｊ ＝ １ （ａｊｔ － ａｔ） ２ ｍｉ ＝ ∑ ｄ ｔ ＝ １ ∑ ｍｉ ｊ ＝ １ （ａｊｔ － ａｔ） ２ ｍｉ 其中： ∑ ｍｉ ｊ ＝ １ （ａｊｔ － ａｔ） ２ ｍｉ ＝ ∑ ｍｉ ｊ ＝ １ ａｊｔ ２ ｍｉ － ａｔ ２ 因此 ∑ ｍｉ ｊ ＝ １‖ｚｊ － ｚ‖２ ｍｉ ＝ ∑ ｄ ｔ ＝ １ ∑ ｍｉ ｊ ＝ １ ａｊｔ ２ ｍｉ － ａｔ ２ ∑ ｍｉ ｊ ＝ １ ａｊｔ ２ 是簇 ｉ 中所有元素中第 ｔ 维的平方和， ａｔ 是簇 ｉ 中所有元素第 ｔ 维的平均值。 所以为了计 算 Ｓｉ，每一维只需要维护两个值就可以了：平方和与 平均值。 当簇标号交换的话，能在 Ｏ（１） 复杂度内 修正这两个值。 修改完每个维度的这两个值后，就 可以用 ＤＢ⁃Ｉｎｄｅｘ 算出函数值了。 可以看出修改一个簇的平方和与平均值复杂度 是 Ｏ（ ｄ） 的。 因此 ＤＢ⁃Ｉｎｄｅｘ 的计算复杂度就是 Ｏ（ｋ×ｋ×ｄ）了。 没有加速的 ＤＢ⁃Ｉｎｄｅｘ 的计算复杂度 是 Ｏ（ｎ×ｄ）。 一般情况下，ｋ≪ｎ。 所以这种方法的 效率有明显的提升。 ３．３ 更准确的 ｐ ⁃ｖａｌｕｅ 上边提到计算 ＤＢ⁃Ｉｎｄｅｘ 的方法的复杂度为 Ｏ（ｋ×ｋ×ｄ）。 虽然相比于原先的计算方法已经优化 很多，但是对于 ｐ ⁃ｖａｌｕｅ 非常小的情况，可能依旧由 于抽样数目有限而无法算出精确的 ｐ ⁃ｖａｌｕｅ。 这种 情况下算出的 ｐ ⁃ｖａｌｕｅ 就会为 ０，然而这样的结果是 不准确的。 如果知道了样本 ＤＢ⁃Ｉｎｄｅｘ 函数值的概率分布 就可以根据原始聚类结果的函数值算出精确的 ｐ ⁃ ｖａｌｕｅ 了［１４］ 。 聚类是一种半监督的机器学习，其本 质对元素所属类别的划分。 如果对元素随机划分无 穷次。 那么质量特别高的划分的比例会很小。 同样 的，质量极端差的划分占的比例也会很小。 很大比 重的划分都介于它们之间。 而正态分布的特点是： 极端概率很小，中间的概率很大。 经过对数据的分 析，聚类划分的 ＤＢ⁃Ｉｎｄｅｘ 函数值比较符合正态分 布。 因此可以假设抽样样本 ＤＢ⁃Ｉｎｄｅｘ 的函数值符 合正态分布。 实际上正态分布符合很多自然概率分 布的指标。 下面要做的就是得到正态分布的参数。 对于一维的正态分布均值和方差用式（１） 和（２） 得到： μ ＝ ∑ Ｎ ｉ ＝ １ ｘｉ Ｎ （１） ∂ ＝ （ｘｉ － ｘ） ２ Ｎ － １ （２） 有了概率分布函数，就能将原始聚类结果 ｘ０ 代 入概率分布算出 ｐ ⁃ｖａｌｕｅ 了。 这样估出概率分布函数实现了在整体复杂度没 有增加的前提下用较少的抽样得到更为精确 ｐ ⁃ｖａｌ⁃ ｕｅ 的目的了。 本文利用公式 Ｐｐｅｒｍ０ ∑ Ｎ ｎ ＝ １ Ｉ（ｙｎ ＞ ｘ０ ） Ｎ 计算 ｐ ⁃ｖａｌ⁃ ｕｅ 实际上是利用了大数定律。 大数定律的本质是 如果有无穷次试验，事件出现的频率就会无限趋近 于事件发生的概率。 而由于抽样次数有限，本文假 设了 ＤＢ⁃Ｉｎｄｅｘ 的函数值符合正态分布。 不过对于 抽样 Ｎ 次后发现，已经有足够的样本可以精确算出 ｐ ⁃ｖａｌｕｅ 的话，就不需要用正态分布计算了。 然而如 果抽样 Ｎ 次后没有足够的样本可以用大数定律精 确地计算 ｐ ⁃ｖａｌｕｅ 的话就要拟合正态概率分布函数 了。 对于有多少个样本满足 ｘｉ ≤ ｘ０ 算是足够呢？ 这是一个阈值问题。 上边的过程总结起来如算 法 ４。 算法 ４ ＥＣＰ 抽样 Ｎ 次，算出每次的函数值 ｘｉ 统计 ｘｉ≤ｘ０ 的数目 Ｍ 如果 Ｍ≥Ｌｉｍｉｔ 利用公式 Ｐｐｅｒｍ０计算 ｐ ⁃ｖａｌｕｅ 否则，拟合正态概率分布算出 ｐ ⁃ｖａｌｕｅ 其中 Ｌｉｍｉｔ 是 ＥＣＰ 的一个参数，是用 Ｐｐｅｒｍ０ 计算 出 ｐ ⁃ｖａｌｕｅ 的最低数目限制。 ＥＣＰ 不同于很多其他 的置换检验方法。 这种方法实现了用较少的抽样计 ·３０４· 智 能 系 统 学 报 第 １１ 卷
第3期 谷飞洋，等：基于置换检验的聚类结果评估 ·305. 算出更为精确p-value的目的，在效率上有了非常 针对iis数据集，利用ECP计算出的p-value 大的飞跃。 与f-score的相关系数为-0.578018，与accuracy的 4实验 相关系数为-0.699331。具体的结果如图1。针对 wine数据集，利用ECP计算得到的p-value与f 实验选取了iris、wine和yeast等3个数据集。 score的相系数为-0.535734，与accuracy的相关系 这3个数据集都来自UCI数据库。iis、wime和 数为-0.538754。具体的结果为图2。对于yeast数 yeast数据集的属性都是数值型的，并且这3个数据 据集，利用ECP计算得到的p-value与f-score的相 集都带有类标签。 关系数为-0.500340，与accuracy的相关系数为 4.1利用p-value选择合适的聚类算法 -0.167325。具体结果为图3。 从聚类这个概念提出以来出现了很多聚类算 从实验结果可以看出用本文方法算出来的P 法。对于一个具体的应用，选择合适的聚类算法是 value是可靠的。需要注意的是yeast的数据集簇结 一个很重要的问题。本文认为对于同一个数据集用 构比较明显，聚类的结果比较集中。 不同的算法聚类，p-value小的那个结果更为可靠。 3.0 为此本文对同一数据集选用多种算法聚类来验证 2.5 p-value对选择聚类算法的有效性。实验结果如表 。 1。从实验结果可以看出，对于同一数据集p-value 2.0 8 小的聚类算法对应的f-score和accuracy比较大。 这说明利用p-value选择聚类算法是可靠的。本文 0 还计算了p-value与f-score和accuracy的相关系 o 数。本文用k-means对同一数据集聚类100次。通 0. 0 0.2 0.4 0.6 0.8 过控制k-means的迭代次数来控制划分的质量。这 p-value 样就避免了正常k-means聚类只会出现若干个固定 (a)p-value与f-score的关系 情况的问题。 1.0r 表1不同聚类方法的p-value,f-score,accuracy 0.9 Table 1 The p-value,f-score,accuracy of different clus- 0.8 ter algorithms 数据 算法 p-value f-score accuracy 0.6 Random 0.456254 1.134140 0.380000 0.5 0.4 P Hierarchical 0.100548 1.656570 0.666667 0 Iris Clustering 0.2 04 0.6 08 p-value DBSCAN 0.042825 2.7144000.906667 (b)p-value与accuracy的关系 k-means 0.042751 2.655840 0.886667 图1Iris数据集p-value与f~score和accuracy的关系 Random 0.5595881.095420 0.410112 Fig.1 The relationship between p-value and f-score, Hierarchical accuracy of iris dataset 0.0015741.666460 0.657303 Wine Clustering DBSCAN1.892991e-052.8337500.943820 2.58 k-means1.818384e-052.832200 0.943820 Random 0.6881451.0782600.357198 2.0 0 Hierarchical 0.0038710.835371 0.360277 1.5 Yeast Clustering DBSCAn 0.0007111.304800 0.434950 1.0 ×10 0 5 k-means7.544556e-051.881950 0.480370 p-value (a)p-value与f-score的关系
算出更为精确 ｐ ⁃ｖａｌｕｅ 的目的，在效率上有了非常 大的飞跃。 ４ 实验 实验选取了 ｉｒｉｓ、ｗｉｎｅ 和 ｙｅａｓｔ 等 ３ 个数据集。 这 ３ 个数据集都来自 ＵＣＩ 数据库［１５］ 。 ｉｒｉｓ、ｗｉｎｅ 和 ｙｅａｓｔ 数据集的属性都是数值型的，并且这 ３ 个数据 集都带有类标签。 ４．１ 利用 ｐ ⁃ｖａｌｕｅ 选择合适的聚类算法 从聚类这个概念提出以来出现了很多聚类算 法。 对于一个具体的应用，选择合适的聚类算法是 一个很重要的问题。 本文认为对于同一个数据集用 不同的算法聚类， ｐ ⁃ｖａｌｕｅ 小的那个结果更为可靠。 为此本文对同一数据集选用多种算法聚类来验证 ｐ ⁃ｖａｌｕｅ 对选择聚类算法的有效性。 实验结果如表 １。 从实验结果可以看出，对于同一数据集 ｐ ⁃ｖａｌｕｅ 小的聚类算法对应的 ｆ ⁃ｓｃｏｒｅ 和 ａｃｃｕｒａｃｙ 比较大。 这说明利用 ｐ ⁃ｖａｌｕｅ 选择聚类算法是可靠的。 本文 还计算了 ｐ ⁃ｖａｌｕｅ 与 ｆ ⁃ｓｃｏｒｅ 和 ａｃｃｕｒａｃｙ 的相关系 数。 本文用 ｋ⁃ｍｅａｎｓ 对同一数据集聚类 １００ 次。 通 过控制 ｋ⁃ｍｅａｎｓ 的迭代次数来控制划分的质量。 这 样就避免了正常 ｋ⁃ｍｅａｎｓ 聚类只会出现若干个固定 情况的问题。 表 １ 不同聚类方法的 ｐ ⁃ｖａｌｕｅ， ｆ ⁃ｓｃｏｒｅ， ａｃｃｕｒａｃｙ Ｔａｂｌｅ １ Ｔｈｅ ｐ ⁃ｖａｌｕｅ， ｆ ⁃ｓｃｏｒｅ， ａｃｃｕｒａｃｙ ｏｆ ｄｉｆｆｅｒｅｎｔ ｃｌｕｓ⁃ ｔｅｒ ａｌｇｏｒｉｔｈｍｓ 数据 算法 ｐ⁃ｖａｌｕｅ ｆ⁃ｓｃｏｒｅ ａｃｃｕｒａｃｙ Ｉｒｉｓ Ｒａｎｄｏｍ ０．４５６ ２５４ １．１３４ １４０ ０．３８０ ０００ Ｈｉｅｒａｒｃｈｉｃａｌ Ｃｌｕｓｔｅｒｉｎｇ ０．１００ ５４８ １．６５６ ５７０ ０．６６６ ６６７ ＤＢＳＣＡＮ ０．０４２ ８２５ ２．７１４ ４００ ０．９０６ ６６７ ｋ⁃ｍｅａｎｓ ０．０４２ ７５１ ２．６５５ ８４０ ０．８８６ ６６７ Ｗｉｎｅ Ｒａｎｄｏｍ ０．５５９ ５８８ １．０９５ ４２０ ０．４１０ １１２ Ｈｉｅｒａｒｃｈｉｃａｌ Ｃｌｕｓｔｅｒｉｎｇ ０．００１ ５７４ １．６６６ ４６０ ０．６５７ ３０３ ＤＢＳＣＡＮ １．８９２ ９９１ｅ⁃０５ ２．８３３ ７５０ ０．９４３ ８２０ ｋ⁃ｍｅａｎｓ １．８１８ ３８４ｅ⁃０５ ２．８３２ ２００ ０．９４３ ８２０ Ｙｅａｓｔ Ｒａｎｄｏｍ ０．６８８ １４５ １．０７８ ２６０ ０．３５７ １９８ Ｈｉｅｒａｒｃｈｉｃａｌ Ｃｌｕｓｔｅｒｉｎｇ ０．００３ ８７１ ０．８３５ ３７１ ０．３６０ ２７７ ＤＢＳＣＡＮ ０．０００ ７１１ １．３０４ ８００ ０．４３４ ９５０ ｋ⁃ｍｅａｎｓ ７．５４４ ５５６ ｅ⁃０５ １．８８１ ９５０ ０．４８０ ３７０ 针对 ｉｒｉｓ 数据集，利用 ＥＣＰ 计算出的 ｐ ⁃ｖａｌｕｅ 与 ｆ ⁃ｓｃｏｒｅ 的相关系数为－０．５７８ ０１８，与 ａｃｃｕｒａｃｙ 的 相关系数为－０．６９９ ３３１。 具体的结果如图 １。 针对 ｗｉｎｅ 数据集，利用 ＥＣＰ 计算得到的 ｐ ⁃ｖａｌｕｅ 与 ｆ ⁃ ｓｃｏｒｅ 的相系数为－０．５３５ ７３４，与 ａｃｃｕｒａｃｙ 的相关系 数为－０．５３８ ７５４。 具体的结果为图 ２。 对于 ｙｅａｓｔ 数 据集，利用 ＥＣＰ 计算得到的 ｐ ⁃ｖａｌｕｅ 与 ｆ ⁃ｓｃｏｒｅ 的相 关系数为 － ０． ５００ ３４０，与 ａｃｃｕｒａｃｙ 的相关系数为 －０．１６７ ３２５。 具体结果为图 ３。 从实验结果可以看出用本文方法算出来的 ｐ ⁃ ｖａｌｕｅ 是可靠的。 需要注意的是 ｙｅａｓｔ 的数据集簇结 构比较明显，聚类的结果比较集中。 （ａ）ｐ⁃ｖａｌｕｅ 与 ｆ⁃ｓｃｏｒｅ 的关系 （ｂ）ｐ⁃ｖａｌｕｅ 与 ａｃｃｕｒａｃｙ 的关系 图 １ Ｉｒｉｓ 数据集 ｐ⁃ｖａｌｕｅ 与 ｆ⁃ｓｃｏｒｅ 和 ａｃｃｕｒａｃｙ 的关系 Ｆｉｇ．１ Ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｐ⁃ｖａｌｕｅ ａｎｄ ｆ⁃ｓｃｏｒｅ， ａｃｃｕｒａｃｙ ｏｆ ｉｒｉｓ ｄａｔａｓｅｔ （ａ）ｐ⁃ｖａｌｕｅ 与 ｆ⁃ｓｃｏｒｅ 的关系 第 ３ 期 谷飞洋，等：基于置换检验的聚类结果评估 ·３０５·
·306· 智能系统学报 第11卷 1.0r 4.2利用p-vaue决定数据集簇的数目k 0.9 很多聚类算法需要预先设定划分数目k。本文 研究了p-value与k的关系。对于同一数据集，选择 0.8 不同的k用k-means分别聚类，然后计算对应的p- 0.7 vaue。计算结果如表2。 0.6 。° % 从表2中看出随着k的增加，p-value的值变 0.5 小。因为k越大，对数据集划分得越细，同一个簇内 0.4 ×103 0 2 的元素就会越相似，p-value自然就会越小。然而 p-value 划分的越细并不意味着就一定越好。举个极端的例 (b)p-value与accuracy的关系 子，将一个数据量为n的数据集划分成n个簇是毫 图2Wine数据集p-value与∫score和accuracy的关系 Fig.2 The relationship between p-value and f-score, 无意义的。 accuracy of wine dataset 本文研究了一种利用p-value的变化幅度来确 2.6 定k的新方法。这里给出一个定义： R(i)=P(i-1) 2.2 p() 20 式中：p(i-1)是当k取i-1时聚类结果的p-val 00 ue,p(i)是当k取i时的聚类结果的p-value。R(i) 1.6 w。 的意义是当k增加I时p-value的变化幅度。将表 1.4 000 2的结果按照公式计算的结果如表3。 ×10H 0 2 4 6 8 由实验结果可以看出，对于iis数据集，当k取 p-value 3的时候，R(3)=2.538900最大。事实上iis的类 (a)p-value与f-score的关系 0.54 别数目就是3。接着看wine数据集，当i取3的时 B 0.53 候R(3)=97.836510最大。真实情况wine的类别 0.52 数目就是3。对于yeast数据集当i取4的时候 0.51 R(4)=14.991890最大，以此来确定簇的数目为4。 而事实上yeast的类别数目就是4。 0.49 利用本文提出的定义能正确算出数据集中的簇 0.48 0.47 。。。°。 数目k。因此可以说明计算聚类的p-value对于确 ×10时 4 6 定聚类数目k也是有一定意义的。不过对于R() p-value 这个定义还存在一定的问题。根据R的定义，i的 (b)p-value与accuracy的关系 图3 Yeast数据集p-value与f-score和accuracy的关系 取值不小于3。因此对于簇数目为2的情况还不能 Fig.3 The relationship between p-value and f-score, 够做出合适的处理。 accuracy of yeast dataset 表2不同k下的p -value Table 2 The p-value of clusters for differentk 数据 2 3 4 5 6 7 Iris 0.108518 0.042742 0.020435 0.017261 0.006991 0.003208 Wine 0.001946 1.988773e-05 7.579904e-07 2.381891e-08 2.125773e-09 1.537855e-09 Yeast 0.006911 0.001040 6.937873e-05 9.647412e-06 1.327582e-06 3.264579e-06 表3不同k下的R(k) Table 3 The R(k)of clusters for differentk 数据 3 4 5 6 Iris 2.538900 2.091640 1.183870 2.469150 2.179010 Wine 97.836510 26.237440 31.823050 11.204820 1.382300 Yeast 6.644860 14.991890 7.191430 7.266900 0.406660
（ｂ）ｐ⁃ｖａｌｕｅ 与 ａｃｃｕｒａｃｙ 的关系 图 ２ Ｗｉｎｅ 数据集 ｐ⁃ｖａｌｕｅ 与 ｆ⁃ｓｃｏｒｅ 和 ａｃｃｕｒａｃｙ 的关系 Ｆｉｇ．２ Ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｐ ⁃ｖａｌｕｅ ａｎｄ ｆ⁃ｓｃｏｒｅ， ａｃｃｕｒａｃｙ ｏｆ ｗｉｎｅ ｄａｔａｓｅｔ （ａ）ｐ⁃ｖａｌｕｅ 与 ｆ⁃ｓｃｏｒｅ 的关系 （ｂ）ｐ⁃ｖａｌｕｅ 与 ａｃｃｕｒａｃｙ 的关系 图 ３ Ｙｅａｓｔ 数据集 ｐ⁃ｖａｌｕｅ 与 ｆ⁃ｓｃｏｒｅ 和 ａｃｃｕｒａｃｙ 的关系 Ｆｉｇ．３ Ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｐ⁃ｖａｌｕｅ ａｎｄ ｆ⁃ｓｃｏｒｅ， ａｃｃｕｒａｃｙ ｏｆ ｙｅａｓｔ ｄａｔａｓｅｔ ４．２ 利用 ｐ ⁃ｖａｌｕｅ 决定数据集簇的数目 ｋ 很多聚类算法需要预先设定划分数目 ｋ。 本文 研究了 ｐ ⁃ｖａｌｕｅ 与 ｋ 的关系。 对于同一数据集，选择 不同的 ｋ 用 ｋ⁃ｍｅａｎｓ 分别聚类，然后计算对应的 ｐ ⁃ ｖａｌｕｅ。 计算结果如表 ２。 从表 ２ 中看出随着 ｋ 的增加， ｐ ⁃ｖａｌｕｅ 的值变 小。 因为 ｋ 越大，对数据集划分得越细，同一个簇内 的元素就会越相似， ｐ ⁃ｖａｌｕｅ 自然就会越小。 然而 划分的越细并不意味着就一定越好。 举个极端的例 子，将一个数据量为 ｎ 的数据集划分成 ｎ 个簇是毫 无意义的。 本文研究了一种利用 ｐ ⁃ｖａｌｕｅ 的变化幅度来确 定 ｋ 的新方法。 这里给出一个定义： Ｒ（ｉ） ＝ ｐ（ｉ － １） ｐ（ｉ） ， 式中：ｐ（ ｉ－１）是当 ｋ 取 ｉ – １ 时聚类结果的 ｐ ⁃ｖａｌ⁃ ｕｅ，ｐ （ｉ）是当 ｋ 取 ｉ 时的聚类结果的 ｐ ⁃ｖａｌｕｅ。 Ｒ（ｉ） 的意义是当 ｋ 增加 １ 时 ｐ ⁃ｖａｌｕｅ 的变化幅度。 将表 ２ 的结果按照公式计算的结果如表 ３。 由实验结果可以看出，对于 ｉｒｉｓ 数据集，当 ｋ 取 ３ 的时候，Ｒ（３） ＝ ２．５３８ ９００ 最大。 事实上 ｉｒｉｓ 的类 别数目就是 ３。 接着看 ｗｉｎｅ 数据集，当 ｉ 取 ３ 的时 候 Ｒ（３）＝ ９７．８３６ ５１０ 最大。 真实情况 ｗｉｎｅ 的类别 数目就是 ３。 对于 ｙｅａｓｔ 数据集当 ｉ 取 ４ 的时候 Ｒ（４）＝ １４．９９１ ８９０ 最大，以此来确定簇的数目为 ４。 而事实上 ｙｅａｓｔ 的类别数目就是 ４。 利用本文提出的定义能正确算出数据集中的簇 数目 ｋ。 因此可以说明计算聚类的 ｐ ⁃ｖａｌｕｅ 对于确 定聚类数目 ｋ 也是有一定意义的。 不过对于 Ｒ（ ｉ） 这个定义还存在一定的问题。 根据 Ｒ 的定义，ｉ 的 取值不小于 ３。 因此对于簇数目为 ２ 的情况还不能 够做出合适的处理。 表 ２ 不同 ｋ 下的 ｐ ⁃ｖａｌｕｅ Ｔａｂｌｅ ２ Ｔｈｅ ｐ ⁃ｖａｌｕｅ ｏｆ ｃｌｕｓｔｅｒｓ ｆｏｒ ｄｉｆｆｅｒｅｎｔｋ 数据 ２ ３ ４ ５ ６ ７ Ｉｒｉｓ ０．１０８ ５１８ ０．０４２ ７４２ ０．０２０ ４３５ ０．０１７ ２６１ ０．００６ ９９１ ０．００３ ２０８ Ｗｉｎｅ ０．００１ ９４６ １．９８８ ７７３ｅ⁃０５ ７．５７９ ９０４ｅ⁃０７ ２．３８１ ８９１ｅ⁃０８ ２．１２５ ７７３ｅ⁃０９ １．５３７ ８５５ｅ⁃０９ Ｙｅａｓｔ ０．００６ ９１１ ０．００１ ０４０ ６．９３７ ８７３ｅ⁃０５ ９．６４７ ４１２ｅ⁃０６ １．３２７ ５８２ｅ⁃０６ ３．２６４ ５７９ｅ⁃０６ 表 ３ 不同 ｋ 下的 Ｒ（ｋ） Ｔａｂｌｅ ３ Ｔｈｅ Ｒ（ｋ） ｏｆ ｃｌｕｓｔｅｒｓ ｆｏｒ ｄｉｆｆｅｒｅｎｔｋ 数据 ３ ４ ５ ６ ７ Ｉｒｉｓ ２．５３８ ９００ ２．０９１ ６４０ １．１８３ ８７０ ２．４６９ １５０ ２．１７９ ０１０ Ｗｉｎｅ ９７．８３６ ５１０ ２６．２３７ ４４０ ３１．８２３ ０５０ １１．２０４ ８２０ １．３８２ ３００ Ｙｅａｓｔ ６．６４４ ８６０ １４．９９１ ８９０ ７．１９１ ４３０ ７．２６６ ９００ ０．４０６ ６６０ ·３０６· 智 能 系 统 学 报 第 １１ 卷
第3期 谷飞洋，等：基于置换检验的聚类结果评估 .307· 研究了对于iris、wine和yeast数据集需要多少样本 0.20 能保证p-value不会因样本数目的增加而改变。对于每 个数据集用不同数目样本计算p-vaue,结果如图5。 0.15 0.06 0.10 0.04 0.05 4000-0企0丑0-0 0.02 2 4 6 46 810 次数 抽样次数（以10为底的指数） (a)Iris (b)Wine 0.20 ×10 0.15 美a10 0.05 810 次数 0 00-0-0000 0 2 4 6 (b)Wine 抽样次数（以10为底的指数） ×10 2 (c)Yeast 图5p-value与抽样次数的关系 Fig.5 The relationship between p-value and the num- ber of samples 实验最多抽取1000000个样本。对于这3个 G 数据集，当抽样数目达10000时p-value就基本稳 定了。这一结果证实该方法具有很强的可行性。 4.3与相关算法对比 、2 44 68 0 4.3.1ECP与最大熵模型比较 次数 本文重复了最大熵模型的评估方法，这3个数 (c)Yeast 据集算出的p-value都为l/W。这是因为样本太少， 图4p-value稳定性 算法把原始聚类结果也当做一个样本。前文分析了 Fig.4 The stability of p-value 这种做法的不合理性。利用ECP就可以避免这样 0.15 的情况。除此之外，本文也尝试将最大熵方法的抽 样评估值拟合出正态分布。实验结果如表4。从实 0.10 验结果可以看出，对于wine数据集，最大熵方法算 出的p-value为0.O0l,拟合正态后的p-value为 0.3700352。这两者差距比较大，这说明将最大嫡 0.05 方法拟合成正态分布是不合适的。这一实验说明利 用ECP评估聚类结果更为可靠。 4.3.2ECP与SigClust对比 2 4 6 抽样次数（以10为底的指数） SigClust算法是主要针对k为2聚类结果的评 估。本文从每个数据集中选出了两类用k-means进 (a)Iris 行聚类（比如iris数据集中选出了Setosa、Versicolour
研究了对于 ｉｒｉｓ、ｗｉｎｅ 和 ｙｅａｓｔ 数据集需要多少样本 能保证 ｐ ⁃ｖａｌｕｅ 不会因样本数目的增加而改变。 对于每 个数据集用不同数目样本计算 ｐ ⁃ｖａｌｕｅ，结果如图５。 （ａ）Ｉｒｉｓ （ｂ） Ｗｉｎｅ （ｃ） Ｙｅａｓｔ 图 ４ ｐ⁃ｖａｌｕｅ 稳定性 Ｆｉｇ．４ Ｔｈｅ ｓｔａｂｉｌｉｔｙ ｏｆ ｐ⁃ｖａｌｕｅ （ａ）Ｉｒｉｓ （ｂ） Ｗｉｎｅ （ｃ） Ｙｅａｓｔ 图 ５ ｐ⁃ｖａｌｕｅ 与抽样次数的关系 Ｆｉｇ．５ Ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｐ⁃ｖａｌｕｅ ａｎｄ ｔｈｅ ｎｕｍ⁃ ｂｅｒ ｏｆ ｓａｍｐｌｅｓ 实验最多抽取１ ０００ ０００个样本。 对于这 ３ 个 数据集，当抽样数目达 １０ ０００ 时 ｐ ⁃ｖａｌｕｅ 就基本稳 定了。 这一结果证实该方法具有很强的可行性。 ４．３ 与相关算法对比 ４．３．１ ＥＣＰ 与最大熵模型比较 本文重复了最大熵模型的评估方法，这 ３ 个数 据集算出的 ｐ ⁃ｖａｌｕｅ 都为 １ ／ Ｎ。 这是因为样本太少， 算法把原始聚类结果也当做一个样本。 前文分析了 这种做法的不合理性。 利用 ＥＣＰ 就可以避免这样 的情况。 除此之外，本文也尝试将最大熵方法的抽 样评估值拟合出正态分布。 实验结果如表 ４。 从实 验结果可以看出，对于 ｗｉｎｅ 数据集，最大熵方法算 出的 ｐ⁃ｖａｌｕｅ 为 ０． ００１， 拟 合 正 态 后 的 ｐ⁃ｖａｌｕｅ 为 ０．３７０ ０３５ ２。 这两者差距比较大，这说明将最大熵 方法拟合成正态分布是不合适的。 这一实验说明利 用 ＥＣＰ 评估聚类结果更为可靠。 ４．３．２ ＥＣＰ 与 ＳｉｇＣｌｕｓｔ 对比 ＳｉｇＣｌｕｓｔ 算法是主要针对 ｋ 为 ２ 聚类结果的评 估。 本文从每个数据集中选出了两类用 ｋ⁃ｍｅａｎｓ 进 行聚类（比如 ｉｒｉｓ 数据集中选出了 Ｓｅｔｏｓａ、Ｖｅｒｓｉｃｏｌｏｕｒ 第 ３ 期 谷飞洋，等：基于置换检验的聚类结果评估 ·３０７·
·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在效率上有质的提升
两类进行对比）。 为了让聚类质量有层次的差距， 对 ｋ⁃ｍｅａｎｓ 的聚类结果进行不同程度的破坏。 破坏 的程度越大，聚类的质量越差。 实验结果如表 ５。 从实验看 ＳｉｇＣｌｕｓｔ 与 ＥＣＰ 都能够区别出很好和很差 的聚类。 但是可以很明显地看出，ＳｉｇＣｌｕｓｔ 对聚类质 量的区分度不够大。 比如对于 ｉｒｉｓ 数据集计算的 ｆ １ 为 ２ 和 １．８，ＳｉｇＣｌｕｓｔ 算出的 ｐ⁃ｖａｌｕｅ 都是 ０，没有区分 开这 ２ 个不同划分的质量。 同样地 ｉｒｉｓ 数据集 ｆ １ 为 １．３６ 和１．１５８ ６５，ＳｉｇＣｌｕｓｔ 算出的 ｐ⁃ｖａｌｕｅ 都为 １。 实 验可以看出 ＥＣＰ 能很好地区分聚类质量的差距。 因此，与 ＳｉｇＣｌｕｓｔ 相比，ＥＣＰ 不仅能处理 ｋ ＞ ２ 的情 况，而且能更好地评估聚类质量。 表 ４ ＥＣＰ 与最大熵方法对比 Ｔａｂｌｅ ４ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＥＣＰ ａｎｄ ｍａｘｉｍｕｍ ｅｎｔｒｏｐｙ ｍｅｔｈｏｄ 算法 ｉｒｉｓ ｗｉｎｅ ｙｅａｓｔ 最大熵 ０．００１ ０．００１ ０．００１ 最大熵 拟合正态 ４．８９１ ８１７ｅ⁃０５ ０．３７０ ０３５ ２ ０．００２ ６２６ ６５５ ＥＣＰ ０．０４２ ７４２ １３ １．９８８ ７７３ｅ⁃０５ ６．９３７ ８７３ｅ⁃０５ 表 ５ ＥＣＰ 与 Ｓｉｇｃｌｕｓｔ 对比 Ｔａｂｌｅ ５ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＥＣＰ ａｎｄ Ｓｉｇｃｌｕｓｔ 数据 ｐ⁃ｖａｌｕｅ ／ ＥＣＰ ｐ⁃ｖａｌｕｅ ／ Ｓｉｇｃｌｕｓｔ Ｓｉｇｃｌｕｓｔ ｆ⁃ｓｃｏｒｅ ａｃｃｕｒａｃｙ Ｉｒｉｓ ０．１１４ ５７２ ８ ０ ２ １ ０．１２１ ６８８ １ ０ １．８ ０．９ ０．１５７ １６８ ９ １ １．３６ ０．６８ ０．２２８ ２９６ ５ １ １．１５８ ６５ ０．５８ ｗｉｎｅ ０．００１ ５３４ ７８３ ０ １．８７６ ８１ ０．９３８ ４６２ ０．００２ ８７８ ４９６ ０．１９９ ２ １．６７３ ６６ ０．８３８ ４６２ ０．００６ ０８２ ３５６ １ １．４３０ ７４ ０．７１５ ３８５ ０．２２１ ６５６ １ １．０１１ ６４ ０．５４６ １５４ ｙｅａｓｔ ０．００６ ７６１ ９９３ ０ １．１３０ ０５ ０．５６７ ２６５ ０．０１０ ７７５ １ １ １．０７７ ８６ ０．５３９ ２３８ ０．０１２ ５４９ ８７ １ １．０７３ ４８ ０．５３６ ９９６ ０．２５６ ４０６ ２ １ １．０４４ ０３ ０．５２２ ４２２ ４．３．３ ＥＣＰ 与 ＥＣＰ１ 对比 这一部分说明 ＥＣＰ 比加速的 ＥＣＰ１ 在效率上 有很大提高。 ＥＣＰ１ 是未加速的 ＥＣＰ 算法。 本文将 这两种算法进行了效率上的对比。 实验结果如表 ６。 实验分别用两种算法抽样 １００ ０００ 次并得到对 应的统计值。 可以看出，对于 ｉｒｉｓ 数据集，ＥＣＰ 比 ＥＣＰ１ 快了 ６０ 倍。 可见 ＥＣＰ 在效率上有质的提升。 表 ６ ＥＣＰ 与 ＥＣＰ１ 效率对比 Ｔａｂｌｅ ６ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＥＣＰ ａｎｄ ＥＣＰ１ 算法 ｉｒｉｓ ｗｉｎｅ ｙｅａｓｔ ＥＣＰ１ １８ ｓ ５０ ｓ ５６ｓ ＥＣＰ １１０９ ｓ ７３４ ｓ ２８０ ｍ ５ 结束语 本文提出了一种新的基于置换检验的聚类结果 评估方法 ＥＣＰ。 为了增大抽样的数目，利用 ＤＢ⁃Ｉｎ⁃ ｄｅｘ 的计算特点减小了对样本函数值计算的复杂 度。 为了得到更精确的 ｐ ⁃ｖａｌｕｅ，根据聚类划分的特 点，假设了 ＤＢ⁃Ｉｎｄｅｘ 的函数值是符合高斯分布的， 进而可以用较少的抽样估出更为准确的 ｐ ⁃ｖａｌｕｅ。 从实验的结果来看，ＥＣＰ 对评估聚类结果有很好的 效果，并且具有很强的实用性。 参考文献： ［１］ＴＡＮ Ｐａｎｇｎｉｎｇ， ＳＴＥＩＮＢＡＣＨ Ｍ， ＫＵＭＡＲ Ｖ． Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｄａｔａ ｍｉｎｉｎｇ［Ｍ］． Ｂｏｓｔｏｎ： Ａｄｄｉｓｏｎ⁃Ｗｅｓｌｅｙ， ２００５． ［ ２］ ＨＡＮ Ｊｉａｗｅｉ， ＫＡＭＢＥＲ Ｍ， ＰＥＩ Ｊｉａｎ． Ｄａｔａ ｍｉｎｉｎｇ： ｃｏｎ⁃ ｃｅｐｔｓ ａｎｄ ｔｅｃｈｎｉｑｕｅｓ［Ｍ］． ３ｒｄ ｅｄ． Ｂｕｒｌｉｎｇｔｏｎ， ＭＡ， ＵＳＡ： Ｅｌｓｅｖｉｅｒ， ２０１２： １⁃３３． ［３］尹宏伟， 李凡长． 谱机器学习研究综述［ Ｊ］． 计算机科学 与探索， ２０１５， ９（１２）： １４０９⁃１４１９． ＹＩＮ Ｈｏｎｇｗｅｉ， ＬＩ Ｆａｎｚｈａｎｇ． Ｓｕｒｖｅｙ ｏｎ ｓｐｅｃｔｒａｌ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｆｒｏｎｔｉｅｒｓ ｏｆ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ， ２０１５， ９（１２）： １４０９⁃１４１９． ［４］ＪＡＩＮ Ａ Ｋ， ＭＵＲＴＹ Ｍ Ｎ， ＦＬＹＮＮ Ｐ Ｊ． Ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ： ａ ｒｅｖｉｅｗ［Ｊ］． ＡＣＭ ｃｏｍｐｕｔｉｎｇ ｓｕｒｖｅｙｓ， １９９９， ３１（ ３）： ２６４⁃ ３２３． ［５］ＷＵ Ｘｉｎｄｏｎｇ， ＫＵＭＡＲ Ｖ， ＱＵＩＮＬＡＮ Ｊ Ｒ， ｅｔ ａｌ． Ｔｏｐ １０ ａｌ⁃ ｇｏｒｉｔｈｍｓ ｉｎ ｄａｔａ ｍｉｎｉｎｇ［Ｊ］． Ｋｎｏｗｌｅｄｇｅ ａｎｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓ⁃ ｔｅｍｓ， ２００８， １４（１）： １⁃３７． ［６］ ＨＡＬＫＩＤＩ Ｍ， ＢＡＴＩＳＴＡＫＩＳ Ｙ， ＶＡＺＩＲＧＩＡＮＮＩＳ Ｍ． Ｏｎ ｃｌｕｓｔｅｒｉｎｇ ｖａｌｉｄａｔｉｏｎ ｔｅｃｈｎｉｑｕｅｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｉｎｔｅｌｌｉｇｅｎｔ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ， ２００１， １７（２⁃３）： １０７⁃１４５． ［７］ＨＡＮＤＬ Ｊ， ＫＮＯＷＬＥＳ Ｊ， ＫＥＬＬ Ｄ Ｂ． Ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｌｕｓｔｅｒ ｖａｌｉｄａｔｉｏｎ ｉｎ ｐｏｓｔ⁃ｇｅｎｏｍｉｃ ｄａｔａ ａｎａｌｙｓｉｓ［Ｊ］． Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ， ２００５， ２１（１５）： ３２０１⁃３２１２． ［８］ＫＯＮＴＯＮＡＳＩＯＳ Ｋ Ｎ， ＶＲＥＥＫＥＮ Ｊ， ＤＥ ＢＩＥ Ｔ． Ｍａｘｉｍｕｍ ｅｎｔｒｏｐｙ ｍｏｄｅｌｌｉｎｇ ｆｏｒ ａｓｓｅｓｓｉｎｇ ｒｅｓｕｌｔｓ ｏｎ ｒｅａｌ⁃ｖａｌｕｅｄ ｄａｔａ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １１ｔｈ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｄａｔａ ｍｉｎｉｎｇ． Ｖａｎｃｏｕｖｅｒ， ＢＣ， Ｃａｎａｄａ， ２０１１： ３５０⁃３５９． ·３０８· 智 能 系 统 学 报 第 １１ 卷
第3期 谷飞洋，等：基于置换检验的聚类结果评估 .309. [9]OJALA M.Assessing data mining results on matrices with Bioinformatics,2009,25(12):i161-i168. randomization[C]//Proceedings of international conference [15]ASUNCION A,NEWMAN D J.UCI machine leaming re- on data mining.Sydney,Australia,2010:959-964. pository[EB/OL].2007.http://archive.ics.uci.edu/ml/. [10]OJALA M,VUOKKO N,KALLIO A,et al.Randomiza- 作者简介： tion methods for assessing data analysis results on real-val- 谷飞洋，男，1991年生，硕士研究 ued matrices [J].Statistical analysis and data mining, 生，主要研究方向是数据挖掘和生物 2009,2(4):209-230. 信息。 [11]LIU Yufeng,HAYES D N,NOBEL A,et al.Statistical significance of clustering for high-dimension,low-sample size data[J].Journal of the American statistical associa- ion,2008,103(483):1281-1293. [12]PARK P J,MANJOURIDES J,BOONETTI M,et al.A 田博，女，1992年生，硕士研究生， permutation test for determining significance of clusters 主要研究方向为数据挖掘和生物信息。 with applications to spatial and gene expression data[J]. Computational statistics data analysis,2009,53(12): 4290-4300. [13]张刚，刘悦，郭嘉丰，等.一种层次化的检索结果聚类 方法[J].计算机研究与发展，2008,45(3)：542-547. ZHANG Gang,LIU Yue,GUO Jiafeng,et al.A Hierar- 何增有，男，1976年生，副教授，主 chical search result clustering method[J].Journal of com- 要研究方向为数据挖掘和生物信息学， puter research and development,2008,45(3):542-547. 学术论文均发表在该领域的顶级期刊 [14]KNIJNENBURG T A,WESSELS L F A,REINDERS M J 或会议上，出版学术专著1部。 T,et al.Fewer permutations,more accurate p-values[J]. 2016年第九届SPE机器学习国际会议 2016 The 9th International Conference on Machine Vision (ICMV 2016) Welcome to the official website for 2016 The 9th International Conference on Machine Vision (ICMV 2016).ICMV conference is ini- tiated by School of Electronics,Si Chuan University,China,assisted by Halmstad University,Sweden,University of Barcelona,Spain. This is the annual conference started in 2007(Islamabad,Pakistan),ICMV 2009 (Dubai,UAE),ICMV 2010 (Hong Kong),ICMV 2011 (Singapore),ICMV 2012 (Wuhan,China),ICMV 2013 London,UK),ICMV 2014 Milano,Italy),ICMV 2015 (Barcelona, Spain).ICMV 2016 will take place in Nice,France during November 18-20,2016,the conference chairs are Prof.Antanas Verikas, Halmstad University,Sweden,Prof.Petia Radeva,University of Barcelona,Spain and Prof.Dmitry Nikolaev,Russian Academy of Sci- ence,Russia. The emergence of Machine Vision as a ubiquitous platform for innovations has laid the foundation for the rapid growth of the Informa- tion.Side-by-side,the use of mobile and wireless devices such as PDA,laptop,and cell phones for accessing the Intemet has paved the ways for related technologies to flourish through recent developments.In addition,the Machine Vision Technology is promoting better inte- gration of the digital world with physical environment.This conference serves to foster communication among researchers and practitioners working in a wide variety of scientific areas with a common interest in improving Machine Vision related techniques. High quality,original papers are solicited in all areas of Machine Vision.The final program will be the result of a highly selective re- view process designed to include the best work of its kind in every category.The program will include invited talks as well as oral and poster presentations of refereed papers. Website:http://www.icmv.org/index.html
［９］ＯＪＡＬＡ Ｍ． Ａｓｓｅｓｓｉｎｇ ｄａｔａ ｍｉｎｉｎｇ ｒｅｓｕｌｔｓ ｏｎ ｍａｔｒｉｃｅｓ ｗｉｔｈ ｒａｎｄｏｍｉｚａｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｄａｔａ ｍｉｎｉｎｇ． Ｓｙｄｎｅｙ， Ａｕｓｔｒａｌｉａ， ２０１０： ９５９⁃９６４． ［１０］ ＯＪＡＬＡ Ｍ， ＶＵＯＫＫＯ Ｎ， ＫＡＬＬＩＯ Ａ， ｅｔ ａｌ． Ｒａｎｄｏｍｉｚａ⁃ ｔｉｏｎ ｍｅｔｈｏｄｓ ｆｏｒ ａｓｓｅｓｓｉｎｇ ｄａｔａ ａｎａｌｙｓｉｓ ｒｅｓｕｌｔｓ ｏｎ ｒｅａｌ⁃ｖａｌ⁃ ｕｅｄ ｍａｔｒｉｃｅｓ ［ Ｊ ］． Ｓｔａｔｉｓｔｉｃａｌ ａｎａｌｙｓｉｓ ａｎｄ ｄａｔａ ｍｉｎｉｎｇ， ２００９， ２（４）： ２０９⁃２３０． ［１１］ＬＩＵ Ｙｕｆｅｎｇ， ＨＡＹＥＳ Ｄ Ｎ， ＮＯＢＥＬ Ａ， ｅｔ ａｌ． Ｓｔａｔｉｓｔｉｃａｌ ｓｉｇｎｉｆｉｃａｎｃｅ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ｆｏｒ ｈｉｇｈ⁃ｄｉｍｅｎｓｉｏｎ， ｌｏｗ⁃ｓａｍｐｌｅ ｓｉｚｅ ｄａｔａ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ Ａｍｅｒｉｃａｎ ｓｔａｔｉｓｔｉｃａｌ ａｓｓｏｃｉａ⁃ ｔｉｏｎ， ２００８， １０３（４８３）： １２８１⁃１２９３． ［１２］ ＰＡＲＫ Ｐ Ｊ， ＭＡＮＪＯＵＲＩＤＥＳ Ｊ， ＢＯＯＮＥＴＴＩ Ｍ， ｅｔ ａｌ． Ａ ｐｅｒｍｕｔａｔｉｏｎ ｔｅｓｔ ｆｏｒ ｄｅｔｅｒｍｉｎｉｎｇ ｓｉｇｎｉｆｉｃａｎｃｅ ｏｆ ｃｌｕｓｔｅｒｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ ｔｏ ｓｐａｔｉａｌ ａｎｄ ｇｅｎｅ ｅｘｐｒｅｓｓｉｏｎ ｄａｔａ［ Ｊ］． Ｃｏｍｐｕｔａｔｉｏｎａｌ ｓｔａｔｉｓｔｉｃｓ ＆ ｄａｔａ ａｎａｌｙｓｉｓ， ２００９， ５３（１２）： ４２９０⁃４３００． ［１３］张刚， 刘悦， 郭嘉丰， 等． 一种层次化的检索结果聚类 方法［Ｊ］． 计算机研究与发展， ２００８， ４５（３）： ５４２⁃５４７． ＺＨＡＮＧ Ｇａｎｇ， ＬＩＵ Ｙｕｅ， ＧＵＯ Ｊｉａｆｅｎｇ， ｅｔ ａｌ． Ａ Ｈｉｅｒａｒ⁃ ｃｈｉｃａｌ ｓｅａｒｃｈ ｒｅｓｕｌｔ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍ⁃ ｐｕｔｅｒ ｒｅｓｅａｒｃｈ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ， ２００８， ４５（３）： ５４２⁃５４７． ［１４］ＫＮＩＪＮＥＮＢＵＲＧ Ｔ Ａ， ＷＥＳＳＥＬＳ Ｌ Ｆ Ａ， ＲＥＩＮＤＥＲＳ Ｍ Ｊ Ｔ， ｅｔ ａｌ． Ｆｅｗｅｒ ｐｅｒｍｕｔａｔｉｏｎｓ， ｍｏｒｅ ａｃｃｕｒａｔｅ ｐ ⁃ｖａｌｕｅｓ［Ｊ］． Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ， ２００９， ２５（１２）： ｉ１６１⁃ｉ１６８． ［１５］ＡＳＵＮＣＩＯＮ Ａ， ＮＥＷＭＡＮ Ｄ Ｊ． ＵＣＩ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｒｅ⁃ ｐｏｓｉｔｏｒｙ［ＥＢ／ ＯＬ］． ２００７． ｈｔｔｐ： ／ ／ ａｒｃｈｉｖｅ．ｉｃｓ．ｕｃｉ．ｅｄｕ ／ ｍｌ ／ ． 作者简介： 谷飞洋，男，１９９１ 年生，硕士研究 生，主要研究方向是数据挖掘和生物 信息。 田博，女，１９９２ 年生，硕士研究生， 主要研究方向为数据挖掘和生物信息。 何增有，男，１９７６ 年生，副教授，主 要研究方向为数据挖掘和生物信息学， 学术论文均发表在该领域的顶级期刊 或会议上，出版学术专著 １ 部。 ２０１６ 年第九届 ＳＰＩＥ 机器学习国际会议 ２０１６ Ｔｈｅ ９ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｖｉｓｉｏｎ （ＩＣＭＶ ２０１６） Ｗｅｌｃｏｍｅ ｔｏ ｔｈｅ ｏｆｆｉｃｉａｌ ｗｅｂｓｉｔｅ ｆｏｒ ２０１６ Ｔｈｅ ９ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｖｉｓｉｏｎ （ＩＣＭＶ ２０１６）． ＩＣＭＶ ｃｏｎｆｅｒｅｎｃｅ ｉｓ ｉｎｉ⁃ ｔｉａｔｅｄ ｂｙ Ｓｃｈｏｏｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ， Ｓｉ Ｃｈｕａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｃｈｉｎａ， ａｓｓｉｓｔｅｄ ｂｙ Ｈａｌｍｓｔａｄ Ｕｎｉｖｅｒｓｉｔｙ， Ｓｗｅｄｅｎ， Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｂａｒｃｅｌｏｎａ， Ｓｐａｉｎ． Ｔｈｉｓ ｉｓ ｔｈｅ ａｎｎｕａｌ ｃｏｎｆｅｒｅｎｃｅ ｓｔａｒｔｅｄ ｉｎ ２００７（Ｉｓｌａｍａｂａｄ，Ｐａｋｉｓｔａｎ），ＩＣＭＶ ２００９ （Ｄｕｂａｉ， ＵＡＥ）， ＩＣＭＶ ２０１０ （Ｈｏｎｇ Ｋｏｎｇ）， ＩＣＭＶ ２０１１ （Ｓｉｎｇａｐｏｒｅ）， ＩＣＭＶ ２０１２ （ Ｗｕｈａｎ， Ｃｈｉｎａ）， ＩＣＭＶ ２０１３ （ Ｌｏｎｄｏｎ， ＵＫ），ＩＣＭＶ ２０１４ （Ｍｉｌａｎｏ， Ｉｔａｌｙ）， ＩＣＭＶ ２０１５ （ Ｂａｒｃｅｌｏｎａ， Ｓｐａｉｎ）． ＩＣＭＶ ２０１６ ｗｉｌｌ ｔａｋｅ ｐｌａｃｅ ｉｎ Ｎｉｃｅ， Ｆｒａｎｃｅ ｄｕｒｉｎｇ Ｎｏｖｅｍｂｅｒ １８⁃２０，２０１６， ｔｈｅ ｃｏｎｆｅｒｅｎｃｅ ｃｈａｉｒｓ ａｒｅ Ｐｒｏｆ． Ａｎｔａｎａｓ Ｖｅｒｉｋａｓ， Ｈａｌｍｓｔａｄ Ｕｎｉｖｅｒｓｉｔｙ， Ｓｗｅｄｅｎ， Ｐｒｏｆ． Ｐｅｔｉａ Ｒａｄｅｖａ， Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｂａｒｃｅｌｏｎａ， Ｓｐａｉｎ ａｎｄ Ｐｒｏｆ． Ｄｍｉｔｒｙ Ｎｉｋｏｌａｅｖ， Ｒｕｓｓｉａｎ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉ⁃ ｅｎｃｅ， Ｒｕｓｓｉａ． Ｔｈｅ ｅｍｅｒｇｅｎｃｅ ｏｆ Ｍａｃｈｉｎｅ Ｖｉｓｉｏｎ ａｓ ａ ｕｂｉｑｕｉｔｏｕｓ ｐｌａｔｆｏｒｍ ｆｏｒ ｉｎｎｏｖａｔｉｏｎｓ ｈａｓ ｌａｉｄ ｔｈｅ ｆｏｕｎｄａｔｉｏｎ ｆｏｒ ｔｈｅ ｒａｐｉｄ ｇｒｏｗｔｈ ｏｆ ｔｈｅ Ｉｎｆｏｒｍａ⁃ ｔｉｏｎ． Ｓｉｄｅ⁃ｂｙ⁃ｓｉｄｅ， ｔｈｅ ｕｓｅ ｏｆ ｍｏｂｉｌｅ ａｎｄ ｗｉｒｅｌｅｓｓ ｄｅｖｉｃｅｓ ｓｕｃｈ ａｓ ＰＤＡ， ｌａｐｔｏｐ， ａｎｄ ｃｅｌｌ ｐｈｏｎｅｓ ｆｏｒ ａｃｃｅｓｓｉｎｇ ｔｈｅ Ｉｎｔｅｒｎｅｔ ｈａｓ ｐａｖｅｄ ｔｈｅ ｗａｙｓ ｆｏｒ ｒｅｌａｔｅｄ ｔｅｃｈｎｏｌｏｇｉｅｓ ｔｏ ｆｌｏｕｒｉｓｈ ｔｈｒｏｕｇｈ ｒｅｃｅｎｔ ｄｅｖｅｌｏｐｍｅｎｔｓ． Ｉｎ ａｄｄｉｔｉｏｎ， ｔｈｅ Ｍａｃｈｉｎｅ Ｖｉｓｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ ｉｓ ｐｒｏｍｏｔｉｎｇ ｂｅｔｔｅｒ ｉｎｔｅ⁃ ｇｒａｔｉｏｎ ｏｆ ｔｈｅ ｄｉｇｉｔａｌ ｗｏｒｌｄ ｗｉｔｈ ｐｈｙｓｉｃａｌ ｅｎｖｉｒｏｎｍｅｎｔ． Ｔｈｉｓ ｃｏｎｆｅｒｅｎｃｅ ｓｅｒｖｅｓ ｔｏ ｆｏｓｔｅｒ ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｍｏｎｇ ｒｅｓｅａｒｃｈｅｒｓ ａｎｄ ｐｒａｃｔｉｔｉｏｎｅｒｓ ｗｏｒｋｉｎｇ ｉｎ ａ ｗｉｄｅ ｖａｒｉｅｔｙ ｏｆ ｓｃｉｅｎｔｉｆｉｃ ａｒｅａｓ ｗｉｔｈ ａ ｃｏｍｍｏｎ ｉｎｔｅｒｅｓｔ ｉｎ ｉｍｐｒｏｖｉｎｇ Ｍａｃｈｉｎｅ Ｖｉｓｉｏｎ ｒｅｌａｔｅｄ ｔｅｃｈｎｉｑｕｅｓ． Ｈｉｇｈ ｑｕａｌｉｔｙ， ｏｒｉｇｉｎａｌ ｐａｐｅｒｓ ａｒｅ ｓｏｌｉｃｉｔｅｄ ｉｎ ａｌｌ ａｒｅａｓ ｏｆ Ｍａｃｈｉｎｅ Ｖｉｓｉｏｎ． Ｔｈｅ ｆｉｎａｌ ｐｒｏｇｒａｍ ｗｉｌｌ ｂｅ ｔｈｅ ｒｅｓｕｌｔ ｏｆ ａ ｈｉｇｈｌｙ ｓｅｌｅｃｔｉｖｅ ｒｅ⁃ ｖｉｅｗ ｐｒｏｃｅｓｓ ｄｅｓｉｇｎｅｄ ｔｏ ｉｎｃｌｕｄｅ ｔｈｅ ｂｅｓｔ ｗｏｒｋ ｏｆ ｉｔｓ ｋｉｎｄ ｉｎ ｅｖｅｒｙ ｃａｔｅｇｏｒｙ． Ｔｈｅ ｐｒｏｇｒａｍ ｗｉｌｌ ｉｎｃｌｕｄｅ ｉｎｖｉｔｅｄ ｔａｌｋｓ ａｓ ｗｅｌｌ ａｓ ｏｒａｌ ａｎｄ ｐｏｓｔｅｒ ｐｒｅｓｅｎｔａｔｉｏｎｓ ｏｆ ｒｅｆｅｒｅｅｄ ｐａｐｅｒｓ． Ｗｅｂｓｉｔｅ： ｈｔｔｐ：／ ／ ｗｗｗ．ｉｃｍｖ．ｏｒｇ ／ ｉｎｄｅｘ．ｈｔｍｌ 第 ３ 期 谷飞洋，等：基于置换检验的聚类结果评估 ·３０９·