基于圖嵌入的自適應多視降維方法

尹寶才，張超輝，胡永利，孫艷豐，王博岳

（1. 北京工業(yè)大學 信息學部，北京 100124; 2. 北京人工智能研究院，北京 100124）

隨著攝像頭、傳感器以及互聯(lián)網(wǎng)技術的快速發(fā)展，人們能夠越來越便捷地獲取各種各樣的多視數(shù)據(jù)，例如描述人的人臉、筆跡、指紋等特征，描述圖像的顏色、紋理、形狀等特征。多視數(shù)據(jù)能夠更全面的描述目標對象，有益于克服單視數(shù)據(jù)中常見的光照、遮擋等難題，在識別[1]、聚類[2]等多視學習任務中表現(xiàn)出顯著優(yōu)勢。然而，多視數(shù)據(jù)一般維度較高[3]，對其進行向量化表示時容易引發(fā)“維數(shù)災難”問題，給傳統(tǒng)多視學習算法帶來了極大的困難。降維是數(shù)據(jù)挖掘的基礎和熱點問題，在克服“維數(shù)災難”的同時還能挖掘數(shù)據(jù)中的判別信息，但其很難處理多視數(shù)據(jù)。因此，如何對多視數(shù)據(jù)進行有效的降維成為一個亟待解決的問題。

多視降維方法主要分為兩類：有監(jiān)督多視降維方法[4]和無監(jiān)督多視降維方法[5]。有監(jiān)督數(shù)據(jù)降維通過標簽數(shù)據(jù)學習從高維數(shù)據(jù)到低維數(shù)據(jù)的降維模型，并利用該降維模型對新高維數(shù)據(jù)進行降維。然而，互聯(lián)網(wǎng)上大部分數(shù)據(jù)是沒有標簽的，對其進行人工標注不僅效率低下且需要付出高昂的成本，因此無監(jiān)督多視降維方法的研究變得更為重要。無監(jiān)督多視降維方法不使用數(shù)據(jù)的標簽信息，挖掘數(shù)據(jù)間聯(lián)系來學習數(shù)據(jù)的低維表示。截止到目前，針對多視數(shù)據(jù)的無監(jiān)督降維方法的研究，國內(nèi)外都剛剛起步。

典范相關分析(canonical correlation analysis,CCA)及其變體[6-7]是研究多視圖數(shù)據(jù)之間線性相關的一種有效方法。具體地，判別典型相關分析(discriminative CCA, DCCA)[8]結合了CCA和線性判別分析(linear discriminative analysis, LDA)[9]，從不同的角度考慮了同一類別數(shù)據(jù)之間的相關性，以提高低維子空間的判別能力。張量典型相關分析(tensor CCA, TCCA)[10]通過分析不同視圖之間的協(xié)方差張量，將CCA推廣到處理多視數(shù)據(jù)，但是該方法計算成本過高限制了其應用范圍。偏最小二乘(partial least squares, PLS)[11]使用回歸方式將不同視的數(shù)據(jù)映射到公共線性子空間。分布式頻譜嵌入(distributed spectral embedding, DSE)[12]將數(shù)據(jù)平滑地嵌入到低維空間中?；诙嗪藢W習(multiple kernel learning, MKL)[13]的方法將多核學習與圖嵌入結合實現(xiàn)降維任務。多視聯(lián)合降維(multi-view dimensionality co-reduction, MDcR)[14]使用核匹配方法挖掘多個視圖之間的依存關系，從而獲得每視數(shù)據(jù)的低維投影。耦合塊對齊算法(coupled patch alignment, CPA)[15]將樣本和其跨視角下的同類近鄰以及異類近鄰組成局部塊，平衡跨視角類內(nèi)的緊密性與類間的可分離性，并擴展成多維耦合塊對齊，解決了任意數(shù)量視角的共同學習問題。

綜上，現(xiàn)有的多視降維方法存在以下主要缺點：1) 這些方法僅關注不同視數(shù)據(jù)之間的關系，而忽略同視數(shù)據(jù)內(nèi)部的關系；2) 這些方法通常僅考慮降維后的數(shù)據(jù)關系，而忽略原始數(shù)據(jù)的關聯(lián)關系；3) 這些方法通常將不同視數(shù)據(jù)映射到一個公共空間，當不同視原始數(shù)據(jù)的維度不同時降維結果受影響較大。針對這些問題，本文提出的基于圖嵌入的自適應多視降維(MVDR-GE)方法在考慮每視內(nèi)數(shù)據(jù)關聯(lián)性的基礎上，自適應地學習相似矩陣來探索不同視之間數(shù)據(jù)的關聯(lián)關系，獲得各視數(shù)據(jù)的正交投影矩陣實現(xiàn)多視降維任務。

1 相關工作

1.1 圖嵌入降維

通過式(2)可求得高維數(shù)據(jù)X的投影矩陣P∈K×V。

令Z=PX，式(2)可以寫成圖正則化表示：

1.2 自適應局部結構學習

自適應局部結構學習旨在通過度量樣本之間的歐氏距離來自適應地學習樣本間的相似度，從而獲得樣本的局部結構信息。對于每個樣本xi和樣本xj，sij為衡量兩個樣本之間相似性的值。則自適應學習相似性矩陣S可通過下面優(yōu)化問題求得[17]：

盡管sij可以自適應地學習兩個樣本的相似度，但是式(4)不能避免S的對角線為1這種平凡解，故引入正則化約束：

式(5)是面向單視數(shù)據(jù)的自適應局部結構學習的公式，將其擴展到多視數(shù)據(jù)后可得：

2 基于圖嵌入的自適應多視降維

基于模型式(3)的思路，通過多視共享相似性矩陣可以很有效地探索視與視數(shù)據(jù)間的關系，則多視圖嵌入降維模型為

式中P(m)P(m)T=I的目的是避免平凡解。

對式(7)進行分解，則：

式(9)中的相似度矩陣S只關注降維后數(shù)據(jù)關聯(lián)關系，忽略了原始數(shù)據(jù)間的結構關系，從而不能保證降維后的數(shù)據(jù)保留原始數(shù)據(jù)的結構。因此，引入對原始數(shù)據(jù)的約束后，則：

式中 λ1、 λ2和 λ3是平衡各個模塊重要性的參數(shù)。此外，為了避免降維后數(shù)據(jù)丟失信息嚴重，引入約束視內(nèi)數(shù)據(jù)重構誤差項：

3 算法優(yōu)化

目標函數(shù)式(12)是典型非凸優(yōu)化問題，本文通過迭代更新的方法，求解P(m)和S。

3.1 固定 S 更 新P(m)

通過特征值分解得方法，可以求得投影矩陣P(m)并可指定其目標維度。

3.2 固定 P(m)更 新S

當固定投影矩陣P(m)時，重構誤差項不參與更新，目標函數(shù)式(12)變?yōu)?/p>

將式(14)中的低維數(shù)據(jù)和原始數(shù)據(jù)之間的距離設為dij：

則式(14)可簡化為

將式(16)變換為最小二乘形式：

綜上所述，通過不斷的迭代更新，最終得到各視的投影矩陣P(m)，實現(xiàn)多視降維任務。

該模型的算法如下：

算法1 基于圖嵌入的自適應多視降維方法（MVDR-GE）。

輸入 多視數(shù)據(jù) {X(1),X(2),···,X(M)}；每視維度降至 {K(1),K(2),···,K(M)} ；參數(shù)λ1、λ2和λ3。

2) 當不滿足收斂條件時：

Form=1：M

根據(jù)式（13）計算各式投影矩陣P(m)；

End for

根據(jù)式（17）計算相似度矩陣S；

End

輸出 各視降維矩陣 {P(1),P(2),···,P(M)}。

4 實驗及結果分析

為了驗證本文所提出的多視降維方法的有效性，在多個公開數(shù)據(jù)集上進行了驗證實驗。

4.1 數(shù)據(jù)集描述

IXMAS[18]數(shù)據(jù)集是由5個不同視角拍攝的視頻組成的多視視頻數(shù)據(jù)集，包含10個人的11種日常行為：看手表、抱胳膊、抓頭、坐下、起來、轉(zhuǎn)身、走、揮手、拳擊、踢、撿。本文為每個視角提取177維視頻特征。

ORL數(shù)據(jù)集由40個人、每人10幅不同的人臉照片構成。每個人拍攝照片的時間不同，光照和面部表情不同，本文調(diào)整圖像大小為64×64，并提取圖像的光照強度(intensity)、局部二值模式(local binary pattern, LBP)[19]和Gabor[19]特征構造多視數(shù)據(jù)，維度分別是4 096、3 304和6 750。

PIE數(shù)據(jù)集包含從68個人中采集的共1 428張人臉圖像，該數(shù)據(jù)集提取特征的方法跟ORL數(shù)據(jù)集相同。

MSRCV1[21]數(shù)據(jù)集包含240張圖片，這些圖片屬于9個類別，本文實驗選取其中的樹、建筑物、飛機、牛、人臉、汽車和自行車等7個類別共210張圖片。分別提取每張圖片的CENT(1 302維)、COLOR(48維)、GIST(512維)、LBP(256維)4種特征作為此數(shù)據(jù)集的多視數(shù)據(jù)。

Notting-Hill[22]諾丁山數(shù)據(jù)集來源于電影《諾丁山》，收集了5個角色的多張人臉照片。本文調(diào)整圖像大小為64×64并提取跟ORL數(shù)據(jù)集相同的特征，維度分別為2 000、3 304和6 750。

4.2 實驗及結果

為了驗證方法的有效性，與以下幾個經(jīng)典降維方法做了實驗結果對比。

主成分分析(principal component analysis,PCA)[23]：該方法是經(jīng)典的無監(jiān)督線性降維方法，通過將原始數(shù)據(jù)投影到線性子空間中對數(shù)據(jù)進行降維。

樸素多視降維(naive multi-view dimension reduction, NaMDR)[14]：此方法獨立地減小了每個視圖的維度，而沒有約束不同的視圖。

多視聯(lián)合降維(multi-view dimensionality co-reduction, MDcR)[14]：該方法利用核匹配方法挖掘多個視圖之間的依存關系，并獲得每視數(shù)據(jù)的低維投影。

對于不同的數(shù)據(jù)集，特征的維數(shù)也不相同，本文統(tǒng)一將數(shù)據(jù)的目標特征維度設置為10維。為了進一步驗證多視學習的有效性，本文對比了不同單視數(shù)據(jù)的最好性能和多視聯(lián)合的性能，其中不同單視數(shù)據(jù)的最好性能在表格中用single表示，多視聯(lián)合的性能在表格中用multiple表示。具體地說，在得到降維數(shù)據(jù)后，本文進行了聚類/識別實驗從而間接對降維性能進行了評估。全部實驗是在Window 10、64位操作系統(tǒng)、Inter Corei5-6500 3.20 GHz和20 G RAM的工作站上實現(xiàn)的，軟件環(huán)境為Matlab 2018a。

4.2.1 聚類實驗

在聚類實驗中，采用3個評價指標度量聚類性能：準確性(accuracy, ACC)、歸一化互信息(normalized mutual information, NMI)和純度(Purity)。這些指標越高代表聚類表現(xiàn)越好。在獲得不同降維方法的降維數(shù)據(jù)后，本文使用自動加權多圖(auto-weighted multi-view learning, AMGL)[23]聚類方法對其進行聚類。由于此方法最后一步是執(zhí)行K-means操作，所以本文進行30次實驗取均值和標準差作為最終的實驗結果。最后的實驗結果為平均值±標準差的形式。本文在IXMAS、PIE、Notting-Hill 3個數(shù)據(jù)集上進行了聚類實驗，實驗結果如表1～3所示。

本文用加粗的字體表示最好的實驗結果。從表1～3中可以看出，本文提出的多視降維方法無論在單視特征還是多視特征上都取得了最好的聚類表現(xiàn)。其他降維方法在ACC、NMI和Purity指標上，都不能取得一個令人滿意的結果。由于本文提出的多視降維方法利用一個融合多視數(shù)據(jù)相似度的矩陣去輔助生成投影矩陣，使得用投影矩陣和原始數(shù)據(jù)運算得到的每視的低維數(shù)據(jù)能夠融合其他視數(shù)據(jù)的信息，并且本文不同視數(shù)據(jù)的相似度矩陣S是自適應學習得到的，所以在擁有很強的靈活性的同時又能保證多視數(shù)據(jù)相互融合之后的低維數(shù)據(jù)具有代表高維數(shù)據(jù)的判別性信息，最終對多視低維數(shù)據(jù)進行聚類時獲得一個令人滿意的表現(xiàn)。同時，對比單視低維數(shù)據(jù)聚類也能獲得最好的結果，表明本文提出的多視降維方法已經(jīng)很好地融合了多視數(shù)據(jù)。

表1 IXMAS數(shù)據(jù)集聚類實驗結果Table 1 Clustering experiment results of IXMAS dataset

表2 PIE數(shù)據(jù)集聚類實驗結果Table 2 Clustering experiment results of PIE dataset

表3 Notting-Hill數(shù)據(jù)集聚類實驗結果Table 3 Clustering experiment results of Notting-Hill dataset

4.2.2 識別實驗

本文在ORL、Notting-Hill和MSRCV1數(shù)據(jù)集上進行了識別實驗，采用最近鄰分類器作為識別方法，采用識別準確度作為評價指標。由于在Notting-Hill和MSRCV1數(shù)據(jù)集上每類的樣本不相同，本文從每類所有的樣本中選取了M個樣本進行訓練，記作Gm，其余的樣本進行測試。本文實驗設置為隨機選取30次訓練集進行訓練和測試，并報告平均識別結果。最后的實驗結果為平均值±標準差的形式。

實驗結果如表4～6所示，本文提出的方法在絕大多數(shù)情況上獲得了最好的識別效果。由于本文提出的多視降維方法能夠很好地融合多視數(shù)據(jù)的特征，使得降維后的低維數(shù)據(jù)能充分表示高維數(shù)據(jù)且具有更強的判別性，因此本文的方法能在識別實驗中得到一個比較高的準確度，這也驗證了本文的方法相較于其他對比方法，能夠更好地對不同視角數(shù)據(jù)進行融合，使降維后的低維數(shù)據(jù)更有利于進行識別。在ORL人臉數(shù)據(jù)集和Notting-Hill數(shù)據(jù)集上，本文提出的方法雖然在單視數(shù)據(jù)和多視數(shù)據(jù)上均獲得最好的實驗結果，單視實驗結果整體略優(yōu)于多視實驗結果，其他方法也同樣出現(xiàn)了該問題。這一現(xiàn)象的原因在于兩個數(shù)據(jù)集提取的LBP特征能夠很好地反應圖像的特征，在拼接多視數(shù)據(jù)進行識別時，本文選用的識別方法不能很好地融合多視數(shù)據(jù)進行識別。

表4 ORL數(shù)據(jù)集識別實驗結果Table 4 Recognition experiment results of ORL dataset

表5 Notting-Hill數(shù)據(jù)集識別實驗結果Table 5 Recognition experiment results of Notting-Hill dataset

表6 MSRCV1數(shù)據(jù)集識別實驗結果Table 6 Recognition experiment results of MSRCV1 dataset

5 結束語

本文提出了一種基于圖嵌入的自適應多視降維方法。通過圖嵌入的方法能夠?qū)⒏呔S數(shù)據(jù)嵌入到一個低維的子空間，并使得到的低維數(shù)據(jù)能夠具有高維數(shù)據(jù)的特點。通過自適應學習一個多視數(shù)據(jù)共享的相似性矩陣，能夠?qū)Σ煌暤臄?shù)據(jù)在降維的過程中進行融合，使得降維后的每個視之間的數(shù)據(jù)都包含其它視特征的信息。實驗結果證明，本文提出的方法在多視數(shù)據(jù)降維的同時能夠促進多視數(shù)據(jù)的融合，并且能夠提高后續(xù)聚類/識別任務的實驗效果。雖然本文提出的方法能獲得了令人滿意的多視降維表現(xiàn)，但降維過程比較耗時，今后的研究將致力于如何降低算法的復雜度。