不完備多視圖的在線反向圖正則化聚類*

鄧萬宇 耿美娜 李建強

（西安郵電大學計算機學院 西安 710121）

1 引言

現今，隨著信息技術、計算機技術以及互聯網技術的迅速發展，獲取數據的方式越來越多，人們已經進入了大數據時代。大數據在國內外已經如火如荼的發展起來，在各個領域都在滲透，近年來，人們對于數據信息價值性和可靠性都有著較高的要求，在大數據的時代背景下，每天都會產生各種形式的數據，包括文字、圖片、視頻以及音頻，這些數據優勢是規模大、種類多、要求實時性強。

在當今大數據時代，同一數據對象往往可以在不同的視圖下進行描述，所獲取的數據常?？梢杂啥鄠€特征集合進行表示，不同視圖下的觀測揭示了事物的不同屬性，這類數據通常被稱為多視圖數據［2］。多視圖數據的學習主要是在聚類這個背景下被研究，對于此類多視圖的研究被稱為多視圖學習［3］，目前，多視圖學習在機器學習、數據挖掘、人工智能等不同領域得到了廣泛的研究［4～6］。在這些視圖中，每一個視圖可以滿足于特定的數據分析任務需求，不同視圖之間通常包含互補的信息。類似于我們所倡導的多視圖看問題的思維，機器學習如何綜合利用多視圖數據建立性能更為有效的學習模型，從而服務于人類的生活和工業生產，具有重要的理論意義和廣泛的應用前景。

在多視圖的聚類中，存在一些實際問題，往往假設這個數據是完整的，然而在實際應用中，可用的多視圖數據是不完備的，即意味著缺少某些視圖的功能，這對多視圖聚類帶來了很大的困難。如何處理不完全多視圖數據并從中挖掘到該類數據的共享信息，利用多視圖數據的一致原則以及互補原則完成多視圖聚類任務，已經引起機器學習領域研究人員的廣泛關注。如果對于這類不完備多視圖數據直接進行聚類分析，則會丟失很多的信息，因此，首先要對不完備多視圖數據進行分析處理，再對數據進行聚類。顯然，現有的多視圖聚類方法無法將不完備視圖的多視圖數據聚類，因為無法學習通用相似圖或者所有視圖的低維表示。此外，多個視圖之間由于缺少配對視圖可用的補充信息，因此視圖非常有限。這些因素使得不完備多視圖數據的研究成為一個挑戰。對這類不完備多數圖數據集上進行聚類稱為不完備多視圖聚類［7～12］。因此，本文的研究對象是不完備的多視圖數據，關注如何能夠更好地處理的不完備的多視圖數據，聚焦不完備多視圖技術的相關技術。

同樣，在上述中解決的不完備多視圖數據都是離線的，沒有考慮到大規模的一些數據問題，其不能直接存放在內存中，并且很難離線處理。對于這個問題的處理，到目前為止，針對此問題已經提出了兩種解決方法［13～14］。

對于處理這種大規模的不完備多視圖數據，本文提出了一種基于非負矩陣分解［15～20］的在線反向圖正則化算法（Nonnegative matrix factorization algorithm based on online inverse graph regularization：IMC_OIRG）方法。

本文提出的IMC_OIRG 算法，主要具有以下優點：

1）當數據太大而不能放入內存中時，依舊可以處理不完備多視圖數據，即可以最小化不完備多視圖數據對聚類結果的影響。

2）對于這種數據過大的數據，依舊可以將不同特征空間的各種視圖進行組合，根據其一致性和互補性，能夠使得可以獲得更好的聚類結果。

3）將非負矩陣分解與反向圖正則化進行結合，保證多視圖局部結構的一致性，使得不完備多視圖數據能夠進一步對齊，使得能夠得到更好的公共潛在特征表示。

2 相關工作

2.1 問題描述

對于不完備多視圖聚類，簡要描述問題的表述，假定給出一個有N個樣本nv個視圖的數據集，在本文中定義一個指示矩陣B∈Rnv×N。

其中，B的每一行代表一個視圖的存在。若多視圖數據是完備的，每個視圖包含所有的實例，則B為一個全1矩陣，即=N，k=1，2，…，nv。若多視圖數據是不完備的，數據矩陣X(k)將有許多行缺失，即指示矩陣表示為＜N，k=1，2，…，nv。本文的目標為將不完備多視圖數據的N個實例聚類成K個聚類。

2.2 相關工作

OPIMC［14］為解決不完備多視圖聚類問題提出了一個框架，借助于正則化矩陣分解和加權矩陣分解，將數據矩陣X(k)∈Rdk×N分解為兩個矩陣G(k)∈RDk×K和F(k)∈RN×K，同時令，為了考慮到不同視圖之間的一致性信息，假設不同的矩陣，共享相同的矩陣F。同時還考慮到實例的缺失信息，借助加權矩陣分解來處理每個視圖的不完備性。對于大量的不完備多視圖數據，假設每個視圖都是通過塊獲得的，并且塊的大小為s，最終目標函數表示為是第k個視圖的第t個數據塊，Ft是第t個對角數權據重塊矩的陣聚。類權指重示矩矩陣陣，被是定第義為t個數據塊的

3 算法模型

在本節中，提出了IMC_OIRG 算法，處理大規模的不完備多視圖數據，利用動態權重學習推斷缺失的視圖，同時，利用反向圖正則化進一步對齊視圖，學習局部特征，來實現有效的公共表示學習。

3.1 算法提出與模型構建

給定nv個視圖，N個樣本的不完備多視圖數據，使用非負矩陣分解的模型進行分解，將X(k)∈分解為兩個矩陣G(k)∈和F(k)∈，分別表示為第k個視圖的基矩陣和潛在特征矩陣。其中，K表示為聚類的目標數，目標函數可以寫成如式（4）所示。

在此基礎上，由于不完備多視圖數據的特點，目標函數無法直接進行優化，簡單的填充實例不能很好地解決這個問題。因此，本文利用加權非負矩陣分解的思想，引入一個對角權重矩陣P(k)∈RN×N，其中，表示為第k個視圖的第i個實例，同時，對于在視圖中出現的實例權重賦予1，對于視圖中缺失的實例賦予較低的權重。因此，目標函數式（5）表示為

本節的目標為找到每個視圖的潛在特征矩陣和一個共同的共識，這個共識矩陣表示了所有的視圖的綜合信息。因此，目標函數式（6）可以被重新寫為

其中，λ1(k)表示為重建誤差與學習到的第k個視圖的共識一致性不一致之間的權衡參數。

在上述式（6）中，不僅對于不同的視圖分配了不同的權重，而且表示出了一致的共識矩陣，對于不完備視圖的性質，為了加強潛在特征矩陣的稀疏性，仍添加一項l1范數。同時對潛在特征矩陣添加范數限制后，對于噪聲和異常值是魯棒的。

其中，‖ · ‖1表示l1范數，λ2(k)表示為第k個視圖重建的稀疏性和準確性之間的折衷參數。

對于不完備多視圖數據，由于所有視圖的可用實例數都小于總樣本數，獲取數據的局部流行結構是不可能的，因此，使用反向圖進行學習，如式（8）所示。

其中，其中，1 是一個全1 的向量。其次，令Pi，:1=1，是為了防止任何實例與其鄰居不相連的平凡解。rank(LW)表示為LW的秩。通過反向圖正則化，保證了多視圖間的一致性流形結構，進一步對齊所有恢復的不完整視圖。

3.2 目標函數

最終，對于不完備多視圖數據，根據上述學習，形成了一個學習模型，得出解決不完備多視圖數據的算法的目標函數，如下。

在實際的應用過程中，數據矩陣由于過大，因而無法直接放入內存中。對于此問題，本章采用以低計算和存儲復雜性的在線方式來解決此問題。將輸入的數據在時間t時分成塊，s表示為數據塊的大小，也就是實例的大小。因此，輸入的數據矩陣為，最終的目標函數表示為式（10）。

對于目標函數式（10）中引入的權重矩陣，和之前用平均特征值進行直接填充的方法不同，不完備多視圖數據，本節研究的多視圖數據太大而不能放入內存，平均特征值不能直接進行計算，對此，引入一個動態權重矩陣，即當讀入一個新的數據塊時，采用動態（最新）平均值來填充，不是采用全局的平均特征值來填充缺失的實例。

可利用的實例中可以被動態設置為

3.3 優化

對于目標函數式（10）的求解問題，可以發現，對于每一個t，需要對和{T}，然而，目標函數不是聯合凸的，因此采用交替迭代的方法來更新求解。

1）更新G(k)，固定其他變量，關于G(k)的最小化目標函數為

對G(k)取 一 階，?導(t)對數于G，(k其)的 梯中度，為令

因此，?(t)(G(k))相對于G(k)的Hessian矩陣為

使用二階的投影矩陣下降法，在時間t更新G(k)的方程為

其中，z表示迭代的次數，γz表示步長，??(t)(G(k))表示目標函數對G(k)的一階導數。對于選取合適的步長γz，本章考慮使用簡單而有效的Armijo的投影規則，令γz=ηφz，φz是第一個非負整數。

3）更新W，固定其他變量，關于W 的最小化目標函數為

對式（21）進一步進行簡化：

式（22）的封閉形式可以通過(Nie et al.2016)提出的有效算法來實現。

4）更新T，固定其他變量，關于T的最小化目標函數為

其可以通過對應于最小二乘的前c個最小特征值的一組特征向量來優化。

在式（24）中，假設λ1(k)為正，對其求一階導數并使其為0：

在算法1 中總結了IMC_OIRG 的整個優化過程：

算法1：IMC_OIRG

Input：不完備多視圖數據{X(k)} ，聚類數K，數據塊大小s，參數{λ1(k)，λ2(k)，λ3(k)，λ4(k)} .

為不完備多視圖實例設置權重；repeat

for k=1:nv do

根據式（16）更新G(k).

根據式（22）更新W.

根據式（23）更新T.

直至收斂

3.4 收斂性分析

如算法1 所示，提出的IMC_OIRG 方法是通過交替迭代的來求解最優解的，通過此方法，可以收斂到一個局部最優解。

4 實驗

4.1 數據集

數據集介紹如下，我們選取四個數據集，Handwritten Dutch Digit Recognition（Digit）、Web Knowledge Base（WebKB）、Reuters Multilingual Text Data（Reuters）、YouTube Multiview Video Games（You-Tube）。數據集總結見表1。

表1 所用基準數據采集系統的描述

4.2 對比試驗

我們將本文提出的方法與幾種之前的方法進行比較：IMC_OIRG 是本文提出的在線多視圖聚類方法，為了便于比較，將所有視圖的參數設置為相同。OPIMC 利用正則化矩陣分解和加權矩陣分解的單趟在線聚類方法；MIC 是OMVC 的線下情況，基于聯合非負矩陣分解的聚類方法；OMVC 是提出的在線不完備多視圖聚類方法；Multi NMF 是提出的一種經典的離線多視圖聚類方法；ONMF 是一個在線的單視圖文檔聚類算法，為了應用ONMF，將所有規范化的視圖連接在一起，形成一個大的單一視圖。另外，由于MIC 和MultiNMF 都是離線方法，因此將所有的數據都考慮在內，通?？梢垣@得比在線方法更好的性能。

4.3 實驗設置

在本次實驗中，采用兩個廣泛使用的評估指標，準確性（AC）和歸一化互信息（NMI），用來橫量聚類性能。同時，對于每個數據集掃描十遍（Pass）并匯報每一次的NMI和AC。實驗結果如圖1所示。

圖1 實驗結果

本文選取的四個數據集都是完整的，為了模擬不完備多視圖的情況，在每個視圖中令缺失度為0.4。對于數據塊的設計，將小數據集s 為50，大數據集為2000。由于在對比方法中，除ONMF以外所有方法都有幾個參數設置，因此對比較方法中的所有參數進行網格搜索，并且給出最佳結果。另外，MultiNMF、ONMF-I 和ONMF-DA 無法處理不完備多視圖的視圖，為了應用這些方法，本文用平均特征值填充缺失實例。在評價中，本文采用K-means從一致性潛在特征矩陣中得到聚類解。

4.4 結果分析

圖1（a）～（d）顯示了本文提出的方法在數據集Digit 和WebKB 的性能，從圖中可以觀察到，對于Digit 數據集，在第六次之后，算法達到了相似的結果，同時，比其他的方法效果要好一點。對于Web-KB數據集，前幾次的效果不是很好，造成這個現象的主要原因可能是因為設置的缺失度與設定的塊的尺寸不合適，導致公共潛在特征矩陣學出較難，經過多次Pass之后，聚類性能提升。

圖1（e）～（h）顯示了本文提出的方法在數據集Reuters 和Youtube 的性能，從圖中可以觀察到，對于Reuters數據集，第五次Pass之后，慢慢達到了較好的結果，對于Youtube數據集，直接就能看出來比較其他方法比較有效，聚類性能明顯有效。

4.5 復雜性分析

在本文提出的算法中，使用平均損失來進行IMC_OIRG方法的收斂性實驗，在每次讀取數據塊t之后，平均損失被定義為

圖2 平均損失值

圖3 Digit參數

4.6 參數敏感度分析

在本文中利用Digit 數據集對四個參數{λ1(k)，λ2(k)，λ3(k)，λ4(k)} 進行分析，當參數分別位于范圍［10-6，10-1］，［10-8，10-2］，［10-8，10-2］，［10-10，10-3］內時，可以看到有一個好的效果，在實驗中，利用網格搜索策略來尋找四個最佳的參數。從圖中3 可以看出，當{λ1(k)=10-3，λ2(k)=10-7，λ3(k)=10-7，λ4(k)=10-8}時效果是最佳的。

4.7 數據塊分析

在本文所提出的方法中，設定的數據塊s是一個重要的參數，為了學習不同s對于聚類結果的影響，選取Digit 數據集，缺失度為{1 ，0.2，0.4} ，令s={2 ，10，50，250} ，在表2 中，給出實驗結果?？梢杂^察出，本文所提出的方法，效果性能優于其他的方法，并且可以看出，當數據塊大的比數據塊小的效果好一些，原因在于，當數據塊越大，其中可以利用的數據信息就會越多，其中，當s=50 或者s=250 時，效果更好。

表2 Digit對于不同缺失率和不同數據塊

5 結語

本文提出了一種解決不完備多視圖數據的方法——不完備多視圖的在線反向圖正則化聚類（Online Reverse Graph Regularized Clustering for Incomplete Multi-view）。在加權非負矩陣分解的前提下，最小化潛在特征矩陣和共識之間的不一致，給缺失實例賦予動態權重，減少缺失實例的影響，學習反向圖正則化，利用視圖的局部信息，進一步對齊視圖。同時，對于大數據的數據集，對其進行逐塊處理。通過實驗證明了本文所提出方法IMC_OIRG的有效性。