第12卷第1期 智能系统学报 Vol.12 No.1 2017年2月 CAAI Transactions on Intelligent Systems Feb.2017 D0I:10.11992/is.201611007 网络出版地址：http://kns.cmki.net/kcms/detail/23.1538.TP.20170227.2211.022.html 最近最远得分的聚类性能评价指标 冯柳伟2，常冬霞12，邓勇3，赵耀2 (1.北京交通大学信息科学研究所，北京100044：2.北京交通大学计算机与信息科学学院，北京100044；3.中国科 学院软件研究所，北京100190) 摘要：聚类算法是数据分析中广泛使用的方法之一，而类别数往往是决定聚类算法性能的关键。目前，大部分聚 类算法需要预先给定类别数，在很多情况下，很难根据数据集的先验知识获得有效的类别数。因此，为了获得数据 集的类别数，本文基于最近邻一致性和最远邻相异性的准则，提出了一种最近最远得分评价指标，并在此基础上提 出了一种自动确定类别数的聚类算法。实验结果证明了所提评价指标在确定类别数时的有效性和可行性。 关键词：最近邻一致性；最远邻相异性：K-means聚类算法；评分机制；评价指标：层次聚类 中图分类号：TP391文献标志码：A文章编号：1673-4785(2017)01-0067-08 中文引用格式：冯柳伟，常冬霞，邓勇，等.最近最远得分的聚类性能评价指标[J].智能系统学报，2017,12(1)：67-74. 英文引用格式：FENGLiuwei,CHANG Dongxia,DENG Yong,etal.A clustering evaluation index based on the nearest and furthest score [J].CAAI Transactions on Intelligent Systems,2017,12(1):67-74. A clustering evaluation index based on the nearest and furthest score FENG Liuwei 23,CHANG Dongxia3,DENG Yong',ZHAO Yao23 (1.Institute of Information Science,Beijing Jiaotong University Beijing 100044,China;2.School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China;3.Institute of Software,Chinese Academy of Sciences,Beijing 100190,China) Abstract:The clustering algorithm is one of the widely-used methods in data analysis.However,the number of clusters is essential to determine the performance of the clustering algorithm.At present,the number of clusters usually need to be specified in advance.In most cases,it is difficult to obtain the valid cluster number according to a priori knowledge of the dataset.To obtain the number of clusters automatically,a Nearest and Furthest Score (NFS)index was proposed based on the principles of the nearest neighbor consistency and the furthest neighbor difference.Moreover,an Automatic Clustering NFS (ACNFS)algorithm was also proposed,which can determine the number of clusters automatically.The experimental results prove the index is reasonable and practicable to determine the cluster number. Keywords:the nearest neighbor consistency;the furthest neighbor difference;K-means clustering algorithm; scoring mechanism;evaluation index:hierarchical clustering 聚类算法作为数据分析中广泛使用的主要方数据间的相似度尽可能大，而不同类别数据间的相 法之一，已经广泛应用于模式识别、机器学习、图像 似度则尽可能小。目前，常用聚类算法可以分为划 处理和数据挖掘等方面1。简单来说，聚类就是 分法、层次法、基于密度的方法、基于网格的方法和 根据数据的特征将数据划分为几类，使得同一类别 基于模型的方法。事实上，很多聚类算法往往需要 预先知道聚类问题的类别数。然而，在很多实际情 收稿日期：2016-11-07.网络出版日期：2017-02-27. 况下，很难根据数据特征获得有效的类别数。因 基金项目：国家自然科学基金“重点”项目(61532005). 通信作者：常冬霞.E-mail:dxchange@bjtu.cdu.cn. 此，为了获得有效的类别数，很多学者基于聚类的
第 １２ 卷第 １ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．１ ２０１７ 年 ２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｆｅｂ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６１１００７ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０２２７．２２１１．０２２．ｈｔｍｌ 最近最远得分的聚类性能评价指标 冯柳伟１，２ ，常冬霞１，２ ，邓勇３ ，赵耀１，２ （１． 北京交通大学 信息科学研究所，北京 １０００４４；２． 北京交通大学 计算机与信息科学学院，北京 １０００４４； ３．中国科 学院 软件研究所，北京 １００１９０） 摘 要：聚类算法是数据分析中广泛使用的方法之一，而类别数往往是决定聚类算法性能的关键。 目前，大部分聚 类算法需要预先给定类别数，在很多情况下，很难根据数据集的先验知识获得有效的类别数。 因此，为了获得数据 集的类别数，本文基于最近邻一致性和最远邻相异性的准则，提出了一种最近最远得分评价指标，并在此基础上提 出了一种自动确定类别数的聚类算法。 实验结果证明了所提评价指标在确定类别数时的有效性和可行性。 关键词：最近邻一致性；最远邻相异性；Ｋ⁃ｍｅａｎｓ 聚类算法；评分机制；评价指标；层次聚类 中图分类号： ＴＰ３９１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０１－００６７－０８ 中文引用格式：冯柳伟，常冬霞，邓勇，等．最近最远得分的聚类性能评价指标［Ｊ］． 智能系统学报， ２０１７， １２（１）： ６７－７４． 英文引用格式：ＦＥＮＧ Ｌｉｕｗｅｉ， ＣＨＡＮＧ Ｄｏｎｇｘｉａ， ＤＥＮＧ Ｙｏｎｇ，ｅｔ ａｌ． Ａ ｃｌｕｓｔｅｒｉｎｇ ｅｖａｌｕａｔｉｏｎ ｉｎｄｅｘ ｂａｓｅｄ ｏｎ ｔｈｅ ｎｅａｒｅｓｔ ａｎｄ ｆｕｒｔｈｅｓｔ ｓｃｏｒｅ ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１７， １２（１）： ６７－７４． Ａ ｃｌｕｓｔｅｒｉｎｇ ｅｖａｌｕａｔｉｏｎ ｉｎｄｅｘ ｂａｓｅｄ ｏｎ ｔｈｅ ｎｅａｒｅｓｔ ａｎｄ ｆｕｒｔｈｅｓｔ ｓｃｏｒｅ ＦＥＮＧ Ｌｉｕｗｅｉ １，２，３ ，ＣＨＡＮＧ Ｄｏｎｇｘｉａ １，２，３ ， ＤＥＮＧ Ｙｏｎｇ ４ ， ＺＨＡＯ Ｙａｏ １，２，３ （１． Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ， Ｂｅｉｊｉｎｇ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ Ｂｅｉｊｉｎｇ １０００４４， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ， Ｂｅｉｊｉｎｇ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｂｅｉｊｉｎｇ １０００４４， Ｃｈｉｎａ； ３． Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｏｆｔｗａｒｅ， Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ， Ｂｅｉｊｉｎｇ １００１９０， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｗｉｄｅｌｙ⁃ｕｓｅｄ ｍｅｔｈｏｄｓ ｉｎ ｄａｔａ ａｎａｌｙｓｉｓ． Ｈｏｗｅｖｅｒ， ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ｉｓ ｅｓｓｅｎｔｉａｌ ｔｏ ｄｅｔｅｒｍｉｎｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ． Ａｔ ｐｒｅｓｅｎｔ， ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ｕｓｕａｌｌｙ ｎｅｅｄ ｔｏ ｂｅ ｓｐｅｃｉｆｉｅｄ ｉｎ ａｄｖａｎｃｅ． Ｉｎ ｍｏｓｔ ｃａｓｅｓ， ｉｔ ｉｓ ｄｉｆｆｉｃｕｌｔ ｔｏ ｏｂｔａｉｎ ｔｈｅ ｖａｌｉｄ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ ａｃｃｏｒｄｉｎｇ ｔｏ ａ ｐｒｉｏｒｉ ｋｎｏｗｌｅｄｇｅ ｏｆ ｔｈｅ ｄａｔａｓｅｔ． Ｔｏ ｏｂｔａｉｎ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ａｕｔｏｍａｔｉｃａｌｌｙ， ａ Ｎｅａｒｅｓｔ ａｎｄ Ｆｕｒｔｈｅｓｔ Ｓｃｏｒｅ （ＮＦＳ） ｉｎｄｅｘ ｗａｓ ｐｒｏｐｏｓｅｄ ｂａｓｅｄ ｏｎ ｔｈｅ ｐｒｉｎｃｉｐｌｅｓ ｏｆ ｔｈｅ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｃｏｎｓｉｓｔｅｎｃｙ ａｎｄ ｔｈｅ ｆｕｒｔｈｅｓｔ ｎｅｉｇｈｂｏｒ ｄｉｆｆｅｒｅｎｃｅ． Ｍｏｒｅｏｖｅｒ， ａｎ Ａｕｔｏｍａｔｉｃ Ｃｌｕｓｔｅｒｉｎｇ ＮＦＳ （ＡＣＮＦＳ） ａｌｇｏｒｉｔｈｍ ｗａｓ ａｌｓｏ ｐｒｏｐｏｓｅｄ， ｗｈｉｃｈ ｃａｎ ｄｅｔｅｒｍｉｎｅ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ａｕｔｏｍａｔｉｃａｌｌｙ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｐｒｏｖｅ ｔｈｅ ｉｎｄｅｘ ｉｓ ｒｅａｓｏｎａｂｌｅ ａｎｄ ｐｒａｃｔｉｃａｂｌｅ ｔｏ ｄｅｔｅｒｍｉｎｅ ｔｈｅ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ． Ｋｅｙｗｏｒｄｓ： ｔｈｅ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｃｏｎｓｉｓｔｅｎｃｙ； ｔｈｅ ｆｕｒｔｈｅｓｔ ｎｅｉｇｈｂｏｒ ｄｉｆｆｅｒｅｎｃｅ； Ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ； ｓｃｏｒｉｎｇ ｍｅｃｈａｎｉｓｍ； ｅｖａｌｕａｔｉｏｎ ｉｎｄｅｘ； ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅｒｉｎｇ 收稿日期：２０１６－１１－０７． 网络出版日期：２０１７－０２－２７． 基金项目：国家自然科学基金“重点”项目（６１５３２００５）． 通信作者：常冬霞． Ｅ⁃ｍａｉｌ：ｄｘｃｈａｎｇ＠ ｂｊｔｕ．ｅｄｕ．ｃｎ． 聚类算法作为数据分析中广泛使用的主要方 法之一，已经广泛应用于模式识别、机器学习、图像 处理和数据挖掘等方面［１－４］ 。 简单来说，聚类就是 根据数据的特征将数据划分为几类，使得同一类别 数据间的相似度尽可能大，而不同类别数据间的相 似度则尽可能小。 目前，常用聚类算法可以分为划 分法、层次法、基于密度的方法、基于网格的方法和 基于模型的方法。 事实上，很多聚类算法往往需要 预先知道聚类问题的类别数。 然而，在很多实际情 况下，很难根据数据特征获得有效的类别数。 因 此，为了获得有效的类别数，很多学者基于聚类的
·68 智能系统学报 第12卷 不同性质分别提出了一系列评价聚类结果的评价 BWP指标和IGP指标等。 指标。对给定范围的类别数依次对数据集进行聚 l.1 Calinski-Harabasz(CH)指标 类，并采用评价指标对每次的聚类结果进行评价， CH指标是Calinski和Harabasz提出的确定最 然后选择一个使评价指标最优的类别数。目前，常 佳聚类数的评价指标。该指标是一种基于样本 用有效性评价指标大致可以分为3种类型，分别是 的类内距离和类间离差矩阵的测度，其判断函数为 基于数据集模糊划分的指标、基于数据集样本几何 CH(k)= BGSS WGSS (1) 结构的指标和基于数据集统计信息的指标。其中， -1'n-K 1991年，Xie等利用模糊聚类的目标函数，同时考 式中：n为数据集样本数，K为类别数。且 虑数据集本身的结构和模糊隶属度的性质，提出了 Xie-Beni指标。之后，很多学者基于数据集模糊划 WGSs=2[(m,-1)d+…+(mk-1)d] 分提出了一系列改善的评价指标[6]，但这些指标 不适合对硬聚类算法的聚类结果进行评价。另外 BGS5-[(-1)+(n-K)A] -类是基于数据集样本几何结构的评价指标[1c6 式中：d是第j类中样本间的平均距离，j=1,2,…, 1974年，Calinski和Harabasz提出了基于全部样本 的类内离差矩阵和类间离差矩阵测度的Calinski- k:?是所有样本间的平均距离。且Ax为 Harabasz(CH)指标2.1979年，Davies和Bouldin Ak=1Σ(n,-1)(2-) 提出了基于样本的类内散度与各聚类中心间距离 n-K台 测度的Davies-Bouldin(DB)指标[1]，以及随后提出 CH指标值越大表示聚类结果的类内距离越小 的基于最大化类内相似度和最小化类间相似度目 而类间距离越大，聚类结果性能越好。但是随着类 标的Weighted inter--intra(Wint)指标a)、基于样本 别数搜索范围的变化，CH指标得到的最佳聚类数 类内离差矩阵的Krzanowski-Lai(KL)指标1]、周世 会发生变化，并且随着搜索范围增大，CH指标得到 兵等提出的基于样本间的最小类间距离与类内距 的最佳聚类数有逐渐增大的趋势[)。 离的Between-Within Proportion(BWP)指标Ii6)。但 1.2BWP指标 是这些评价指标均具有一定的局限性，对数据结构 BWP指标是周世兵等人提出的一种基于样本 无法完全分离的数据集进行评价得到的结果并不 的几何结构设计的确定聚类类别数的评价指标[6]」 理想。2007年，Kapp等基于数据集统计的思想，使 该指标利用聚类结果的类内紧密性和类间分离性 用类内数据点的in-goup比例来评价聚类结果，提 来衡量聚类结果。指标的最大值对应的类数作为 出了n-Group Proportion(IGP)评价指标]。该评 聚类数。该指标的判断函数为 价指标使用样本与其最近邻样本划分到同一类的 BWP(K) 比例来衡量聚类结果的质量。但是由于IGP只关 n bwp(i,j) (2) 注最近邻一致性，使得IG指标值会随着聚类数的 式中：K是类别数，bwp(i,j)为 增加而减少，导致在很多实际情况下，利用IG指 b(i,j)-w(i,j) bwp(i,j) 标得到的类别数往往比实际的类别数小。针对这 b(i,j）+w(i,j） 种情况，本文基于最近邻一致性和最远邻相异性的 式中：b(i,)是第j类中的第i个样本到其他每类中 原则，提出了一种最近最远得分指标(NFS),并基于 样本平均距离的最小值，称为最小类间距；w(i,)是 此指标，提出了一种基于NFS指标自动确定类别数 第j类中的第i个样本的类内距离。且 的聚类算法。实验结果验证了本文所提的评价指 b(i,j)=, min x-x 标的有效性和可行性。 k,m产八几mp=1 1 已有评价指标 w(i,j)=- ‖xg9-9I2 众所周知，很多聚类算法需要用户根据先验知 BWP指标值越大则表示聚类结果的类内越紧 识给出算法所需要的类别数。但是，在很多实际应 密而类间越远离，聚类结果性能越好。但是该评价 用中很难获得有效的先验知识，因此，确定聚类问 指标不适合非完全分离的数据集。 题的类别数成为了聚类分析的一个研究的热点。 1.3IGP指标 目前传统的确定类别数的方法是根据评价指标来 IGP指标是Kapp提出的评价指标[)。此指标 确定类别数。至今提出的评价指标包括CH指标、 的设计思想是：当对新的样本进行分类时，新样本
不同性质分别提出了一系列评价聚类结果的评价 指标。 对给定范围的类别数依次对数据集进行聚 类，并采用评价指标对每次的聚类结果进行评价， 然后选择一个使评价指标最优的类别数。 目前，常 用有效性评价指标大致可以分为 ３ 种类型，分别是 基于数据集模糊划分的指标、基于数据集样本几何 结构的指标和基于数据集统计信息的指标。 其中， １９９１ 年，Ｘｉｅ 等［５］利用模糊聚类的目标函数，同时考 虑数据集本身的结构和模糊隶属度的性质，提出了 Ｘｉｅ⁃Ｂｅｎｉ 指标。 之后，很多学者基于数据集模糊划 分提出了一系列改善的评价指标［６⁃９］ ，但这些指标 不适合对硬聚类算法的聚类结果进行评价。 另外 一类是基于数据集样本几何结构的评价指标［１０⁃１６］ 。 １９７４ 年，Ｃａｌｉńｓｋｉ 和 Ｈａｒａｂａｓｚ 提出了基于全部样本 的类内离差矩阵和类间离差矩阵测度的 Ｃａｌｉńｓｋｉ⁃ Ｈａｒａｂａｓｚ（ＣＨ） 指标［１２］ 。 １９７９ 年，Ｄａｖｉｅｓ 和 Ｂｏｕｌｄｉｎ 提出了基于样本的类内散度与各聚类中心间距离 测度的 Ｄａｖｉｅｓ⁃Ｂｏｕｌｄｉｎ（ＤＢ）指标［１３］ ，以及随后提出 的基于最大化类内相似度和最小化类间相似度目 标的 Ｗｅｉｇｈｔｅｄ ｉｎｔｅｒ⁃ｉｎｔｒａ（ Ｗｉｎｔ） 指标［１４］ 、基于样本 类内离差矩阵的 Ｋｒｚａｎｏｗｓｋｉ⁃Ｌａｉ（ＫＬ）指标［１５］ 、周世 兵等提出的基于样本间的最小类间距离与类内距 离的 Ｂｅｔｗｅｅｎ⁃Ｗｉｔｈｉｎ Ｐｒｏｐｏｒｔｉｏｎ（ＢＷＰ） 指标［１６］ 。 但 是这些评价指标均具有一定的局限性，对数据结构 无法完全分离的数据集进行评价得到的结果并不 理想。 ２００７ 年，Ｋａｐｐ 等基于数据集统计的思想，使 用类内数据点的 ｉｎ⁃ｇｒｏｕｐ 比例来评价聚类结果，提 出了 Ｉｎ⁃Ｇｒｏｕｐ Ｐｒｏｐｏｒｔｉｏｎ（ ＩＧＰ） 评价指标［１７］ 。 该评 价指标使用样本与其最近邻样本划分到同一类的 比例来衡量聚类结果的质量。 但是由于 ＩＧＰ 只关 注最近邻一致性，使得 ＩＧＰ 指标值会随着聚类数的 增加而减少，导致在很多实际情况下，利用 ＩＧＰ 指 标得到的类别数往往比实际的类别数小。 针对这 种情况，本文基于最近邻一致性和最远邻相异性的 原则，提出了一种最近最远得分指标（ＮＦＳ），并基于 此指标，提出了一种基于 ＮＦＳ 指标自动确定类别数 的聚类算法。 实验结果验证了本文所提的评价指 标的有效性和可行性。 １ 已有评价指标 众所周知，很多聚类算法需要用户根据先验知 识给出算法所需要的类别数。 但是，在很多实际应 用中很难获得有效的先验知识，因此，确定聚类问 题的类别数成为了聚类分析的一个研究的热点。 目前传统的确定类别数的方法是根据评价指标来 确定类别数。 至今提出的评价指标包括 ＣＨ 指标、 ＢＷＰ 指标和 ＩＧＰ 指标等。 １．１ Ｃａｌｉｎｓｋｉ⁃Ｈａｒａｂａｓｚ（ＣＨ）指标 ＣＨ 指标是 Ｃａｌｉńｓｋｉ 和 Ｈａｒａｂａｓｚ 提出的确定最 佳聚类数的评价指标［１２］ 。 该指标是一种基于样本 的类内距离和类间离差矩阵的测度，其判断函数为 ＣＨ（ｋ） ＝ ＢＧＳＳ Ｋ － １ ／ ＷＧＳＳ ｎ － Ｋ （１） 式中：ｎ 为数据集样本数，Ｋ 为类别数。 且 ＷＧＳＳ ＝ １ ２ ［（ｎ１ － １） ｄ － ２ １ ＋ … ＋ （ｎＫ － １） ｄ － ２ Ｋ ］ ＢＧＳＳ ＝ １ ２ ［（Ｋ － １） ｄ － ２ ＋ （ｎ － Ｋ）ＡＫ ］ 式中：ｄ －２ ｊ 是第 ｊ 类中样本间的平均距离，ｊ ＝ １，２，…， ｋ；ｄ －２ 是所有样本间的平均距离。 且 ＡＫ 为 ＡＫ ＝ １ ｎ － Ｋ∑ Ｋ ｉ ＝ １ （ｎｉ － １）（ ｄ － ２ － ｄ － ２ ｉ ） ＣＨ 指标值越大表示聚类结果的类内距离越小 而类间距离越大，聚类结果性能越好。 但是随着类 别数搜索范围的变化，ＣＨ 指标得到的最佳聚类数 会发生变化，并且随着搜索范围增大，ＣＨ 指标得到 的最佳聚类数有逐渐增大的趋势［１８］ 。 １．２ ＢＷＰ 指标 ＢＷＰ 指标是周世兵等人提出的一种基于样本 的几何结构设计的确定聚类类别数的评价指标［１６］ ， 该指标利用聚类结果的类内紧密性和类间分离性 来衡量聚类结果。 指标的最大值对应的类数作为 聚类数。 该指标的判断函数为 ＢＷＰ（Ｋ） ＝ １ ｎ ∑ Ｋ ｊ ＝ １ ∑ ｎｊ ｉ ＝ １ ｂｗｐ（ｉ，ｊ） （２） 式中：Ｋ 是类别数，ｂｗｐ（ｉ，ｊ）为 ｂｗｐ（ｉ，ｊ） ＝ ｂ（ｉ，ｊ） － ｗ（ｉ，ｊ） ｂ（ｉ，ｊ） ＋ ｗ（ｉ，ｊ） 式中：ｂ（ｉ，ｊ）是第 ｊ 类中的第 ｉ 个样本到其他每类中 样本平均距离的最小值，称为最小类间距；ｗ（ｉ，ｊ）是 第 ｊ 类中的第 ｉ 个样本的类内距离。 且 ｂ（ｉ，ｊ） ＝ ｍｉｎ １≤ｍ≤ｋ，ｍ≠ｊ １ ｎｍ ∑ ｎｍ ｐ ＝ １ ‖ ｘ （ｍ） ｐ － ｘ （ｊ） ｉ ‖ æ è ç ö ø ÷ ｗ（ｉ，ｊ） ＝ １ ｎｊ － １ ∑ ｎｊ ｑ ＝ １，ｑ≠ｉ ‖ ｘ （ｊ） ｑ － ｘ （ｊ） ｉ ‖２ ＢＷＰ 指标值越大则表示聚类结果的类内越紧 密而类间越远离，聚类结果性能越好。 但是该评价 指标不适合非完全分离的数据集。 １．３ ＩＧＰ 指标 ＩＧＰ 指标是 Ｋａｐｐ 提出的评价指标［１７］ 。 此指标 的设计思想是：当对新的样本进行分类时，新样本 ·６８· 智 能 系 统 学 报 第 １２ 卷
第1期 冯柳伟，等：最近最远得分的聚类性能评价指标 ·69· 应该被划分到与其最相似的样本所在类别。因此 定义4每类的得分。定义cs(G)为第j类的得 该指标使用样本与其最近邻样本划分到同一类的 分，其定义为属于第j类的所有样本的得分的平均 比例来衡量聚类结果的质量。该指标的评价函数为 值，即 IGP(K)= 1 ∑ig鄂(u,X) (3) K 0 式中：K是类别数；g即(u,X)表示数据集X中的第u cs(i)=- (7) 类的指标值， 式中n:为第j类中的样本总数。 ig鄂(u,X)= (jl Classx(j)=Classx(j)=u) 定义5NFS。定义nfs(K)为在类别数为K下 (jl Classx(j)=u) 聚类结果的最近最远得分，定义为所有类得分的平 式中：是距离样本j最近的样本，Classx)表示数 均值，即 据集X中的第j个样本所属的类别。 nfs(K) cs(j) (8) IGP指标的值越大表示样本和其最近邻划分到 同一类的概率越高，聚类结果越好。但是IG指标 式中K是类别数。 只关注了最近邻一致性，使得IG指标值不适合判 2.2NFS指标的分析 断非完全分离的数据集。 NFS指标的设计原则是每个样本应该和距离其 2最近最远得分评价指标 最近的样本划分到同一类别中，而与距离其最远的 样本划分到不同类别中。因此，每个样本拥有两个 为了能准确地得到聚类问题的类别数，本文在 影响评分的因子，分别是最近得分因子和最远得分 基于最近邻一致性和最远邻相异性的原则上，提出 因子。对于最近得分因子，如果某个样本与距离其 了最近最远得分(nearest and furthest score,NFS)评 最近的样本划分到同一类中，则得1分，表示对此聚 价指标。 类结果的支持，而如果划分到不同类中，则得-1分， 2.1相关概念定义 表示对此聚类结果的反对。最远得分因子的规定 X={x1,x2,…,xn}是一个n维矢量空间的有 也是如此。 限子集，K是类别数，C={c1,c2,…,cx}是聚类算法 随着类别数的增加，样本和其最近邻样本被划 所得类别中心集合。 分到不同类别中的概率将会增加，从而导致了最近 定义1最近得分。定义ns(i)是第i个样本的 得分累积和的减少：然而随着类别数的增加，样本 最近得分，第个样本是距离其最近的样本，若样本 和其最远邻样本被划分到同一类的概率将会减少， i与样本j属于同一类别，则第i个样本的最近得分 从而导致了最远得分累积和的增加。因此，在评价 值为1：否则其最近得分值为-1，即 聚类结果时仅采用最近得分或最远得分将很难得 ns(i)= ∫1，sc(i)=sc() 到正确的类别数，需要综合利用这两个得分才能获 1-1,sc(i)≠sc(Gj) (4) 得好的聚类结果。为了说明这个问题，我们将利用 式中：sc(i)代表第i个样本所属的类别，sc()代表 图1所示的数据集在不同类别数下的聚类结果来说 距离样本i最近的样本j所属的类别。 明同时考虑最近得分和最远得分的必要性。观察 定义2最远得分。定义s(i)是第i个样本的 图1所示数据集，可知此数据集的最佳类别数为4。 最远得分，第1个样本是距离其最远的样本，若样本 如果只考虑最近邻得分时，如图1(a)所示，当K=2 i与样本1属于不同类别，则第i个样本的最远得分 时，所有样本和其最近邻样本都在同一类中，而如 值为1，否则其最远得分值-1，即 图1(b)和图1(c)所示，当K=3或K=4时，样本和 fs(i)=(-1,se(i)=se(1) 其最近邻划分到不同类的比率就会增大，聚类结果 \1,sc(i)≠sc(l) (5) 的最近得分值会下降，因此K=2时，使最近得分值 式中：sC(i)代表第i个样本所属的类别；sc(l)代表 达到最大，故采用最近得分准则所得到的最佳类别 距离样本i最远的样本1所属的类别。 数为2。而如果只考虑最远得分时，如图1(a)所 定义3样本得分。定义s(i)是第i个样本的 示，当K=2时，样本和其最远邻样本被划分到同一 得分值，则第i个样本的最近得分和最远得分的平 类的比率很大，而如图1(b)和图1(c)所示，当K=3 均值为第i个样本的得分，即 或K=4时，样本与其最远邻样本划分到同一类的比 s(i)=ns(i)+fs(i) 率下降，而且当K=3时，样本和其最远邻样本分别 (6) 划分到不同类中，此时聚类结果的最远得分值达到
应该被划分到与其最相似的样本所在类别。 因此 该指标使用样本与其最近邻样本划分到同一类的 比例来衡量聚类结果的质量。 该指标的评价函数为 ＩＧＰ（Ｋ） ＝ １ Ｋ∑ Ｋ ｕ ＝ １ ｉｇｐ（ｕ，Ｘ） （３） 式中：Ｋ 是类别数；ｉｇｐ（ｕ，Ｘ）表示数据集 Ｘ 中的第 ｕ 类的指标值，且 ｉｇｐ（ｕ，Ｘ） ＝ ｊ ｜ ＣｌａｓｓＸ（ｊ） ＝ ＣｌａｓｓＸ（ｊ Ｎ { ） ＝ ｕ} ｊ ｜ Ｃｌａｓｓ { Ｘ（ｊ） ＝ ｕ} 式中：ｊ Ｎ 是距离样本 ｊ 最近的样本，ＣｌａｓｓＸ (ｊ) 表示数 据集 Ｘ 中的第 ｊ 个样本所属的类别。 ＩＧＰ 指标的值越大表示样本和其最近邻划分到 同一类的概率越高，聚类结果越好。 但是 ＩＧＰ 指标 只关注了最近邻一致性，使得 ＩＧＰ 指标值不适合判 断非完全分离的数据集。 ２ 最近最远得分评价指标 为了能准确地得到聚类问题的类别数，本文在 基于最近邻一致性和最远邻相异性的原则上，提出 了最近最远得分（ｎｅａｒｅｓｔ ａｎｄ ｆｕｒｔｈｅｓｔ ｓｃｏｒｅ，ＮＦＳ）评 价指标。 ２．１ 相关概念定义 Ｘ ＝ ｘ１ ，ｘ２ ，…，ｘｎ { } 是一个 ｎ 维矢量空间的有 限子集，Ｋ 是类别数，Ｃ ＝ ｃ１ ，ｃ２ ，…，ｃＫ { } 是聚类算法 所得类别中心集合。 定义 １ 最近得分。 定义 ｎｓ（ｉ）是第 ｉ 个样本的 最近得分，第 ｊ 个样本是距离其最近的样本，若样本 ｉ 与样本 ｊ 属于同一类别，则第 ｉ 个样本的最近得分 值为 １；否则其最近得分值为－１，即 ｎｓ（ｉ） ＝ １， ｓｃ（ｉ） ＝ ｓｃ（ｊ） － １， ｓｃ（ｉ） ≠ ｓｃ（ｊ） { （４） 式中：ｓｃ（ｉ）代表第 ｉ 个样本所属的类别，ｓｃ（ ｊ）代表 距离样本 ｉ 最近的样本 ｊ 所属的类别。 定义 ２ 最远得分。 定义 ｆｓ（ｉ）是第 ｉ 个样本的 最远得分，第 ｌ 个样本是距离其最远的样本，若样本 ｉ 与样本 ｌ 属于不同类别，则第 ｉ 个样本的最远得分 值为 １，否则其最远得分值－１，即 ｆｓ（ｉ） ＝ － １， ｓｃ（ｉ） ＝ ｓｃ（ｌ） １， ｓｃ（ｉ） ≠ ｓｃ（ｌ） { （５） 式中：ｓｃ（ｉ）代表第 ｉ 个样本所属的类别；ｓｃ（ ｌ）代表 距离样本 ｉ 最远的样本 ｌ 所属的类别。 定义 ３ 样本得分。 定义 ｓ（ｉ）是第 ｉ 个样本的 得分值，则第 ｉ 个样本的最近得分和最远得分的平 均值为第 ｉ 个样本的得分，即 ｓ（ｉ） ＝ ｎｓ（ｉ） ＋ ｆｓ（ｉ） ２ （６） 定义 ４ 每类的得分。 定义 ｃｓ（ｊ）为第 ｊ 类的得 分，其定义为属于第 ｊ 类的所有样本的得分的平均 值，即 ｃｓ（ｊ） ＝ ∑ ｎｊ ｉ ＝ １ ｓ（ｉ） ｎｊ （７） 式中 ｎｊ 为第 ｊ 类中的样本总数。 定义 ５ ＮＦＳ。 定义 ｎｆｓ（Ｋ）为在类别数为 Ｋ 下 聚类结果的最近最远得分，定义为所有类得分的平 均值，即 ｎｆｓ（Ｋ） ＝ １ Ｋ∑ Ｋ ｊ ＝ １ ｃｓ（ｊ） （８） 式中 Ｋ 是类别数。 ２．２ ＮＦＳ 指标的分析 ＮＦＳ 指标的设计原则是每个样本应该和距离其 最近的样本划分到同一类别中，而与距离其最远的 样本划分到不同类别中。 因此，每个样本拥有两个 影响评分的因子，分别是最近得分因子和最远得分 因子。 对于最近得分因子，如果某个样本与距离其 最近的样本划分到同一类中，则得 １ 分，表示对此聚 类结果的支持，而如果划分到不同类中，则得－１ 分， 表示对此聚类结果的反对。 最远得分因子的规定 也是如此。 随着类别数的增加，样本和其最近邻样本被划 分到不同类别中的概率将会增加，从而导致了最近 得分累积和的减少；然而随着类别数的增加，样本 和其最远邻样本被划分到同一类的概率将会减少， 从而导致了最远得分累积和的增加。 因此，在评价 聚类结果时仅采用最近得分或最远得分将很难得 到正确的类别数，需要综合利用这两个得分才能获 得好的聚类结果。 为了说明这个问题，我们将利用 图 １ 所示的数据集在不同类别数下的聚类结果来说 明同时考虑最近得分和最远得分的必要性。 观察 图 １ 所示数据集，可知此数据集的最佳类别数为 ４。 如果只考虑最近邻得分时，如图 １（ ａ）所示，当 Ｋ ＝ ２ 时，所有样本和其最近邻样本都在同一类中，而如 图 １（ｂ）和图 １（ｃ）所示，当 Ｋ ＝ ３ 或 Ｋ ＝ ４ 时，样本和 其最近邻划分到不同类的比率就会增大，聚类结果 的最近得分值会下降，因此 Ｋ ＝ ２ 时，使最近得分值 达到最大，故采用最近得分准则所得到的最佳类别 数为 ２。 而如果只考虑最远得分时，如图 １ （ ａ） 所 示，当 Ｋ ＝ ２ 时，样本和其最远邻样本被划分到同一 类的比率很大，而如图 １（ｂ）和图 １（ｃ）所示，当 Ｋ ＝ ３ 或Ｋ ＝ ４ 时，样本与其最远邻样本划分到同一类的比 率下降，而且当 Ｋ ＝ ３ 时，样本和其最远邻样本分别 划分到不同类中，此时聚类结果的最远得分值达到 第 １ 期 冯柳伟，等：最近最远得分的聚类性能评价指标 ·６９·
·70 智能系统学报 第12卷 最大，因此，采用最远得分准则所得到的最佳类别 算在不同类别数下的NS评价指标值，第3步是根 数为3。为了选择出正确的类别数，评价指标应该 据评价指标得到使聚类结果达到最好的类别数。 综合考虑最近得分和最远得分这两个因素。基于 该算法具体步骤如下。 以上的理论，在NS评价指标中每个样本的得分设 1)使用基于最短距离的分层聚类算法[]并设 计为最近得分和最远得分的均值。 定合适的截止阈值得到类别数，把该类别数作为搜 索上限K,设置搜索下限K.=2,得到聚类数的搜 索范围[Ka,K]。 2)对于搜索范围[K,K]中不同的聚类数K 分别运行以下步骤： ①利用K-means【2o]算法对数据集进行聚类； ②根据式(4)~(8)计算聚类结果的NFS指 标值； ③根据式(9)得到最佳聚类数Kp。 0 2 ACNFS算法流程如图2所示。 (a)K=2 开始 输出数据 2 得到类别数搜索范围[KnKJ 设置：Kmn2 K-means算法聚类 计算NFS评价指标nfs(K) 0 2 N (b)K=3 Y Kmp-Kianp1 K-maxinfs(》 结束○ 图2 ACNFS算法流程图 Fig.2 The flow chart of ACNFS algorithm 3.2 ACNFS时间复杂度分析 假定数据集有n个样本，则ACNFS算法的时间 (c)K=4 复杂度分析如下。 图1不同聚类数下的聚类 1)ACNFS算法首先采用基于最短距离的分层聚 Fig.1 Clustering under different cluster number 类算法，该算法每次把距离最近的两类合并成一类，其 NS指标值衡量的是样本对聚类结果的满意 时间复杂度为O(tn2),其中t为迭代次数且tn。 度，NS指标值越大聚类结果就越好。因此，依据 2)算法第二步中使用K-means算法进行聚类， NFS选取最佳类别数的公式为 其时间复杂度为O(n),其中l为迭代次数，K为 Ko max (nfs(K)) (9) 2∠K6Km 类别数，且ln,Kgn。 3)采用K-menas聚类之后需要采用NFS评价 3 基于NFS的自动聚类算法 指标对聚类结果进行评估。我们需要计算样本间 3.1 ACNFS算法 的距离从而计算每个样本的最近得分与最远得分， 基于NFS的自动聚类算法(automatic clustering 因此计算NS指标值的时间复杂度为O(n2)。 algorithm based on the NFS,ACNFS)主要包括3个主 为了获得类别数，需要重复K-means和计算NS指 要步骤。第1步确定类别数的搜索范围，第2步计 标值K-K+1次，因此2)和3)的总的时间复杂度为
最大，因此，采用最远得分准则所得到的最佳类别 数为 ３。 为了选择出正确的类别数，评价指标应该 综合考虑最近得分和最远得分这两个因素。 基于 以上的理论，在 ＮＦＳ 评价指标中每个样本的得分设 计为最近得分和最远得分的均值。 （ａ）Ｋ＝ ２ （ｂ）Ｋ＝ ３ （ｃ）Ｋ＝ ４ 图 １ 不同聚类数下的聚类 Ｆｉｇ．１ Ｃｌｕｓｔｅｒｉｎｇ ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ ＮＦＳ 指标值衡量的是样本对聚类结果的满意 度，ＮＦＳ 指标值越大聚类结果就越好。 因此，依据 ＮＦＳ 选取最佳类别数的公式为 Ｋｏｐｔ ＝ ｍａｘ ２≤Ｋ≤Ｋｍａｘ {ｎｆｓ（Ｋ）} （９） ３ 基于 ＮＦＳ 的自动聚类算法 ３．１ ＡＣＮＦＳ 算法 基于 ＮＦＳ 的自动聚类算法（ ａｕｔｏｍａｔｉｃ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ＮＦＳ，ＡＣＮＦＳ）主要包括 ３ 个主 要步骤。 第 １ 步确定类别数的搜索范围，第 ２ 步计 算在不同类别数下的 ＮＦＳ 评价指标值，第 ３ 步是根 据评价指标得到使聚类结果达到最好的类别数。 该算法具体步骤如下。 １）使用基于最短距离的分层聚类算法［１９］ 并设 定合适的截止阈值得到类别数，把该类别数作为搜 索上限 Ｋｍａｘ，设置搜索下限 Ｋｍｉｎ ＝ ２，得到聚类数的搜 索范围 Ｋｍｉｎ ，Ｋｍａｘ [ ] 。 ２）对于搜索范围 Ｋｍｉｎ ，Ｋｍａｘ [ ] 中不同的聚类数 Ｋ 分别运行以下步骤： ① 利用 Ｋ⁃ｍｅａｎｓ ［２０］算法对数据集进行聚类； ②根据式（ ４） ～ （ ８） 计算聚类结果的 ＮＦＳ 指 标值； ③根据式（９）得到最佳聚类数 Ｋｏｐｔ。 ＡＣＮＦＳ 算法流程如图 ２ 所示。 图 ２ ＡＣＮＦＳ 算法流程图 Ｆｉｇ．２ Ｔｈｅ ｆｌｏｗ ｃｈａｒｔ ｏｆ ＡＣＮＦＳ ａｌｇｏｒｉｔｈｍ ３．２ ＡＣＮＦＳ 时间复杂度分析 假定数据集有 ｎ 个样本，则 ＡＣＮＦＳ 算法的时间 复杂度分析如下。 １）ＡＣＮＦＳ 算法首先采用基于最短距离的分层聚 类算法，该算法每次把距离最近的两类合并成一类，其 时间复杂度为 Ｏ ｔｎ ２ ( ) ，其中 ｔ 为迭代次数且ｔ≪ｎ。 ２）算法第二步中使用 Ｋ⁃ｍｅａｎｓ 算法进行聚类， 其时间复杂度为 Ｏ（ ｎＫｌ），其中 ｌ 为迭代次数，Ｋ 为 类别数，且 ｌ≪ｎ，Ｋ≪ｎ。 ３）采用 Ｋ⁃ｍｅｎａｓ 聚类之后需要采用 ＮＦＳ 评价 指标对聚类结果进行评估。 我们需要计算样本间 的距离从而计算每个样本的最近得分与最远得分， 因此计算 ＮＦＳ 指标值的时间复杂度为 Ｏ ｎ ２ ( ) 。 为了获得类别数，需要重复 Ｋ⁃ｍｅａｎｓ 和计算 ＮＦＳ 指 标值 Ｋｍａｘ －Ｋｍｉｎ ＋１ 次，因此 ２）和 ３）的总的时间复杂度为 ·７０· 智 能 系 统 学 报 第 １２ 卷
第1期 冯柳伟，等：最近最远得分的聚类性能评价指标 ·71 O(n2+nll)×(K-Kn+1),且(K-K+1)n。 因此，ACNFS算法总的时间复杂度即 为0(tm2+(n2+nkl)×(Kx-Kia)）。 4 实验 为了验证本文所提NFS指标和ACNFS算法的 有效性，我们进行了仿真实验。在实验中我们将采 用6个人工数据集和4个UCI真实数据，对CH指 标、BWP指标，IGP指标和NFS指标确定类别数的 2 0 性能进行比较。实验证明，基于NS指标所提出的 (d)Dataset 4 ACNFS算法可以有效地确定数据集的类别数，实现 2.0 1.5 类别中心和类别数的自动估计。 1.0 在仿真实验中，我们所采用的人工数据集如图 0.5 3所示，而真实数据集则为UCI数据库中的IRIS 0 Balance Scale,Wine以及Soybean-small数据集。为 -0.5 了方便，我们将上述所有数据集的特征总结到表1 -1.0 -1.5 中，其中n表示数据集中样本点的个数，K表示数据 -2.0 集中样本点的类别数，d表示数据集中样本点的特 -2.5 征维数，最后一列表示各类别中样本点的个数。 -2.0-1.5-1.0-0.500.51.01.52.02.5 10 (e)Dataset 5 8 6 4 0 0 6 8 10 (a)Dataset 1 2.5r -2.0-1.5-1.0-0.500.51.01.52.02.5 2.0 。h (f)Dataset 6 图3人工数据集 +料 1.0 有 Fig.3 Artificial dataset 0.5 表1 实验中所使用的10组数据集特征 0 Table 1 The characters of the ten data sets used in -0.5 our experiments -10 数据集 n K d 每类中样本点的个数 -1.0 -0.5 0 0.5 1.0 1.5 2.0 Dataset 1 800 2 2 400.400 (b)Dataset 2 Dataset 2 800 3 2 400.200.200 Dataset 3 800 3 2 400.200.200 15 Dataset 4 1 100 4 200,400,200 Dataset 5 1 000 5 2 400.200.200.300 Dataset 6 900 6 200.200,200.200,200 Iris 150 3 4 150.150.150.150.150.150 Balance Scale 630 3 4 50,50,50 -10 1015 Wine 178 3 13 54.288.288 -10 -5 0 5 Sovbean-small 47 435 59,71,48 (c)Dataset 3
Ｏ（（ｎ ２＋ｎｋｌ）×（Ｋｍａｘ －Ｋｍｉｎ ＋１）），且（Ｋｍａｘ －Ｋｍｉｎ ＋１）≪ｎ。 因 此， ＡＣＮＦＳ 算 法 总 的 时 间 复 杂 度 即 为Ｏ ｔｎ ２＋（ｎ ２＋ｎｋｌ）×（Ｋｍａｘ ( －Ｋｍｉｎ ） ) 。 ４ 实验 为了验证本文所提 ＮＦＳ 指标和 ＡＣＮＦＳ 算法的 有效性，我们进行了仿真实验。 在实验中我们将采 用 ６ 个人工数据集和 ４ 个 ＵＣＩ 真实数据，对 ＣＨ 指 标、ＢＷＰ 指标、ＩＧＰ 指标和 ＮＦＳ 指标确定类别数的 性能进行比较。 实验证明，基于 ＮＦＳ 指标所提出的 ＡＣＮＦＳ 算法可以有效地确定数据集的类别数，实现 类别中心和类别数的自动估计。 在仿真实验中，我们所采用的人工数据集如图 ３ 所示，而真实数据集则为 ＵＣＩ 数据库中的 ＩＲＩＳ， Ｂａｌａｎｃｅ Ｓｃａｌｅ，Ｗｉｎｅ 以及 Ｓｏｙｂｅａｎ⁃ｓｍａｌｌ 数据集。 为 了方便，我们将上述所有数据集的特征总结到表 １ 中，其中 ｎ 表示数据集中样本点的个数，Ｋ 表示数据 集中样本点的类别数，ｄ 表示数据集中样本点的特 征维数，最后一列表示各类别中样本点的个数。 （ａ）Ｄａｔａｓｅｔ １ （ｂ）Ｄａｔａｓｅｔ ２ （ｃ）Ｄａｔａｓｅｔ ３ （ｄ）Ｄａｔａｓｅｔ ４ （ｅ）Ｄａｔａｓｅｔ ５ （ｆ）Ｄａｔａｓｅｔ ６ 图 ３ 人工数据集 Ｆｉｇ．３ Ａｒｔｉｆｉｃｉａｌ ｄａｔａｓｅｔ 表 １ 实验中所使用的 １０ 组数据集特征 Ｔａｂｌｅ １ Ｔｈｅ ｃｈａｒａｃｔｅｒｓ ｏｆ ｔｈｅ ｔｅｎ ｄａｔａ ｓｅｔｓ ｕｓｅｄ ｉｎ ｏｕｒ ｅｘｐｅｒｉｍｅｎｔｓ 数据集 ｎ Ｋ ｄ 每类中样本点的个数 Ｄａｔａｓｅｔ １ ８００ ２ ２ ４００，４００ Ｄａｔａｓｅｔ ２ ８００ ３ ２ ４００，２００，２００ Ｄａｔａｓｅｔ ３ ８００ ３ ２ ４００，２００，２００ Ｄａｔａｓｅｔ ４ １ １００ ４ ２ ２００，４００，２００ Ｄａｔａｓｅｔ ５ １ ０００ ５ ２ ４００，２００，２００，３００ Ｄａｔａｓｅｔ ６ ９００ ６ ２ ２００，２００，２００，２００，２００ Ｉｒｉｓ １５０ ３ ４ １５０，１５０，１５０，１５０，１５０，１５０ Ｂａｌａｎｃｅ Ｓｃａｌｅ ６３０ ３ ４ ５０，５０，５０ Ｗｉｎｅ １７８ ３ １３ ５４，２８８，２８８ Ｓｏｙｂｅａｎ⁃ｓｍａｌｌ ４７ ４ ３５ ５９，７１，４８ 第 １ 期 冯柳伟，等：最近最远得分的聚类性能评价指标 ·７１·
·72 智能系统学报 第12卷 首先，分别采用CH指标、BWP指标，IGP指标 表5给出了对数据集Dataset4采用不同评价 和NFS指标估计人工数据集Dataset 1~Dataset6的 指标得到的类别数和各类别数出现的百分比。采 类别数，实验结果如表2~7所示。 用NFS指标、CH指标和BWP指标均可以得到正确 表2中给出了对数据集Dataset1采用不同评 的类别数，而采用IGP指标却无法得到正确的类别 价指标得到的类别数和各类别数出现的百分比。 数。从具体情况分析，NFS指标和CH指标性能较 第2列到第8列的数据是百分数值，而百分数值代 好，评价结果稳定，每次都可以得到正确的类别数： 表算法在运行N次，得到相应的类别数的次数与N 而BWP指标差一点，正确率只有71.3%。 的比值。实验中取N=20。表2中的最后1列表示 表5 Dataset4的类别数 通过投票准则获得的数据集的类别数。从表2可以 Table 5 The cluster number of Dataset 4 看出，对人工数据集Dataset1采用这4种评价指标 评价指标23456.78 最终类别数 均能得到正确的类别数，而且评价结果稳定，每次 CH 001000000 4 都能得到正确类别数。 BWP 0071.3208.700 4 表2 Dataset1的类别数 IGP 95500000 2 Table 2 The cluster number of Dataset 1 NFS 001000000 评价指标2345678 最终类别数 CH100000000 表6给出了对数据集Dataset5采用不同评价 BWP10000000 0 2 指标得到的类别数和各类别数出现的百分比。采 1GP100000000 用NFS指标、CH指标和BWP指标均可以得到正确 NFS100000000 2 的类别数，而采用IGP指标却无法得到正确的 表3给出了对数据集Dataset2采用不同评价 类别数。 指标得到的类别数和各类别数出现的百分比。从 表6 Dataset5的类别数 Dataset2的散点分布图中可以看出，有两类数据无 Table 6 The cluster number of Dataset 5 法完全分离。因此，只有采用NFS指标得到的类别 评价指标2345678 最终类别数 数是正确的类别数，而且评价结果稳定，每次都能 CH 00.0100000 5 得到正确的类别数；而采用其他的评价指标却无法 BWP 00 01000 0 0 5 得到正确的类别数。 IGP 750250000 2 表3 Dataset2的类别数 NFS000100000 Table 3 The cluster number of Dataset 2 评价指标23 45678 最终类别数 表7给出了对数据集Dataset6采用不同评价 CH100000000 指标得到的类别数和各类别数出现的百分比。采 用四种评价指标均能得到该数据集的正确类别数。 BWP100000000 IGP100000000 其中NFS指标、BWP指标和CH指标的性能较好， 评价结果稳定；而IGP指标性能差一点，正确率 NFS010000000 3 为90%。 表4给出了对数据集Dataset3采用不同评价 表7 Dataset6的类别数 指标得到的类别数和各类别数出现的百分比。由 Table 7 The cluster number of Dataset 6 于在数据集Dataset3中，不同类之间是完全可分 评价指标2345678最终类别数 的，因此采用这4个评价指标，均可以得到正确的类 CH 000010000 别数，而且评价结果稳定。 6 表4 Dataset3的类别数 BWP 00 001000 0 6 Table 4 The cluster number of Dataset 3 IGP 100009000 6 评价指标2345678最终类别数 NFS 000010000 6 CH 01000000 0 3 由表2~7所示的实验结果可如，对于可分性较 BWP 010000000 3 好的人工数据集，CH指标、BWP指标和NFS指标 IGP 010000000 3 均能获得正确的类别数。下面将采用UCI中的真 NFS010000000 3 实数据集IRIS、Balance Scale、Wine以及
首先，分别采用 ＣＨ 指标、ＢＷＰ 指标、ＩＧＰ 指标 和 ＮＦＳ 指标估计人工数据集 Ｄａｔａｓｅｔ １ ～ Ｄａｔａｓｅｔ ６ 的 类别数，实验结果如表 ２～７ 所示。 表 ２ 中给出了对数据集 Ｄａｔａｓｅｔ １ 采用不同评 价指标得到的类别数和各类别数出现的百分比。 第 ２ 列到第 ８ 列的数据是百分数值，而百分数值代 表算法在运行 Ｎ 次，得到相应的类别数的次数与 Ｎ 的比值。 实验中取 Ｎ＝ ２０。 表 ２ 中的最后 １ 列表示 通过投票准则获得的数据集的类别数。 从表 ２ 可以 看出，对人工数据集 Ｄａｔａｓｅｔ １ 采用这 ４ 种评价指标 均能得到正确的类别数，而且评价结果稳定，每次 都能得到正确类别数。 表 ２ Ｄａｔａｓｅｔ １ 的类别数 Ｔａｂｌｅ ２ Ｔｈｅ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ ｏｆ Ｄａｔａｓｅｔ １ 评价指标 ２ ３ ４ ５ ６ ７ ８ 最终类别数 ＣＨ １００ ０ ０ ０ ０ ０ ０ ２ ＢＷＰ １００ ０ ０ ０ ０ ０ ０ ２ ＩＧＰ １００ ０ ０ ０ ０ ０ ０ ２ ＮＦＳ １００ ０ ０ ０ ０ ０ ０ ２ 表 ３ 给出了对数据集 Ｄａｔａｓｅｔ ２ 采用不同评价 指标得到的类别数和各类别数出现的百分比。 从 Ｄａｔａｓｅｔ ２ 的散点分布图中可以看出，有两类数据无 法完全分离。 因此，只有采用 ＮＦＳ 指标得到的类别 数是正确的类别数，而且评价结果稳定，每次都能 得到正确的类别数；而采用其他的评价指标却无法 得到正确的类别数。 表 ３ Ｄａｔａｓｅｔ ２ 的类别数 Ｔａｂｌｅ ３ Ｔｈｅ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ ｏｆ Ｄａｔａｓｅｔ ２ 评价指标 ２ ３ ４ ５ ６ ７ ８ 最终类别数 ＣＨ １００ ０ ０ ０ ０ ０ ０ ２ ＢＷＰ １００ ０ ０ ０ ０ ０ ０ ２ ＩＧＰ １００ ０ ０ ０ ０ ０ ０ ２ ＮＦＳ ０ １００ ０ ０ ０ ０ ０ ３ 表 ４ 给出了对数据集 Ｄａｔａｓｅｔ ３ 采用不同评价 指标得到的类别数和各类别数出现的百分比。 由 于在数据集 Ｄａｔａｓｅｔ ３ 中，不同类之间是完全可分 的，因此采用这 ４ 个评价指标，均可以得到正确的类 别数，而且评价结果稳定。 表 ４ Ｄａｔａｓｅｔ ３ 的类别数 Ｔａｂｌｅ ４ Ｔｈｅ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ ｏｆ Ｄａｔａｓｅｔ ３ 评价指标 ２ ３ ４ ５ ６ ７ ８ 最终类别数 ＣＨ ０ １００ ０ ０ ０ ０ ０ ３ ＢＷＰ ０ １００ ０ ０ ０ ０ ０ ３ ＩＧＰ ０ １００ ０ ０ ０ ０ ０ ３ ＮＦＳ ０ １００ ０ ０ ０ ０ ０ ３ 表 ５ 给出了对数据集 Ｄａｔａｓｅｔ ４ 采用不同评价 指标得到的类别数和各类别数出现的百分比。 采 用 ＮＦＳ 指标、ＣＨ 指标和 ＢＷＰ 指标均可以得到正确 的类别数，而采用 ＩＧＰ 指标却无法得到正确的类别 数。 从具体情况分析，ＮＦＳ 指标和 ＣＨ 指标性能较 好，评价结果稳定，每次都可以得到正确的类别数； 而 ＢＷＰ 指标差一点，正确率只有 ７１．３％。 表 ５ Ｄａｔａｓｅｔ ４ 的类别数 Ｔａｂｌｅ ５ Ｔｈｅ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ ｏｆ Ｄａｔａｓｅｔ ４ 评价指标 ２ ３ ４ ５ ６ ７ ８ 最终类别数 ＣＨ ０ ０ １００ ０ ０ ０ ０ ４ ＢＷＰ ０ ０ ７１．３ ２０ ８．７ ０ ０ ４ ＩＧＰ ９５ ５ ０ ０ ０ ０ ０ ２ ＮＦＳ ０ ０ １００ ０ ０ ０ ０ ４ 表 ６ 给出了对数据集 Ｄａｔａｓｅｔ ５ 采用不同评价 指标得到的类别数和各类别数出现的百分比。 采 用 ＮＦＳ 指标、ＣＨ 指标和 ＢＷＰ 指标均可以得到正确 的类别数， 而采用 ＩＧＰ 指标却无法得 到 正 确 的 类别数。 表 ６ Ｄａｔａｓｅｔ ５ 的类别数 Ｔａｂｌｅ ６ Ｔｈｅ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ ｏｆ Ｄａｔａｓｅｔ ５ 评价指标 ２ ３ ４ ５ ６ ７ ８ 最终类别数 ＣＨ ０ ０ ０ １００ ０ ０ ０ ５ ＢＷＰ ０ ０ ０ １００ ０ ０ ０ ５ ＩＧＰ ７５ ０ ２５ ０ ０ ０ ０ ２ ＮＦＳ ０ ０ ０ １００ ０ ０ ０ ５ 表 ７ 给出了对数据集 Ｄａｔａｓｅｔ ６ 采用不同评价 指标得到的类别数和各类别数出现的百分比。 采 用四种评价指标均能得到该数据集的正确类别数。 其中 ＮＦＳ 指标、ＢＷＰ 指标和 ＣＨ 指标的性能较好， 评价结果稳定；而 ＩＧＰ 指标性能差一点，正确率 为 ９０％。 表 ７ Ｄａｔａｓｅｔ ６ 的类别数 Ｔａｂｌｅ ７ Ｔｈｅ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ ｏｆ Ｄａｔａｓｅｔ ６ 评价指标 ２ ３ ４ ５ ６ ７ ８ 最终类别数 ＣＨ ０ ０ ０ ０ １００ ０ ０ ６ ＢＷＰ ０ ０ ０ ０ １００ ０ ０ ６ ＩＧＰ １０ ０ ０ ０ ９０ ０ ０ ６ ＮＦＳ ０ ０ ０ ０ １００ ０ ０ ６ 由表 ２ ～ ７ 所示的实验结果可如，对于可分性较 好的人工数据集，ＣＨ 指标、ＢＷＰ 指标和 ＮＦＳ 指标 均能获得正确的类别数。 下面将采用 ＵＣＩ 中的真 实 数 据 集 ＩＲＩＳ、 Ｂａｌａｎｃｅ Ｓｃａｌｅ、 Ｗｉｎｅ 以 及 ·７２· 智 能 系 统 学 报 第 １２ 卷
第1期 冯柳伟，等：最近最远得分的聚类性能评价指标 ·73· Soybean-small来验证CH指标、BWP指标、IGP指标 5 结束语 和NFS指标在确定类别数时的性能。 表8给出了数据集Wine在采用不同评价指标 众所周知，很多聚类算法需要根据先验知识给 时，在不同的类别数下的指标值，其中带下划线的 出算法所需要的类别数。但是，在很多实际应用中 数据是该指标下的最大值。NFS指标和BWP指标 很难获得有效的先验知识，因此确定聚类问题的类 在类别数K=3时取最大值，而其他指标在类别数K 别数成为了一个研究的热点。本文首先基于最近 =2时取最大值，但是由于数据集Wime的真实类别 邻一致性和最远邻相异性的原则，提出了一种最近 数为3，因此采用NFS指标和BWP指标可以得到正 最远得分评价指标(NFS),并在此基础上提出了一 确的类别数，而采用其他评价指标则无法得到正确 种基于NS自动聚类算法，实现了对类别数和类别 的类别数。 中心的自动估计。与已经提出的评价指标相比， 表81 Wine的指标值 NFS指标是基于数据集统计信息的指标，而且NFS Table 8 The index value for Wine 指标考虑了最近样本和最远样本两个方面，通过评 类别数 CH BWP IGP NFS 分机制还保证了每个样本都对评价指标产生影响。 从而使NFS指标在RIS等数据集中呈现较好的结 2 7521600 0.32507 0.96217 0.86706 果。但是NFS指标并不是最完美的，因此还需要继 49268500.33404 0.94062 0.9009 续进行相关研究。 33564400.3023 0.78952 0.77477 参考文献： 25788400.26958 0.71 0.69746 [1]刘恋，常冬霞，邓勇.动态小生境人工鱼群算法的图像 6 21474150.23255 0.67366 0.69212 分割[J].智能系统学报，2015,10(5)：669-674. > 18239050.20382 0.64983 0.66635 LIU Lian,CHANG Dongxia,DENG Yong.An image 16088700.18771 0.64815 0.6332 segmentation method based on dynamic niche artificial fish- swarm algorithm J].CAAI transactions on intelligent 14387650.18471 0.61281 0.61655 systems,2015,10(5):669-674. 12918500.178710.59433 0.5766 [2]NIKOLAOU T G.KOLOKOTSA DS,STAVRAKAKIS G S. 最终类别数 2 et al.On the application of clustering techniques for office buildings'energy and thermal comfort classification [J]. 表9给出了4组真实数据集分别在采用不同评 IEEE transactions on smart grid,2012,3(4):2196-2210. 价指标下得到的类别数，这里依然是运行多次实验 [3]CHANG Hong,YEUNG D Y.Robust path-based spectral 通过投票准则确定最终的类别数，括号中的数据表 clustering with application to image segmentation [C]/ 示类别数出现的百分比。参考表1中各数据集的真 Proceedings of the Tenth IEEE International Conference on 实类别数，可以得到如下结论：采用NS指标可以 Computer Vision.Beijing,China,2005,1:278-285. 得到所有真实数据集的正确的类别数，其中对于 [4]SHI Jianbo,MALIK J.Normalized cuts and image Balance Scale和Wine数据集，评价结果稳定，效果 segmentation[J].IEEE transactions on pattern analysis 较好，而对于IRIS和Soybean-small数据集，评价结 and machine intelligence,2000,22(8):888-905. 果差一点，只有60%和45%的正确率：然而采用 [5]XIE X L,BENI G.A validity measure for Fuzzy clustering BWP指标只可以得到数据集Wine的正确类别数， [J].IEEE transactions on pattern analysis and machine 而且评价结果稳定：但是采用CH指标和IGP指标 intelligence,1991,13(8):841-847 则无法得到数据集的正确类别数。 [6]PAL N R.BEZDEK J C.On cluster validity for the fuzzy c- 表9真实数据集的类别数 means model J].IEEE transactions on fuzzy systems, Table 9 The cluster number of the real datasets 1995,3(3):370-379. [7]郑宏亮，徐本强，赵晓慧，等.新的模糊聚类有效性指 数据集 CH BWP IGP NFS 标[J].计算机应用，2014.34(8)：2166-2169 IRIS 2(100)2(100) 2(100) 3(60) ZHENG Hongliang,XU Benqiang,ZHAO Xiaohui,et al. Balance Scale 2(100)8(70)2(100) 3(100) Novel validity index for fuzzy clustering J].Journal of Wine 2(100)3(100)2(100) 3(100) computer applications,2014,34(8):2166-2169. Soybean-small 2(100)3(32.9)3(40) 4(45) [8]岳士弘，黄妮，王鹏龙.基于矩阵特征值分析的模糊聚
Ｓｏｙｂｅａｎ⁃ｓｍａｌｌ来验证 ＣＨ 指标、ＢＷＰ 指标、ＩＧＰ 指标 和 ＮＦＳ 指标在确定类别数时的性能。 表 ８ 给出了数据集 Ｗｉｎｅ 在采用不同评价指标 时，在不同的类别数下的指标值，其中带下划线的 数据是该指标下的最大值。 ＮＦＳ 指标和 ＢＷＰ 指标 在类别数 Ｋ ＝ ３ 时取最大值，而其他指标在类别数 Ｋ ＝ ２ 时取最大值，但是由于数据集 Ｗｉｎｅ 的真实类别 数为 ３，因此采用 ＮＦＳ 指标和 ＢＷＰ 指标可以得到正 确的类别数，而采用其他评价指标则无法得到正确 的类别数。 表 ８ Ｗｉｎｅ 的指标值 Ｔａｂｌｅ ８ Ｔｈｅ ｉｎｄｅｘ ｖａｌｕｅ ｆｏｒ Ｗｉｎｅ 类别数 ＣＨ ＢＷＰ ＩＧＰ ＮＦＳ ２ ７ ５２１ ６００ ０．３２５ ０７ ０．９６２ １７ ０．８６７ ０６ ３ ４ ９２６ ８５０ ０．３３４ ０４ ０．９４０ ６２ ０．９００ ９ ４ ３ ３５６ ４４０ ０．３０２ ３ ０．７８９ ５２ ０．７７４ ７７ ５ ２ ５７８ ８４０ ０．２６９ ５８ ０．７１ ０．６９７ ４６ ６ ２ １４７ ４１５ ０．２３２ ５５ ０．６７３ ６６ ０．６９２ １２ ７ １ ８２３ ９０５ ０．２０３ ８２ ０．６４９ ８３ ０．６６６ ３５ ８ １ ６０８ ８７０ ０．１８７ ７１ ０．６４８ １５ ０．６３３ ２ ９ １ ４３８ ７６５ ０．１８４ ７１ ０．６１２ ８１ ０．６１６ ５５ １０ １ ２９１ ８５０ ０．１７８ ７１ ０．５９４ ３３ ０．５７６ ６ 最终类别数 ２ ３ ２ ３ 表 ９ 给出了 ４ 组真实数据集分别在采用不同评 价指标下得到的类别数，这里依然是运行多次实验 通过投票准则确定最终的类别数，括号中的数据表 示类别数出现的百分比。 参考表 １ 中各数据集的真 实类别数，可以得到如下结论：采用 ＮＦＳ 指标可以 得到所有真实数据集的正确的类别数，其中对于 Ｂａｌａｎｃｅ Ｓｃａｌｅ 和 Ｗｉｎｅ 数据集，评价结果稳定，效果 较好，而对于 ＩＲＩＳ 和 Ｓｏｙｂｅａｎ⁃ｓｍａｌｌ 数据集，评价结 果差一点，只有 ６０％ 和 ４５％ 的正确率；然而采用 ＢＷＰ 指标只可以得到数据集 Ｗｉｎｅ 的正确类别数， 而且评价结果稳定；但是采用 ＣＨ 指标和 ＩＧＰ 指标 则无法得到数据集的正确类别数。 表 ９ 真实数据集的类别数 Ｔａｂｌｅ ９ Ｔｈｅ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ ｏｆ ｔｈｅ ｒｅａｌ ｄａｔａｓｅｔｓ 数据集 ＣＨ ＢＷＰ ＩＧＰ ＮＦＳ ＩＲＩＳ ２（１００） ２（１００） ２（１００） ３（６０） Ｂａｌａｎｃｅ Ｓｃａｌｅ ２（１００） ８（７０） ２（１００） ３（１００） Ｗｉｎｅ ２（１００） ３（１００） ２（１００） ３（１００） Ｓｏｙｂｅａｎ⁃ｓｍａｌｌ ２（１００） ３（３２．９） ３（４０） ４（４５） ５ 结束语 众所周知，很多聚类算法需要根据先验知识给 出算法所需要的类别数。 但是，在很多实际应用中 很难获得有效的先验知识，因此确定聚类问题的类 别数成为了一个研究的热点。 本文首先基于最近 邻一致性和最远邻相异性的原则，提出了一种最近 最远得分评价指标（ＮＦＳ），并在此基础上提出了一 种基于 ＮＦＳ 自动聚类算法，实现了对类别数和类别 中心的自动估计。 与已经提出的评价指标相比， ＮＦＳ 指标是基于数据集统计信息的指标，而且 ＮＦＳ 指标考虑了最近样本和最远样本两个方面，通过评 分机制还保证了每个样本都对评价指标产生影响。 从而使 ＮＦＳ 指标在 ＩＲＩＳ 等数据集中呈现较好的结 果。 但是 ＮＦＳ 指标并不是最完美的，因此还需要继 续进行相关研究。 参考文献： ［１］刘恋， 常冬霞， 邓勇． 动态小生境人工鱼群算法的图像 分割［Ｊ］． 智能系统学报， ２０１５， １０（５）： ６６９－６７４． ＬＩＵ Ｌｉａｎ， ＣＨＡＮＧ Ｄｏｎｇｘｉａ， ＤＥＮＧ Ｙｏｎｇ． Ａｎ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｄｙｎａｍｉｃ ｎｉｃｈｅ ａｒｔｉｆｉｃｉａｌ ｆｉｓｈ⁃ ｓｗａｒｍ ａｌｇｏｒｉｔｈｍ ［ Ｊ ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１５， １０（５）： ６６９－６７４． ［２］ＮＩＫＯＬＡＯＵ Ｔ Ｇ， ＫＯＬＯＫＯＴＳＡ Ｄ Ｓ， ＳＴＡＶＲＡＫＡＫＩＳ Ｇ Ｓ， ｅｔ ａｌ． Ｏｎ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ｏｆｆｉｃｅ ｂｕｉｌｄｉｎｇｓ ｅｎｅｒｇｙ ａｎｄ ｔｈｅｒｍａｌ ｃｏｍｆｏｒｔ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ［ Ｊ ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｓｍａｒｔ ｇｒｉｄ， ２０１２， ３（４）： ２１９６－２２１０． ［３］ ＣＨＡＮＧ Ｈｏｎｇ， ＹＥＵＮＧ Ｄ Ｙ． Ｒｏｂｕｓｔ ｐａｔｈ⁃ｂａｓｅｄ ｓｐｅｃｔｒａｌ ｃｌｕｓｔｅｒｉｎｇ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｔｅｎｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ． Ｂｅｉｊｉｎｇ， Ｃｈｉｎａ， ２００５， １： ２７８－２８５． ［ ４ ］ ＳＨＩ Ｊｉａｎｂｏ， ＭＡＬＩＫ Ｊ． Ｎｏｒｍａｌｉｚｅｄ ｃｕｔｓ ａｎｄ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０００， ２２（８）： ８８８－９０５． ［５］ＸＩＥ Ｘ Ｌ， ＢＥＮＩ Ｇ． Ａ ｖａｌｉｄｉｔｙ ｍｅａｓｕｒｅ ｆｏｒ Ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， １９９１， １３（８）： ８４１－８４７． ［６］ＰＡＬ Ｎ Ｒ， ＢＥＺＤＥＫ Ｊ Ｃ． Ｏｎ ｃｌｕｓｔｅｒ ｖａｌｉｄｉｔｙ ｆｏｒ ｔｈｅ ｆｕｚｚｙ ｃ⁃ ｍｅａｎｓ ｍｏｄｅｌ ［ Ｊ ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｆｕｚｚｙ ｓｙｓｔｅｍｓ， １９９５， ３（３）： ３７０－３７９． ［７］郑宏亮， 徐本强， 赵晓慧， 等． 新的模糊聚类有效性指 标［Ｊ］． 计算机应用， ２０１４， ３４（８）： ２１６６－２１６９． ＺＨＥＮＧ Ｈｏｎｇｌｉａｎｇ， ＸＵ Ｂｅｎｑｉａｎｇ， ＺＨＡＯ Ｘｉａｏｈｕｉ， ｅｔ ａｌ． Ｎｏｖｅｌ ｖａｌｉｄｉｔｙ ｉｎｄｅｘ ｆｏｒ ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１４， ３４（８）： ２１６６－２１６９． ［８］岳士弘， 黄媞， 王鹏龙． 基于矩阵特征值分析的模糊聚 第 １ 期 冯柳伟，等：最近最远得分的聚类性能评价指标 ·７３·
·74 智能系统学报 第12卷 类有效性指标[J].天津大学学报：自然科学与工程技 ZHOU Shibing,XU Zhenyuan,TANG Xuqing.Method for 术版，2014,47(8)：689-696. determining optimal number of clusters in K-means YUE Shihong,HUANG Ti,WANG Penglong.Matrix clustering algorithm[J].Journal of computer applications, eigenvalue analysis-based clustering validity index[J]. 2010,30(8):1995-1998. Journal of Tianjin university:science and technology,2014, [17]KAPP A V,TIBSHIRANI R.Are clusters found in one 47(8):689-696. dataset present in another dataset[].Biostatistics,2007, [9]卿铭，孙晓梅.一种新的聚类有效性函数：模糊划分的 8(1):9-31 模糊嫡[J].智能系统学报，2015,10(1)：75-80. [18]周世兵.聚类分析中的最佳聚类数确定方法研究及应 QING Mei,SUN Xiaomei.A new clustering effectiveness 用[D].无锡：江南大学，2011. function:fuzzy entropy of fuzzy partition [J].CAAI ZHOU Shibing.Research and application on determining transactions on intelligent systems,2015,10(1):75-80. optimal number of cluster in cluster analysis[D].Wuxi: [10]王开军，李健，张军英，等.聚类分析中类数估计方法 Jiangnan University,2011. 的实验比较[J].计算机工程，2008,34(9)：198- [19]Gower J C,Ross G J S.Minimum spanning trees and 199.202. single linkage cluster analysis [J].Journal of the royal WANG Kaijun,LI Jian,ZHANG Junying,et al. statistical society,1969.18(1):54-64. Experimental comparison of clusters number estimation for [20 MACQUEEN J.Some methods for classification and cluster analysis[J].Computer engineering,2008,34(9): analysis of multivariate observations[C]//Proceedings of 198-199,202. the 5th Berkeley Symposium on Mathematical Statistics [ll]王勇，唐靖，饶勤菲，等.高效率的K-means最佳聚类 and Probability.Berkeley,USA,1967:281-297 数确定算法[J].计算机应用，2014,34(5)： 作者简介： 1331-1335 冯柳伟，女，1992年生，硕士研究 WANG Yong,TANG Jing,RAO Qinfei,et al.High 生，研究方向为聚类算法。 efficient K-means algorithm for determining optimal number of clusters[J].Journal of computer applications,2014,34 (5):1331-1335 [12]CALINSKI T,HARABASZ J.A dendrite method for cluster analysis [J].Communications in statistics,1974,3 (1):1-27 常冬霞，女，1977年生.副教授，硕 [13]DAVIES D L.BOULDIN D W.A cluster separation 士生导师，主要研究方向为进化计算、 measure[J].IEEE transactions on pattern analysis and 非监督分类算法、图像分割以及图像分 machine intelligence,1979,PAMI-1(2):224-227. 类。发表学术论文10余篇，其中SC检 [14]DIMITRIADOU E,DOLNICAR S,WEINGESSEL A.An 索5篇，El检索2篇。 examination of indexes for determining the number of clusters in binary data sets[J].Psychometrika,2002,67 (1):137-159. 邓勇，男，1974年生，副研究员，博 [15]KRZANOWSKI W J,LAI Y T.A criterion for determining 士，主要研究方向为智能信息处理、数 the number of groups in a data set using sum-of-squares 据库系统技术及应用等。主持和参与 clustering[J].Biometrics,1988,44(1):23-34. 国家“863”计划1项，北京市自然科学 [16]周世兵，徐振源，唐旭清.K-means算法最佳聚类数确 基金项目1项。发表学术论文20余 定方法[J】.计算机应用，2010,30(8)：1995-1998 篇，其中收录10余篇
类有效性指标［ Ｊ］． 天津大学学报： 自然科学与工程技 术版， ２０１４， ４７（８）： ６８９－６９６． ＹＵＥ Ｓｈｉｈｏｎｇ， ＨＵＡＮＧ Ｔｉ， ＷＡＮＧ Ｐｅｎｇｌｏｎｇ． Ｍａｔｒｉｘ ｅｉｇｅｎｖａｌｕｅ ａｎａｌｙｓｉｓ － ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ ｖａｌｉｄｉｔｙ ｉｎｄｅｘ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｔｉａｎｊｉｎ ｕｎｉｖｅｒｓｉｔｙ： ｓｃｉｅｎｃｅ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ， ２０１４， ４７（８）： ６８９－６９６． ［９］卿铭， 孙晓梅． 一种新的聚类有效性函数： 模糊划分的 模糊熵［Ｊ］． 智能系统学报， ２０１５， １０（１）： ７５－８０． ＱＩＮＧ Ｍｅｉ， ＳＵＮ Ｘｉａｏｍｅｉ． Ａ ｎｅｗ ｃｌｕｓｔｅｒｉｎｇ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｆｕｎｃｔｉｏｎ： ｆｕｚｚｙ ｅｎｔｒｏｐｙ ｏｆ ｆｕｚｚｙ ｐａｒｔｉｔｉｏｎ ［ Ｊ ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１５， １０（１）： ７５－８０． ［１０］王开军， 李健， 张军英， 等． 聚类分析中类数估计方法 的实验比较［ Ｊ］． 计算机工程， ２００８， ３４ （ ９）： １９８ － １９９， ２０２． ＷＡＮＧ Ｋａｉｊｕｎ， ＬＩ Ｊｉａｎ， ＺＨＡＮＧ Ｊｕｎｙｉｎｇ， ｅｔ ａｌ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｌｕｓｔｅｒｓ ｎｕｍｂｅｒ ｅｓｔｉｍａｔｉｏｎ ｆｏｒ ｃｌｕｓｔｅｒ ａｎａｌｙｓｉｓ［Ｊ］． Ｃｏｍｐｕｔｅｒ ｅｎｇｉｎｅｅｒｉｎｇ， ２００８， ３４（９）： １９８－１９９， ２０２． ［１１］王勇， 唐靖， 饶勤菲， 等． 高效率的 Ｋ－ｍｅａｎｓ 最佳聚类 数确 定 算 法 ［ Ｊ ］． 计 算 机 应 用， ２０１４， ３４ （ ５ ）： １３３１－１３３５． ＷＡＮＧ Ｙｏｎｇ， ＴＡＮＧ Ｊｉｎｇ， ＲＡＯ Ｑｉｎｆｅｉ， ｅｔ ａｌ． Ｈｉｇｈ ｅｆｆｉｃｉｅｎｔ Ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｅｔｅｒｍｉｎｉｎｇ ｏｐｔｉｍａｌ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１４， ３４ （５）： １３３１－１３３５． ［１２］ＣＡＬＩＮ ＇ ＳＫＩ Ｔ， ＨＡＲＡＢＡＳＺ Ｊ． Ａ ｄｅｎｄｒｉｔｅ ｍｅｔｈｏｄ ｆｏｒ ｃｌｕｓｔｅｒ ａｎａｌｙｓｉｓ ［ Ｊ ］． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｉｎ ｓｔａｔｉｓｔｉｃｓ， １９７４， ３ （１）： １－２７． ［ １３ ］ ＤＡＶＩＥＳ Ｄ Ｌ， ＢＯＵＬＤＩＮ Ｄ Ｗ． Ａ ｃｌｕｓｔｅｒ ｓｅｐａｒａｔｉｏｎ ｍｅａｓｕｒｅ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， １９７９， ＰＡＭＩ－１（２）： ２２４－２２７． ［１４］ＤＩＭＩＴＲＩＡＤＯＵ Ｅ， ＤＯＬＮＩＣ ˇ ＡＲ Ｓ， ＷＥＩＮＧＥＳＳＥＬ Ａ． Ａｎ ｅｘａｍｉｎａｔｉｏｎ ｏｆ ｉｎｄｅｘｅｓ ｆｏｒ ｄｅｔｅｒｍｉｎｉｎｇ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ｉｎ ｂｉｎａｒｙ ｄａｔａ ｓｅｔｓ［ Ｊ］． Ｐｓｙｃｈｏｍｅｔｒｉｋａ， ２００２， ６７ （１）： １３７－１５９． ［１５］ＫＲＺＡＮＯＷＳＫＩ Ｗ Ｊ， ＬＡＩ Ｙ Ｔ． Ａ ｃｒｉｔｅｒｉｏｎ ｆｏｒ ｄｅｔｅｒｍｉｎｉｎｇ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｇｒｏｕｐｓ ｉｎ ａ ｄａｔａ ｓｅｔ ｕｓｉｎｇ ｓｕｍ⁃ｏｆ⁃ｓｑｕａｒｅｓ ｃｌｕｓｔｅｒｉｎｇ［Ｊ］． Ｂｉｏｍｅｔｒｉｃｓ， １９８８， ４４（１）： ２３－３４． ［１６］周世兵， 徐振源， 唐旭清． Ｋ⁃ｍｅａｎｓ 算法最佳聚类数确 定方法［Ｊ］． 计算机应用， ２０１０， ３０（８）： １９９５－１９９８． ＺＨＯＵ Ｓｈｉｂｉｎｇ， ＸＵ Ｚｈｅｎｙｕａｎ， ＴＡＮＧ Ｘｕｑｉｎｇ． Ｍｅｔｈｏｄ ｆｏｒ ｄｅｔｅｒｍｉｎｉｎｇ ｏｐｔｉｍａｌ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ｉｎ Ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１０， ３０（８）： １９９５－１９９８． ［１７］ ＫＡＰＰ Ａ Ｖ， ＴＩＢＳＨＩＲＡＮＩ Ｒ． Ａｒｅ ｃｌｕｓｔｅｒｓ ｆｏｕｎｄ ｉｎ ｏｎｅ ｄａｔａｓｅｔ ｐｒｅｓｅｎｔ ｉｎ ａｎｏｔｈｅｒ ｄａｔａｓｅｔ［Ｊ］． Ｂｉｏｓｔａｔｉｓｔｉｃｓ， ２００７， ８（１）： ９－３１． ［１８］周世兵． 聚类分析中的最佳聚类数确定方法研究及应 用［Ｄ］． 无锡： 江南大学， ２０１１． ＺＨＯＵ Ｓｈｉｂｉｎｇ． Ｒｅｓｅａｒｃｈ ａｎｄ ａｐｐｌｉｃａｔｉｏｎ ｏｎ ｄｅｔｅｒｍｉｎｉｎｇ ｏｐｔｉｍａｌ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒ ｉｎ ｃｌｕｓｔｅｒ ａｎａｌｙｓｉｓ［Ｄ］． Ｗｕｘｉ： Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， ２０１１． ［１９］ Ｇｏｗｅｒ Ｊ Ｃ， Ｒｏｓｓ Ｇ Ｊ Ｓ． Ｍｉｎｉｍｕｍ ｓｐａｎｎｉｎｇ ｔｒｅｅｓ ａｎｄ ｓｉｎｇｌｅ ｌｉｎｋａｇｅ ｃｌｕｓｔｅｒ ａｎａｌｙｓｉｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ ｒｏｙａｌ ｓｔａｔｉｓｔｉｃａｌ ｓｏｃｉｅｔｙ， １９６９， １８（１）：５４－６４． ［ ２０ ］ ＭＡＣＱＵＥＥＮ Ｊ． Ｓｏｍｅ ｍｅｔｈｏｄｓ ｆｏｒ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｎｄ ａｎａｌｙｓｉｓ ｏｆ ｍｕｌｔｉｖａｒｉａｔｅ ｏｂｓｅｒｖａｔｉｏｎｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ｔｈ Ｂｅｒｋｅｌｅｙ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｍａｔｈｅｍａｔｉｃａｌ Ｓｔａｔｉｓｔｉｃｓ ａｎｄ Ｐｒｏｂａｂｉｌｉｔｙ． Ｂｅｒｋｅｌｅｙ， ＵＳＡ， １９６７： ２８１－２９７． 作者简介： 冯柳伟，女，１９９２ 年生，硕士研究 生，研究方向为聚类算法。 常冬霞，女，１９７７ 年生，副教授，硕 士生导师，主要研究方向为进化计算、 非监督分类算法、图像分割以及图像分 类。 发表学术论文 １０ 余篇，其中 ＳＣＩ 检 索 ５ 篇，ＥＩ 检索 ２ 篇。 邓勇，男，１９７４ 年生，副研究员，博 士，主要研究方向为智能信息处理、数 据库系统技术及应用等。 主持和参与 国家“８６３”计划 １ 项，北京市自然科学 基金项目 １ 项。 发表学术论文 ２０ 余 篇，其中收录 １０ 余篇。 ·７４· 智 能 系 统 学 报 第 １２ 卷