基于深度圖正則化矩陣分解的多視圖聚類算法

劉相男，丁世飛，王麗娟,2

（1.中國礦業大學 計算機科學與技術學院，江蘇 徐州 221116; 2.徐州工業職業技術學院 信息與電氣工程學院，江蘇 徐州 221400）

隨著多元化數據的產生與積累，傳統聚類算法只針對于單一視角進行數據的相似性聚類對于現實中的很多數據不再適用。現實社會中，數據集往往從多個數據源收集，或存在不同的表示形式和特征信息構成多視圖數據[1-3]。例如，同一事件通過不同的內容形式播報出來；同一文檔可以翻譯成多種語言；網頁數據可以通過文本或網頁鏈接獲取。相較于單一視角的數據，多視圖數據從多個視角呈現對象，使之特征信息更加完整。那么，如何利用多個視圖的完整信息發現不同視圖間存在的一致的潛在信息成為多視圖聚類算法的目標[4-5]。

近年來，多視圖聚類算法獲得了越來越多的關注和發展。根據多視圖聚類算法的根本機制和原則，多視圖聚類算法主要包括基于K-means的算法、基于矩陣分解的算法、基于圖的算法以及基于子空間的算法[6]。例如，伍國鑫等[7]結合co-training的思想提出了一個改進的多視圖K-means聚類算法。Xu等[8]提出了一種基于K-means處理高維數據的算法，將多視圖聚類和特征選擇集成到一個聯合框架中，選擇合適的視圖和重要的特征聚類。最近提出的FRMVK算法提出使用較小權重消除不相關特征，實現簡化有效特征信息的目的[9]。Nie等[10]開發了一種基于圖的聚類算法，能夠同時學習多視圖聚類和局部結構。之后，Nie等[11]又提出了一種基于圖的多視圖聚類算法，其基礎思想是從一系列低質量的特定視圖中生成一個具備魯棒性的共有圖。Gao等[12]在早期考慮嘗試擴展傳統的基于子空間的多視圖聚類算法，稱為多視圖子空間聚類算法(multi-view subspace clustering, MVSC) 。Zhang等[6]提出可以在隱藏公共空間中進行子空間聚類。針對多個視圖在聚類性能上貢獻度的差異問題，黃靜對每個視圖進行了加權[13]；范瑞東等[14]則采用了更具魯棒性的自加權方式。Zheng等[15]提出使用l2,1范式解決融合的多視圖數據中特定樣本與特定簇之間的關聯性問題，從而獲得多視圖數據的共有信息。

在眾多研究中，非負矩陣分解算法及其擴展算法因其良好的聚類可解釋性而受到越來越多的關注[16]，如何通過非負矩陣分解獲取多視圖數據潛在的數據信息成為熱點研究方向之一[17]。半非負矩陣分解算法(semi-nonnegative matrix factorization, Semi-NMF)是為擴展非負矩陣分解算法(nonnegative matrix factorization, NMF)的應用范圍而提出的算法[18]。考慮到特征表示矩陣與原始數據矩陣之間的映射矩陣存在隱藏的層次結構信息，Trigeorgis等[19]提出一種深度半非負矩陣分解模型，通過逐層分解自動學習數據點的層次屬性。從數據的幾何結構出發，數據點往往是從嵌入在高維環境空間中的低維流形空間中采樣而得[20]，數據的固有幾何結構在矩陣分解中并沒有得到充分的運用。而現有的很多算法證明了圖正則化從樣本的相似性上保護了數據的幾何結構[21]，例如，Zhao等[20]將深度矩陣分解模型應用于多視圖，并在最后一層分解中加入圖正則化，有效提高模型性能。算法MMNMF將共識系數矩陣與多流形正則化相結合，在對數據進行矩陣分解的同時保護數據的局部幾何結構[22]。Zhang等[23]通過圖嵌入增強了有用的信息，并在每個視圖中使用正交約束進行聚類，從而刪除多余信息。

考慮到深度半非負矩陣分解模型和圖正則化各自對于數據的層次屬性和固有幾何結構的作用，同時從保護數據的局部結構和全局結構兩個方面出發，在深度分解模型中，對每一層的特征表示矩陣加入兩個圖正則化限制，從而充分挖掘出數據的層次屬性信息的同時保護數據的固有幾何結構。換言之相較于現有的基于矩陣分解的多視圖聚類算法，本文提出的算法不僅使用了局部結構的相似性而且加入了全局結構的不相似性共同構成圖正則化器，從而更全面的保護和使用數據的幾何結構關系。與此同時，圖正則化器不只作為共識表示矩陣的調節器，同時將其加入每一層分解中，使得多視角的幾何結構關系擴展至每個視角的每一層的表示矩陣中，保持幾何關系的穩定性，最大化視角間關系。除此之外，考慮到多視圖數據的差異性，對每個視圖加入一個權重值，調節每個視圖在共識表示矩陣中所占比重。本文針對所提出的模型采用相應的迭代優化算法，從理論上證明算法的收斂性。在多個數據集上的實驗結果與分析證實了算法的性能優越性。

1 相關工作

1.1 半非負矩陣分解算法

非負矩陣分解(nonnegative matrix factorization, NMF)算法對基礎矩陣Z和特征矩陣H的非負限制使得算法本身更具備聚類易解釋性, 但與此同時數據矩陣X的適用性也受到了限制。為了擴展矩陣分解的應用范圍，Ding等[18]提出了一種半非負矩陣分解算法(semi-nonnegative matrix factorization, Semi-NMF)，改變了對數據矩陣X和基礎矩陣Z的限制條件，其優化問題為

式中： ‖ ·‖代表Frobenius范數；X∈ Rd×n是輸入的數據矩陣，包括n個樣本；Z∈ Rd×k是分解后的基礎矩陣；H∈ Rk×n是分解后的特征表示矩陣，它是非負的；k是數據矩陣經過矩陣分解之后的維度。使用迭代的優化算法，文獻[18]給出式(1)中基礎矩陣Z和特征表示矩陣H的更新策略為

式中：H?是指矩陣H的Moore-Penrose偽逆矩陣；矩陣M的 [M]pos表示矩陣的負數均用0代替，相似的 [M]neg表示矩陣中的正數均用0代替，兩者的計算公式如下：

1.2 深度矩陣分解算法

Semi-NMF是NMF算法的擴展算法，從聚類的角度出發，分解之后產生的基礎矩陣Z可以看作是聚類質心矩陣，特征矩陣H可以看作數據點聚類之后的成員關系矩陣[18,24]。那么，半非負矩陣分解產生的低維表示矩陣H與原始特征矩陣X之間的映射矩陣Z中很有可能包含更為復雜的層次結構信息。因此，Trigeorgis等[19]提出一種深度矩陣分解模型(deep Semi-nonnegative matrix factorization, Deep Semi-NMF)。其算法結構如圖1所示。

圖1 深度半非負矩陣分解Fig.1 Deep semi-nonnegative matrix factorization

從圖1中可以看出，深度矩陣分解算法使用多層分解的方式，將i層的分解矩陣Zi作為下一層分解的輸入矩陣，最后一層的特征表示矩陣將用于聚類獲得數據的類別信息。多層次分解的具體過程和優化問題如下列公式所示：

式中：Zi是第i層的映射矩陣；Hi是第i層的特征表示矩陣。

2 多視圖深度圖正則化矩陣分解聚類算法

深度半非負矩陣分解算法通過逐層分解的方式證實了原始數據與特征表示矩陣之間隱藏著低維特征屬性的層次屬性，但是在應用于多視圖聚類時忽略了數據的固有幾何結構。本文提出多視圖深度圖正則化矩陣分解聚類算法，通過對深度矩陣分解的各層加入兩個圖正則化的限制，保護數據的幾何結構信息。

2.1 圖正則化

假如兩個數據點Xi和Xj在數據分布中有相近的內部幾何關系，那么在新的基礎空間中對應的表示矩陣Zi和Zj應該擁有類似的關系，這就是流形假設[25-26]。這種幾何結構信息可以通過構建數據點的最近鄰圖進行有效的建模[27]。Mikhail通過最近鄰圖對數據局部幾何結構的保護提出降維算法?拉普拉斯特征映射(laplacian eigenmaps, LE)[28]。在此基礎上，SNE(stochastic neighbor embedding)算法加入數據幾何結構的全局關系，認為高維空間數據點之間的不相似性關系在低維空間中保持不變[29]。EE(elastic embedding)算法[30]沿用SNE的思想，改變全局結構的計算方式，使得算法更簡單，更易實現。EE算法的目標函數為

2.2 多視圖深度圖正則化矩陣分解聚類算法的目標函數

受到EE算法[30]對數據幾何結構的保護以及數據隱藏的層次屬性的啟發，在深度矩陣分解的各層中加入局部幾何結構和全局幾何結構信息，將兩個圖正則化嵌入深度分解的各層，使得數據的幾何結構對數據新的表示矩陣進行微調。算法的目標就是為了最小化下列問題：

其中優化問題(式(2))中對數據的局部幾何結構的計算可進一步簡化：

那么優化問題(2)可以改寫為：

根據對數據全局幾何結構的計算方式，優化問題(3)可進一步簡化為

3 算法優化

為優化模型的性能，在對數據進行深度圖正則化矩陣分解之前，需要對每個視角各層的基礎矩陣和特征表示矩陣進行初始化。這里使用加入了圖正則化的半非負矩陣分解算法進行各層的初始化。之后，使用迭代更新的方式優化函數變量。算法的成本函數為

根據拉格朗日乘子法，對每個變量進行求導更新計算。

2) 固定變量、 αv，優化更新，HP。

當l

定理1更新公式(6)的有限解滿足KKT條件。

證明有關的優化問題是含有不等式約束條件的拉格朗日函數：

其中參數 ξ是為了滿足不等式約束條件≥0而產生的乘子。對式(7)進行求導并使之為0，即根據對偶性定理，可以得到：

根據M=[M]pos?[M]neg，式(8)可以簡化為

根據等式的收斂性，式(7)與式(8)等價。當其中一個等式滿足時另一個等式也是滿足的，且具有可逆性。

當l=P時，更新變量HP。HP是通過逐層分解獲得的視角間共有的特征表示矩陣，優化問題同樣滿足KKT條件，同時考慮到視角的互補性和差異性，在更新每個視角的最后一層時在式(5)的基礎上加入視角權重獲得共識表示矩陣。

多視圖深度圖正則化矩陣分解聚類算法的整體優化過程如下：{}

輸入多視圖數據X=X1,X2,···,Xv，參數λ，γ，各層維度 = [l1,l2,···,lP]，最近鄰居數k；

輸出各層基礎矩陣和特征矩陣以及視角間的共識表示矩陣HP。

1) 使用加入圖正則化的Semi-NMF算法初始化每個視角各層的基礎矩陣和特征矩陣;視角權重 αv=1/V;構建每個視角的全局圖和局部圖。

2)當v= 1:V時

3) 當l=P?1:1時，根據逐層分解的方式更新各層特征矩陣：

4)當l=1:P時

5) 當l

6) 當l=P時，使用式(9)更新HP。

7) 使用式(10)更新視角權重 αv。

8) 重復2)~7)直至收斂。

4 實驗

4.1 實驗設置

本實驗中選擇了5個數據集，包括3個面部基準數據集和2個圖像數據集，面部數據集和圖像數據集均具備良好的結構信息，能更顯著的表現逐層分解中加入圖正則化的效果。

Yale面部數據集由15個人在面部表情和配置信息不同的情況下產生的共165張GIF格式的灰度圖像。每個人有11張圖片，面部表情和配置信息包括表情、光照方向、情緒(快樂/悲傷)、有無眼鏡等[3]。

Extend Yale B面部數據集由38個人在將近64個不同光照條件下所得的面部圖像組成。在實驗中，選擇了640張，10個子集的面部圖像進行測試。

UMIST面部數據集包括20個人的564張圖像(混合種族、性別、外觀)。每個人都以一系列的姿勢顯示，從側面到正面，均已PGM的格式存在，大約220像素×220像素，256灰度，像素值用作特征表示[31]。

COIL-20(columbia university image library)圖像數據集包含了20個對象物體，每個物體在水平上旋轉360°，每隔5°拍攝一張照片，因此每個對象共72幅圖，圖片大小為64像素×64像素，總共1 440張圖像。

Caltech101數據集是圖像數據集，共包括了101種分類，每個分類包含了40張到800張不等的圖片，大多數類別有50張圖片。每一張圖片的大小為300像素 × 200像素。我們選擇了20個類別，共2 386張圖像。

本實驗中選擇了9對比算法。

BestSC：在多視圖數據的每個視角數據采用標準的譜聚類算法[32]，記錄最好的實驗結果。

ConcateFea：將所有視角的特征結合起來，使用譜聚類算法獲得實驗結果。

ConcatePCA：將所有視角的特征結合起來，使用PCA將特征矩陣映射到低維子空間，使用譜聚類算法獲得聚類結果。

Co-Reg SPC：通過共正則化聚類假設的方式使得數據點在不同視角中擁有相同的聚類成員關系[33]。

Co-Train SPC：基于潛在聚類為同一類別分配一個數據點，無關視角的假設，通過協同訓練的方式獲得視角之間一致的聚類[34]。

Min-Disagreement SPC：該算法以最小化不一致性為標準構建二分圖，使用譜聚類算法進行聚類[35]。

DiMSC：在子空間聚類的背景下，使用希爾伯特施密特獨立標準(HSIC)探索多視圖數據的完整性信息[36]。

GMVNMF：將PVC算法[37]從雙視圖擴展到多視圖聚類，同時加入視角圖拉普拉斯規則化探索每個視角中數據分布的內部幾何結構[38]。

DMF_MVC：將 deep semi-nmf model[19]應用于多視圖數據，同時對最終獲得的特征表示矩陣加入視角的圖拉普拉斯矩陣進行微調[20]。

為更加全面的比較算法性能，本文中選擇了6種不同的度量指標，包括標準化互信息(normalized mutual information, NMI)，準確率 (accuracy,ACC)，調整蘭德指數 (adjusted rand index, AR)，綜合評價指標(f-score)，精確率(precision)，召回率(recall)。這些指標都是數值越大，性能越好。在實驗中，每個算法都采用其原算法中最佳的參數設置并運行10次以上，最終結果以均值和標準差的方式呈現。

4.2 實驗結果與分析

表1是本文算法與其他對比算法在Yale面部數據集上的實驗結果。從實驗結果可以看出，本文提出的算法相較于其他對比算法性能均良好，其中NMI和ACC兩個指標提高了10%以上，其余指標均在15%以上。表2是算法在Extend Yale B面部數據集上的實驗結果。在該數據集上，本文提出的算法在各項指標上均有所提高。將其與各項指標的最佳數值對比，在NMI上提高了4.4%，在ACC上提高了3.4%，在AR上提高了4.9%，在F-Measure上提高了5.2%，在精確率和召回率上各提高了2.1%和1.3%，均值保持在3.5%。表3是算法在面部數據集UMIST上的實驗結果。從實驗結果上看，本文提出的算法比其他算法擁有5個指標的提高，且均在2%~5%以上。在召回率上，本文算法性能并沒有達到最好，但是總體來看，本文的算法性能更加穩定。表4是算法在圖像數據集COIL-20上的實驗結果。從表中可以看出，本文提出的算法較之其他算法表現良好。同時，各項指標的提高均值來看，本文算法與基于譜聚類的算法性能相近，尤其是BestSC算法，這就說明本文算法能夠捕捉最佳視角信息并使用圖規則化改善聚類性能。表5是各算法在Caltech101-20圖像數據集上的性能表現。從數據中可以看出，Co-Train SPC算法因其協同訓練的方式能夠最大化視角間的標準化互信息。雖然在某些指標上，本文提出的算法并未達到最優，但是在其他指標上表現良好，且比協同訓練的兩種算法提高了10%以上。

表1 不同算法在Yale面部數據集上的實驗結果(均值±標準差)Table 1 Experimental results of different algorithms on the Yale face dataset (mean ± standard deviation)

表2 不同算法在Extend Yale B面部數據集上的實驗結果(均值±標準差)Table 2 Experimental results of different algorithms on the Extend Yale B face dataset (mean ± standard deviation)

表3 不同算法在UMIST面部數據集上的實驗結果(均值±標準差)Table 3 Experimental results of different algorithms on the UMIST face dataset (mean ± standard deviation)

表4 不同算法在COIL-20數據集上的實驗結果(均值±標準差)Table 4 Experimental results of different algorithms on the COIL-20 dataset (mean ± standard deviation)

表5 不同算法在Caltech101-20數據集上的實驗結果(均值±標準差)Table 5 Experimental results of different algorithms on the Caltech101-20 dataset (mean ± standard deviation)

值得注意的是，本文的算法是基于矩陣分解的。在對比算法中，算法GMVNMF和DMF_MVC也是建立在矩陣分解之上的，且均加入了圖正則化。從實驗結果中可以看出，本文提出的算法在4個數據集上的表現比兩種算法都好。其中，在Yale面部數據集上，本文算法相較于兩種算法在各項指標上平均提高了43.1%和18.7%；在Extend Yale B面部數據集上分別平均提高了27.8%和6.6%；在UMIST面部數據集上，本文提出的算法在與算法GMVNMF進行比較時雖然在召回率上表現略低，但是在NMI上提高了9.3%，在ACC上提高了20.7%，在AR上提高了20.8%，在F-Measure上提高了18.5%，在精確率上提高了30%，均值仍能保持在14.5%，并且本文提出的算法在各項指標上表現更加穩定；在與算法DMF_MVC進行比較時，本文的算法在各項指標上分別提高了8.2%、11.8%、13.7%、12.9%、13.5%和16.3%，均值達在12.7%。在COIL-20圖像數據集上則平均提高了30.6%和7.3%；在Caltech101-20圖像數據集上平均提高了12.9%和11.2%。由此可見，本文算法使用的圖正則化計算方式和逐層加入視角圖正則化對于聚類有顯著的改善效果。

4.3 算法分析

4.3.1 參數分析

算法中包括了視角權重和圖正則化使用的平衡參數γ、λ，深度矩陣分解的各層維度以及計算局部圖和全局圖使用的最近鄰值k，兩者結合計算圖矩陣的平衡參數η，其中λ與η有計算關聯性。考慮到數據中局部關系和全局關系的等價值性，實驗中固定設置 η =1。參數，參數最近鄰值k的選擇在KNN算法中是一個開放性的問題，這里選擇 {5 ,10,15}3個值進行測試。

圖2和圖3是在參數γ、λ和各層維度{[100 50],[150 50],[150 100]}影響下，算法生成的NMI和ACC的變化曲線。首先，從圖2中可以看出，當γ變化時，NMI和ACC的各3條曲線變化幅度并不大，均控制在0.03以下，這就說明γ的變化對算法的性能影響不大。其次，從圖3中NMI和ACC的變化曲線中可以看出，只有在分解維度為[150 100]時，參數λ的變化對于性能的影響才是最大的，同時，當λ=0.01時兩項指標均達到最大且變化明顯。最后從圖2和圖3中可以看出算法在分解維度為[100 50]時效果最好，且最為穩定；在分解維度為[150 100]時效果最差，同時曲線波動也最大。

圖2 不同參數γ和各層維度下算法在Yale面部數據集上的性能變化（k=5，λ=0.01）Fig.2 Performance changes of the algorithm on the Yale face dataset under different parameters γ and each layer dimension (k=5，λ=0.01)

圖3 不同參數λ和各層維度下算法在Yale面部數據集上的性能變化（k=5，γ=0.1）Fig.3 Performance changes of the algorithm on the Yale face dataset under different parameters λ and each layer dimension (k=5，γ=0.1)

圖4是算法在參數γ和最近鄰k兩者影響下生成的NMI和ACC數值折線圖。從圖中可以看出，NMI和ACC在k=10時達到最大值，在k=15時值最小，同時k=10與k=5對算法的影響控制在0.03之內；再結合圖2可以進一步看出，參數γ在取中的值時，效果能夠達到最優。

圖4 不同參數γ和最近鄰k下算法在Yale面部數據集上的性能變化（λ=0.01，各層維度=[100 50]）Fig.4 Performance changes of the algorithm on the Yale face dataset under different parameters γ and the nearest neighbors k (λ=0.01，各層維度=[100 50])

4.3.2 收斂性分析

關于算法的收斂性問題，從理論上來說，定理1說明了算法模型在每個視角的特征表示矩陣和共識表示矩陣優化問題上均落在一個固定點上。如圖5是在實驗中，設定參數值γ=10，λ=0.01，k=10，各層維度=[100 50]，優化問題 (4)與NMI隨著迭代次數不斷增加而產生的變化曲線。從圖5中可以明確看出，隨著迭代次數的增加，目標函數值逐漸降低，NMI增加并逐漸保持穩定。當迭代次數在1~15時，目標函數值下降迅速；當達到20次或保持在50~67次時，NMI一直穩定在最高值，之后逐漸保持穩定，且目標函數值下降緩慢。為保證實驗數據的穩定性，實驗中迭代次數設定為100次。

圖5 迭代更新時算法的目標函數值和性能變化(γ=10,λ=0.01, k=10,各層維度=[100 50])Fig.5 The objective function value and performance change of the algorithm during iterative update(γ=10, λ=0.01, k=10, layer dimension=[100 50])

4.3.3 聚類可視化分析

為更形象的展示本文算法聚類過程，我們可視化了聚類結果，如圖6所示。我們選擇了每個數據集中的3個類別，每個類中包含隨機的10張圖片。從圖中可以看出每個類中均包含非本類別中的圖片對象。從圖6(a)中可以看出，每個類中包含少量的錯誤對象，證明了算法的高準確率，同樣的效果也可以從圖6(d)中看到。在Extend YaleB數據集的3個類別中，算法的準確率并沒有達到最優，如圖6(c)中所示，算法在第3個類別中存在一定的錯誤。在圖像數據集中，算法在COIL-20數據集上的表現良好(圖6(b))，每個類別從上到下的準確率可以達到90%，90%，80%。對于圖像構成更為復雜的Caltech101-20數據集，算法的準確度還有一定的進步空間(圖6(e))。

圖6 算法在各數據集上的聚類可視化Fig.6 Cluster visualization of the algorithm on each dataset

4.3.4 復雜度分析

圖7展示了所有算法在5個數據集上的運行時間變化。本文所使用的實驗環境是Inter Core i7 8 500 8 GB內存，Matlab R2018a版本。為保證數據的穩定性，大多數算法均運行了10次以上。結合運行時間和實驗數據集兩個內容可以看出大多數算法的時間復雜度與數據點的量級有直接聯系。數據點越多，算法中涉及的計算和處理所消耗的時間越多。在時間復雜度上，基于矩陣分解的算法所需要的時間復雜度為。同時，通過上述對算法收斂性的內容可以看出，基于矩陣分解的算法需要100次以上的迭代才能保持性能穩定，因此，基于矩陣分解的算法比其他大多數算法都需要消耗更長的時間。值得注意的是，相較于相近的DMF_MVC算法，本文提出的算法在時間復雜度上并沒有明顯的提高。這就說明本文的算法在保證性能提高的同時并沒有增加時間消耗。

圖7 各算法在數據集上的運行時間Fig.7 Running time of each algorithm on the dataset

5 結束語

本文中提出一種基于深度圖正則化矩陣分解的多視圖聚類算法，該算法使用深度非負矩陣分解模型并逐層加入圖正則化限制，獲取數據層次信息的同時保護數據的幾何結構。權重的使用和共識表示矩陣的生成確保數據的一致性和差異性。實驗數據表明，該算法在含有豐富幾何結構的數據集上能夠達到較高的準確率和穩定性。今后，需要加強對數據幾何結構信息以及多視圖數據表示學習的研究，提高多視圖聚類的性能。