汪忠國，吳 敏，譚芳芳

1.安徽信息工程學院，安徽 蕪湖 241000

2.中國科學技術大學 軟件學院，合肥 230051

3.安徽信息工程學院 基礎教學部，安徽 蕪湖 241000

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

汪忠國1+，吳 敏2，譚芳芳3

1.安徽信息工程學院，安徽 蕪湖 241000

2.中國科學技術大學 軟件學院，合肥 230051

3.安徽信息工程學院 基礎教學部，安徽 蕪湖 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.

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

大數(shù)據(jù)；隨機跳躍；Web對象；標簽分類；自動標注

1 引言

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

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

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

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

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

2 問題定義

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

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

定義2（標簽相關子圖）定義GL=(VL,EL)，其為無向圖，VL中的每個頂點表示L中的一個標簽，每個邊緣EL連接權重表征標簽間的相關性。

定義3（混合圖）定義G=(V,E)，其為有向圖，頂點 集 為 V=V×VL，邊 緣 集 為 E=E()?E(L)?E(L)，E(L)中的每個邊緣表征對應Web對象和節(jié)點間的關系。

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

3 混合圖構建

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

3.1 Web對象親和子圖

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

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

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

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

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

其中，λ為平衡重建誤差和稀疏度的正則化標量。使用截斷牛頓內(nèi)點法來解決該優(yōu)化問題。算法1給出基于稀疏圖重建方法的Web對象親和子圖構建方法。

算法1親和子圖構建方法

3.2 標簽相關子圖

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

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

可歸一化為：

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

因此，共生的相似性為：

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

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

3.3 子圖融合

在獲得Web對象親和子圖G和標簽相關子圖GL后，可結合兩圖并通過添加Web對象標簽的邊緣進行混合圖G構建。不同的標簽對特定Web對象有不同貢獻，可通過標簽間的鏈接權重表征。與等值標簽權重不同，這里自適應地計算并分配不同的權重到連接邊緣中：

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

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

4 混合圖的隨機跳躍變遷策略

本章主要針對3.3節(jié)的子圖融合圖，在對象節(jié)點與標簽節(jié)點邊緣權重基礎上，進行自動標注研究，特別是針對未標記對象，設計一種高效的標注策略。

4.1 概率矩陣定義

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

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

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

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

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

因為W表征Web對象間的相似度，表示W(wǎng)eb對象親和子圖G中頂點i和 j的權重邊緣和。

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

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

（4）PL(i,j)是從標簽到Web對象的轉換概率矩陣，等于PL(i,j)的轉置。

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

4.2 隨機跳躍變遷策略

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

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

相關性評分計算過程如下：對于給定的未標記測試Web對象oi，其穩(wěn)態(tài)概率可計算為：

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

算法2隨機跳躍變遷策略

輸出：等級收斂分配概率

1.for i=1:t do

3. 預計算并存儲Λ=(S-1-αVU)-1；

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

5.end

4.3 時間復雜度分析

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

5 實驗分析

5.1 實驗設置

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

Table1 Experimental testsets表1 實驗測試集

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

為對5種算法進行公正評測，這里基于Rand標準進行評價[12]：

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

5.2 實驗結果

5.2.1 UCI數(shù)據(jù)集實驗

圖2給出5種標簽聚類方法在選取的4組UCI Web測試集上Rand指標學習過程曲線。

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

5.2.2 真實測試集實驗

圖3給出5種標簽聚類方法在選取的4組真實測試集上Rand指標學習過程曲線。

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

6 結束語

Fig.2 Comparison of UCIWeb testsets圖2 UCIWeb測試集對比

Fig.3 Comparison of real testsets圖3 真實測試集對比

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

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.

附中文參考文獻：

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

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

汪忠國（1985—），男，安徽蕪湖人，2010年于中國科學技術大學獲得碩士學位，現(xià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年于東南大學獲得碩士學位，現(xiàn)為中國科學技術大學教授、博士生導師，主要研究領域為教育信息化。

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—），女，湖南衡陽人，2010年于湖南師范大學獲得碩士學位，現(xiàn)為安徽信息工程學院講師，主要研究領域為模糊數(shù)學。

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(安徽省教育廳自然科學研究項目).

Received 2016-05,Accepted 2016-08.

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