汪忠國(guó)，吳 敏，譚芳芳

1.安徽信息工程學(xué)院，安徽 蕪湖 241000

2.中國(guó)科學(xué)技術(shù)大學(xué) 軟件學(xué)院，合肥 230051

3.安徽信息工程學(xué)院 基礎(chǔ)教學(xué)部，安徽 蕪湖 241000

稀疏混合圖隨機(jī)跳躍Web對(duì)象多標(biāo)簽半監(jiān)督分類*

汪忠國(guó)1+，吳 敏2，譚芳芳3

1.安徽信息工程學(xué)院，安徽 蕪湖 241000

2.中國(guó)科學(xué)技術(shù)大學(xué) 軟件學(xué)院，合肥 230051

3.安徽信息工程學(xué)院 基礎(chǔ)教學(xué)部，安徽 蕪湖 241000

+Corresponding author:E-mail:wguoshzhuo@sina.com

WANG Zhongguo,WU M in,TAN Fangfang.Sparsem ixed graph random jum p transition policy forWeb objectmulti-labelclassification.Journalof Frontiersof Computer Scienceand Technology,2017,11(7)：1166-1174.

針對(duì)Web對(duì)象的多標(biāo)簽分類的自動(dòng)標(biāo)注過程中，存在的標(biāo)記數(shù)據(jù)耗時(shí)和不足導(dǎo)致分類性能不高的問題，提出了基于稀疏混合圖隨機(jī)跳躍變遷策略的Web對(duì)象多標(biāo)簽分類算法。首先，在構(gòu)建Web對(duì)象親和子圖和標(biāo)簽相關(guān)子圖基礎(chǔ)上，通過權(quán)重自適應(yīng)方式構(gòu)建Web對(duì)象標(biāo)簽分類的混合圖，實(shí)現(xiàn)半監(jiān)督形式的自動(dòng)標(biāo)注，解決人工標(biāo)注存在的耗時(shí)問題；其次，針對(duì)混合圖求解問題，利用隨機(jī)跳躍變遷策略實(shí)現(xiàn)混合圖對(duì)象與預(yù)測(cè)標(biāo)簽間的概率分配，實(shí)現(xiàn)未標(biāo)記的Web對(duì)象所屬類別標(biāo)簽的概率估計(jì)，并獲得其top-k最高相關(guān)性分?jǐn)?shù)；最后，在UCI Web測(cè)試集和真實(shí)大數(shù)據(jù)上進(jìn)行測(cè)試，結(jié)果顯示所提算法的Rand指標(biāo)要優(yōu)于對(duì)比算法，驗(yàn)證了算法的有效性。

大數(shù)據(jù)；隨機(jī)跳躍；Web對(duì)象；標(biāo)簽分類；自動(dòng)標(biāo)注

1 引言

隨著互聯(lián)網(wǎng)的迅速發(fā)展，異構(gòu)網(wǎng)絡(luò)對(duì)象大量出現(xiàn)，自動(dòng)標(biāo)注已成為搜索、排名和索引應(yīng)用中越來越重要的組成部分[1-2]。Web對(duì)象的注釋可利用多標(biāo)簽分類方式實(shí)現(xiàn)，一個(gè)對(duì)象可從受控詞匯表分配一個(gè)或多個(gè)標(biāo)簽[3]。全監(jiān)督學(xué)習(xí)分類過程，需要足夠量的標(biāo)記數(shù)據(jù)，以進(jìn)行有效的訓(xùn)練[4]。但在現(xiàn)實(shí)應(yīng)用中，數(shù)據(jù)的標(biāo)記過程非常耗時(shí)，如何利用未標(biāo)記數(shù)據(jù)[5]，有效減少所需的多標(biāo)簽對(duì)象分類標(biāo)記數(shù)據(jù)量，是研究的熱點(diǎn)。

當(dāng)前，在半監(jiān)督多標(biāo)簽分類領(lǐng)域的研究主要有如下4個(gè)方向：（1）非負(fù)矩陣分解[6]，該方法尋找非負(fù)矩陣，根據(jù)設(shè)定的更新法則獲得滿足非負(fù)矩陣相等的乘子，但其存在矩陣構(gòu)建復(fù)雜和計(jì)算較為耗時(shí)的問題；（2）基于圖形的方法[7]，該方法將Web標(biāo)簽分類過程抽象為圖形，分類過程更為直觀；（3）基于內(nèi)容的特征方法[8]，此類方法需要用到標(biāo)簽特征，但是特征提取算法會(huì)影響標(biāo)簽的分類效果；（4）主題模型方式[9]，即對(duì)文字隱含主題建模，克服傳統(tǒng)信息檢索存在的文檔相似計(jì)算問題，效果很好，唯一缺點(diǎn)是不夠直觀。

近年來研究發(fā)現(xiàn)，圖形方法是半監(jiān)督多標(biāo)簽分類最為有效的方法[10]，該方法將整個(gè)數(shù)據(jù)集作為一個(gè)圖，其中的節(jié)點(diǎn)對(duì)應(yīng)于標(biāo)記和未標(biāo)記的數(shù)據(jù)點(diǎn)（實(shí)例），邊緣則反映了數(shù)據(jù)點(diǎn)之間的相似性。但是，該方法構(gòu)建圖的方式有許多種，例如K NN（K-nearest neighbor）圖或球圖，并且這些圖具有一定的局限性，如對(duì)數(shù)據(jù)噪聲敏感性。同時(shí)所提出的技術(shù)包括采用節(jié)點(diǎn)或邊采樣進(jìn)行原始圖構(gòu)建的方式，但是此類方法需要一定的專業(yè)知識(shí)，會(huì)引入額外的計(jì)算成本。同時(shí)，現(xiàn)有圖形方法在處理多標(biāo)簽分類時(shí)，沒有充分考慮標(biāo)簽之間的相互依存關(guān)系[11]。雖然簡(jiǎn)化了問題設(shè)計(jì)，但會(huì)導(dǎo)致標(biāo)簽分類算法效果不理想，特別是對(duì)于依存關(guān)系多標(biāo)簽，分別執(zhí)行標(biāo)簽分類，會(huì)相應(yīng)增加算法實(shí)現(xiàn)難度，不利于標(biāo)注效果提升。

對(duì)此，提出了一種基于稀疏混合圖隨機(jī)跳躍變遷Web對(duì)象多標(biāo)簽半監(jiān)督分類算法，其將對(duì)象和標(biāo)簽融合為單一混合圖，其中包含對(duì)象親和子圖和標(biāo)簽相關(guān)子圖，以及連接對(duì)象和標(biāo)簽的邊緣。通過添加對(duì)象和標(biāo)簽的權(quán)重邊緣進(jìn)行混合圖構(gòu)建。然后，通過隨機(jī)跳躍過程實(shí)現(xiàn)混合圖對(duì)象標(biāo)簽關(guān)聯(lián)，并對(duì)未標(biāo)記對(duì)象標(biāo)簽連接進(jìn)行概率估計(jì)。

本文貢獻(xiàn)為：（1）提出以對(duì)象標(biāo)簽混合圖為基礎(chǔ)的半監(jiān)督學(xué)習(xí)方法進(jìn)行網(wǎng)絡(luò)對(duì)象的自動(dòng)標(biāo)注，并利用稀疏表示和隨機(jī)游動(dòng)的混合對(duì)象標(biāo)簽圖進(jìn)行權(quán)重自適應(yīng)分配。（2）探索利用參數(shù)自由最小化實(shí)現(xiàn)稀疏圖重建，可對(duì)網(wǎng)絡(luò)對(duì)象特征尺寸遠(yuǎn)大于樣本大小的相似性進(jìn)行計(jì)算。（3）利用雅虎真實(shí)數(shù)據(jù)驗(yàn)證所提算法的有效性。

2 問題定義

給定一組標(biāo)記和未標(biāo)記的Web對(duì)象及一組標(biāo)簽，目標(biāo)是為每個(gè)未標(biāo)記的Web對(duì)象自動(dòng)分配k個(gè)標(biāo)簽。可通過執(zhí)行隨機(jī)跳躍變遷策略對(duì)混合Web對(duì)象標(biāo)簽圖進(jìn)行標(biāo)簽分配概率計(jì)算。所采用的混合圖G包含兩個(gè)獨(dú)立子圖，分別命名為Web對(duì)象親和子圖G和標(biāo)簽相關(guān)子圖GL，子圖G和GL通過一組Web對(duì)象標(biāo)簽邊緣E(L)相連，表示W(wǎng)eb對(duì)象和標(biāo)簽之間的分配關(guān)系。

定義1（Web對(duì)象親和子圖）定義G=(V,E)，其為有向圖，V中的每個(gè)頂點(diǎn)表示中的一個(gè)Web對(duì)象，每個(gè)邊緣E連接權(quán)重表征Web對(duì)象間的親和關(guān)系。

定義2（標(biāo)簽相關(guān)子圖）定義GL=(VL,EL)，其為無向圖，VL中的每個(gè)頂點(diǎn)表示L中的一個(gè)標(biāo)簽，每個(gè)邊緣EL連接權(quán)重表征標(biāo)簽間的相關(guān)性。

定義3（混合圖）定義G=(V,E)，其為有向圖，頂點(diǎn) 集 為 V=V×VL，邊 緣 集 為 E=E()?E(L)?E(L)，E(L)中的每個(gè)邊緣表征對(duì)應(yīng)Web對(duì)象和節(jié)點(diǎn)間的關(guān)系。

形式上，自動(dòng)標(biāo)注任務(wù)可表示成多標(biāo)簽Web對(duì)象分類問題：對(duì)于給定標(biāo)簽和未標(biāo)記Web對(duì)象集合={o1,o2,…,on}，及 k個(gè)標(biāo)簽集 L={l1,l2,…,lk}，每個(gè)Web對(duì)象oi可提取一個(gè)特征點(diǎn)并表征為特征向量vi∈Rm，其對(duì)應(yīng)標(biāo)簽子集li?Rk。Web對(duì)象親和子圖G中，Web 對(duì)象之間的相似性測(cè)度為 W∈Rn×n，W(i,j)表示W(wǎng)eb對(duì)象oi和oj之間的相似度；類似的，標(biāo)簽相關(guān)子圖WL∈Rk×k，表征標(biāo)簽 li和 lj間的關(guān)聯(lián)度。假定前r個(gè)Web對(duì)象已標(biāo)記，目標(biāo)是從L中選擇最合適的標(biāo)簽對(duì)剩余n-r未標(biāo)記Web對(duì)象進(jìn)行標(biāo)簽預(yù)測(cè)。對(duì)于向量w，||w||1表示w的L1范數(shù)，I表示單位矩陣，Λ表示逆矩陣，W表示給定矩陣。

3 混合圖構(gòu)建

如前所述，現(xiàn)有圖形方法，例如K NN圖或球圖，對(duì)數(shù)據(jù)噪聲存在較大敏感性，其采用的通過節(jié)點(diǎn)或邊采樣進(jìn)行原始圖構(gòu)建的方式，需要專業(yè)知識(shí)，會(huì)增加額外的計(jì)算成本。對(duì)此，這里針對(duì)Web對(duì)象和標(biāo)簽的標(biāo)注問題，通過構(gòu)建Web對(duì)象親和子圖和標(biāo)簽相關(guān)子圖，將標(biāo)注問題設(shè)計(jì)為兩子圖節(jié)點(diǎn)間的權(quán)重分配問題，實(shí)現(xiàn)對(duì)象標(biāo)簽的自適應(yīng)概率分配。

3.1 Web對(duì)象親和子圖

在對(duì)象親和子圖中，每個(gè)頂點(diǎn)表示一個(gè)Web對(duì)象特征向量。加權(quán)邊緣能夠反映對(duì)象之間的親和力。對(duì)象親和子圖是基于稀疏表示構(gòu)造的，而不是傳統(tǒng)的一對(duì)一的兩兩相似圖。因此，它對(duì)數(shù)據(jù)噪聲不敏感，可有效避免冗余和信息分散，并且這種稀疏重建過程能夠更好地捕捉對(duì)象間的語(yǔ)義關(guān)系，從而改善對(duì)象的半監(jiān)督分類。

給定標(biāo)記Web對(duì)象矩陣，其由所有類 Α={Α1,Α2,…,Αk}構(gòu)成，其中 Αk∈Rm×nk為第k個(gè)類別的訓(xùn)練樣本。為表征訓(xùn)練Web對(duì)象的結(jié)構(gòu)信息，需從原始Web對(duì)象 Α′={Α1′,Α2′,…,Αk′}中進(jìn)行字典學(xué)習(xí)，其中Αk′∈ Rm×dk，dk≤nk。這里采用稀疏非負(fù)矩陣分解來生成字典。利用稀疏非負(fù)矩陣分解將原標(biāo)簽Web對(duì)象轉(zhuǎn)化成壓縮格式，可保留原始Web對(duì)象的結(jié)構(gòu)信息。對(duì)子數(shù)據(jù)集進(jìn)行矩陣因式分解：

則整個(gè)數(shù)據(jù)集可表示為V=U?A，其中U為未標(biāo)記Web對(duì)象。對(duì)于給定Web對(duì)象可表示成特征向量集V={v1,v2,…,vn}，其中vi∈Rm，可基于稀疏學(xué)習(xí)框架構(gòu)建G的l1范數(shù)圖，Web對(duì)象的每個(gè)特征向量都應(yīng)是具有非負(fù)系數(shù)的數(shù)據(jù)集內(nèi)所有其他特征向量的線性組合。稀疏表示給出了每個(gè)特征向量和其他特征向量間的關(guān)系，可以一對(duì)一方式構(gòu)建Web對(duì)象的親和力圖。

雖然底層組合優(yōu)化性質(zhì)導(dǎo)致稀疏解決方案求解為NP難問題，稀疏表示仍可通過凸l1范數(shù)最小化進(jìn)行修復(fù)。對(duì)于給定Web對(duì)象vi，其與其他Web對(duì)象的關(guān)系可通過vi=Viw獲得，其中vi∈Rm是重建樣本，w∈Rn是重建系數(shù)，其由除vi外其余Web對(duì)象的K個(gè)標(biāo)簽類別進(jìn)行構(gòu)建，可表示為如下最小化問題：

其中，||·||1為w的l1范數(shù)，趨向于最小化重建誤差的l1范數(shù)。利用線性規(guī)劃算法求解該方程，要求vi=Viw為確定系統(tǒng)的線性方程組。特征維數(shù)須小于樣本空間維數(shù)，即m?n。然而在實(shí)驗(yàn)中，數(shù)據(jù)集并不符合該前提條件。例如，雅虎藝術(shù)數(shù)據(jù)集包含大約5 000個(gè)樣本，但其特征維度超過20 000，即m?n。因此，式（3）無精確解。為此，可通過m×m單位矩陣將超定系統(tǒng)Vi轉(zhuǎn)化為不確定系統(tǒng)，則式（3）可轉(zhuǎn)換為：

其中，λ為平衡重建誤差和稀疏度的正則化標(biāo)量。使用截?cái)嗯ｎD內(nèi)點(diǎn)法來解決該優(yōu)化問題。算法1給出基于稀疏圖重建方法的Web對(duì)象親和子圖構(gòu)建方法。

算法1親和子圖構(gòu)建方法

3.2 標(biāo)簽相關(guān)子圖

標(biāo)簽相關(guān)子圖用于捕獲類別標(biāo)簽間的相互關(guān)系，其中頂點(diǎn)表示成二進(jìn)制向量，以此表達(dá)類別標(biāo)簽。通過標(biāo)簽共生的相似性和內(nèi)核為基礎(chǔ)的相似性計(jì)算，可對(duì)標(biāo)簽間的相關(guān)性進(jìn)行估計(jì)。使用余弦相似性來衡量標(biāo)簽的相關(guān)性，構(gòu)造標(biāo)簽矩陣C∈RK×N，其中每行表示每個(gè)訓(xùn)練Web對(duì)象中出現(xiàn)的標(biāo)簽，每列表示每個(gè)訓(xùn)練Web對(duì)象的標(biāo)簽分配。Ci,j∈{0,1}表示第 j個(gè)Web對(duì)象的第i個(gè)標(biāo)簽的出現(xiàn)概率。這里，標(biāo)簽矩陣是非常稀疏的。對(duì)此矩陣進(jìn)行平滑操作，用標(biāo)簽小的非零概率值取代概率為0的矩陣值。平滑概率為：

其中，n(lj,O)表示W(wǎng)eb對(duì)象分配的標(biāo)簽lj數(shù)量；||為訓(xùn)練Web對(duì)象數(shù)量。則C可表示為：

可歸一化為：

其中，sli,lj評(píng)價(jià)li和lj之間的共現(xiàn)頻率，余弦相似性為：

因此，共生的相似性為：

其中，λ是超定參數(shù)；li是二進(jìn)制向量。要表現(xiàn)出第二直覺，采用內(nèi)核相似性，令Γli和Γlj分別為包含標(biāo)簽li和lj的Web對(duì)象集，則基于內(nèi)核的li和lj相似性為：

其中，K是給定Web對(duì)象vi的近鄰數(shù)目，其聯(lián)系標(biāo)簽為li；vi和vj分別表示對(duì)應(yīng)標(biāo)簽li和lj的Web對(duì)象特征。子圖權(quán)值矩陣可通過結(jié)合兩成對(duì)標(biāo)簽進(jìn)行相似性計(jì)算：

3.3 子圖融合

在獲得Web對(duì)象親和子圖G和標(biāo)簽相關(guān)子圖GL后，可結(jié)合兩圖并通過添加Web對(duì)象標(biāo)簽的邊緣進(jìn)行混合圖G構(gòu)建。不同的標(biāo)簽對(duì)特定Web對(duì)象有不同貢獻(xiàn)，可通過標(biāo)簽間的鏈接權(quán)重表征。與等值標(biāo)簽權(quán)重不同，這里自適應(yīng)地計(jì)算并分配不同的權(quán)重到連接邊緣中：

Fig.1 Sub graph fusion process圖1 子圖融合過程

子圖融合過程包含兩步：邊緣添加和權(quán)重賦值。這里以圖1為例對(duì)子圖融合過程進(jìn)行闡述。圖1中對(duì)象17在對(duì)象的親和圖中分配有3個(gè)標(biāo)簽“Science”、“Food”和“Industry”。在此情形下，首先，3個(gè)對(duì)象標(biāo)簽的邊緣被添加在混合圖中，并將其連接在一起。其次，注意到不同的標(biāo)簽對(duì)特定對(duì)象有不同的貢獻(xiàn)，例如對(duì)于對(duì)象17“Science”標(biāo)簽相對(duì)于“Food”標(biāo)簽更為重要，則對(duì)于“Science”標(biāo)簽與對(duì)象17的連接權(quán)重應(yīng)賦予更大的值，這里采用的邊緣權(quán)重計(jì)算公式見式（15）。

4 混合圖的隨機(jī)跳躍變遷策略

本章主要針對(duì)3.3節(jié)的子圖融合圖，在對(duì)象節(jié)點(diǎn)與標(biāo)簽節(jié)點(diǎn)邊緣權(quán)重基礎(chǔ)上，進(jìn)行自動(dòng)標(biāo)注研究，特別是針對(duì)未標(biāo)記對(duì)象，設(shè)計(jì)一種高效的標(biāo)注策略。

4.1 概率矩陣定義

在獲得混合圖G后，計(jì)算每個(gè)未標(biāo)記Web對(duì)象的標(biāo)簽相關(guān)性，高相關(guān)性表征正確標(biāo)簽分配具有較高的概率。利用這種相關(guān)性指導(dǎo)標(biāo)注過程，可避免標(biāo)注的盲目性，提高標(biāo)注效率。首先，需要計(jì)算混合圖G的親和矩陣：

其中，W可根據(jù)算法1計(jì)算；WL可根據(jù)式（14）計(jì)算；WL可根據(jù)式（15）計(jì)算，。從權(quán)重矩陣W獲得的轉(zhuǎn)移概率矩陣P為：

其中，P和PLL分別是Web對(duì)象親和子圖G和標(biāo)簽相關(guān)子圖GL的內(nèi)部轉(zhuǎn)移概率矩陣；PL和PL分別為G和GL間的內(nèi)部轉(zhuǎn)移概率矩陣。然后，設(shè)置跳躍概率α∈[0,1]，表示子圖間的隨機(jī)跳躍變遷概率。并不是G中的所有頂點(diǎn)，都與Web對(duì)象標(biāo)簽的邊緣相連接。例如，未標(biāo)記Web對(duì)象不分配任何標(biāo)簽，則沒有與任何Web對(duì)象標(biāo)簽邊緣連接。表示W(wǎng)eb對(duì)象oi至少與1個(gè)Web對(duì)象標(biāo)簽邊緣連接。在隨機(jī)跳躍變遷過程中，如果其位于G中一個(gè)Web對(duì)象頂點(diǎn)，則其至少與1個(gè)Web對(duì)象標(biāo)簽邊緣連接，它將以概率α跳到標(biāo)簽相關(guān)子圖GL，或以概率1-α繼續(xù)停留在Web對(duì)象親和子圖G。

現(xiàn)在用如下公式轉(zhuǎn)換矩陣對(duì)其進(jìn)行描述。

（1）POO(i,j)與矩陣W成比例，可根據(jù)算法1獲得：

因?yàn)閃表征Web對(duì)象間的相似度，表示W(wǎng)eb對(duì)象親和子圖G中頂點(diǎn)i和 j的權(quán)重邊緣和。

（2）PLL(i,j)是從Web對(duì)象到標(biāo)簽的轉(zhuǎn)換概率矩陣，其與矩陣WL成比例。

（3）PL(i,j)是從Web對(duì)象到標(biāo)簽的轉(zhuǎn)換概率矩陣，其與矩陣WL成比例。

（4）PL(i,j)是從標(biāo)簽到Web對(duì)象的轉(zhuǎn)換概率矩陣，等于PL(i,j)的轉(zhuǎn)置。

其中，D、DL、DL和 DLT為對(duì)角矩陣，可得：

4.2 隨機(jī)跳躍變遷策略

傳統(tǒng)圖形方法采用節(jié)點(diǎn)或邊采樣方式進(jìn)行標(biāo)記，但是Web中對(duì)象和標(biāo)簽的數(shù)量巨大，采樣率設(shè)置及采樣的無序性會(huì)降低標(biāo)記效果。因此，這里通過在混合圖G中Web對(duì)象和標(biāo)簽節(jié)點(diǎn)進(jìn)行隨機(jī)跳躍變遷，來估計(jì)一個(gè)未標(biāo)記Web對(duì)象可能屬于的類別標(biāo)簽。該方法特點(diǎn)是找到對(duì)于給定未標(biāo)記Web對(duì)象的類別標(biāo)簽，其具有top-k最高相關(guān)性分?jǐn)?shù)。該方式充分考慮節(jié)點(diǎn)間的相關(guān)性，可對(duì)標(biāo)記過程進(jìn)行指導(dǎo)，提高自動(dòng)標(biāo)注效果。

隨機(jī)跳躍變遷思路：使用對(duì)象的親和力稀疏圖重構(gòu)提取結(jié)構(gòu)元文本，利用標(biāo)簽相關(guān)，通過線性組合捕捉標(biāo)簽共生的兩兩相關(guān)性。通過隨機(jī)游走的自適應(yīng)權(quán)重分配，進(jìn)行混合圖構(gòu)造來推斷標(biāo)簽和對(duì)象之間的概率分配關(guān)系。通過隨機(jī)跳躍變遷策略沿邊緣以概率1-c跳躍到鄰近頂點(diǎn)，或者以概率c跳回到頂點(diǎn)i。令ui(j)表示從頂點(diǎn)i到頂點(diǎn) j的穩(wěn)定狀態(tài)訪問速率，可用來估計(jì)頂點(diǎn)i和頂點(diǎn) j之間的親和力。

相關(guān)性評(píng)分計(jì)算過程如下：對(duì)于給定的未標(biāo)記測(cè)試Web對(duì)象oi，其穩(wěn)態(tài)概率可計(jì)算為：

其中，πoi為重啟向量，初始化πoi為零向量，第i個(gè)條目設(shè)置為1。然后執(zhí)行隨機(jī)跳躍變遷策略直至收斂。融合概率向量uoi表示從Web對(duì)象oi開始的混合圖G中的V()和V(L)的所有頂點(diǎn)的穩(wěn)態(tài)訪問概率，主要關(guān)注點(diǎn)在V(L)的訪問概率，利用其可計(jì)算未標(biāo)記Web對(duì)象oi的分配概率。

算法2隨機(jī)跳躍變遷策略

輸出：等級(jí)收斂分配概率

1.for i=1:t do

3. 預(yù)計(jì)算并存儲(chǔ)Λ=(S-1-αVU)-1；

4. 計(jì)算并輸出uoi=(1-α)(voi+αU∧Vvoi)；

5.end

4.3 時(shí)間復(fù)雜度分析

假定混合圖稀疏矩陣中，頂點(diǎn)僅與k組近鄰節(jié)點(diǎn)關(guān)聯(lián)，則矩陣每行至多有k組非零特征元素。假定tmax為迭代過程的次數(shù)上限，迭代過程的時(shí)間復(fù)雜度是O((n-|T|)k|T|tmax)。因?yàn)閷?shí)驗(yàn)過程中tmax與k均為用戶所指定，且為常值，所以可直接將其移除，而不會(huì)對(duì)時(shí)間復(fù)雜度O((n-|T|)|T|)產(chǎn)生影響。此外，相似度矩陣計(jì)算成本為O(|T|nk)。隨機(jī)跳躍過程需要O(|T|3)計(jì)算復(fù)雜度。在對(duì)真實(shí)大型數(shù)據(jù)進(jìn)行處理時(shí)，會(huì)存在|T|遠(yuǎn)小于n的情形，且此情形可忽略其對(duì)算法計(jì)算復(fù)雜度的影響。因此該過程的計(jì)算復(fù)雜度簡(jiǎn)化成線性復(fù)雜度O(n)。若考慮相似度稀疏矩陣的計(jì)算復(fù)雜度O(n2)，那么本文算法的計(jì)算復(fù)雜度可表示為O(n2)。

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)設(shè)置

本節(jié)實(shí)驗(yàn)選取的對(duì)比算法為光譜學(xué)習(xí)（spectral learning，SL）[12]、高斯內(nèi)核K均值（sem i-supervised kernelK-means，SSKK）[13]、譜正則化約束聚類（constrained clustering via spectral regularization，CCSR）[14]及成對(duì)度量約束K-均值（metric pairw ise constrainedK-means，MPCK）[15]4種半監(jiān)督分類方法，在UCI測(cè)試集及真實(shí)測(cè)試集上進(jìn)行實(shí)驗(yàn)驗(yàn)證。表1給出本文使用的8組測(cè)試集信息，共涉及4組UCIWeb測(cè)試集及4組大型Web真實(shí)測(cè)試集。

Table1 Experimental testsets表1 實(shí)驗(yàn)測(cè)試集

表 1中，Parkinsons、Tissue和 Breast均為醫(yī)學(xué)Web對(duì)象集，Ionosphere為物理Web對(duì)象集，TDT2為文本W(wǎng)eb對(duì)象集，MNIST為數(shù)字識(shí)別Web測(cè)試集，Letter為英文字母Web測(cè)試集，CMU PIE是人臉Web測(cè)試集。

為對(duì)5種算法進(jìn)行公正評(píng)測(cè)，這里基于Rand標(biāo)準(zhǔn)進(jìn)行評(píng)價(jià)[12]：

式（28）中，TP為同類對(duì)象正確劃分?jǐn)?shù)量；TN為不同類對(duì)象正確劃分?jǐn)?shù)量?？梢奟and指標(biāo)越大表明算法的分類效果越好。硬件設(shè)置：CPU i5-4510，RAM 4GB ddr3-1 600，系統(tǒng)Win7旗艦。

5.2 實(shí)驗(yàn)結(jié)果

5.2.1 UCI數(shù)據(jù)集實(shí)驗(yàn)

圖2給出5種標(biāo)簽聚類方法在選取的4組UCI Web測(cè)試集上Rand指標(biāo)學(xué)習(xí)過程曲線。

根據(jù)圖2給出的5種對(duì)比算法在4組UCIWeb測(cè)試集上的Rand指標(biāo)曲線對(duì)比情況可知，本文算法的Rand指標(biāo)要整體上優(yōu)于選取的對(duì)比算法。圖2（a）中，在約束數(shù)量小于300時(shí)，本文算法的Rand指標(biāo)要差于CCSR和SSKK算法。而圖2（d）中，在約束數(shù)量小于200時(shí)，本文算法的Rand指標(biāo)要差于CCSR算法。圖2（b）和圖2（c）中，在約束數(shù)量較低時(shí)，幾種算法的Rand指標(biāo)差距不大，這表明本文算法在約束數(shù)量多時(shí)性能優(yōu)勢(shì)更為明顯。

5.2.2 真實(shí)測(cè)試集實(shí)驗(yàn)

圖3給出5種標(biāo)簽聚類方法在選取的4組真實(shí)測(cè)試集上Rand指標(biāo)學(xué)習(xí)過程曲線。

根據(jù)圖3給出的5種對(duì)比算法在4組真實(shí)Web測(cè)試集上的Rand指標(biāo)曲線對(duì)比情況可知，本文算法的Rand指標(biāo)要更為明顯優(yōu)于對(duì)比算法。圖3（a）和圖3（c）顯示本文算法在TDT2測(cè)試集和Letter測(cè)試集上，在選取約束數(shù)量情況下，要明顯優(yōu)于對(duì)比算法。圖3（b）和圖3（d）顯示本文算法在MNIST測(cè)試集和CMU PIE測(cè)試集上，在約束數(shù)量小于60時(shí)，與SSKK算法相差不大，但是隨著約束數(shù)量升高，本文算法要明顯優(yōu)于選取的對(duì)比算法。上述實(shí)驗(yàn)結(jié)果顯示，本文算法在真實(shí)測(cè)試集上具有與在UCI構(gòu)造測(cè)試集上相近的測(cè)試結(jié)果，顯示了本文算法對(duì)于實(shí)際情況的適應(yīng)性。

6 結(jié)束語(yǔ)

Fig.2 Comparison of UCIWeb testsets圖2 UCIWeb測(cè)試集對(duì)比

Fig.3 Comparison of real testsets圖3 真實(shí)測(cè)試集對(duì)比

本文提出了基于稀疏混合圖隨機(jī)跳躍變遷策略的Web對(duì)象多標(biāo)簽分類算法，有效解決了Web對(duì)象多標(biāo)簽分類的自動(dòng)標(biāo)注過程中計(jì)算性能不高的問題。算法用到了混合圖概念和隨機(jī)跳躍變遷策略，并通過UCIWeb測(cè)試集和真實(shí)大數(shù)據(jù)測(cè)試，驗(yàn)證了其有效性。下一步工作計(jì)劃研究其他標(biāo)簽相似性計(jì)算方法，并研究其如何影響標(biāo)簽分類精度，以及利用過渡概率與邊權(quán)重實(shí)現(xiàn)隨機(jī)跳躍變遷策略性能提升等。

References:

[1]Chen Zezhi,Ellis T.Semi-automatic annotation samples for vehicle type classification in urban environments[J].IET IntelligentTransportSystems,2015,9(3):240-249.

[2]Khosrow-Khavar F,Tavakolian K,Blaber A P.Automatic annotation of seismocardiogram w ith high-frequency precordial accelerations[J].IEEE Journal of Biomedical and Health Informatics,2015,19(4):1428-1434.

[3]Zhang Jinzeng,Wen Jie,Meng Xiaofeng.Multi-tag route query based on order constraints in road networks[J].Journal of Computers,2012,35(11):2317-2322.

[4]He Ping,Xu Xiaohua,Lu Lin.Sem i-supervised clustering via two-level random walk[J].Journalof Software,2014,25(5):997-1013.

[5]Rad R,Jamzad M.Automatic image annotation by a loosely joint non-negative matrix factorisation[J].IET Computer Vision,2015,9(6):806-813.

[6]Cabral R,De la Torre F,Costeira JP.Matrix completion for weakly-supervised multi-label image classification[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2015,37(1):121-135.

[7]Passino G,Patras I,Izquierdo E.Aspect coherence forgraphbased semantic image labelling[J].IET Computer Vision,2010,4(3):183-194.

[8]Contractor D,Negi S,Popat K.Smarter learning content management using the learning content hub[J].IBM Journalof Research and Development,2015,59(6):1-9.

[9]Sabuncu M R,Yeo B T T,Van LeemputK.A generativemodel for image segmentation based on label fusion[J].IEEE Transactionson Medical Imaging,2010,29(10):1714-1729.

[10]Karasuyama M,Mam itsuka H.Multiple graph label propagation by sparse integration[J].IEEE Transactions on Neural Networksand Learning Systems,2013,24(12):1999-2012.

[11]Feng Lin,Wang Jing,Liu Shenglan.Multi-label dimensionality reduction and classification w ith extreme learningmachines[J].Journal of Systems Engineering and Electronics,2014,25(3):502-513.

[12]Kamvar SD,K lein D,Manning C D.Spectral learning[C]//Proceedings of the 18th International Joint Conference on Artificial Intelligence,Acapulco,Mexico,Aug 9-15,2003.San Francisco,USA:Morgan Kaufmann Publishers Inc,2003:561-566.

[13]Kulis B,Basu S,Dhillon I,etal.Semi-supervised graph clustering:a kernel approach[J].Machine Learning,2009,74(1):1-22.

[14]LiZhenguo,Liu Jianzhuang,Tang Xiaoou.Constrained clustering via spectral regularization[C]//Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition,M iam i,USA,Jun 20-25,2009.Washington:IEEEComputer Society,2009:421-428.

[15]CaiDeng,He Xiaofei,Han Jiawei,etal.Graph regularized non-negativematrix factorization for data representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(8):1548-1560.

附中文參考文獻(xiàn)：

[3]張金增,文潔,孟小峰.路網(wǎng)環(huán)境下訪問序列受限的多標(biāo)簽路線查詢算法[J].計(jì)算機(jī)學(xué)報(bào),2012,35(11):2317-2322.

[4]何萍,徐曉華,陸林.雙層隨機(jī)游走半監(jiān)督聚類[J].軟件學(xué)報(bào),2014,25(5):997-1013.

汪忠國(guó)（1985—），男，安徽蕪湖人，2010年于中國(guó)科學(xué)技術(shù)大學(xué)獲得碩士學(xué)位，現(xiàn)為安徽信息工程學(xué)院講師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘。

WU M in was born in 1963.He received the M.S.degree from SoutheastUniversity in 1989.Now he is a professor and Ph.D.supervisor at University of Science and Technology of China.His research interest is educational informationization.

吳敏（1963—），男，安徽蚌埠人，1989年于東南大學(xué)獲得碩士學(xué)位，現(xiàn)為中國(guó)科學(xué)技術(shù)大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)榻逃畔⒒?/p>

TAN Fangfang was born in 1979.She received the M.S.degree from Hunan Normal University in 2010.Now she isa lectureratAnhui Instituteof Information Technology.Her research interest is fuzzymathematics.

譚芳芳（1979—），女，湖南衡陽(yáng)人，2010年于湖南師范大學(xué)獲得碩士學(xué)位，現(xiàn)為安徽信息工程學(xué)院講師，主要研究領(lǐng)域?yàn)槟：龜?shù)學(xué)。

Sparse M ixed Graph Random Jum p Transition Policy for Web Object M ulti-Label Classification*

WANG Zhongguo1+,WUM in2,TAN Fangfang3

1.Anhui Institute of Information Technology,Wuhu,Anhui241000,China

2.Schoolof Software Engineering,University of Science and Technology of China,Hefei230051,China

3.Foundation Teaching Department,Anhui Institute of Information Technology,Wuhu,Anhui241000,China

In order to solve the problem of time consum ing and insufficient for labeling data,which leads the low computationalefficiency inmulti-label classification ofWeb objects,this paper proposes amulti-label classification algorithm based on sparsem ixed graph random jump transition strategy forWeb object.Firstly,based on the construction of theWeb objectaffinity graph and tag correlation,weightadaptivemethod is used to constructa hybrid graph ofWeb object label classification,which realizes the automatic annotation of sem i-supervised form and solves the time consuming problem ofmanualannotation;Secondly,in order to solve the problem ofm ixed graph,the random jump transition strategy is used to get the probability distribution between them ixed graph and the prediction tag,which realizes the probability estimation of the class label of the unlabeledWeb objectand obtains the highesttop-k correlation score;Finally,through the teston UCIWeb datasetand realbig data,the results show that the Rand index of the proposed algorithm is better than the selected contrast algorithms,which verifies the effectiveness of the proposed algorithm.

big data;random jump;Web object;labelclassification;automaticmarking

gguowasborn in 1985.He

theM.S.degree in educational technology from University of Science and Technology of China in 2010.Now he is a lecturer atAnhui Institute of Information Technology.His research interest is datam ining.

A

：TP181

*The Natural Science Research Projectof Education Departmentof AnhuiProvince underGrantNo.KJ2016A075(安徽省教育廳自然科學(xué)研究項(xiàng)目).

Received 2016-05,Accepted 2016-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-08-01,http://www.cnki.net/kcms/detail/11.5602.TP.20160801.1406.004.htm l