一種改進的混合屬性數據聚類算法

摘要:K-prototypes算法是處理混合屬性數據的主要聚類算法，但是存在對初值敏感、參數依賴和易受“噪聲”干擾等問題。為了克服以上缺點，該文對K-prototypes算法的初始中心點選擇進行了研究與分析，提出了一種基于近鄰法的初始中心點選擇策略對算法進行改進，算法先利用近鄰法獲得初始中心點集和k值，然后進行K-prototypes運算，最后加入識別異常數據點的規則。改進后的算法成功解決了傳統K-prototypes算法的缺陷，而且具有更好的分類精度和穩定性。經實驗證明，改進算法是正確和有效的，明顯優于傳統的K-prototypes算法。

關鍵詞:聚類分析;初始中心點;K-原型算法;聚類算法;混合屬性數據

中圖分類號:TP301文獻標識碼:A 文章編號:1009-3044(2010)11-2713-04

A K-prototypes Algorithm Based on Improved Initial Center Points

CHEN Dan， WANG Zhen-hua

(Faculty of Computer， Guangdong University of Technology， Guangzhou 510006， China)

Abstract: The K-prototypes is the main clustering algorithm that capable of handling mixed numeric and categorical data. However， K-prototypes sensitive to its initial center points， is parameter-dependent and susceptible to noise interference. In order to overcome them， a method is proposed to build initial center points heuristically through the neighbors of objects， and then calculate according the K-prototypes algorithm's procedures. At last， use a rule to optimize the clustering results which able to identify the abnormal points. The proposed algorithm successfully resolved the defects of the traditional algorithm， improves the accuracy of clustering results and stability of the algorithm. Experiments show the proposed algorithm leads to better accurate and scalable， superior to the traditional K-prototypes.

Key words: Clustering analysis; Initial center points; K-prototypes; Clustering algorithm; mixed numeric and categorical data

聚類是數據挖掘中的一種數據分析技術，具有重要意義和很強的挑戰性。其基本原理是將數據劃分成有意義的簇，相同簇的對象之間具有較高的相似性，而不同簇的對象之間則相似程度較低。這種數據分析技術廣泛應用于模式識別、數據分析、圖像處理和商業研究等方面。目前已劃分出多種聚類算法，常見的聚類算法有基于劃分的K-均值，基于密度的DBSCAN算法，基于層次的BRICH算法等。基于劃分的聚類算法K-means簡單快速，對處理大數據集，但它是基于歐氏距離的劃分，難以滿足混合屬性集聚類的要求。文獻[1-2]對K-means算法進行擴展，先后出現了K-modes算法和K-prototypes算法。K-prototypes算法能夠有效地處理混合屬性數據集聚類的問題，但它的缺點也很明顯:1) 對于不同的初始值，可能會導致不同的聚類結果;2) 需要用戶給定初始參數，這些參數的選擇需要用戶具備大量的先驗知識才能確定，而用戶通常對數據集缺乏先驗知識導致所選參數對聚類結果產生很大的影響;3) 算法非常容易受“噪聲”干擾，導致聚類精度下降。

近鄰法是由Cover和Hart于1968年提出的，是非參數法中最重要的方法之一。它的原理是以全部訓練樣本作為代表點，計算測試樣本與所有樣本的距離，并以最近鄰樣本的類別作為決策，具有原理直觀，方法簡單等優點。因此，本文提出了一種基于近鄰法的初始中心點選擇策略對算法進行改進，利用近鄰法，啟發式地獲得初始中心點和k值。最后用一個基于最小距離的規則來識別異常數據點，防止“噪聲”的干擾。

改進后的算法能有效地解決傳統K-prototypes算法的缺點，基本特征有三點:1) 在選擇初始中心點的時候，采用近鄰法，有依據的選擇初始中心，避免了傳統K-prototypes算法對初值選擇的盲目性;2)它可以自動的獲取k個聚類，解決了K-prototypes算法k值必須預先給定的問題;3)為了避免算法中的“噪聲”干擾，采用了一個基于最大距離的啟發式規則，將離聚類中心最遠的數據點識別為“異常數據點”;經過實驗證明，其聚類后的精度和穩定性要優于原算法。

1 K-prototypes算法

K-prototypes算法是由Huang提出的可以對分類屬性和數值屬性相混合的數據進行聚類的一種有效算法[2]。其基本思想和K-均值算法類似，只是在K-prototypes算法中定義了一個對數值與分類兩種屬性都計算的相似性度量，以此作為聚類的目標函數，通過不斷更新聚類原型來達到優化目標函數，獲得最優聚類效果的目的。

算法描述如下:假定待聚類對象集合為X={X1，X2， …，Xn}，由n個觀測對象組成，屬于混合型數據集，且每個觀測對象Xi={Xi1，Xi2， …，Xin}有 個屬性，由A1A2， …Am來表示，其中A1A2， …Ap為數字屬性，Ap+1A p+2，…Am為可分類屬性，屬性Aj取值域用Dom(Aj)表示，且xij∈Dom(Aj)。對于可分類屬性有Dom(Aj)={aj(1)，aj(2)， …，aj(nj)}，其中nj指屬性Aj取值的數目。聚類中心用Z表示，相應的，簡單記作Za=(za1，za2， …，zam)。

K-prototypes算法的距離函數d由數值型和可分類型兩部分組成[3-4]:

d(Xi，Za)=dr(Xi，Za)+rdc(Xi，Za)(1)

其中:γ∈[0，1]，為分類屬性的權重參數;

dr(Xi，Za)=(xij-zaj)2，由歐式距離度量;

rdc(Xi，Za)= γδ(xij，zaj)，

當xij≠zaj時，δ(xij，zaj)=1;

當xij=zaj時，δ(xij，zaj)=0.

K-prototypes算法最小化目標函數[4]:

F(W，Z)=wiad(Xi，Za)(2)

滿足:

wia∈[0，1];1≤i≤n;1≤a≤k

wia=1;1≤i≤n

0≤waai≤n;1≤a≤k

綜上所述，K-prototypes聚類算法具體步驟如下:

1) 初始化初始聚類數k和聚類中心Z，即從數據集中隨機選取k個初始聚類原型;

2) 按照2)式定義的目標函數最小化原則，將數據集中的各個對象劃分到離它最近的聚類原型所代表的類中;

3) 對于每個聚類， 重新計算新的聚類原型;

4) 計算每個數據對象對于新的數據原型的差異度，如果離一個數據對象最近的聚類原型不是當前數據對象所屬聚類原型，則重新分配這兩個聚類的對象;

5) 重復Step 3和Step 4，直到各個聚類中不再有數據對象發生變化。

2對K-prototypes算法的改進

針對上面列出的K-prototypes的不足，該文提出一種基于近鄰的初始點選擇算法，該算法思想來源于近鄰方法[6]，可確定初始的中心點集和 值。并在原型算法中加入適當的啟發式規則，使算法能夠有效地辨識異常數據點，綜合這三點改進，算法獲得更好的穩定和聚類結果。算法流程圖如圖1。

2.1 基于近鄰方法的初始中心點選擇策略

基于近鄰方法的初始聚類中心選擇策略基本思想為:以全部樣本數據作為代表點，計算測試數據點與所有樣本之間的距離，如果小于初始閾值，就把該點劃分為與測試數據點相同的類，記數變量增1，同時更新最短距離。最后選擇鄰居數目最多的數據對象作為初始中心點。

樣本點 的鄰居定義為P=Neigbour(x， θ):

{

判斷P是否為x的鄰居;

IfDist(P，x)≤θ返回1;

Else 返回0;

}

其中 為兩個數據對象的相似度量函數。

算法描述如下:

1) 定義一個初始閥值θ和中心點集Z，Z初始值為空;

2) 從數據集中隨機選一個點Q作為起始點;從Q開始遞歸地按照深度優先方式遍歷各點，P=Neigbour(Q， θ) ;如果返回值為1，則判斷P屬于以Q為中心的聚類，更新閥值θ，并使初始值為0的局部變量m=m+1(用于記錄Q的鄰居數目);否則退回到前一點繼續搜索。遍歷數據集中的每一個數據點;

3) 選擇鄰居數目最多的數據對象作為第一個初始中心點，加入到Z中，初始值為0的全局變量k=k+1;

4) 將原數據集刪除中心點及其鄰居，如果還有未被聚簇的點，即在這些數據點集中重復執行(2)-(4);

5) 輸出初始聚類中心Z和k。

2.2 對異常數據點的識別

聚類算法是將數據集中相似的數據歸為一類，因此理論上，一個簇中的所有數據點都應該離簇中心點比較近。然而可能存在一些異常點，它們不屬于任何聚簇。為了有效識別這些異常點，在K-prototypes中加入以下啟發式規則，在算法進行全局搜索的時候，引導算法避免異常數據點的干擾。

加入的算法啟發式規則描述如下:

Min{d(Xi，Za)} ≤ε; 1≤i≤n; 1≤a≤k(3)

其中ε為距離閥值。

算法在最后利用這個啟發式規則來檢驗聚類結果是否滿足這個條件，不滿足則標記為異常點;如果所有的異常點數目小于閥值ψ，則算法結束;否則，則將所有的異常點歸為一類，令k=k+1; 重新迭代，直到所有的異常點數目小于ψ。

2.3 改進后K-prototypes算法步驟

綜上所述，改進后的算法描述如下:

輸入:待處理數據集S，參數 θ，ε，ψ，γ

輸出:k個聚簇

步驟:

Step 1:使用數據預處理技術處理不完整、有噪聲的數據集，為后續聚類做準備。

Step 2:使用基于近鄰的初始中心點選擇方法獲得初始中心點集Za=(za1，za2，…，zam)和聚類數k;

Step 3: 按照(2)式的目標函數最小化原則，將數據集中的各個對象劃分到離它最近的聚類原型所代表的類中;

Step 4:對于每個聚類，重新計算新的聚類原型Za’;計算每個數據對象 對于新的數據原型Za’的差異度d(x，Za’)，如果離一個數據對象最近的聚類原型不是當前數據對象所屬聚類原型，則重新分配這兩個聚類的對象;

Step 5:重復Step 3和step 4，如果各個聚類無數據對象發生變化，轉至Step6;

Step 6:利用啟發式規則(3)來檢驗聚類結果，標記異常數據點，如果異常數據點數小于ψ，算法結束;否則將這些異常數據點歸為一類，并使k=k+1，轉至Step3，反復迭代，直至使異常數據點控制在較小范圍內，算法結束。

3 實驗結果與分析

為了驗證所改進后的K-prototypes算法的有效性和可行性， 實驗過程分別采用隨機選擇初始點的K-prototypes算法和改進后的K-prototypes算法對給定數據集進行測試，并比較分析聚類結果。

系統配置為:Intel 酷睿2 雙核 CPU，1G內存，Windows XP，應用Matlab6.5平臺進行實驗仿真。

3.1 實驗1:人造數據實驗

為了顯示的直觀性，我們構造的數據樣本共有300個樣本，可以劃分為3類，分別為A類、B類和C類。每個樣本具有2個特征:一個數值型和一個分類型。使用隨機選取十組初始聚類中心所得到的最壞與最好結果與優化選取初始聚類中心的算法所得到的結果進行比較。如圖2所示。

實驗1參數設置:θ=0.20，ε=4.5，ψ=50;γ取0.5。

從圖4可以直觀地看出，傳統K-prototypes算法對于不同的初始聚類中心會得到差別很大的聚類結果;這說明初始聚類中心的選擇對算法的分類性能有很大的影響;圖5是采用改進后的K-prototypes算法，相比之下，改進后的K-prototypes算法具有更好的分類效果。

3.2 實驗2:標準數據庫數據實驗

實驗2采用UCI機器學習庫[7]中的真實數據集Voting和Cleve作為聚類對象，其中Voting為分類型數據集，而Cleve為混合類型的數據集，分別用原始K-prototypes算法和改進后的K-prototypes算法對其進行聚類分析，數據集描述如表1所示。

上述數據集Voting、Cleve都包含多個屬性，不能直觀地顯示其聚類結果，故從正確識別率和穩定性兩個方面進行分析。

3.2.1 評價標準

為了將原始數據的分類特征與算法得到的聚類結果作比較，本文采用聚類結果正確率作為聚類實驗結果的評價標準。

評價聚類效果的指標如下:

E=(n/N) ×100%

其中:n為正確分類的對象數，N為總對象數。E∈[0，1]，為正確識別率，其值越大，表明聚類結果越精確;反之，聚類結果誤差越大。

4.2.2 聚類性能分析

實驗過程中，兩個算法的參數設置分別如下:在改進后的K-prototypes算法中，對于Voting，Cleve兩個數據集，分別設置閾值θ=0.15，ε=4.5，ψ=70;θ=0.20，ε=4.8，ψ=50，…，每組閾值分別運行5次;γ分別取1，0.7。

將傳統算法運行10次，通過打亂數據集的各個數據位置，反復仿真得出以下聚類結果。

表2是對兩組實驗數據的聚類精度值的對表，從表2可以直觀地看出:采用改進后K-prototypes算法進行聚類，得到的聚類精度都在90%以上，比原始K-prototypes算法聚類精度高很多。而采用原始K-prototypes算法聚類得到的結果有時高，有時低，波動比較大，說明原始K-prototypes算法對初始值很敏感，對于不同輸入順序的初始值而得到不同的聚類精度;相比，采用改進后的K-prototypes算法，每組實驗的聚類結果波動很小，聚類精度高。由此可證明，改進后的K-prototypes算法成功地解決了原始算法對初始值非常敏感，參數必須預先設定和對易受“噪聲” 影響等缺點。因此，實驗結果表明:本文提出的基于近鄰法的K-prototypes算法在分類精度和穩定性兩個方面都是十分有效的。

4 結論

該文提出了一種改進的K-prototypes混合屬性數據聚類算法，通過近鄰法獲取初始中心點集和初始聚類數目，避免了初始中心點選擇的盲目性和對聚類數目k值的依賴性;同時加入啟發式規則，防止了“噪聲點”的干擾。通過實驗可以看出該算法成功解決了原K-prototypes算法對初始敏感的缺點，并且自動獲取初始中心點集和初始聚類。通過對聚類結果的精度分析和穩定性分析，可看出改進后的算法優于傳統的K-prototypes聚類算法。

參考文獻:

[1] Ralambondrainy H. A Conceptual Version of the k-means Algorithm[J].Pattern recognition Letters，1995(16):1147-1157.

[2] Huang Zhexue. Extension to the k-means algorithm for clustering large data sets with categorical values[J]. Data Mining and Knowledge Discovery，1998(2):283-304.

[3] 陳寧， 陳安等. 數值型和分類型混合數據的模糊K-prototypes聚類算法[J].軟件學報，2001，12(8):1107-1119.

[4] 尹波，何松華.基于PSO的模糊K-prototypes聚類[J].計算機工程與設計，2008(11):2283-2285.

[5] 吳孟書，吳喜之.一種改進的K-prototypes聚類算法[J].統計與決策，2008(5).

[6] Dasarathy B V. Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques[M].Los Alamitos， CA: IEEE Computer Society Press，1991.

[7] Blake C，Keogn E，Merz C.UCI repository of machine learning database，1998[EB/OL].http://www.ics.uci.edu/~mlearn/ML-Respository. html.