第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]岳士弘，黄妮，王鹏龙.基于矩阵特征值分析的模糊聚Ｓｏｙｂｅａｎ⁃ｓｍａｌｌ来验证 ＣＨ 指标、ＢＷＰ 指标、ＩＧＰ 指标 和 ＮＦＳ 指标在确定类别数时的性能。 表 ８ 给出了数据集 Ｗｉｎｅ 在采用不同评价指标 时，在不同的类别数下的指标值，其中带下划线的 数据是该指标下的最大值。 ＮＦＳ 指标和 ＢＷＰ 指标 在类别数 Ｋ ＝ ３ 时取最大值，而其他指标在类别数 Ｋ ＝ ２ 时取最大值，但是由于数据集 Ｗｉｎｅ 的真实类别 数为 ３，因此采用 ＮＦＳ 指标和 ＢＷＰ 指标可以得到正 确的类别数，而采用其他评价指标则无法得到正确 的类别数。 表 ８ Ｗｉｎｅ 的指标值 Ｔａｂｌｅ ８ Ｔｈｅ ｉｎｄｅｘ ｖａｌｕｅ ｆｏｒ Ｗｉｎｅ 类别数 ＣＨ ＢＷＰ ＩＧＰ ＮＦＳ ２ ７ ５２１ ６００ ０．３２５ ０７ ０．９６２ １７ ０．８６７ ０６ ３ ４ ９２６ ８５０ ０．３３４ ０４ ０．９４０ ６２ ０．９００ ９ ４ ３ ３５６ ４４０ ０．３０２ ３ ０．７８９ ５２ ０．７７４ ７７ ５ ２ ５７８ ８４０ ０．２６９ ５８ ０．７１ ０．６９７ ４６ ６ ２ １４７ ４１５ ０．２３２ ５５ ０．６７３ ６６ ０．６９２ １２ ７ １ ８２３ ９０５ ０．２０３ ８２ ０．６４９ ８３ ０．６６６ ３５ ８ １ ６０８ ８７０ ０．１８７ ７１ ０．６４８ １５ ０．６３３ ２ ９ １ ４３８ ７６５ ０．１８４ ７１ ０．６１２ ８１ ０．６１６ ５５ １０ １ ２９１ ８５０ ０．１７８ ７１ ０．５９４ ３３ ０．５７６ ６ 最终类别数 ２ ３ ２ ３ 表 ９ 给出了 ４ 组真实数据集分别在采用不同评 价指标下得到的类别数，这里依然是运行多次实验 通过投票准则确定最终的类别数，括号中的数据表 示类别数出现的百分比。 参考表 １ 中各数据集的真 实类别数，可以得到如下结论：采用 ＮＦＳ 指标可以 得到所有真实数据集的正确的类别数，其中对于 Ｂａｌａｎｃｅ Ｓｃａｌｅ 和 Ｗｉｎｅ 数据集，评价结果稳定，效果 较好，而对于 ＩＲＩＳ 和 Ｓｏｙｂｅａｎ⁃ｓｍａｌｌ 数据集，评价结 果差一点，只有 ６０％ 和 ４５％ 的正确率；然而采用 ＢＷＰ 指标只可以得到数据集 Ｗｉｎｅ 的正确类别数， 而且评价结果稳定；但是采用 ＣＨ 指标和 ＩＧＰ 指标 则无法得到数据集的正确类别数。 表 ９ 真实数据集的类别数 Ｔａｂｌｅ ９ Ｔｈｅ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ ｏｆ ｔｈｅ ｒｅａｌ ｄａｔａｓｅｔｓ 数据集 ＣＨ ＢＷＰ ＩＧＰ ＮＦＳ ＩＲＩＳ ２（１００） ２（１００） ２（１００） ３（６０） Ｂａｌａｎｃｅ Ｓｃａｌｅ ２（１００） ８（７０） ２（１００） ３（１００） Ｗｉｎｅ ２（１００） ３（１００） ２（１００） ３（１００） Ｓｏｙｂｅａｎ⁃ｓｍａｌｌ ２（１００） ３（３２．９） ３（４０） ４（４５） ５ 结束语 众所周知，很多聚类算法需要根据先验知识给 出算法所需要的类别数。 但是，在很多实际应用中 很难获得有效的先验知识，因此确定聚类问题的类 别数成为了一个研究的热点。 本文首先基于最近 邻一致性和最远邻相异性的原则，提出了一种最近 最远得分评价指标（ＮＦＳ），并在此基础上提出了一 种基于 ＮＦＳ 自动聚类算法，实现了对类别数和类别 中心的自动估计。 与已经提出的评价指标相比， ＮＦＳ 指标是基于数据集统计信息的指标，而且 ＮＦＳ 指标考虑了最近样本和最远样本两个方面，通过评 分机制还保证了每个样本都对评价指标产生影响。 从而使 ＮＦＳ 指标在 ＩＲＩＳ 等数据集中呈现较好的结 果。 但是 ＮＦＳ 指标并不是最完美的，因此还需要继 续进行相关研究。 参考文献： ［１］刘恋， 常冬霞， 邓勇． 动态小生境人工鱼群算法的图像 分割［Ｊ］． 智能系统学报， ２０１５， １０（５）： ６６９－６７４． ＬＩＵ Ｌｉａｎ， ＣＨＡＮＧ Ｄｏｎｇｘｉａ， ＤＥＮＧ Ｙｏｎｇ． Ａｎ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｄｙｎａｍｉｃ ｎｉｃｈｅ ａｒｔｉｆｉｃｉａｌ ｆｉｓｈ⁃ ｓｗａｒｍ ａｌｇｏｒｉｔｈｍ ［ Ｊ ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１５， １０（５）： ６６９－６７４． ［２］ＮＩＫＯＬＡＯＵ Ｔ Ｇ， ＫＯＬＯＫＯＴＳＡ Ｄ Ｓ， ＳＴＡＶＲＡＫＡＫＩＳ Ｇ Ｓ， ｅｔ ａｌ． Ｏｎ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ｏｆｆｉｃｅ ｂｕｉｌｄｉｎｇｓ􀆳 ｅｎｅｒｇｙ ａｎｄ ｔｈｅｒｍａｌ ｃｏｍｆｏｒｔ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ［ Ｊ ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｓｍａｒｔ ｇｒｉｄ， ２０１２， ３（４）： ２１９６－２２１０． ［３］ ＣＨＡＮＧ Ｈｏｎｇ， ＹＥＵＮＧ Ｄ Ｙ． Ｒｏｂｕｓｔ ｐａｔｈ⁃ｂａｓｅｄ ｓｐｅｃｔｒａｌ ｃｌｕｓｔｅｒｉｎｇ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｔｅｎｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ． Ｂｅｉｊｉｎｇ， Ｃｈｉｎａ， ２００５， １： ２７８－２８５． ［ ４ ］ ＳＨＩ Ｊｉａｎｂｏ， ＭＡＬＩＫ Ｊ． Ｎｏｒｍａｌｉｚｅｄ ｃｕｔｓ ａｎｄ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０００， ２２（８）： ８８８－９０５． ［５］ＸＩＥ Ｘ Ｌ， ＢＥＮＩ Ｇ． Ａ ｖａｌｉｄｉｔｙ ｍｅａｓｕｒｅ ｆｏｒ Ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， １９９１， １３（８）： ８４１－８４７． ［６］ＰＡＬ Ｎ Ｒ， ＢＥＺＤＥＫ Ｊ Ｃ． Ｏｎ ｃｌｕｓｔｅｒ ｖａｌｉｄｉｔｙ ｆｏｒ ｔｈｅ ｆｕｚｚｙ ｃ⁃ ｍｅａｎｓ ｍｏｄｅｌ ［ Ｊ ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｆｕｚｚｙ ｓｙｓｔｅｍｓ， １９９５， ３（３）： ３７０－３７９． ［７］郑宏亮， 徐本强， 赵晓慧， 等． 新的模糊聚类有效性指 标［Ｊ］． 计算机应用， ２０１４， ３４（８）： ２１６６－２１６９． ＺＨＥＮＧ Ｈｏｎｇｌｉａｎｇ， ＸＵ Ｂｅｎｑｉａｎｇ， ＺＨＡＯ Ｘｉａｏｈｕｉ， ｅｔ ａｌ． Ｎｏｖｅｌ ｖａｌｉｄｉｔｙ ｉｎｄｅｘ ｆｏｒ ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１４， ３４（８）： ２１６６－２１６９． ［８］岳士弘， 黄媞， 王鹏龙． 基于矩阵特征值分析的模糊聚 第 １ 期 冯柳伟，等：最近最远得分的聚类性能评价指标 ·７３·