尚曉群 楊海峰 蔡江輝

（太原科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院 太原 030024）

1 引言

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

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

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

圖1 基于多變量自學(xué)習(xí)與融合策略過程

2 理論基礎(chǔ)

2.1 信息熵

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

其中不確定性函數(shù)H 是概率pi的減函數(shù)，即當(dāng)概率大時，不確定性小；反之，不確定性就大。信息熵反映了離散隨機事件的出現(xiàn)概率。

2.2 譜聚類

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

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

FTF=IC是正交約束，F(xiàn) 的最優(yōu)解決方法是包含拉普拉斯矩陣L 的c 個最小特征值對應(yīng)的c 個特征向量。

3 基于多變量自學(xué)習(xí)與融合策略的多視圖聚類算法

3.1 基本思想

本算法相繼自學(xué)習(xí)三種多視圖數(shù)據(jù)的變量，即視圖內(nèi)全局變量、視圖內(nèi)局部變量和視圖間變量。為了充分捕獲多視圖數(shù)據(jù)的信息，本算法使用信息熵理論來自學(xué)習(xí)多變量，充分考慮特征與特征、特征與視圖和視圖與視圖的潛在關(guān)系。

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

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

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

視圖內(nèi)局部變量：根據(jù)視圖內(nèi)全局變量和信息熵理論，視圖內(nèi)局部變量中每個屬性對應(yīng)的值可被定義為

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

其中，r 是k 在當(dāng)前屬性中出現(xiàn)的總次數(shù)占所有樣本個數(shù)的比值。

視圖間變量：基于每個視圖的視圖內(nèi)全局變量、視圖內(nèi)局部變量和該視圖中屬性數(shù)目占所有視圖屬性數(shù)目的比例，定義視圖間變量中每個視圖對應(yīng)的值，如下所示：

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

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

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

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

3.2 算法描述

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

本文的算法內(nèi)容主要包括兩個部分，第一部分是多變量自學(xué)習(xí)與融合，第二部分為獲取聚類標(biāo)簽過程。多變量自學(xué)習(xí)與融合的時間復(fù)雜度為O（n2），獲取聚類標(biāo)簽過程的時間復(fù)雜度為O（n2），算法的整體時間復(fù)雜度為O（n2）。

4 實驗分析

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

4.1 實驗設(shè)置

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

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

4.2 實驗結(jié)果與分析

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

表1 在各個數(shù)據(jù)集上的ACC實驗結(jié)果（%）；每列的最高分數(shù)用黑體標(biāo)出

表2 在各個數(shù)據(jù)集上的ARI實驗結(jié)果（%）；每列的最高分數(shù)用黑體標(biāo)出

表3 在各個數(shù)據(jù)集上的NMI實驗結(jié)果（%）；每列的最高分數(shù)用黑體標(biāo)出

表4 在各個數(shù)據(jù)集上的Purity實驗結(jié)果（%）；每列的最高分數(shù)用黑體標(biāo)出

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

5 結(jié)語

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