武政平，荀亞玲

(太原科技大學 計算機科學與技術(shù)學院,太原 030024)

聚類分析[1]作為數(shù)據(jù)挖掘中應用較為廣泛的無監(jiān)督技術(shù)之一,被廣泛應用于文本挖掘[2]、模式識別[3]和Web搜索[4]等領(lǐng)域。隨著大數(shù)據(jù)涌現(xiàn),高維數(shù)據(jù)的聚類成為大家關(guān)注的重難點之一,傳統(tǒng)聚類分析方法都會受到“維災”影響,使聚類分析效果較差。子空間聚類作為一類聚類分析方法,選擇一些對聚類分析貢獻價值高的屬性所構(gòu)成的子空間,并對數(shù)據(jù)對象之間存在的相似性度量,有效地克服“維災”的影響[5],提高了聚類效果。

投影聚類作為一類子空間聚類,有效降低了冗余屬性或無關(guān)屬性對聚類分析的影響,但選擇簇所在的投影子空間時,未充分考慮各屬性維自身所具有的特征,從而降低了聚類分析效率。本文采用高斯混合模型定義下的相關(guān)子空間,充分體現(xiàn)了各屬性維自身所具有的特征,并提出了一種投影聚類分析算法。

1 相關(guān)工作

傳統(tǒng)的聚類方法,例如基于劃分，基于密度,基于模型等會受到“維災”影響,不再適用于高維數(shù)據(jù)集。投影聚類作為一類子空間聚類分析方法,通過將數(shù)據(jù)集投影到若干屬性維構(gòu)成有意義的低維子空間上,并根據(jù)數(shù)據(jù)間的相似性實現(xiàn)聚類分析[6],有效降低了“維災”影響,已成為高維數(shù)據(jù)聚類分析的研究熱點之一。

如何尋找簇所在的有意義子空間是投影聚類的難點,目前的典型研究工作為：CLIQUE[7]算法采用密度和網(wǎng)格的思想,可以自動發(fā)現(xiàn)聚類簇所在的子空間,但子空間剪枝會丟失部分密集區(qū)域。Aggarwal等人用SVD尋找簇所在的相關(guān)子空間,提出了ORCLUS算法,既可以發(fā)現(xiàn)軸平行的子空間聚類簇,也可以發(fā)現(xiàn)非軸平行的子空間聚類簇。但需要預先指定子空間的維數(shù),使聚類分析隨著空間維度的增加伸縮性變差。Procopiuc等人用超立方體方法,提出了DOC[8]算法,進一步提高了聚類簇的質(zhì)量,但設置全局的間隔寬度使其缺乏靈活性;聚類迭代過程需遍歷整個數(shù)據(jù)集,時間復雜度呈現(xiàn)指數(shù)增長。Yip等人通過自動調(diào)整最小相似和最小相似維參數(shù)來指導聚類族的合并和相關(guān)子空間的確定,提出了HARP[9]算法,優(yōu)點每個簇可以自動確定相關(guān)維,凝聚過程僅在確定的相關(guān)維中進行,有效提高了凝聚效率。此外,層次聚類固有的高時間復雜度也很難應用于大數(shù)據(jù)分析。此外,Mohamed等人用稀疏因子得到原始數(shù)據(jù)的稀疏度矩陣,結(jié)合伽瑪分布,找到該聚類的軸平行的線性相關(guān)子空間,提出了PCKA[10]算法,優(yōu)點是尋找相關(guān)子空間變得容易,但忽略了每個維度自身的特點以及無關(guān)屬性對聚類精度和效率的影響。

綜上所述,投影聚類是高維數(shù)據(jù)聚類分析有效途徑之一,有效地降低了“維災”影響，但在確定簇所在的相關(guān)子空間時,具有較高的時間復雜度;預先設定的參數(shù)值選擇不合適時,導致聚類精度無法保證,限制了投影聚類的適用性;選擇子空間時,未充分考慮各屬性維自身所具有的特征,從而降低了聚類效率。

2 相關(guān)子空間

隨著高維數(shù)據(jù)維度的增加,“維災”現(xiàn)象和數(shù)據(jù)自身的稀疏特性對聚類分析效果影響也越來越明顯。在高維數(shù)據(jù)中,數(shù)據(jù)對象只有在其有意義的屬性維集合中,才能體現(xiàn)出貢獻價值高的信息。在聚類分析中,將數(shù)據(jù)對象分布較集中或聚類簇中各數(shù)據(jù)對象的密度差異較小構(gòu)成的子空間,稱為相關(guān)子空間或稠密子空間,即相關(guān)子空間可以反映聚類簇所在屬性維上的有用信息,而數(shù)據(jù)集在此區(qū)域分布比較稀疏或數(shù)據(jù)對象的密度差異比較明顯構(gòu)成的子空間,稱之為不相關(guān)子空間或稀疏子空間,即不相關(guān)子空間未能充分反映與聚類簇的有用信息。

在文獻[10]中,采用稀疏度因子,尋找與聚類分析有關(guān)的屬性維子集構(gòu)成的相關(guān)子空間。設伽瑪分布的組件為q,數(shù)據(jù)集DS是由n條d維數(shù)據(jù)對象obj的組成的任意數(shù)據(jù)集,其中obji表示第i個數(shù)據(jù)對象,Aj表示第j個屬性維，Xij(i=1,2,…,n;j=1,2,…,d)表示第i個數(shù)據(jù)對象obji在第j個屬性維上的取值,yij是第i個數(shù)據(jù)對象obji在第j維屬性(Aj)的稀疏度因子,對每一維度稀疏度的頻率進行統(tǒng)計,并用伽瑪分布進行擬合。locq代表組件q的位置,loc代表每個維的所有l(wèi)ocq值在整個數(shù)據(jù)集中的集合,即loc={loc1,…,locq,…,locmtotal}.通過MDL選擇技術(shù)和EM算法來識別每個數(shù)據(jù)對象obj每個維度稀疏度因子y出現(xiàn)頻率所在的子空間來判斷。如果子空間是稠密子空間,Zij賦值為1;如果子空間是稀疏子空間,Zij賦值為0.稱向量Zi={Zi1,Zi2,Zij,…,Zid}是obji的子空間定義向量。向量Zi中,由Zij=1屬性維集構(gòu)成的子空間稱之為obji的相關(guān)子空間,由Zij=0屬性維集構(gòu)成的子空間稱之為obji的不相關(guān)子空間[11]。

在文獻[12]中,利用數(shù)據(jù)對象的KNN尋找其所在的相關(guān)子空間。由數(shù)據(jù)集DS中的各個數(shù)據(jù)對象及其局部數(shù)據(jù)集LDS,可以有效地確定各個數(shù)據(jù)對象所在相關(guān)子空間形成的簇。對于數(shù)據(jù)集中任意一個數(shù)據(jù)對象obji,LDS是由數(shù)據(jù)對象obj本身與其KNN得到的K個數(shù)據(jù)對象組成的局部數(shù)據(jù)集。因此，將計算數(shù)據(jù)對象各屬性值Xij相對于LDS的局部稀疏度因子計算公式定義如下：

(1)

(2)

其中:pj(xi)代表的是數(shù)據(jù)對象xi的局部數(shù)據(jù)集LDS在其j維屬性上取值構(gòu)成的集合,cij代表的是pj(xi)的平均值。

由公式(1)可知,yij代表的是局部數(shù)據(jù)集各屬性維的平均值偏離程度,yij較大時代表此屬性維的分布比較分散，表明xij在其局部數(shù)據(jù)集中密度較小,xij所在的子空間為稀疏子空間(不相關(guān)子空間);yij較小時代表此屬性維的分布比較集中,表明xij在其局部數(shù)據(jù)集中密度較大，xij所在的子空間為稠密子空間(相關(guān)子空間)。由此可見,稀疏度的引入可以更加方便地度量數(shù)據(jù)空間的稠密和稀疏區(qū)域,進而發(fā)現(xiàn)空間高維數(shù)據(jù)的相關(guān)子空間。

3 高斯混合模型與無關(guān)屬性剔除

3.1 高斯混合模型與相關(guān)子空間

在文獻[10]中,通過引入稀疏度因子來度量高維數(shù)據(jù)集中的相關(guān)子空間和不相關(guān)子空間，卻忽略了每一維度稀疏度因子自身的屬性特征;通過對每一維度稀疏度出現(xiàn)的頻率進行統(tǒng)計，而每一維度各稀疏度出現(xiàn)的頻率分布可以用伽瑪分布進行擬合,雖然也能較好地體現(xiàn)數(shù)據(jù)的分布,但是PCKA算法通過探測伽瑪組件來確定稠密區(qū)域時,是基于所有伽瑪組件在所有維度上的中位數(shù)是可比的。當數(shù)據(jù)集中包含的簇密度差異很大或者一部分簇分布在稀疏區(qū)域時，卻會丟失部分相關(guān)屬性維,導致所確定的相關(guān)子空間不夠準確，適用性降低。

由公式(1)可知,由數(shù)據(jù)集的各屬性值對應的局部稀疏因子,可生成整個數(shù)據(jù)集的稀疏因子矩陣。在稀疏因子矩陣中,每個維度的稀疏度yij由稀疏子空間和稠密子空間兩部分混合而成。高斯混合模型可以精確地量化事物,其靈活性可以很好地擬合各屬性維度稀疏度的分布，同時體現(xiàn)各維度中稠密區(qū)域所在的位置,且不需要在全維度上進行相似性度量,有效解決了當聚類簇間密度差異很大或者聚類簇分布在稀疏區(qū)域時造成相關(guān)屬性維的丟失問題,為聚類分析提供更多有價值的信息。僅需考慮各維度稀疏度自身特點,且適應于分布不同數(shù)據(jù)集。EM算法作為一種常用的迭代算法,具有良好的可操作性和收斂性,高斯混合模型的各個參數(shù)可以通過EM算法來得到。因此,采用高斯混合模型和EM算法可以有效地識別每個數(shù)據(jù)對象在各屬性維度上的稀疏程度,并確定所在的子空間是稀疏子空間還是稠密子空間,并將其識別得到的稠密子空間視為相關(guān)子空間。刻畫和描述數(shù)據(jù)對象維度的稀疏度因子的高斯混合模型定義如下:

(3)

(4)

采用高斯混合模型對數(shù)據(jù)對象的每一維度的稀疏度因子進行擬合時,由于稀疏度因子由兩部分組成,即稀疏部分和稠密部分。將稀疏度較小的數(shù)據(jù)構(gòu)成的稠密子空間定義為相關(guān)子空間，稀疏度較大的數(shù)據(jù)構(gòu)成的稀疏子空間定義為不相關(guān)子空間,因此將組件個數(shù)設為m=2.通過EM算法對參數(shù)進行估計就可以得到每一維度稀疏度因子屬于兩個高斯分布的概率值pi1和pi2.如果pi1>pi2,則該稀疏度屬于第一個高斯分布;如果pr1

將Zij定義為一個二元矩陣,Zij∈{0,1},Zij代表的是第i個數(shù)據(jù)對象第j維度所對應的值，如果yij屬于稠密子空間,則Zij=1;如果yij屬于稀疏子空間，則Zij=0.Zi定義為子空間向量，在Zi中,值為1的所組成的屬性維構(gòu)成的是第i個數(shù)據(jù)對象對應的相關(guān)子空間,值為0的所組成的屬性維構(gòu)成的是第i個數(shù)據(jù)對象對應的不相關(guān)子空間。由此得到了每個數(shù)據(jù)對象的子空間向量。顯然,利用公式(3)就可以得到數(shù)據(jù)集中各個數(shù)據(jù)對象的子空間向量。

3.2 無關(guān)屬性剔除

在投影聚類中,無關(guān)屬性主要包括:離群點、無關(guān)或冗余屬性維等。如果數(shù)據(jù)集中包含有離群數(shù)據(jù)、無關(guān)或冗余屬性維則會嚴重影響聚類效果。無關(guān)屬性則是不同于其它數(shù)據(jù)對象或?qū)傩跃S的集合,不屬于任何一個已識別的相關(guān)空間，而是屬于不相關(guān)子空間中,為有效剔除高維數(shù)據(jù)集中的無關(guān)屬性,可以充分利用二進制矩陣Z,因為二進制矩陣Z中包含了聚類分析所需要的有意義子空間和原數(shù)據(jù)集的位置有用信息。為了通過二進制矩陣的權(quán)重來識別那些相似的數(shù)據(jù)點，可以計算如下Jaccard相似系數(shù)來度量:

(5)

其中：a=|Z1j=Z2j=1|；b=|Z1j= 1&Z2j= 0|；c=|Z1j= 0&Z2j=1|;j∈{1,2,…,d}；JC的取值為0到1，當JC=0時代表兩數(shù)據(jù)對象不完全相似,JC=1時代表兩數(shù)據(jù)對象完全相似。如果兩數(shù)據(jù)對象的JC值超過了預先設定的λ=0.7，則兩數(shù)據(jù)對象相似需要保留。

4 PCCSGMM算法描述

綜上所述,采用KNN生成每個數(shù)據(jù)對象的局部數(shù)據(jù)集,利用公式(1),計算數(shù)據(jù)集中每個數(shù)據(jù)對象每個維度的稀疏度因子,得到全局的稀疏度矩陣;每一維度稀疏度因子的分布可以用高斯混合模型進行擬合,利用EM算法對高斯混合模型中的參數(shù)進行估算,得到每個數(shù)據(jù)對象的相關(guān)子空間；然后,對數(shù)據(jù)集的無關(guān)屬性進行剔除；最后,對處理后的數(shù)據(jù)集,采用K-means進行聚類。具體算法如下:

算法:PCCSGMM(Projection Clustering Analysis Algorithm Based on Gaussian Mixture Model and Correlated Subspaces) 算法

輸入:數(shù)據(jù)集DS,條數(shù)為N,屬性維度為d

輸出:聚類結(jié)果

2) for(i=0；i

3) SPi = getSpd()/*依據(jù)公式(1)計算數(shù)據(jù)集DS中數(shù)據(jù)對象的稀疏度矩陣*/}

4) Z = getAllCorrelatedSubspace()/*計算相關(guān)子空間*/

6) 對2個數(shù)據(jù)對象對應位置相減,得到多個位置的距離和矩陣,冒泡排序,得到每個數(shù)據(jù)對象的K近鄰;

7) 利用公式(1)計算得到每個數(shù)據(jù)對象的稀疏度,通過EM計算每個數(shù)據(jù)對象每個維度屬于k類別的概率;

8)在相關(guān)子空間中,將一個數(shù)據(jù)對象與剩余數(shù)據(jù)對象相應位置進行比較,每比較完一次,就將對應位置是1的個數(shù)進行求和,記錄在result中;

9)基于步驟8)利用公式(5)計算相似度,如果相似度大于0.7且該數(shù)據(jù)對象的K近鄰個數(shù)大于等于K則保留該數(shù)據(jù)對象,否則,剔除該數(shù)據(jù)對象;

10)基于步驟9)得到條數(shù)為n1數(shù)據(jù)集與矩陣,對每一維進行處理,如果某一屬性全是0或全是1則說明該屬性維對聚類影響不大,剔除該屬性維;

11)處理后得到條數(shù)為n1維數(shù)為d1數(shù)據(jù)集進行基于K-means迭代L次輸出k個簇，計算距離要考慮相關(guān)子空間中相關(guān)屬性對簇形成的貢獻。

12) ENDPCCSGMM

PCCSGMM算法在計算每個數(shù)據(jù)對象的K近鄰時,時間復雜度為O(N*logN),求稀疏矩陣的時間復雜度為O(N*d*k),識別不相關(guān)子空間和剔除無關(guān)屬性維度的時間復雜度為2O(N*d)+O(N^2*d)+O(n1*d)≈O(N*d)+O(N^2*d),最后聚類的時間復雜度為O(n1*d1*k*L).因此,PCCSGMM算法總的時間復雜度為O(N*logN)+O(N*d*k)+O(N*d)+O(N^2*d)+O(n1*d1*k*L).

5 實驗結(jié)果及分析

實驗環(huán)境：Intel(R) Core(TM) i3-4010U CPU,4.00GB內(nèi)存,Windows 7操作系統(tǒng),Eclipse作為開發(fā)平臺,采用java語言作為開發(fā)工具,實現(xiàn)了PCCSGMM算法。實驗數(shù)據(jù)為UCI標準數(shù)據(jù)集。

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

5.1 聚類精度

圖1給出了PCCSGMM、PCKA、DDC-K-means,在不同數(shù)據(jù)集上的標準互信息的變化趨勢實驗結(jié)果,表明PCCSGMM算法均比PCKA、DDC-K-means算法的標準互信息高,主要原因是PCCSGMM算法在構(gòu)建相關(guān)子空間時,采用高斯混合分布可有效地分區(qū)每個維的數(shù)據(jù)且考慮了每個屬性維自身的特點,得到的相關(guān)子空間準確率較高。圖2給出了PCCSGMM、PCKA、DDC-K-means算法,在不同數(shù)據(jù)集上的調(diào)整蘭德指數(shù)的變化趨勢實驗結(jié)果,表明PCCSGMM算法在Heart數(shù)據(jù)集上效果較差,原因是Heart數(shù)據(jù)量較小維度較大,利用KNN就會變差,基于距離的K-means也會變差,造成聚類結(jié)果與真實標簽的相似性降低,其它數(shù)據(jù)集上PCCSGMM均高于PCKA、DDC-K-means算法。

圖1 NMI標準互信息的比較

由圖1和圖2實驗結(jié)果可以看出,數(shù)據(jù)集的維度對PCCSGMM影響較小,主要原因是PCCSGMM利用了相關(guān)子空間中的屬性維，刪除了不相關(guān)子空間對聚類的影響。

圖2 ARI調(diào)整蘭德指數(shù)

圖3給出了PCCSGMM、PCKA、DDC-K-means算法在不同數(shù)據(jù)集上的調(diào)和平均(V-measure)變化趨勢實驗結(jié)果,并表明PCCSGMM算法在綜合考慮均一性和完整性方面優(yōu)于其他對比算法,其主要原因是PCCSGMM算法可以自適應地對每一維度的數(shù)據(jù)進行有效區(qū)分,且考慮了每個維度在數(shù)據(jù)空間中的重要性,并可以發(fā)現(xiàn)大部分隱藏數(shù)據(jù)所在的相關(guān)子空間。

圖3 UCI數(shù)據(jù)集對算法V-measure影響

5.2 聚類效率

圖4給出了PCCSGMM、PCKA、DDC-K-means,在不同數(shù)據(jù)集上運行時間。圖4(a)給出了中低維數(shù)據(jù)集Heart、Wine、Image、Seed上PCCSGMM及對比算法的效率變化趨勢實驗結(jié)果,實驗結(jié)果表明PCCSGMM的效率高于PCKA,原因是PCCSGMM在確定相關(guān)子空間時對每一維度的密度因子進行高斯擬合來確定相關(guān)子空間,而PCKA在對每一維的密度因子頻率進行擬合在確定稠密區(qū)域時基于全維可比得到,需要基于全屬性上各維度可比進行排序來確定相關(guān)子空間,使算法的效率降低。PCCSGMM聚類分析前進行了無關(guān)屬性剔除，使得K-means在計算距離的時間縮短,提高了聚類效率,而PCKA聚類前沒有進行無關(guān)屬性剔除，因此聚類效率略低于PCCSGMM.PCCSGMM效率比DDC-K-means低,原因是維度較低時，PCCSGMM計算KNN和剔除無關(guān)屬性時消耗了較多時間。

圖4(b)給出了PCCSGMM、PCKA、DDC-K-means算法在Wireless、Avila數(shù)據(jù)集上的效率變化趨勢實驗結(jié)果,該實驗結(jié)果表明PCCSGMM在Avila數(shù)據(jù)集上的效率比PCKA高。原因是聚類分析前對無關(guān)屬性進行剔除,K-means計算距離時消耗時間減少。但沒有DDC-K-means好,原因是剔除無關(guān)屬性消耗了較多時間。PCCSGMM在Wireless上效果較差,原因是Wireless數(shù)據(jù)集本身的無關(guān)屬性較少,PCCSGMM在剔除無關(guān)屬性時消耗時間較長。

圖4 UCI 數(shù)據(jù)集對算法效率的影響

6 結(jié)論與展望

文中針對高維數(shù)據(jù)出現(xiàn)的“維災”和無關(guān)屬性對聚類分析的影響，給出了一種基于相關(guān)子空間的聚類算法PCCSGMM,該算法充分了考慮了數(shù)據(jù)每一維自身的特點,有效減少了不相關(guān)子空間和無關(guān)屬性對聚類效率和精度的影響。采用部分UCI標準數(shù)據(jù)集進行驗證,證明了PCCSGMM算法的有效性和準確性。接下來將設計應用系統(tǒng)用于光譜數(shù)據(jù)聚類分析。