陳新泉

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

1 引言

從數(shù)據(jù)挖掘的角度看，聚類分析的目的是獲取數(shù)據(jù)集的空間分布結(jié)構(gòu)，進而描述那些有意義、有實際價值的數(shù)據(jù)集分布結(jié)構(gòu)?，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的其它點所構(gòu)成的集合。

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

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

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

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

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

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

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

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

3.2 雙重近鄰無向圖的簡易構(gòu)造算法

算法1 雙重近鄰無向圖的構(gòu)造算法

輸入 數(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òu)造出一個雙重近鄰無向圖G＝（S，E）。其中，E＝｛（u，v）｜u ∈NN（v），u，v ∈S｝。注意：根據(jù)雙重近鄰點集的定義，u ∈NN（v）成立，意味著v ∈NN（u）也成立。

算法說明：

3.3 雙重近鄰無向圖的改進構(gòu)造算法

在算法1 中，每一個數(shù)據(jù)點對Xi和Xj的相異度要計算兩次。算法1 的改進構(gòu)造算法（算法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＊的缺點。

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

②由算法1＊構(gòu)造出的｜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ù)設(shè)定的有序?qū)傩陨系南喈惗扔嬎闶絛isorder（·，·）、無序?qū)傩陨系南喈惗扔嬎闶絛issort（·，·）、有序?qū)傩陨系南喈惗乳撝礑Torder和無序?qū)傩陨系南喈惗乳撝礑Tsort，采用算法1或算法1＊構(gòu)造出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 （可選）采用一種基于合并的層次聚類方法，反復(fù)地對從步驟3獲得的初級聚類簇中的聚類進行滿足合并條件的聚類合并操作，直到不能再合并為止。

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

算法說明：

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

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

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

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

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

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

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

3.7 性能比較

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

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

4 仿真實驗

4.1 仿真實驗設(shè)計

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

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

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

參數(shù)DTorder的設(shè)定方法：通過多次實驗探測或根據(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è)置合適的參數(shù)DTorder后，算法A2、A3和A4對于四類人工數(shù)據(jù)集的聚類質(zhì)量要遠遠好于K-means算法和AP算法。這是因為這些數(shù)據(jù)集具有良好的聚類分布結(jié)構(gòu)，且沒有近鄰噪聲點干擾而導(dǎo)致相近的聚類區(qū)域被連通成一個聚類。

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

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

5 結(jié)束語

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

將雙重聚類方法與特征權(quán)重優(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é)構(gòu)的雙重聚類方法 [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.