洪 敏 賈彩燕 李亞芳 于 劍
1(交通數(shù)據(jù)分析與挖掘北京市重點(diǎn)實(shí)驗(yàn)室(北京交通大學(xué)) 北京 100044)
飛速發(fā)展的信息技術(shù)使現(xiàn)實(shí)世界中的數(shù)據(jù)不僅呈現(xiàn)出規(guī)模龐大的特性,而且多源信息采集技術(shù)和多樣化的特征表示使得多視圖數(shù)據(jù)在眾多實(shí)際應(yīng)用中越來(lái)越普遍.例如Web網(wǎng)頁(yè)可以從3個(gè)不同的角度描述:詞向量視圖直觀刻畫(huà)了網(wǎng)頁(yè)文本中單詞的出現(xiàn)情況;網(wǎng)頁(yè)中的圖像提供了豐富的視覺(jué)特征視圖;網(wǎng)頁(yè)與網(wǎng)頁(yè)之間的鏈接關(guān)系展示了網(wǎng)頁(yè)內(nèi)容彼此之間的相關(guān)性.多視圖數(shù)據(jù)的互補(bǔ)性和一致性有利于從不同方位協(xié)同完成特定的機(jī)器學(xué)習(xí)任務(wù).因此,多視圖學(xué)習(xí)逐漸受到人們的關(guān)注.
多視圖研究最早起源于Yarowsky[1]和Blum等人[2]提出的消除單詞歧義算法和協(xié)同訓(xùn)練算法.Yarowsky[1]將文檔中單詞信息和單詞所在文檔信息定義為2個(gè)視圖,并將不同視圖加入各自的分類(lèi)器進(jìn)行交互學(xué)習(xí).Blum等人[2]在對(duì)多視圖定義分類(lèi)器的同時(shí),基于視圖獨(dú)立性的原則引入?yún)f(xié)同訓(xùn)練.Bickel等人[3]以協(xié)同EM(expectation maximiza-tion)算法為基礎(chǔ),提出了多視圖EM和兩視圖球狀K-means算法.Cleuziou等人[4]提出了CoFKM(centralized method for multiple-view clustering)算法,通過(guò)集中式策略使多個(gè)視圖的信息盡可能的一致.Sa[5]構(gòu)造了一個(gè)二視圖譜聚類(lèi)算法,創(chuàng)建一個(gè)描述2個(gè)視圖共現(xiàn)信息的二部圖,以最小化視圖之間的不一致性.Kumar等人[6-7]相繼提出了在多視圖譜聚類(lèi)加入?yún)f(xié)同訓(xùn)練和協(xié)同正則的方法,保持了不同視圖上聚類(lèi)結(jié)果的一致性.
但是,上述方法平等看待各個(gè)視圖,難以體現(xiàn)不同視圖信息對(duì)簇結(jié)構(gòu)重要性的差異,因此出現(xiàn)了一些視圖權(quán)重學(xué)習(xí)的經(jīng)典算法.較早的工作是Tzortzis等人[8]給出的多視圖帶權(quán)凸混合模型(convex mixture models, CMM).該模型對(duì)不同視圖訓(xùn)練相應(yīng)的CMM模型,同時(shí)為各個(gè)視圖分配自適應(yīng)權(quán)重,并將自學(xué)習(xí)視圖權(quán)重思想推廣至核K-means,設(shè)計(jì)了多視圖核函數(shù)K-means算法(multi-view kernelK-means, MVKKM)[9].該算法通過(guò)預(yù)先定義的核函數(shù)將原始數(shù)據(jù)映射到新的特征空間,并根據(jù)視圖對(duì)簇劃分結(jié)果的貢獻(xiàn)度為每一個(gè)視圖分配權(quán)重.為了適用大規(guī)模多視圖數(shù)據(jù),Cai等人[10]給出了RMKMC模型,不僅在目標(biāo)函數(shù)中新增視圖權(quán)值參數(shù),同時(shí)2,1范式還增強(qiáng)了算法的魯棒性.最近,Nie等人[11-12]從圖的角度提出了2種適用聚類(lèi)和半監(jiān)督分類(lèi)的多視圖學(xué)習(xí)模型:AMGL和MLAN.AMGL[11]憑借視圖近鄰圖學(xué)習(xí),構(gòu)建出了多視圖譜聚類(lèi)權(quán)重學(xué)習(xí)框架;MLAN[12]通過(guò)學(xué)習(xí)多圖局部流形結(jié)構(gòu),不斷修正簇結(jié)構(gòu)矩陣以?xún)?yōu)化聚類(lèi)性能.
多視圖學(xué)習(xí)不僅是不同視圖之間的有效性融合,而且視圖特征的選擇也是多視圖學(xué)習(xí)的重要組成部分.Chen等人[13]提出了自適應(yīng)雙權(quán)多視圖算法(TW-K-means).該算法能同時(shí)學(xué)習(xí)視圖權(quán)重和特征權(quán)重對(duì)簇結(jié)構(gòu)的貢獻(xiàn).Xu等人[14]提出了具有特征選擇的加權(quán)多視圖聚類(lèi)算法(weighted multi-view clustering with feature selection, WMCFS).Zhang等人[15]在多視圖權(quán)重學(xué)習(xí)模型中增加了視圖間的一致性約束,設(shè)計(jì)了性能良好的TW-Co-K-means模型.
除了以上的學(xué)習(xí)不同視圖和特征對(duì)簇結(jié)構(gòu)貢獻(xiàn)差異的“全局”模型外,Li等人以節(jié)點(diǎn)屬性和節(jié)點(diǎn)的鏈接關(guān)系為2種數(shù)據(jù)源,學(xué)習(xí)了不同樣本點(diǎn)上不同類(lèi)型信息對(duì)社區(qū)結(jié)構(gòu)(即簇結(jié)構(gòu))貢獻(xiàn)的“局部”差異[16],給出了Adapt-SA模型,取得了不錯(cuò)的效果.但該模型需要對(duì)2種信息下的數(shù)據(jù)進(jìn)行同維變換,不但缺乏靈活性且同維變換易造成原有數(shù)據(jù)上信息的損失.因此,我們基于兩視圖同維變換樣本局部權(quán)值學(xué)習(xí)模型Adapt-SA,提出了一種新的多視圖樣本加權(quán)聚類(lèi)算法(sample-weighted multi-view clustering, SWMVC).該算法不僅可以學(xué)習(xí)不同樣本點(diǎn)對(duì)多個(gè)視圖間權(quán)重的差異,具有“局部”學(xué)習(xí)能力,而且還可以從“全局”角度反映不同視圖對(duì)簇結(jié)構(gòu)的貢獻(xiàn)差異.另外,該方法不僅克服了Adapt-SA方法同維變換的約束,而且將Adapt-SA的思想從2個(gè)視圖擴(kuò)展到多個(gè)視圖上.
MVKKM(multi-view clustering kernelK-means)[9]是一種基于核函數(shù)的多視圖權(quán)值模型.相比傳統(tǒng)的視圖權(quán)值方法,該算法使用事先定義的核函數(shù)對(duì)數(shù)據(jù)進(jìn)行映射,然后在多視圖K-means中學(xué)習(xí)各個(gè)視圖的重要性.其目標(biāo)函數(shù):
(1)
基于MVKKM思想,WMCFS(weighted multi-view clustering with feature selection)[14]模型在多視圖K-means聚類(lèi)過(guò)程中同時(shí)考慮不同視圖和各個(gè)特征的差異,設(shè)計(jì)了目標(biāo)函數(shù):
(2)
其中,ωv和τv分別表示視圖權(quán)重和視圖中各個(gè)特征的權(quán)重,p和β是分別控制視圖和特征稀疏性的參數(shù).
TW-Co-K-means(two-level weighted collaborativeK-means)[15]采用協(xié)同策略約束不同視圖之間的一致性,進(jìn)而學(xué)習(xí)視圖和特征對(duì)簇結(jié)構(gòu)的重要性.其目標(biāo)函數(shù):
(3)
(4)
(5)
Adapt-SA(adaptive fusion of structural and attribute information)[16]是面向圖聚類(lèi)問(wèn)題提出的一種學(xué)習(xí)樣本上不同種類(lèi)信息(鏈接信息和節(jié)點(diǎn)屬性)對(duì)節(jié)點(diǎn)簇結(jié)構(gòu)重要性差異的K-means型算法.該算法首先將2類(lèi)信息映射到同維空間上,再進(jìn)行加權(quán)融合.因此,融合后的表示具有統(tǒng)一的簇中心.其目標(biāo)函數(shù):
(6)
Adapt-SA雖然可以學(xué)習(xí)不同樣本間2類(lèi)信息重要性的差異,但該方法在進(jìn)行信息融合時(shí),需要對(duì)原空間數(shù)據(jù)進(jìn)行同維變換,可能會(huì)造成一定的信息損失.并且,同維變化也會(huì)帶來(lái)算法復(fù)雜性的增加.在實(shí)際應(yīng)用中,可能某個(gè)視圖的維度適當(dāng),最宜在原空間進(jìn)行簇結(jié)構(gòu)學(xué)習(xí),使得Adapt-SA缺乏靈活性.因此,本部分我們給出了一種普適性更強(qiáng)且能夠?qū)W習(xí)不同樣本點(diǎn)權(quán)值的多視圖K-means算法,以彌補(bǔ)Adapt-SA算法的不足.
為方便介紹所提出的算法模型,本節(jié)所用符號(hào)的具體含義如表1所示:
Table 1 The Symbol Meaning表1 符號(hào)含義
受Adapt-SA思想的啟發(fā),并結(jié)合多視圖K-means算法,為了描述多視圖聚類(lèi)過(guò)程中每個(gè)樣本點(diǎn)的不同視圖對(duì)簇結(jié)構(gòu)的貢獻(xiàn),SWMVC算法優(yōu)化模型:
(7)
因此,SWMVC模型具備3方面的特點(diǎn):1)能使每一個(gè)視圖擁有獨(dú)立的簇中心;2)每個(gè)樣本點(diǎn)對(duì)多個(gè)視圖擁有自己對(duì)簇結(jié)構(gòu)貢獻(xiàn)的權(quán)重影響,具有局部學(xué)習(xí)能力,同時(shí)通過(guò)樣本點(diǎn)在各視圖上的不同重要程度,易于統(tǒng)計(jì)各視圖對(duì)簇結(jié)構(gòu)的全局重要性;3)不但可以在多個(gè)視圖的原空間進(jìn)行操作,也可以在變換后的視圖空間(如使用Adapt-SA模型中的同維變換策略)進(jìn)行學(xué)習(xí),靈活性高.
在求解時(shí),針對(duì)每一個(gè)類(lèi)尋求所有視圖到每個(gè)類(lèi)中心的帶權(quán)距離最小值.即按照式(8)進(jìn)行計(jì)算,之后根據(jù)得到的最小值結(jié)果對(duì)每個(gè)數(shù)據(jù)點(diǎn)進(jìn)行指派.
(8)
(9)
(10)
(11)
(12)
根據(jù)上述模型求解過(guò)程知,本節(jié)構(gòu)建的基于樣本加權(quán)的多視圖聚類(lèi)算法(SWMVC)的詳細(xì)步驟如算法1所示:
算法1.SWMVC.
輸入:多視圖數(shù)據(jù)集X={X1,X2,…,XV}、類(lèi)個(gè)數(shù)K、參數(shù)λ、最大迭代次數(shù)tmax;
輸出:X的共有隸屬度δ、樣本權(quán)集αv.
② 根據(jù)式(8)更新δ;
⑤t=t+1;
⑥ 如果t>tmax,停止算法,返回δ和αv.
為了評(píng)估本文提出的基于樣本加權(quán)的多視圖聚類(lèi)模型(SWMVC)算法的效果,對(duì)不同的多視圖權(quán)值聚類(lèi)模型進(jìn)行實(shí)驗(yàn)和對(duì)比分析.我們選取了視圖之間是異質(zhì)特性的6個(gè)數(shù)據(jù)集,分別是WebKB中的Cornell,Texas,Washington,Wisconsin網(wǎng)絡(luò)/文本數(shù)據(jù)集和圖像/文本數(shù)據(jù)集Wiki和VOC以及視圖具有同質(zhì)特性的2個(gè)數(shù)據(jù)集:Handwritten numerals和Caltech101-7.
1) WebKB數(shù)據(jù)集
Cornell,Texas,Washington和Wisconsin是WebKB網(wǎng)頁(yè)數(shù)據(jù)集的子集,分別包含195,187,230,265個(gè)樣本.每個(gè)樣本通過(guò)引用關(guān)系視圖和文本內(nèi)容屬性視圖進(jìn)行描述,對(duì)應(yīng)的成對(duì)視圖維數(shù)分別是195維和1 703維、187維和1 703維、230維和1 703維、265維和1 626維.該數(shù)據(jù)集涉及到5個(gè)類(lèi)別課程、學(xué)院、學(xué)生、工程和員工.
2) Wiki數(shù)據(jù)集
Wiki是從維基百科專(zhuān)題文章中提取的數(shù)據(jù)集,常用于跨模態(tài)檢索中.該數(shù)據(jù)集由2 173個(gè)訓(xùn)練樣本和693個(gè)測(cè)試樣本組成的圖片-文本對(duì)數(shù)據(jù),共有10個(gè)類(lèi).其中,每一張圖片使用128維SIFT特征向量視圖表示,并含有相關(guān)圖片的10維文本LDA主題描述向量視圖.
3) Pascal Visual Object Classes 2007數(shù)據(jù)集
Pascal Visual Object Classes 2007(VOC)是一個(gè)自然圖像數(shù)據(jù)集.選用其中的2 808張圖片,每一張圖像有512維的GIST特征和399維的TF-IDF(term frequency-inverse document frequency)文本特征.涉及到20個(gè)類(lèi)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)是一個(gè)含有10個(gè)類(lèi)的2 000個(gè)手寫(xiě)體數(shù)字?jǐn)?shù)據(jù)集.本實(shí)驗(yàn)選取其中的5個(gè)視圖數(shù)據(jù),分別是維數(shù)76維FOU特征、216維FAC特征、64維KAR特征、240維PIX特征和47維ZER特征.
5) Caltech101-7數(shù)據(jù)集
Caltech101-7是一個(gè)對(duì)象識(shí)別數(shù)據(jù)集.包括1 474張圖片,被劃分為7個(gè)類(lèi),分別是Face,Motorbike,DollaBill,Garfield,Snoopy,Stop-Sign,Windsor-Chair,含有圖像的Gabor,Wavelet,CENTRIST,HOG,GIST和LBP 6個(gè)特征,并將其作為Caltech101-7的6個(gè)視圖,對(duì)應(yīng)視圖的特征維數(shù)分別為48維、40維、254維、1984維、512維和928維.
為了全面評(píng)估本文提出的基于樣本加權(quán)的多視圖聚類(lèi)模型的性能,在實(shí)驗(yàn)部分中對(duì)比研究了多視圖聚類(lèi)領(lǐng)域中的多個(gè)代表性算法:
1) WMCFS[14]是一種具有特征選擇功能的多視圖聚類(lèi)算法.該方法的2個(gè)參數(shù)p和β利用網(wǎng)格貪心搜索方法在3.1節(jié)介紹的8個(gè)數(shù)據(jù)集上依次設(shè)置為{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]是一種面向圖聚類(lèi)的多視圖聚類(lèi)算法.與傳統(tǒng)圖聚類(lèi)不同的是,它考慮局部流形結(jié)構(gòu)在每一輪迭代不斷修改相似性矩陣,直至獲得最優(yōu)矩陣.該方法可以自動(dòng)學(xué)習(xí)各個(gè)視圖的權(quán)重系數(shù).其隱含參數(shù)近鄰數(shù)k=9.
3) AMGL[11]該方法假設(shè)所有圖共享潛在簇結(jié)構(gòu),是一種無(wú)參數(shù)的多圖學(xué)習(xí)框架,即在學(xué)習(xí)時(shí)能夠?yàn)楦鱾€(gè)圖分配合適的權(quán)值,可以應(yīng)用于多視圖聚類(lèi)和半監(jiān)督分類(lèi)任務(wù).其隱含參數(shù)近鄰數(shù)k=5.
4) TW-Co-K-means[15]是一種融合視圖和特征的多視圖算法.該方法全面考慮不同視圖的互補(bǔ)性和一致性,以協(xié)同方式挖掘不同視圖間的共享信息,同時(shí)考量了每個(gè)視圖的多樣性特點(diǎn).參數(shù)η,α和β在各個(gè)數(shù)據(jù)集分別采用網(wǎng)格貪心搜索方法設(shè)置為{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)的多視圖聚類(lèi)算法.模型中含有樣本權(quán)稀疏系數(shù),參數(shù)λ經(jīng)過(guò)網(wǎng)格貪心搜索方法在各數(shù)據(jù)集的值分別設(shè)為100,75,35,60,0.5,1,10,45.
本節(jié)首先展示不同方法在各種多視圖數(shù)據(jù)集上的聚類(lèi)效果,然后展示W(wǎng)ebKB,Wiki和VOC所有樣本在給定視圖的權(quán)重分布,最后研究了參數(shù)λ的敏感性.
1) 多視圖聚類(lèi)效果對(duì)比
表2~4分別展示了各多視圖聚類(lèi)方法在8個(gè)數(shù)據(jù)集上的聚類(lèi)評(píng)價(jià)指標(biāo)ACC,NMI和F-measure.其中,各個(gè)算法精度選用20次運(yùn)行結(jié)束的最大值,各多視圖聚類(lèi)算法在同一數(shù)據(jù)集上的最好結(jié)果用黑體表示.
由表2~4可以看出:
① 相比傳統(tǒng)多視圖聚類(lèi)方法,本文提出的基于樣本加權(quán)的多視圖聚類(lèi)算法(SWMVC)在Cornell,Texas,Washington,Wisconsin,Wiki和VOC數(shù)據(jù)集上有較好的性能提升.具體來(lái)說(shuō),SWMVC的ACC和F-meansure指標(biāo)值比傳統(tǒng)的多視圖聚類(lèi)算法TW-Co-K-means在前5個(gè)數(shù)據(jù)上分別提高了約0.03和0.02,在VOC上取得了次優(yōu)結(jié)果.在NMI指標(biāo)上,SWMVC在異質(zhì)數(shù)據(jù)Texas,Washington,Wisconsin和VOC獲得了最高結(jié)果,在Cornell和Wiki以0.208 2和0.538 8取得了第2高結(jié)果.究其原因,我們發(fā)現(xiàn):WebKB的4個(gè)數(shù)據(jù)集由鏈接結(jié)構(gòu)視圖和文本內(nèi)容視圖2種異構(gòu)視圖描述,能夠形成較強(qiáng)的互補(bǔ)關(guān)系;Wiki和VOC由圖像特征視圖和文本特征視圖2種異構(gòu)視圖組成,同樣具有較好的互補(bǔ)性,且文本特征視圖解釋力強(qiáng)于圖像特征描述子.
② SWMVC在手寫(xiě)數(shù)據(jù)集HW和圖像數(shù)據(jù)集Caltech101-7表現(xiàn)欠佳,原因在于盡管這2個(gè)數(shù)據(jù)集的多個(gè)視圖從各個(gè)方面進(jìn)行了描述,但是視圖之間表現(xiàn)出同質(zhì)特性,視圖間的信息互補(bǔ)性相對(duì)較弱,且對(duì)簇結(jié)構(gòu)的刻畫(huà)能力在局部樣本上的差異性不明顯.
Note: The best results are highlighted in bold.
Table 3 NMI of Different Clustering Algorithms on Multi-View Datasets表3 不同聚類(lèi)算法在多視圖數(shù)據(jù)集上的NMI值
Note: The best results are highlighted in bold.
Table 4 F-measure of Different Clustering Algorithms on Multi-View Datasets表4 不同聚類(lèi)算法在多視圖數(shù)據(jù)集上的F值
Note: The best results are highlighted in bold.
Fig. 1 Weights of samples in a given view圖1 各個(gè)樣本在給定視圖上的權(quán)重
③ 根據(jù)實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn):MLAN模型在HW和Caltech101-7效果顯著.究其原因,MLAN學(xué)習(xí)了數(shù)據(jù)的局部流形結(jié)構(gòu),多個(gè)同質(zhì)視圖上局部流形結(jié)構(gòu)的整合較好地反映出了全局的簇結(jié)構(gòu)信息,是目前較為突出的模型.
④ 綜合WMCFS和TW-Co-K-means多視圖特征算法在上述8個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果可見(jiàn):良好的特征選擇機(jī)制可以提高多視圖聚類(lèi)算法的性能.
2) 節(jié)點(diǎn)權(quán)重分析
為了進(jìn)一步驗(yàn)證本文提出的SWMVC算法,我們?cè)趫D1中展示了該方法在6個(gè)異構(gòu)視圖數(shù)據(jù)集Cornell,Texas,Washington,Wisconsin,Wiki和VOC上學(xué)習(xí)到的樣本權(quán)重.其中,橫坐標(biāo)表示樣本編號(hào),縱坐標(biāo)表示各樣本在WebKB四個(gè)數(shù)據(jù)鏈接視圖上的權(quán)重及Wiki,VOC數(shù)據(jù)集的各樣本點(diǎn)在文本視圖上的權(quán)重.
由圖1可以看出:整體上WebKB四個(gè)數(shù)據(jù)集的樣本在鏈接視圖所占權(quán)重較大,即拓?fù)浣Y(jié)構(gòu)更能刻畫(huà)數(shù)據(jù)特性;Wiki和VOC各樣本點(diǎn)在文本視圖權(quán)重大于圖像特征視圖.同時(shí)視圖包含重要度樣本越多,說(shuō)明該視圖該視圖越重要,實(shí)現(xiàn)了對(duì)數(shù)據(jù)“全局”信息重要性的學(xué)習(xí).
對(duì)于同質(zhì)的多視圖數(shù)據(jù)集HW和Caltech101-7,SWMVC算法學(xué)習(xí)到的各樣本點(diǎn)的權(quán)重差異性小.由于這2個(gè)數(shù)據(jù)集視圖多,考慮到空間限制,只簡(jiǎn)單描述如下:HW數(shù)據(jù)集所有樣本在FAC,FOU,KAR和ZER視圖權(quán)重基本分布在0.21左右,在PIX特征視圖權(quán)值約為0.16;Caltech101-7所有樣本點(diǎn)在前3個(gè)視圖權(quán)重約為0.20,第4個(gè)視圖權(quán)值約是0.06,最后2個(gè)權(quán)值為0.17左右.從而進(jìn)一步可見(jiàn),我們的方法更適于差異性較大的異構(gòu)互補(bǔ)視圖的簇結(jié)構(gòu)學(xué)習(xí)問(wèn)題.
Fig. 2 The influence of λ on sample weights圖2 參數(shù)λ對(duì)樣本權(quán)重分布的影響
本文主要提出了一種基于樣本加權(quán)的多視圖聚類(lèi)算法(SWMVC).為了更好地學(xué)習(xí)多視圖蘊(yùn)含的信息,本文受Adapt-SA算法啟發(fā),引進(jìn)多視圖學(xué)習(xí)思想,從不同視圖角度學(xué)習(xí)樣本對(duì)簇結(jié)構(gòu)的貢獻(xiàn)度.這種多視圖樣本加權(quán)學(xué)習(xí)機(jī)制不僅體現(xiàn)了樣本差異性,而且還刻畫(huà)了視圖的重要度,實(shí)現(xiàn)了對(duì)數(shù)據(jù)“局部”和“全局”性質(zhì)的學(xué)習(xí).與此同時(shí),SWMVC能夠保留數(shù)據(jù)原始信息,有助于降低模型復(fù)雜度.在6個(gè)異質(zhì)視圖數(shù)據(jù)集和2個(gè)同質(zhì)視圖數(shù)據(jù)集上的大量實(shí)驗(yàn)對(duì)比表明:本文提出的模型在異質(zhì)視圖數(shù)據(jù)上具有不錯(cuò)的聚類(lèi)效果.