結合地標點與自編碼的快速多視圖聚類網絡

馬睿，周治平

（江南大學 物聯網技術應用教育部工程研究中心，江蘇 無錫 214122）

聚類作為一種無監督的學習方法可將給定的數據集根據數據的內在聯系劃分成多個集內相似度高而集間相似度低的子集，獲得了數據挖掘、模式識別、圖像分割等諸多領域的關注[1]。并且由于現實世界中多視圖數據的普遍存在，例如，文檔可以由不同語言來編寫，基因可由不同技術來測量[2]。充分利用多視圖數據以探索到更豐富、全面的數據特征從而獲得更好的性能也成為聚類發展的方向。

多視圖子空間聚類由于其優越的性能和豐富的可擴展性得到了飛速發展[3]。例如，Cao 等[4]在各個視圖之間利用希爾伯特施密特獨立性準則(HSIC)進行視圖間相互約束，從而捕獲到更豐富的數據關系。Wang 等[5]通過新穎的位置感知準則來利用多個視圖的互補信息，同時通過一致性約束來獲得多個視圖的通用聚類指示矩陣。Brbic等[6]在生成多個視圖的聯合親和度矩陣時利用低秩稀疏進行約束，并將方法擴展到核空間以適用于非線性數據。Nie 等[7]通過避免引入超參數的完全自動加權方案來為每個視圖分配不同的權重以區分不同視圖的重要性。Wang 等[8]試圖通過整合編碼的補充信息，利用具有最大依賴性的空間學習技術來形成多視圖的信息豐富的完整感知相似性。Li 等[9]通過將潛在表示強制構造為最大程度接近多個視圖的形式從而能夠靈活地編碼來自不同視圖的互補信息。隨著科技迅速發展，網絡數據量也隨之劇烈膨脹并越發呈現紛繁復雜狀態。例如，Facebook 每月約報告60 億張新照片，YouTube 每分鐘約上傳72 小時的視頻。而聚類分析的主要任務之一就是對大規模數據集進行無監督分類[10]。雖然上述多視圖聚類方法相較于單視圖聚類方法在聚類精度方面有了質的提升，但是它們都呈現出較高的計算復雜度，從而在大規模數據集上的使用具有局限性[11]。

為了提升面向大規模數據集的可擴展性，亟需找到一種優質的能降低計算復雜度的聚類算法，為了解決這一問題，He 等[12]利用隨機傅里葉特征來顯式表示內核空間中的數據，顯式特征映射可顯著加快特征向量近似，從而提高譜聚類預測速度。Tian 等[13]發現自編碼器和譜聚類本質上都是在保留原始數據最重要數據特征的同時實現降維處理，因此運用自編碼器來替代譜聚類中的拉普拉斯矩陣特征分解，對于大規模數據集來說，這一處理極大地減少了內存消耗，但此方法仍需要直接處理規模龐大的數據。因此Yin 等[14]提出了一種具有局部相似性表示的基于地標的光譜聚類方法，該方法首先通過使用給定的相似度函數對原始數據點的“最相似”地標進行編碼，然后對編碼數據點進行奇異值分解以得到頻譜嵌入數據點，再利用傳統聚類方法例如K-means 對嵌入數據點進行劃分。Banijamali 等[15]將地標表示與非線性低維映射相結合，同時避免了直接處理大規模數據集與拉普拉斯矩陣特征分解步驟，實現了更精確的快速聚類方法。雖然上述基于譜聚類的擴展算法十分有效地降低了譜聚類的計算量，但它們都是針對單視圖譜聚類進行的，對于多視圖學習場景顯然無能為力。

綜上所述，本文提出一種結合地標點和自編碼的快速多視圖聚類方法。為了提取大規模數據集中的強代表性點以降低存儲開銷，首先利用加權PageRank 排序算法在每個視圖中選取原始數據中權重較高的數據點作為每個視圖的地標點，為了避免傳統的手工生成相似度矩陣中指數函數與近鄰點個數的選擇，本文利用凸二次規劃函數直接從數據中獲得每個視圖的相似度矩陣，融合多視圖信息，將生成的多視圖共識相似度矩陣作為自編碼器的輸入，利用自編碼器替代拉普拉斯矩陣特征分解獲得多視圖數據的聯合嵌入表示，最后利用K-means 算法進行最后的聚類劃分。為了避免微調環節覆蓋之前所得最優參數從而獲得更精確的聚類結果，本文將自編碼器的重建損失和聚類損失放在同一學習框架下從而能夠對自編碼器的參數和聚類中心進行聯合更新。

1 相關算法理論

1.1 多視圖子空間聚類

鑒于融合多視圖數據以捕獲到更全面的聚類有效信息是十分有必要的，多視圖子空間聚類最近獲得了大量關注。給出多視圖數據

根據自表示思想通過一個稀疏系數矩陣重構原始數據，則多視圖子空間聚類網絡的目標函數為

式中：Si為第i個視圖的相似度矩陣，不同形式的f(·)可以給出不同性質的解。例如，文獻[4]利用HSIC 鼓勵圖對之間的差異性，文獻[6]利用低秩稀疏對相似度矩陣Si進行約束，文獻[9]生成了一個潛在的表示空間以靈活編碼多視圖信息。但是所有這些多視圖子空間聚類方法每個視圖的相似度矩陣Si的大小都為n×n，從而都至少需要O(n2k)的時間，且都涉及拉普拉斯矩陣特征分解，因此具有計算效率以及存儲空間上的劣勢，使其很難擴展到樣本點n數量龐大的大規模數據集上。

1.2 錨圖構造

相似度矩陣的構造對于譜聚類來說非常重要，對于構造大規模數據集的相似度矩陣，錨圖是一種十分有效的方法[16]。

利用K-means 或隨機選擇等方法從含有n個樣本點的數據集中提取出具有m(m?n)個樣本點的子集，每個子集中的點作為地標點來逼近原數據集，引入k近鄰點來度量點對之間的局部親和力。利用地標點與原數據來構造一個稀疏相似度矩陣Z∈Rn×m:

式中：〈i〉表示xi的r(r

然而此啟發式策略存在一個總是被忽略的固有缺點，即所構建的圖形質量很大程度依賴于指數函數和近鄰點個數r的選擇，因此，下游任務可能會受到負面影響。

2 結合地標點與自編碼的快速多視圖聚類算法

2.1 圖形構造

大規模數據集中存在很多冗余數據，少量樣本完全滿足重建子空間的需求。傳統的地標點選擇方法有文獻[15]中的隨機抽樣和使用K均值中心點作為地標點的方法。但是隨機抽樣可能導致地標點彼此過于靠近，這可能導致鄰域重疊。而采用K均值中心作為地標點的方法運行時間過長且當數據規模極大，超出系統的內存時，K均值聚類算法需要不斷地執行讀取操作[17]。因此，本文采用文獻[18]中的加權PageRank算法來為每個視圖選擇wpr值最高的m個樣本點作為地標點。

為了避免式(2)形式生成相似度矩陣的不足之處，本文在多視圖聚類框架下采取直接從數據生成相似度矩陣的方法，該方法不僅能揭示數據低維結構，還對噪聲和數據規模有著極強的魯棒性。在多視圖思想下利用重構誤差和約束項建立采用地標點的多視圖聚類模型目標函數：

式中：V為從不同來源或者利用不同收集方式獲取到的視圖總個數；Xv、Av、Zv分別為第v個視圖的原始數據矩陣、地標點矩陣、相似度矩陣。因為無需設置近鄰點，該形式生成的相似度矩陣不再受困于只能捕獲到數據的局部分布這一桎梏，并能完整感知數據從而保留數據的全局結構?？梢钥闯?，與式(2)相比，對于每個視圖，本方法只需在mn個數據點之間計算相似度矩陣而非傳統子空間聚類中的n2個數據點。對于大規模數據集來說，此舉可在利用多視圖一致性與互補性確保聚類精度的同時使復雜度顯著降低。

由于現實世界中數據的固有結構呈現出普遍非線性狀態[19]，將式(3)擴展到核空間中進行。定義φ:RD→H為從原始輸入空間到核希爾伯特空間 H 的映射，對于每個包含n個樣本點的視圖，其變換后形式為

由m個地標點構成的強代表性數據矩陣的變換后形式為

核函數定義為

則式(3)可轉變為

通過求解式(4)可以捕獲到φ(x)與φ(a)間的線性稀疏關系，即樣本點x與地標點a間的非線性關系。將式(4)按列重新寫出：

進而式(5)可轉變成為二次型形式(6)，從而能直接通過凸二次規劃函數求解得到各個視圖的由數據直接生成的相似度矩陣Zv：

2.2 聯合優化框架

自編碼器是一種利用非線性變換函數fi將原始輸入xi映射到低維嵌入空間，獲得嵌入表示hi，再通過另一映射函數gw’對hi進行解碼重構，通過最小化原始輸入xi與嵌入表示hi的重構輸出yi之間的重構損失Lr來迭代更新的人工神經網絡[14]，其均值誤差測量形式目標函數為

文獻[15]同樣利用自編碼器來配合聚類，然而其僅在聚類步驟前簡單疊加無監督深度學習框架，這樣形成的低維嵌入空間可能反而會損壞聚類分配效果。為此本文將聚類步驟和表示學習統一到一個基于KL 散度的利用損失函數迭代更新自編碼器參數{M1、M2；θ1、θ2}和聚類中心cj的聯合學習框架中，從而能聯合優化聚類標簽的分配和特征的學習，也使位于自編碼器隱藏層的低維特征能夠最大限度的保留原始數據的固有局部結構。將聚類損失目標函數定義為

式中：Q為由t-SNE 測量的軟標簽的分布；P為由Q導出的目標分布。KL 散度衡量了兩種不同分布之間的差異性，若對其進行最小化則能使得目標分布P能夠盡可能接近聚類輸出分布Q。qij表示根據t-SNE 測量得到的嵌入表示hi與聚類中心cj的相似程度[14]，其表達式如下：

pij則是由qij確定的目標分布：

因此，總體的優化目標函數為

其中，λ(0<λ<1)為控制嵌入空間失真程度的平衡參數。則根據mini-batch 隨機梯度算法反向傳播逐層訓練網絡后計算出的聚類損失Lc關于嵌入表示hi和聚類中心cj的梯度計算公式為

給定m為小批量樣本數，η為學習速率，編碼器權重M1、譯碼器權重M2、聚類中心cj的更新公式分別為

當連續兩次更新的類標簽分配之間的變化率小于給定的閾值 δ時迭代停止。

2.3 算法流程圖

結合地標點與自編碼的快速多視圖聚類網絡算法流程如圖1 所示。

圖1 所提算法流程圖Fig.1 Flow chart of the proposed algorithm

2.4 算法復雜度分析

當有v個視圖，每個視圖有n個樣本點，每個視圖的地標點個數為m時 ：1)利用加權PageRank算法為每個視圖進行地標點選擇，因此本文地標點選擇步驟的時間復雜度為O(vtmn)，t為生成每個樣本點的wpr 的迭代次數；2)構造多個視圖的相似度矩陣，DiMSC 和FMR 等多視圖子空間聚類方法由于未進行1) 地標點選擇，在2) 中DiMSC 和FMR 算法構造的每個視圖的自表示矩陣圖形大小均為n×n，二者的計算復雜度分別為O(Tvn3+vdn2)、O(T(L+1))(n3+kn2)，其中L表示FMR 算法中涉及的梯度下降法的迭代次數，T為DiMSC、FMR 算法總迭代次數。當數據規模n很大時，L、T?n，因此DiMSC 和FMR 算法步驟2)的計算復雜度均可視為O(n3)，這遠遠高于本文算法的m×n(m?n)圖形的計算復雜度O(vnm3)。3) 聚類步驟，DiMSC 和FMR 算法的步驟3)采用常規譜聚類，涉及到n2圖的拉普拉斯矩陣特征分解，需要消耗O(n3)的時間復雜度，且存儲開銷極大。而所提算法采用自編碼器替代拉普拉斯矩陣特征分解步驟，自編碼器參數和聚類中心聯合更新，僅需O(nD2+ndk)的時間，其中D為自編碼器隱藏層的最大單元數，d為自編碼器中間層的維數，k為簇數，與此同時存儲開銷也被大大降低。因為通常k?d?D，所以本文所提算法的總體時間復雜度為O(vtpn+vnm3+nD2)。可以看出，本文提出的采用地標點的快速多視圖聚類網絡的總體時間復雜度為樣本點數n的線性次方，而DiMSC 和FMR 聚類算法的總體時間復雜度為樣本點數n的三次方。表1 給出了所提算法與多視圖聚類算法DiMSC、FMR 的時間復雜度對比結果。與通常的多視圖聚類算法相比本文算法的效率大大提升，且所需的存儲開銷顯著降低，從而可更適用于大規模數據集。

表1 不同方法時間復雜度對比Table1 Complexity analysis of different methods

3 實驗與結果分析

3.1 實驗環境及評價指標

為了證明本文所提方法對大規模多視圖數據的適用性，選取100leaves、Handwritten（HW）、Caltech101-7/20、NUS-WIDE-Object (NUS)五個大規模的多視圖數據集進行實驗，每個數據集樣本點數都在1000 以上，表2 為5個大規模多視圖數據集的詳細介紹，其中V為多視圖數據集的視圖編號。本文算法實驗是在python3.7 運行，計算機配置為Intel Core i5CPU 1.6 GHz、4 GB 內存，操作系統為macOS Catalina。

表2 數據集介紹Table2 Description of the datasets

將本文方法所得聚類結果與樣本真實標簽進行比較，利用聚類準確率(ACC)、標準化互信息(NMI)和運行時間(Time)來作為性能評估指標，ACC 和NMI 取值均在0～1，值越大說明聚類性能越佳，運行時間越短說明算法越具有普遍適用性，即越適用于大規模數據集。

3.2 數據集及對比算法

為證明本文提出的算法的有效性，將其分別與單視圖聚類算法和多視圖聚類算法進行對比，對比單視圖聚類算法分別為文獻[21]中的傳統單視圖譜聚類算法SC 和文獻[15]中的使用K均值進行地標點選擇后利用嵌入表示替代拉普拉斯矩陣分解步驟的SCAL-K，同時與4個近期出現的性能優異的多視圖聚類算法DiMSC[4]、MLRSSC[6]、MSC_IAS[8]、FMR[10]進行對比。

為保證算法對比的公平性，所有對比算法都遵從算法原論文的實驗設置，并調試參數獲得其最優值。文獻[15]中的SCAL-K 算法及本文算法的自編碼器部分的編碼器維度設置為p-500-500-2000-10，解碼器部分為編碼器的鏡像，最小批量樣本數設置為256，初始學習速率 η設為 0.1，停止閾值設置為h=10?3，并把控制嵌入空間失真程度的平衡參數 λ設置為 0.1。對于兩個單視圖聚類算法，在數據集的每個視圖上運行實驗后取多個視圖里的最佳結果展示。

3.3 實驗結果分析

各個算法在5個數據集上的實驗結果如表3～7所示。實驗結果ACC 和NMI 中的性能最優異項被加黑標出。

表3 不同算法在100leaves 數據集上的表現Table3 Performance of different algorithms on the 100leaves dataset

表4 不同算法在Handwritten 數據集上的表現Table4 Performance of different algorithms on the Handwritten dataset

表5 不同算法在Caltech101-7 數據集上的表現Table5 Performance of different algorithms on the Caltech101-7 dataset

本文算法主要針對多視圖聚類算法運行效率進行研究，可以看出，本文所提算法在表3～6的4個大規模多視圖數據集上的運行速度均快于多視圖聚類算法MLRSSC、MSC_IS、DiMSC、FMR，在表7 的NUS 數據集上同樣快于多視圖聚類算法MSC_IS。并且可以看出，在越大型的數據集上本文所提算法在運行時間上的優越性愈加明顯，甚至可以達到相較于傳統多視圖聚類算法快幾個數量級的效果，例如在NUS 數據集上MSC_IS 算法需要36 749.39 s 運行時間而本算法僅需586.61 s。因為執行時間的波動主要受選取的地標點個數m的影響，而100leaves 數據集取得最佳聚類結果時采用的地標點個數在幾個數據集中為最小值，因此所提算法在100leaves 數據集上的運行時間最短。并且，同時采用了地標點與深度嵌入的單視圖聚類算法SCAL-K(best)在多個數據集上的速度也快于SC(best)。上述現象均說明了采用地標點和嵌入表示替代矩陣分解對提升聚類算法運行速度的有效性。此外，當面對例如NUS 等每個視圖的樣本點數n超過10000 的數據集時，多種多視圖聚類算法例如MLRSSC、DiMSC、FMR 會由于超出存儲空間而無法得到實驗結果，因此表7 僅給出了SC(best)、SCAL-K(best)、MSC_IS 的對比實驗結果，與之相反的是本文所提算法在5個多視圖數據集上均能得到實驗結果，這證明了本文所提算法需要相較于傳統多視圖聚類算法更低的存儲開銷與計算復雜度。上述現象均證明了本算法較傳統多視圖聚類算法對大規模數據集具有更強的適用性。

表6 不同算法在Caltech101-20 數據集上的表現Table6 Performance of different algorithms on the Caltech101-20 dataset

表7 不同算法在NUS 數據集上的表現Table7 Performance of different algorithms on the NUS dataset

本文所提算法的性能在ACC 方面始終具有明顯的優越性，均取得了所有實驗算法結果ACC中的最大值，分別在100leaves、HW、Caltech101-7、Caltech101-20、NUS 上超過了第二佳算法1.3%、1.27%、21.3%、4.0%、1.75%。而NMI 方面本文算法同樣可實現與其他多視圖聚類算法相當甚至更好的性能，這證明了本文算法的一致性與穩定性?？梢缘贸?，本文所提出的采用地標點的快速多視圖聚類算法在大幅度提升聚類速度的同時仍能夠保持較好的聚類精確度。

為了進一步研究改進，本文在Handwritten 數據集上使用t-SNE 進行了二維可視化對比研究。圖2(a)為本文算法的聚類結果視圖，圖2(b)為對比的利用給定標簽生成的可視化結果，其中t-SNE_1、t-SNE_2 代表分別采用經t-SNE 方法降維后的二維數據的第1 列和第2 列數據作為可視化呈現的x軸和y軸。可以看出，雖然仍有少部分數據點未進行正確的聚類劃分，但總體上本文算法可以良好地反映聚類結構，從而進一步證明本文算法可以在提升大規模數據集算法效率的同時保持較好的聚類精確度。

圖2 Handwritten 數據集實驗結果t-SNE 可視化Fig.2 Visualization of experimental results on the Handwritten dataset with t-SNE

由于所提方法采用地標點進行原數據重建，地標點個數m越少所提算法的運行時間就越短，但算法的精度卻不一定和地標點個數m呈線性關系。因此本文作了敏感分析實驗，以100leaves、Handwritten、Caltech101-7 等3個數據集的ACC為例，調整地標點個數m，圖3 給出了模型對地標點個數的敏感性。可以看出，地標點個數m太少時難以完整代表原數據所有特征，而當地標點個數m過多時會使其本身的代表性降低并引入額外的錯誤從而導致性能變差。

圖3 地標點敏感實驗結果Fig.3 Results of landmark sensitive experiments

4 結束語

本文提出了一種結合地標表示和自編碼器的多視圖快速聚類方法，在多視圖的框架下利用了加權PageRank方法選擇地標點以減少存儲開銷，通過所選擇的地標點重構原始多視圖數據直接得到多視圖共識相似度矩陣，在降低了計算復雜度的同時充分利用了多個視圖中具有互補性與一致性的聚類有效信息，利用自編碼器替代拉普拉斯矩陣特征分解，聯合更新自編碼器參數以及聚類中心，以保證聚類精度。在5個多視圖數據集上的實驗證明本文所提算法擁有良好的性能。但是本文中多個視圖的信息僅是通過簡單的相加來融合而并未進行視圖差異區分，在未來，致力于進一步研究如何在保證計算速度的情況下更好將多個視圖的信息具有區分性地融合，以更好地提升聚類性能。