基于聯(lián)合熵的多視圖集成聚類分析

趙曉杰，牛雪瑩，張繼福

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

0 概述

多視圖聚類是將給定的多視圖數(shù)據(jù)依據(jù)相似性劃分為不同的簇，使得相同簇中的對象盡量相似，不同簇中的對象盡量不同［1］。多視圖數(shù)據(jù)可以使得問題描述的角度更全面，提供比傳統(tǒng)單視圖數(shù)據(jù)更豐富的信息來揭示其內在結構，并已成功應用于社交網(wǎng)絡［2-3］、多模態(tài)生物特征分析等領域［4-5］。多視圖集成聚類作為一類典型多視圖聚類分析方法，通過集成聚類的思想使多個視圖較弱的基本分區(qū)集成為一個較強的一致分區(qū)，并利用多個獨立的基聚類器分別對原始數(shù)據(jù)集進行聚類，然后使用某種集成策略獲得最終的聚類結果，其關鍵在于從特征融合轉移到分區(qū)融合，相較于特征融合更有利于單視圖高層信息的保持。但如何充分利用多視圖數(shù)據(jù)的一致性和互補性，是改善并提升多視圖集成聚類效果的關鍵。

分區(qū)融合策略是多視圖集成聚類的關鍵步驟之一，可分為視圖加權和簇加權兩種。視圖加權［6-7］主要是根據(jù)每個視圖的基聚類損失來確定每個視圖的權重，并將每個視圖視為一個整體，同一視圖中的基聚類簇被賦予相同的權重，而簇加權是根據(jù)每個視圖分區(qū)中基聚類簇的質量來確定權重的。簇加權可比視圖加權獲得更加詳細和靈活的信息，更有利于融合多視圖分區(qū)。目前，簇加權［8］主要采用基聚類簇內最小平均距離，更加緊密的、數(shù)據(jù)對象之間距離更小的簇被賦予高權重，稀疏的簇被賦予低權重。基聚類簇的疏密程度僅能體現(xiàn)數(shù)據(jù)本身分布特性，并不能反映簇質量優(yōu)劣，即基于最小平均距離的簇評價標準并不能很好地表示聚類質量優(yōu)劣。本文采用聯(lián)合熵估計多視圖聚類簇的不確定性，提出一種基于聯(lián)合熵的多視圖集成聚類算法。聯(lián)合熵體現(xiàn)了多視圖中所有基聚類簇的數(shù)據(jù)分布特征，保留了基聚類簇加權優(yōu)勢，體現(xiàn)了不同視圖相似對象構成的對應類簇存在差異性，有效地提升了多視圖集成聚類效果。本文設計基于聯(lián)合熵的基聚類簇質量評估方法，構造基于基聚類簇質量評估的加權共協(xié)矩陣，提出基于聯(lián)合熵的多視圖集成聚類算法（Multi-View Ensemble Clustering algorithm based on Joint Entropy，MVECJE）。

1 相關工作

多視圖聚類綜合了數(shù)據(jù)的多個視圖信息，獲得了優(yōu)于單視圖聚類的性能，已成為一個研究熱點［9-11］。多視圖聚類按照視圖的融合方式主要分為基于特征融合的多視圖聚類［12-15］和基于集成的多視圖聚類［16-19］兩大類。

基于特征融合的多視圖聚類分析的基本思想是將多視圖數(shù)據(jù)的多種特征表示融合成為一個單一表示，并應用傳統(tǒng)的聚類分析實現(xiàn)聚類分析任務，同時該類方法在聚類結果的解釋方面具有一定優(yōu)勢。典型的研究工作主要包括：文獻［20］利用正則相關分析的方法從多個視圖的特征中選取相關度最高的視圖，以此作為數(shù)據(jù)融合后的唯一表示；文獻［21］利用譜聚類將數(shù)據(jù)在每種視圖下都表示成一個圖，并為每個圖賦以權重，并用隨機游走的方法進行融合形成數(shù)據(jù)的唯一表示；文獻［22］提出一種多核K-means 算法來組合多視圖數(shù)據(jù)，并將此組合作為數(shù)據(jù)的最終表示；文獻［23］用一種核的方法給各視圖自適應地賦予權重，之后將這些加權的視圖融合為一個最終的表示。這類方法融合后的表示具有可解釋性強的特點，但大多依賴于融合前圖的初始化，而初始化圖的質量通常難以得到保障。

基于集成的多視圖聚類分析融合各個視圖的聚類結果。與特征融合不同，它們會保持數(shù)據(jù)的原始表示［24］。但在多視圖數(shù)據(jù)中，低質量視圖可能會影響最終的聚類性能，所以，在融合過程中不能平等地對待所有視圖的聚類結果。為了確定不同視圖對于最終聚類結果的貢獻，研究者提出了許多視圖加權的多視圖聚類方法：文獻［17］給每個視圖賦一個權重并給出一個超參數(shù)對權重進行約束；文獻［25］通過一個自加權的方法來給視圖自動賦權重，并且不需要額外的超參數(shù)。一般來說，大多數(shù)現(xiàn)有的視圖加權方法根據(jù)每個視圖的聚類損失來確定每個視圖的權重，以使損失較低的視圖具有較高的權重。但一個低損失的視圖不能保證其內部的簇就一定具有高質量，因為視圖加權是針對每個視圖整體的加權，視圖內部簇的質量好壞并不能在視圖權重上得到體現(xiàn)。所以，通過將每個視圖作為一個整體來粗略地分配權重，并不能反映一個視圖中各個簇的重要性。針對視圖加權的問題，一些研究者提出了基于距離對簇加權的多視圖聚類方法。這類方法雖然改進了視圖加權的方法，研究核心從視圖層面轉移到了簇層面，但以距離衡量簇內相似度的加權方式并不完善。因為視角的不同，簇的相似度是存在差異的，但不同視圖中對應簇的點是一樣的，在這種情況下，不同視圖下同樣點構成的簇由于相似度的不同，被賦予了不同的權重，不利于得到有效的相似度矩陣。

綜上所述，基于特征融合的多視圖聚類分析方法太過依賴初始圖的質量，基于集成的多視圖聚類分析方法則容易忽略視圖內部基聚類簇的質量，從而影響視圖內部基聚類簇局部特性的體現(xiàn)。

2 關鍵視圖與聯(lián)合熵

在多視圖聚類中，如何處理少數(shù)關鍵視圖是關鍵和核心，影響著多視圖聚類性能。文獻［6］通過折中稀疏權重與平均權重調整各視圖權重，從而保證了少數(shù)關鍵視圖信息，其基本概念描述如下：

假設一個多視圖數(shù)據(jù)集由V個視圖組成，每個視圖有N個實例，由表示，其中，表示來自第v個視圖的第i個實例，d(v)表示第v個視圖的特征維數(shù)。視圖中的實例在高維映射下可以表示為，這些實例將會被分成M個不相交的基聚類簇，其目標函數(shù)可表示為：

在式（1）中，當p→1時，僅選擇一個最佳視圖，而當p→∞時，每個視圖上權重ωv趨于相等。為了評判關鍵視圖，在聚類過程中嵌入一種核方法對多視圖重要性自動排序；然后，根據(jù)視圖排序對視圖賦予權重，這樣就在稀疏權重與平均權重之間進行了折中，從而避免了視圖賦權中極端情況的產生。盡管視圖權重體現(xiàn)了視圖整體的重要性，但視圖內部基聚類簇的重要性并未得到體現(xiàn)。

采用傳統(tǒng)聚類算法，在給定的輸入?yún)?shù)下，生成的若干類簇稱之為基聚類，基聚類中的每一個類簇稱之為基聚類簇，基聚類簇是由相似數(shù)據(jù)對象構成的一個數(shù)據(jù)子集［26］。為了使視圖內部基聚類簇的重要性得以體現(xiàn)，首先按照選取的聚類算法，按不同參數(shù)運行M次，生成M個基聚類，且每個基聚類中包含了若干基聚類簇。在基聚類的生成過程中，盡管選用了同一聚類算法在不同參數(shù)下產生基聚類，但在選擇聚類算法時，盡量選取輸入?yún)?shù)少，且在不同輸入?yún)?shù)下生成不同基聚類的算法，從而保證基聚類的多樣性。

MVKKM 是一種多核K-means 聚類算法［6］，僅有聚類個數(shù)k和視圖權重約束p兩個輸入?yún)?shù)，相比其他聚類算法，MVKKM 輸入?yún)?shù)少，且在不同參數(shù)下生成的聚類簇也不盡相同，從而保證了基聚類的多樣性。假定數(shù)據(jù)集O={o1，o2，…，oN}，其中，oi是第i個數(shù)據(jù)對象，N是數(shù)據(jù)集O中數(shù)據(jù)對象的個數(shù)。采用MVKKM 算法并選用M個不同參數(shù)對數(shù)據(jù)集O進行聚類，生成M個基聚類，每個基聚類由一定數(shù)量的基聚類簇組成。M個基聚類的集合表示如下：

其中：Π表示所有基聚類的集合；π（m）表示第m個基聚類中包含的n（m）個基聚類簇；表示π（m）中第n（m）個基聚類簇。

為了便于表示與計算，將所有基聚類中的基聚類簇表示為如下集合：

其中：Ci表示第i個基聚類簇；nc表示Π中所有基聚類簇的個數(shù)。

基聚類的形式化表示如下：

其中：π表示基聚類；p為參數(shù)，不同的p產生不同的基聚類π。

聯(lián)合熵是信息熵的推廣，用于對與一組隨機變量相關的不確定性進行度量，并具有以下特性：1）非負性，即一組隨機變量的聯(lián)合熵是一個非負數(shù)；2）高值性，即一組變量的聯(lián)合熵大于或等于該組變量的所有單個熵的最大值；3）低值性，即一組變量的聯(lián)合熵小于或等于該組變量各個熵的總和。相關概念定義如下：

對于一對離散隨機變量(X，Y)，聯(lián)合熵H(X，Y)定義如下：

其中：x和y分別是X和Y的特定值；p(x，y)是這些值產生交集時的聯(lián)合概率。

當且僅當隨機變量X和Y相互獨立時，則認為H(X，Y)=H(X)+H(Y)。因此，給定n個獨立的隨機變量X1，X2，…，Xn時，有：

3 多視圖集成聚類

3.1 基聚類簇質量評估

視圖權重主要針對分布稀疏性，只能體現(xiàn)視圖整體的重要性，并不能體現(xiàn)視圖內部基聚類簇的重要性，影響了多視圖聚類效果。為了使視圖內部基聚類簇的重要性得以體現(xiàn)，對由式（3）得到的基聚類簇集合中的每個簇進行不確定性分析。由式（5）可知，聯(lián)合熵度量了一組隨機變量的不確定性，而基聚類簇中的數(shù)據(jù)對象可看作一組隨機變量，因而聯(lián)合熵可有效刻畫基聚類簇的不確定性［26］。

對于由式（2）得到的基聚類集合Π，參照式（5），式（3）中的基聚類簇Ci相對于基聚類π(m)∈Π的不確定性描述如下：

由式（8）可知，對于任意的i、j和m，都有p(Ci，∈[0，1]，因而H(m)(Ci)∈［0，+∞）。當基聚類簇Ci中的所有數(shù)據(jù)對象都屬于π(m)中的同一基聚類簇時，Ci對π(m)的不確定性達到最小，即0；當基聚類簇Ci中的數(shù)據(jù)對象屬于π（m）中更多不同的基聚類簇時，Ci相對于π(m)的不確定性就會變大，表明Ci中的數(shù)據(jù)對象相對于π(m)不會出現(xiàn)在同一基聚類簇中。

對于任意的基聚類簇Ci，參照式（6），基聚類簇Ci對于基聚類集合Π的不確定性描述如下：

其中：M表示集合Π中基聚類的個數(shù)。

由式（9）可知，任意的基聚類簇Ci在集合Π中的不確定性，都有H(Π)(Ci)∈[0，+∞)。

為了將基聚類簇不確定性取值范圍控制在［0，1］之間，可采用指數(shù)函數(shù)對基聚類簇不確定性進行轉換，并將其定義為基聚類簇不確定性指數(shù)（Cluster Uncertainty Index，CUI），描述如下：

其中：M表示集合Π中基聚類的個數(shù)。

由式（10）可知：當基聚類簇Ci的不確定性為最小值0時，其CUI 值將達到最大值，即1；當基聚類簇Ci的不確定性趨于無窮時，其CUI 值趨近于0。

3.2 加權共協(xié)矩陣

共協(xié)矩陣描述了在基聚類集合中每一對數(shù)據(jù)出現(xiàn)在同一基聚類簇的頻率，可用來表征基聚類結構。雖然共協(xié)矩陣常應用于集成聚類分析中，但由于其平等地對待所有數(shù)據(jù)對象，因此未能有效地體現(xiàn)基聚類特性，影響了集成聚類性能。由式（10）可知，CUI 刻畫了基聚類中基聚類簇的不確定性，并且不同基聚類簇的CUI 值是不同的，因此以CUI 值作為權值，可使基聚類簇重要性得到有效體現(xiàn)。對于給定基聚類集合Π，參照文獻［27］共協(xié)矩陣的描述，加權共協(xié)矩陣定義如下：

在式（11）中，權值是由CUI 值來表征的，體現(xiàn)了基聚類簇重要性，CUI 值越大，基聚類簇越重要，反之亦然。

3.3 基聚類集成

依據(jù)式（11）定義的加權共協(xié)矩陣，可獲得多視圖集成聚類的一致劃分，并采用自底向上策略實現(xiàn)聚合聚類。假設每個數(shù)據(jù)對象是一個單獨的基聚類簇或區(qū)域，初始的N個數(shù)據(jù)對象視為N個初始區(qū)域，基本步驟如下：

2）根據(jù)基聚類簇間相似度S（t）將相似度最高的兩個區(qū)域合并成一個新的區(qū)域，并更新區(qū)域集。第t步中的區(qū)域集合描述如下：

其中：表示R(t)集合中的第i個區(qū)域；|R(t)|表示R(t)中的區(qū)域個數(shù)。

在區(qū)域合并后，將根據(jù)新的區(qū)域集合更新相似度矩陣，為下一次迭代過程做準備，迭代到第t步的相似度矩陣S(t)中的第（i，j）項描述如下：

3）當區(qū)域集合中的個數(shù)|R(t′)|=k時迭代終止，并將最后的區(qū)域集R(t′)作為最終的結果輸出。

在上述基聚類集成步驟中，采用聯(lián)合熵來評估基聚類簇的不確定性，并以CUI 值作為加權共協(xié)矩陣中的權值，以此構建新的初始相似度矩陣，體現(xiàn)重要數(shù)據(jù)對象的地位與作用。

3.4 基于聯(lián)合熵的多視圖集成聚類算法

依據(jù)上文所述，利用聯(lián)合熵，多視圖集成聚類分析基本思想為：首先針對各視圖數(shù)據(jù)，采用多核K-means 聚類MVKKM 算法生成基聚類集合；然后利用式（11）得到加權共協(xié)矩陣，并作為初始相似度矩陣；最后利用層次聚類思想，自底向上地聚合基聚類簇，進而得到最終的多視圖集成聚類簇。算法描述如下：

算法MVECJE

輸入多視圖數(shù)據(jù)集，k

輸出聚類結果R(t′)（|R(t′)|=k）

1.利用MVKKM 算法生成M個基聚類；

2.由式（9）計算基聚類集合中所有基聚類簇的不確定性；

3.由式（10）計算基聚類集合中所有基聚類簇的CUI 值；

4.由式（11）計算得到WWCA矩陣；

5.初始化相似度矩陣S(0)和區(qū)域集合R(0)，|R(0)|=N；

6.While |R(t)|＞k Do（t=1，2，…，N-1）

7.依據(jù)S(t-1)將R(t-1)中兩個相似度最高區(qū)域進行合并；

8.由式（12）、式（13）得到新的R(t)和S(t)；

9.End While

時間復雜度分析如下：MVECJE 算法中的主要操作包括生成基聚類與迭代生成基聚類簇。生成基聚類主要是利用MVKKM 算法，參照文獻［6］可知，時間復雜度為O(N2(V+τ)τ′)，其中，N為數(shù)據(jù)對象的個數(shù)，V為視圖個數(shù)，τ為核K-means 算法的迭代 次數(shù)，τ′為整體的迭代次數(shù)。生成基聚類簇的過程需要迭代t次，每次迭代后需要更新并保存相似度矩陣，時間復雜度為O(tN2)。因此，MVECJE 算法時間復雜度為

4 實驗分析

實驗環(huán)境：Intel?CoreTMi7-7700HQ CPU@2.80 GHz，8 GB內存，Windows 10。為了驗證MVECJE 算法的有效性，采 用NMI、ACC 和ARI 這3 個聚類性能指標［28］，對比算法為CoregSC［29］、AWGL［17］、MMSC［16］、DIMSC［13］、COMVSC［30］、MVKKM［6］和CWK2M［8］。選取4 個廣泛使用的多視圖數(shù)據(jù)集進行性能評估，即MSRC-v1、Caltech101-7和Handwritten numerals（HW）3 個圖像數(shù)據(jù)集和1 個Reuters 文本數(shù)據(jù)集，詳見表1，其中括號內的數(shù)字是特征維數(shù)。

表1 實驗數(shù)據(jù)集Table 1 Experimental datasets

4.1 聚類簇權重

為了進一步驗證簇權重在集成過程中的重要性，在MVECJE 算法中，刪除簇權重處理步驟，即對基聚類直接進行集成處理，并標記為MVEC_1 算法。對比在4 個數(shù)據(jù)集上的實驗結果，詳見表2，其中加粗數(shù)據(jù)表示最優(yōu)值，下同。

表2 聚類簇權重對聚類性能的影響Table 2 Effect of cluster weight on clustering performance

由表2 可知，聚類簇權重可以有效改善聚類性能，相對于MVECJE算法，MVEC_1 算法的3個聚類指標值都有不同程度的提高，其主要原因是利用聯(lián)合熵賦予的聚類簇權重，體現(xiàn)了各多視圖聚類簇的重要程度。

4.2 聚合迭代

為了驗證MVECJE 算法中聚合迭代次數(shù)對聚類性能的影響，以3 個評價指標值作為y軸、以迭代次數(shù)作為x軸繪制曲線。在表1 所示的4 個數(shù)據(jù)集上MVECJE 算法的NMI、ACC、ARI 聚類指標如圖1所示。

圖1 迭代次數(shù)對聚類性能的影響Fig.1 Effect of the number of iterations on clustering performance

由圖1 可知，隨著迭代次數(shù)的增加，體現(xiàn)聚類性能的NMI、ACC、ARI 聚類指標值逐步提升，且多視圖聚類性能也逐步趨于穩(wěn)定，其主要原因是在每次聚合迭代集成過程中，根據(jù)更新后的相似度矩陣合并了相似度高的聚類簇，隨著迭代次數(shù)的增加，聚類簇的變化也逐漸變小，并趨于穩(wěn)定。

4.3 聚類性能

為了驗證MVECJE 算法的聚類準確性，對同一數(shù)據(jù)集使用相同的內核：M=15。對MSRC-v1、Caltech101-7 和HW 數(shù)據(jù)集使用高斯核，并將標準差設置為每個視圖中數(shù)據(jù)對象之間成對的歐氏距離的中位數(shù)，對Reuters 數(shù)據(jù)集使用線性核。對于MVKKM 和CWK2M，參數(shù)p以對數(shù)形式進行搜索（lgp從0.1 到2，步長為0.2），而初始中心的選擇則通過全局核K-Means 算法來對每個視圖進行選擇。由于MVKKM 和CWK2M 的中心初始化是相對固定的，因此僅運行1次，其他對比算法則運行30次，并返回30 次結果的平均值。

由表3 可知，MVECJE 算法在4 個數(shù)據(jù)集上均表現(xiàn)出良好的聚類性能，尤其在Caltech101-7 和HW 數(shù)據(jù)集上優(yōu)勢最為明顯，而在MSRC-v1 和Reuters 數(shù)據(jù)集上，僅ACC 指標值略遜于CWK2M 算法。具體分析如下：

表3 多視圖聚類性能對比Table 3 Comparison of multi-view clustering performance

1）MVECJE 是一種集成聚類方法，提高了聚類結果的質量和健壯性，且充分利用了基聚類，并采用了基于聯(lián)合熵的簇評估方式，使得其具有良好的聚類性能。

2）CoregSC、AWGL 和MMSC 是基于譜聚類的多視圖聚類分析方法，聚類性能大多依賴于關聯(lián)矩陣的構造，但關聯(lián)矩陣的質量通常是難以保障的，而MVECJE 則不需要構造關聯(lián)矩陣這一過程，從而也體現(xiàn)了MVECJE 的優(yōu)越性。

3）DIMSC 和COMVSC 是基于子空間的多視圖聚類分析方法，且這兩種多視圖聚類分析方法都沒有進行加權操作，都將每個視圖同等對待。因此，視圖與視圖內部聚類簇的重要性將難以體現(xiàn)，而MVECJE 則是在聚類簇這一層面上進行的分析，從表3 中也可直觀看出，MVECJE 相比于DIMSC 和COMVSC 的優(yōu)勢是非常明顯的。

4）MVKKM 是一種視圖加權的多視圖聚類分析方法，而MVECJE 則是以聯(lián)合熵為基礎并對聚類簇加權的多視圖集成聚類算法。由于MVECJE 考慮了比MVKKM 更細粒度的權重，因此獲得了優(yōu)于MVKKM 的聚類性能。

5）CWK2M 和MVECJE 都是基于簇加權的多視圖聚類分析方法，但對簇加權的方式不同：CWK2M采用歐氏距離為簇加權，MVECJE 對簇聯(lián)合熵加權。MVECJE 算法在MSRC-v1 和Reuters 數(shù)據(jù)集上，僅ACC 指標值略遜于CWK2M 算法，這可能是因為數(shù)據(jù)集對象個數(shù)較少，無法有效地體現(xiàn)聯(lián)合熵加權的有效性。

為了驗證MVECJE 算法的聚類效率，采用表1所示的數(shù)據(jù)集，對不同算法的聚類效率進行對比，如表4 所示。

表4 聚類效率對比Table 4 Comparison of clustering efficiency 單位：s

由表4可知，除CoregSC 效率較高、CWK2M 效率較低以外，包括MVECJE 在內的其他算法聚類效率基本相同，主要原因是：CoregSC 算法通過將各視圖的特征向量矩陣正則化為一個共同一致的特征向量矩陣，使得每個視圖的特征向量相似，因此無須像其他聚類算法一樣將所有視圖的特征向量矩陣進行組合；CWK2M 算法采用了一種基于距離的簇加權方法，其簇權重需要重復迭代計算。

5 結束語

本文采用聯(lián)合熵評估基聚類簇質量，提出一種多視圖集成聚類分析方法，有效地刻畫了基聚類簇的重要程度與質量優(yōu)劣，體現(xiàn)了基聚類簇在不同視圖中存在差異化的特點，并改善了多視圖集成聚類性能。下一步研究工作是針對聚類簇集成，優(yōu)化其迭代步驟，降低時間復雜度。