基于多階近鄰約束的深度不完整多視圖聚類方法

王 梅 ,王偉東 ,劉 勇 ,于源澤

（1.東北石油大學計算機與信息技術學院，大慶，163318；2.中國人民大學高瓴人工智能學院，北京，100049）

近年來有許多多視圖聚類方法被提出［1-9］，其中大部分工作都顯示或隱式地采用數據完整性假設，即所有實例的所有視圖都是可見的.然而，在實際應用中，由于數據收集和傳輸的復雜性，數據完整性假設很難成立，從而導致不完整多視圖聚類問題.與完整的多視圖數據相比，缺失視圖不僅削弱了原始多視圖豐富的語義信息，而且由于缺失導致的分布不確定性，使得提取數據信息更加困難.Li et al［10］首次利用非負矩陣分解技術挖掘公共潛在子空間，提出了部分對齊的多視圖聚類算法（Partial Multi-View Clustering，PVC）.Hu and Chen［11］提出一種基于半非負矩陣分解的雙重對齊不完整多視圖聚類算法（Doubly Aligned Incomplete Multi -View Clustering Algorithm，DAIMC）.Zhao et al［12］通過一個新的圖拉普拉斯項來處理不完全多模態視覺數據分組問題，并提出不完整的多模態視覺數據聚類算法（Incomplete Multi-modal Visual Data Grouping，IMG）.Wang et al［13］將數據缺失問題轉化為矩陣相似性問題，提出一種面向擾動的不完整多視圖聚類方法（Perturbation-Oriented Incomplete Multi-View Clustering，PIC）.Liu et al［14］將不完整多視圖聚類重新定義為聯合優化問題，提出一種具有不完整多核K-means 方法（Multiple Kernel K-means with Incomplete Kernels，MKKM-IK）.次 年，Liu et al［15］發現過于復雜的優化限制了MKKM-IK 聚類性能的提升.為此，他們提出一種高效且有效的不完整多視圖聚類算法（Efficient and Effective Incomplete Multi-View Clustering，EE-R-IMVC）.Wen et al［16］設計了由不完全圖構造的拉普拉斯矩陣來約束缺失視圖，提出了一種基于一致張量框架下的缺失視圖推斷的不完整多視圖聚類算法（Unifified Embedding Alignment Framework，UEAF）.劉曉琳等［17］通過交叉擴散的方式將不同階的深層結構信息進行融合，提出一種基于多階近鄰擴散融合的不完整多視圖聚類算法（Incomplete Multi-View Clustering Algorithm Based on Multi-Order Neighborhood Dffusion and Fusion，MNDF）.

盡管上述方法在不完整多視圖聚類任務上具有良好的表現，但大多數方法是利用淺層模型完成不完整多視圖聚類任務，在處理高維和大規模數據時性能有限.對此現有部分不完整多視圖聚類方法［18-27］利用深度網絡卓越的非線性擬合能力挖掘數據深層次信息.Zhang et al［18］同時考慮了多視圖的互補性和類分布，設計并構建了一個部分交叉多視圖網絡（Cross Partial Multi-View Networks，CPM-Nets）處理不完整多視圖問題.Wang et al［19］構建了一個帶有生成器的多視圖聚類模型，通過顯式生成缺失視圖數據解決不完全多視圖問題.Zhang et al［20］引入了一種單階段后期融合方法，該方法結合了缺失視圖的插補和聚類.Tang and Liu［21］為了減少缺失視圖導致的聚類性能退化，提出了深度安全不完整多視圖聚類方法（Deep Safe Incomplete Multi-View Clustering，DSIMVC）.Zhang et al［22］引入了可學習的潛在表示，以從多個視圖中挖掘公共語義.受到信息論的啟發，Lin et al［23］將一致性學習與缺失數據恢復統一到一個框架中，提出了基于對比預測的不完整多視圖聚類方法（Incomplete Multi-View Clustering via Contrastive Prediction，COMPLETER）.次 年，Lin et al［24］在COMPLETER 的基礎上加以改進，提出了雙重對比預測模型（Dual Contrastive Prediction for Incomplete Multi-View Representation Learning，DCP），解決了兩個以上視圖的缺失問題.Yang et al［25］建立了一個統一的框架，同時解決視圖對齊和樣本缺失問題.

然而現有的基于深度學習的不完整多視圖聚類方法只考慮了視圖的屬性信息，而忽視了結構信息對聚類的影響，導致提取的特征不能充分表示原始數據的潛在結構.近年來，已經有研究人員發現數據的內在結構對于無監督學習至關重要.經典的最近鄰圖約束被廣泛應用于各種機器學習方法［28-29］中，使得提取的語義表示能夠保持數據的原始拓撲結構.也有一些多視圖學習方法［30-33］通過構造先驗鄰接矩陣來幫助保持數據的原始內在結構.這是基于一個基本的假設：如果兩個樣本在原始特征空間中彼此接近，那么它們在嵌入空間中也很接近.但是在數據不完整的情況下，很難從數據中直接獲得完整的圖.為此，也有一些方法利用視圖間的互補性構建近似完整的近鄰圖，指導編碼器提取高級語義特征.然而，這些方法都是直接計算數據集中兩個樣本間的相似性，學習到的圖魯棒性差，且易受噪聲影響導致所獲得的圖難以準確刻畫數據的結構信息，從而降低聚類性能.

考慮到上述問題，本文提出了一種基于多階近鄰約束的深度不完整多視圖聚類方法（Deep Incomplete Multi-View Clustering Based on Multi-Order Neighborhood Constraint，DMNC）.首 先，結合自注意力機制和多視圖學習的特點，設計了一個基于Transformer 的編碼器.與簡單的線性編碼器相比，它能夠進行交叉視圖間的信息交互，有利于挖掘多個視圖間的互補性.其次，引入了加權融合策略來組合多視圖互補信息，同時避免了缺失視圖帶來的影響.最后，考慮到數據的不同階結構信息，利用不完整多視圖的互補性，提出一種多階近鄰約束，其目的是構建一個融合多階近鄰關系的近似完整的近鄰圖指導編碼器提取更緊致、更有判別性的高級語義特征.另一方面，更明顯的區別性語義特征也可以促進缺失視圖的恢復.大量的實驗和直觀的可視化結果也驗證了本文所提方法的有效性.

1 相關理論

1.1 高階近鄰關系一階近鄰關系指的是直接計算兩個樣本間的相似性或在向量空間的距離，比如計算兩個特征向量之間的歐式距離表示這兩個向量之間的相似性，歐式距離越小，樣本之間越相似.大多數基于圖嵌入的方法都是為了保持這種一階近鄰關系而設計的，然而這些方法并沒有觀察到數據的深層結構信息.換句話說，觀察到的一階近鄰關系難以準確刻畫數據的潛在結構.高階近鄰關系刻畫的是一種更深層次的近鄰關系［17，34］.比如，樣本之間的二階近鄰關系并不是通過計算樣本間距離來確定，而是通過樣本的共享鄰域結構來確定.二階近鄰關系的一般概念可以解釋為共享鄰居越多的樣本點越有可能相似.在復雜的樣本關系中，多階相似性對數據潛在結構的挖掘更為重要.

舉例說明，圖1 為包含10 個樣本的近鄰關系圖，連邊表示樣本間的一階近鄰關系，連邊越粗表明一階近鄰關系越緊密.可以看出，樣本6 和樣本7 具有較高的一階近鄰關系，僅按一階近鄰關系進行數據劃分時將會把樣本6 和樣本7 視為同一類.另外，盡管樣本5 和樣本6 之間不存在一階近鄰關系，但是它們共享許多共同的鄰居，即它們具有很高的二階近鄰關系，因此以二階近鄰關系進行數據劃分時，樣本5 與樣本6 應該同屬于一類，這也更加符合數據的真實結構.

圖1 近鄰關系圖Fig.1 Neighborhood relationship

圖2 多頭自注意力機制Fig.2 Multi-Head Attention

定義M(o)∈Rn×n為樣本對之間的第o階近鄰矩陣，其中每個元素的計算如式（1）所示：

1.2 多頭自注意力機制注意力機制是一種能夠選擇性地關注重要信息而忽略其他可見信息的方法.自注意力機制［35］是注意力機制的一種變體，與傳統的注意力機制相比，減少了對外部信息的依賴，更加聚焦于捕捉數據或特征內部的相關性.本文采用自注意力機制來計算同一樣本不同視圖之間的相關性，從而更好地理解數據內部的結構和關聯性.縮放點積注意力（Scaled Dotproduct Attention）是一種常用的自注意力計算公式.首先，需要使用線性變陣矩陣{WQ，WK，WV}計算每個特征或視圖的Q(query)，K(key)和V(value)，自注意力的計算如下：

其中，dk是K的向量維度，除以是為了穩定梯度，防止反向傳播時梯度消失.

為了增強自注意力機制的表示能力，促使模型在相同的注意力機制下學習多樣化的行為，并捕獲特征或視圖內各種范圍的依賴關系，提出了多頭注意力機制.如下所示：

2 基于多階近鄰約束的深度不完整多視圖聚類方法

本文提出一種基于多階近鄰約束的深度不完整多視圖聚類方法（Deep Incomplete Multi-View Clustering Based on Multi-Order Neighborhood Constraint，DMNC），用于學習具有不完整多視圖樣本的表示.DMNC 模型框架如圖3 所示，考慮到本文的下游任務是無監督聚類，由于缺乏直接區分數據的監督信息，本文只能利用可用的原始數據來施加重構約束，以學習視圖所共享的公共語義表示.因此，設計了一個基于Transformer 的自編碼器同時完成多視圖公共表示學習與缺失視圖恢復.此外，為了使提取的公共語義表示能夠包含數據的潛在結構信息，設計了一個多階近鄰約束項，以獲取帶有多階結構信息的公共表示.為了保證恢復的缺失視圖對下游任務有利，采用兩階段的學習策略.第一階段：利用多視圖的一致性恢復缺失視圖，避免缺失位置的噪聲數據產生負面影響；第二階段：將第一階段恢復的數據和原始不完整數據相結合生成新的數據（近似完整數據），完成多視圖聚類.因此，在第二階段，整個模型可以被視為一個通用的多視圖聚類網絡，而不需要任何額外的計算.

圖3 DMNC 模型框架Fig.3 The framework of DMNC

2.1 符號定義為了便于表達，首先對不完整多視圖聚類方法的基本符號作出定義.

給定具有m個視圖和n個樣本的多視圖數據集，將它們劃分為c個類，dv表示第v個視圖的維度.為了表示缺失數據，引入缺失指示矩陣W∈{0，1}n×m，其中，Wi，j=1 表示第i個樣本的第j個視圖可見，否則表示第i個樣本的第j個視圖缺失，表示第v個視圖可見樣本數.表示模型重構的數據，是填充有重構數據的插補數據.Z∈Rn×m×de是完成交叉視圖信息交互后的深層特征，de表示深層特征的維度，其融合表示是本文的目標矩陣.

2.2 交叉視圖信息交互模塊與單視圖數據相比，多視圖學習成功的關鍵是視圖之間的互補性，即每個視圖存在其他視圖沒有的特有信息.為了聚合視圖間的互補信息，本文設計了一個具有交叉視圖信息交互的編碼器（Cross-View Information Interaction Transformer Encoder，CFormer）.首先，原始數據各個視圖的特征維度不同，為了便于后續模塊能夠并行處理所有視圖，為所有視圖添加一組低級的特征提取器，將原始多視圖數據映射到具有相同維度的嵌入空間.簡單起見，選擇m個多層感知機作為低級特征提取器.其中，θ(v)為多層感知機Φ(v)的參數.本文提出的編碼器與經典的Transformer 中的編碼器類似，主要區別在于本文在計算多頭自注意力得分時引入了缺失視圖指標矩陣，以防止缺失視圖參與注意力的計算.具體實現如下：給定多頭自注意力機制的頭數h，對于每個樣本的嵌入特征∈Rm×de，利用h組線性變換參數矩陣獲取相應的query，key和value的映射，其中，dh=de/h.為了根據帶有缺失的嵌入特征計算注意力，定義了一個填充函數zerofil（l），表示用-e9填充零值，并構造了樣本i的掩碼矩陣，其中，wi是缺失視圖指示矩陣W的第i行向量.采用式（6）計算帶有缺失視圖的自注意力：

在第二階段，對于完整視圖數據采用式（7）計算注意力：

對于樣本i，拼接所有輸出：

總之，在編碼器模塊中，同一樣本的所有視圖都將在并行編碼過程中交換信息.因此，每個視圖的私有信息在某種程度上被其他視圖共享.最后，具有交叉視圖信息交互的編碼器CFormer 可以公式化為

2.3 一致性視圖恢復模塊大量多視圖工作［36-39］都假設所有視圖共享同一樣本的共同語義，如公共表示或聚類標簽.受此啟發，本文設計了一個簡單的加權融合模塊獲得所有視圖共享的公共表示：

僅通過加權融合獲得的公共表示Zˉ還無法保證其包含了各個視圖共享的共同語義.為此，本文設計了一個對稱的具有缺失視圖恢復的解碼器（Missing Views Reconstruct Transformer Decoder，RFormer），利用公共表示Zˉ重構包括缺失視圖在內的所有數據.同樣地，為了使模型的輸入輸出格式統一，在輸入解碼器之前，添加一個多層感知機具有缺失視圖恢復的解碼器 RFormer 可以公式化為D∶

由于缺乏直接區分恢復數據的監督信息，本文只能利用可用的原始數據來施加部分重構約束.因此，引入一個加權重構損失Lre.

2.4 多階近鄰約束模塊在數據不完整的情況下，一些現有的方法簡單地跳過缺失視圖來構造鄰接圖，這是明顯有偏的，特別是在缺失率較大的數據上.因此，本文期望獲得一個近似完整的鄰接圖來指導編碼器提取高級語義特征.同時，考慮到多階相似性信息可以為數據提供不同層次的結構描述信息，融合這些不同階的相似性關系能夠為聚類算法提供更加明確的聚類指導.另一方面，更明顯的區別性語義特征也可以促進缺失視圖的恢復.結合這兩點，本文提出多階近鄰圖約束.首先，構建不完整視圖的近鄰矩陣，以第v個視圖為例，定義M(o)(v)∈Rnv×nv為樣本對之間的第o階近鄰矩陣，其中每個元素計算如式（11）所示：

由于視圖存在樣本缺失的情況，所以僅能計算可見樣本之間的相似性.基于視圖之間的互補性，假設每個視圖的數據樣本信息是缺失的，但是多個視圖的結構信息是互補且完備的［40-41］.為此，對同階的m個不完整視圖進行互補性對齊融合，旨在獲得同階的互補近鄰圖A(o)∈Rn×n：

為了使不同階的互補近鄰圖具有相同的度量尺度，首先，需要對互補近鄰圖進行歸一化，即，其中，D(o)為度矩陣，對角線元素為同時，本文采用加權融合的方式獲得包含不同階結構信息的近鄰圖G∈Rn×n：

最后，多階近鄰約束損失函數Lrg如式（16）所示：

2.5 損失函數與聚類綜上所述，模型在第一階段的整體損失函數如式（17）所示：

其中，β是平衡這兩個損失的超參數.

第二階段的損失函數如式（18）所示：

本文在第二階段進行了完整的多視圖聚類，將第二階段獲得的融合嵌入特征Zˉ∈Rn×de作為最終的聚類指標矩陣.簡單起見，本文在Zˉ上執行K-means，以獲得最終的聚類結果.

3 實驗分析

3.1 實驗數據在四個廣泛使用的多視圖數據集上全面地評估了提出的方法.數據集的詳細信息如表1 所示.MNIST-USPS 是一個流行的手寫數字數據集，包含5000 個樣本和兩種不同風格的數字圖像.Columbia Consumer Video（CCV）是一個包含20 個類6773 個樣本的視頻數據集，每個樣本包含三個視圖STIP，SIFT 和MFCC.Multi-Fashion 是一個圖像數據集，本文將三種不同的風格視為一個樣本的三種視圖.Caltech7 是Caltech101 數據集的一個子集，是具有多個視圖的RGB 圖像數據集，本文從中選擇了1474 張涵蓋七個類別的圖像，每幅圖像都提取六種特征，即WM，CENTRIST，LBP，GIST，HOG 和Gabor.

表1 實驗使用的數據集的詳細信息Table 1 Information of datasets used in experiments

3.2 對比方法將本文提出的方法與以下四類方法進行聚類性能的比較實驗.

（1）基線方法：BSV 是一種簡單的基線方法，用平均向量填充缺失的視圖，并對每個視圖執行K-means 以獲得最佳結果；Concat 是另一種流行的基線方法，它將所有視圖與BSV 相同的計算策略對齊，并簡單地將它們連接起來進行單視圖聚類.

（2）利用對齊信息的方法：PVC［10］是不完整多視圖聚類的一項先驅工作，旨在尋找對齊樣本和非對齊樣本共享的潛在空間.

（3）利用結構信息的方法：UEAF［16］考慮了多視圖數據的局部結構，將獲取一致性特征向量與缺失視圖推理統一到一個框架.

（4）基于數據補全的方法：MKKM-IK［14］是一個基于核矩陣補全的算法，采用集成的思想將多個核矩陣進行融合；EE-R-IMVC［15］將每個不完整基礎矩陣與學習的共識聚類矩陣進行歸因，以提高聚類性能；DCP［24］是一種基于互信息理論的深度不完整多視圖聚類方法.

3.3 實驗設置及評價指標所有模型都基于PyTorch［42］實現，在Ubuntu 20.04 系統和NVIDIA 1080Ti GPU 的服務器上完成所有實驗.對于所有數據集，模型的CFormer 和RFormer 分別由三個相同的多頭自注意力層組成，并且為每個視圖設計了一個視圖特有的多層感知機，每個多層感知機由三個全連接層構成.近鄰數K和權衡系數β分別設置為100 和0.1.

為了評估模型處理不完整的多視圖數據的性能，隨機刪除每個視圖p%(p∈{10，30，50})的實例，但對于每個樣本至少保留一個視圖可用.采用廣泛使用的三個指標評價模型最終的聚類性能，包括聚類精度（Accuracy，ACC），歸一化互信息（Normalized Mutual Information，NMI）和純度（Purity），這些指標的值越高表明聚類性能越好.為了減少隨機性產生的影響，所有方法在每個數據集上獨立重復10 次，取平均值.詳細的實驗結果見表2～5，表中黑體字表示每種實驗設置下的最佳結果.

表2 不同缺失率下各聚類方法在MNIST-USPS 數據集上的聚類結果Table 2 Results on MNIST-USPS with different incomplete rates

表3 不同缺失率下各聚類方法在CCV 數據集上的聚類結果Table 3 Results on CCV with different incomplete rates

表4 不同缺失率下各聚類方法在Multi-Fashion 數據集上的聚類結果Table 4 Results on Multi-Fashion with different incomplete rates

表5 不同缺失率下各聚類方法在Caltech7 數據集上的聚類結果Table 5 Results on Caltech7 with different incomplete rates

3.4 實驗結果與分析從這些實驗結果中能夠得出以下結論.

（1）本文所提方法在大多數指標上都優于其他七種方法，尤其在有二個視圖的Multi-Fashion數據集上，該方法的準確率比第二優的方法大約高7%.表明本文提出的方法在多視圖聚類任務中取得了顯著的改進效果.橫向比較所有結果發現，缺失視圖對多視圖學習的影響非常大.較高的缺失率通常會導致較差的學習結果，這是因為缺失視圖削弱了原始多視圖中豐富的語義信息.然而，和其他方法相比，本文方法在缺失視圖的情況下性能下降較緩，這表明該方法對缺失視圖相對不敏感.其主要原因是多階近鄰圖通過多次迭代計算多階近鄰關系，可以在多個視圖之間進行信息的交互，更好地捕捉到樣本之間的潛在依賴和重要關系，更準確地刻畫數據的結構，從而更好地消除缺失視圖帶來的負面影響.

（2）在大多數情況下，基于傳統機器學習的不完整多視圖聚類方法的效果比基于深度學習的方法聚類的效果差，因為深度學習模型通過多個隱層的連接和非線性變換，能夠逐漸構建多層次的抽象表示，可以從原始輸入數據中學習到更具有代表性的特征表示.與其他深度多視圖聚類方法不同，本文采用Transformer 作為基礎模型，能夠在特征表示過程中自動學習到不同視圖之間的依賴關系和重要性，進而可以更好地捕捉到多視圖數據中不同視圖之間的相關性和互補性.

（3）和只考慮一階近鄰關系的UEAF 方法相比，本文方法的效果更好，因為本文擴展了引入多階近鄰關系的思想.通過考慮多階近鄰關系，DMNC 能夠更全面地捕捉數據中樣本之間的聯系和結構.同時，多階近鄰關系允許本文在建模過程中考慮更長的依賴關系，從而更準確地刻畫數據的結構.最重要的是，多階近鄰關系的引入有助于改善聚類結果的連通性，通過考慮多階近鄰關系，能夠更好地將相似的樣本彼此連接起來，并且減少不相似樣本之間的連接.這可以有效地提高聚類的連貫性和一致性，使得聚類結果更加合理和可解釋.

（4）與其他數據集相比，本文的方法在Caltech7 數據集上的提升較少.這是因為Caltech7 數據集中各類樣本的數量較少，深度學習方法在這種情況下的效果并不明顯.另外，其他方法在該數據集上的提升效果也不顯著，這說明該數據集本身較難被聚類.因此，本文方法對于該數據集的優化能力有限.

3.5 參數敏感性分析及消融研究以50%缺失率的不完整多視圖數據集MNIST-USPS 為例，評估超參數對聚類性能的影響.DMNC 的超參數包括近鄰數K和權衡系數β，為了評估算法對K和β的敏感性，K設置為{20，40，60，80，100}，β設置為{0.01，0.1，1，10，100}.如圖4 所示，可以發現DMNC 對K的選擇具有魯棒性.此外，選擇一個好的β將顯著提高DMNC 的性能.

圖4 在MNIST-USPS 數據集上的參數敏感性分析實驗Fig.4 Parameter analysis on MNIST-USPS

其次，為了評估不同階近鄰關系對模型性能的影響，設置了不同階數的對比實驗，將近鄰約束的階數設置在零階至四階內，如表6 所示.其中，零階表示不帶有近鄰約束項，一階表示傳統K 近鄰約束.從表可見，三階互補近鄰圖獲得了最好的聚類性能.

表6 在MNIST-USPS 數據集上采用不同階近鄰關系時DMNC 算法的性能比較Table 6 Performance of DMNC with different orders of neighborhood relationships on MNIST-USPS

3.6 收斂性分析及可視化為了證明DMNC 的收斂性，在MNIST-USPS 數據集上進行實驗，缺失率p固定為50%.圖5 展示了隨著迭代次數的增加，損失值和聚類性能的變化.由圖可見，損失值不斷下降直到收斂.同時，ACC，NMI和Purity的值也隨著迭代次數的增加逐漸增加，最后趨于穩定，這些結果證明了DMNC 的收斂性.

圖5 DMNC 在MNIST-USPS 數據集上的收斂曲線Fig.5 Convergence curves of DMNC on MNIST-USPS

此外，隨著迭代次數增加，本文使用t-SNE［43］對學習到的特征進行可視化.如圖6 所示，隨著迭代次數增加，集群結構變得更加緊湊和分離.這些結果驗證了近似完整的多階近鄰圖可以指導編碼器提取更緊致、更有判別性的高級語義特征.

圖6 對MNIST-USPS 數據集的聚類可視化Fig.6 Multi-view clustering visualization on MNISTUSPS

4 結論

本文同時考慮到多視圖的互補性、一致性及視圖內的結構信息提出一種針對不完整多視圖問題的深度聚類方法，在利用基于Transformer 的深度自編碼器進行交叉視圖間信息交互的同時引入加權融合層獲取多視圖公共表示.同時，利用視圖內不同階的潛在結構信息，構建近似完整的多階近鄰圖，指導編碼器提取更緊致、更有判別性的高級語義特征.在多個數據集上的實驗結果證明了本文方法的有效性.

本文提出的模型只是在一些基準數據集上取得了良好的結果，并沒有將其應用到更實際的數據集上.同時，在構建多階近鄰圖時只利用了可見的視圖，下一步工作是研究新的策略將重構數據融入構建多階近鄰圖中并解決兩階段優化問題.