面向混合屬性數(shù)據(jù)集的雙重聚類方法＊

陳新泉

（重慶三峽學院計算機科學與工程學院，重慶 404000）

1 引言

從數(shù)據(jù)挖掘的角度看，聚類分析的目的是獲取數(shù)據(jù)集的空間分布結(jié)構，進而描述那些有意義、有實際價值的數(shù)據(jù)集分布結(jié)構?，F(xiàn)今多數(shù)聚類算法只能處理數(shù)值型數(shù)據(jù)集，對類別屬性數(shù)據(jù)集和混合屬性數(shù)據(jù)集的研究不夠深入。由于實際中的聚類分析需求多數(shù)是面向混合屬性數(shù)據(jù)集，所以近年來針對類別屬性及混合屬性數(shù)據(jù)集的聚類分析得到一些研究人員的重視。如Huang Z X[1]將經(jīng)典的K-means算法[2]擴展到混合屬性數(shù)據(jù)集中，提出了K-prototype算法。Hsu C C等[3]提出了一種可處理混合屬性數(shù)據(jù)集的層次聚類算法。Bai L等[4]將探測最優(yōu)聚類數(shù)目和發(fā)現(xiàn)初始聚類中心這兩個過程結(jié)合起來，從而達到有效處理類別屬性數(shù)據(jù)集的目的。Liang等[5]為解決混合屬性數(shù)據(jù)聚類的一個重要難點，提出了一種基于信息理論的探測最優(yōu)聚類數(shù)目的方法。到目前為止，雖然已發(fā)表了不少面向混合屬性數(shù)據(jù)集的聚類分析研究成果，但沒有一種算法對所有類型的數(shù)據(jù)集都是有效的。

本文第2節(jié)先對問題作簡要的描述；第3節(jié)提出了一種面向混合屬性數(shù)據(jù)集的雙重聚類方法；第4節(jié)通過仿真實驗來比較分析本文所提聚類算法的聚類效果；第5節(jié)對本文作簡要的總結(jié)，并指出進一步的研究方向。

2 問題描述

其中，Xi＝（xi1，xi2，…，xim）和Xj＝（xj1，xj2，…，xjm）分別為第i個數(shù)據(jù)點和第j 個數(shù)據(jù)點在m 個屬性上的取值。易知，對任意的兩個數(shù)據(jù)點，都有disorder（·，·）∈[0，＋∞），dissort（·，·）∈[0，m2]。

3 混合屬性數(shù)據(jù)集的雙重聚類方法

定義1 混合數(shù)據(jù)集S＝｛X1，X2，…，Xn｝中點P 的雙重近鄰點集NN（P）定義為：

其中，disorder（X，P）為S 中的點X與點P 在有序?qū)傩陨系南喈惗?，dissort（X，P）為S 中的點X與點P 在無序?qū)傩陨系南喈惗?，DTorder為有序?qū)傩陨系南喈惗乳撝担珼Tsort為無序?qū)傩陨系南喈惗乳撝怠?/p>

定義1的實質(zhì)是，NN（P）是從S＝｛X1，X2，…，Xn｝中選取與點P 在有序?qū)傩陨系南喈惗炔怀^DTorder、在無序?qū)傩陨系南喈惗炔怀^DTsort的其它點所構成的集合。

3.1 雙重聚類方法的基本流程

混合屬性數(shù)據(jù)集的雙重聚類方法包括如下五個步驟：

（1）根據(jù)應用問題的領域知識，構造有序?qū)傩陨系南喈惗扔嬎闶胶蜔o序?qū)傩陨系南喈惗扔嬎闶?，設定有序?qū)傩陨系南喈惗乳撝岛蜔o序?qū)傩陨系南喈惗乳撝怠?/p>

（2）構造混合屬性數(shù)據(jù)集的雙重近鄰點集及雙重近鄰無向圖。

（3）采用一種搜索策略，構造雙重近鄰無向圖的初級聚類簇并建立其聚類結(jié)構描述。

（4）（可選）采用一種聚類合并算法，對初級聚類簇中的聚類進行滿足聚類合并條件的聚類合并操作，直到不能再合并為止。

（5）最終獲得的聚類簇即為該算法的輸出結(jié)果。

接下來對這個基本流程的具體步驟作進一步的說明，并在算法實現(xiàn)方面給出若干討論。

3.2 雙重近鄰無向圖的簡易構造算法

算法1 雙重近鄰無向圖的構造算法

輸入 數(shù)據(jù)集S＝｛X1，X2，…，Xn｝、有序?qū)傩陨系南喈惗扔嬎闶絛isorder（·，·）、無序?qū)傩陨系南喈惗扔嬎闶絛issort（·，·）、有序?qū)傩陨系南喈惗乳撝礑Torder、無序?qū)傩陨系南喈惗乳撝礑Tsort。

輸出 S＝｛X1，X2，…，Xn｝的雙重近鄰無向圖。

步驟1

步驟2 根據(jù)S 中每個點的雙重近鄰點集NN（Xi）（i＝1，2.…，n），構造出一個雙重近鄰無向圖G＝（S，E）。其中，E＝｛（u，v）｜u ∈NN（v），u，v ∈S｝。注意：根據(jù)雙重近鄰點集的定義，u ∈NN（v）成立，意味著v ∈NN（u）也成立。

算法說明：

3.3 雙重近鄰無向圖的改進構造算法

在算法1 中，每一個數(shù)據(jù)點對Xi和Xj的相異度要計算兩次。算法1 的改進構造算法（算法1＊）對每一個數(shù)據(jù)點對Xi和Xj的相異度只需計算一次，從而達到改進時空效率的目的。算法1＊的具體描述可參見文獻[6]，它的優(yōu)缺點簡述如下：

（1）算法1＊的優(yōu)點。

①在算法1＊中，存儲雙重近鄰點集NN（Xi）（i＝1，2.…，n）的鄰接表空間可減少一半；

②若邊（Xi，Xj）（i＜j）是雙重近鄰無向圖G＝（S，E）的一條邊，如果在后續(xù)的搜索過程中采用寬度優(yōu)先策略，算法1的搜索過程必然存在對邊（Xj，Xi）的搜索操作，而算法1＊在寬度優(yōu)先搜索過程中，入對、出對操作量可減少一半。

（2）算法1＊的缺點。

①構造出的雙重近鄰點集NN（Xi）（i＝1，2.…，n）不完全滿足定義1；

②由算法1＊構造出的｜NN（Xi）｜（i＝1，2.…，n）不一定等于點Xi的雙重近鄰點數(shù)目。

3.4 基于分離集合并的雙重近鄰圖聚類算法

算法2 基于分離集合并的雙重近鄰圖聚類算法

輸入 數(shù)據(jù)集S＝｛X1，X2，…，Xn｝，有序?qū)傩陨系南喈惗扔嬎闶絛isorder（·，·）、無序?qū)傩陨系南喈惗扔嬎闶絛issort（·，·）、有序?qū)傩陨系南喈惗乳撝礑Torder、無序?qū)傩陨系南喈惗乳撝礑Tsort。

輸出 S＝｛X1，X2，…，Xn｝的聚類簇描述。

步驟1 根據(jù)設定的有序?qū)傩陨系南喈惗扔嬎闶絛isorder（·，·）、無序?qū)傩陨系南喈惗扔嬎闶絛issort（·，·）、有序?qū)傩陨系南喈惗乳撝礑Torder和無序?qū)傩陨系南喈惗乳撝礑Tsort，采用算法1或算法1＊構造出S＝｛X1，X2，…，Xn｝的一個雙重近鄰無向圖G＝（S，E）。其中E＝｛（u，v）｜u∈NN（v），u，v ∈S｝。

步驟2 對S＝｛X1，X2，…，Xn｝中的每個點，執(zhí)行如下的三個步驟：

步驟2.1

步驟2.2

步驟2.3

步驟3 由數(shù)組ClusterIndex[1..n]很容易得到S 的初級聚類簇C0＝｛InitC1，InitC2，…｝。

三步驟4 （可選）采用一種基于合并的層次聚類方法，反復地對從步驟3獲得的初級聚類簇中的聚類進行滿足合并條件的聚類合并操作，直到不能再合并為止。

步驟5 從步驟3或步驟4 獲得的聚類簇即為本算法的輸出結(jié)果。

算法說明：

（3）在步驟2中，經(jīng)過步驟2.2的Union（）操作后，UFSTree[1..n]可能會成為一個具有兩層或兩層以上樹結(jié)構的聚類點歸屬指向數(shù)組，所以本算法必須在步驟2.3 中的for循環(huán)下加上一個while循環(huán)才能獲得“一個連通子圖的所有結(jié)點都指向一個父結(jié)點，所有連通子圖的連通信息都存儲在分離集數(shù)組結(jié)構中”的期望結(jié)果。仿真實驗程序也證明了在步驟2.3 中的for循環(huán)下，加與不加while循環(huán)，最終得到的ClusterIndex[1..n]值往往是不同的。

經(jīng)過這種基于分離集的合并操作后，可獲得雙重近鄰無向圖G 的若干連通子圖。其中，雙重近鄰無向圖G 的若干連通子圖的連通信息保存在UFSTree[1..n]中（該數(shù)據(jù)結(jié)構的詳細定義及三種基本操作的實現(xiàn)算法可參見實現(xiàn)本算法的源代碼），每個連通子圖對應數(shù)據(jù)集S 的一個初級聚類。

（4）在步驟3中，若事先給出了孤立點集的判定閾值，當雙重近鄰無向圖G 的某連通子圖的數(shù)據(jù)點數(shù)小于該判定閾值時，則可判定由該連通子圖所形成的初級聚類為孤立點集。

3.5 基于寬度優(yōu)先搜索的雙重近鄰圖聚類算法

基于寬度優(yōu)先搜索的雙重近鄰圖聚類算法（算法3）首先構造出數(shù)據(jù)集的一個雙重近鄰無向圖，接著采用修改后的寬度優(yōu)先搜索技術搜索出該雙重近鄰無向圖的所有連通子圖，從而獲得數(shù)據(jù)集的初級聚類結(jié)果。該算法的具體描述及討論可參見文獻[6]。

3.6 基于深度優(yōu)先搜索的雙重近鄰圖聚類算法

基于深度優(yōu)先搜索的雙重近鄰圖聚類算法（算法4）也是首先構造出數(shù)據(jù)集的一個雙重近鄰無向圖，接著采用修改后的深度優(yōu)先搜索技術搜索出該雙重近鄰無向圖的所有連通子圖，從而獲得數(shù)據(jù)集的初級聚類結(jié)果。該算法的具體描述及討論可參見文獻[6]。

3.7 性能比較

本文幾個算法的時間與空間復雜度比較如表1所示。

Table 1 Comparison of time and space complexity in several algorithms表1 幾個算法的時間與空間復雜度比較

4 仿真實驗

4.1 仿真實驗設計

在Intel Pentium（R）Dual-Core CPU T4500 2.30GHz、2GB內(nèi)存、Windows XP SP3下的Visual C＋＋6.0開發(fā)環(huán)境下采用C 語言來進行仿真實驗驗證。實驗數(shù)據(jù)集有人工數(shù)據(jù)集和UCI標準數(shù)據(jù)集兩大類。

（1）人工數(shù)據(jù)集。作者編程生成的不帶噪聲的具有五個或七個顯著聚類區(qū)域的二維實值數(shù)據(jù)集。該數(shù)據(jù)集有四類，具體描述如下：

DS1：400個數(shù)據(jù)點，五個聚類的人工無噪聲數(shù)據(jù)集；DS2：400個數(shù)據(jù)點，七個聚類的人工無噪聲數(shù)據(jù)集；DS3：10 000個數(shù)據(jù)點，五個聚類的人工無噪聲數(shù)據(jù)集；DS4：10 000個數(shù)據(jù)點，七個聚類的人工無噪聲數(shù)據(jù)集。

（2）UCI 標準數(shù)據(jù)集。選 用Iris、Glass、Waveform、Wine、Vertebral、German 和Credit[7]七個數(shù)據(jù)集。除Iris外，其余幾個UCI數(shù)據(jù)集的有序數(shù)值屬性部分都規(guī)整到區(qū)間[0，1]中。

人工數(shù)據(jù)集和UCI數(shù)據(jù)集作為算法的數(shù)據(jù)輸入，以圖形顯示的方式來驗證雙重近鄰無向圖的構造算法及其改進算法的正確性；以圖形顯示及聚類結(jié)果輸出的方式來驗證采用三個聚類算法（基于分離集合并的雙重近鄰圖聚類算法（標記為A2）、基于寬度優(yōu)先搜索的雙重近鄰圖聚類算法（標記為A3）和基于深度優(yōu)先搜索的雙重近鄰圖聚類算法（標記為A4））構造初級聚類簇的正確性，并以Kmeans算法[2]和AP 算法[9]作對比來分析它們的算法效率及聚類精度。

在本仿真實驗中，分離集數(shù)據(jù)結(jié)構定義及其三個基本操作是在文獻[10]的基礎上進行了一點修改而實現(xiàn)的。

用來衡量算法的性能及聚類效果的指標有：算法所花費的時間（采用ST 標記，單位為秒）、聚類數(shù)目（采用NC 標記）、預設的聚類數(shù)目（采用PNC標記）、所有數(shù)據(jù)點到其聚類平均點的平均距離（采用ADM 標記）和聚類純度（采用CP 標記）。

參數(shù)DTorder的設定方法：通過多次實驗探測或根據(jù)數(shù)據(jù)集（或其樣本）的最小生成樹來估計。

4.2 仿真實驗結(jié)果

表2列出了三個基于不同搜索策略的雙重近鄰圖聚類算法（A2、A3和A4）與兩個知名聚類算法（K-means算法和AP 算法）處理四類人工數(shù)據(jù)集的對比實驗結(jié)果。表3列出了三個雙重近鄰圖聚類算法（A2、A3和A4）與兩個知名聚類算法（Kmeans算法和AP算法）處理五個UCI有序?qū)傩詳?shù)據(jù)集的對比實驗結(jié)果。表4列出了三個雙重近鄰圖聚類算法（A2、A3和A4）與兩個知名聚類算法（K-means算法和AP算法）處理兩個UCI混合屬性數(shù)據(jù)集的對比實驗結(jié)果。

4.3 實驗結(jié)果分析及結(jié)論

從表2、表3和表4中可以看出，算法A2、A3和A4的聚類結(jié)果相同。無論是反映雙重近鄰無向圖的連通子圖的個數(shù)（即聚類數(shù)目），還是反映聚類緊密度的一個度量（如所有點到其聚類平均點的平均值）都是一樣的。算法A2、A3 和A4 僅在所花費的時間代價上有時會存在一點差別。這個實驗結(jié)果與三個算法的理論分析結(jié)果完全相吻合。

Table 2 Experimental results contrast of five clustering algorithms for four class artificial data sets表2 五個聚類算法處理四類人工數(shù)據(jù)集的對比實驗結(jié)果

Table 3 Experimental results contrast of five clustering algorithms for five UCI ordered-attributes data sets表3 五個聚類算法處理五個UCI有序?qū)傩詳?shù)據(jù)集的對比實驗結(jié)果

Table 4 Comparison experimental results of five clustering algorithms for two UCI mixed-attributes data sets表4 五個聚類算法處理二個UCI混合屬性數(shù)據(jù)集的對比實驗結(jié)果

從實驗結(jié)果圖示及表2可以看出，當設置合適的參數(shù)DTorder后，算法A2、A3和A4對于四類人工數(shù)據(jù)集的聚類質(zhì)量要遠遠好于K-means算法和AP算法。這是因為這些數(shù)據(jù)集具有良好的聚類分布結(jié)構，且沒有近鄰噪聲點干擾而導致相近的聚類區(qū)域被連通成一個聚類。

從表3和表4 可以看出，算法A2、A3 和A4并非對所有的UCI數(shù)據(jù)集都能取得比K-means算法和AP算法更好的聚類質(zhì)量。未能取得高聚類質(zhì)量的首要原因是算法A2、A3和A4在計算這些數(shù)據(jù)集的相異度時，設定這些UCI數(shù)據(jù)集（除Iris外，其余數(shù)據(jù)集都對有序?qū)傩圆糠诌M行了規(guī)整化）的屬性權重都為1，并未考慮有些屬性權重取值為1與該數(shù)據(jù)集的類別分布相差甚遠。另外一個原因是算法A2、A3和A4進行聚類分布探測的根基是通過發(fā)現(xiàn)近鄰連通子圖的方式來進行的，這類算法一般都難以探測出不具有明顯聚類分布結(jié)構的數(shù)據(jù)集。當存在較多近鄰噪聲時，甚至多個相近的“球型”聚類區(qū)域也會被連通起來。

事實上，算法A2、A3和A4更適合發(fā)現(xiàn)那些具有明顯聚類分布結(jié)構且無近鄰噪聲點的數(shù)據(jù)集。可以想見，在設定DTorder和DTsort后，如果存在一些近鄰噪聲點把所有的典型聚類分布區(qū)域連通起來，那么這三個算法就會判定它們是一個大聚類。這種算法的近鄰互連性可解釋為什么這三個算法在聚類有些UCI數(shù)據(jù)集時會取得更差的聚類質(zhì)量。

5 結(jié)束語

面對動態(tài)、海量的混合屬性數(shù)據(jù)集的數(shù)據(jù)預處理需求，本文提出了一種可以處理混合屬性數(shù)據(jù)集的雙重聚類方法。通過四類人工數(shù)據(jù)集和七個UCI標準數(shù)據(jù)集的仿真實驗，驗證了雙重聚類方法的三個具體實現(xiàn)算法盡管所采用的算法策略不同，但最終取得的結(jié)果是一致的。仿真實驗還表明，對于一些具有明顯聚類分布結(jié)構且無近鄰噪聲干擾的數(shù)據(jù)集，這種方法經(jīng)常能取得比K-means算法和AP算法更好的聚類精度，從而說明這種雙重聚類方法具有一定的有效性。

將雙重聚類方法與特征權重優(yōu)化方法結(jié)合起來作進一步的改進研究，并與其它更多經(jīng)典的聚類算法在算法速度及聚類質(zhì)量方面對更多的數(shù)據(jù)集做更多的比較是下一步的工作。

[1]Huang Z X.Extensions to the K-means algorithm for clustering large data sets with categorical values[J].Data Mining and Knowledge Discovery，1998，2.3）：283-304.

[2]Jain A K.Data clustering：50years beyond K-means[J].Pattern Recognition Letters，2010，31（8）：651-666.

[3]Hsu C C，Chen C L，Su Y W.Hierarchical clustering of mixed data based on distance hierarchy[J].Information Sciences，2007，177（20）：4474-4492.

[4]Bai L，Liang J Y，Dang C Y.An initialization method to simultaneously find initial cluster centers and the number of clusters for clustering categorical data[J].Knowledge-Based Systems，2011，2.（6）：785-795.

[5]Liang Ji-ye，Zhao Xing-wang，Li De-yu，et al.Determining the number of clusters using information entropy for mixed data[J].Pattern Recognition，2012，45（6）：2251-2265.

[6]Chen Xin-quan.Dual clustering method based on double-levels indexing structure facing to mixed-attributes data set[EB／OL].[2012-03-21].http：／／www.paper.edu.cn／index.php／default／releasepaper／content／201203-627.（in Chinese）

[7]Frank A，Asuncion A.UCI Machine Learning Repository[EB／OL].[2010-09-01].http：／／archive.ics.uci.edu／ml.

[8]Chen Xin-quan.Clustering algorithm research based on near neighbour point set[EB／OL].[2009-12-09].http：／／www.paper.edu.cn／index.php／default／releasepaper／content／200912-254.（in Chinese）

[9]Frey B J，Dueck D.Clustering by passing messages between data points[J].Science，2007，315（16）：972-976.

[10]Cormen T H，Leiserson C E，Rivest R L，et al.Introduction to algorithms[M].Third Edition.New York：The MIT Press，2009.

附中文參考文獻：

[6]陳新泉.面向混合屬性數(shù)據(jù)點集的基于雙層索引結(jié)構的雙重聚類方法 [EB／OL].[2012-03-21].http：／／www.paper.edu.cn／index.php／default／releasepaper／content／201203-627.

[8]陳新泉.基于近鄰點集的聚類算法研究[EB／OL].[2009-12-09].http：／／www.paper.edu.cn／index.php／default／releasepaper／content／200912-254.