基于視圖互信息加權(quán)的多視圖集成聚類算法

勞景歡，黃 棟*，王昌棟，賴劍煌

（1.華南農(nóng)業(yè)大學(xué) 數(shù)學(xué)與信息學(xué)院，廣州 510642；2.中山大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510006）

0 引言

聚類分析（clustering analysis）是一類重要的無監(jiān)督學(xué)習(xí)技術(shù)，其目標(biāo)在于將一組給定數(shù)據(jù)點(diǎn)劃分為若干小類，每一個小類稱為一個簇（cluster），以期簇內(nèi)數(shù)據(jù)點(diǎn)盡可能相似，不同簇的數(shù)據(jù)點(diǎn)盡可能不同［1］。傳統(tǒng)聚類算法大多關(guān)注單視圖數(shù)據(jù)，即數(shù)據(jù)集僅有一個數(shù)據(jù)源（或僅有一個特征集）；而在現(xiàn)實(shí)應(yīng)用場景中，數(shù)據(jù)來源往往多樣化，同一個數(shù)據(jù)集也可能有多個數(shù)據(jù)源的特征集，由此構(gòu)成多視圖數(shù)據(jù)（multi-view data）。傳統(tǒng)聚類算法［2-4］的單視圖學(xué)習(xí)模式往往難以有效應(yīng)對多視圖聚類問題，如何充分利用多視圖場景下不同數(shù)據(jù)視圖之間的互補(bǔ)與一致信息提升多視圖聚類性能，是近年來聚類分析領(lǐng)域的一個熱點(diǎn)研究方向［5-17］。

近幾年，國內(nèi)外研究人員提出了許多行之有效的多視圖聚類算法［5-12］。Tang 等［12］提出了一種基于跨視圖相似圖融合的多視圖聚類算法，通過跨視圖擴(kuò)散，學(xué)習(xí)得到一個統(tǒng)一的圖相似性矩陣，并在該統(tǒng)一相似性矩陣上進(jìn)行譜聚類，生成聚類結(jié)果。Khan 等［11］提出了一種基于流形優(yōu)化的多視圖聚類算法，通過構(gòu)造一個聯(lián)合的拉普拉斯矩陣，以包含所有單視圖去噪處理后的簇信息，再使用k均值（k-means）聚類和Stiefel 流形方法優(yōu)化聯(lián)合聚類目標(biāo)，減少聯(lián)合視圖和單個視圖之間的聚類信息分歧。Zhang 等［18］提出了一種新的單步共識多視圖子空間聚類算法，構(gòu)建統(tǒng)一學(xué)習(xí)框架以同時學(xué)習(xí)得到相似性矩陣、共識表示和最終聚類標(biāo)簽矩陣。

這些多視圖聚類算法在聚類性能上取得了較大改進(jìn)［11-12，18］，但這些算法往往無差別對待所有視圖，未充分考慮視圖間的重要性差異，對于低質(zhì)量視圖也給予同等對待，可能導(dǎo)致低可靠度信息或噪聲信息在計(jì)算過程中持續(xù)傳播，對最終聚類結(jié)果產(chǎn)生負(fù)面影響，因此，多視圖加權(quán)機(jī)制近年來越來越得到重視，許多具有視圖加權(quán)能力的多視圖聚類算法［19-23］也相繼提出。Wang 等［20］提出了一種基于圖的多視圖聚類算法，通過多視圖權(quán)值、單視圖相似性和統(tǒng)一相似性三者之間的相互迭代更新，得到優(yōu)化后的權(quán)值和統(tǒng)一圖矩陣，再對統(tǒng)一圖矩陣進(jìn)行秩約束并得到最終的簇劃分。Chen等［21］提出了一種基于多視圖加權(quán)融合和離散化矩陣分解的多視圖譜聚類算法，通過對不同視圖加權(quán)學(xué)習(xí)得到統(tǒng)一相似性矩陣，對相似性矩陣進(jìn)行特征分解得到一組特征向量，進(jìn)而從特征向量中學(xué)習(xí)一個連續(xù)的聚類標(biāo)簽，將其離散化以建立最終聚類。Huang 等［22］提出了一種同時執(zhí)行核空間多視圖聚類任務(wù)和學(xué)習(xí)相似性關(guān)系的多視圖聚類模型，可在構(gòu)建準(zhǔn)確的相似圖、自動分配最優(yōu)權(quán)重的同時得到最終聚類指示矩陣。這些算法對多視圖聚類的加權(quán)機(jī)制進(jìn)行了多角度的探索，但這些算法大多依賴于特定目標(biāo)函數(shù)的迭代優(yōu)化，且往往涉及一個或多個超參數(shù)的預(yù)設(shè)或精調(diào)，其目標(biāo)函數(shù)的適用性及超參數(shù)設(shè)置的合理性均對實(shí)際應(yīng)用有較大影響。如何自動、高效地得到多視圖可靠度及其權(quán)值，構(gòu)建魯棒聚類結(jié)果，仍是目前多視圖聚類研究的一個挑戰(zhàn)性問題。

針對前述問題，本文提出一種基于視圖互信息加權(quán)的多視圖集成聚類（Multi-view Ensemble Clustering based on View-wise Mutual Information Weighting，MEC-VMIW）算法。該算法可分為視圖互加權(quán)階段和多視圖集成聚類階段兩個階段。在視圖互加權(quán)階段，首先對數(shù)據(jù)集進(jìn)行多次隨機(jī)降采樣，在單次降采樣的數(shù)據(jù)集中對每個視圖構(gòu)建一個聚類結(jié)果，利用多視圖的降采樣聚類集合評價每個視圖內(nèi)的聚類結(jié)果，再取它們的平均得分，得到各個視圖的一個評價分?jǐn)?shù)；然后，將此降采樣、構(gòu)建降采樣聚類、視圖評價過程重復(fù)T次，可得各視圖的T個評價分?jǐn)?shù)，以它的最終平均得分作為視圖權(quán)值。在多視圖集成聚類階段，借助集成聚類的思想［24-30］，在各個視圖中構(gòu)建多個基聚類（base clusterings），再將多個基聚類結(jié)果建模至二部圖（bipartite graph）模型，進(jìn)而作高效二部圖分割以得到最終聚類結(jié)果。

1 本文算法

1.1 視圖互信息加權(quán)機(jī)制

本文提出視圖互信息加權(quán)機(jī)制，在無監(jiān)督情況下可用來評價多視圖數(shù)據(jù)中不同視圖的可靠度并對它賦予相應(yīng)權(quán)值。為降低運(yùn)算規(guī)模，同時提升多次運(yùn)行時的多樣性，首先對原始數(shù)據(jù)集進(jìn)行隨機(jī)降采樣，采樣比例γ∈(0，1]；在具體實(shí)現(xiàn)中，令γ=0.5，即每次降采樣時保留一半數(shù)據(jù)點(diǎn)。進(jìn)一步地，在降采樣所得的數(shù)據(jù)點(diǎn)中，計(jì)算它們的歐氏距離，并以高斯核函數(shù)將它們映射至相似度，再取它們的K近鄰（K-Nearest Neighbors，KNN），構(gòu)建一個稀疏的K近鄰相似性矩陣，其中，高斯核函數(shù)的帶寬參數(shù)（bandwidth parameter）設(shè)置為K近鄰圖距離的平均值。在得到相似性矩陣的基礎(chǔ)上，通過譜聚類（Spectral Clustering，SC）算法［2］分別得到每個視圖的一個聚類結(jié)果。

然后，借助歸一化互信息（Normalized Mutual Information，NMI）［31］對每個視圖的聚類結(jié)果與其他視圖的聚類結(jié)果進(jìn)行相互評分。對于任意的兩個基聚類πi和πj，計(jì)算公式如下：

通過多個視圖的降采樣聚類結(jié)果以NMI 進(jìn)行相互評分，可以對不同視圖之間的聚類結(jié)果一致性或認(rèn)可度進(jìn)行評價，并將獲得其他視圖認(rèn)可（得分）更高的聚類（及其對應(yīng)視圖）視作具有更高可靠度，由此確認(rèn)視圖間權(quán)重。針對單次視圖互評可能存在的偶然性，本文將前述過程重復(fù)T次，得到平均互評得分。

在單次視圖互評的基礎(chǔ)上重復(fù)運(yùn)行T次，可得每個視圖的平均評價分?jǐn)?shù)，將它作為視圖權(quán)重。令Wv表示為第v個視圖的T次互評平均得分（即權(quán)重），計(jì)算如下：

由此，通過視圖互信息加權(quán)機(jī)制，可以得到各個視圖間的權(quán)重W={W1，W2，…，WV}，其 中Wv表示第v個視圖 的權(quán)重。

1.2 視圖基聚類生成策略

集成聚類的目標(biāo)在于融合多個基聚類結(jié)果的信息以得到一個更優(yōu)、更魯棒聚類結(jié)果［27］。常規(guī)集成聚類往往以k均值聚類算法生成基聚類集合，雖然k均值聚類算法具有計(jì)算簡單、效率高等優(yōu)點(diǎn)，但聚類結(jié)果對質(zhì)心選取的依賴程度高且難以有效應(yīng)對非線性可分?jǐn)?shù)據(jù)集。譜聚類與k均值聚類算法相比，可生成任意簇形狀的聚類結(jié)果，有效應(yīng)對非線性可分?jǐn)?shù)據(jù)集，因此本文采用譜聚類算法生成多視圖基聚類。

為了得到更優(yōu)聚類結(jié)果，本文將對多視圖數(shù)據(jù)的多個基聚類進(jìn)行集成，構(gòu)造簇與數(shù)據(jù)點(diǎn)之間的二部圖結(jié)構(gòu)，然后以高效圖分割算法得到最終的聚類結(jié)果。該二部圖中，包含數(shù)據(jù)集的所有樣本點(diǎn)。若使用降采樣的方式得到具有部分樣本的基聚類，將不能構(gòu)造具有正確權(quán)值的二部圖。為此，與視圖互加權(quán)階段使用降采樣數(shù)據(jù)集不同，基聚類生成過程使用的是完整數(shù)據(jù)集。為充分挖掘各視圖信息，本文為每個視圖生成M個基聚類，由此為多視圖數(shù)據(jù)集得到總計(jì)M×V個基聚類。在每個視圖中，本文基于歐氏距離與高斯核函數(shù)映射構(gòu)造數(shù)據(jù)點(diǎn)的相似性矩陣，進(jìn)而構(gòu)建其K近鄰相似性圖，然后利用譜聚類算法對其進(jìn)行劃分。對于所有的基聚類，如果它們的簇數(shù)均相同，可能得到的基聚類集合較為單調(diào)。對于每一個基聚類，如果簇數(shù)偏離真實(shí)的簇數(shù)過大，則可能得到準(zhǔn)確性較差的基聚類。為了使所構(gòu)建的基聚類集合具有多樣性，對每個基聚類的簇個數(shù)在隨機(jī)選取，其中y表示該數(shù)據(jù)集的真實(shí)類別個數(shù)。對于V個視圖，在每個視圖中生成M個基聚類，將第v個視圖所生成的基聚類集合記作：

其中視圖v的第i個基聚類表示為，令nv，i表示簇個數(shù)，則有：

值得注意的是，在1.1 節(jié)中基于視圖互信息加權(quán)機(jī)制已經(jīng)得到各個視圖的權(quán)重W={W1，W2，…，WV}，進(jìn)一步將之與各個視圖的基聚類集合相結(jié)合，即得到基聚類權(quán)重，即在視圖v的基聚類集合Πv內(nèi)的基聚類對應(yīng)獲得視圖v的權(quán)重Wv。

1.3 二部圖建模與多視圖集成聚類

在構(gòu)建多視圖基聚類集合Π的基礎(chǔ)上，將對多個基聚類的信息進(jìn)行融合，構(gòu)建最終的多視圖聚類結(jié)果。本文采用二部圖結(jié)構(gòu)對多基聚類的集成過程進(jìn)行建模。在基聚類集合中，每個基聚類包含若干個簇，將全體基聚類所包含的簇集合表示為：

其中NC表示簇的總數(shù)。顯然，全體基聚類的簇個數(shù)等于各個基聚類簇個數(shù)之和，即NC=

具體地，以簇集C和數(shù)據(jù)點(diǎn)集X為節(jié)點(diǎn)集，將集成聚類問題構(gòu)造為加權(quán)二部圖模型。所建立的加權(quán)二部圖結(jié)構(gòu)如圖1 所示。當(dāng)兩個節(jié)點(diǎn)同為簇節(jié)點(diǎn)或者同為數(shù)據(jù)點(diǎn)節(jié)點(diǎn)時，兩節(jié)點(diǎn)之間沒有邊的連接；當(dāng)且僅當(dāng)一個節(jié)點(diǎn)為數(shù)據(jù)點(diǎn)節(jié)點(diǎn)、另一個節(jié)點(diǎn)為簇節(jié)點(diǎn)且該簇中包含了這個數(shù)據(jù)點(diǎn)時，兩個節(jié)點(diǎn)之間才有邊的連接，兩者之間連接邊的權(quán)值由該簇隸屬的基聚類權(quán)值所決定。

圖1 加權(quán)二部圖G示意圖Fig.1 Schematic diagram of bipartite graph G

該二部圖結(jié)構(gòu)表示如下：

其中：X和C表示二部圖G的兩部分節(jié)點(diǎn)集合，L為圖G的邊集合。對于任意的兩個節(jié)點(diǎn)xi和Cj，邊的權(quán)值定義如下：

其中：xi是數(shù)據(jù)點(diǎn)節(jié)點(diǎn)，Cj是簇節(jié)點(diǎn)。xi隸屬于Cj且xi所在的基聚類隸屬于視圖v的基聚類集合Πv，則xi與Cj之間的權(quán)值由視圖v的權(quán)值所決定?；诙繄D的結(jié)構(gòu)特點(diǎn)，可使用遷移分割（transfer cut）算法［32］將該二部圖結(jié)構(gòu)高效劃分為若干互不相交的節(jié)點(diǎn)子集，將每一個節(jié)點(diǎn)子集中的數(shù)據(jù)點(diǎn)視作一個簇，得到最終的多視圖集成聚類結(jié)果。

2 實(shí)驗(yàn)與結(jié)果分析

本章在6 個多視圖數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并將本文提出的基于視圖互信息加權(quán)的多視圖集成聚類（MEC-VMIW）算法與譜聚類算法及4 個多視圖聚類算法對比分析。

2.1 數(shù)據(jù)集與對比算法

本節(jié)實(shí)驗(yàn)將在6 個多視圖數(shù)據(jù)集上展開，分別是3Sources、Notting-Hill、Reuters、Mfeat、Caltech-7、Caltech-20，具體信息如表1 所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab.1 Experimental datasets

將MEC-VMIW 算法與5 個單視圖和多視圖聚類算法進(jìn)行對比，對比算法分別是：SC 算法［2］、RMSC（Robust Multi-view Spectral Clustering）［33］、AWP（multi-view clustering via Adaptively Weighted Procrustes）［9］、MCGC（Multi-view Consensus Graph Clustering）［34］和CoMSC（Multiview Subspace Clustering via Co-training robust data representation）［17］。

在這些對比算法中，SC 算法是單視圖聚類算法，SC-Avg表示SC 算法在所有視圖取到的平均得分，SC-Best 表示SC 算法在所有視圖中取到的最高得分；RMSC、AWP、MCGC 和CoMSC 是多視圖聚類算法。

2.2 參數(shù)設(shè)置與評價指標(biāo)

為了實(shí)驗(yàn)的公平性，在所有對比實(shí)驗(yàn)中，首先將數(shù)據(jù)集進(jìn)行歸一化處理。在各個數(shù)據(jù)集的實(shí)驗(yàn)中，每個算法均重復(fù)運(yùn)行20 次，取其平均得分及標(biāo)準(zhǔn)差作為評價標(biāo)準(zhǔn)。

在MEC-VMIW 算法中，構(gòu)建K近鄰相似性矩陣所采用的近鄰個數(shù)設(shè)置為K=10，視圖互加權(quán)過程中降采樣次數(shù)設(shè)置為T=10，基聚類生成過程中每個視圖的基聚類個數(shù)設(shè)置為M=10。值得一提的是，本文算法對不同參數(shù)設(shè)置具有很好的魯棒性，可在所有數(shù)據(jù)集中使用相同參數(shù)配置。在各個對比算法中，本文采用對應(yīng)論文中的參數(shù)設(shè)置。

在評價指標(biāo)上，本文采用歸一化互信息（NMI）［31］和調(diào)整后蘭德指數(shù)（Adjusted Rand Index，ARI）［27］這兩個常用指標(biāo)評價聚類性能，其中：NMI 的取值范圍為［0，1］，ARI 的取值范圍為［-1，1］，NMI 與ARI 的得分越高，表示所得聚類結(jié)果與真實(shí)類標(biāo)越契合，即聚類性能越好。

2.3 與其他算法的對比實(shí)驗(yàn)

本節(jié)將在6 個多視圖數(shù)據(jù)集上對MEC-VMIW 算法與5個對比聚類算法進(jìn)行對比分析。各個聚類算法在數(shù)據(jù)集上的NMI 與ARI 分?jǐn)?shù)分別如表2、3 所示。

表2 本文算法與其他聚類算法的NMI得分 單位：%Tab.2 NMI scores of the proposed algorithm and other clustering algorithms unit：%

如表2 所示，本文算法在4 個數(shù)據(jù)集上取得了最高NMI得分，并且MEC-VMIW 算法的平均NMI 得分為60.80%，顯著高于其他對比算法。除本文算法之外，AWP 算法取得了第二高分的平均NMI 得分，僅為54.16%。

如表3 所示，本文算法在ARI 得分方面也表現(xiàn)出類似優(yōu)勢，平均ARI 得分為53.61%，顯著高于取得次高的平均ARI得分45.20%。AWP 算法雖然在Caltech-7 和Caltech-20 等兩個數(shù)據(jù)集上ARI 得分小幅高于本文算法，但它在3Sources、Notting-Hill、Reuters 等數(shù)據(jù)集上的ARI 得分均顯著低于本文算法，特別是在Reuters 數(shù)據(jù)集上AWP 算法的ARI 得分僅為2.42%。相較于其他對比算法，本文所提出的多視圖集成聚類算法也表現(xiàn)出更為魯棒的聚類性能。

表3 本文算法與其他聚類算法的ARI得分 單位：%Tab.3 ARI scores of the proposed algorithm and other clustering algorithms unit：%

2.4 參數(shù)分析

本節(jié)將在6 個多視圖數(shù)據(jù)集中對MEC-VMIW 算法的參數(shù)K、M的敏感性進(jìn)行分析，驗(yàn)證MEC-VMIW 算法在不同參數(shù)配置下的聚類魯棒性。

在構(gòu)建K近鄰相似性矩陣過程中，參數(shù)K表示近鄰個數(shù)。為驗(yàn)證近鄰個數(shù)K對MEC-VMIW 算法的聚類性能影響，本文令K的取值在｛5，10，15，20｝變化，得到在不同的K值下MEC-VMIW 算法的NMI 與ARI 得分，如圖2、3 所示。由實(shí)驗(yàn)結(jié)果可以看到，MEC-VMIW 算法在不同的近鄰數(shù)K下表現(xiàn)出相當(dāng)穩(wěn)定的聚類性能，在同一個數(shù)據(jù)集中，得到的結(jié)果的NMI 和ARI 的表現(xiàn)的波動趨勢較為一致。MEC-VMIW 算法在3Sources、Mfeat 和Caltech-20 等數(shù)據(jù)集中，隨著K的增大，得到的NMI 值呈單調(diào)遞增/遞降趨勢，但均在K=10 之后逐漸收 斂。在Notting-Hill、Reuters 和Caltech-7 等數(shù)據(jù)集中，K∈[10，15]時得到的分?jǐn)?shù)最高。由于在K=10、15、20 的得分較為穩(wěn)定，不妨將K設(shè)置在［10，20］區(qū)間，可對不同數(shù)據(jù)均為較好的魯棒性。在本文實(shí)驗(yàn)中，對所有數(shù)據(jù)集均采用K=10的統(tǒng)一設(shè)置（從結(jié)果來看，取K=10 和取K=15 的性能差不多，甚至K=10 更好；結(jié)合運(yùn)算時間成本，由于K越大需要的計(jì)算時間越多，所以選擇K=10 更為合理）。

圖2 不同K值下MEC-VMIW算法的NMI得分Fig.2 NMI scores of MEC-VMIW algorithm at different K values

圖3 近鄰個數(shù)K的不同取值下MEC-VMIW算法的ARI得分Fig.3 ARI scores of MEC-VMIW algorithm at different K values

在基聚類生成過程中，M表示每個視圖基聚類個數(shù)。為驗(yàn)證單個視圖基聚類個數(shù)M對MEC-VMIW 算法的聚類性能影響，本文也令M的取值在｛5，10，15，20｝變化，得到在不同的M值下MEC-VMIW算法的NMI與ARI得分，如圖4、5所示。

圖4 每個視圖基聚類個數(shù)M的不同取值下MEC-VMIW算法的NMI得分Fig.4 NMI scores of MEC-VMIW algorithm at different M values

圖5 每個視圖基聚類個數(shù)M的不同取值下MEC-VMIW算法的ARI得分Fig.5 ARI scores of MEC-VMIW algorithm at different M values

需要注意的是，在具有V個視圖的多視圖數(shù)據(jù)中，單視圖基聚類個數(shù)為M則意味著多個視圖的總基聚類個數(shù)為M×V。如圖4、5所示，本文算法在不同M取值下表現(xiàn)出較穩(wěn)定的聚類性能，其中M∈[10，15]是它在不同數(shù)據(jù)集下的建議取值。在本文實(shí)驗(yàn)中，本文對所有數(shù)據(jù)集均采用M=10的統(tǒng)一設(shè)置。

3 結(jié)語

本文提出了一種基于視圖互信息加權(quán)的多視圖集成聚類（MEC-VMIW）算法，主要過程可分為視圖互信息加權(quán)和多視圖集成聚類這兩個主要階段。在視圖互信息加權(quán)階段，所提算法首先對數(shù)據(jù)集進(jìn)行多次隨機(jī)降采樣，在每次降采樣數(shù)據(jù)集中構(gòu)建各視圖聚類結(jié)果，并以其聚類結(jié)果互評價策略得到各視圖評分，進(jìn)而將此降采樣、構(gòu)建降采樣聚類、視圖評價過程重復(fù)若干次以得到最終平均得分，并將之作為視圖權(quán)值。在多視圖集成聚類階段，本文借助于集成聚類的思想，在各個視圖中構(gòu)建基聚類集合，進(jìn)而將其建模至二部圖結(jié)構(gòu)，再以高效二部圖分割算法得到最終多視圖聚類結(jié)果。在多個數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提出多視圖集成聚類算法的有效性與魯棒性。在未來研究工作中，可繼續(xù)探索本文方法在缺乏多視圖數(shù)據(jù)、大規(guī)模多視圖數(shù)據(jù)上的進(jìn)一步擴(kuò)展。