王繼奎，楊正國，易紀海，劉學文，王會勇，聶飛平

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

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

K-Means算法屬于硬劃分，在優(yōu)化的過程中容易出現(xiàn)劃分不準確等問題.為解決這一問題，研究人員提出了模糊均值聚類算法(Fuzzy C-Means,FCM)[17].FCM被廣泛應用于各個領域，大大提升了聚類能力.然而FCM算法仍然具有對異常點敏感，魯棒性不強，僅適用于球形分布的數(shù)據(jù)等問題.研究人員在FCM算法的基礎上，又提出了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).機器學習算法在面對高維數(shù)據(jù)時，產(chǎn)生了維度災難問題，比如計算復雜度高.在許多場合，盡管數(shù)據(jù)的維度很高，但是有意義的數(shù)據(jù)分布往往嵌入在某個低維子空間中.降維技術不僅能使高維數(shù)據(jù)更好地被理解或者可視化，而且可以很好地解決機器學習算法在面臨數(shù)據(jù)維度高時產(chǎn)生的諸多問題.降維技術主要包括無監(jiān)督降維、半監(jiān)督降維和有監(jiān)督降維等類別.主成分分析(Principal Component Analysis,PCA)與局部保留投影(Local Preserving Projection,LPP)[22]是兩個常用的無監(jiān)督線性降維方法.針對線性降維技術不適用于流形數(shù)據(jù)的問題，研究人員又提出了許多非線性的降維技術，比如locally linear embedding[23-24]、Isomap[25]及Laplacian Eigenmap[26]等.這些非線性的降維方法計算復雜度高，不適用于數(shù)據(jù)規(guī)模大的數(shù)據(jù)集，而且處理新增數(shù)據(jù)不方便.這些問題限制了非線性降維方法的實際應用.

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

1 相關工作

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

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ù)近鄰關系得到保持.然而，目前的線性降維算法僅利用了數(shù)據(jù)本身的信息，沒有利用數(shù)據(jù)的分布信息.比如，不同類別間的數(shù)據(jù)靠得很近，而相同類別內(nèi)的數(shù)據(jù)較為分散的時候，PCA效果不佳，容易將不同類別的數(shù)據(jù)投影在相近的空間中，不利于降維后的聚類.

1.2 模糊聚類

模糊聚類是在k均值聚類的基礎上發(fā)展出來的一種算法.其目標函數(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ù)，當γ=1，F(xiàn)CM等價于K-Means.通過迭代算法可以求出最優(yōu)的模糊矩陣α，類簇中心矩陣M.通過調(diào)整γ的取值，F(xiàn)CM可以取得比K-Means更好的聚類效果.然而，F(xiàn)CM與K-Means同樣僅適用于球形數(shù)據(jù)且對異常點敏感、算法魯棒性差.

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

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

2.1 模型提出

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

(2)

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

(3)

(4)

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

2.2 模型求解

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

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

(5)

其中：

(6)

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

(7)

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

(8)

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

(9)

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

(10)

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

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

表1 算法1Tab.1 Algorithm 1

(11)

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

(12)

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

(13)

其中:

(14)

模型(13)的目標函數(shù)關于mk求導并令導數(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項和第2項用跡的形式表示為:

(19)

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

(20)

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

則引理1得證.

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

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

表2 EFSC算法Tab.2 EFSC algorithm

2.3 算法復雜度分析

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

3 實 驗

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

3.1 參數(shù)設置

3.2 實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

3.4 收斂曲線

我們將EFSC算法在不同的數(shù)據(jù)集上運行100次，并記錄下每次迭代計算所得的最優(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中的收斂曲線也驗證了EFSC算法的正確性.

4 結(jié) 語

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