基于遺傳算法的混合類型數(shù)據(jù)聚類分析

摘要: 針對聚類分析算法在數(shù)據(jù)挖掘應(yīng)用中存在的問題，該文結(jié)合遺傳算法，對傳統(tǒng)K均值聚類算法進行了改進，提出了混合類型數(shù)據(jù)聚類新算法，擴展了聚類分析的應(yīng)用范圍。實驗結(jié)果表明，該算法具有較好的聚類性能。

關(guān)鍵詞:遺傳算法;層次化聚類;目標(biāo)函數(shù);優(yōu)化

中圖分類號:TP18文獻標(biāo)識碼:A文章編號:1009-3044(2009)32-8875-02

A GA-Based Mixed Type Data Clustering Analysis

DONG Jian-kang1， WU Qi-ming2

(1.Computer Science School， Gansu Political Science and Law Institute， Lanzhou 730070， China; 2.Department of Computer and Information Science， Hechi University， Yizhou 546300， China)

Abstract: To overcome the faultiness of the available clustering algorithm for the applications in data mining， a GA-based mixed type data clustering algorithm was proposed， which integrated genetic algorithm and improved the traditional K-means clustering algorithm. It extends the scope of the application of cluster analysis. The experiments show that the proposed algorithm works well.

Key words: genetic algorithms; clustering; objective function; optimization

聚類是根據(jù)數(shù)據(jù)的不同特征，將其劃分為不同的數(shù)據(jù)類。它的目的是使得屬于同一類別的個體之間的距離盡可能的小，而不同類別上的個體間的距離盡可能的大。數(shù)據(jù)的特征值多種多樣。二元變量只有兩個狀態(tài)，非此即彼;區(qū)間標(biāo)度變量是一個粗略線性標(biāo)度的連續(xù)變量，如溫度、高度、重量等;標(biāo)稱變量則由多個離散值組成，如地圖顏色可能有五個狀態(tài):紅色、黃色、綠色、粉紅色、藍色。作聚類分析時，可能用到一種變量，也可能是多種變量的組合。 傳統(tǒng)的聚類分析是一種硬劃分，它把每個待辨識的對象嚴(yán)格地劃分到某類中，具有非此即彼的性質(zhì)，因此這種類別劃分的界限是分明的。而實際上大多數(shù)對象并沒有嚴(yán)格的屬性，如何對混和屬性數(shù)據(jù)進行聚類分析是件極具挑戰(zhàn)性的工作，也是目前聚類分析研究的主流[1]。

聚類算法可分為以下幾類[2]:

1) 劃分方法:給定一個包含n個對象的數(shù)據(jù)集，將其劃分為k個子集，其中每個子集均代表一個聚類;

2) 層次方法:通過分解給定的數(shù)據(jù)集來創(chuàng)建一個層次，根據(jù)層次分解形成的方式采用自上而下或自下而上的方法進行聚類;

3) 基于密度方法:實際上就是不斷增長所獲得的聚類，直到“臨近”密度小于一定閾值為止;

4) 基于網(wǎng)格方法:將數(shù)據(jù)集劃分為有限數(shù)目的單元以形成網(wǎng)格結(jié)構(gòu)，所有聚類操作均在這一網(wǎng)格結(jié)構(gòu)上進行;

5) 基于模型的方法:為每個聚類假設(shè)一個模型，再去發(fā)現(xiàn)符合相應(yīng)模型的數(shù)據(jù)對象。文章主要分析劃分方法。

2 聚類分析的數(shù)學(xué)模型

假設(shè)X={x1，x2，…，xn}是待分析的對象全體，也可稱為論域或樣本集合。X中的每個對象(也可稱為樣本)(1≤i≤n)常用有限個參數(shù)值來刻畫，每個參數(shù)值用于刻畫xi的某個特征(屬性)。于是對象xi就對應(yīng)著一個向量P(xi)=(xi1，xi2，…，xim)， 其中xij()是xi在j個特征上的值，P(xi)稱為xi的特征向量或模式向量。聚類分析就是分析論域或樣本集合X中的n個樣本所對應(yīng)的模式矢量間的空間距離及分散情況，按照各樣本間的距離遠(yuǎn)近或相似程度把x1， x2，…， xn劃分成k個不相交的模式子集X1， X2， …， Xk，并要求滿足下列條件:

X1∪X2∪…∪Xk=X，Xi∩Xj=?準(zhǔn)(1≤i， j≤k，i≠j)

樣本xj(1≤j≤n)對子集xi(1≤i≤k)的隸屬度關(guān)系可用隸屬度函數(shù)表示為:

其中，隸屬度函數(shù)必須滿足條件Wij∈Mhk。也就是說:

1) 要求每一個樣本能且只能隸屬于某一類。

2) 要求每個子類都是非空的。

在這個表達式中是用于約束每一個樣本能且只能屬于某一類這一條件的;用于約束\"每個子類都是非空的\"。如果將以上定義的隸屬度函數(shù)wij擴展到[0，1]這個區(qū)間即為模糊聚類的定義。模糊聚類又稱為軟聚類，相應(yīng)的非模糊聚類也可稱為硬聚類。

3 混合類型數(shù)據(jù)聚類算法的目標(biāo)函數(shù)

令X={x1，x2，…，xn}，表示有n個樣本的數(shù)據(jù)集，其中xi=[xi1，xi2，…，xim]T表示第i個樣本的m個特征值。令K是一個正整數(shù)，那么對X進行聚類的目的就是要找到一個劃分，將X中的目標(biāo)分為K個類。

為了找到最好的一個劃分，要求選擇一個聚類難則來指導(dǎo)搜索劃分。下面我們要尋找一個目標(biāo)函數(shù)作為聚類準(zhǔn)則。當(dāng)前較為流行的目標(biāo)函數(shù)有[3]:

當(dāng)樣本同時具有數(shù)值和類屬混合特征時，樣本的特征矢量用xi=[xi1r，…，xilr，xi，l+1c，…，ximc]T表示，混合類型目標(biāo)xi和xj之間的相異勝測度可由下式計算:

公式右邊第一項為歐幾里德距離平方，用于計算數(shù)值型屬性的相似性。第二項為二值型屬性特征的相似性測度。其值為0和1。權(quán)值用來調(diào)節(jié)兩種特征在目標(biāo)函數(shù)中的比例，以避免偏向任何其中一個特征。

4 基于遺傳的混合類型數(shù)據(jù)聚類算法

利用遺傳算法可以進行全局的并行搜索，避免出現(xiàn)局部最優(yōu)以及提高搜索效率問題。

4.1 編碼和初始種群的生成

編碼即遺傳算法中樣本的表示。編碼方法有很多，如二進制編碼、實數(shù)編碼、符號編碼等等。針對本文的問題，對矩陣W進行編碼。

設(shè)n個樣本分屬于K類，則樣本空間可以表示為:

X=(x1x2…xn)

其中xi取整數(shù)值1-K中的一個，表示第i個樣本屬于第xi個類。

4.2 選擇算子的實現(xiàn)

遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行擇優(yōu)選擇操作:適應(yīng)度數(shù)值高的個體被遺傳到下一代群體中的概率較大;適應(yīng)度低的個體被遺傳到下一代群體中的概率較小。通過調(diào)節(jié)遺傳選擇概率數(shù)值來獲得較好的遺傳進度。本文采用類似錦標(biāo)賽選擇法，首先，隨機地從種群中挑選一定數(shù)目的個體，然后將最好的個體選擇作為父代個體。重復(fù)進行這個過程直到選到足夠的個體。錦標(biāo)賽選擇的參數(shù)為競爭規(guī)模Tour。適應(yīng)度函數(shù)如第3小節(jié)所示。

4.3 交叉運算

交叉運算是指在父代個體中選擇兩個染色體，然后對其中的部分基因按某種方式相互交換，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他自然計算算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。由于需要聚類的數(shù)目一般不會很大，染色體長度也不會很大，因此本文采用單點交叉。單點交叉又稱為簡單交叉，它是指在個體編碼串中隨機設(shè)置一個交叉點，然后在該點相互交換兩個配對個體的部分基因。本文采用的是單點交叉的形式。交叉點隨機選擇，但介于1-K之間。

如:父代為 1，5，8，9，2，3，7，6，4，10選擇交叉點為7則7與10-7進行交叉。得到的子代為:1，5，6，9，2，3，7，8，4，10。

4.4 變異運算

變異運算是用來模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變現(xiàn)象，它以很小的概率隨機地改變遺傳基因的值。

在染色體以二進制編碼的系統(tǒng)中，它隨機地將染色體的某一個基因由1變成0，或由0變成1。通過變異操作，可確保群體中遺傳基因類型的多樣性，以使搜索能在盡可能大的空間中進行，避免丟失在搜索中有用的遺傳信息而陷入局部解，獲得質(zhì)量較高的優(yōu)化解答。遺傳算法中的變異運算是產(chǎn)生新個體的輔助方法，它是必不可少的一個運算步驟。變異本身是一種局部隨機搜索，與選擇算子結(jié)合在一起，保證了遺傳算法的有效性，使遺傳算法具有局部的隨機搜索能力，同時使得遺傳算法保持種群的多樣性，以防止出現(xiàn)過早收斂。

5 結(jié)論

我們分別用傳統(tǒng)K均值聚類算法和基于遺傳的混合類型數(shù)據(jù)聚類算法進行了實驗，實驗結(jié)果驗證了最初的設(shè)想。基于遺傳的混合類型數(shù)據(jù)聚類算法的正確率均在95%以上，比傳統(tǒng)K均值聚類算法的正確率要高。說明基于遺傳的混合類型數(shù)據(jù)聚類算法確實能達到全局最優(yōu)。

參考文獻:

[1] 郝占剛，王正歐.基于遺傳算法和k-medoids算法的聚類新算法[J].現(xiàn)代圖書情報技術(shù)，2006(5):44-46.

[2] 史忠植.知識發(fā)現(xiàn)[M].北京:清華大學(xué)出版社，2002:137-139.

[3] 范明，孟小峰.數(shù)據(jù)挖掘概念與技術(shù)[M].北京:機械工業(yè)出版社，2001:223-230.