黃 松，邱建林

(南通大學(xué) 信息科學(xué)技術(shù)學(xué)院，江蘇 南通 226019)

0 引 言

k-means聚類算法[1-3]是一種基于劃分的數(shù)據(jù)挖掘技術(shù)，此算法操作簡單、效率高、局部搜索性能好，且能有效處理大規(guī)模數(shù)據(jù)，但由于聚類數(shù)目的不確定性和初始聚類中心選取的隨機性，使得聚類結(jié)果波動大、準確率低。針對這些問題，文獻[4]通過改進聚類有效性函數(shù)來選取最佳聚類數(shù)；文獻[5]利用粒計算的屬性分辨能力，降低了屬性值過大對聚類有效性函數(shù)的影響，從而得到最佳聚類數(shù)；文獻[6]提出了一種優(yōu)化初始聚類中心的方法，使聚類結(jié)果更準確；文獻[7]提出了一種基于改進遺傳算法的k-means聚類方法，將遺傳算法的思想引入到聚類算法中，使得聚類結(jié)果更穩(wěn)定，聚類效果更好。但都只考慮了聚類數(shù)目或者初始聚類中心，文獻[8]提出了一種雙重遺傳k-means算法(DGKA)，該算法利用雙層遺傳算法確定聚類數(shù)目和自適應(yīng)控制初始聚類中心，在算法結(jié)束時能同時獲得較優(yōu)聚類數(shù)和初始聚類中心，但此算法的內(nèi)層算法過于依賴外層算法，使得聚類結(jié)果不穩(wěn)定。因此，針對此問題，本文提出了一種改進的遺傳k-means聚類算法(PGKMA)，該算法采用并行計算的方式，解決了DGKA算法中聚類穩(wěn)定性過于依賴外層算法的問題，通過兩個經(jīng)典實例驗證了算法的準確性和有效性，并利用該算法對玉米樣本集進行聚類分析，對聚類后的玉米良種集，采用DTOPSIS(dynamic technique for order preference by similarity to ideal solution)法[5]綜合評價并排序，獲得精英玉米品種，從而指導(dǎo)玉米良種選育工作。

1 相關(guān)知識

1.1 k-means算法

k-means算法的核心思想是根據(jù)隨機給定的聚類數(shù)k，從數(shù)據(jù)集中隨機選擇k個對象作為初始聚類中心，通過某種度量方式(一般采用歐式距離)將數(shù)據(jù)對象劃分到與之距離最近的簇中，然后重新計算聚類中心，再次劃分，不斷重復(fù)此過程，直到聚類中心不再發(fā)生改變。

定義1 設(shè)X=(x1,x2,…,xn)，Y=(y1,y2,…,yn)，X與Y的歐式距離定義為

(1)

k-means算法描述如下：

算法1：k-means聚類算法

輸入：包含n個對象的數(shù)據(jù)集D，聚類數(shù)k

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

(1) begin

(2) 從D中隨機選取k個對象作為初始聚類中心{c1,c2,…,ck};

(3) fori=1:n

(4) forj=1:k

(5) 計算Di與cj的歐式距離，并將其賦給距離最近的簇；

(6) endfor

(7) endfor

(8) 計算每個類的平均值并更新聚類中心；

(9) 重復(fù)(3)到(8)，直到聚類中心不再發(fā)生改變；

(10) 輸出最終聚類結(jié)果S；

(11) end

1.2 遺傳算法

遺傳算法(genetic algorithm，GA)是一種借鑒生物界進化規(guī)律，按照適者生存，優(yōu)勝略汰的遺傳機制，逐步演化形成的一種全局搜索方法。其主要特點是對目標函數(shù)沒有連續(xù)可微的限制；遺傳操作不直接作用于數(shù)據(jù)空間；具有隱含的并行性和全局搜索能力；在搜索空間中能夠自適應(yīng)調(diào)整進化方向，獲取問題的近似最優(yōu)解。因此，遺傳算法被人們廣泛地應(yīng)用于聚類分析[9]、圖像識別[10]、組合優(yōu)化[11]和機器學(xué)習(xí)[12]等領(lǐng)域。

1.3 DTOPSIS綜合評價法

DTOPSIS是一種逼近理想解的綜合排序方法[13]，通過為需要進行評價的樣本建立評價矩陣，對評價矩陣進行無量綱化處理后加權(quán)獲得決策矩陣，然后計算品種的正負理想解，并計算各品種與正負理想解之間的距離，進而得到各品種與理想解之間的相對接近度，最后對相對接近度進行排序獲得最優(yōu)的品種。其具體步驟為：

(1)建立樣本指標評價矩陣

(2)

(2)對評價矩陣無量綱化處理

(3)

(3)建立規(guī)范化決策矩陣R，其中Rij=Wj*Zij，Wj為第j個指標權(quán)重；

(4)計算品種的正負理想解

(4)

(5)計算各品種與正負理想解之間的距離

(5)

(6)計算各品種對理想解的相對接近度

(6)

(7)將相對接近度按大小進行排序，最大的即為最優(yōu)個體。

2 改進的遺傳k-means聚類算法的設(shè)計

針對k-means算法初始聚類中心過于依賴聚類數(shù)目的問題，采用并行計算的方式獲取聚類數(shù)目和初始聚類中心，并行計算過程如圖1所示。

圖1 并行計算結(jié)構(gòu)

PGKMA算法解決了DGKA算法內(nèi)層算法過于依賴外層算法的問題，不僅能同時獲取當(dāng)前最佳聚類數(shù)和初始聚類中心，而且聚類結(jié)果更穩(wěn)定、更準確。綜合考慮算法的特殊性，設(shè)計了合適的編解碼策略，適應(yīng)度函數(shù)和遺傳操作。

2.1 編碼與解碼策略

圖2 初始聚類中心染色體編碼

PGKMA解碼策略，染色體每d個等位基因串組成一個聚類中心。

2.2 適應(yīng)度函數(shù)設(shè)計

定義2 簇內(nèi)對象相似度可由平均類內(nèi)距表示為

(7)

其中，xij為第i類的第j個對象；Ni為第i類樣本容量；ci為第i類聚類中心。

定義3 簇間對象差異性可由類間距表示為

(8)

聚類結(jié)果的優(yōu)劣直接決定著適應(yīng)度函數(shù)值的高低，而平均類內(nèi)距和類間距直接反映了聚類結(jié)果的好壞，因此，適應(yīng)度函數(shù)定義為

(9)

平均類內(nèi)距越小，類間距越大，聚類效果越好，適應(yīng)度函數(shù)值越大。

2.3 遺傳操作設(shè)計

2.3.1 選擇操作

PGKMA算法采用錦標賽選擇法，設(shè)N，n分別為父代，子代種群個數(shù)，當(dāng)n≤0.8×N時，從父代種群中隨機選取m個個體，計算適應(yīng)度函數(shù)值，保留適應(yīng)度函數(shù)值最大的個體到子代；當(dāng)n>0.8×N時，隨機選取m個個體，計算適應(yīng)度函數(shù)值，保留適應(yīng)度函數(shù)值最小的個體到子代；從而增加了種群多樣性，防止算法收斂于局部最優(yōu)解；同時將精英個體直接復(fù)制到下一代中，保證了進化進程的正確性。

2.3.2 交叉操作設(shè)計

采用單中心交叉方式，即依概率Pc隨機產(chǎn)生一個交叉點(該交叉點位于每條染色體聚類中心的交界處)，交換兩條染色體交叉點后長度為d的部分，從而獲得兩條新的染色體。單中心交叉如圖3所示。

圖3 單中心交叉

2.3.3 變異操作設(shè)計

采用單中心k-means變異操作，即依概率Pm在聚類中心交界處隨機產(chǎn)生一個變異點，變異長度為d，將與之距離最近的數(shù)據(jù)點賦給該變異中心，并重新計算均值替換變異中心編碼值。

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

本文選取UCI標準數(shù)據(jù)庫中的Iris和Glass數(shù)據(jù)集作為實驗數(shù)據(jù)，分別從最佳聚類數(shù)K、最佳初始聚類中心C、類內(nèi)距ICS、類間距ICD、適應(yīng)度函數(shù)值F、迭代次數(shù)G和正確率，對傳統(tǒng)k-means算法、雙重遺傳k-means算法(DGKA)和本文PGKMA進行比較。在Windows 10操作系統(tǒng)下，硬件條件為Intel(R)Core(TM)i7-8550u CPU @ 1.80 GHz 1.99 GHz，8 GB內(nèi)存，使用Matlab編程實現(xiàn)。

PGKMA算法步驟如下：

input：數(shù)據(jù)集，算法參數(shù)

output：最佳聚類數(shù)Kopt，最佳初始聚類中心Copt，聚類結(jié)果

步驟1 根據(jù)聚類數(shù)K的取值范圍，為各K值初始化對應(yīng)的聚類中心種群；

步驟2 同時對各聚類中心種群進行k-means聚類操作，得到聚類結(jié)果；

步驟3 計算各K值下的適應(yīng)度函數(shù)值，并記錄適應(yīng)度函數(shù)最大值；

步驟4 比較各K值下的適應(yīng)值，并記錄最大值F1max及其對應(yīng)的聚類數(shù)K；

步驟5 若time1=5或gen1=100，轉(zhuǎn)步驟9，否則，轉(zhuǎn)步驟6；

步驟6 若Kopt=K，則time1=time1+1，F(xiàn)max=F1max，轉(zhuǎn)步驟8；否則轉(zhuǎn)步驟7；

步驟7Kopt=K，time1=1，F(xiàn)max=0，轉(zhuǎn)步驟8；

步驟8 通過遺傳操作更新各K值下的聚類中心種群，gen1=gen1+1，轉(zhuǎn)步驟2；

步驟9 獲取Kopt對應(yīng)的聚類中心種群；

步驟10 k-means聚類得到聚類結(jié)果；

步驟11 計算適應(yīng)值，并記錄最大值F2max，聚類中心Copt；

步驟12 若time2=10或gen2=150，則輸出結(jié)果，算法結(jié)束，否則轉(zhuǎn)步驟13；

步驟13 若F2max=Fmax，則time2=time2+1，轉(zhuǎn)步驟15，否則，轉(zhuǎn)步驟14；

步驟14Fmax=F2max，time2=1，轉(zhuǎn)步驟15；

步驟15 遺傳操作獲得新一代聚類中心種群，gen2=gen2+1，轉(zhuǎn)步驟10。

PGKMA算法采用混合結(jié)束策略，即當(dāng)Fmax連續(xù)10代保持不變，或者算法達到最大迭代次數(shù)時，輸出最佳聚類數(shù)，最佳初始聚類中心，聚類結(jié)果。

Iris是一個150*4的數(shù)據(jù)集，包含150個對象，每個對象包含4個屬性，最佳聚類數(shù)為3；Glass是一個214*9的數(shù)據(jù)集，包含214個對象，每個對象包含9個屬性，最優(yōu)聚類數(shù)為6。實驗參數(shù)設(shè)置見表1。

表1 實驗參數(shù)設(shè)置

表2和表3是兩類數(shù)據(jù)集在3個算法下的最佳聚類數(shù)K、最佳初始聚類中心C和迭代次數(shù)G的測試結(jié)果。從表中可以看出，傳統(tǒng)KM算法迭代次數(shù)最多，DGKM算法和PGKMA算法均有一定程度減少，且PGKMA算法迭代次數(shù)最少。

表2 Iris數(shù)據(jù)集測試結(jié)果

表3 Glass數(shù)據(jù)集測試結(jié)果

為了進一步比較算法的正確性和聚類結(jié)果的穩(wěn)定性，將每種算法運行30次，實驗結(jié)果見表4，表5。

表4 Iris數(shù)據(jù)集運行結(jié)果

表5 Glass數(shù)據(jù)集運行結(jié)果

通過表4、表5和圖4、圖5可以看出，傳統(tǒng)KM算法的類內(nèi)距離最大，類間距離最小，DGKM和PGKMA算法均有所改善，且PGKMA算法的類內(nèi)距離最小，類間距離最大。從適應(yīng)度函數(shù)值來看，適應(yīng)度函數(shù)值的大小與類間距離成正比，類內(nèi)距離成反比，且PGKMA算法的適應(yīng)度函數(shù)值最大。針對傳統(tǒng)KM算法在求解聚類時類間個體差異不明顯和DGKM算法聚類結(jié)果不穩(wěn)定的問題，PGKMA算法加強了類內(nèi)個體的緊湊度和不同類間個體的差異度，提高了聚類結(jié)果的穩(wěn)定性。

圖4 Iris數(shù)據(jù)集聚類結(jié)果分析

圖5 Glass數(shù)據(jù)集聚類結(jié)果分析

從圖6可知，傳統(tǒng)KM算法聚類結(jié)果受聚類數(shù)和初始聚類中心的影響最大，正確率最低。DGKM算法通過雙重算法對聚類數(shù)進行控制，改善了聚類結(jié)果的質(zhì)量，提高了聚類的準確率，但聚類質(zhì)量過于依賴聚類數(shù)目的確定。PGKMA算法解決了DGKM算法存在的問題，并進一步提高了聚類結(jié)果的準確率。

3 改進的遺傳k-means聚類算法的應(yīng)用

本文選取南通市農(nóng)業(yè)信息組2006年玉米數(shù)據(jù)集(Y組)作為樣本集，見表6，該樣本集包括51個子類對象和15個父類對象，每個對象包含全生育期、株高、穗粗、行粒數(shù)、千粒重、出籽率、小區(qū)產(chǎn)量等20多種屬性。

圖6 Glass和Iris數(shù)據(jù)集聚類正確率對比

3.1 玉米樣本集的最佳聚類數(shù)和初始聚類中心選取

采用并行遺傳k-means聚類算法進行離散化，然后運用基于遺傳算法的粗糙集屬性約簡算法對玉米數(shù)據(jù)子類進行橫向約簡，得到最小約簡集為{全生育期，穗高，穗粗，行粒數(shù)，千粒重，出籽率，小區(qū)產(chǎn)量}，約簡后的數(shù)據(jù)表見表7。

由表8和圖7可知，本文算法得到的聚類結(jié)果平均類內(nèi)距最小，類間距最大，有效性函數(shù)值最大，聚類結(jié)果最好。最佳聚類數(shù)為3，最佳初始聚類中心是5，31，37，聚類結(jié)果如下：

表6 玉米數(shù)據(jù)集

表7 屬性約簡后的玉米樣本集

第一類：Y1，Y3，Y30，Y50，Y51；

第二類：Y2，Y6，Y7，Y8，Y10，Y14，Y16，Y20，Y22，Y23，Y24，Y26，Y27，Y28，Y29，Y31，Y32，Y34，Y35，Y36，Y37，Y39，Y44，Y46，Y47，Y48，Y49；

第三類：Y4，Y5，Y9，Y11，Y12，Y13，Y15，Y17，Y18，Y19，Y21，Y25，Y33，Y38，Y40，Y41，Y42，Y43，Y45。

表8 不同算法下的各項指標的數(shù)值

圖7 聚類結(jié)果分析

表9是樣本與各類各屬性的平均值，從表中可以看出，第一類玉米品種的穗高、千粒重、小區(qū)產(chǎn)量都遠低于樣本平均值，所以第一類玉米屬于劣種玉米類，作為異常點刪除；第三類玉米品種各屬性均值接近樣本均值，沒有明顯的優(yōu)勢，屬于普通玉米類；第二類玉米品種的行粒數(shù)、千粒重、小區(qū)產(chǎn)量都很高樣本平均值，適用于育種。因此，本文選取第二類玉米子集作為良種集進行良種選育。

表9 樣本和各類的各屬性平均值

3.2 玉米種子綜合評價

對聚類后的玉米良種集，采用前文介紹的綜合排序方法進行排序，得到第二類良種玉米集的相對接近度為

C=

將C按大小進行排序，可得精英玉米品種為：Y47，Y49，Y48，Y29，Y20，Y22，這與南通市農(nóng)業(yè)信息組所給良種排名一致。

利用PGKMA算法對玉米樣本集進行聚類分析，將優(yōu)良的玉米品種聚為一類，通過屬性平均值分析，減少普通品種和劣種對選育工作的影響，降低了盲目育種的復(fù)雜度和工作量。采用DTOPSIS法對良種集進行綜合評價，將得分較高的6個玉米品種作為精英品種，確保得到最優(yōu)良的玉米品種。

4 結(jié)束語

通過兩個經(jīng)典實例對比分析可知，由于聚類數(shù)目的不確定性和初始聚類中心的隨機性，傳統(tǒng)的KM算法聚類結(jié)果不穩(wěn)定。DGKA算法雖然在算法結(jié)束時能獲得相對較優(yōu)的聚類數(shù)和初始聚類中心，但聚類結(jié)果過于依賴外層聚類數(shù)的確定。本文算法采用并行計算的方式同時獲得當(dāng)前代最佳聚類數(shù)和初始聚類中心，設(shè)計合適的編解碼方案，適應(yīng)度函數(shù)以及遺傳操作，提高了聚類結(jié)果的正確率和穩(wěn)定性。最后，將PGKMA算法應(yīng)用于玉米良種選育中，在獲取精英玉米品種的同時，降低了選育工作的復(fù)雜度和工作量。