基于高斯混合模型的相關(guān)子空間投影聚類分析

武政平，荀亞玲

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

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

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

1 相關(guān)工作

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

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

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

2 相關(guān)子空間

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

在文獻(xiàn)[10]中,采用稀疏度因子,尋找與聚類分析有關(guān)的屬性維子集構(gòu)成的相關(guān)子空間。設(shè)伽瑪分布的組件為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)的稀疏度因子,對每一維度稀疏度的頻率進(jìn)行統(tǒng)計,并用伽瑪分布進(jìn)行擬合。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]。

在文獻(xiàn)[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ū)域,進(jìn)而發(fā)現(xiàn)空間高維數(shù)據(jù)的相關(guān)子空間。

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

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

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

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

(3)

(4)

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

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

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

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

(5)

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

4 PCCSGMM算法描述

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

算法: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ù)對象對應(yīng)位置相減,得到多個位置的距離和矩陣,冒泡排序,得到每個數(shù)據(jù)對象的K近鄰;

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

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

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

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

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

12) ENDPCCSGMM

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

5 實(shí)驗(yàn)結(jié)果及分析

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

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

5.1 聚類精度

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

圖1 NMI標(biāo)準(zhǔn)互信息的比較

由圖1和圖2實(shí)驗(yàn)結(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)變化趨勢實(shí)驗(yàn)結(jié)果,并表明PCCSGMM算法在綜合考慮均一性和完整性方面優(yōu)于其他對比算法,其主要原因是PCCSGMM算法可以自適應(yīng)地對每一維度的數(shù)據(jù)進(jìn)行有效區(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ù)集上運(yùn)行時間。圖4(a)給出了中低維數(shù)據(jù)集Heart、Wine、Image、Seed上PCCSGMM及對比算法的效率變化趨勢實(shí)驗(yàn)結(jié)果,實(shí)驗(yàn)結(jié)果表明PCCSGMM的效率高于PCKA,原因是PCCSGMM在確定相關(guān)子空間時對每一維度的密度因子進(jìn)行高斯擬合來確定相關(guān)子空間,而PCKA在對每一維的密度因子頻率進(jìn)行擬合在確定稠密區(qū)域時基于全維可比得到,需要基于全屬性上各維度可比進(jìn)行排序來確定相關(guān)子空間,使算法的效率降低。PCCSGMM聚類分析前進(jìn)行了無關(guān)屬性剔除，使得K-means在計算距離的時間縮短,提高了聚類效率,而PCKA聚類前沒有進(jìn)行無關(guān)屬性剔除，因此聚類效率略低于PCCSGMM.PCCSGMM效率比DDC-K-means低,原因是維度較低時，PCCSGMM計算KNN和剔除無關(guān)屬性時消耗了較多時間。

圖4(b)給出了PCCSGMM、PCKA、DDC-K-means算法在Wireless、Avila數(shù)據(jù)集上的效率變化趨勢實(shí)驗(yàn)結(jié)果,該實(shí)驗(yàn)結(jié)果表明PCCSGMM在Avila數(shù)據(jù)集上的效率比PCKA高。原因是聚類分析前對無關(guān)屬性進(jì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)的“維災(zāi)”和無關(guān)屬性對聚類分析的影響，給出了一種基于相關(guān)子空間的聚類算法PCCSGMM,該算法充分了考慮了數(shù)據(jù)每一維自身的特點(diǎn),有效減少了不相關(guān)子空間和無關(guān)屬性對聚類效率和精度的影響。采用部分UCI標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行驗(yàn)證,證明了PCCSGMM算法的有效性和準(zhǔn)確性。接下來將設(shè)計應(yīng)用系統(tǒng)用于光譜數(shù)據(jù)聚類分析。