黃欣辰,皋 軍,黃豪杰

(1.鹽城工學(xué)院信息工程學(xué)院,江蘇 鹽城 224002; 2.江蘇科技大學(xué)計算機(jī)學(xué)院,江蘇 鎮(zhèn)江 212003)

0 引 言

聚類分析的目的是根據(jù)對象之間的相似度對對象分組，使得簇內(nèi)對象相似度盡量高，而簇間對象相似度盡量低，簇內(nèi)相似性越大，簇間差別越大，聚類性能越好[1]。但單個的聚類方法不能令人產(chǎn)生滿意的結(jié)果，聚類集成是一種將多個不同的聚類結(jié)果進(jìn)行合并，能夠獲得比傳統(tǒng)聚類算法更好聚類結(jié)果的方法[2]。目前聚類集成的研究主要集中在無監(jiān)督學(xué)習(xí)領(lǐng)域中，沒有考慮到用戶或者專家提供的先驗知識。而半監(jiān)督聚類集成將少量帶有標(biāo)簽的數(shù)據(jù)代入到聚類集成中，監(jiān)督與指導(dǎo)集成過程，最終獲得更加優(yōu)越的聚類結(jié)果，使得整個過程更具穩(wěn)定性、準(zhǔn)確性和魯棒性[3-5]。

常見的半監(jiān)督聚類方法有3種。第1種是基于約束的半監(jiān)督聚類[4],樣本兩兩之間包含了一組成對約束信息，即正約束(must-link)和負(fù)約束(cannot-link)信息，通過它們能很有效地指導(dǎo)聚類過程。must-link約束規(guī)定：若2個樣本滿足must-link約束，則2個樣本在聚類時一定被劃分到同一個簇中。cannot-link約束規(guī)定：若2個樣本滿足cannot-link約束，則2個樣本在聚類時一定被劃分到不同簇之中。第2種是基于距離的半監(jiān)督聚類[6],這類算法是根據(jù)樣本之間的約束信息來構(gòu)造一個距離度量函數(shù)，對樣本點進(jìn)行劃分，形成分組。第3種是基于約束和距離的半監(jiān)督聚類算法[7],它是第1種和第2種方法的融合。

隨著大數(shù)據(jù)時代的到來，各種各樣的數(shù)據(jù)出現(xiàn)在人們生活中，如文本數(shù)據(jù)、圖片數(shù)據(jù)、聲音數(shù)據(jù)、視頻數(shù)據(jù)、基因數(shù)據(jù)等，且這些冗長的數(shù)據(jù)越來越呈現(xiàn)出高維性的特點，使得很多算法在數(shù)據(jù)分析過程中引起“維數(shù)災(zāi)難”[8-9]。在實際生活中，通常先對高維數(shù)據(jù)進(jìn)行降維處理，然后再進(jìn)行后續(xù)操作。

針對上述問題，本文在現(xiàn)有的半監(jiān)督降維聚類算法基礎(chǔ)上，提出一種基于PCA降維技術(shù)的成對約束半監(jiān)督聚類集成算法(Semi supervised clustering ensemble with pairwise constraints based on PCA dimension reduction, SSCEDR)。首先通過PCA主成分分析對原始數(shù)據(jù)進(jìn)行降維，然后結(jié)合半監(jiān)督聚類集成技術(shù)，在降維后的空間中將成對約束等先驗知識代入到聚類集成過程，得到最終的聚類結(jié)果。在多組數(shù)據(jù)集上進(jìn)行的實驗表明，SSCEDR算法能夠提升聚類質(zhì)量，取得更好的聚類結(jié)果。

1 PCA降維

降維是一種對高維數(shù)據(jù)進(jìn)行維數(shù)約簡的方法，一般根據(jù)高維數(shù)據(jù)特征的重要性，有選擇地保留一些重要特征，實現(xiàn)數(shù)據(jù)從高維到低維的轉(zhuǎn)化。常見的降維算法有奇異值分解(SVD)[10]、主成分分析(PCA)[11]、線性判別分析(LDA)[12]、因子分析(FA)[13]、獨立成分分析(ICA)[14]。

本文選用的降維算法是PCA(Principal Componet Analysis),即主成分分析法，是一種應(yīng)用十分普遍的線性降維算法。主成分分析的核心思想是將n維特征映射到k維特征，得到一種新的正交特征，即主成分，它是在原有n維特征的基礎(chǔ)上重建的k維特征[15]。

給定一組數(shù)據(jù)：X=[x1,x2，…,xn],降維的目標(biāo)是要找出一個投影矩陣W=[w1,w2,…,wd],使得數(shù)據(jù)的低維表示Y=WTX能夠保留原有高維數(shù)據(jù)的原始結(jié)構(gòu)。PCA需要找到數(shù)據(jù)方差最大的方向，定義目標(biāo)函數(shù)為：

=arg max Tr(WTSW)

(1)

它的衡量指標(biāo)是數(shù)據(jù)方差，數(shù)據(jù)間的方差越大，包含數(shù)據(jù)的原始特征信息越多，數(shù)據(jù)間的方差越小，包含數(shù)據(jù)的原始特征信息就越少。PCA就是在盡可能地保留原始數(shù)據(jù)重要特征的基礎(chǔ)上，對數(shù)據(jù)進(jìn)行降維，將高維數(shù)據(jù)投影到數(shù)據(jù)方差最大的方向組成新的子空間[16]。

(2)

G(k)為方差累計貢獻(xiàn)率，也叫特征值累計貢獻(xiàn)率，當(dāng)累計貢獻(xiàn)率大于90%時，一般認(rèn)為能足夠反映原來的數(shù)據(jù)信息，此時對應(yīng)的k就是降維后的維數(shù)。

2 基于成對約束的半監(jiān)督聚類集成

常見的半監(jiān)督聚類算法有基于約束的方法(CBSSC)[17]、基于距離測度函數(shù)學(xué)習(xí)的方法(DBSSC)[18]、結(jié)合約束與距離的半監(jiān)督算法(CDBSSC)[19]。受文獻(xiàn)[20]的啟發(fā)，本文選擇基于約束的方法，來指導(dǎo)半監(jiān)督信息的添加，引入一種基于成對約束的半監(jiān)督聚類集成算法(Semi supervised clustering Ensemble based on pairwise constraints，SSCE)。

基于成對約束的半監(jiān)督聚類集成可分為2個步驟:1)輸入數(shù)據(jù)集，運行常用聚類分析算法，輸出聚類成員集P={p1,p2,…,pH}，這一步稱為聚類成員生成；2)添加半監(jiān)督信息，得到半監(jiān)督相似矩陣S′，輸出最終結(jié)果Pf，這一步為半監(jiān)督共識函數(shù)設(shè)計[21]。下面著重對第二步予以闡述。

定義1must-link集合M={(xi,xj)},若(xi,xj)∈M，則表明數(shù)據(jù)xi和xj必屬于同類，即xi和xj滿足正關(guān)聯(lián)約束關(guān)系。

定義2cannot-link集合C={(xi,xj)},若(xi,xj)∈C，則表明數(shù)據(jù)xi和xj必屬于不同類，即xi和xj滿足負(fù)關(guān)聯(lián)約束關(guān)系。

故可用aij來表示樣本點i和樣本點j之間的相似度，aij用公式(3)表示：

(3)

即樣本點i和j滿足must-link約束aij=1，否則aij=0。

根據(jù)公式(3)，能夠得到包含must-link約束信息的矩陣M和包含cannot-link約束信息的矩陣C。矩陣M和矩陣C的維度與數(shù)據(jù)集X的相似性矩陣S相同。其中S=(s(xi,xj))N×N,s(xi,xj)=NMI(P(i,:),P(j,:))。

加入半監(jiān)督信息后的相似性矩陣用D表示，計算公式如公式(4)：

D=S-C+M

(4)

因為矩陣S、M和C的取值范圍都在0～1，所以矩陣D的取值范圍在-1～2之間，因此需要對矩陣D繼續(xù)優(yōu)化。如果2個樣本的相似度大于1，則一定是同一類，故令它們相似度為1；如果2個樣本的相似度小于0，則一定是不同類，故令它們相似度為0。因此可用公式(5)來優(yōu)化矩陣D，獲得半監(jiān)督相似性矩陣S′:

(5)

基于成對約束的半監(jiān)督聚類集成算法。

輸入：數(shù)據(jù)集X={x1,x2,…,xN},簇個數(shù)k,聚類成員個數(shù)H。

1)運行k-means算法H次，每次隨機(jī)選取初始質(zhì)心，生成H個初始聚類成員；形成集成成員集P；

2)根據(jù)公式(3)～公式(5)得到相似性矩陣S′;

3)計算拉普拉斯矩陣L的最小特征值和對應(yīng)特征向量，構(gòu)建特征向量空間F；

4)在特征向量空間F中運行k-means算法得到最終聚類結(jié)果Pf。

輸出：最終聚類結(jié)果Pf。

3 基于PCA降維的半監(jiān)督聚類集成算法

基于上面的描述，本文提出一種基于PCA降維技術(shù)和成對約束的半監(jiān)督聚類集成算法，首先通過PCA降維對原始高維數(shù)據(jù)進(jìn)行降維，將原始數(shù)據(jù)降維到k維，并最大限度地保持原有數(shù)據(jù)集的一些重要特征，然后對得到的降維后的數(shù)據(jù)集進(jìn)行基于成對約束的半監(jiān)督聚類集成，其步驟如下：

輸入：數(shù)據(jù)集X={x1,x2,…,xN},簇個數(shù)k,聚類成員個數(shù)H.降維后的維數(shù)d。

1)數(shù)據(jù)降維:

②計算樣本的協(xié)方差矩陣XXT,并進(jìn)行特征值分解；

③取最大的d個特征值所對應(yīng)的特征向量(ω1,…,ωd)組成特征向量矩陣W；

④將數(shù)據(jù)轉(zhuǎn)化到d維空間中，即Y=WTX。

2)對數(shù)據(jù)集Y,運行k-means算法H次，每次隨機(jī)選取初始質(zhì)心，生成H個初始聚類成員,形成集成成員集P。

3)根據(jù)公式(3)～公式(5)得到相似性矩陣S′。

4)計算拉普拉斯矩陣L的最小特征值和對應(yīng)特征向量，構(gòu)建特征向量空間F。

5)在特征向量空間F中運行k-means算法得到最終聚類結(jié)果Pf。

輸出：最終聚類結(jié)果Pf。

4 實 驗

4.1 實驗數(shù)據(jù)集和評價標(biāo)準(zhǔn)

為了驗證算法的有效性，實驗中共選用了8組數(shù)據(jù)集，其中4組UCI數(shù)據(jù)集，2組手寫體圖像數(shù)據(jù)集，2組人臉數(shù)據(jù)集。樣本數(shù)從148到2500不等，類別數(shù)從2到40不等，原始維數(shù)從13到1024不等。詳細(xì)數(shù)據(jù)見表1。

表1 實驗數(shù)據(jù)集

因為所選的數(shù)據(jù)集類別標(biāo)簽已知，真實的類別標(biāo)簽可以為各類評價指標(biāo)使用。實驗采用Micro-p[22]這種常見的聚類性能評價指標(biāo)來判斷聚類效果。

Micro-p具體公式為：

其中,k為數(shù)據(jù)集的類別數(shù)，n是數(shù)據(jù)集中對象的總數(shù)，ai是聚類結(jié)果中正確分到第i個類的個數(shù)。顯然Micro-p值越大，聚類結(jié)果和真實類別標(biāo)簽越匹配，當(dāng)聚類結(jié)果和真實類別標(biāo)簽一一對應(yīng)時，Micro-p值達(dá)到最大值1。

4.2 實驗設(shè)計

本文提出一種基于PCA降維技術(shù)的成對約束半監(jiān)督聚類集成算法(SSCEDR)，實驗的目的是驗證所提的算法能否獲得較好的聚類效果。實驗分為2部分：1)對數(shù)據(jù)集進(jìn)行PCA降維，選擇合適降維維度，并在UCI數(shù)據(jù)集上測試算法的基本能力；2)在手寫體數(shù)據(jù)集和人臉數(shù)據(jù)集上，將本文提出的算法SSCEDR與其他主流算法進(jìn)行對比。對比算法分為2類，傳統(tǒng)的聚類集成算法和常見的半監(jiān)督降維算法。傳統(tǒng)的算法包括半監(jiān)督聚類集成算法SSCE、無監(jiān)督聚類集成算法CSPA、HGPA。常見的半監(jiān)督降維算法包括基于約束的半監(jiān)督降維SSDR、半監(jiān)督判別分析SDA以及約束Fisher判別分析cFDA。為了實驗具有可對比性，實驗對數(shù)據(jù)集以k-means算法，運行100次，生成初始聚類成員集P={p1,p2,…,p100}，作為幾種聚類集成算法的輸入。

4.3 實驗結(jié)果

4.3.1 PCA降維實驗結(jié)果

圖1顯示了PCA降維算法在各個維度的特征值累計貢獻(xiàn)率，通過圖1可以看出隨著降維算法維度的增加，特征值貢獻(xiàn)率先是快速增長，達(dá)到一定的維度后就平穩(wěn)增長。當(dāng)特征值貢獻(xiàn)率達(dá)到0.9時，意味著只有約10%的信息被丟失，此時降維效果最佳。通過實驗發(fā)現(xiàn)當(dāng)數(shù)據(jù)集Wine降到7維、Lymphography降到10維、Sonar降到16維、Ionosphere降到16維、USPS降到22維、MNIST降到90維、ORL降到60維、Yale降到50維時，特征值貢獻(xiàn)率均超過了0.9，足夠能反映原始變量的信息，故選擇此時的維度，作為降維后的數(shù)據(jù)集維度。

(a)Wine

更新后的實驗數(shù)據(jù)集信息如表2所示。

表2 降維后的實驗數(shù)據(jù)集

4.3.2 測試算法基本聚類能力

UCI數(shù)據(jù)集常用來測試聚類算法的聚類效果。本文通過測試UCI數(shù)據(jù)集的4個數(shù)據(jù)子集：Wine數(shù)據(jù)集、Lymphography數(shù)據(jù)集、Sonar數(shù)據(jù)集、Ionosphere數(shù)據(jù)集來表明本文方法的基本聚類能力。表3與圖2顯示了本文算法SSCEDR在UCI數(shù)據(jù)集上的Micro-p值。

表3 SSCEDR在UCI數(shù)據(jù)集上的表現(xiàn)

圖2 SSCEDR在UCI數(shù)據(jù)集上的Micro-p值

通過表3可以發(fā)現(xiàn)PCA+SSCE在UCI數(shù)據(jù)集Wine、Sonar、Ionosphere上的Micro-p值均超過了0.75，具有不錯的聚類能力。為了更好驗證SSCEDR算法的聚類效果，實驗將本文算法與其他主流聚類集成算法在高維數(shù)據(jù)集上結(jié)果進(jìn)行比較。

4.3.3 與其他聚類算法進(jìn)行對比

在大容量數(shù)據(jù)集上進(jìn)行實驗，能更好地驗證聚類算法性能。本文在大容量數(shù)據(jù)集USPS、MNIST、ORL和Yale上，將本文提出的算法SSCEDR與傳統(tǒng)的算法SSCE、CSPA、HGPA等算法和半監(jiān)督降維算法SSDR、SDA、cFDA進(jìn)行比較。

表4展示在大容量數(shù)據(jù)集上，本文算法SSCEDR與傳統(tǒng)聚類集成算法的Micro-p值，為了更直觀地比較算法的Micro-p值，將表4中聚類集成算法的Micro-p值以柱狀圖的形式展示在圖3中。

表4 與傳統(tǒng)算法在數(shù)據(jù)集上的實驗結(jié)果比較

觀察表4和圖3，可以更直觀地發(fā)現(xiàn)：

圖3 本文算法與傳統(tǒng)算法的結(jié)果比較

1)在實驗所取的4個大容量數(shù)據(jù)集上，本文算法SSCEDR和半監(jiān)督聚類集成算法SSCE取得的Micro-p值均高于無監(jiān)督聚類集成CSPA和HGPA的Micro-p值。這表明加入成對約束信息的半監(jiān)督聚類集成算法，能在聚類集成過程中，更好地指導(dǎo)數(shù)據(jù)聚類。與無監(jiān)督聚類集成相比，半監(jiān)督聚類集成能取得更好的聚類結(jié)果。

2)觀察柱狀圖可以發(fā)現(xiàn)，除了在手寫體數(shù)據(jù)集MNIST上，SSCEDR算法取得的Micro-p值低于SSCE算法的值，在其他3個數(shù)據(jù)集上都取得了最高的Micro-p值，且相對于其他算法有較明顯的優(yōu)勢。這說明結(jié)合降維技術(shù)的半監(jiān)督聚類集成，在實驗數(shù)據(jù)集上取得了較好的聚類結(jié)果。

表5展示了本文算法SSCEDR與其他的常見的半監(jiān)督降維算法在數(shù)據(jù)集上的結(jié)果，為了方便比較它們的Micro-p值，將表5中的實驗結(jié)果以柱狀圖的形式展示在圖4中。

表5 與其他半監(jiān)督降維算法在數(shù)據(jù)集上的結(jié)果比較

圖4 本文算法與其他降維算法的結(jié)果比較

觀察表5和圖4可以發(fā)現(xiàn),在數(shù)據(jù)集USPS、MNIST、ORL和Yale上，本文提出的基于PCA降維的成對約束半監(jiān)督算法相比較其他半監(jiān)督降維算法均取得較高的Micro-p值，這表明結(jié)合PCA降維的半監(jiān)督聚類集成，在大容量數(shù)據(jù)集上取得了比較好的聚類結(jié)果。

總體來看，在聚類性能方面，半監(jiān)督聚類集成算法較優(yōu)于無監(jiān)督聚類集成算法，本文提出的SSCEDR算法相比較于傳統(tǒng)的無監(jiān)督聚類集成算法、半監(jiān)督聚類集成算法以及常見的半監(jiān)督降維算法更具有優(yōu)勢，在多組數(shù)據(jù)集上都獲得了較好的聚類結(jié)果，因此本文提出的結(jié)合降維技術(shù)的半監(jiān)督選擇聚類集成算法能提高半監(jiān)督聚類集成算法的聚類效果。

5 結(jié)束語

本文在現(xiàn)有的半監(jiān)督聚類集成算法基礎(chǔ)上，提出了一種基于PCA降維的成對約束半監(jiān)督聚類集成算法。該算法首先通過PCA降維技術(shù)，將高維數(shù)據(jù)轉(zhuǎn)化為低維數(shù)據(jù)，然后在降維空間上進(jìn)行半監(jiān)督聚類集成，添加成對約束信息指導(dǎo)聚類過程，使得算法的聚類性能得到提高。實驗結(jié)果表明，結(jié)合PCA降維的半監(jiān)督聚類集成算法性能相較傳統(tǒng)的無監(jiān)督聚類集成算法和半監(jiān)督聚類集成算法有了一定的提升，且比一些常見的半監(jiān)督降維算法更具優(yōu)勢，在某些數(shù)據(jù)集上效果明顯。但是算法的有效性和穩(wěn)定性還需要進(jìn)一步提高，如數(shù)據(jù)集降維后的維數(shù)是否能保證原始數(shù)據(jù)特征不丟失、數(shù)據(jù)間的成對約束是否正確、聚類成員個數(shù)的設(shè)定等，都可能影響算法的最終性能。