樣本加權(quán)的多視圖聚類算法

洪 敏 賈彩燕 李亞芳 于 劍

1(交通數(shù)據(jù)分析與挖掘北京市重點實驗室(北京交通大學) 北京 100044)

飛速發(fā)展的信息技術(shù)使現(xiàn)實世界中的數(shù)據(jù)不僅呈現(xiàn)出規(guī)模龐大的特性，而且多源信息采集技術(shù)和多樣化的特征表示使得多視圖數(shù)據(jù)在眾多實際應用中越來越普遍.例如Web網(wǎng)頁可以從3個不同的角度描述：詞向量視圖直觀刻畫了網(wǎng)頁文本中單詞的出現(xiàn)情況；網(wǎng)頁中的圖像提供了豐富的視覺特征視圖；網(wǎng)頁與網(wǎng)頁之間的鏈接關(guān)系展示了網(wǎng)頁內(nèi)容彼此之間的相關(guān)性.多視圖數(shù)據(jù)的互補性和一致性有利于從不同方位協(xié)同完成特定的機器學習任務.因此，多視圖學習逐漸受到人們的關(guān)注.

多視圖研究最早起源于Yarowsky[1]和Blum等人[2]提出的消除單詞歧義算法和協(xié)同訓練算法.Yarowsky[1]將文檔中單詞信息和單詞所在文檔信息定義為2個視圖，并將不同視圖加入各自的分類器進行交互學習.Blum等人[2]在對多視圖定義分類器的同時，基于視圖獨立性的原則引入?yún)f(xié)同訓練.Bickel等人[3]以協(xié)同EM(expectation maximiza-tion)算法為基礎(chǔ)，提出了多視圖EM和兩視圖球狀K-means算法.Cleuziou等人[4]提出了CoFKM(centralized method for multiple-view clustering)算法，通過集中式策略使多個視圖的信息盡可能的一致.Sa[5]構(gòu)造了一個二視圖譜聚類算法，創(chuàng)建一個描述2個視圖共現(xiàn)信息的二部圖，以最小化視圖之間的不一致性.Kumar等人[6-7]相繼提出了在多視圖譜聚類加入?yún)f(xié)同訓練和協(xié)同正則的方法，保持了不同視圖上聚類結(jié)果的一致性.

但是，上述方法平等看待各個視圖，難以體現(xiàn)不同視圖信息對簇結(jié)構(gòu)重要性的差異，因此出現(xiàn)了一些視圖權(quán)重學習的經(jīng)典算法.較早的工作是Tzortzis等人[8]給出的多視圖帶權(quán)凸混合模型(convex mixture models, CMM).該模型對不同視圖訓練相應的CMM模型，同時為各個視圖分配自適應權(quán)重，并將自學習視圖權(quán)重思想推廣至核K-means，設計了多視圖核函數(shù)K-means算法(multi-view kernelK-means, MVKKM)[9].該算法通過預先定義的核函數(shù)將原始數(shù)據(jù)映射到新的特征空間，并根據(jù)視圖對簇劃分結(jié)果的貢獻度為每一個視圖分配權(quán)重.為了適用大規(guī)模多視圖數(shù)據(jù)，Cai等人[10]給出了RMKMC模型，不僅在目標函數(shù)中新增視圖權(quán)值參數(shù)，同時2,1范式還增強了算法的魯棒性.最近，Nie等人[11-12]從圖的角度提出了2種適用聚類和半監(jiān)督分類的多視圖學習模型：AMGL和MLAN.AMGL[11]憑借視圖近鄰圖學習，構(gòu)建出了多視圖譜聚類權(quán)重學習框架;MLAN[12]通過學習多圖局部流形結(jié)構(gòu)，不斷修正簇結(jié)構(gòu)矩陣以優(yōu)化聚類性能.

多視圖學習不僅是不同視圖之間的有效性融合，而且視圖特征的選擇也是多視圖學習的重要組成部分.Chen等人[13]提出了自適應雙權(quán)多視圖算法(TW-K-means).該算法能同時學習視圖權(quán)重和特征權(quán)重對簇結(jié)構(gòu)的貢獻.Xu等人[14]提出了具有特征選擇的加權(quán)多視圖聚類算法(weighted multi-view clustering with feature selection, WMCFS).Zhang等人[15]在多視圖權(quán)重學習模型中增加了視圖間的一致性約束，設計了性能良好的TW-Co-K-means模型.

除了以上的學習不同視圖和特征對簇結(jié)構(gòu)貢獻差異的“全局”模型外，Li等人以節(jié)點屬性和節(jié)點的鏈接關(guān)系為2種數(shù)據(jù)源，學習了不同樣本點上不同類型信息對社區(qū)結(jié)構(gòu)(即簇結(jié)構(gòu))貢獻的“局部”差異[16]，給出了Adapt-SA模型，取得了不錯的效果.但該模型需要對2種信息下的數(shù)據(jù)進行同維變換，不但缺乏靈活性且同維變換易造成原有數(shù)據(jù)上信息的損失.因此，我們基于兩視圖同維變換樣本局部權(quán)值學習模型Adapt-SA，提出了一種新的多視圖樣本加權(quán)聚類算法(sample-weighted multi-view clustering, SWMVC).該算法不僅可以學習不同樣本點對多個視圖間權(quán)重的差異，具有“局部”學習能力，而且還可以從“全局”角度反映不同視圖對簇結(jié)構(gòu)的貢獻差異.另外，該方法不僅克服了Adapt-SA方法同維變換的約束，而且將Adapt-SA的思想從2個視圖擴展到多個視圖上.

1 相關(guān)算法介紹

1.1 MVKKM

MVKKM(multi-view clustering kernelK-means)[9]是一種基于核函數(shù)的多視圖權(quán)值模型.相比傳統(tǒng)的視圖權(quán)值方法，該算法使用事先定義的核函數(shù)對數(shù)據(jù)進行映射，然后在多視圖K-means中學習各個視圖的重要性.其目標函數(shù):

(1)

1.2 WMCFS

基于MVKKM思想，WMCFS(weighted multi-view clustering with feature selection)[14]模型在多視圖K-means聚類過程中同時考慮不同視圖和各個特征的差異，設計了目標函數(shù):

(2)

其中，ωv和τv分別表示視圖權(quán)重和視圖中各個特征的權(quán)重，p和β是分別控制視圖和特征稀疏性的參數(shù).

1.3 TW-Co-K-means

TW-Co-K-means(two-level weighted collaborativeK-means)[15]采用協(xié)同策略約束不同視圖之間的一致性，進而學習視圖和特征對簇結(jié)構(gòu)的重要性.其目標函數(shù):

(3)

(4)

(5)

1.4 Adapt-SA

Adapt-SA(adaptive fusion of structural and attribute information)[16]是面向圖聚類問題提出的一種學習樣本上不同種類信息(鏈接信息和節(jié)點屬性)對節(jié)點簇結(jié)構(gòu)重要性差異的K-means型算法.該算法首先將2類信息映射到同維空間上，再進行加權(quán)融合.因此，融合后的表示具有統(tǒng)一的簇中心.其目標函數(shù):

(6)

2 基于樣本加權(quán)的多視圖聚類算法

Adapt-SA雖然可以學習不同樣本間2類信息重要性的差異，但該方法在進行信息融合時，需要對原空間數(shù)據(jù)進行同維變換，可能會造成一定的信息損失.并且，同維變化也會帶來算法復雜性的增加.在實際應用中，可能某個視圖的維度適當，最宜在原空間進行簇結(jié)構(gòu)學習，使得Adapt-SA缺乏靈活性.因此，本部分我們給出了一種普適性更強且能夠?qū)W習不同樣本點權(quán)值的多視圖K-means算法，以彌補Adapt-SA算法的不足.

2.1 基本定義

為方便介紹所提出的算法模型，本節(jié)所用符號的具體含義如表1所示：

Table 1 The Symbol Meaning表1 符號含義

2.2 SWMVC算法

受Adapt-SA思想的啟發(fā)，并結(jié)合多視圖K-means算法，為了描述多視圖聚類過程中每個樣本點的不同視圖對簇結(jié)構(gòu)的貢獻，SWMVC算法優(yōu)化模型:

(7)

因此，SWMVC模型具備3方面的特點：1)能使每一個視圖擁有獨立的簇中心；2)每個樣本點對多個視圖擁有自己對簇結(jié)構(gòu)貢獻的權(quán)重影響，具有局部學習能力，同時通過樣本點在各視圖上的不同重要程度，易于統(tǒng)計各視圖對簇結(jié)構(gòu)的全局重要性；3)不但可以在多個視圖的原空間進行操作，也可以在變換后的視圖空間(如使用Adapt-SA模型中的同維變換策略)進行學習，靈活性高.

2.3 SWMVC模型求解

在求解時，針對每一個類尋求所有視圖到每個類中心的帶權(quán)距離最小值.即按照式(8)進行計算，之后根據(jù)得到的最小值結(jié)果對每個數(shù)據(jù)點進行指派.

(8)

(9)

(10)

(11)

(12)

根據(jù)上述模型求解過程知，本節(jié)構(gòu)建的基于樣本加權(quán)的多視圖聚類算法(SWMVC)的詳細步驟如算法1所示：

算法1.SWMVC.

輸入：多視圖數(shù)據(jù)集X={X1,X2,…,XV}、類個數(shù)K、參數(shù)λ、最大迭代次數(shù)tmax;

輸出：X的共有隸屬度δ、樣本權(quán)集αv.

② 根據(jù)式(8)更新δ；

⑤t=t+1；

⑥ 如果t>tmax，停止算法，返回δ和αv.

3 實驗設計與結(jié)果分析

3.1 數(shù)據(jù)集描述

為了評估本文提出的基于樣本加權(quán)的多視圖聚類模型(SWMVC)算法的效果，對不同的多視圖權(quán)值聚類模型進行實驗和對比分析.我們選取了視圖之間是異質(zhì)特性的6個數(shù)據(jù)集，分別是WebKB中的Cornell,Texas,Washington,Wisconsin網(wǎng)絡/文本數(shù)據(jù)集和圖像/文本數(shù)據(jù)集Wiki和VOC以及視圖具有同質(zhì)特性的2個數(shù)據(jù)集：Handwritten numerals和Caltech101-7.

1) WebKB數(shù)據(jù)集

Cornell,Texas,Washington和Wisconsin是WebKB網(wǎng)頁數(shù)據(jù)集的子集，分別包含195,187,230,265個樣本.每個樣本通過引用關(guān)系視圖和文本內(nèi)容屬性視圖進行描述，對應的成對視圖維數(shù)分別是195維和1 703維、187維和1 703維、230維和1 703維、265維和1 626維.該數(shù)據(jù)集涉及到5個類別課程、學院、學生、工程和員工.

2) Wiki數(shù)據(jù)集

Wiki是從維基百科專題文章中提取的數(shù)據(jù)集，常用于跨模態(tài)檢索中.該數(shù)據(jù)集由2 173個訓練樣本和693個測試樣本組成的圖片-文本對數(shù)據(jù)，共有10個類.其中，每一張圖片使用128維SIFT特征向量視圖表示，并含有相關(guān)圖片的10維文本LDA主題描述向量視圖.

3) Pascal Visual Object Classes 2007數(shù)據(jù)集

Pascal Visual Object Classes 2007(VOC)是一個自然圖像數(shù)據(jù)集.選用其中的2 808張圖片,每一張圖像有512維的GIST特征和399維的TF-IDF(term frequency-inverse document frequency)文本特征.涉及到20個類aeroplane,bicycle,bird,boat,bottle,bus,car,cat,chair,cow,dining table,dog,horse,motorbike,person,potted plant,sheep,sofa,train,tv/monitor.

4) Handwritten numerals數(shù)據(jù)集

Handwritten numerals(HW)是一個含有10個類的2 000個手寫體數(shù)字數(shù)據(jù)集.本實驗選取其中的5個視圖數(shù)據(jù)，分別是維數(shù)76維FOU特征、216維FAC特征、64維KAR特征、240維PIX特征和47維ZER特征.

5) Caltech101-7數(shù)據(jù)集

Caltech101-7是一個對象識別數(shù)據(jù)集.包括1 474張圖片，被劃分為7個類，分別是Face,Motorbike,DollaBill,Garfield,Snoopy,Stop-Sign,Windsor-Chair，含有圖像的Gabor,Wavelet,CENTRIST,HOG,GIST和LBP 6個特征，并將其作為Caltech101-7的6個視圖，對應視圖的特征維數(shù)分別為48維、40維、254維、1984維、512維和928維.

3.2 實驗方案

為了全面評估本文提出的基于樣本加權(quán)的多視圖聚類模型的性能，在實驗部分中對比研究了多視圖聚類領(lǐng)域中的多個代表性算法：

1) WMCFS[14]是一種具有特征選擇功能的多視圖聚類算法.該方法的2個參數(shù)p和β利用網(wǎng)格貪心搜索方法在3.1節(jié)介紹的8個數(shù)據(jù)集上依次設置為{5,0.5}，{30,0.0005}，{20,0.5}，{30,0.0002}，{10,0.5}，{20,0.0005}，{10,0.1}和{5,0.0005}.

2) MLAN[12]是一種面向圖聚類的多視圖聚類算法.與傳統(tǒng)圖聚類不同的是，它考慮局部流形結(jié)構(gòu)在每一輪迭代不斷修改相似性矩陣，直至獲得最優(yōu)矩陣.該方法可以自動學習各個視圖的權(quán)重系數(shù).其隱含參數(shù)近鄰數(shù)k=9.

3) AMGL[11]該方法假設所有圖共享潛在簇結(jié)構(gòu)，是一種無參數(shù)的多圖學習框架，即在學習時能夠為各個圖分配合適的權(quán)值，可以應用于多視圖聚類和半監(jiān)督分類任務.其隱含參數(shù)近鄰數(shù)k=5.

4) TW-Co-K-means[15]是一種融合視圖和特征的多視圖算法.該方法全面考慮不同視圖的互補性和一致性，以協(xié)同方式挖掘不同視圖間的共享信息，同時考量了每個視圖的多樣性特點.參數(shù)η，α和β在各個數(shù)據(jù)集分別采用網(wǎng)格貪心搜索方法設置為{0.8,10,60}，{0.8,30,60}，{0.1,20,80}，{0.9,50,80}，{0.3,30,8}，{0.01,80,50}，{0.6,10,50}和{0.2,30,8}.

5) SWMVC是本文提出的基于樣本加權(quán)的多視圖聚類算法.模型中含有樣本權(quán)稀疏系數(shù)，參數(shù)λ經(jīng)過網(wǎng)格貪心搜索方法在各數(shù)據(jù)集的值分別設為100,75,35,60,0.5,1,10,45.

3.3 實驗結(jié)果分析

本節(jié)首先展示不同方法在各種多視圖數(shù)據(jù)集上的聚類效果，然后展示W(wǎng)ebKB,Wiki和VOC所有樣本在給定視圖的權(quán)重分布，最后研究了參數(shù)λ的敏感性.

1) 多視圖聚類效果對比

表2～4分別展示了各多視圖聚類方法在8個數(shù)據(jù)集上的聚類評價指標ACC，NMI和F-measure.其中，各個算法精度選用20次運行結(jié)束的最大值，各多視圖聚類算法在同一數(shù)據(jù)集上的最好結(jié)果用黑體表示.

由表2～4可以看出：

① 相比傳統(tǒng)多視圖聚類方法，本文提出的基于樣本加權(quán)的多視圖聚類算法(SWMVC)在Cornell，Texas，Washington，Wisconsin，Wiki和VOC數(shù)據(jù)集上有較好的性能提升.具體來說，SWMVC的ACC和F-meansure指標值比傳統(tǒng)的多視圖聚類算法TW-Co-K-means在前5個數(shù)據(jù)上分別提高了約0.03和0.02，在VOC上取得了次優(yōu)結(jié)果.在NMI指標上，SWMVC在異質(zhì)數(shù)據(jù)Texas,Washington,Wisconsin和VOC獲得了最高結(jié)果，在Cornell和Wiki以0.208 2和0.538 8取得了第2高結(jié)果.究其原因，我們發(fā)現(xiàn)：WebKB的4個數(shù)據(jù)集由鏈接結(jié)構(gòu)視圖和文本內(nèi)容視圖2種異構(gòu)視圖描述，能夠形成較強的互補關(guān)系；Wiki和VOC由圖像特征視圖和文本特征視圖2種異構(gòu)視圖組成，同樣具有較好的互補性，且文本特征視圖解釋力強于圖像特征描述子.

② SWMVC在手寫數(shù)據(jù)集HW和圖像數(shù)據(jù)集Caltech101-7表現(xiàn)欠佳，原因在于盡管這2個數(shù)據(jù)集的多個視圖從各個方面進行了描述，但是視圖之間表現(xiàn)出同質(zhì)特性，視圖間的信息互補性相對較弱，且對簇結(jié)構(gòu)的刻畫能力在局部樣本上的差異性不明顯.

Note: The best results are highlighted in bold.

Table 3 NMI of Different Clustering Algorithms on Multi-View Datasets表3 不同聚類算法在多視圖數(shù)據(jù)集上的NMI值

Note: The best results are highlighted in bold.

Table 4 F-measure of Different Clustering Algorithms on Multi-View Datasets表4 不同聚類算法在多視圖數(shù)據(jù)集上的F值

Note: The best results are highlighted in bold.

Fig. 1 Weights of samples in a given view圖1 各個樣本在給定視圖上的權(quán)重

③ 根據(jù)實驗結(jié)果可以發(fā)現(xiàn)：MLAN模型在HW和Caltech101-7效果顯著.究其原因，MLAN學習了數(shù)據(jù)的局部流形結(jié)構(gòu)，多個同質(zhì)視圖上局部流形結(jié)構(gòu)的整合較好地反映出了全局的簇結(jié)構(gòu)信息，是目前較為突出的模型.

④ 綜合WMCFS和TW-Co-K-means多視圖特征算法在上述8個數(shù)據(jù)集的實驗結(jié)果可見：良好的特征選擇機制可以提高多視圖聚類算法的性能.

2) 節(jié)點權(quán)重分析

為了進一步驗證本文提出的SWMVC算法，我們在圖1中展示了該方法在6個異構(gòu)視圖數(shù)據(jù)集Cornell,Texas,Washington,Wisconsin,Wiki和VOC上學習到的樣本權(quán)重.其中，橫坐標表示樣本編號，縱坐標表示各樣本在WebKB四個數(shù)據(jù)鏈接視圖上的權(quán)重及Wiki,VOC數(shù)據(jù)集的各樣本點在文本視圖上的權(quán)重.

由圖1可以看出：整體上WebKB四個數(shù)據(jù)集的樣本在鏈接視圖所占權(quán)重較大，即拓撲結(jié)構(gòu)更能刻畫數(shù)據(jù)特性；Wiki和VOC各樣本點在文本視圖權(quán)重大于圖像特征視圖.同時視圖包含重要度樣本越多，說明該視圖該視圖越重要，實現(xiàn)了對數(shù)據(jù)“全局”信息重要性的學習.

對于同質(zhì)的多視圖數(shù)據(jù)集HW和Caltech101-7，SWMVC算法學習到的各樣本點的權(quán)重差異性小.由于這2個數(shù)據(jù)集視圖多，考慮到空間限制，只簡單描述如下：HW數(shù)據(jù)集所有樣本在FAC,FOU,KAR和ZER視圖權(quán)重基本分布在0.21左右，在PIX特征視圖權(quán)值約為0.16；Caltech101-7所有樣本點在前3個視圖權(quán)重約為0.20，第4個視圖權(quán)值約是0.06，最后2個權(quán)值為0.17左右.從而進一步可見，我們的方法更適于差異性較大的異構(gòu)互補視圖的簇結(jié)構(gòu)學習問題.

3.3 參數(shù)敏感性分析

Fig. 2 The influence of λ on sample weights圖2 參數(shù)λ對樣本權(quán)重分布的影響

4 總 結(jié)

本文主要提出了一種基于樣本加權(quán)的多視圖聚類算法(SWMVC).為了更好地學習多視圖蘊含的信息，本文受Adapt-SA算法啟發(fā)，引進多視圖學習思想，從不同視圖角度學習樣本對簇結(jié)構(gòu)的貢獻度.這種多視圖樣本加權(quán)學習機制不僅體現(xiàn)了樣本差異性，而且還刻畫了視圖的重要度，實現(xiàn)了對數(shù)據(jù)“局部”和“全局”性質(zhì)的學習.與此同時，SWMVC能夠保留數(shù)據(jù)原始信息，有助于降低模型復雜度.在6個異質(zhì)視圖數(shù)據(jù)集和2個同質(zhì)視圖數(shù)據(jù)集上的大量實驗對比表明：本文提出的模型在異質(zhì)視圖數(shù)據(jù)上具有不錯的聚類效果.