基于粒計(jì)算的k值選取及其應(yīng)用

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

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

0 引 言

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

1 相關(guān)知識(shí)

1.1 k－means聚類算法簡(jiǎn)介

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

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

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

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

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

式中：U—— 論域，n——?jiǎng)澐謮K數(shù)；ωl值越大，表明屬性l的分辨能力越弱，反之越強(qiáng)。

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

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

1.3 DTOPSIS綜合評(píng)價(jià)法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 算法描述

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

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

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

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

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

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

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

2.3 實(shí)驗(yàn)結(jié)果與分析

為測(cè)試算法的正確性及可行性，在UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yà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 算法的正確性驗(yàn)證

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

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

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

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

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

2.3.2 算法的可行性驗(yàn)證

將改進(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)都高。因此可以驗(yàn)證改進(jìn)的聚類有效性指標(biāo)的可行性。

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

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

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

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

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

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

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

根據(jù)有效性函數(shù)得出最佳k值為3，即kopt＝3。算法運(yùn)行每次會(huì)有些許差別，對(duì)整體聚類效果影響不大，聚類結(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ù)分析可知，第一類中兩個(gè)樣本中Y1穗高和千粒重特別低，Y30的株高和產(chǎn)量都很低，可作為異常點(diǎn)刪除。第二類的沒(méi)有明顯的優(yōu)勢(shì)特征，品種一般。第三類的特點(diǎn)較為突出，株高、穗高、千粒重、穗粗、區(qū)產(chǎn)量都很高，符合我們所需要的良種要求，適合用于育種。由以上分析可知第三類為玉米良種集。

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

3.2 玉米種子的綜合評(píng)價(jià)

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

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

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

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

4 結(jié)束語(yǔ)

本文將粒度概念引入到準(zhǔn)則函數(shù)中，綜合考慮類間距和類內(nèi)距，用改進(jìn)后的準(zhǔn)則函數(shù)來(lái)判斷聚類有效性函數(shù)選取最佳的聚類數(shù)目。采用UCI國(guó)際標(biāo)準(zhǔn)數(shù)據(jù)集驗(yàn)證了算法的正確性和可行性，解決了k－均值聚類算法需要事先給定合適k值的問(wèn)題。最后將其應(yīng)用的實(shí)際的玉米良種選育中，得出所需要的玉米良種。為了提高計(jì)算效率，還可以對(duì)初始聚類中心進(jìn)行優(yōu)化，提高算法性能，減少算法的運(yùn)行時(shí)間，這方面有待進(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ì)算的粗糙集聚類算法 ［J］.計(jì)算機(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］.計(jì)算機(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é)報(bào) （自然科學(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］.計(jì)算機(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）. ［馬箐，謝娟英.基于粒計(jì)算的K－mediods聚類算法 ［J］.計(jì)算機(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)度法在番茄品種綜合評(píng)價(jià)中的應(yīng)用比較 ［J］.中國(guó)農(nóng)學(xué)通報(bào)，2010，26 （22）：259－263.］