基于特征選擇與魯棒圖學(xué)習(xí)的多視圖聚類

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

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

0 概述

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

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

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

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

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

1 相關(guān)工作

在本節(jié)中，首先引入符號說明，然后分別介紹多視圖子空間聚類算法和自適應(yīng)近鄰圖學(xué)習(xí)方法。

1.1 符號說明

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

表1 符號說明Table 1 Symbol description

1.2 多視圖子空間聚類

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

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

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

1.3 自適應(yīng)近鄰圖學(xué)習(xí)

其中：Sv是第v個視圖的相似矩陣，通過式（4）自適應(yīng)學(xué)習(xí)到的Sv能夠保留數(shù)據(jù)樣本的局部結(jié)構(gòu)。

2 FRMC 算法

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

2.1 目標函數(shù)

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

2.2 目標函數(shù)求解

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

構(gòu)造式（6）的拉格朗日函數(shù)式為：

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

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

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

構(gòu)造式（10）的拉格朗日函數(shù)式為：

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

式（13）是關(guān)于Zv的凸函數(shù)，對Zv求導(dǎo)并將它置為0，則式（13）的封閉解為：

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

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

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

式（18）也是關(guān)于Jv的凸函數(shù)，對Jv求導(dǎo)并將其置為0，則式（18）的解為：

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

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

通過構(gòu)造上式的拉格朗日函數(shù)式并利用KKT［27］條件得到qi的最優(yōu)解為：

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

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

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

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

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

算法1FRMC

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

輸出聚類結(jié)果C

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

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

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

3.1 數(shù)據(jù)集

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

表2 數(shù)據(jù)集信息統(tǒng)計Table 2 Information statistics of datasets

1）BBCSport 數(shù)據(jù)集主要有2 個視圖，包含了來自BBC 體育網(wǎng)站的544 份文件，分別對應(yīng)于5 個熱門領(lǐng)域發(fā)表的體育文章。

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

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

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

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

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

3.2 對比算法

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

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

2）從噪聲數(shù)據(jù)中學(xué)習(xí)魯棒圖（RGC）［7］：該算法自適應(yīng)地消除了原始數(shù)據(jù)中的噪聲和誤差，從干凈的數(shù)據(jù)中學(xué)習(xí)魯棒圖，提高了聚類和半監(jiān)督分類的性能。

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

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

5）自加權(quán)多視圖學(xué)習(xí)（AMGL）［17］：該算法沒有額外的參數(shù)，能夠自動學(xué)習(xí)每個視圖的最優(yōu)權(quán)值。

6）多視圖低秩稀疏子空間聚類（MLRSSC）［11］：該算法通過構(gòu)造所有視圖之間共享的親和矩陣來學(xué)習(xí)聯(lián)合子空間表示。

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

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

3.3 評價指標

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

表3 BBCSport 數(shù)據(jù)集上的實驗結(jié)果Table 3 Experimental results on BBCSport dataset %

表4 MSRC-v1 數(shù)據(jù)集上的實驗結(jié)果Table 4 Experimental results on MSRC-v1 dataset %

表5 HW2 數(shù)據(jù)集上的實驗結(jié)果Table 5 Experimental results on HW2 dataset %

表6 Scene 數(shù)據(jù)集上的實驗結(jié)果Table 6 Experimental results on Scene dataset %

表7 Uci-3view 數(shù)據(jù)集上的實驗結(jié)果Table 7 Experimental results on Uci-3view dataset %

表8 ORL 數(shù)據(jù)集上的實驗結(jié)果Table 8 Experimental results on ORL dataset %

3.4 實驗結(jié)果分析

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

1）與單視圖聚類算法SC 和RGC 相比，F(xiàn)RMC 在4 種評價指標上聚類性能提高了10～40 個百分點。FRMC 可通過學(xué)習(xí)數(shù)據(jù)樣本的全局結(jié)構(gòu)和局部結(jié)構(gòu)更好地利用多視圖信息。

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

3）與在原始數(shù)據(jù)上構(gòu)建圖的AWP、SwMC和AMGL算法相比，F(xiàn)RMC 濾除了原始數(shù)據(jù)中的噪聲和離群點，表現(xiàn)出更好的聚類性能。

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

綜上所述，與其他相對比算法相比，F(xiàn)RMC 可以顯著提高聚類性能。

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

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

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

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

3.6 收斂性分析

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

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

3.7 魯棒性分析

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

實驗選取了2 種具有代表性的算法來驗證FRMC 的魯棒性，如圖2 所示，圖中展示了數(shù)據(jù)噪聲為0.6 時的聚類圖，可見FRMC 算法學(xué)習(xí)到的矩陣的塊結(jié)構(gòu)比其他算法更清晰。因此，F(xiàn)RMC 在捕獲數(shù)據(jù)空間的不同結(jié)構(gòu)方面表現(xiàn)得更好。

圖2 對塊對角合成數(shù)據(jù)進行聚類的結(jié)果Fig.2 Clustering results on the block diagonal synthetic data

3.8 參數(shù)分析和聚類可視化

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

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

圖3 HW2 數(shù)據(jù)集上的聚類可視化結(jié)果Fig.3 Clustering visualization results on HW2 dataset

4 結(jié)束語

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