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

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

高維分類型數(shù)據(jù)加權(quán)子空間聚類算法

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

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

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

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

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

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

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

1 相關知識和理論基礎

1.1 信息熵

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

其信息熵計算公式為：

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

1.2 聚類的特征子空間

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

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

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

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

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

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

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

1.3 子空間權(quán)值

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

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

1.4 相似度

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

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

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

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

一條分類型數(shù)據(jù)和一個分類型簇的相似度：

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

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

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

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

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

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

2 算法AWSC

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

2.1 數(shù)據(jù)的預處理

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

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

2.2 聚類階段

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

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

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

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

2.2.2 初始簇的合并

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

2.3 算法偽代碼

偽代碼如下：

算法AWSC

輸入：數(shù)據(jù)集D；類的個數(shù)K；閾值init_rate

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

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

Repeat

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

（2）由式（4）、（7）計算子空間權(quán)重；

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

（4）結(jié)合式（13）進行簇的合并；

Until clusters=K

3 實驗仿真及結(jié)果分析

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

3.1 評價指標

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

3.2 數(shù)據(jù)實驗

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

3.2.1 數(shù)據(jù)描述

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

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

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

表1 數(shù)據(jù)集基本信息

3.2.2 實驗結(jié)果及對比

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

表2 各算法在數(shù)據(jù)集上的正確率

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

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

圖1 各算法在不同數(shù)據(jù)集的準確率

圖2 Soybean、Zoo在不同參數(shù)下的準確率

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

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

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

4 結(jié)論及展望

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

[1]Han Jiawei，Kamber M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟曉峰，譯.北京：機械工業(yè)出版社，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]孫浩軍，杜育林，姜大志.基于信息熵的高維分類型數(shù)據(jù)子空間聚類算法[J].山東大學學報：自然科學版，2011，45（5）：37-45.

[13]陳孝新，熵權(quán)法在股票市場的應用[J].商業(yè)研究，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]李桃迎，陳燕，張金松，等.一種面向分類屬性數(shù)據(jù)的聚類融合算法研究[J].計算機應用研究，2011，28（5）：1671-1673.

[19]馬海峰，劉宇熹.基于相關隨機子空間的分類數(shù)據(jù)聚類集成[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

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

高維數(shù)據(jù)；聚類；子空間；信息熵；層次聚類

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—），男，教授，研究領域為模式識別、數(shù)據(jù)挖掘等；閃光輝（1986—），男，碩士研究生，研究領域為數(shù)據(jù)挖掘技術(shù)與應用；高玉龍（1988—），男，碩士研究生，研究領域為數(shù)據(jù)挖掘技術(shù)與應用；袁婷（1988—），女，碩士研究生，研究領域為數(shù)據(jù)挖掘技術(shù)與應用；吳云霞（1988—），女，碩士研究生，研究領域為數(shù)據(jù)挖掘技術(shù)與應用。

E-mail：haojunsun@stu.edu.cn

2013-01-14

2013-03-29

1002-8331（2014）23-0131-05

CNKI網(wǎng)絡優(yōu)先出版：2013-07-15,http://www.cnki.net/kcms/detail/11.2127.TP.20130715.0936.002.html