兩階段判別嵌入式聚類

支曉斌, 李亞蘭

(1.西安郵電大學(xué) 理學(xué)院， 陜西 西安 710121； 2.西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121)

聚類是按照一定的要求和規(guī)律對(duì)事物進(jìn)行區(qū)分和分類的非監(jiān)督模式識(shí)別過程，被廣泛應(yīng)用于眾多領(lǐng)域，包括圖像處理、信息檢索、數(shù)據(jù)挖掘等[1]。其目的是將相似的樣本分配到同一類，不相似的樣本分配到不同類，并揭示數(shù)據(jù)有意義的結(jié)構(gòu)。在實(shí)際應(yīng)用過程中，通常遇到高維數(shù)據(jù)集，數(shù)據(jù)的高維度性不僅增加了算法的計(jì)算時(shí)間和內(nèi)存需求，而且由于噪聲效應(yīng)和空間維度的欠采樣，會(huì)對(duì)聚類性能產(chǎn)生不利影響，這一現(xiàn)象被稱為“維數(shù)詛咒”[2]。因此，高維數(shù)據(jù)聚類成為聚類分析研究的難點(diǎn)和熱點(diǎn)問題之一，而實(shí)際應(yīng)用過程中普遍存在的高維數(shù)據(jù)使得對(duì)高維數(shù)據(jù)的聚類分析具有重要意義。

對(duì)于高維數(shù)據(jù)的聚類問題，現(xiàn)存在眾多具有針對(duì)性的聚類方法[3-10]。無監(jiān)督的判別聚類(discriminative clustering, DC)算法[3]將聚類和線性判別分析(linear discriminant analysis, LDA)[4]結(jié)合起來，實(shí)現(xiàn)了在降維過程中對(duì)數(shù)據(jù)的聚類。由于聚類是在LDA降維后的子空間中完成的，故DC算法常?？梢援a(chǎn)生比K-均值(K-means, KM)算法[5]更優(yōu)的聚類效果。從“核”方法的角度考慮，DC算法可等價(jià)于判別K-均值聚類(discriminative K-means, DKM)算法[6]，但存在散度矩陣奇異性問題。為避免DC算法中LDA的小樣本問題[7]和克服散度矩陣奇異性問題，判別嵌入式聚類(discriminative embedded clustering, DEC)算法[8]將子空間學(xué)習(xí)和聚類統(tǒng)一起來，用基于子空間學(xué)習(xí)的最大間距準(zhǔn)則(maximum margin criterion, MMC)[9]降維，以代替DC算法中的LDA降維，來得到最佳的判別向量。但是，這些算法都存在對(duì)高維數(shù)據(jù)計(jì)算復(fù)雜度高，聚類速度慢的問題。高效判別嵌入式聚類(efficient discriminative embedded clustering, EDEC)算法[10]利用QR[11]分解，并依據(jù)MMC對(duì)數(shù)據(jù)進(jìn)行兩次降維處理，可降低DEC算法的復(fù)雜度，但對(duì)數(shù)據(jù)的適應(yīng)性較差。

為改善DEC算法的運(yùn)行效率和EDEC算法對(duì)數(shù)據(jù)的適應(yīng)性問題，本文給出兩階段判別嵌入式聚類(two-stage discriminative embedded clustering, TSDEC)算法。在EDEC算法的基礎(chǔ)上引入正則化因子λ，得到EDEC算法的一種廣義形式。當(dāng)λ→∞時(shí)，TSDEC算法將退化為EDEC算法，而當(dāng)λ取其它值時(shí)，則得到不同于EDEC的新算法，從而提高了EDEC算法對(duì)數(shù)據(jù)的適應(yīng)性。此外，TSDEC與EDEC算法復(fù)雜度相當(dāng)，主要時(shí)間計(jì)算復(fù)雜度都是O(nmc)(n代表數(shù)據(jù)樣本的個(gè)數(shù)，m代表數(shù)據(jù)維數(shù)，c代表類數(shù))，故適合處理比較大的高維數(shù)據(jù)。

1 DEC算法

為了使得DC 算法能夠有效地對(duì)高維數(shù)據(jù)聚類，并且克服散度矩陣奇異性問題，DEC算法將幾個(gè)經(jīng)典降維方法統(tǒng)一到同一框架下，對(duì)數(shù)據(jù)聚類的同時(shí)實(shí)現(xiàn)降維，提高了DC算法的聚類效率。平衡參數(shù)η取不同值時(shí)，DEC算法可將已有的幾個(gè)經(jīng)典降維方法視為特殊情況。例如，當(dāng)η→0時(shí)，DEC算法等價(jià)于通過主成分分析(principal component analysis, PCA)[12]先對(duì)樣本降維，再對(duì)降維后數(shù)據(jù)用KM算法聚類；當(dāng)η=1時(shí)，DEC算法等價(jià)于通過正交質(zhì)心法(orthogonal centroid method, OCM)[13]先對(duì)樣本降維，再對(duì)降維后數(shù)據(jù)用KM算法聚類；當(dāng)η=2時(shí)，DEC算法等價(jià)于通過MMC先對(duì)樣本降維，再對(duì)降維后數(shù)據(jù)用KM算法聚類；當(dāng)η→∞時(shí)，DEC算法等價(jià)于通過正交最小二乘判別分析(orthogonal least squares discriminant analysis, OLSDA)[14]先對(duì)樣本降維，再對(duì)降維后數(shù)據(jù)用KM算法聚類。

X=(x1,x2, …,xn)。

聚類的目標(biāo)是將所有數(shù)據(jù)樣本分成c類，設(shè)第j類為Xj，其中含有nj個(gè)數(shù)據(jù)樣本(j=1,2,…,c)，以這些數(shù)據(jù)樣本為列向量可構(gòu)成m×nj的數(shù)據(jù)矩陣Xj。

DEC算法可以描述為優(yōu)化問題

maxJDEC(W,H)=
tr {WT[Sb+(1-η)Sw]W},
s.t.WTW=I。

其中，η為平衡參數(shù)，W為樣本由高維空間映射到低維空間的待求變換矩陣，矩陣H=(hij)n×c為待求隸屬度矩陣，若數(shù)據(jù)樣本xi屬于第j類，則hij=1；否則，hij=0。類內(nèi)散度矩陣Sw和類間散度矩陣Sb分別定義為

矩陣Hw和Hb分別定義為

Hw=[X1-v1e1,…,Xc-vcec],

(1)

(2)

其中，ej=(1,2,…,1)∈nj為行向量。

以m′代表嵌入子空間中數(shù)據(jù)的維數(shù)，T代表算法運(yùn)行的迭代次數(shù)，那么，DEC算法的時(shí)間計(jì)算復(fù)雜度為O[(nm2+ncm′)T]。

2 TSDEC算法

TSDEC算法首先用奇異值分解方法代替EDEC算法中的QR分解對(duì)正則化的類間散度矩陣做預(yù)處理，對(duì)數(shù)據(jù)矩陣進(jìn)行初次降維；然后，在低維空間利用DEC算法中的經(jīng)典降維方法對(duì)數(shù)據(jù)進(jìn)行二次降維；最后，對(duì)降維兩次的數(shù)據(jù)進(jìn)行聚類。初次降維后數(shù)據(jù)的維數(shù)可以達(dá)到c維，故可使第二次降維過程變得更加高效，提升算法對(duì)高維數(shù)據(jù)的聚類效率。另外，引入正則化過程，得到EDEC算法的一種廣義形式，以提高EDEC算法對(duì)數(shù)據(jù)的適應(yīng)性。

TSDEC算法詳細(xì)步驟如下。

步驟1對(duì)原始數(shù)據(jù)集執(zhí)行規(guī)范化和中心化過程，并初始化類標(biāo)簽矩陣H。

步驟2根據(jù)(2)式構(gòu)造矩陣Hb。

步驟3對(duì)矩陣Hb進(jìn)行奇異值分解,得

Hb=UΣVT,

其中，U∈m×m和V∈c×c為正交矩陣，Σ∈m×c為對(duì)角陣。

步驟4Σ的前c行c列構(gòu)成方陣Σ1，以Ic代表c階單位矩陣，將奇異值矩陣正則化為

再令

步驟5令

W=(w1,w2,…,wc)。

步驟7利用求得的特征子空間，計(jì)算最優(yōu)變換矩陣G=QW。

步驟8利用y=GTx對(duì)數(shù)據(jù)進(jìn)行投影變換，在降維后的投影空間中對(duì)數(shù)據(jù)執(zhí)行KM聚類算法，更新隸屬度矩陣H。如果滿足‖H-H0‖<ε，則停止計(jì)算；否則，令H0=H，轉(zhuǎn)回步驟3。ε為停止閾值。

TSDEC算法將DEC算法的主要計(jì)算復(fù)雜度由O(nm2)降低為O(nmc)，通常對(duì)于高維數(shù)據(jù)集有m?c，因此，TSDEC算法在運(yùn)行速率上與EDEC算法相當(dāng)，而比DEC算法更高效。

TSDEC算法在EDEC算法的基礎(chǔ)上增加了步驟4中的奇異值矩陣正則化過程，即令

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

將TSDEC算法與KM算法、DEC算法和EDEC算法在不同正則化參數(shù)下對(duì)6個(gè)數(shù)據(jù)集進(jìn)行對(duì)比性實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)選取6個(gè)數(shù)據(jù)集，包括3個(gè)UCI數(shù)據(jù)集[15]Wine、Letter(abc)、Satimage，一個(gè)文本數(shù)據(jù)集[16]Doc，一個(gè)手寫體數(shù)據(jù)集[17]MNIST和一個(gè)基因表達(dá)數(shù)據(jù)集[18]Global Cancer Map(GCM)。數(shù)據(jù)特性如表1所示。

表1 6個(gè)數(shù)據(jù)集的相關(guān)特性

實(shí)驗(yàn)在Intel Core i5 2.8 GHz CPU，4 GB內(nèi)存Window 10環(huán)境下的電腦上進(jìn)行運(yùn)算。為了防止算法陷入局部最優(yōu)，算法運(yùn)行10次后取平均值。最大運(yùn)行迭代次數(shù)設(shè)置為100，停止閾值ε設(shè)為10-5。

3.2 準(zhǔn)確度測試

針對(duì)6個(gè)數(shù)據(jù)集，平衡參數(shù)η依次取值為2、1、1、∞、2、2，正則化參數(shù)λ的取值集合為{10-6，10-5，10-4，10-3，10-2，10-1，100，101，102，103，104，105，106}。4種算法在各數(shù)據(jù)集上的聚類性能隨正則化參數(shù)的變化趨勢如圖1所示。其中，DEC算法在GCM數(shù)據(jù)集上運(yùn)行內(nèi)存溢出，無法獲得聚類準(zhǔn)確度，而KM算法、DEC算法和EDEC算法的聚類準(zhǔn)確度各是一條不隨正則化參數(shù)λ變化的直線。

由圖1所示聚類結(jié)果可知，對(duì)于大多數(shù)正則化參數(shù)λ，TSDEC算法的聚類準(zhǔn)確度優(yōu)于其它3種算法。當(dāng)正則化參數(shù)λ越大時(shí)，TSDEC算法的聚類準(zhǔn)確度越接近于EDEC算法，這驗(yàn)證了TSDEC算法是EDEC算法的廣義形式，且當(dāng)正則化參數(shù)λ趨于無窮大時(shí)，EDEC算法成為TSDEC算法的特例。

圖1各數(shù)據(jù)集聚類結(jié)果

不同正則化參數(shù)下的最優(yōu)聚類準(zhǔn)確度及平均聚類準(zhǔn)確度結(jié)果如表2所示。其中，“—”表示DEC算法在相應(yīng)參數(shù)下內(nèi)存溢出。

由表2可知，在大多數(shù)數(shù)據(jù)集上，TSDEC算法的最優(yōu)聚類準(zhǔn)確度及平均聚類準(zhǔn)確度優(yōu)于KM算法、DEC算法EDEC算法。

表2 4種算法在6組數(shù)據(jù)集上的聚類準(zhǔn)確度

3.3 運(yùn)行時(shí)間測試

4種算法對(duì)6個(gè)數(shù)據(jù)集在不同正則化參數(shù)取值下的運(yùn)行時(shí)間如圖2所示。其中，DEC算法在GCM數(shù)據(jù)集上運(yùn)行內(nèi)存溢出，無法獲得運(yùn)行時(shí)間，而KM算法、DEC算法和EDEC算法的運(yùn)行時(shí)間各是一條不隨正則化參數(shù)λ變化的直線。

圖2 各數(shù)據(jù)集上4種算法的運(yùn)行時(shí)間

由圖2可知，除了GCM數(shù)據(jù)集，KM算法在其它數(shù)據(jù)集上的平均運(yùn)行效率最高，運(yùn)行時(shí)間是4種算法中最少的，但聚類準(zhǔn)確度相較于其它算法有所偏低。TSDEC算法與EDEC算法的運(yùn)行效率基本持平，且當(dāng)正則化參數(shù)λ越大時(shí)，TSDEC算法的運(yùn)行時(shí)間越接近于EDEC算法。對(duì)于兩個(gè)高維數(shù)據(jù)集DOC和GCM而言，TSDEC算法和EDEC算法的運(yùn)行效率明顯優(yōu)于DEC算法。

各數(shù)據(jù)集在不同正則化參數(shù)下的最優(yōu)聚類準(zhǔn)確度和平均聚類準(zhǔn)確度相對(duì)應(yīng)的運(yùn)行時(shí)間如表3所示。其中，To和Tm分別表示各算法的最快運(yùn)行時(shí)間和平均運(yùn)行時(shí)間， “—”表示DEC算法在相應(yīng)參數(shù)下內(nèi)存溢出。由表3可知，除KM算法外，在大多數(shù)數(shù)據(jù)集上，EDEC算法的平均運(yùn)行效率較高，而TSDEC算法的最優(yōu)運(yùn)行效率相較于DEC算法和EDEC算法有所提高。

表3 4種算法在6組數(shù)據(jù)集上的運(yùn)行時(shí)間

4 結(jié)語

TSDEC算法通過對(duì)正則化的類間散度矩陣做奇異值分解，得到數(shù)據(jù)的降維預(yù)處理，再對(duì)降維后數(shù)據(jù)進(jìn)行判別嵌入式聚類，可以看作是在EDEC算法中引入類間散度矩陣正則化過程所得到的一般性算法。TSDEC算法將DEC算法的主要時(shí)間復(fù)雜度由O(nm2)降低為O(nmc)。實(shí)驗(yàn)結(jié)果表明，正則化過程的引入提高了原EDEC算法對(duì)數(shù)據(jù)的適應(yīng)能力。對(duì)大多數(shù)的數(shù)據(jù)集而言，TSDEC算法的聚類準(zhǔn)確度(包括平均準(zhǔn)確度和不同參數(shù)下的最優(yōu)準(zhǔn)確度)優(yōu)于DEC與EDEC算法。TSDEC算法的運(yùn)行效率與EDEC算法相當(dāng)，對(duì)于高維數(shù)據(jù)集，二者的運(yùn)行效率均優(yōu)于DEC算法。TSDEC為線性聚類算法，為了提高算法對(duì)非線性可分?jǐn)?shù)據(jù)的聚類性能，下一步的工作是利用核技巧[19]給出TSDEC算法的核版本。