稀疏約束的嵌入式模糊均值聚類算法

王繼奎，楊正國，易紀(jì)海，劉學(xué)文，王會勇，聶飛平

(1.蘭州財(cái)經(jīng)大學(xué) 信息工程學(xué)院，甘肅 蘭州 730020；2.桂林電子科技大學(xué) 數(shù)學(xué)和計(jì)算科學(xué)學(xué)院，廣西 桂林 541004；3.西北工業(yè)大學(xué) 光學(xué)影像分析與學(xué)習(xí)中心，陜西 西安 710119)

聚類分析是機(jī)器學(xué)習(xí)領(lǐng)域研究的熱點(diǎn)之一，被廣泛應(yīng)用在圖像識別[1]、文本分析[2-3]和客戶關(guān)系管理[4]等領(lǐng)域中.K-Means[5]是其中最經(jīng)典的聚類算法.K-Means算法聚類速度快，性能好.然而，K-Means計(jì)算出的類簇中心并不是實(shí)際存在的數(shù)據(jù).作為K-Means的替代算法，Kmedoids[6]選擇離計(jì)算出的類簇中心最近的樣本作為類簇中心.盡管K-Means算法計(jì)算速度快，被廣泛使用，但是也具有若干缺點(diǎn)，比如對異常點(diǎn)敏感，魯棒性不強(qiáng)及僅適用于球形分布的數(shù)據(jù)等.為了解決這些問題，研究者們進(jìn)行系列研究[7-12].文獻(xiàn)[13-16]對K-Means算法進(jìn)行擴(kuò)展完成分類屬性數(shù)據(jù)、混合類型數(shù)據(jù)聚類.

K-Means算法屬于硬劃分，在優(yōu)化的過程中容易出現(xiàn)劃分不準(zhǔn)確等問題.為解決這一問題，研究人員提出了模糊均值聚類算法(Fuzzy C-Means,FCM)[17].FCM被廣泛應(yīng)用于各個領(lǐng)域，大大提升了聚類能力.然而FCM算法仍然具有對異常點(diǎn)敏感，魯棒性不強(qiáng)，僅適用于球形分布的數(shù)據(jù)等問題.研究人員在FCM算法的基礎(chǔ)上，又提出了Kernel based FCM[18]、Multivariate FCM、Modified probabilistic FCM[19]、Conditional spatial FCM[20]、Generalized entropy-based physicalistic FCM[21]等算法.

隨著科技的發(fā)展，高維數(shù)據(jù)不斷涌現(xiàn).機(jī)器學(xué)習(xí)算法在面對高維數(shù)據(jù)時(shí)，產(chǎn)生了維度災(zāi)難問題，比如計(jì)算復(fù)雜度高.在許多場合，盡管數(shù)據(jù)的維度很高，但是有意義的數(shù)據(jù)分布往往嵌入在某個低維子空間中.降維技術(shù)不僅能使高維數(shù)據(jù)更好地被理解或者可視化，而且可以很好地解決機(jī)器學(xué)習(xí)算法在面臨數(shù)據(jù)維度高時(shí)產(chǎn)生的諸多問題.降維技術(shù)主要包括無監(jiān)督降維、半監(jiān)督降維和有監(jiān)督降維等類別.主成分分析(Principal Component Analysis,PCA)與局部保留投影(Local Preserving Projection,LPP)[22]是兩個常用的無監(jiān)督線性降維方法.針對線性降維技術(shù)不適用于流形數(shù)據(jù)的問題，研究人員又提出了許多非線性的降維技術(shù)，比如locally linear embedding[23-24]、Isomap[25]及Laplacian Eigenmap[26]等.這些非線性的降維方法計(jì)算復(fù)雜度高，不適用于數(shù)據(jù)規(guī)模大的數(shù)據(jù)集，而且處理新增數(shù)據(jù)不方便.這些問題限制了非線性降維方法的實(shí)際應(yīng)用.

面對高維數(shù)據(jù)聚類，傳統(tǒng)的策略是先利用降維技術(shù)將高維數(shù)據(jù)轉(zhuǎn)變?yōu)榈途S數(shù)據(jù)，然后用一個具體的聚類算法完成聚類.兩階段的策略將降維過程與隨后的聚類過程分開.目前也有一些研究從多視圖的角度進(jìn)行高維數(shù)據(jù)的聚類，取得了不錯的效果[27-28].如何將降維過程與降維后的聚類過程融為一體，建立統(tǒng)一的優(yōu)化模型成為新的研究思路.在此想法的基礎(chǔ)上，我們將經(jīng)典的線性降維技術(shù)與FCM算法統(tǒng)一在一個模型中，提出了一種稀疏約束的嵌入式模糊均值聚類算法(Embedded Fuzzy c-means with Sparsity Constraint,EFSC).本文主要完成了以下工作:(1) 提出了將線性降維與模糊聚類算法統(tǒng)一的聚類算法EFSC；(2) 將稀疏約束施加在模糊矩陣上，提高了EFSC算法的聚類性能；(3) 提出了一種有效的迭代優(yōu)化算法完成模型優(yōu)化；(4) 對EFSC聚類模型的時(shí)間復(fù)雜度進(jìn)行分析，分析表明EFSC具有輸入數(shù)據(jù)規(guī)模的線性時(shí)間復(fù)雜度；(5) 在基準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明與經(jīng)典的聚類算法相比，EFSC算法具有更高的準(zhǔn)確度，驗(yàn)證了EFSC算法的有效性.

1 相關(guān)工作

在聚類分析和數(shù)據(jù)降維方面，研究者們進(jìn)行了大量卓有成效的研究.其中線性降維是最常用的降維技術(shù)，模糊聚類是很有效的聚類算法.下面對這兩種經(jīng)典算法進(jìn)行介紹.

1.1 線性降維

給定數(shù)據(jù)集X=[x1,x2,…,xn]，X∈d×n表示數(shù)據(jù)集，xi∈d×1表示一個數(shù)據(jù)，d表示數(shù)據(jù)的維度，n表示數(shù)據(jù)的個數(shù).線性降維的目的是尋找一個投影矩陣W∈Rd×d′將數(shù)據(jù)X投影到d′維度子空間，其中，d′?d.在眾多的線性降維算法中，PCA和LPP是兩個常用的算法.PCA使降維后的數(shù)據(jù)方差最大化，而LPP則使得降維前后的數(shù)據(jù)近鄰關(guān)系得到保持.然而，目前的線性降維算法僅利用了數(shù)據(jù)本身的信息，沒有利用數(shù)據(jù)的分布信息.比如，不同類別間的數(shù)據(jù)靠得很近，而相同類別內(nèi)的數(shù)據(jù)較為分散的時(shí)候，PCA效果不佳，容易將不同類別的數(shù)據(jù)投影在相近的空間中，不利于降維后的聚類.

1.2 模糊聚類

模糊聚類是在k均值聚類的基礎(chǔ)上發(fā)展出來的一種算法.其目標(biāo)函數(shù)如下:

(1)

式(1)中：M∈d×c表示類簇中心；mk∈d×1表示第k個中心；α∈n×c表示模糊矩陣；αi∈1×c表示模糊矩陣α的第i行，1c=[1,1,…,1]T表示維度為c，元素全為1的向量；αi1c=1表示模糊矩陣α的每一行和為1；αik表示樣本xi對類簇中心mk的模糊系數(shù)；γ>1表示模糊指數(shù)，當(dāng)γ=1，F(xiàn)CM等價(jià)于K-Means.通過迭代算法可以求出最優(yōu)的模糊矩陣α，類簇中心矩陣M.通過調(diào)整γ的取值，F(xiàn)CM可以取得比K-Means更好的聚類效果.然而，F(xiàn)CM與K-Means同樣僅適用于球形數(shù)據(jù)且對異常點(diǎn)敏感、算法魯棒性差.

2 EFSC-稀疏約束的嵌入式模糊均值聚類算法

傳統(tǒng)的高維數(shù)據(jù)聚類往往采用兩階段的策略.先利用某個降維技術(shù)將數(shù)據(jù)降到指定的維度，然后執(zhí)行一個具體的聚類算法完成聚類.一個新的研究思路是將降維過程與聚類過程合二為一，使降維過程與聚類過程互相監(jiān)督.

2.1 模型提出

我們的目的是創(chuàng)建一個模型將投影矩陣嵌入在聚類模型中，將投影矩陣、類簇中心和模糊矩陣一起優(yōu)化，使降維過程與聚類過程合二為一.為此，我們提出了以下模型:

(2)

模型(2)與(1)的區(qū)別在于模型(2)加入了一個投影矩陣W∈Rd×d′.當(dāng)α∈n×c確定后，我們可以學(xué)習(xí)W∈Rd×d′和M∈d′×c，當(dāng)學(xué)習(xí)到最優(yōu)的W和M后，我們可以反過來學(xué)習(xí)最優(yōu)的模糊矩陣α.因?yàn)槟Ｐ?2)采用計(jì)算降維后的樣本點(diǎn)和類簇中心的距離，如果存在若干異常點(diǎn)，則整個模型受異常點(diǎn)的影響較大，類簇中心會向異常點(diǎn)移動，從而偏離了真正的類簇中心.為了解決這一問題，我們進(jìn)一步提出以下模型:

(3)

(4)

其中K表示αi中的非零元素的個數(shù).模型(4)就是我們提出的EFSC算法模型.我們的新模型將線性降維、模糊聚類統(tǒng)一在一起，并且加入了更加魯棒的距離函數(shù)以及模糊矩陣的稀疏約束來提升聚類效果.

2.2 模型求解

我們采用迭代優(yōu)化的方法求解模型(4)，其正確性已經(jīng)由文獻(xiàn)[29]證明.具體來說，在每次迭代過程中固定一組變量，優(yōu)化另一組變量.EFSC算法的每次迭代分以下兩步進(jìn)行:

(1) 固定W、M，優(yōu)化α:當(dāng)W、M固定，模型(4)簡化為:

(5)

其中：

(6)

由于αi的約束發(fā)生在每行，因此問題(5)可以分解為n個獨(dú)立的子問題分別求解，其第i個子問題如下所示:

(7)

根據(jù)拉格朗日乘數(shù)法和KKT(Karush-Kuhn-Tucker)條件得到αik的最優(yōu)解為:

(8)

(2) 固定α，優(yōu)化W、M:當(dāng)α固定，模型(4)簡化為:

(9)

模型(9)難以直接求解.文獻(xiàn)[30]提出了一種新穎的迭代變權(quán)方法可解決此類問題.一種通用的優(yōu)化問題描述為:

(10)

其中：hi(x)為任意凹函數(shù)；x∈C表示x上的任意約束.令h′i(gi(x))表示凹函數(shù)hi在點(diǎn)gi(x)上的任意超梯度.可采用如下迭代變權(quán)優(yōu)化算法解決:

顯然，模型(9)是模型(10)的特例.因而可以用表1所示的迭代變權(quán)法解決.令:

表1 算法1Tab.1 Algorithm 1

(11)

算法1中步驟2求解的模型轉(zhuǎn)化為:

(12)

式(11)、(12)對應(yīng)于算法1中的1、2步，分別完成了超梯度與參數(shù)的更新.文獻(xiàn)[30]提出的迭代變權(quán)算法保證了模型(12)的最優(yōu)解滿足模型(9)的KKT條件，所以模型(12)的最優(yōu)解就是模型(9)的局部最優(yōu)解.模型(12)可進(jìn)一步轉(zhuǎn)化為:

(13)

其中:

(14)

模型(13)的目標(biāo)函數(shù)關(guān)于mk求導(dǎo)并令導(dǎo)數(shù)為0，得:

(15)

由式(15)可求得mk的最優(yōu)解為:

(16)

(17)

為了得到W的最優(yōu)解，我們提出以下引理:

證 令Z=WTX∈d′×n，zi表示Z的第i列，F(xiàn)=WTY∈d′×c，fk表示F的第k列，則

(18)

顯然，式(18)中的第1項(xiàng)和第2項(xiàng)用跡的形式表示為:

(19)

令ei表示第i個規(guī)范向量，可將式(18)中最后一個等號右邊的第3項(xiàng)轉(zhuǎn)化為:

(20)

結(jié)合公式(18)、(19)和(20)得:

則引理1得證.

所以問題(17)中W的最優(yōu)解可由Q最小的d′個特征值對應(yīng)的特征向量給出，通過式(16)求出mk的最優(yōu)解.

通過以上分析，ESFC算法流程由表2列出.

表2 EFSC算法Tab.2 EFSC algorithm

2.3 算法復(fù)雜度分析

令n表示輸入數(shù)據(jù)的規(guī)模，c表示類簇?cái)?shù)，d表示數(shù)據(jù)的維度.EFSC算法在每一次迭代中，計(jì)算fik的時(shí)間復(fù)雜度為O(ndc)；計(jì)算sik的時(shí)間復(fù)雜度為O(nc)；求解W的時(shí)間復(fù)雜度為O(nd2)，計(jì)算mk的時(shí)間復(fù)雜度為O(ndc)；計(jì)算αik的時(shí)間復(fù)雜度為O(ndc).設(shè)迭代次數(shù)為t，d≤n，c≤n，則整個算法的時(shí)間復(fù)雜度為O(max(nd2,ndc)t).由此可見，EFSC算法具有輸入數(shù)據(jù)規(guī)模n的線性時(shí)間復(fù)雜度.

3 實(shí) 驗(yàn)

為了驗(yàn)證EFSC算法的有效性，選擇YALE、UPS、COIL和ORL 4個數(shù)據(jù)集(http:∥www.cad.zju.edu.cn/home/dengcai/Data/data.html)進(jìn)行實(shí)驗(yàn)，在實(shí)驗(yàn)時(shí)先使用PCA將數(shù)據(jù)降到100維.實(shí)驗(yàn)采用常用的準(zhǔn)確度作為度量標(biāo)準(zhǔn)，選擇K-Means、KMedoids、FCM、AKFM[31]、RSFKM[32]和兩階段的PCA+FCM進(jìn)行對比.實(shí)驗(yàn)環(huán)境為Win7操作系統(tǒng)、2.7GHz AMD A12-9800B R7 CPU、Matlab2012a.

3.1 參數(shù)設(shè)置

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

在實(shí)驗(yàn)過程中所有算法的類簇?cái)?shù)c由真值給出.K-Means、KMedoids、FCM、AKFM和RSKM算法各運(yùn)行20次，計(jì)算聚類準(zhǔn)確度的均值和方差.PCA+FCM兩階段方法和EFSC各運(yùn)行20次，記錄每一維度的最優(yōu)結(jié)果，并計(jì)算所有維度最優(yōu)聚類準(zhǔn)確度的均值和方差.實(shí)驗(yàn)結(jié)果如表3所示.

表3 各算法在YALE、UPS、COIL和ORL數(shù)據(jù)集上的準(zhǔn)確度比較Tab.3 Comparison results on YALE,UPS,COIL and ORL datasets in term of accuracy

從表3可以看出EFSC在全部4個基準(zhǔn)數(shù)據(jù)集上都取得了最好的聚類效果.K-Means、Kmedoids在全部4個基準(zhǔn)數(shù)據(jù)集上準(zhǔn)確度接近，表明這兩個算法本質(zhì)上非常接近.AKFM和RSKM算法在YALE、UPS、COIL和ORL的準(zhǔn)確度明顯高于K-Means、Kmedoids算法，表明引入模糊性和魯棒的距離函數(shù)可提升聚類的性能.PCA+FCM兩階段策略的聚類準(zhǔn)確度僅次于EFSC算法，這表明高維數(shù)據(jù)的本質(zhì)結(jié)構(gòu)通常嵌入在低維空間中.EFSC算法同時(shí)進(jìn)行降維和聚類，聚類效果明顯好于傳統(tǒng)的先降維后聚類的兩階段方法PCA+FCM.在YALE、UPS、COIL和ORL 4個數(shù)據(jù)集上，EFSC算法比PCA+FCM兩階段方法的聚類準(zhǔn)確度分別提升了1.71%、0.40%、2.60%和14.52%.

3.3 參數(shù)敏感性分析

(1) 維度對聚類準(zhǔn)確度的影響

高維數(shù)據(jù)集的本質(zhì)類簇結(jié)構(gòu)往往存在于某個較低維的子空間中.我們在γ=1.1，K=c的條件下進(jìn)行實(shí)驗(yàn)，檢驗(yàn)不同的維度對聚類準(zhǔn)確度的影響.實(shí)驗(yàn)結(jié)果如圖1所示.從圖1可以看出，聚類準(zhǔn)確度在不同的維度取得不同的值，在維度較低時(shí)，聚類準(zhǔn)確度較低；當(dāng)維度d→100時(shí)，取得最高的聚類準(zhǔn)確度.實(shí)驗(yàn)結(jié)果表明一方面高維數(shù)據(jù)的最優(yōu)類簇結(jié)構(gòu)存在于較低維的空間中，另一方面也表明對于圖像數(shù)據(jù)經(jīng)過PCA降到100維后，難以使用很低的維度描述其本質(zhì)類簇結(jié)構(gòu).

(2) 模糊指數(shù)對聚類準(zhǔn)確度的影響

模糊指數(shù)的不同取值會改變聚類中心的分布，從而改變聚類效果，模糊指數(shù)選擇對于基于FCM的系列算法性能有決定性影響.不同的數(shù)據(jù)集往往對應(yīng)著不同的最佳模糊指數(shù).我們在K=c，d=98，γ∈[1,3]，步長為0.1的條件下對EFSC算法進(jìn)行實(shí)驗(yàn)，檢驗(yàn)不同的模糊指數(shù)取值對聚類準(zhǔn)確度的影響實(shí)驗(yàn)結(jié)果，如圖2所示.圖2表明，在γ→1時(shí)候，EFSC取得了最高的聚類準(zhǔn)確度，γ值的變化對不同數(shù)據(jù)集的聚類結(jié)果影響巨大.總體來說，隨著γ的增加，聚類準(zhǔn)確度存在降低的趨勢.

(3) 稀疏約束對聚類準(zhǔn)確度的影響

實(shí)驗(yàn)經(jīng)驗(yàn)表明，權(quán)重矩陣的稀疏約束往往可以獲得更好的聚類效果.我們在γ=1.1，d=98，K∈[1,c]步長為1的條件下進(jìn)行實(shí)驗(yàn)，檢驗(yàn)不同的稀疏約束對聚類準(zhǔn)確的影響.實(shí)驗(yàn)結(jié)果如圖3所示.從圖3可以看出K的取值對聚類準(zhǔn)確度的影響不大，并且沒有明顯的相關(guān)性.但是，當(dāng)K取得合適的值時(shí)，EFSC算法取得最高的聚類準(zhǔn)確度.比如對YALE數(shù)據(jù)集，當(dāng)K=3時(shí)，取得最優(yōu)的聚類準(zhǔn)確度50.30%；對于UPS數(shù)據(jù)集當(dāng)K=4時(shí)，EFSC取得最高的聚類準(zhǔn)確度70.98%；對于COIL數(shù)據(jù)集，當(dāng)K=2取得最高的聚類準(zhǔn)確度68.61%；對于ORL數(shù)據(jù)集，當(dāng)K=28時(shí)，取得最高的聚類準(zhǔn)確度79.25%.對于不同數(shù)據(jù)集，稀疏約束K的取值各不同，需在實(shí)踐中調(diào)整K的取值，以使EFSC具有最佳的聚類效果.

3.4 收斂曲線

我們將EFSC算法在不同的數(shù)據(jù)集上運(yùn)行100次，并記錄下每次迭代計(jì)算所得的最優(yōu)值.對所記錄的最優(yōu)值歸一化后繪制在一張圖形上.圖4展示了EFSC算法在YALE、UPS、COIL和ORL數(shù)據(jù)集上的收斂曲線.

從圖4可以看出EFSC算法在YALE、UPS和COIL數(shù)據(jù)集上迭代不到20次就收斂了，在ORL數(shù)據(jù)集上，大約迭代40次就收斂了.所以，EFSC算法收斂的速度很快.圖4中的收斂曲線也驗(yàn)證了EFSC算法的正確性.

4 結(jié) 語

與傳統(tǒng)的高維數(shù)據(jù)聚類采用兩階段算法不同，本文提出了將線性降維和FCM模糊聚類統(tǒng)一的EFSC模型，并給出了一種有效的迭代優(yōu)化算法，交替學(xué)習(xí)投影矩陣W、類簇中心M和模糊矩陣α.在EFSC模型中加入了新的距離計(jì)算函數(shù)，消除了異常點(diǎn)的影響，使得模型更具魯棒性.同時(shí)，我們在模型中加入了對模糊矩陣α的稀疏約束，提升了模型的聚類性能.在基準(zhǔn)測試數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明：與K-Means、Kmedoids、FCM、AKFM、RSKM和PCA+FCM兩階段算法相比，EFSC算法具有更高的聚類準(zhǔn)確度，驗(yàn)證了EFSC算法的有效性.