崔志剛

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

0 引言

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

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)的模式進(jìn)行劃分，該算法終止于沒有一個模式可以在被重新指配給其它的聚類中心族。該算法由于初始的聚類中心選擇的隨機性，使得算法存在一個潛在的問題，及選擇的聚類中心是否合適。

2 混合遺傳聚類算法

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

2.1 編碼

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

2.2 初始

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

2.3 選擇

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

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

2.4 交叉

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

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

3 改進(jìn)的混合遺傳聚類算法

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

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

步驟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，則將之作為又一新的凝聚點，如此反復(fù)迭代直到?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ù)目和初始聚類中心，為后面的聚類過程打下了一個較好的基礎(chǔ)。

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

4 實例

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

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

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

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

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

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

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

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

5 結(jié)語

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

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

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

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

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