基于多變量自學習與融合策略的多視圖聚類算法*

尚曉群 楊海峰 蔡江輝

（太原科技大學計算機科學與技術學院 太原 030024）

1 引言

來自不同數據源的數據類型（如文本、圖像、視頻等）描述同一對象或主題，形成了多視圖數據［1～3］。例如，一個多媒體片段可由視頻信號和音頻信號同時描述；一個網頁的特征可通過文檔文本、超鏈接、圖片信息等表示；一張圖片可通過不同的特征提取器捕獲其相應的表示，如LBP、SIFT、HOG等。多視圖數據的爆炸性增長，引發了對其進行有效分析和處理的技術需求增長。在數據挖掘中，聚類分析［4］是一項非常重要的技術，能將相似度高的數據劃分到一個簇。在過去的幾十年里，許多的聚類方法已經被發展，如K-means，譜聚類，基于核的聚類方法，基于圖的聚類方法和基于密度的聚類方法。旨在利用跨視圖間數據的互補性和一致性信息，多視圖聚類方法［5～6］已引起廣泛的關注。

現有的多視圖聚類方法主要分為五類：協同訓練風格算法、多核學習、多視圖圖形聚類、多視圖子空間聚類、多任務多視圖聚類［7］。此外，多視圖圖形聚類被進一步劃分為基于圖形、基于網絡和基于譜論；多視圖子空間聚類被進一步劃分為基于子空間學習和基于非負矩陣分解。由于多視圖聚類的可擴展性，許多學者做了進一步的研究。楊敏申等［8］在k-means 聚類過程中進行特征降維，改進了多視圖k-means聚類。王浩等［9］對基于圖形的多視圖聚類在通用方法和圖形度量兩個方面進行研究，提出了一個基于圖形的多視圖聚類系統GBS。

盡管現有的多視圖聚類算法已在不同方面被改進與完善，且取得了不錯的聚類結果，但是，合理挖掘視圖的一致性信息和互補性信息依然是目前多視圖聚類研究的難題與挑戰。針對這個問題，本文提出一種新穎的多視圖聚類算法MSFC，基于多變量自學習與融合策略過程如圖1 所示，該算法自學習數據集對應的視圖內全局變量、視圖內局部變量和視圖間變量，并將其整體投射于一個相似性度量函數，獲取融合矩陣，以得到更加準確的聚類結果。

圖1 基于多變量自學習與融合策略過程

2 理論基礎

2.1 信息熵

信息熵［10～11］是一種信息的度量化方法，基本思想是：用信息量度量信息的多少，再對產生的信息量作期望。對于一個離散隨機變量X，所有狀態為｛x1，x2，…，xn｝，當狀態為xi時，對應的概率為pi，則X的信息熵可以被定義為

其中不確定性函數H 是概率pi的減函數，即當概率大時，不確定性??；反之，不確定性就大。信息熵反映了離散隨機事件的出現概率。

2.2 譜聚類

譜聚類方法［12～13］可歸納為以下三個主要步驟：1）構建數據集的相似度矩陣W；2）通過相似度矩陣，計算度矩陣和拉普拉斯矩陣的前k 個特征值與特征向量，構建特征向量空間；3）利用k-means 或其它經典聚類算法對特征向量空間中的特征向量進行聚類。假設數據集X 有c 個簇，譜聚類的目標函數：

Y=［y1，y2，y3，…yn］T∈Rn×c是聚類指示矩陣，Y∈Idx表示每個樣本的類標簽向量，即向量yi∈｛0，1｝c×1只包含一個元素1，其他的元素均為0。由于在Y上施加離散約束會導致NP 難問題，為了解決這個問題，對Y 松弛化，得到連續的聚類指示矩陣F=［f1，f2，f3，…，fn］T∈Rn×c，目標函數轉換為

FTF=IC是正交約束，F 的最優解決方法是包含拉普拉斯矩陣L 的c 個最小特征值對應的c 個特征向量。

3 基于多變量自學習與融合策略的多視圖聚類算法

3.1 基本思想

本算法相繼自學習三種多視圖數據的變量，即視圖內全局變量、視圖內局部變量和視圖間變量。為了充分捕獲多視圖數據的信息，本算法使用信息熵理論來自學習多變量，充分考慮特征與特征、特征與視圖和視圖與視圖的潛在關系。

給定多視圖數據X=｛x1，x2，…，xn｝∈Rd×n，其中，d表示每個樣例的屬性維數，n表示樣本個數，X 的第（i，j）項、第i 個樣本、第j 個屬性分別用xij、xi和xj表示，s表示視圖個數，c表示多視圖數據的類個數。

視圖內全局變量：首先，對于各視圖的每個屬性，計算所有樣本與均值的偏離程度gij，然后，依據偏離程度和聚類個數，得到視圖內全局變量中每個項的Gij，其計算公式為

其中，m 是當前視圖第j個屬性的所有樣本的均值，l是該項所在屬性的最小偏離值，b是該項所在屬性的最大偏離值。

視圖內局部變量：根據視圖內全局變量和信息熵理論，視圖內局部變量中每個屬性對應的值可被定義為

果實受到病蟲害和鳥類危害之后會嚴重影響到果實的外部商品性能，還會導致果樹出現落果現象，影響到果實質量，從而給養殖戶造成更多的額外損失。為了有效預防上述情況發生，在果實形成之后對果實進行套袋處理，能夠有效避免上述多種因素損害，同時，還能夠保持果實應有的色彩和飽滿度。果實套袋時間要結合不同果樹品種綜合選擇，一般情況下，果實套袋時間應該在果實進入膨大期后進行。

其中，r 是k 在當前屬性中出現的總次數占所有樣本個數的比值。

視圖間變量：基于每個視圖的視圖內全局變量、視圖內局部變量和該視圖中屬性數目占所有視圖屬性數目的比例，定義視圖間變量中每個視圖對應的值，如下所示：

其中，b為所有視圖特征的總個數。

融合：相似性度量函數計算公式如下：

通過式（8），可得到多視圖數據的融合矩陣。在此基礎上，構建鄰接矩陣W。首先，使用K 近鄰方法計算中間矩陣P，其基本思想是，若樣本點i屬于樣本點j 的k 近鄰樣本或樣本點j 屬于樣本點i 的k 近鄰樣本，則對應的P 矩陣項設為1，否則，為0，公式為

其中，KNN（xi）表示樣本xi的k 個近鄰樣本。然后，由中間矩陣P形成最終鄰接矩陣W，其計算公式為

3.2 算法描述

基于多變量自學習與融合策略的多視圖聚類算法首先根據聚類數目，通過式（4）和式（5）獲取每個視圖的視圖內全局變量；基于視圖內全局變量和信息熵理論，使用式（6）計算每個視圖的視圖內局部變量；在此前計算的基礎上，利用式（7）獲取視圖間變量。其次，相似性度量函數將基于數據集自學習的多個變量融合為一個矩陣。之后，運用式（9）、式（10）、式（11）相繼計算鄰接矩陣、度矩陣和拉普拉斯矩陣。通過k-means 獲得最終的聚類結果。具體步驟如下：

本文的算法內容主要包括兩個部分，第一部分是多變量自學習與融合，第二部分為獲取聚類標簽過程。多變量自學習與融合的時間復雜度為O（n2），獲取聚類標簽過程的時間復雜度為O（n2），算法的整體時間復雜度為O（n2）。

4 實驗分析

在1 臺Intel（R）Core（TM）i5-8250U CPU @1.60GHz 筆記本電腦，Windows 10 操作系統中使用Python語言在Anaconda2的Spyder4.1.5平臺實現了基于多變量自學習與融合策略的多視圖聚類算法。

4.1 實驗設置

本實驗采用5 個數據集評估提出的MSFC 算法，包括Handwritten（手寫數字0～9 的多視圖數據集，共6 個視圖）、Anuran Calls（青蛙音節的特征數據集，共兩個視圖）、IS（室外圖像數據集，共兩個視圖）、Cloud（AVHRR 圖像數據集，共兩個視圖）、3sources（多視圖文本數據集，共3 個視圖）。將所提算法與6 個多視圖聚類算法進行比較，包括AASC［14］（親和性聚合譜聚類算法）、RMSC［15］（通過低秩和稀疏分解實現的魯棒多視圖譜聚類算法）、MVGL［16］（圖學習的多視圖聚類算法）、AWP［17］（通過自適應加權普氏分析的多視圖聚類算法）、WMSC［18］（基于譜擾動的加權多視圖譜聚類）、MCGC［19］（多視圖共識圖聚類算法）。為了有效評估各個聚類算法的性能，本實驗使用四種指標作為評估度量，包含ACC（準確率）、ARI（調整蘭德系數）、NMI（標準化互信息）和Purity（純度）。

對于多視圖對比算法，我們按照作者原文中給的參數設定分別運行，并選取參數范圍內對應的最佳聚類結果作為實驗的最終結果。在所有對比算法的實驗中，我們將最近鄰的數目kNN 均設置為6。對于帶有參數的算法：WMSC（兩個參數）、RMSC（1 個參數）、MCGC（1 個參數），這些算法的參數取值范圍為｛10-5，10-4，10-3，…，104，105｝m，其中，m為算法參數的數目。

4.2 實驗結果與分析

在本節中，在五個數據集上進行實驗來驗證基于多變量自學習與融合策略的多視圖聚類算法的有效性。表1、表2、表3 和表4 分別展示了四個評價指標的實驗結果。

表1 在各個數據集上的ACC實驗結果（%）；每列的最高分數用黑體標出

表2 在各個數據集上的ARI實驗結果（%）；每列的最高分數用黑體標出

表3 在各個數據集上的NMI實驗結果（%）；每列的最高分數用黑體標出

表4 在各個數據集上的Purity實驗結果（%）；每列的最高分數用黑體標出

從總體上來看，本章提出的基于多變量自學習與融合策略的多視圖聚類算法在多個多視圖數據集上均明顯優于所有的多視圖聚類基線方法（AASC，RMSC，MVGL，AWP，WMSC，MCGC）。相較于對比方法，MSFC 算法的優勢主要體現在以下兩個方面。一方面，多變量自學習合理提取了多視圖數據的潛在結構信息；另一方面，所提相似性度量函數有效度量了樣本之間的相似性關系，從而提升了聚類結果。

5 結語

本文提出了一種基于多變量自學習與融合策略的多視圖聚類算法，該算法通過聚類數目和信息熵，對多視圖數據的三種變量進行自學習，以充分利用視圖內與視圖間的潛在信息。在此基礎上，構建了一個新的相似性度量函數，進行多變量的融合。在多個數據集上的實驗結果表明，本文提出的MSFC 算法優于現有的多視圖聚類算法，驗證了該算法的可行性和優越性。本文下一步的研究方向為考慮如何能提高算法的運行速度，加快完成多視圖數據樣本分組的任務。