尚曉群 楊海峰 蔡江輝
(太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 太原 030024)
來自不同數(shù)據(jù)源的數(shù)據(jù)類型(如文本、圖像、視頻等)描述同一對(duì)象或主題,形成了多視圖數(shù)據(jù)[1~3]。例如,一個(gè)多媒體片段可由視頻信號(hào)和音頻信號(hào)同時(shí)描述;一個(gè)網(wǎng)頁的特征可通過文檔文本、超鏈接、圖片信息等表示;一張圖片可通過不同的特征提取器捕獲其相應(yīng)的表示,如LBP、SIFT、HOG等。多視圖數(shù)據(jù)的爆炸性增長,引發(fā)了對(duì)其進(jìn)行有效分析和處理的技術(shù)需求增長。在數(shù)據(jù)挖掘中,聚類分析[4]是一項(xiàng)非常重要的技術(shù),能將相似度高的數(shù)據(jù)劃分到一個(gè)簇。在過去的幾十年里,許多的聚類方法已經(jīng)被發(fā)展,如K-means,譜聚類,基于核的聚類方法,基于圖的聚類方法和基于密度的聚類方法。旨在利用跨視圖間數(shù)據(jù)的互補(bǔ)性和一致性信息,多視圖聚類方法[5~6]已引起廣泛的關(guān)注。
現(xiàn)有的多視圖聚類方法主要分為五類:協(xié)同訓(xùn)練風(fēng)格算法、多核學(xué)習(xí)、多視圖圖形聚類、多視圖子空間聚類、多任務(wù)多視圖聚類[7]。此外,多視圖圖形聚類被進(jìn)一步劃分為基于圖形、基于網(wǎng)絡(luò)和基于譜論;多視圖子空間聚類被進(jìn)一步劃分為基于子空間學(xué)習(xí)和基于非負(fù)矩陣分解。由于多視圖聚類的可擴(kuò)展性,許多學(xué)者做了進(jìn)一步的研究。楊敏申等[8]在k-means 聚類過程中進(jìn)行特征降維,改進(jìn)了多視圖k-means聚類。王浩等[9]對(duì)基于圖形的多視圖聚類在通用方法和圖形度量兩個(gè)方面進(jìn)行研究,提出了一個(gè)基于圖形的多視圖聚類系統(tǒng)GBS。
盡管現(xiàn)有的多視圖聚類算法已在不同方面被改進(jìn)與完善,且取得了不錯(cuò)的聚類結(jié)果,但是,合理挖掘視圖的一致性信息和互補(bǔ)性信息依然是目前多視圖聚類研究的難題與挑戰(zhàn)。針對(duì)這個(gè)問題,本文提出一種新穎的多視圖聚類算法MSFC,基于多變量自學(xué)習(xí)與融合策略過程如圖1 所示,該算法自學(xué)習(xí)數(shù)據(jù)集對(duì)應(yīng)的視圖內(nèi)全局變量、視圖內(nèi)局部變量和視圖間變量,并將其整體投射于一個(gè)相似性度量函數(shù),獲取融合矩陣,以得到更加準(zhǔn)確的聚類結(jié)果。
圖1 基于多變量自學(xué)習(xí)與融合策略過程
信息熵[10~11]是一種信息的度量化方法,基本思想是:用信息量度量信息的多少,再對(duì)產(chǎn)生的信息量作期望。對(duì)于一個(gè)離散隨機(jī)變量X,所有狀態(tài)為{x1,x2,…,xn},當(dāng)狀態(tài)為xi時(shí),對(duì)應(yīng)的概率為pi,則X的信息熵可以被定義為
其中不確定性函數(shù)H 是概率pi的減函數(shù),即當(dāng)概率大時(shí),不確定性??;反之,不確定性就大。信息熵反映了離散隨機(jī)事件的出現(xiàn)概率。
譜聚類方法[12~13]可歸納為以下三個(gè)主要步驟:1)構(gòu)建數(shù)據(jù)集的相似度矩陣W;2)通過相似度矩陣,計(jì)算度矩陣和拉普拉斯矩陣的前k 個(gè)特征值與特征向量,構(gòu)建特征向量空間;3)利用k-means 或其它經(jīng)典聚類算法對(duì)特征向量空間中的特征向量進(jìn)行聚類。假設(shè)數(shù)據(jù)集X 有c 個(gè)簇,譜聚類的目標(biāo)函數(shù):
Y=[y1,y2,y3,…yn]T∈Rn×c是聚類指示矩陣,Y∈Idx表示每個(gè)樣本的類標(biāo)簽向量,即向量yi∈{0,1}c×1只包含一個(gè)元素1,其他的元素均為0。由于在Y上施加離散約束會(huì)導(dǎo)致NP 難問題,為了解決這個(gè)問題,對(duì)Y 松弛化,得到連續(xù)的聚類指示矩陣F=[f1,f2,f3,…,fn]T∈Rn×c,目標(biāo)函數(shù)轉(zhuǎn)換為
FTF=IC是正交約束,F(xiàn) 的最優(yōu)解決方法是包含拉普拉斯矩陣L 的c 個(gè)最小特征值對(duì)應(yīng)的c 個(gè)特征向量。
本算法相繼自學(xué)習(xí)三種多視圖數(shù)據(jù)的變量,即視圖內(nèi)全局變量、視圖內(nèi)局部變量和視圖間變量。為了充分捕獲多視圖數(shù)據(jù)的信息,本算法使用信息熵理論來自學(xué)習(xí)多變量,充分考慮特征與特征、特征與視圖和視圖與視圖的潛在關(guān)系。
給定多視圖數(shù)據(jù)X={x1,x2,…,xn}∈Rd×n,其中,d表示每個(gè)樣例的屬性維數(shù),n表示樣本個(gè)數(shù),X 的第(i,j)項(xiàng)、第i 個(gè)樣本、第j 個(gè)屬性分別用xij、xi和xj表示,s表示視圖個(gè)數(shù),c表示多視圖數(shù)據(jù)的類個(gè)數(shù)。
視圖內(nèi)全局變量:首先,對(duì)于各視圖的每個(gè)屬性,計(jì)算所有樣本與均值的偏離程度gij,然后,依據(jù)偏離程度和聚類個(gè)數(shù),得到視圖內(nèi)全局變量中每個(gè)項(xiàng)的Gij,其計(jì)算公式為
其中,m 是當(dāng)前視圖第j個(gè)屬性的所有樣本的均值,l是該項(xiàng)所在屬性的最小偏離值,b是該項(xiàng)所在屬性的最大偏離值。
視圖內(nèi)局部變量:根據(jù)視圖內(nèi)全局變量和信息熵理論,視圖內(nèi)局部變量中每個(gè)屬性對(duì)應(yīng)的值可被定義為
果實(shí)受到病蟲害和鳥類危害之后會(huì)嚴(yán)重影響到果實(shí)的外部商品性能,還會(huì)導(dǎo)致果樹出現(xiàn)落果現(xiàn)象,影響到果實(shí)質(zhì)量,從而給養(yǎng)殖戶造成更多的額外損失。為了有效預(yù)防上述情況發(fā)生,在果實(shí)形成之后對(duì)果實(shí)進(jìn)行套袋處理,能夠有效避免上述多種因素?fù)p害,同時(shí),還能夠保持果實(shí)應(yīng)有的色彩和飽滿度。果實(shí)套袋時(shí)間要結(jié)合不同果樹品種綜合選擇,一般情況下,果實(shí)套袋時(shí)間應(yīng)該在果實(shí)進(jìn)入膨大期后進(jìn)行。
其中,r 是k 在當(dāng)前屬性中出現(xiàn)的總次數(shù)占所有樣本個(gè)數(shù)的比值。
視圖間變量:基于每個(gè)視圖的視圖內(nèi)全局變量、視圖內(nèi)局部變量和該視圖中屬性數(shù)目占所有視圖屬性數(shù)目的比例,定義視圖間變量中每個(gè)視圖對(duì)應(yīng)的值,如下所示:
其中,b為所有視圖特征的總個(gè)數(shù)。
融合:相似性度量函數(shù)計(jì)算公式如下:
通過式(8),可得到多視圖數(shù)據(jù)的融合矩陣。在此基礎(chǔ)上,構(gòu)建鄰接矩陣W。首先,使用K 近鄰方法計(jì)算中間矩陣P,其基本思想是,若樣本點(diǎn)i屬于樣本點(diǎn)j 的k 近鄰樣本或樣本點(diǎn)j 屬于樣本點(diǎn)i 的k 近鄰樣本,則對(duì)應(yīng)的P 矩陣項(xiàng)設(shè)為1,否則,為0,公式為
其中,KNN(xi)表示樣本xi的k 個(gè)近鄰樣本。然后,由中間矩陣P形成最終鄰接矩陣W,其計(jì)算公式為
基于多變量自學(xué)習(xí)與融合策略的多視圖聚類算法首先根據(jù)聚類數(shù)目,通過式(4)和式(5)獲取每個(gè)視圖的視圖內(nèi)全局變量;基于視圖內(nèi)全局變量和信息熵理論,使用式(6)計(jì)算每個(gè)視圖的視圖內(nèi)局部變量;在此前計(jì)算的基礎(chǔ)上,利用式(7)獲取視圖間變量。其次,相似性度量函數(shù)將基于數(shù)據(jù)集自學(xué)習(xí)的多個(gè)變量融合為一個(gè)矩陣。之后,運(yùn)用式(9)、式(10)、式(11)相繼計(jì)算鄰接矩陣、度矩陣和拉普拉斯矩陣。通過k-means 獲得最終的聚類結(jié)果。具體步驟如下:
本文的算法內(nèi)容主要包括兩個(gè)部分,第一部分是多變量自學(xué)習(xí)與融合,第二部分為獲取聚類標(biāo)簽過程。多變量自學(xué)習(xí)與融合的時(shí)間復(fù)雜度為O(n2),獲取聚類標(biāo)簽過程的時(shí)間復(fù)雜度為O(n2),算法的整體時(shí)間復(fù)雜度為O(n2)。
在1 臺(tái)Intel(R)Core(TM)i5-8250U CPU @1.60GHz 筆記本電腦,Windows 10 操作系統(tǒng)中使用Python語言在Anaconda2的Spyder4.1.5平臺(tái)實(shí)現(xiàn)了基于多變量自學(xué)習(xí)與融合策略的多視圖聚類算法。
本實(shí)驗(yàn)采用5 個(gè)數(shù)據(jù)集評(píng)估提出的MSFC 算法,包括Handwritten(手寫數(shù)字0~9 的多視圖數(shù)據(jù)集,共6 個(gè)視圖)、Anuran Calls(青蛙音節(jié)的特征數(shù)據(jù)集,共兩個(gè)視圖)、IS(室外圖像數(shù)據(jù)集,共兩個(gè)視圖)、Cloud(AVHRR 圖像數(shù)據(jù)集,共兩個(gè)視圖)、3sources(多視圖文本數(shù)據(jù)集,共3 個(gè)視圖)。將所提算法與6 個(gè)多視圖聚類算法進(jìn)行比較,包括AASC[14](親和性聚合譜聚類算法)、RMSC[15](通過低秩和稀疏分解實(shí)現(xiàn)的魯棒多視圖譜聚類算法)、MVGL[16](圖學(xué)習(xí)的多視圖聚類算法)、AWP[17](通過自適應(yīng)加權(quán)普氏分析的多視圖聚類算法)、WMSC[18](基于譜擾動(dòng)的加權(quán)多視圖譜聚類)、MCGC[19](多視圖共識(shí)圖聚類算法)。為了有效評(píng)估各個(gè)聚類算法的性能,本實(shí)驗(yàn)使用四種指標(biāo)作為評(píng)估度量,包含ACC(準(zhǔn)確率)、ARI(調(diào)整蘭德系數(shù))、NMI(標(biāo)準(zhǔn)化互信息)和Purity(純度)。
對(duì)于多視圖對(duì)比算法,我們按照作者原文中給的參數(shù)設(shè)定分別運(yùn)行,并選取參數(shù)范圍內(nèi)對(duì)應(yīng)的最佳聚類結(jié)果作為實(shí)驗(yàn)的最終結(jié)果。在所有對(duì)比算法的實(shí)驗(yàn)中,我們將最近鄰的數(shù)目kNN 均設(shè)置為6。對(duì)于帶有參數(shù)的算法:WMSC(兩個(gè)參數(shù))、RMSC(1 個(gè)參數(shù))、MCGC(1 個(gè)參數(shù)),這些算法的參數(shù)取值范圍為{10-5,10-4,10-3,…,104,105}m,其中,m為算法參數(shù)的數(shù)目。
在本節(jié)中,在五個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)來驗(yàn)證基于多變量自學(xué)習(xí)與融合策略的多視圖聚類算法的有效性。表1、表2、表3 和表4 分別展示了四個(gè)評(píng)價(jià)指標(biāo)的實(shí)驗(yàn)結(jié)果。
表1 在各個(gè)數(shù)據(jù)集上的ACC實(shí)驗(yàn)結(jié)果(%);每列的最高分?jǐn)?shù)用黑體標(biāo)出
表2 在各個(gè)數(shù)據(jù)集上的ARI實(shí)驗(yàn)結(jié)果(%);每列的最高分?jǐn)?shù)用黑體標(biāo)出
表3 在各個(gè)數(shù)據(jù)集上的NMI實(shí)驗(yàn)結(jié)果(%);每列的最高分?jǐn)?shù)用黑體標(biāo)出
表4 在各個(gè)數(shù)據(jù)集上的Purity實(shí)驗(yàn)結(jié)果(%);每列的最高分?jǐn)?shù)用黑體標(biāo)出
從總體上來看,本章提出的基于多變量自學(xué)習(xí)與融合策略的多視圖聚類算法在多個(gè)多視圖數(shù)據(jù)集上均明顯優(yōu)于所有的多視圖聚類基線方法(AASC,RMSC,MVGL,AWP,WMSC,MCGC)。相較于對(duì)比方法,MSFC 算法的優(yōu)勢主要體現(xiàn)在以下兩個(gè)方面。一方面,多變量自學(xué)習(xí)合理提取了多視圖數(shù)據(jù)的潛在結(jié)構(gòu)信息;另一方面,所提相似性度量函數(shù)有效度量了樣本之間的相似性關(guān)系,從而提升了聚類結(jié)果。
本文提出了一種基于多變量自學(xué)習(xí)與融合策略的多視圖聚類算法,該算法通過聚類數(shù)目和信息熵,對(duì)多視圖數(shù)據(jù)的三種變量進(jìn)行自學(xué)習(xí),以充分利用視圖內(nèi)與視圖間的潛在信息。在此基礎(chǔ)上,構(gòu)建了一個(gè)新的相似性度量函數(shù),進(jìn)行多變量的融合。在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,本文提出的MSFC 算法優(yōu)于現(xiàn)有的多視圖聚類算法,驗(yàn)證了該算法的可行性和優(yōu)越性。本文下一步的研究方向?yàn)榭紤]如何能提高算法的運(yùn)行速度,加快完成多視圖數(shù)據(jù)樣本分組的任務(wù)。