兩階段判別嵌入模糊聚類(lèi)

支曉斌, 牛傳林, 李亞蘭

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

聚類(lèi)[1]是統(tǒng)計(jì)多變量分析的方法之一，作為機(jī)器學(xué)習(xí)、模式識(shí)別和計(jì)算機(jī)視覺(jué)領(lǐng)域中的一種基本方法，其目的是將相似模式的數(shù)據(jù)分配到同一個(gè)類(lèi)別中，不同模式的數(shù)據(jù)分配到不同類(lèi)別中，并對(duì)數(shù)據(jù)內(nèi)部結(jié)構(gòu)進(jìn)行重構(gòu)。然而，高維數(shù)據(jù)的復(fù)雜性會(huì)影響聚類(lèi)性能，即“維數(shù)詛咒”[2]。對(duì)高維數(shù)據(jù)聚類(lèi)仍然是一個(gè)具有挑戰(zhàn)性的問(wèn)題。

判別聚類(lèi)(discriminative clustering, DC)算法[3]將無(wú)監(jiān)督的聚類(lèi)方法和有監(jiān)督的基于線性判別分析(linear discriminant analysis, LDA)[4]的降維方法組合在一個(gè)聚類(lèi)框架中，交替執(zhí)行初始數(shù)據(jù)空間中的LDA降維和低維變換空間中的聚類(lèi)過(guò)程，實(shí)現(xiàn)了對(duì)高維數(shù)據(jù)的有效聚類(lèi)，但是，該方法運(yùn)行效率低。判別K-均值 (discriminativeK-means, DKM) 聚類(lèi)算法[5]通過(guò)消除基于LDA的迭代降維過(guò)程，簡(jiǎn)化了DC算法，但存在小樣本問(wèn)題[6]。判別嵌入式聚類(lèi)(discriminative embedded clustering, DEC)算法[7]通過(guò)交替執(zhí)行基于子空間學(xué)習(xí)的降維方法和K-均值聚類(lèi)方法，利用最大間距準(zhǔn)則(maximum margin criterion, MMC)[8]代替DC聚類(lèi)算法中的LDA方法實(shí)現(xiàn)對(duì)數(shù)據(jù)的降維處理，從而避免了LDA面對(duì)小樣本的問(wèn)題。但是，DEC算法的計(jì)算復(fù)雜度高，當(dāng)數(shù)據(jù)維數(shù)較高時(shí)，運(yùn)行速度慢。為了提高DEC算法的運(yùn)行效率，改進(jìn)的判別嵌入式(efficient discriminative clustering, EDEC)算法[9]先利用QR分解[10]實(shí)現(xiàn)對(duì)樣本的初次降維，然后利用MMC對(duì)降維后的數(shù)據(jù)再次降維，通過(guò)兩次降維，降低了DEC算法的計(jì)算復(fù)雜度，同時(shí)也提高了算法的聚類(lèi)性能，但該算法對(duì)數(shù)據(jù)適應(yīng)性較差。為了進(jìn)一步改善EDEC算法對(duì)數(shù)據(jù)樣本適應(yīng)性差的問(wèn)題，兩階段判別嵌入式聚類(lèi)(two-stage discriminative embedded clustering, TSDEC)算法[11]在EDEC算法的基礎(chǔ)上對(duì)類(lèi)間散度矩陣正則化處理，即引入正則化參數(shù)，使得在保持與EDEC算法相同運(yùn)行效率的情況下，提高了算法對(duì)數(shù)據(jù)的適應(yīng)性能力。但是，TSDEC算法中的聚類(lèi)過(guò)程使用的是K-均值 (K-means, KM)聚類(lèi)算法[12]，本質(zhì)上是一種硬聚類(lèi)算法，無(wú)法有效地反映數(shù)據(jù)集的真實(shí)分布結(jié)構(gòu)。

在TSDEC算法的基礎(chǔ)上，本文提出一種兩階段判別嵌入模糊聚類(lèi) (two-stage discriminative embedded fuzzy clustering, TSDEFC)算法。該算法首先通過(guò)兩階段降維方法對(duì)數(shù)據(jù)進(jìn)行處理，降低算法的計(jì)算復(fù)雜度；其次在初始化和迭代過(guò)程中，利用模糊C-均值(fuzzyC-means, FCM)聚類(lèi)算法[13]實(shí)現(xiàn)對(duì)數(shù)據(jù)的聚類(lèi)，充分考慮每個(gè)樣本點(diǎn)對(duì)數(shù)據(jù)類(lèi)中心的影響，以期有效地反映數(shù)據(jù)的真實(shí)分布結(jié)構(gòu)。

1 兩階段判別嵌入式聚類(lèi)

兩階段判別嵌入式聚類(lèi)算法在EDEC算法的基礎(chǔ)上引入正則化參數(shù)λ，通過(guò)對(duì)類(lèi)間散度矩陣正則化處理提高算法對(duì)數(shù)據(jù)的適應(yīng)性[11]。TSDEC算法首先用奇異值分解[14]對(duì)正則化處理后的類(lèi)間散度矩陣進(jìn)行降維處理，初次降維后的樣本數(shù)據(jù)的維數(shù)最大可以降到(c-1)維；然后，在低維嵌入子空間中利用基于最大間距準(zhǔn)則的子空間學(xué)習(xí)方法，對(duì)降維后的樣本數(shù)據(jù)再次降維；最后，使用KM算法[12]對(duì)兩次降維后的樣本數(shù)據(jù)進(jìn)行聚類(lèi)。通過(guò)兩次對(duì)樣本數(shù)據(jù)降維處理，降低了算法的計(jì)算復(fù)雜度，提高了算法的效率。

X={X1,…,Xj,…,Xc}。

其中Xj表示第j類(lèi)的數(shù)據(jù)樣本矩陣。

聚類(lèi)的類(lèi)內(nèi)緊致性和類(lèi)間分離性可用類(lèi)內(nèi)散度矩陣Sw和類(lèi)間散度矩陣Sb表示，分別定義[15]為

(1)

(2)

通過(guò)對(duì)矩陣Hb作奇異值分解得到[14]

Hb=SΣDT。

其中：S∈m×m,D∈m×m,且S和D都是正交矩陣；Σ∈m×c為半正定對(duì)角陣。Σ1為Σ的前c行c列構(gòu)造的矩陣，對(duì)其正則化[11]得到

(3)

其中Ic為c階單位矩陣。

由式(3)可知，矩陣Σ1引入了正則化參數(shù)λ，避免了矩陣奇異性問(wèn)題，從而可以提高算法對(duì)數(shù)據(jù)的適應(yīng)性。

2 兩階段判別嵌入模糊聚類(lèi)算法

2.1 初始化聚類(lèi)和迭代中的FCM算法

KM[12]算法是一種硬聚類(lèi)算法，得到的是對(duì)數(shù)據(jù)的硬劃分矩陣。這種硬劃分不能準(zhǔn)確地描述數(shù)據(jù)的分布情況。FCM算法[13]是一種軟聚類(lèi)算法，通過(guò)模糊隸屬度矩陣確定每個(gè)數(shù)據(jù)樣本屬于某類(lèi)類(lèi)別的確定性程度。在FCM的聚類(lèi)結(jié)果中，每個(gè)樣本不再屬于確定的類(lèi)別，而是以不同的程度屬于各個(gè)類(lèi)別[16]。

FCM算法的目標(biāo)函數(shù)定義[13]為

(4)

其中：矩陣U={uij}n×c為模糊隸屬度矩陣；M為樣本類(lèi)中心矩陣；b為控制聚類(lèi)結(jié)果模糊程度的參數(shù)，取值大于1；dj表示第j類(lèi)數(shù)據(jù)樣本的均值；uij∈[0,1]表示數(shù)據(jù)樣本xi屬于各個(gè)聚類(lèi)的模糊程度，滿足

用目標(biāo)函數(shù)J對(duì)dj和uij分別求偏導(dǎo)，并令偏導(dǎo)數(shù)為0，可得式(4)最小化的必要條件分別為

(5)

(6)

通過(guò)迭代方法求解式(5)和式(6)，得到式(4)的最優(yōu)目標(biāo)函數(shù)值，具體步驟如下。

輸入數(shù)據(jù)樣本X，控制聚類(lèi)模糊程度的參數(shù)b，聚類(lèi)類(lèi)別數(shù)c，迭代次數(shù)以及閾值δ。

輸出模糊隸屬度矩陣U。

步驟1初始化模糊隸屬度矩陣U0。

步驟2根據(jù)式(5)計(jì)算類(lèi)中心矩陣M。

步驟3根據(jù)式(6)更新隸屬度矩陣U，如果滿足‖U-U0‖<δ，則停止迭代，得到最優(yōu)目標(biāo)函數(shù)值；否則，令U0=U，返回步驟2，重復(fù)迭代。

2.2 TSDEFC算法原理及其步驟

兩階段判別嵌入模糊聚類(lèi)算法在TSDEC算法的基礎(chǔ)上引入FCM算法，對(duì)樣本進(jìn)行初始聚類(lèi)，得到初始的模糊隸屬度矩陣；通過(guò)兩階段降維方法[11]對(duì)數(shù)據(jù)進(jìn)行降維處理；最后在低維嵌入子空間中利用FCM算法對(duì)降維后的數(shù)據(jù)再次進(jìn)行模糊聚類(lèi)，得到最終的模糊隸屬度矩陣，按照最大隸屬度原則確定每個(gè)樣本點(diǎn)的類(lèi)別。

TSDEFC算法具體步驟如下。

輸入數(shù)據(jù)樣本X，聚類(lèi)數(shù)目c，迭代次數(shù)T以及停止閾值ε。

輸出隸屬度矩陣H。

步驟1對(duì)數(shù)據(jù)樣本X進(jìn)行規(guī)范化和中心化處理，并初始化模糊聚類(lèi)得到模糊隸屬度矩陣U0。

步驟2將U0根據(jù)隸屬度最大化原則構(gòu)造矩陣H0。

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

步驟4矩陣Hb作奇異值分解，即

Hb=SΣDT。

步驟8由G=QW得到最優(yōu)變換矩陣。

步驟9利用y=GTx對(duì)數(shù)據(jù)進(jìn)行投影變換，在低維嵌入子空間中使用FCM聚類(lèi)算法對(duì)兩次降維后的數(shù)據(jù)聚類(lèi)，得到模糊聚類(lèi)結(jié)果并更新模糊隸屬度矩陣U。

步驟10根據(jù)模糊集合的最大隸屬度準(zhǔn)則，得到數(shù)據(jù)的隸屬度矩陣H。如果‖H-H0‖<ε，則停止迭代，聚類(lèi)完成；否則，令H0=H，轉(zhuǎn)到步驟3，直至滿足‖H-H0‖<ε為止。

TSDEFC算法是一種軟聚類(lèi)算法，通過(guò)計(jì)算每個(gè)數(shù)據(jù)點(diǎn)隸屬于多個(gè)不同類(lèi)別的模糊程度，充分考慮了每個(gè)樣本點(diǎn)對(duì)聚類(lèi)中心的影響，從而有效地反映數(shù)據(jù)集的真實(shí)分布結(jié)構(gòu)。

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

實(shí)驗(yàn)是在Intel (R) Core 2.5 GHz，4 GB 內(nèi)存的Windows10 系統(tǒng)進(jìn)行。為了驗(yàn)證TSDEFC聚類(lèi)算法能夠更加有效地反映數(shù)據(jù)的真實(shí)結(jié)構(gòu)，在不同的模糊參數(shù)條件下，選取UCI數(shù)據(jù)庫(kù)[17]中的Brain、Leukemia、Control、Satimage和Colon 及基因表達(dá)數(shù)據(jù)集Global Cancer Map(GCM)[18]等6個(gè)數(shù)據(jù)集，分別對(duì)比TSDEFC算法與TSDEC算法、DEC算法、KM算法以及FCM算法的聚類(lèi)精度和魯棒性。6個(gè)數(shù)據(jù)集的相關(guān)特性如表1所示。

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

3.1 聚類(lèi)精度測(cè)試

6個(gè)數(shù)據(jù)集的平衡參數(shù)η取值為2，正則化參數(shù)λ取值為10-6。b1表示初始化FCM算法中的模糊參數(shù)，b2表示在低維子空間中執(zhí)行FCM聚類(lèi)過(guò)程的模糊參數(shù)。為使實(shí)驗(yàn)結(jié)果便于分析，令b1=b2，兩參數(shù)所取值的集合為{1.1，1.2，1.3，1.4，1.5，1.6，1.7，1.8，1.9，2.0，2.1，2.2，2.3，2.4，2.5，2.6，2.7，2.8，2.9，3.0}。當(dāng)模糊參數(shù)取不同的值時(shí)，5種算法運(yùn)行10次后取其平均值作為最終結(jié)果，最大迭代次數(shù)設(shè)置為100，停止閾值ε設(shè)置為10-5。6個(gè)數(shù)據(jù)集的聚類(lèi)精度的趨勢(shì)分別如圖1至圖6所示。

圖1 對(duì)Brain的聚類(lèi)結(jié)果對(duì)比

圖2 對(duì)Leukemia的聚類(lèi)結(jié)果對(duì)比 圖3 對(duì)Control的聚類(lèi)結(jié)果對(duì)比

圖4 對(duì)Satimage的聚類(lèi)結(jié)果對(duì)比

圖5 對(duì)Colon的聚類(lèi)結(jié)果對(duì)比 圖6 對(duì)GCM的聚類(lèi)結(jié)果對(duì)比

由圖1至圖6的聚類(lèi)結(jié)果可以看出，TSDEC算法、DEC算法和KM算法是硬聚類(lèi)算法，與模糊參數(shù)無(wú)關(guān)，因此對(duì)應(yīng)的聚類(lèi)精度是一條直線。而FCM算法和TSDEFC算法的聚類(lèi)精度隨模糊參數(shù)的取值的不同而變化。在大多數(shù)模糊參數(shù)取值下，TSDEFC算法的聚類(lèi)精度優(yōu)于其他4種算法，當(dāng)模糊參數(shù)越趨近于1時(shí)，聚類(lèi)精度越接近于TSDEC的聚類(lèi)精度。

在處理高維數(shù)據(jù)時(shí)，DEC算法在高維數(shù)據(jù)集Leukemia和GCM上溢出，無(wú)法得到聚類(lèi)精度。從圖5和圖6可以看出，TSDEFC算法對(duì)于數(shù)據(jù)集Colon和GCM的聚類(lèi)精度明顯優(yōu)于TSDEC算法、DEC算法和FCM算法。

TSDEFC算法、TSDEC算法、DEC算法、KM算法和FCM算法在不同模糊參數(shù)下獲得的最優(yōu)聚類(lèi)精度如表2所示。其中，“—”表示DEC算法無(wú)法得到關(guān)于高維數(shù)據(jù)集Leukemia和GCM的聚類(lèi)精度。

表2 5種算法對(duì)6個(gè)數(shù)據(jù)集的聚類(lèi)最優(yōu)精度對(duì)比

由表2可以看出， TSDEFC算法的最優(yōu)聚類(lèi)精度高于其他4種算法。

3.2 魯棒性測(cè)試

利用GCM和Brain兩個(gè)高維數(shù)據(jù)測(cè)試TSDEFC算法對(duì)數(shù)據(jù)初始化的魯棒性。使用KM算法隨機(jī)初始化10次所得的隸屬度矩陣作為FCM算法、DEC算法、TSDEC算法和TSDEFC算法的初始隸屬度矩陣。5種算法對(duì)GCM和Brain數(shù)據(jù)集10次運(yùn)行的結(jié)果分別如圖7和8所示，其中FCM和TSDEFC中的模糊參數(shù)b分別取值2和1.3。DEC算法在對(duì)數(shù)據(jù)集GCM聚類(lèi)時(shí)內(nèi)存溢出，無(wú)法獲得最終的聚類(lèi)精度。

圖7 對(duì)GCM運(yùn)行10次的聚類(lèi)精度對(duì)比

圖8 對(duì)Brain運(yùn)行10次的聚類(lèi)精度對(duì)比

由圖7和圖8的聚類(lèi)結(jié)果可知，對(duì)于不同的數(shù)據(jù)集，TSDEFC算法和FCM算法的聚類(lèi)精度均超過(guò)了KM算法。TSDEFC算法在10次運(yùn)行中具有比TSDEC算法更優(yōu)或相同的聚類(lèi)精度。由于初始隸屬度矩陣是隨機(jī)選擇的，表明選取合適的模糊參數(shù)，TSDEFC算法相對(duì)于TSDEC算法具有更優(yōu)的對(duì)初始化的魯棒性。

4 結(jié)語(yǔ)

TSDEFC算法利用兩階段降維方法對(duì)數(shù)據(jù)降維處理，降低了算法的復(fù)雜度。采用FCM算法代替TSDEC算法中的KM算法，對(duì)數(shù)據(jù)模糊化聚類(lèi)，求得每個(gè)數(shù)據(jù)點(diǎn)屬于多個(gè)聚類(lèi)的確定性程度，充分考慮每個(gè)數(shù)據(jù)點(diǎn)對(duì)聚類(lèi)中心的不同貢獻(xiàn)。實(shí)驗(yàn)結(jié)果表明，在多個(gè)模糊參數(shù)取值下，TSDEFC算法的聚類(lèi)精度要高于FCM算法，且其聚類(lèi)精度也優(yōu)于硬聚類(lèi)版本的TSDEC算法、DEC算法以及KM算法。尤其對(duì)高維數(shù)據(jù)聚類(lèi)時(shí)，TSDEFC算法的聚類(lèi)精度優(yōu)于TSDEC算法、DEC算法及FCM算法，且TSDEFC算法相對(duì)于硬聚類(lèi)版本的算法有更優(yōu)的對(duì)初始化的魯棒性。