一種網頁分類中基于圖的半指導學習算法

摘要：提出一種基于圖的半指導學習算法用于網頁分類。采用k近鄰算法構建一個帶權圖，圖中節點為已標志或未標志的網頁，連接邊的權重表示類的傳播概率，將網頁分類問題形式化為圖中類的概率傳播。為有效利用圖中未標志節點輔助分類，結合網頁的內容信息和鏈接信息計算網頁間的鏈接權重，通過已標志節點，類別信息以一定概率從已標志節點推向未標志節點。實驗表明，本文提出的算法能有效改進網頁分類結果。

關鍵詞：圖模型；半指導學習；網頁分類；鏈接信息

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001－3695(2008)03－0735－03

0引言

網頁分類作為一種傳統的機器學習任務，通常采用有指導學習，通過對一系列訓練樣本的分析來預測未知網頁的類別歸屬。實際應用中，未分類的網頁隨處可得，已分類的網頁卻很少。因為對網頁分類需要借助領域專家的經驗，并且要花費大量的人力、物力，代價昂貴。為了解決這一矛盾，人們嘗試用半指導學習的方法進行分類。半指導學習就是利用少量已標志的數據和大量未標志數據構造分類器，對未標志數據進行分類。由于半指導學習只需要少量的標志數據，并且能獲得較高的分類精度，近年來受到廣泛關注。

典型的半指導分類方法有生成混合數據模型、selftraining、cotraining、基于最大間隔和基于圖的方法。文獻[1]中，大量未標志數據和少量已標志數據構成混合數據模型，假定每個數據所屬類別服從高斯分布，半指導學習運用EM算法對數據所屬類別進行估計。文獻[2]首先利用訓練集中的數據訓練一個分類器，對未分類的數據進行標志；然后選擇那些最確定分類類別的數據加入到訓練集中，重復訓練過程(selftraining)。從訓練方法上可以看出，如果訓練過程中出現誤分類，分類錯誤會自我增強，導致最終分類失敗。Blum等人[3]提出的協同訓練（cotraining）方法假設對象的特性可被分解為兩個條件獨立的子特征，首先利用兩個子特征在訓練集上分別訓練出兩個分類器；然后用訓練好的兩個分類器分別為未標志的數據分類，并將新標志的數據作為新的訓練數據增加到對方訓練集中，以便重新對分類器進行訓練。Cotraining減少了selftraining中錯誤會不斷被加強的危險，但cotraining需要足夠且冗余的特征以分別訓練兩套分類器的要求相當苛刻。Zhou zhihua等人[4]提出了tritraining方法，使用了第三個分類器。如果前兩個分類器對未標志數據的分類結果一致，那么這個分類結果用于訓練第三個分類器，以在數據集不具備多個子特征的情況下降低協同訓練的條件要求。文獻[5]介紹了基于最大間隔的半指導學習方法，假定決策邊界在低密度區，并利用未標志數據確定這些區域以達到分類效果。文獻[6]在實例集上構造一個圖，利用高斯隨機域和諧函數方法學習圖中未標志節點的類別。

網頁分類中，由于同類型的網頁存在較強的共現模式與依賴性，圖模型可以較好地體現這種關系。本文提出了一種基于圖的半指導學習算法用于網頁分類。為了達到較高的分類精度，針對網頁特點，構建一個kNN圖，結合網頁的內容特征和鏈接特征計算網頁間的相似度，決定其向鄰居節點傳播的概率。實驗結果表明采用本文所介紹的學習算法能有效利用未標志數據獲得較高的分類精度。

1圖的構造方法

在圖模型中，圖中的節點為已標志的和未標志的數據，邊的權重體現對應兩個連接節點的關聯程度，通常可以用相似度或距離來衡量，如圖1所示。常用的創建圖的方法有全連接圖、稀疏圖、kNN圖、NN圖等。全連接圖中任意兩個節點間都有一條權重邊相連，兩個節點越相似，連接邊的權重越大。全連接圖可采用統一的權重計算方法計算連接邊的權重，但計算量較大。稀疏圖中節點間的連接邊較少，相應的計算量較小，有時可以獲得很好的性能，但如何選取連接邊以及連接邊的權重計算都需要在大量先驗知識的前提下精心設計。kNN圖中任意兩個節點i和j之間是否有一條連接邊取決于i是否為j的k近鄰或j是否為i的k近鄰。其中k為可調參數，用于控制圖中邊的密度。∈NN圖中連接邊的存在與否由節點間的距離決定。對任意兩節點i和j，只有滿足d(i， j)≤∈，i，j間才有連接邊。因此，參數∈用于控制節點的鄰居半徑。無論采用哪種方法構造圖，圖模型中只有少數節點是已標志的，大部分節點都是未標志的，但節點所屬的類可以通過連接邊向它的鄰居節點傳播，就像已標志節點將類別信息推向未標志節點。因此，基于圖的半指導學習方法可以充分利用未標志節點達到分類效果。

實際應用中，根據相關領域知識構建圖對于獲得較高的分類精度具有重要意義。本文采用k近鄰的方法構建圖，圖中每個節點代表一個網頁，連接邊的權值為兩個網頁間的相似程度。通過多次實驗分析，發現，在k近鄰圖中取較小k值效果更好。原因在于一方面k值較小計算更快；另一方面，由于是稀疏圖，大部分網頁節點間的噪聲鏈接也被去掉了，能獲得較好的效果。

2網頁分類中連接邊的權重計算

網頁分類中，網頁用帶權特征向量N= (tk，tw)表示。其中：tk = [t1，t2，…，tn]，ti表示網頁中按權重由大到小排列的第i個詞語；tw= [tw1，tw2，…，twn]，twi為ti的權重值。網頁特征詞權重的計算方法如下：首先對HTML的不同標簽分為六類，用m表示，每類賦予固定的位置權重Wm。標簽類及對應的權重值分別為：標題（W1= 0.9），一級標題和鏈接錨文字（W2= 0.8），二級標題（W3= 0.6），三級標題（W4= 0.4），正文體中加重字、黑體字、斜體字（W5= 0.2），正文體其他內容（W6= 0.1）。先通過公式wi=6m=1Nm×wm計算頁面特征向量中每個關鍵詞ti對應的權重。其中：Nm表示關鍵詞在標簽類不同部分出現的次數；wm為對應標簽類的權重。網頁中所有關鍵詞的權重計算出來后再進行歸一化處理。針對一些連接詞，如“and”“is”“the”等在很多網頁中會頻繁出現的情況，建立一個通用詞列表，將這些不能代表網頁特征的詞排除在外。衡量網頁內容是否相似有多種方法，本文采用cosin距離計算兩個網頁的相似度。網頁Ni和Nj間基于內容的相似度計算如下：

Wij=exp-1/a(1-cos(Ni，Nj))； a是常數(1)

網頁中既包含文本信息，又包含大量的鏈接信息。文本信息是網頁所展示的內容，內容相近的網頁往往屬于同一類別，而網頁中的鏈接信息又可反映鏈接網頁間的相關關系。因此，網頁間的相似度衡量包含文本信息和鏈接信息兩個方面。

網頁中的鏈接信息并不都是有用或有效的，如網頁中通常包含很多噪聲鏈接，像廣告、導航條等。有效減少噪聲鏈接的干擾對提高網頁分類精度非常重要。本文采用主題詞表法對噪聲信息進行過濾，只要給定主題詞或術語的頻率低于一定值，就可以判定該節點為噪聲節點。去噪之后，就可以結合鏈接信息來計算網頁間的相關函數。

為了更好地捕捉到復雜鏈接對象間的相關關系，本文從互信息、鏈接距離和鏈接特征三個方面來衡量鏈接相關函數。

假設Ni代表一個網頁，pNi是那些鏈接指向Ni的網頁（鏈入網頁）。相應地，CNi是那些Ni所指向的網頁（鏈出網頁）。兩個網頁Ni和Nj的鏈接特征可由式（2）計算：

3圖模型中類的傳播算法

網頁分類中，構建的帶權圖為G= (N， E)。其中：N為頂點的集合；E表示邊的集合。假設圖中共有n個頂點，其中l個節點已作標志，未標志的節點數為u（u=n-l，一般 l<

Pij=Wij/nk=1Wik (5)

圖中的n個節點分屬于c個不同的類別，可以定義一個n×c的矩陣D， 表示節點所屬類別的概率。由于圖中有l個節點是已標志的，其余u個節點均為未標志，可以將矩陣D分解為Dl和Du兩部分，其中:Dl是已知的；Du是未知的。算法的目的就是求出Du的值以判別未標志節點所屬的類別。

圖中類的概率傳播算法可描述如下：

a)節點類別以一定概率向鄰居節點傳播D= P×D；

b)已標志節點所屬類別概率保持不變；

c)重復步驟a）b)，直到矩陣D收斂。

4實驗及結果分析

為了衡量上述分類算法的效果，本文在數據集WebKB上進行網頁分類實驗。WebKB數據集包含4 000多個網頁，網頁間的鏈接數超過11 000個。這些網頁分別屬于學生、教員、職員、系、工程、課程等七個不同的類別。

在本文的實驗中，取k=5，構造一個5NN圖， a= 0.03，b= 0.3，β= 0.2。先采用兩種不同的權重計算方法在WebKB數據集上進行對比實驗：一種采用基于內容的方法，按式（1）計算連接邊的權值；另一種結合網頁的內容和鏈接信息按式（4）計算連接邊的權值。分別在數量不同的標志數據集（訓練集）上進行實驗。實驗中，在數據集中隨機選擇網頁進行標志，其余的作為未標志網頁。對每種隨機選取的標志數據集分別計算六輪，然后取平均。兩種不同的權重計算方法進行半指導學習的結果如圖2所示。

從圖2中實驗數據可以得出兩個結論：

a)結合鏈接信息的權重學習方法明顯地比單純基于內容的學習方法取得較高的分類精度。雖然結合鏈接信息的權重學習方法計算代價更大，但合理運用鏈接信息確實可以提高分類精度。

b)隨著已標志數據數量的不斷增加，分類精度的提高效果逐漸趨緩。

網頁分類作為一種典型的應用在機器學習領域中被廣泛研究。本文再與兩種典型的半指導學習方法transductive SVM[5]和harmonic Gaussian method[7]進行比較。圖3顯示了三種分類模型作用在WebKB數據集上的結果。

從圖3可以看出，本文提出的半指導學習算法比TSVM和harmonic Gaussian method分類取得了更好的效果，主要原因在于：

a）主題相同的網頁傾向于相互引用，圖模型較好地體現了這個特點。比如網頁1引用3的部分內容，3又引用2的部分內容，如此等等。這樣，即使兩個網頁相距很遠（共同詞很少），在本文的圖模型中仍然可以通過其他網頁間接相連，相關的類信息也可以通過這些連接邊以一定概率傳播。

b）網頁的鏈接信息為網頁分類提供了有用的信息。

5結束語

本文提出了一種用于基于圖模型的半指導學習算法，并應用在網頁分類中。在WebKB數據集上的實驗表明，本文討論的模型和提出的算法能有效地利用未標志網頁及網頁間的鏈接信息改進網頁分類效果。除了用于網頁分類外，基于圖模型的半指導學習方法還能用于Web搜索等其他Web相關應用。筆者下一步的工作將繼續研究如何有效地對鏈接信息去噪，如何進一步優化半指導學習的計算方法，以探索圖模型更廣泛的應用。

參考文獻：

［1］SHAHSHAHANI B，LANDGREBE D.The effect of unlabeled samples in reducing the small sample size problem and mitigating the hughes phenomenon [J].IEEE Trans on Geoscience and Remote Sensing，1994，32(5):10871095.

[2]YAROWSKY D.Unsupervised word sense disambiguation rivaling supervised methods[C]//Proc of the 33rd Annual Meeting of the Association for Computational Linguistics.1995:189196.

[3]BLUM A，MITCHELL T.Combining labeled and unlabeled data with cotraining [C]//Proc of the 11th Annual Conference on Computational Learning Theory.Madison:ACM Press，1998:92100.

[4]ZHOU Zhihua，LI Ming.Tritraining: exploiting unlabeled data using three classifiers [J].IEEE Trans Knowledge and Data Engineering，2005，17（11）:15291541.

[5]JOACHIMS T.Transductive inference for text classification using support vector machines [C]//Proc of the 16th International Conf on Machine Learning. San Francisco:Morgan Kaufmann，1999:200－209.

[6]ZHU X J.Semisupervised learning with graphs [D].[S.l.]:Carnegie Mellon University， 2005.

[7]HUANG T M，KECMAN V.Semisupervised learning from unbalanced labeled data:an improvement [C]//Knowledge Based and Emergent Technologies Relied Intelligent Information and Engineering Systems， Lecture Notes on Computer Science 3215.Heidelberg:SpringerVerlag， 2004:765771.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”