支曉斌,蘆玉良

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

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

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

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

1　DEC算法和LSLDA算法

1.1　DEC算法

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

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

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

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

(1)

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

(2)

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

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

1.2　LSLDA算法

LDA可描述為廣義特征值問題[10]

XSXTw=αXXTw。

(3)

其中S為n×n階對稱半正定矩陣，定義為

式(3)可改寫為標準特征值問題

(XXT)?XSXTw=αw,

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

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

LSLDA算法的具體步驟如下。

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

步驟2解決最小二乘問題

(4)

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

2　LSDEC算法

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

LSDEC算法具體步驟如下。

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

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

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

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

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

3　實驗及分析

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

3.1　實驗設(shè)置

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

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

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

3.2　算法聚類精度測試

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

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

3.3　算法耗時測試

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

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

(a) Wine

(b) Satimage

(c) Mfeat4

(d) Letter (abc)

(e) Spambse

(f) MINIST

(g) Doc

(h) Lekumia

圖1各數(shù)據(jù)聚類精度對比

(a) Wine

(b) Satimage

(c) Mfeat4

(d) Letter (abc)

(e) Spambse

(f) MINIST

(g) Doc

(h) Lekumia

圖2各數(shù)據(jù)聚類時間對比

4　結(jié)語

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