基于特征選擇與魯棒圖學習的多視圖聚類

黃奕軒，杜世強，，余瑤，肖慶江，宋金梅

（1.西北民族大學 數學與計算機科學學院，蘭州 730030；2.西北民族大學 中國民族信息技術研究院，蘭州 730030）

0 概述

隨著數據收集和存儲能力的提高，各領域已經積累了豐富的數據資源，快速對這些數據進行處理、分析和分類尤為重要。聚類［1-2］作為處理和分析數據的高效方法之一，已被廣泛應用于機器學習、模式識別和數據挖掘等領域。

由于信息源的多樣性，越來越多的多視圖數據不斷涌入人們的生活，為了對多視圖數據進行分類，一系列多視圖聚類方法相繼被提出。多視圖聚類通過融合多個視圖的互補信息和兼容信息，從而獲得更穩定的聚類性能。其中用于多視圖的譜聚類算法［3-4］和K-means［5-7］算法應用最為廣泛。與K-means聚類相比，譜聚類作為一種基于圖的算法，在檢測數據結構方面有著更強的能力［8］。根據圖構建方式的不同，現有的多視圖聚類方法主要分為兩類：基于自表示的子空間多視圖聚類和基于自適應近鄰圖學習的多視圖聚類。

基于自表示的子空間多視圖聚類算法用剩余其他數據點的線性組合來表示某一數據點，得到的系數矩陣即為圖矩陣，其在濾除噪聲影響的同時獲取了數據樣本的全局結構。文獻［9］對表示矩陣施加低秩約束來捕獲數據樣本的全局結構。潛在嵌入空間的多視圖聚類模型［10］先將各視圖數據映射為共同的表示矩陣，然后再學習全局相似圖進行譜聚類。文獻［11］提出一種基于自適應圖的子空間學習框架，通過同時學習數據的低秩表示和局部結構來獲得子空間的最佳全局表示。多視圖低秩稀疏子空間聚類［12］通過構造所有視圖之間共享的親和矩陣來學習子空間表示。文獻［13］同時對每個視圖的子空間表示進行聚類，為保證不同視圖之間的一致性，模型強制將不同視圖中的數據點分為同一類。文獻［14］在子空間表示學習的基礎上提出主動學習共識子空間的方法。文獻［15］將原始數據映射到低維子空間中，在低維數據中挖掘信息的同時捕獲數據的全局結構和局部結構，從而提高了聚類性能。但是，上述方法忽略了不同視圖的重要性，即信息量較多的視圖和信息量較少的視圖被同等對待，因此會丟失一些重要的信息。

基于自適應近鄰圖學習的多視圖聚類方法具有識別不同視圖的聚類能力，其通過給每個數據點分配一個概率作為另一個數據點的鄰域來構建一個圖，并將學習到的概率作為兩個數據點之間的相似性，可以有效探索數據樣本的局部結構。文獻［16］提出自適應近鄰學習方法，將歐式距離作為度量標準，自適應地構造一個關系矩陣。文獻［17］采用自適應近鄰圖學習方法構造數據樣本的相似矩陣，然后融合相似矩陣進行譜聚類來獲取最終聚類結果。之后，文獻［18］對上述模型又進行了改進，將圖矩陣、圖融合和圖聚類整合到一個框架中，以獲得整體最優解。文獻［19］提出了無參數自適應鄰域構建無向圖的方法降低算法的復雜度。為了解決不同視圖的特征不同這一問題，文獻［20］提出了一個無參數模型，可以自適應地為相似圖分配權重。基于自適應加權的多視圖聚類［21］首先分別學習不同視圖的譜嵌入，然后通過譜旋轉學習到一致的聚類結果。多圖自加權多視圖聚類［22］利用原始數據樣本分別學習多個關系圖，然后采用自加權技術融合多個關系圖得到一個共識圖，但是他們都是從原始數據中學習圖，忽略了噪聲和離群點的影響，無法保證樣本之間的真實相似度。

針對上述問題，本文提出基于特征選擇和魯棒圖學習的多視圖聚類算法FRMC。通過特征選擇學習每個視圖的特征，利用自表示學習從多視圖數據中得到樣本的表示系數。在此基礎上，引入自適應近鄰圖方法在表示系數的基礎上構造魯棒圖矩陣，利用矩陣加權和得到最終的親和圖矩陣用于譜聚類。FRMC 算法將特征選擇、噪聲去除和魯棒圖學習集成在一個框架中，從而獲得整體最優解，通過特征選擇為不同的特征分配不同的權重，通過自適應學習不同視圖的特征，降低高維數據并減少冗余特征，通過自表示學習濾除噪聲和離群點同時獲取數據樣本的全局結構，在自適應近鄰學習構建魯棒圖的同時保持數據樣本的局部結構。

1 相關工作

在本節中，首先引入符號說明，然后分別介紹多視圖子空間聚類算法和自適應近鄰圖學習方法。

1.1 符號說明

為方便起見，用X表示樣本矩陣，X的每一列表示一個樣本。本文算法中的符號說明如表1 所示。

表1 符號說明Table 1 Symbol description

1.2 多視圖子空間聚類

多視圖子空間聚類算法首先從自表示學習框架中學習各視圖表示矩陣，然后利用學習到的表示矩陣構建拉普拉斯矩陣進行譜聚類。模型的一般表示形式如下［23］：

其中：Zv∈Rn×n(v=1，2，…，m)，是自表示矩陣，Z的每一列zi都被認為是樣本xi在X為字典情況下的新表示；第一項R(Xv，Xv Zv)=，表示重構誤差項；α>0 用于平衡正則化項?(·)。

在相似圖B上進行譜聚類可以得到最終的聚類結果，其中：

1.3 自適應近鄰圖學習

其中：Sv是第v個視圖的相似矩陣，通過式（4）自適應學習到的Sv能夠保留數據樣本的局部結構。

2 FRMC 算法

本節提出了基于特征選擇和魯棒圖學習的多視圖聚類算法（FRMC），并給出其目標函數的優化過程。與其他相關算法相比，FRMC 主要有以下3 個特點：1）自適應選擇不同視圖的特征，在數據降維的同時減少了噪聲和冗余特征的影響，并且在自表示矩陣的基礎上能自適應地學習魯棒圖；2）同時捕獲數據樣本的全局結構和局部結構，采用l2，1范數測量樣本噪聲能更準確地揭示數據的真實分布；3）使用一種基于交替方向最小化的算法來優化目標函數。

2.1 目標函數

考慮到原始數據通常包含高度冗余特征，筆者希望充分地利用跨多個視圖的有效特征，使得數據空間結構變得更加清晰。因此，為了更好地揭示多視圖聚類結構，本文將特征選擇技術應用于聚類算法中。文獻［9-15］的研究證明了多視圖子空間聚類算法能有效地減少噪聲的影響，提高算法的魯棒性。因此，本文將特征選擇和魯棒圖學習集成到一個框架中。FRMC 算法的主要計算公式如下：

2.2 目標函數求解

式（5）可以通過交替方向最小化（ADM）策略［25］和增廣拉格朗日乘子法（ALM）來解決。為方便求解Zv，本文引入輔助變量Qv和Jv。相應地，問題式（5）可以表示為：

構造式（6）的拉格朗日函數式為：

其中：μ>0 是懲罰參數；和(v=1，2，…，m)是拉格朗日乘數。為解決問題式（7），通過固定其他變量來最小化L1，迭代地更新每個變量，更新規則如下：

1）更新Pv。固定除Pv以外的其他變量，子問題Pv為：

根據式（4），問題式（8）可以表示為：

構造式（10）的拉格朗日函數式為：

2）更新Zv。固定除Zv以外的其他變量，子問題Zv為：

式（13）是關于Zv的凸函數，對Zv求導并將它置為0，則式（13）的封閉解為：

3）更新Ev。固定除Ev以外的其他變量，子問題Ev為：

引用文獻［26］提出的方法解決上述問題，得到解：

4）更新Jv。固定除Jv以外的其他變量，子問題Jv為：

式（18）也是關于Jv的凸函數，對Jv求導并將其置為0，則式（18）的解為：

5）更新Qv。固定除Qv以外的其他變量，子問題Qv為：

為了簡化符號，暫時忽略視圖數v。式（20）中每個i是獨立的，通過解決以下問題獲得Q的第i行：

通過構造上式的拉格朗日函數式并利用KKT［27］條件得到qi的最優解為：

其中：(·)+=max(·，0)。

6）更新Av。Lv也是Av的函數，固定除Av以外的其他變量，子問題Av為：

式（24）對于每個i是獨立的，因此，對于每個可以分別解決以下問題：

將ai限制為k個非零項，有aik≥0，ai，k+1≤01=1。由上述條件可得：

FRMC 算法詳細迭代更新過程如算法1 所示。

算法1FRMC

輸入多視圖數據Xv=∈?dv×n，參數α、β、γ、μ

輸出聚類結果C

9）對親和圖矩陣A進行譜聚類，得到聚類結果C。

3 實驗與結果分析

將FRMC 算法與其他算法進行比較，驗證其在聚類任務上的有效性，所有實驗均在Matlab 上進行。

3.1 數據集

為了檢驗算法的性能，在6 個公開的標準數據集上進行聚類實驗，每個數據集的具體信息如表2所示。

表2 數據集信息統計Table 2 Information statistics of datasets

1）BBCSport 數據集主要有2 個視圖，包含了來自BBC 體育網站的544 份文件，分別對應于5 個熱門領域發表的體育文章。

2）MSRC-v1數據集由210 張圖像和7 個類別組成，對于1 張圖像有5 個特征向量，包括色矩、GIST、CENT、HOT 和LBP。

3）HW2 數據集由2 000 張圖像組成，10 個類別從0 到9 個數字不等，實驗選擇了76 個字符形狀的傅里葉系數和216 個輪廓相關特征。

4）Scene 數據集有2 688 張圖像，對于每張圖像提取了4 個不同的特征向量，包括512DGIST、432D色矩、256DHOG 和48DLBP。

5）Uci-3view 數據集由10 個類的手寫數字組成，每個類有200 個不同的數字，有2 000 個數據點。

6）ORL 數據集是人臉數據集，由40 個不同的類別組成，每個類別包含10 幅在不同時間、光照、面部表情和面部細節下拍攝的不同圖像。

3.2 對比算法

為驗證算法的有效性，本文簡要介紹7 種對比算法來驗證FRMC 的性能優勢。

1）譜聚類（SC-best）［28］：該算法返回多個視圖中最好的聚類結果。

2）從噪聲數據中學習魯棒圖（RGC）［7］：該算法自適應地消除了原始數據中的噪聲和誤差，從干凈的數據中學習魯棒圖，提高了聚類和半監督分類的性能。

3）基于自適應加權的多視圖聚類（AWP）［18］：該算法將多個不同的譜嵌入集成到一個一致的索引矩陣中。

4）多圖自加權多視圖聚類（SwMC）［19］：該算法通過融合不同的權重圖來構造相似圖，然后利用相似圖構造一個具有明確塊對角結構的拉普拉斯圖。

5）自加權多視圖學習（AMGL）［17］：該算法沒有額外的參數，能夠自動學習每個視圖的最優權值。

6）多視圖低秩稀疏子空間聚類（MLRSSC）［11］：該算法通過構造所有視圖之間共享的親和矩陣來學習聯合子空間表示。

7）一致和特定的多視圖子空間聚類（CSMSC）［12］：該算法是一種新的多視圖子空間聚類方法，將一致性和特異性共同用于子空間表示學習。

在所有的對比算法中，RGC、AWP、SwMC 和AMGL 使用相似矩陣作為算法的輸入，并將圖學習和聚類集成到一個框架中，而MLRSSC 和CSMSC則使用自表示系數矩陣作為算法的輸入，兩個算法都將子空間學習和聚類集成到一個框架中。

3.3 評價指標

本文使用精度（ACC）、歸一化互信息（NMI）、純度（Purity）和調整蘭德指數（ARI）這4 個指標來評估算法的聚類性能，指標值越高，表示算法的聚類性能越好，表3～表8 列出了聚類結果，其中加粗表示最優結果。

表3 BBCSport 數據集上的實驗結果Table 3 Experimental results on BBCSport dataset %

表4 MSRC-v1 數據集上的實驗結果Table 4 Experimental results on MSRC-v1 dataset %

表5 HW2 數據集上的實驗結果Table 5 Experimental results on HW2 dataset %

表6 Scene 數據集上的實驗結果Table 6 Experimental results on Scene dataset %

表7 Uci-3view 數據集上的實驗結果Table 7 Experimental results on Uci-3view dataset %

表8 ORL 數據集上的實驗結果Table 8 Experimental results on ORL dataset %

3.4 實驗結果分析

由表3～表8 可以看出，FRMC 算法在BBCSport、MSRC-v1、HW2 和ORL4 個公共數據集上都取得最佳聚類效果。FRMC 能自適應選擇有用的特征，有效降低冗余特征的影響，通過魯棒自表示學習獲取表示系數，濾除噪聲的同時獲取數據樣本的全局結構，并與自適應圖學習結合，可以更好地增強多視圖聚類結構。此外，魯棒圖矩陣建立在干凈的表示系數矩陣上，可以更好地揭示樣本之間的屬性。FRMC 的優勢具體體現在以下4 個方面：

1）與單視圖聚類算法SC 和RGC 相比，FRMC 在4 種評價指標上聚類性能提高了10～40 個百分點。FRMC 可通過學習數據樣本的全局結構和局部結構更好地利用多視圖信息。

2）單視圖聚類算法RGC 在Scene 數據集上的性能優于SwMC，這是由于RGC 構造魯棒圖矩陣用作算法的新輸入，而SwMC 直接從原始數據中構造相似矩陣，這表明了構造魯棒圖的重要性。FRMC 構造了基于自表示系數矩陣的魯棒圖，更好地提高了聚類性能。

3）與在原始數據上構建圖的AWP、SwMC和AMGL算法相比，FRMC 濾除了原始數據中的噪聲和離群點，表現出更好的聚類性能。

4）與以自表示系數矩陣為輸入的MLRSSC 和CSMSC 算法相比，FRMC 算法表現出更好的聚類性能：ACC 提升1～20 個百分點，NMI 提升1～10 個百分點，純度提升5～20 個百分點，ARI 提升2～28 個百分點。FRMC 通過自適應選擇重要特征增強了聚類結構，證明了數據進行特征選擇的重要性。

綜上所述，與其他相對比算法相比，FRMC 可以顯著提高聚類性能。

3.5 算法復雜度分析

FRMC 的最高計算成本來自式（14）和式（19）。式（14）中的Zv和式（19）的Jv計算復雜度均為O(n3)。以數據集Scene 為例，由于其數據樣本多，計算量大，因此本文利用Woodbury 公式［29］對式（14）和式（19）求逆，將復雜度降至O(dvn2)。因為Zv在迭代過程中沒有更新，所以只需要一次求逆，故FRMC 的總時間復雜度為O(2m(dvn2))。FRMC 的存儲成本主要也來自Zv，由于求解Zv利用了矩陣的求逆運算，因此存儲復雜度為O(n2)。表9 列出了FRMC 算法和7 種對比算法在6 個數據集上運行10 次的平均時間。

表9 各算法在6 個數據集上的運行時間Table 9 Running time of each algorithm on six datasets 單位：s

由表9 可以看出：基于單視圖的SC 算法運行時間少于多視圖聚類算法，但聚類性能遠低于多視圖聚類算法；AMGL 算法在比較算法中運行時間最少，但在所有數據集上聚類性能低于FRMC 算法；與基于圖學習的RGC、AWP、SwMC 和AMGL 算法相比，FRMC 算法運行時間最長，但是聚類性能最好；與基于自表示學習的方法MLRSSC 和CSMSC 相比，除了在Scene 和Uci-3view 數據集上，FRMC 算法均得到了最好聚類效果；此外，FRMC 算法在6 個數據集上的運行時間少于MLRSSC 算法。由表9 可知，雖然提出的基于特征選擇和魯棒圖學習的多視圖聚類算法運行速度不是最快的，但能夠在可接受的時間范圍內達到更好聚類效果。

3.6 收斂性分析

圖1 顯示了FRMC 在BBCSport 數據集上的收斂曲線，可見算法經過30 次迭代后趨于穩定，這說明FRMC 具有較好的收斂性。

圖1 收斂性曲線Fig.1 Convergence curve

3.7 魯棒性分析

利用合成數據集來驗證算法的魯棒性，實驗具體設置參考文獻［16］。實驗使用的合成數據集是一個100×100 的矩陣，由4 個25×25 的塊矩陣對角排列組成，每個塊內的數據表示1 個類中2 個對應點的親和度，親和度數據在0～1 的范圍內隨機生成，而塊外的數據表示噪聲，噪聲數據在0～f的范圍內隨機生成，f可以設置為0.5、0.6 或0.7。任意選取20 個噪聲數據點，并將其值設置為1。

實驗選取了2 種具有代表性的算法來驗證FRMC 的魯棒性，如圖2 所示，圖中展示了數據噪聲為0.6 時的聚類圖，可見FRMC 算法學習到的矩陣的塊結構比其他算法更清晰。因此，FRMC 在捕獲數據空間的不同結構方面表現得更好。

圖2 對塊對角合成數據進行聚類的結果Fig.2 Clustering results on the block diagonal synthetic data

3.8 參數分析和聚類可視化

FRMC 算法有α、β、γ和μ4 個參數。根據低秩表示算法得到α=，γ可以從式（28）中獲得，因此，采用交叉驗證方法來求解參數β和μ。一般來說，通常在［0.001，1 000］范圍內調整參數，經過大量實驗驗證，當β和μ在［0.001，10］的范圍內時，效果相對較好，所以，選擇這個區間來評估算法的聚類性能。其他7 種比較算法則均按照文獻中所推薦的參數范圍進行網格搜索并選取最好的結果。

本文在HW2 數據集上展示FRMC 和3 種不同對算法的聚類可視化結果（彩色效果見《計算機工程》官網HTML 版），同種顏色的數據點代表同一類，如圖3 所示。對比算法中都存在不同類別分離不充分的情況，FRMC 算法使得同類數據點之間的距離相對較小，不同類之間的距離相對較大，能夠有效地將相似對象分組到同一個類別中。

圖3 HW2 數據集上的聚類可視化結果Fig.3 Clustering visualization results on HW2 dataset

4 結束語

本文提出基于特征選擇和魯棒圖學習的多視圖聚類算法FRMC，將樣本的特征選擇、噪聲去除和魯棒圖學習集成到一個框架中，以使模型獲得整體最優值。此外，不僅通過自適應選擇特征和自表示學習減少冗余特征和噪聲的影響，同時還考慮多視圖數據樣本中的全局結構和局部結構。在6 種不同數據集上與7 種聚類算法的實驗結果對比，驗證了FRMC 在揭示樣本類別屬性方面的良好性能。后續將利用二部圖技術降低FRMC 在處理大規模數據集時的計算復雜度，同時針對每個視圖中聚類的多樣性問題，為每個視圖分配適當的權重，進一步提高算法的聚類性能。