一種改進的混合遺傳聚類算法的數(shù)據(jù)挖掘技術(shù)

崔志剛

武漢大學軟件工程國家重點實驗室 湖北 430063

0 引言

數(shù)據(jù)挖掘(Data Mining)就是從大量數(shù)據(jù)中獲取有效的、新穎的、潛在有用的、最終可理解的模式的非平凡過程。在龐大的數(shù)據(jù)集合中存在相似性很強的數(shù)據(jù)集，如果能將數(shù)據(jù)集進行分類，依據(jù)相似性建立一個種群，使得數(shù)據(jù)挖掘更有目的性和針對性。K-means聚類算法是一種快速有效的分類方法，具有較快的分類速度，但必須手動確定初始聚類中心，因此，若能夠利用算法求得初始聚類中心，則結(jié)合K一均值聚類算法可以實現(xiàn)自動分類。遺傳算法(Genetic A1gorithm—GA)是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，它是一種啟發(fā)式的全局優(yōu)化搜索算法，其簡單通用，魯棒性強，適于并行處理，應用范圍廣。遺傳聚類是將GA應用于聚類的一種方法，其基本思想是通過遺傳學習，將上一代的優(yōu)良特性保留下來，并通過個體之間的基因組合、變異從而產(chǎn)生更為優(yōu)良的下一代個體，這樣經(jīng)過數(shù)代的個體進化，最終找到滿意的個體。鑒此，本文采用K-means算法進行聚類，并采用遺傳聚類算法確定聚類中心，實例結(jié)果驗證了改進的算法有效可行。

1 K-means聚類算法

在聚類算法中需要考慮到底聚類算法到什么時候終止，即是如何確定聚類中心，確定多少聚類中心。K-means聚類將數(shù)據(jù)劃分為n個模式，每個模式的維度為d，取其中的最小K組作為我們的聚類起點，定義如下：

令{xi,i=1,2,…,n}為模式n的集合。其中xij表示xi的第j個特征。定義i=1，2，…，n；k=1，2，…，K，

那么，數(shù)組W=[wij]就有屬性如下

令第k個聚類中心族為ck=(ck1，ck2，…，ckd)，那么

第k個族群的內(nèi)聯(lián)相關(guān)族群定義為

總的內(nèi)聯(lián)相關(guān)族群定義為

由此就可以找到W*=[w*ik]中的最小S(W)，例如

K-means算法是一個迭代算法，它開始于一個任意的族群，在每一次迭代的過程中確定那些模式屬于同一聚類中心族模式，下一次的迭代就是取與該中心族相關(guān)的模式進行劃分，該算法終止于沒有一個模式可以在被重新指配給其它的聚類中心族。該算法由于初始的聚類中心選擇的隨機性，使得算法存在一個潛在的問題，及選擇的聚類中心是否合適。

2 混合遺傳聚類算法

遺傳算法的主要問題是針對不同數(shù)據(jù)集的編碼。通常采取自由選擇的方法，在進化過程中生成：下一代的編碼依據(jù)當前這一代的編碼而不同。下面就關(guān)于編碼及初始化及遺傳運算做進一步的闡述。

2.1 編碼

遺傳算法的染色體編碼有很多種，本文中采用較常用的是基于聚類中心的浮點數(shù)編碼和基于聚類劃分的整數(shù)編碼。由于內(nèi)聯(lián)相關(guān)族群S(W)通常具有多維性、數(shù)量大等特點，聚類問題的樣本數(shù)目一般遠大于其聚類數(shù)目，因此確定染色體的長度 n在{1，2，…，K}中取值，將各個類別的中心編碼為染色體。例如對于一個類別為 4 的聚類問題，假設數(shù)據(jù)集為2維。初始的4個聚類中心點為(1，3)，(2，4)，(6，9)，(8，7)，則染色體編碼為(1, 3，2, 4，6, 9, 8, 7)。這種基于聚類中心的編碼方式縮短了染色體的長度，提高了遺傳算法的速度，對于求解大量數(shù)據(jù)的復雜聚類問題效果較好。

2.2 初始

第一代的初始聚類中心 P(0)是在集合{1，2，…，K}中隨機選擇的。基于此種選擇算法可以在運行到選擇某些族群為空概率為非零的匹配族群的時候停止，由于隨機選擇初始聚類族群以及其他族群可以圍繞此聚類中心進行計算，使得p達到一個較為理想的賦值。

2.3 選擇

根據(jù)適者生存原則選擇下一代的個體。在選擇時，以適應度為選擇原則。適應度準則體現(xiàn)了適者生存，不適應者淘汰的自然法則。

其中 F(Si)表示串 Si的合適的取值并且確定下一次變異的取值。本文采用輪盤賭的原則隨機的選擇。顯然，從式(6)可知：①適應度較高的個體，繁殖下一代的數(shù)目較多。②適應度較小的個體，繁殖下一代的數(shù)目較少；甚至被淘汰。這樣，就產(chǎn)生了對環(huán)境適應能力較強的后代。對于問題求解角度來講，就是選擇出和最優(yōu)解較接近的中間解。

2.4 交叉

交叉從相互關(guān)聯(lián)的數(shù)據(jù)源中，根據(jù)不同的聚類中心的距離，按照某種關(guān)系交叉其中的基因從而形成新的個體。為了從依存對象 xi中找到適應的等位基因 sw(i)，令 dj=d(xi,cj)為xi與cj的歐氏距離，所以等位基因可以依據(jù)下面的公式選擇

其中cm≥1并且dmax=maxj{dj}。

3 改進的混合遺傳聚類算法

新群體的編碼值為中心在變異后產(chǎn)生，將每個數(shù)據(jù)點分配到最近的類，形成新的聚類劃分。按照新的聚類劃分，計算新第二代的聚類中心，取代原來的編碼值。 因為K -means算法具有較強的局部搜索能力，因此引入K-means操作后，可以大大提高遺傳算法的收斂速度。

混合遺傳聚類算法主要是改進了初始模板的選定方法。以每個向量為圓心，以向量空間中所有句子之間距離的平均值為半徑作圓，然后根據(jù)每個圓內(nèi)的數(shù)據(jù)點的密度來排序確定初始聚類中心和初始聚類數(shù)。 這樣，K-means聚類算法需要的初始模板就由以上算法動態(tài)生成，而無需用戶進行事先指定。整個過程包括以下幾個基本步驟：

步驟1：選取兩個正數(shù)，一般R2 =2R1 ，其中R1為距離矩陣W(i,j)中所有元素之間距離的平均值。

步驟2：以每個句子為圓心，以R1為半徑作圓，計算落在每個圓內(nèi)的數(shù)據(jù)元素數(shù)目，即樣本密度。

步驟 3：將樣本密度按從大到小的順序排列，取密度最大者作為第一個凝聚點Z1 ，在密度次大的單元中任選一點k，若與第一凝聚點之間距離大于R2，即 |Z1 -k|> R2，則把k 作為第二個凝聚點Z2 ，否則繼續(xù)判定下一密度最大者，若下一密度最大者中的任一點與前面若干個凝聚點之間距離均大于R2，則將之作為又一新的凝聚點，如此反復迭代直到?jīng)]有新的凝聚點生成。

步驟 4：這些凝聚點作為聚類模板的初值即分類個數(shù) k以及初始k個聚類中心Z1，Z2, Z3,.......，Z k。

步驟5：把得到的k和k個聚類中心Z1，Z2，Z3，.......，Zk 作為k - means 算法的初始模板，繼續(xù)用k-means算法迭代，最后得到k個聚類。

經(jīng)過以上步驟的初始分類，可以得到整個向量空間的分類個數(shù) k 以及模板初始聚類中心 Z={ Z1，Z2，Z3，.......，Zk }，這樣我們就從整個向量空間的統(tǒng)計信息中自動確定了聚類所需要的初始聚類數(shù)目和初始聚類中心，為后面的聚類過程打下了一個較好的基礎。

在確定k和聚類中心Z后，接下來對數(shù)據(jù)元素向量空間進行k-means 迭代。其基本原理是根據(jù)所有向量與聚類中心距離的遠近程度，形成k個互不相交的聚類，較為相似的句子都聚在同一類中。因此自動聚出來的這些自然的類可以被看成描述不同側(cè)面的理想信息，用于區(qū)分及表達不同的類。

4 實例

本文選擇從網(wǎng)絡下載的語料，選用其中的 1000篇，利用手工進行分類，分類結(jié)果如表1。

表1 網(wǎng)絡預料手工分類結(jié)果

衡量信息檢索性能的召回率和精度也是衡量分類算法效果的常用指標。但是聚類過程中的分類類別與手工分類類別不存在確定的一一對應關(guān)系，因此直接以精度和召回率作為評價標準是不可取的。為此本文選擇了平均準確率作為評價的標準。平均準確率是通過考察任意兩篇文章之間類屬關(guān)系是否一致從而來評價聚類的效果。實驗中分別采用傳統(tǒng)的K-means算法與改進算法，比較如表2。

表2 K-means算法與混合遺傳聚類算法比較

實驗結(jié)果表明改進與傳統(tǒng)的K-means算法在運行速度上有一定的提高，平均準確率普遍要好，特別是在正確的指定聚類中心數(shù)K時，平均準確率提高了約9%，由此可以看到改進算法具有一定的優(yōu)勢。由于使用的文本集文本數(shù)量較小，未來還會繼續(xù)在更大規(guī)模的文本集上測試改進算法。

另外，分別用本文所描述的改進方法和傳統(tǒng)K-means聚類算法進行聚類確定文檔集合的子主題數(shù)，并人工確定每個主題文檔集合中包括的子主題數(shù)。其中，在采用傳統(tǒng)K-means聚類方法時，初始聚類數(shù)目和初始聚類中心是需要人為給定的(取句子總數(shù)的 10%)。本文分別將改進算法以及傳統(tǒng)K-means算法得到的子主題數(shù)列出如3表所示。

表3 K-means算法與改進算法子主題數(shù)確定的比較

從上表中可以看出，改進的混合遺傳聚類算法得到的子主題數(shù)比較接近，這表明通過文中的方法在發(fā)現(xiàn)文檔集合中的潛在子主題時比較符合文檔的客觀情況，而通過人為主觀經(jīng)驗得到的子主題數(shù)相對較大。綜上所述，通過改進的混合遺傳聚類算法自適應發(fā)現(xiàn)的子主題數(shù)比較能客觀的反映文檔集合的情況，具有一定的效果。

5 結(jié)語

本文對數(shù)據(jù)挖掘中聚類算法做了詳細的分析，對于不同的聚類方法中所出現(xiàn)的人工確定聚類中心點問題做了改進。本文詳細分析了K-means聚類算法，在此基礎上對于聚類中心點選擇遺傳算法通過交叉變異自適應的方式選取，構(gòu)造向量間的距離矩陣，計算中心點。通過實驗分析，發(fā)現(xiàn)改進的聚類算法有一定的效果。

[1] 申銳.數(shù)據(jù)挖掘技術(shù)中聚類算法的探索與研究[J].山西科技.2009.

[2] 張翠萍,楊善超.基于K-均值聚類算法的中藥葉片顯微圖像分割[J].石河子大學學報(自然科學版).2009.

[3] 范明譯.JiaweiHan Micheline Kamber.Data Mining:Concepts and Techniques[M].北京:機械工業(yè)出版社.2001.

[4] 唐西西.一種新的混合遺傳聚類算法[J].廣西工學院學報.2006.