高維分類型數據加權子空間聚類算法

孫浩軍，閃光輝，高玉龍，袁 婷，吳云霞

汕頭大學 工學院，廣東 汕頭 515063

高維分類型數據加權子空間聚類算法

孫浩軍，閃光輝，高玉龍，袁 婷，吳云霞

汕頭大學 工學院，廣東 汕頭 515063

聚類就是將物理或抽象的數據集合分成相似的對象類的過程，每一個類都是一個彼此相似的對象的集合，每一個對象與屬于同一個類中的對象彼此相似，而與其他類中的對象相異[1]；聚類是理解數據庫中數據結構的一種重要手段，它在機器學習、模式識別、數據挖掘、信息檢索等方面都扮演著重要角色[2]，研究者們已經提出多種數據聚類算法[3-5]，然而在現實生活中，好多數據都擁有很高的維度，由于低維數據與高維數據在很多地方都表現出很大的不同，比如高維數據的稀疏型和“維度效應”[6]等，當用傳統的方法對高維數據聚類時，算法的有效性就大為降低，這也就成為目前聚類研究中的難題之一。

高維數據中往往有許多無關的屬性或者是相關性特別小的屬性，它們對聚類過程帶來的噪聲信息往往比帶來的有用信息還要多。在高維數據聚類中，尤其是在高維稀疏型數據集中，較密集的簇主要集中在一些低維子空間中，并且不同的簇往往與不同的子空間相關聯[7]，子空間聚類算法[8]的提出在一定程度上解決了這一問題。

根據加權方式的不同，子空間聚類可以分為軟子空間（soft subspace）和硬子空間（hard subspace）聚類兩種[9]。軟子空間又可稱為加權子空間，它給子空間的維度賦予[0，1]的權值，表示該維度與該簇的關聯程度；而硬子空間則是把子空間的維度同等看待，認為它們與該簇的關聯程度相同。現有的聚類算法著重于劃分的優化而忽略了子空間的優化或者是采用一個全局參數硬性的選取子空間，如 EWKM[9]的 γ、FKWM[10]的 β、δ等，這些在實際應用中都是很難確定的。

針對連續性數據，人們已經研究出K-means[4]、PAM[5]等經典算法。但是，用于連續性數據的聚類算法對于分類型數據數據卻顯得無能無力，因為對于連續性數據，基于距離的幾何性質可以作為一個標準[11]，但是分類數據的數據值是離散的，基于幾何性質的距離函數不再適用。對于分類型數據的相似度，現有的算法一般采用相異度作為分類型數據之間的距離度量，如：Dice/Jaccard系數和漢明距離等，但是使用它們有明顯的缺陷[12]，因為分類型數據屬性的值域十分狹小，即使低維的分類型數據也會經常出現“維度效應”問題，它們的相異度十分趨向于同一個值，在高維數據中更是如此。

針對這些問題，提出一種加權子空間聚類算法（Algorithm for Weighted Subspace Clustering，AWSC）。AWSC算法基于經典的蟻群聚類算法的聚類過程，采用層次聚類中凝聚聚類的思想進行聚類。在聚類過程中，采用基于子空間的特征向量加權計算兩個簇的相似度，減少了“維度效應”等因素的影響。

1 相關知識和理論基礎

1.1 信息熵

熵，最初作為一個熱力學概念，用來度量熱量的退化或進化。熵是系統無序程度的度量，熵越大，無序性越高，變化可能性越大，香農在信息論中引入熵的概念用來度量信息系統結構的不確定性。依據熵值計算權重[13]已有很多算法，本算法就是基于信息熵理論的基本原理來計算權重的。設有一個信源 X，其概率空間為xi，它們滿足：

其信息熵計算公式為：

從上式可以看出，當X中某一個變量出現概率較大時，則X的信息熵就較小，而當X中的變量出現越均勻，X的信息熵就越大。X的信息熵在一定程度上就代表了X中變量的易變程度或者說是緊湊程度，這樣信息熵就可以用在聚類過程中的子空間的搜索。

1.2 聚類的特征子空間

在高維數據聚類中，尤其是在高維稀疏型數據中，子空間的搜索是至關重要的。在搜索子空間時，子空間數據應盡可能地緊湊，噪聲空間的數據應盡可能地凌亂，然而，怎樣在兩者之間找到一個平衡是一個難題，現有的算法很多是以一個固定的全局參數以信息熵為標準對子空間進行選擇，這樣的算法在實際應用中會有很大的限制。針對這一問題，以信息熵為基礎，找到一個自適應函數 f(e)用于簇的特征子空間的搜索。

首先，應計算出簇的所有維的信息熵，然后，對信息熵按下式進行預處理，使std(i)∈[0，1]，以方便計算。

entropy(i)、min、max分別代表第i維的信息熵值、簇的最小信息熵值和最大信息熵值，std(i)表示第i維的預處理之后的信息熵，稱它為標準信息熵。

其次，按自適應函數 f(e)計算出該簇的特征子空間，所求出的子空間應使 f(e)取得最小值。該函數既考慮了子空間的數據的緊湊度，又考慮了噪聲空間的凌亂程度，以達到子空間搜索的合理化。

這里N、S分別是該簇的噪聲子空間和特征子空間；Variance(N)、Variance(S)分別為噪聲子空間和特征子空間的標準信息熵的方差，定義如下：

其中| M |為子空間M的維數，avgM為子空間M上維的標準信息熵的平均值。

由函數 f(e)求出的特征子空間能代表所屬簇的屬性特征。子空間的特征向量[14]就是在子空間所在的維上的特征值所組成的向量，在分類數據中維的特征值就是在簇中該維上出現次數最多的值，由特征子空間中維的特征值組成的特征向量就能代表所屬簇的特征。

1.3 子空間權值

在特征子空間中，雖然該子空間中維和簇的關聯程度相對來說已經很高，但是，不同的維與簇的關聯程度不可能完全相同，維的信息熵恰恰說明了這一點。但是進行子空間權重的分配時，如果僅僅依據信息熵進行權重的分配是不合理的，比如：兩個簇A、B在同一維上信息熵A的較大、B的較小，如果B中元素個數遠多于A，在聚類過程中B對聚類結果的影響應大于A，那么就應該賦予該維較大的權重，反之相反。因此，將子空間的權重設計為由兩個簇的子空間的信息熵及簇的大小確定。先分別求出兩個簇的子空間，然后在兩個子空間的并集上計算著兩個簇合并時子空間維的權重。比如：簇 A的子空間為（2，3，4，5），簇 B 的為（3，4，5，7），那么A、B 兩個簇的子空間的并集就是（2，3，4，5，7）。然后求出子空間的并集（2，3，4，5，7）每一維的權重，以計算 A、B兩簇的相似度。那么，第 j維的權重就可以表示為：

式中，X為兩簇的子空間的并集；|A|、|B|、| X|分別為A、B兩簇的大小和兩簇子空間并集的大小；std(a，j)、std(b，j)分別為 A、B子空間并集上第 j維的標準化熵值；其中，α是為了讓維的熵值為0的情況下使該式有意義而加入的一個松弛量，為了讓權值的計算盡可能地依據熵值和簇的大小，不讓α對權值的計算產生大的影響，令α為0.000 1；β、γ是兩個參數，它們決定簇的大小和信息熵值對權值的影響，較大的β意味著信息熵對權重的影響較小；較大的γ則意味著簇的大小對權重的影響就越大；反之均相反。采用類似熵權法[13]以熵求權的算法中的權值的計算方式，直接簡單地令 β、γ為1。這樣子空間權重的分配就顯得更加合理，因為一維權值的大小與合并前兩簇的子空間的維的信息熵的大小和簇的大小都直接相關；熵越小，權值應越大；簇越大，權值也應越大；所以把計算權重的公式定為以上形式，這樣求出的權值能更好地用于計算簇的相似度。

1.4 相似度

相似度描述的是兩個物體的相似程度，在聚類中，相似度在很大程度上可以說是兩個數據屬于同一個類的概率，分類數據相似度的度量不同于連續型數據的相似度的幾何度量方式，傳統的歐氏距離等基于幾何性質的距離方式對分類數據已經失效。

傳統的用于分類數據的相似度的度量方式如下：假設有同屬于一個數據集 X的兩個分類型數據，X1(x11，x12，…，x1q)、X2(x21，x22，…，x2q)，它 們 的 相 似 度 可 以 定義為：

這里q為數據集 X的維數，x1i、x2i為 X1、X2在第i維的值。

受CLUC[15]算法的影響，把上式加以擴展得到以下幾個相似度的計量方式：

一條分類型數據和一個分類型簇的相似度：

如果再把此式擴展一下就能得到兩個分類型數據簇的相似度。

假如現有兩個分類型數據的簇A、B，它們基于子空間并集的相似度定義為：

如果再對A、B的子空間的并集加權處理，那么它們基于子空間的加權相似度可定義為：

如果再對A、B取子空間的特征向量，那么它們基于子空間特征向量的加權相似度可定義為：

這里，|A|、|B |為簇A、B的元素個數，xaj、xbj分別為 A中第a、第b個數據元素在第 j維的值，q為簇 A特征子空間的維數，p為A、B兩簇子空間并集的維數，w(j)為A、B子空間的并集中第 j維的權重，vai表示簇 A特征向量中第i維的值。

這一系列相似度的計量方法（式（11）～（14）），其實也是信息熵的一個擴展。但是它們克服了信息熵的一個缺點，按信息熵進行矩陣的相似度計算時，如果兩個矩陣大小相差很大，就會出現意外情況，達不到理想的聚類效果。提出的簇的相似度的計算方式克服了這一缺點，該算法在計算矩陣的相似度時與矩陣的大小無關。

2 算法AWSC

本文的算法大致分為兩步：首先，數據的預處理，進行數據的初始化。然后，對初始化后的數據進行聚類。

2.1 數據的預處理

本算法數據的預處理是為了降低算法復雜性，減少對計算機硬件的要求，減少噪聲數據對聚類的影響。

初始化時，采用一個參數 init_rate（0～1），按式（9）、（11）將數據集做初始的劃分。采用凝聚的概念進行數據集的初始化。首先，遍歷原數據集，當取第一個元素時，把它當做一個初始簇，然后，遍歷其他元素時，通過式（9）或（11）計算它與已有簇的相似度，當它在所有簇中的相似度都小于閾值init_rate時，就把該元素存入一個新簇中，簇的個數增1，當有相似度大于閾值時，就把該元素存入相似度最大的簇中，直至遍歷結束。

2.2 聚類階段

在數據的預處理之后，初始簇的個數遠小于遠數據集中數據個數，接下來的階段就是對初始簇按最大相似度進行合并，直到達到預定類的個數。

2.2.1 子空間的確定及相似度的計算

首先，由式（4）找到初始簇的子空間，找出每個初始簇的特征子空間的特征向量。

然后，以特征子空間的特征向量為基礎計算初始簇之間的相似度。在計算時，首先由式（7）計算兩簇的子空間權重的分配，由兩個簇的子空間特征向量、簇的大小以及子空間權重經式（14）計算兩簇的相似度，從而得到由所有簇對的相似度組成的相似度矩陣。

2.2.2 初始簇的合并

根據相似度矩陣，找到擁具最大相似度的一對簇進行合并；如果相似矩陣有多對簇具有最大相似度則由式（13）找出具有較大值的兩個簇進行合并；合并之后，如果初始簇的個數等于預定類個數K，則算法結束；否則，重新計算簇的子空間及相似度矩陣，再進行合并，直到初始簇的個數達到預定類個數K。

2.3 算法偽代碼

偽代碼如下：

算法AWSC

輸入：數據集D；類的個數K；閾值init_rate

輸出：C 個子集的集合C{c1，c2，…，ck}

初始化：根據式（9）、（11）及參數 init_rate把數據初始化為clusters個簇

Repeat

（1）由式（4）計算每個簇的子空間及其特征向量；

（2）由式（4）、（7）計算子空間權重；

（3）由式（14）得到相似度矩陣；

（4）結合式（13）進行簇的合并；

Until clusters=K

3 實驗仿真及結果分析

實驗仿真采用的是UCI機器學習網站[16]上的數據集，并與其他算法[17-21]仿真結果進行分析比較；聚類結果的分析主要依靠聚類的正確率。

3.1 評價指標

聚類正確率的計算公式如下：其中，K為該數據集的真實的類的個數，Ci為第i個類聚類正確的數據個數，|D|為該數據集的元素個數。

3.2 數據實驗

在這里選用了Congressional Voting Records Data Set（Votes）、Zoo Data Set（Zoo）以及Soybean Data Set（Soybean）3個典型的真實分類型數據集。

3.2.1 數據描述

Votes是435×17的數據集，第一維為類標識，數據分為2類，一類是民主黨包含267個數據，另一類是共和黨包含168個數據。

Soybean是47×36的數據集，第一維為類標識，數據分為 D1、D2、D3、D44類，其中 D1、D2、D3、D4的數據量分別為10、10、10、17。

Zoo是101×17的數據集，第一維為類標識，數據集供分為 7類，類包含的數據量分別為41、20、5、13、4、8、10。三個數據集的信息如表1所示。其中Votes中有一些數據的屬性值缺失，本算法中對其以“？”作為標示。

表1 數據集基本信息

3.2.2 實驗結果及對比

其他幾個算法[13，18-21]在這幾個數據集上準確率如表2所示。其中，AWSC的結果是在init_rate=0.85的情況下產生的；CEVE、RDCE、RRCE算法的結果是取得10次計算中最好結果，“*”為相關算法中沒有此數據集的驗證，默認效果是不太理想，在圖1中為了圖形的完整性，以其他算法的平均值作為補充。

表2 各算法在數據集上的正確率

從以上各表可以看出，AWSC算法明顯優于其他算法，為了更直觀地對比各個算法的效果，將各個算法的實驗結果用直方圖的形式描述出來，如圖1所示。

由圖1可以看出，AWSC算法明顯優于其他算法，充分地體現了AWSC算法的有效性和優越性。這是因為本文算法設計的合理性。為更好地說明本算法的合理性，特對不同參數下的各數據集的正確率進行分析，具體結果如圖2。

圖1 各算法在不同數據集的準確率

圖2 Soybean、Zoo在不同參數下的準確率

Soybean、Zoo兩個數據集有一定的特殊性，所以選擇這兩個數據集作為分析對象。就像3.2.1節描述的那樣，這兩個數據集在數據的分布上有較大的差異，很具有代表性。Soybean數據集簇的大小分布比較均勻，而且經實驗發現，Soybean數據集中的四個簇緊湊性較好；而Zoo數據集的簇的大小的分布就很不均勻，較大的簇的大小達到41，較小的卻只有4，不僅如此，在這四個數據里，只有3個數據是比較緊湊的，而另一個數據離另外3個數據比較“遠”。

由圖2可以看出，Zoo在不同的參數下聚類效果有明顯的差異。對Zoo數據集，因為數據簇的大小分布不均勻，所以看到init_rate較小的時候，聚類效果并不好，這是因為在這種情況下，就會把更多的數據在數據的初始化時凝聚到一塊，這樣較大簇的異常數據和較小簇的數據就有可能聚到一塊，導致聚類效果的降低；而當init_rate取較大值時，這時只有相似性較大的數據初始化時聚到一塊，這時就能取得較好的聚類效果。所有的這些在Soybean數據集的聚類效果圖中可以明顯地感受到，從圖2可以看出，Soybean在圖中列出的參數情況下大部分都能取得很好的聚類效果，就像最初分析的那樣，Soybean數據集簇的大小分布比較均勻、簇內緊湊度較好的緣故。其實，它們在其他參數下也能取得較好的聚類效果，圖中沒有一一列出。

AWSC算法的性能來源于它的自適應性以及權重分配的合理性。每合并兩個簇后，AWSC算法都重新搜索新合并成簇的子空間，這樣就能更準確地搜索出每個簇的子空間；權重分配時考慮簇的大小對權重分配的影響，從而獲得較好的聚類效果。

4 結論及展望

提出了一種加權子空間聚類算法。它利用信息熵和方差去搜索子空間，找到了一個自適應的約束方程，充分地考慮了子空間和噪聲空間的影響，使子空間的搜索更加合理；在分配子空間權重時，考慮子空間信息熵和簇的大小的影響，由此推導出了新的子空間維的權重計算方式。與其他算法相比，AWSC算法權重的分配更加合理，子空間的搜索也更加合理，大幅提高了聚類精度和聚類結果的穩定性。下一步的工作重點是減少參數的個數，進一步提高聚類算法的適應性。

[1]Han Jiawei，Kamber M.數據挖掘概念與技術[M].范明，孟曉峰，譯.北京：機械工業出版社，2008：16-17，30-31，251-252.

[2]Iam-On N，Boongoen T，Garrett S，et al.A link-based cluster ensemble approach for categorical data clustering[J]. IEEE Knowledge and Data Engineering，2012，24（3）：413-425.

[3]Berkhin P.Survey of clustering data mining techniques[M]// Grouping multidimensional data：recent advances in clustering.Berlin：Springer-Verlag，2006：25-71.

[4]Macqueen J.Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability.Berkeley：University of California Press，1967：281-297.

[5]Kaufman L，Rousseeuw P J.Finding groups in data：an introduction to cluster analysis[M].Hoboken：John Wiley& Sons Inc，1990：68-72.

[6]Parsons L，Haque E，Liu H.Subspace clustering for high dimensionaldata：areview[J].ACM SIGKDD Explorations Newsletter，2004，6（1）：90-105.

[7]Zaki M J，Peters M，Assent I，et al.CLICKS：an effective algorithm for mining subspace clusters in categorical datasets[C]//Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining，2005：736-742.

[8]Tan S，Cheng X，Ghanem M，et al.A novel refinement approach for text categorization[C]//Proceedings of the ACM 14th Conference on Information and Knowledge Management，2005：469-476.

[9]Jing L，Ng M K，Huang J Z.An entropy weighting k-means algorithm forsubspace clustering ofhigh-dimensional sparese data[J].IEEE Trans on Knowledge and Data Engineering，2007，19（8）：1026-1041.

[10]Huang J Z，Ng M K，Rong H，et al.Automated variable weighting in k-means type clustering[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2005，27（5）：657-668.

[11]Karypis G，Han E H，Kumar V.Chameleon：hierarchial clustering dynamic modeling[J].IEEE Journals&Magazines，1999，32（8）：68-75.

[12]孫浩軍，杜育林，姜大志.基于信息熵的高維分類型數據子空間聚類算法[J].山東大學學報：自然科學版，2011，45（5）：37-45.

[13]陳孝新，熵權法在股票市場的應用[J].商業研究，2004（16）：139-144.

[14]Zhang P，Wang X，Song P X.Clustering categorical data based on distance vectors[J].The J Am Statistical Assoc，2006，101（473）：355-367.

[15]Nemalhabib A，Shiri N.CLUC：a natural clustering algorithm for categorical[J].ACM，2006：23-27.

[16]UCI data base[EB/OL].[2012-12-19].http：//archive.ics.uci. edu/ml/datasets.html.

[17]He Zengyou，Xu Xiaofei，Deng Shengchun.A cluster ensemblemethod forclustering categoricaldata[J].Information Fusion，2005，6（2）：143-151.

[18]李桃迎，陳燕，張金松，等.一種面向分類屬性數據的聚類融合算法研究[J].計算機應用研究，2011，28（5）：1671-1673.

[19]馬海峰，劉宇熹.基于相關隨機子空間的分類數據聚類集成[J].計算機應用研究，2012.

[20]San O M，Huynh V，Nakamori Y.An alternative extension of the k-means algorithm for clustering categorical data[J].International Journal of Applied Mathematics and Computer Science，2004，14（2）：241-247.

[21]Gan G，Wu J.Subspace cluatering for high dimensional categorical data[J].ACM SIGKDD Explorations Newsletter，2004，6（2）：87-94.

SUN Haojun,SHAN Guanghui,GAO Yulong,YUAN Ting,WU Yunxia

College of Engineering,Shantou University,Shantou,Guangdong 515063,China

Subspace clustering is a kind of effective strategy to high-dimensional data clustering,the principle of subspace clustering is as well as possible keeping original data information,meanwhile as small as possible using subspace to data clustering.Based on the studying of the existing soft subspace clustering,it proposes a new algorithm for subspace searching.The algorithm combines with the size of cluster and information entropy,defines a new subspace dimensional weight distribution mode,and then uses the feature vector of cluster subspace to measure the similarity of two clusters.It uses the idea of agglomerative hierarchical clustering in hierarchical clustering to data clustering,which overcoming the shortcomings of using information entropy or traditional similarity separately.Through the test in the Zoo,Votes,Soybean three typical categorical data set to find out that compared with other algorithms,the proposed algorithm not only can improve the accuracy of clustering,but also has the very high stability.

high-dimensional data;clustering;subspace;information entropy;hierarchical clustering

子空間聚類是高維數據聚類的一種有效手段，子空間聚類的原理就是在最大限度地保留原始數據信息的同時用盡可能小的子空間對數據聚類。在研究了現有的子空間聚類的基礎上，引入了一種新的子空間的搜索方式，它結合簇類大小和信息熵計算子空間維的權重，進一步用子空間的特征向量計算簇類的相似度。該算法采用類似層次聚類中凝聚層次聚類的思想進行聚類，克服了單用信息熵或傳統相似度的缺點。通過在Zoo、Votes、Soybean三個典型分類型數據集上進行測試發現：與其他算法相比，該算法不僅提高了聚類精度，而且具有很高的穩定性。

高維數據；聚類；子空間；信息熵；層次聚類

A

TP301

10.3778/j.issn.1002-8331.1301-0121

SUN Haojun,SHAN Guanghui,GAO Yulong,et al.Algorithm for high-dimensional categorical data weighted subspace clustering.Computer Engineering and Applications,2014,50（23）：131-135.

國家自然科學基金（No.61170130）。

孫浩軍（1963—），男，教授，研究領域為模式識別、數據挖掘等；閃光輝（1986—），男，碩士研究生，研究領域為數據挖掘技術與應用；高玉龍（1988—），男，碩士研究生，研究領域為數據挖掘技術與應用；袁婷（1988—），女，碩士研究生，研究領域為數據挖掘技術與應用；吳云霞（1988—），女，碩士研究生，研究領域為數據挖掘技術與應用。

E-mail：haojunsun@stu.edu.cn

2013-01-14

2013-03-29

1002-8331（2014）23-0131-05

CNKI網絡優先出版：2013-07-15,http://www.cnki.net/kcms/detail/11.2127.TP.20130715.0936.002.html