卞彩峰，邱建林，陳燕云，陸鵬程，陳璐璐

（1.南通大學(xué) 電子信息學(xué)院，江蘇 南通226019；2.南通大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，江蘇 南通226019；3.南通大學(xué) 工程訓(xùn)練中心，江蘇 南通226019）

0 引 言

k－means算法存在聚類數(shù)目難以確定，選取初始聚類中心隨機性比較大等問題。Al－Shboul等［1］通過結(jié)合遺傳算法選擇最優(yōu)的初始聚類中心，提高了聚類的準(zhǔn)確性；文獻(xiàn)［2，3］為了提高k－means算法的準(zhǔn)確性和有效性，提出了結(jié)合系統(tǒng)的方法來選擇初始聚類中心，但是沒有考慮到k值選取的問題；文獻(xiàn) ［4，5］以BWP為聚類有效性評價指標(biāo)確定最佳聚類數(shù)目，但時間復(fù)雜度較高且會受到噪音點的干擾；周濤［6］提出了一種自適應(yīng)粗糙k－means算法，降低了對噪聲的敏感度；Dutta等［7］通過自動選取k值與人為經(jīng)驗結(jié)合來確定k－means算法中的參數(shù)。聚類是在一個統(tǒng)一的粒度下分析問題，是基于相似度函數(shù)需找一個最優(yōu)的粒度［8］。本文通過引入粒計算改進(jìn)類間距和類內(nèi)距離來均衡聚類有效性函數(shù)，從而選取合適的k值，并通過UCI機器學(xué)習(xí)數(shù)據(jù)庫標(biāo)準(zhǔn)數(shù)據(jù)集驗證算法的正確性和可行性。將改進(jìn)的算法應(yīng)用于數(shù)字農(nóng)業(yè)玉米良種選育中，對玉米品種進(jìn)行綜合評價，從而選出玉米良種。

1 相關(guān)知識

1.1 k－means聚類算法簡介

k－means算法是由MacQueen提出的，自提出以來，引起了國內(nèi)外很多學(xué)者的關(guān)注。它基于 “物以類聚，人以群分”的思想，是一種常用的劃分聚類算法，通過將聚類對象劃分到距離最近的均值中心所在的簇，然后不斷更新均值中心的方法，得到聚類結(jié)果。聚類結(jié)果滿足同一個簇中的對象之間具有較高的相似度，而不同簇中的對象的差異度較高。k－means算法的基本思想就是隨機選取k個對象作為初始聚類中心 ｛c1，c2，…，ck｝，然后將剩余的對象按照某種相似性度量分配給相應(yīng)最近的簇中心Ci，得到k個簇C1，C2，…，Ck，再計算每個簇的中心作為新的聚類中心，重復(fù)此過程，直到簇中心不再變化。

1.2 粒計算相關(guān)理論

設(shè)K ＝（U，R）是一個知識庫，P ∈R 為論域U 上的等價關(guān)系，稱為知識＝｛X1，X2，…，Xn｝；知識P ∈R 的粒度，記為

定義1 粒子密度。設(shè)U 為論域，知識P 在U 上的劃分為｛X1，X2，…，Xn｝，則粒子Xi的密度定義為［9］

定義2 屬性的分辨能力。樣本集U 根據(jù)第l個屬性值al劃分為｛X1，X2，…，Xn｝，則屬性l的分辨能力［10］為

式中：U—— 論域，n——劃分塊數(shù)；ωl值越大，表明屬性l的分辨能力越弱，反之越強。

定義3 樣本相似度。設(shè)K ＝（U，R）為聚類空間，U 為論域，R 是屬性集合，樣本相似度函數(shù)定義為

樣本個數(shù)為n，則平均相似度可表示為

1.3 DTOPSIS綜合評價法

DTOPSIS 法［10］（dynamic technique for order prefe－rence by similarity to ideal solution）即逼近理想解的排序法，它借助于多目標(biāo)決策問題的 “理想解”和 “負(fù)理想解”進(jìn)行排序，將每個指標(biāo)都化為可比較的規(guī)范化指標(biāo)，找出每個規(guī)范化指標(biāo)的 “理想解”和 “負(fù)理想解”，因其能詳細(xì)比較各指標(biāo)間的差異而被廣泛應(yīng)用于評價問題中。其步驟為：

（1）將所需評價的樣本指標(biāo)建立為評價矩陣

（2）進(jìn)行無量綱化處理

（3）建立加權(quán)的規(guī)范化決策矩陣R，其中元素Rij＝WjZij，Wj是第j個指標(biāo)的權(quán)重；

（4）求出品種形狀的 “理想解”和 “負(fù)理想解”

（5）得到各品種與理想解和負(fù)理想解的距離

2 基于粒計算的k－means算法的改進(jìn)

k－means算法的改進(jìn)主要有以下幾個方面：一是在聚類中心的選取上進(jìn)行改進(jìn)；二是對k 值的選取上進(jìn)行研究；三是在相似度度量方法和適應(yīng)度函數(shù)上的改進(jìn)；四是其它算法結(jié)合。

本文通過將粒計算應(yīng)用到k－means算法中，選擇密度最大的粗糙粒子的均值作為聚類的初始中心點；將屬性權(quán)重與屬性分辨能力結(jié)合，計算聚類后類間距和類內(nèi)距，準(zhǔn)則函數(shù)是由類內(nèi)距離和類間距離共同作用，本文采用的優(yōu)化準(zhǔn)則函數(shù)能有效地均衡類內(nèi)距離和類間距離的作用。當(dāng)聚類函數(shù)有效性值最高時，表明聚類的結(jié)果最好。

2.1 準(zhǔn)則函數(shù)

（1）類內(nèi)距離。根據(jù)聚類目的，通過類內(nèi)距離來表示樣本對象間的相似性，平均類內(nèi)距離越小則類內(nèi)樣本相似性越高。其定義式為

其中，考慮到每個屬性對于決策的重要度不同，采用屬性分辨能力和屬性權(quán)重對數(shù)據(jù)共同影響 （ω ＞0）。

（2）類間距離。用來評價各個類之間的差異性，隨著k增加，類間差異程度增加。為了使類間距離和類內(nèi)距離達(dá)到一個平衡狀態(tài)，為類間分離程度設(shè)置參數(shù)w

式中：Ci，Cj——第i類和第j類的聚類中心——聚類中心之間距離的個數(shù)。

（3）準(zhǔn)則函數(shù)。聚類的目的是盡量縮減類內(nèi)距離，增加類間距離。本文的聚類有效性函數(shù)綜合考慮了類內(nèi)距離，類間距離以及k 值的作用。當(dāng)有效性函數(shù)值達(dá)到最大時，得到最優(yōu)的聚類結(jié)果。在保證聚類結(jié)果最優(yōu)的情況下，k值選取越小越好。定義準(zhǔn)則函數(shù)為

2.2 算法描述

輸入：包含n個樣本對象的數(shù)據(jù)集。

輸出：聚類結(jié)果。

步驟1 樣本歸一化處理，并計算每個屬性的分辨能力ωl和屬性權(quán)重w；

步驟2 根據(jù)樣本之間的相似函數(shù)S，構(gòu)造樣本間的不可辨識矩陣M，并歸類得到粗粒度集｛X1，X2，…，Xn｝；

步驟3 按式 （2）計算每個粒子的密度，選取密度值最大的前k個粒子的均值作為聚類中心；

步驟4 進(jìn)行k－means聚類，并更新聚類中心；

步驟5 根據(jù)式 （12）計算聚類有效性函數(shù)值f，f 取值最大時對應(yīng)的k值即為最佳聚類數(shù)k；

2.3 實驗結(jié)果與分析

為測試算法的正確性及可行性，在UCI機器學(xué)習(xí)數(shù)據(jù)庫標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行實驗。實驗環(huán)境為Windows 7操作系統(tǒng)下MATLAB 2010b 編程環(huán)境，硬件條件為Intel（R）Core（TM）i3－3220CPU＠3.30GHz，2GB內(nèi)存。

2.3.1 算法的正確性驗證

通常聚類數(shù)目k的最小值為2，對于k的最大值的選取，楊善林研究了k值最優(yōu)解kopt及其上界kmax的條件，驗證了經(jīng)驗規(guī)則kmax≤的合理性，n為樣本數(shù)目。Frey等提出了AP算法來確定最大的k值，該算法能夠快速有效的縮小kmax。由AP算法可知，iris數(shù)據(jù)庫的最高聚類數(shù)為6；wine數(shù)據(jù)庫的最高聚類數(shù)為9，而pima－indians－diabetes的最好聚類數(shù)為8。經(jīng)MATLAB運算對于不同k值情況下有效性函數(shù)值，如圖1～圖3所示。

圖1 iris數(shù)據(jù)集

圖2 wine數(shù)據(jù)集

圖3 pima－indians－dibetes數(shù)據(jù)集

由圖1，對于iris數(shù)據(jù)集，當(dāng)k＝3時，聚類的有效性函數(shù)最大，此時聚類效果最優(yōu)，與UCI數(shù)據(jù)庫中描述分為三類相符；由圖2 可知，對于wine數(shù)據(jù)，當(dāng)k＝3 時，聚類的有效性函數(shù)最大，此時聚類效果最優(yōu)，與UCI數(shù)據(jù)庫中描述分為三類相符；由圖3 可知，對于pima－indians－dibetes數(shù)據(jù)，當(dāng)k＝2時，聚類的有效性函數(shù)最大，此時聚類效果最優(yōu)，與UCI數(shù)據(jù)庫中描述分為三類相符。實驗結(jié)果表明，算法能夠保證k值選取的正確性。

2.3.2 算法的可行性驗證

將改進(jìn)的聚類有效性指標(biāo)、DB指標(biāo)、CH 指標(biāo)、Dunn指標(biāo)、Sil指標(biāo)、BWP指標(biāo)都應(yīng)用于上述數(shù)據(jù)集，從而比較各聚類有效性指標(biāo)的性能。

由表1可以看出，改進(jìn)的聚類有效性指標(biāo)確定最佳聚類數(shù)的準(zhǔn)確率比其它幾種聚類有效性指標(biāo)都高。因此可以驗證改進(jìn)的聚類有效性指標(biāo)的可行性。

3 基于粒計算的k－means算法的應(yīng)用

本文選取南通市農(nóng)業(yè)信息組2006 年玉米數(shù)據(jù)集 （Y組）為樣本集 （見表2）。該玉米信息表由多張表構(gòu)成，涉及到的屬性多達(dá)二十幾種，分別為全生育期、株高、穗高、雙穗率、穗長、穗粗、穗形、穗行數(shù)、行粒數(shù)等等。

表1 聚類結(jié)果比較

表2 原始玉米樣本集 （Y 組）

3.1 玉米樣本集S的k值選取

取玉米子類數(shù)據(jù)進(jìn)行屬性約簡，得到約簡后的屬性為｛全生育期，穗高，穗粗，行粒數(shù)，千粒重，出籽率，小區(qū)產(chǎn)量｝，即可得約簡后的數(shù)據(jù)集見表3。

計算約簡后數(shù)據(jù)集的屬性分辨能力和初始聚類中心點，然后進(jìn)行k聚類。由于樣本個數(shù)為51，k值的選取為2～7。經(jīng)MATLAB運算，可得數(shù)值見表4。

根據(jù)有效性函數(shù)得出最佳k值為3，即kopt＝3。算法運行每次會有些許差別，對整體聚類效果影響不大，聚類結(jié)果如下：

第一類：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。

由原始數(shù)據(jù)分析可知，第一類中兩個樣本中Y1穗高和千粒重特別低，Y30的株高和產(chǎn)量都很低，可作為異常點刪除。第二類的沒有明顯的優(yōu)勢特征，品種一般。第三類的特點較為突出，株高、穗高、千粒重、穗粗、區(qū)產(chǎn)量都很高，符合我們所需要的良種要求，適合用于育種。由以上分析可知第三類為玉米良種集。

表3 經(jīng)屬性約簡后的玉米樣本集 （Y 組）

3.2 玉米種子的綜合評價

對聚類后的良種集中的玉米種子進(jìn)行綜合評價，對其進(jìn)行排名。采用DTOPSIS法對玉米種子進(jìn)行排序，具體步驟前文已經(jīng)介紹，不再贅述。經(jīng)計算，第三類中玉米良種樣本的相對接近度 （保留四位有效數(shù)值）。

表4 不同k值下的各項指標(biāo)的數(shù)值

將相對接近度按大小進(jìn)行排序，可得精英玉米良種為Y47，Y8，Y22，Y36，Y35。這一實驗結(jié)果與南通市農(nóng)業(yè)信息組給出的玉米排名吻合。

為確保我們所得的玉米良種的質(zhì)量，對玉米樣本集進(jìn)行了k－means算法聚類，這樣使得優(yōu)良品種聚集在一起，減少了盲目選種的復(fù)雜性和工作量。綜合得分比較高的玉米品種作為最后的玉米良種，減少了誤把劣種作良種的可能，使得到的玉米良種更加優(yōu)良。

4 結(jié)束語

本文將粒度概念引入到準(zhǔn)則函數(shù)中，綜合考慮類間距和類內(nèi)距，用改進(jìn)后的準(zhǔn)則函數(shù)來判斷聚類有效性函數(shù)選取最佳的聚類數(shù)目。采用UCI國際標(biāo)準(zhǔn)數(shù)據(jù)集驗證了算法的正確性和可行性，解決了k－均值聚類算法需要事先給定合適k值的問題。最后將其應(yīng)用的實際的玉米良種選育中，得出所需要的玉米良種。為了提高計算效率，還可以對初始聚類中心進(jìn)行優(yōu)化，提高算法性能，減少算法的運行時間，這方面有待進(jìn)一步研究。

［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］.計算機應(yīng)用研究，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算法最佳聚類數(shù)確定方法 ［J］.計算機應(yīng)用，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］.山西師范大學(xué)學(xué)報 （自然科學(xué)版），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）.［周濤.具有自適應(yīng)參數(shù)的粗糙k－means聚類算法 ［J］.計算機工程與應(yīng)用，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］.計算機應(yīng)用，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法和灰色關(guān)聯(lián)度法在番茄品種綜合評價中的應(yīng)用比較 ［J］.中國農(nóng)學(xué)通報，2010，26 （22）：259－263.］