基于最小二乘法的判別嵌入式聚類(lèi)算法

支曉斌,蘆玉良

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

聚類(lèi)分析是一種基本的多元統(tǒng)計(jì)分析方法，是無(wú)監(jiān)督模式識(shí)別的一個(gè)重要分支[1]。聚類(lèi)分析能夠根據(jù)數(shù)據(jù)間的相似性對(duì)其進(jìn)行自動(dòng)分類(lèi)，對(duì)于探索數(shù)據(jù)集的內(nèi)部結(jié)構(gòu)具有重要意義，已在模式識(shí)別、圖像處理和數(shù)據(jù)挖掘等領(lǐng)域得到廣泛應(yīng)用。但在實(shí)際應(yīng)用中，聚類(lèi)分析經(jīng)常會(huì)面臨高維數(shù)據(jù)，“維數(shù)災(zāi)難”問(wèn)題使傳統(tǒng)聚類(lèi)算法的聚類(lèi)精度顯著退化，難以得到理想的聚類(lèi)效果。對(duì)高維數(shù)據(jù)的聚類(lèi)已經(jīng)成為聚類(lèi)分析領(lǐng)域的一個(gè)挑戰(zhàn)性問(wèn)題[2]。

判別聚類(lèi)(discriminative clustering,DC)算法首次將線性判別分析(linear discriminant analysis,LDA)和聚類(lèi)算法結(jié)合，在完成對(duì)數(shù)據(jù)特征提取實(shí)現(xiàn)降維的同時(shí)對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)[3]，但DC算法中所用的LDA存在散度矩陣奇異性問(wèn)題和求解特征值計(jì)算復(fù)雜度高的問(wèn)題。判別嵌入式聚類(lèi)(discriminative embedded clustering,DEC)算法[4]采用最大間距準(zhǔn)則(maximum margin criterion,MMC)[5-8]取代LDA來(lái)對(duì)數(shù)據(jù)降維，解決了散度矩陣奇異問(wèn)題。但是，DEC算法與DC算法類(lèi)似，需要求解特征值問(wèn)題，仍然存在計(jì)算復(fù)雜度高的問(wèn)題，嚴(yán)重影響著其實(shí)際應(yīng)用[9]。改進(jìn)的判別嵌入式聚類(lèi)(efficient discriminative embedded clustering,EDEC)算法[9]在原DEC算法上對(duì)數(shù)據(jù)進(jìn)行變換預(yù)處理，利用QR分解對(duì)類(lèi)間散度矩陣做特征分解，對(duì)數(shù)據(jù)做初次降維處理，在此基礎(chǔ)上用MMC對(duì)數(shù)據(jù)進(jìn)行二次降維，兩次降維提高了DEC算法的聚類(lèi)效率。

LDA等價(jià)于最小二乘問(wèn)題，此結(jié)論推廣至正則化的情形后，可得出一種高效率的LDA方法，即基于最小二乘法的線性判別分析(least square based linear discriminant analysis,LSLDA)算法[10]。鑒于這一方法的有效性，為改善DEC算法對(duì)高維數(shù)據(jù)的聚類(lèi)效率，本文將基于最小二乘法的降維過(guò)程引入到DEC算法當(dāng)中，提出一種基于最小二乘法的判別嵌入式聚類(lèi)(least square based discriminative embedded clustering,LSDEC)算法，先對(duì)數(shù)據(jù)做最小二乘變換預(yù)處理以降低數(shù)據(jù)的維數(shù)，再在該降維后的數(shù)據(jù)集上進(jìn)行DEC聚類(lèi)。

1　DEC算法和LSLDA算法

1.1　DEC算法

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

設(shè)這些數(shù)據(jù)點(diǎn)可分為c類(lèi)，第j類(lèi)中含有nj個(gè)數(shù)據(jù)點(diǎn)(j=1,2,…,c)。記第j類(lèi)為Xj，另記以其中數(shù)據(jù)點(diǎn)為列向量構(gòu)成的m×nj矩陣為Xj。

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

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

(1)

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

(2)

而ej=(1,1,…,1)為nj維行向量。

根據(jù)DEC算法，給定隸屬度矩陣，利用MMC對(duì)數(shù)據(jù)做降維處理，用K均值算法對(duì)降維后的數(shù)據(jù)進(jìn)行聚類(lèi)，然后用得到的新的隸屬度矩陣再去指導(dǎo)MMC對(duì)數(shù)據(jù)降維，重復(fù)降維和聚類(lèi)這兩個(gè)過(guò)程直到得到最佳的聚類(lèi)結(jié)果。DEC算法實(shí)現(xiàn)了子空間的選擇和對(duì)數(shù)據(jù)的聚類(lèi)，由于聚類(lèi)過(guò)程是在最優(yōu)子空間內(nèi)完成的，因此該算法具有良好的聚類(lèi)性能，另外，DEC算法利用MMC對(duì)數(shù)據(jù)降維，避免了DC算法存在的散布矩陣奇異性問(wèn)題。但是，DEC算法與DC算法類(lèi)似，需要求解特征值問(wèn)題，對(duì)高維數(shù)據(jù)計(jì)算復(fù)雜度高，這一缺陷限制了DEC算法的應(yīng)用。

1.2　LSLDA算法

LDA可描述為廣義特征值問(wèn)題[10]

XSXTw=αXXTw。

(3)

其中S為n×n階對(duì)稱(chēng)半正定矩陣，定義為

式(3)可改寫(xiě)為標(biāo)準(zhǔn)特征值問(wèn)題

(XXT)?XSXTw=αw,

其中矩陣(XXT)?代表矩陣XXT的廣義逆。

廣義特征值計(jì)算問(wèn)題與基于最小二乘法的LDA等價(jià)，并且這一等價(jià)性結(jié)論在正則化情形下仍然成立[10]。

LSLDA算法的具體步驟如下。

步驟1輸入數(shù)據(jù)矩陣X、帶有類(lèi)標(biāo)簽編碼的矩陣U、正則化參數(shù)γ。

步驟2解決最小二乘問(wèn)題

(4)

由于式(4)中的最小二乘問(wèn)題可以用共軛梯度迭代算法高效率求解，所以LSLDA比直接求解廣義特征值問(wèn)題的LDA更加高效。

2　LSDEC算法

為改善DEC算法對(duì)高維數(shù)據(jù)的聚類(lèi)效率，將LSLDA算法中的基于最小二乘法的降維過(guò)程引入到DEC算法中，通過(guò)對(duì)數(shù)據(jù)做最小二乘變換預(yù)處理，降低DEC算法的時(shí)間復(fù)雜度。

LSDEC算法具體步驟如下。

步驟1對(duì)數(shù)據(jù)進(jìn)行中心化和規(guī)范化處理，初始化隸屬度矩陣H0，給定平衡參數(shù)λ、正則化參數(shù)γ和閾值ε。

步驟2根據(jù)式(4)求解最小二乘問(wèn)題，求得變換矩陣W1。

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

步驟6令G=W1W3，用變換矩陣G對(duì)數(shù)據(jù)進(jìn)行降維處理,即Y=GTX，用K均值聚類(lèi)算法對(duì)降維后的數(shù)據(jù)進(jìn)行聚類(lèi)，更新隸屬度矩陣H。若‖H-H0‖<ε，則算法停止；否則將H賦給H0，返回步驟3。

步驟2至步驟4的加入使DEC算法的計(jì)算復(fù)雜度由原來(lái)的O(nm2)減少為O(nmc)，而高維數(shù)據(jù)的維數(shù)通常遠(yuǎn)大于類(lèi)數(shù)，即m?c，因此，LSDEC算法能夠有效地降低DEC算法的時(shí)間復(fù)雜度。

3　實(shí)驗(yàn)及分析

為驗(yàn)證新提出的LSDEC算法的有效性，將LSDEC算法與K均值算法、DEC算法和EDEC算法在8個(gè)真實(shí)數(shù)據(jù)集上做對(duì)比實(shí)驗(yàn)。

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

實(shí)驗(yàn)所用數(shù)據(jù)包括5個(gè)UCI數(shù)據(jù)集[11]Wine、Letter(abc)、Satimage、Spambse和Mfeat4，手寫(xiě)數(shù)字圖像數(shù)據(jù)MINIST[12]，文本數(shù)據(jù)DOC[13],和基因表達(dá)數(shù)據(jù)集Leukemia(http://cilab.ujn.edu.cn/datasets.htm)，共8組數(shù)據(jù)，各數(shù)據(jù)特性如表1所示。

表1　數(shù)據(jù)特性

實(shí)驗(yàn)在Intel(R)Core i5 2.50GHZ CPU，8G內(nèi)存win10系統(tǒng)環(huán)境下進(jìn)行，從算法運(yùn)行時(shí)間和聚類(lèi)精度兩個(gè)方面來(lái)衡量聚類(lèi)算法的性能。其中聚類(lèi)精度定義為

3.2　算法聚類(lèi)精度測(cè)試

平衡參數(shù)λ取值范圍為集合{10-6，10-4，10-2，100，102，104，106}，各算法在8組數(shù)據(jù)集上的聚類(lèi)精度對(duì)比如圖1所示。為方便表示，在圖中用LSDEC-6和LSDEC-1分別表示正則化參數(shù)取10-6和10-1的LSDEC算法。

由于DEC算法在Lekumia數(shù)據(jù)上運(yùn)行內(nèi)存溢出，所以無(wú)法獲得聚類(lèi)精度和運(yùn)行時(shí)間。由圖1可見(jiàn)，在選取合適的平衡參數(shù)時(shí)，LSDEC算法只有在Satimage數(shù)據(jù)上的最優(yōu)精度不及EDEC算法，在其他7組數(shù)據(jù)上的最優(yōu)精度均高于K均值算法、DEC算法和EDEC算法，而且在部分?jǐn)?shù)據(jù)上精度提升效果明顯。在8組數(shù)據(jù)上，LSDEC算法的聚類(lèi)精度在取任意γ時(shí)都優(yōu)于DEC算法的聚類(lèi)精度。

3.3　算法耗時(shí)測(cè)試

LSDEC算法與K均值算法、DEC算法和EDEC算法在不同平衡參數(shù)下對(duì)8組數(shù)據(jù)的運(yùn)行時(shí)間如圖2所示。

由圖2可見(jiàn)，K均值算法聚類(lèi)效率最高，但其最優(yōu)聚類(lèi)精度不及LSDEC算法。LSDEC算法在聚類(lèi)效率上優(yōu)于DEC算法，隨著數(shù)據(jù)維數(shù)和樣本數(shù)的增加，運(yùn)行效率提升效果越明顯。由以上實(shí)驗(yàn)結(jié)果可以看出，LSDEC算法在聚類(lèi)效率方面對(duì)DEC算法做了有效的改進(jìn)。

(a) Wine

(b) Satimage

(c) Mfeat4

(d) Letter (abc)

(e) Spambse

(f) MINIST

(g) Doc

(h) Lekumia

圖1各數(shù)據(jù)聚類(lèi)精度對(duì)比

(a) Wine

(b) Satimage

(c) Mfeat4

(d) Letter (abc)

(e) Spambse

(f) MINIST

(g) Doc

(h) Lekumia

圖2各數(shù)據(jù)聚類(lèi)時(shí)間對(duì)比

4　結(jié)語(yǔ)

LSDEC算法將最小二乘法引入到DEC算法中，先對(duì)數(shù)據(jù)做最小二乘變換降維預(yù)處理，然后利用MMC對(duì)數(shù)據(jù)進(jìn)行二次降維，兩次降維有效地降低了DEC算法的時(shí)間復(fù)雜度。實(shí)驗(yàn)結(jié)果表明，LSDEC算法不僅在效率上有顯著提升，而且在聚類(lèi)精度上也有所提高。LSDEC算法是一種線性的聚類(lèi)算法，下一步的工作可以將"核"方法[14]引入到LSDEC算法當(dāng)中，將其推廣成一種非線性的聚類(lèi)算法。