基于粒计算的k值选取及其应用

卞彩峰，邱建林，陈燕云，陆鹏程，陈璐璐

（1.南通大学 电子信息学院，江苏 南通226019；2.南通大学 计算机科学与技术学院，江苏 南通226019；3.南通大学 工程训练中心，江苏 南通226019）

0 引 言

k－means算法存在聚类数目难以确定，选取初始聚类中心随机性比较大等问题。Al－Shboul等［1］通过结合遗传算法选择最优的初始聚类中心，提高了聚类的准确性；文献［2，3］为了提高k－means算法的准确性和有效性，提出了结合系统的方法来选择初始聚类中心，但是没有考虑到k值选取的问题；文献 ［4，5］以BWP为聚类有效性评价指标确定最佳聚类数目，但时间复杂度较高且会受到噪音点的干扰；周涛［6］提出了一种自适应粗糙k－means算法，降低了对噪声的敏感度；Dutta等［7］通过自动选取k值与人为经验结合来确定k－means算法中的参数。聚类是在一个统一的粒度下分析问题，是基于相似度函数需找一个最优的粒度［8］。本文通过引入粒计算改进类间距和类内距离来均衡聚类有效性函数，从而选取合适的k值，并通过UCI机器学习数据库标准数据集验证算法的正确性和可行性。将改进的算法应用于数字农业玉米良种选育中，对玉米品种进行综合评价，从而选出玉米良种。

1 相关知识

1.1 k－means聚类算法简介

k－means算法是由MacQueen提出的，自提出以来，引起了国内外很多学者的关注。它基于 “物以类聚，人以群分”的思想，是一种常用的划分聚类算法，通过将聚类对象划分到距离最近的均值中心所在的簇，然后不断更新均值中心的方法，得到聚类结果。聚类结果满足同一个簇中的对象之间具有较高的相似度，而不同簇中的对象的差异度较高。k－means算法的基本思想就是随机选取k个对象作为初始聚类中心 ｛c1，c2，…，ck｝，然后将剩余的对象按照某种相似性度量分配给相应最近的簇中心Ci，得到k个簇C1，C2，…，Ck，再计算每个簇的中心作为新的聚类中心，重复此过程，直到簇中心不再变化。

1.2 粒计算相关理论

设K ＝（U，R）是一个知识库，P ∈R 为论域U 上的等价关系，称为知识＝｛X1，X2，…，Xn｝；知识P ∈R 的粒度，记为

定义1 粒子密度。设U 为论域，知识P 在U 上的划分为｛X1，X2，…，Xn｝，则粒子Xi的密度定义为［9］

定义2 属性的分辨能力。样本集U 根据第l个属性值al划分为｛X1，X2，…，Xn｝，则属性l的分辨能力［10］为

式中：U—— 论域，n——划分块数；ωl值越大，表明属性l的分辨能力越弱，反之越强。

定义3 样本相似度。设K ＝（U，R）为聚类空间，U 为论域，R 是属性集合，样本相似度函数定义为

样本个数为n，则平均相似度可表示为

1.3 DTOPSIS综合评价法

DTOPSIS 法［10］（dynamic technique for order prefe－rence by similarity to ideal solution）即逼近理想解的排序法，它借助于多目标决策问题的 “理想解”和 “负理想解”进行排序，将每个指标都化为可比较的规范化指标，找出每个规范化指标的 “理想解”和 “负理想解”，因其能详细比较各指标间的差异而被广泛应用于评价问题中。其步骤为：

（1）将所需评价的样本指标建立为评价矩阵

（2）进行无量纲化处理

（3）建立加权的规范化决策矩阵R，其中元素Rij＝WjZij，Wj是第j个指标的权重；

（4）求出品种形状的 “理想解”和 “负理想解”

（5）得到各品种与理想解和负理想解的距离

2 基于粒计算的k－means算法的改进

k－means算法的改进主要有以下几个方面：一是在聚类中心的选取上进行改进；二是对k 值的选取上进行研究；三是在相似度度量方法和适应度函数上的改进；四是其它算法结合。

本文通过将粒计算应用到k－means算法中，选择密度最大的粗糙粒子的均值作为聚类的初始中心点；将属性权重与属性分辨能力结合，计算聚类后类间距和类内距，准则函数是由类内距离和类间距离共同作用，本文采用的优化准则函数能有效地均衡类内距离和类间距离的作用。当聚类函数有效性值最高时，表明聚类的结果最好。

2.1 准则函数

（1）类内距离。根据聚类目的，通过类内距离来表示样本对象间的相似性，平均类内距离越小则类内样本相似性越高。其定义式为

其中，考虑到每个属性对于决策的重要度不同，采用属性分辨能力和属性权重对数据共同影响 （ω ＞0）。

（2）类间距离。用来评价各个类之间的差异性，随着k增加，类间差异程度增加。为了使类间距离和类内距离达到一个平衡状态，为类间分离程度设置参数w

式中：Ci，Cj——第i类和第j类的聚类中心——聚类中心之间距离的个数。

（3）准则函数。聚类的目的是尽量缩减类内距离，增加类间距离。本文的聚类有效性函数综合考虑了类内距离，类间距离以及k 值的作用。当有效性函数值达到最大时，得到最优的聚类结果。在保证聚类结果最优的情况下，k值选取越小越好。定义准则函数为

2.2 算法描述

输入：包含n个样本对象的数据集。

输出：聚类结果。

步骤1 样本归一化处理，并计算每个属性的分辨能力ωl和属性权重w；

步骤2 根据样本之间的相似函数S，构造样本间的不可辨识矩阵M，并归类得到粗粒度集｛X1，X2，…，Xn｝；

步骤3 按式 （2）计算每个粒子的密度，选取密度值最大的前k个粒子的均值作为聚类中心；

步骤4 进行k－means聚类，并更新聚类中心；

步骤5 根据式 （12）计算聚类有效性函数值f，f 取值最大时对应的k值即为最佳聚类数k；

2.3 实验结果与分析

为测试算法的正确性及可行性，在UCI机器学习数据库标准数据集上进行实验。实验环境为Windows 7操作系统下MATLAB 2010b 编程环境，硬件条件为Intel（R）Core（TM）i3－3220CPU＠3.30GHz，2GB内存。

2.3.1 算法的正确性验证

通常聚类数目k的最小值为2，对于k的最大值的选取，杨善林研究了k值最优解kopt及其上界kmax的条件，验证了经验规则kmax≤的合理性，n为样本数目。Frey等提出了AP算法来确定最大的k值，该算法能够快速有效的缩小kmax。由AP算法可知，iris数据库的最高聚类数为6；wine数据库的最高聚类数为9，而pima－indians－diabetes的最好聚类数为8。经MATLAB运算对于不同k值情况下有效性函数值，如图1～图3所示。

图1 iris数据集

图2 wine数据集

图3 pima－indians－dibetes数据集

由图1，对于iris数据集，当k＝3时，聚类的有效性函数最大，此时聚类效果最优，与UCI数据库中描述分为三类相符；由图2 可知，对于wine数据，当k＝3 时，聚类的有效性函数最大，此时聚类效果最优，与UCI数据库中描述分为三类相符；由图3 可知，对于pima－indians－dibetes数据，当k＝2时，聚类的有效性函数最大，此时聚类效果最优，与UCI数据库中描述分为三类相符。实验结果表明，算法能够保证k值选取的正确性。

2.3.2 算法的可行性验证

将改进的聚类有效性指标、DB指标、CH 指标、Dunn指标、Sil指标、BWP指标都应用于上述数据集，从而比较各聚类有效性指标的性能。

由表1可以看出，改进的聚类有效性指标确定最佳聚类数的准确率比其它几种聚类有效性指标都高。因此可以验证改进的聚类有效性指标的可行性。

3 基于粒计算的k－means算法的应用

本文选取南通市农业信息组2006 年玉米数据集 （Y组）为样本集 （见表2）。该玉米信息表由多张表构成，涉及到的属性多达二十几种，分别为全生育期、株高、穗高、双穗率、穗长、穗粗、穗形、穗行数、行粒数等等。

表1 聚类结果比较

表2 原始玉米样本集 （Y 组）

3.1 玉米样本集S的k值选取

取玉米子类数据进行属性约简，得到约简后的属性为｛全生育期，穗高，穗粗，行粒数，千粒重，出籽率，小区产量｝，即可得约简后的数据集见表3。

计算约简后数据集的属性分辨能力和初始聚类中心点，然后进行k聚类。由于样本个数为51，k值的选取为2～7。经MATLAB运算，可得数值见表4。

根据有效性函数得出最佳k值为3，即kopt＝3。算法运行每次会有些许差别，对整体聚类效果影响不大，聚类结果如下：

第一类：Y1，Y30；

第二类：Y3，Y5，Y6，Y7，Y9，Y11，Y12，Y15，Y17，Y18，Y19，Y20，Y21，Y25，Y33，Y34，Y38，Y40，Y41，Y42，Y45，Y49，Y50，Y51；

第三类：Y2，Y4，Y8，Y10，Y13，Y14，Y16，Y22，Y23，Y24，Y26，Y27，Y28，Y29，Y31，Y32， Y35，Y36，Y37，Y39，Y43，Y44，Y46，Y47，Y48。

由原始数据分析可知，第一类中两个样本中Y1穗高和千粒重特别低，Y30的株高和产量都很低，可作为异常点删除。第二类的没有明显的优势特征，品种一般。第三类的特点较为突出，株高、穗高、千粒重、穗粗、区产量都很高，符合我们所需要的良种要求，适合用于育种。由以上分析可知第三类为玉米良种集。

表3 经属性约简后的玉米样本集 （Y 组）

3.2 玉米种子的综合评价

对聚类后的良种集中的玉米种子进行综合评价，对其进行排名。采用DTOPSIS法对玉米种子进行排序，具体步骤前文已经介绍，不再赘述。经计算，第三类中玉米良种样本的相对接近度 （保留四位有效数值）。

表4 不同k值下的各项指标的数值

将相对接近度按大小进行排序，可得精英玉米良种为Y47，Y8，Y22，Y36，Y35。这一实验结果与南通市农业信息组给出的玉米排名吻合。

为确保我们所得的玉米良种的质量，对玉米样本集进行了k－means算法聚类，这样使得优良品种聚集在一起，减少了盲目选种的复杂性和工作量。综合得分比较高的玉米品种作为最后的玉米良种，减少了误把劣种作良种的可能，使得到的玉米良种更加优良。

4 结束语

本文将粒度概念引入到准则函数中，综合考虑类间距和类内距，用改进后的准则函数来判断聚类有效性函数选取最佳的聚类数目。采用UCI国际标准数据集验证了算法的正确性和可行性，解决了k－均值聚类算法需要事先给定合适k值的问题。最后将其应用的实际的玉米良种选育中，得出所需要的玉米良种。为了提高计算效率，还可以对初始聚类中心进行优化，提高算法性能，减少算法的运行时间，这方面有待进一步研究。

［1］Al－Shboul B，Myaeng SH.Initializing k－means using genetic algorithms［J］.World Academy of Science，Engineering and Technology，2009，54 （30）：114－118.

［2］Nazeer KAA，Sebastian MP.Improving the accuracy and effi－ciency of the k－means clustering algorithm ［C］／／Proceedings of the World Congress on Engineering，2009：1－3.

［3］LI Lian，LUO Ke，ZHOU Boxiang.Rough clustering algorithm based on granular computing ［J］.Application Research of Computers，2013，30 （10）：2916－2919 （in Chinese）.［李莲，罗可，周博翔.基于粒计算的粗糙集聚类算法 ［J］.计算机应用研究，2013，30 （10）：2916－2919.］

［4］ZHOU Shibing，XU Zhenyuan，TANG Xuqing.Method for determining optimal number of clusters in K－means clustering algorithm ［J］.Journal of Computer Applications，2010，30（8）：1995－1998 （in Chinese）. ［周世兵，徐振源，唐旭清.K－means算法最佳聚类数确定方法 ［J］.计算机应用，2010，30 （8）：1995－1998.］

［5］XIE Juanying，MA Qing，XIE Weixin.A new algorithm to determine the optimal number of clusters ［J］.Journal of Shanxi Normal University（Natural Science Edition），2012，40（1）：13－18 （in Chinese）. ［谢娟英，马箐，谢维信.一种确定最佳聚类书的新算法 ［J］.山西师范大学学报 （自然科学版），2012，40 （1）：13－18.］

［6］ZHOU Tao.Adaptive rough k－means clustering algorithm ［J］.Computer Engineering and Applications，2010，46 （26）：7－10（in Chinese）.［周涛.具有自适应参数的粗糙k－means聚类算法 ［J］.计算机工程与应用，2010，46 （26）：7－10.］

［7］Dutta H，Passonneau RJ，Lee A，et al.Learning parameters of the K－means algorithm from subjective human annotation［C］／／FLAIRS Conference，2011.

［8］Ding Shifei，Xu Li，Zhu Hong，et al.Research and progress of cluster algorithms based on granular computing ［J］.International Journal of Digital Content Technology and its Applications，2010，4 （5）：96－104.

［9］MA Qing，XIE Juanying.New K－mediods clustering algorithm based on granular computing ［J］.Journal of Computer Applications，2012，32 （7）：1973－1977 （in Chinese）. ［马箐，谢娟英.基于粒计算的K－mediods聚类算法 ［J］.计算机应用，2012，32 （7）：1973－1977.］

［10］JIANG Yongping，LIU Shuidong.Results comparison of comprehensive evaluation tomato varieties with DTOPSIS and grey related degree ［J］.Chinese Agricultural Science Bulletin，2010，26 （22）：259－263 （in Chinese）.［姜永平，刘水东.DTOPSIS法和灰色关联度法在番茄品种综合评价中的应用比较 ［J］.中国农学通报，2010，26 （22）：259－263.］