基于譜聚類和L2，1范數的多視圖聚類算法*

賀 娜 馬盈倉 張 丹 續秋霞

（西安工程大學理學院 西安 710600）

1 引言

聚類分析是把一個數據樣本集劃分為多個簇的過程，應用到許多領域，包括圖像模式識別、商務智能和生物學等。通常來說，對于每個樣本，可以對其從不同的視圖進行描述，并且綜合多個視圖的信息有利于得到更好的聚類結果。處理這一問題的方法一般分為基于圖的方法［1～3］、矩陣分解方法［4～6］、基于多重核的方法［7～9］和基于子空間學習的方法［10～11］。特別是基于圖的方法，因其具有挖掘非線性結構信息的能力，在聚類精度方面通常優于其他方法。

經典的譜聚類算法是一種重要的基于圖論的聚類算法［12］，不僅可以在任意樣本空間進行聚類，而且可以收斂到全局最優［13］。但是，該算法也存在一些問題，因譜聚類的最終結果完全依賴于開始構造的相似矩陣，然而不同的構造方法會影響聚類結果，因此構造理想的相似矩陣成為了一個問題［14］。

近年來，許多學者對譜聚類算法中相似矩陣的構造方法做了進一步研究與改進。Shi等通過高斯核函數構造相似矩陣［15］；Ng等提出NJW（Ng-Jor?dan-Weiss）算法通過高斯核函數構造相似矩陣，采用全連接構造方法［16］；Zhang等利用兩個樣本數據點之間的局部密度求得相似矩陣［17］；Nie等通過基于局部連通性為每個數據點分配自適應和最優鄰居來學習相似矩陣［18］；Xie等采用樣本點與樣本點的近鄰點兩者的歐式距離作為局部標準差構造相似矩陣［19］；Nataliani等利用數據點的相關性估計冪參數構造冪高斯核函數來求解相似矩陣［20］。然而這些文獻中構造的相似矩陣都是固定的，不能很好地挖掘和利用數據結構。

為了更好地挖掘和利用數據，近年來發展起來的多視圖學習，在學習過程中充分利用多視圖數據之間的互補信息和關聯信息，使最終的學習結果在各視圖上趨于一致的機器學習算法。本文將多視圖學習引入譜聚類過程，提出了基于譜聚類和L2，1范數的多視圖聚類算法（Multi-view clustering algo?rithm based on spectral clustering andL2，1norm）。將改進的多視圖親和矩陣利用L2，1范數正則項合理地構造出相似矩陣S，同時進行譜聚類過程，F與S交替迭代更新，最后對F進行聚類。該算法不僅可以更好地反映數據的流行結構，而且可以得到更加穩定的聚類結果。

2 相關工作

2.1 多視圖相似矩陣的構造

為了充分利用多視圖數據之間的互補信息和關聯信息，本文將不同視角下的親和矩陣通過相加的方式，融合為一個全局親和矩陣A?，即（v為視圖的個數），由于學習的相似矩陣S與全局親和矩陣A?存在距離，為了得到更好的結果，進一步對相似矩陣進行稀疏化處理，通過L2，1范數的魯棒性學習得到一個最理想的相似矩陣S，表示如下：

其中：我們限制相似矩陣S的每一行和等于1，使其具有仿射性，有利于后期的計算處理。

由于使用L2范數的平方作為損失函數對較大的異常值比較敏感，對較小的異常值不敏感；使用L1范數作為損失函數對較大的異常值不敏感，對較小的異常值比較敏感。然而L2，1范數［21］不僅綜合了L2范數和L1范數的魯棒性優點，還減少了異常值的影響，并保持了適當的稀疏性。

2.2 譜聚類中引入多視圖學習的合理性

在2.1小節中，我們介紹了多視圖相似矩陣的構造保留了各個視圖攜帶的信息，在學習過程中充分利用多視圖數據之間的互補信息和關聯信息，使最終的學習結果在各視圖上趨于一致，構造了一個合理的相似矩陣，本節為了說明在譜聚類中引入多視圖學習的重要性，設計了如下實驗。

我們將經典的單視圖譜聚類算法（即將譜聚類算法在每個視圖上分別執行）與2.1小節中構造的多視圖相似矩陣的算法在數據集ALOI（具體介紹見4.1小節）上構造相似矩陣，參數k均為10，并通過影像圖展示，如圖1所示。所測試的多視圖數據集ALOI有4個視圖，即X={X(1)，X(2)，X(3)，X(4)}∈Rn×dv，分 別 為X(1)∈R64×1079，X(2)∈R64×1079，X(3)∈R77×1079，X(4)∈R13×1079。

圖1 ALOI數據集上生成的相似矩陣影像圖

在圖1（a）～（d）為在每個視圖上分別執行譜聚類算法得出的相似矩陣影像圖，圖（a）為視圖1相似矩陣影像圖，（b）為視圖2相似矩陣影像圖，（c）為視圖3相似矩陣影像圖，（d）為視圖4相似矩陣影像圖，（e）為2.1小節構造的多視圖相似矩陣生成算法得出的相似矩陣影像圖。我們可以看到，經典的單視圖譜聚類算法在視圖1和視圖2的時候，還可以構造出較為合理的相似矩陣，但是在視圖3和視圖4時，結果很不理想，特別是對視圖4構造相似矩陣時，表現出很不好的結果。而相比經典的單視圖譜聚類算法，圖（e）可以很明顯地看到，多視圖學習方法可以構造出比圖（a）～（d）更合理的相似矩陣，比單視圖譜聚類算法更加穩定。

由此可以得出，在譜聚類算法中引入多視圖學習方法，可以構造出更合理的相似矩陣，證明了多視圖學習的優越性和有效性，有利于提高聚類精度。

3 模型的建立及求解

3.1 模型建立

在2.1小節中，構造了理想的相似矩陣，接著，在譜聚類的過程中引入多視圖學習，同時進行相似矩陣的學習和譜聚類過程，建立目標函數為

3.2 模型求解

對于上述目標函數式（2），我們通過迭代交替優化方法來求解。

1）固定S，問題（2）可以轉化為

最優解F由Ls前c個最小的特征值所對應的c個特征向量構成。

2）固定F，對于式（2），根據文獻［22］，已知存在fi∈Rc×1，則下式成立：

由于式（2）對于不同i是獨立的，因此我們可以分別對每個i求解如下問題：

其中：D為對角矩陣，主對角元素dii=1/

根據拉格朗日乘子法，得

對si求偏導，令其等于0，可得

對si的第j個元素，有

根據KKT條件，得

其中(v)+=max(0，v)，定義η下述函數為

注意上式，gi(η)是一個分段單調遞增函數，可以很容易地用牛頓迭代法求解。

3.3 算法流程

MVSC-L2，1算法流程如下所示。

3.4 收斂性證明

引理1［21］對于任意非零向量x，y∈Rc，有以下不等式成立

聯合本文的目標函數，給出如下定理：

定理1目標函數

在固定F時，交替迭代優化S的過程中，目標函數值逐步減小。

證明：令更新后的si為sdow i，上一次的si為，通過式（5）只是式（6）的一個解，而是式（2）的最小解，所以根據式（2）有

因為

所以

由引理1知道：

將式（17）和式（18）相加得

由L2，1范數［21］的定義可得：

因此該算法收斂。

4 實驗

在這一節，將根據三個評價指標［23］來評估我們的結果：聚類精度（ACC），純度（purity），標準化互信息（NMI），對MVSC-L2，1進行評價。

4.1 數據集

3-Sources［24］該數據集包含294篇新聞文章，涵蓋六個標簽：商業、娛樂、健康、政治、體育和技術。第一視圖有3068個特征，第二視圖有3631個特征，第三視圖有3560個特征（http：//mlg.ucd.ie/datasets/3sources.html）。

Caltech-101（7）圖像數據集有101個類別的圖像［25］。我們選取了廣泛使用的7個類，得到了1474張［26］圖像。這七種類別分別是面孔、摩托車、美鈔、加菲貓、停車標志和溫莎椅。每幅圖像由六個特征描述。

Extended Yale-B是由三種視圖描述的人臉圖像數據集。綜上所述，這個數據集中有38個不同的人臉圖像被試。我們選擇前10個被試進行多視圖聚類，每個被試65張圖像（http：//cvc.yale.edu/projects/yalefaces/yalefaces.html）。

ALOI包含1000個對象的110，250張圖像，每個對象大約有100張圖像。該算法提取了10個對象的1079張圖像，包括RGB顏色直方圖，HSV顏色直方圖，顏色相似度，Haralick特征的4個視圖。表1給出了上述四個數據集的簡要說明。

表1 數據的屬性

4.2 評價指標

使用三個評價指標［23］來評估我們的結果：聚類精度（ACC），純度（Purity），標準化互信息（NMI），對于這些廣泛使用的指標，值越大表示集群性能越好。這些指標是通過比較每個樣本獲得的標簽與數據集中提供的真實標簽來計算的。

4.2.1聚類準確率

ACC是反映聚類的精度，定義為

其中n為數據點的個數，τi為第i個樣本點真實的類標簽，ri為學習到的第i個樣本點對應的類標簽。δ(x)，y定義為一個函數，即當x=y時δ(x，y)=1，否則為0；map(ri)是一個映射函數，它將學習到的標簽ri與真實標簽τi進行匹配。ACC的取值范圍為[0，1]，值越靠近1，越好。

4.2.2 純度

Purity是正確類標簽的百分比，定義為

Purity的取值范圍為[0，1]，值越靠近1，越好。

4.2.3 標準互信息

標準化互信息NMI用于表示τi和ri之間的相似程度，定義為

上式中的：ni表示算法中每一類ri(1 ≤i≤c)包含的樣本點的個數以及n?j表示算法中每一類τj(1 ≤j≤c)包含的樣本點的個數；ni，j表示學習到的第i個樣本點對應的類標簽ri和真實的類標簽τj的交集中所包含的樣本點的個數。NMI的取值范圍為[]

0，1，值越靠近1，越好。

4.3 實驗設置

4.3.1 對比算法

將本文提出的算法與其它三種聚類算法進行了比較：分別為SWMC［27］，AMGL［28］，MVGL［29］。比較算法中涉及參數的調整均根據相應文獻作者的建議進行設置并試驗以顯示最優結果，對于所有要求圖的相似度矩陣作為輸入的算法，我們使用文獻［18］中提出的方法來構造每個視圖的相似度矩陣，將k固定為10來驗證它們的性能，原因使它可以避免不同視圖之間的尺度差異，并為每個視圖生成歸一化相似矩陣。

4.3.2 參數設置

本文算法中的參數λ的取值為{0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9，1}。k取 值 為0～15。我們在圖2中描述了不同參數的變化，其中橫坐標表示k的取值，縱坐標表示λ的取值，豎坐標表示聚類準確率ACC，具體的設置在四個數據集（a）3-sources、（b）Extended Yale-B、（c）Caltech-101（7）、（d）ALOI上的k和λ的取值分別為（8，0.9），（8，0.2），（10，0.7），（14，0.6）。

圖2 MVSC-L2，1中參數在數據集（a）3-sources、（b）Extended Yale-B、（c）Caltech-101（7）、（d）ALOI上的變化

4.4 實驗結果

從表2、表3和表4顯示的結果中可以得到，在ACC，Purity和NMI三個評價指標下，首先在數據集3-sources上，我們所提的算法，相比次優的分別提高23.84%、20%、19.6%；在數據集Extended Yale-B上，我們所提的算法，相比次優的分別提高6.77%、7.08%、6.56%；在數據集Caltech-101（7）上，我們所提的算法，相比次優的分別提高0.13%、0.07%、7.43%；在數據集ALOI上，我們所提的算法，相比次優的分別提高8.89%、0.88%、0.52%。綜上，我們的算法MVSC-L2，1的聚類性能明顯高于對比算法，具有良好的聚類效果。

表2 不同算法在各數據集下的ACC比較

表3 不同算法在各數據集下的Purity比較

表4 不同算法在各數據集下的NMI比較

5 結語

本文提出了一種新的多視圖聚類算法MVSC-L2，1，該算法在構造相似矩陣時，采用將各個視圖的信息相加融合的方式，比單視圖算法更優，然后同時進行相似矩陣和譜聚類過程，更新迭代優化S和F，最后對F進行聚類。在多個數據集上的實驗結果表明，該算法可以產生較好的聚類結果。但是由于參數λ是人為選取的，使得該算法有一定的局限性。如何自動確定參數，是下一步的研究方向。