一種網(wǎng)頁分類中基于圖的半指導(dǎo)學(xué)習(xí)算法

摘要：提出一種基于圖的半指導(dǎo)學(xué)習(xí)算法用于網(wǎng)頁分類。采用k近鄰算法構(gòu)建一個(gè)帶權(quán)圖，圖中節(jié)點(diǎn)為已標(biāo)志或未標(biāo)志的網(wǎng)頁，連接邊的權(quán)重表示類的傳播概率，將網(wǎng)頁分類問題形式化為圖中類的概率傳播。為有效利用圖中未標(biāo)志節(jié)點(diǎn)輔助分類，結(jié)合網(wǎng)頁的內(nèi)容信息和鏈接信息計(jì)算網(wǎng)頁間的鏈接權(quán)重，通過已標(biāo)志節(jié)點(diǎn)，類別信息以一定概率從已標(biāo)志節(jié)點(diǎn)推向未標(biāo)志節(jié)點(diǎn)。實(shí)驗(yàn)表明，本文提出的算法能有效改進(jìn)網(wǎng)頁分類結(jié)果。

關(guān)鍵詞：圖模型；半指導(dǎo)學(xué)習(xí)；網(wǎng)頁分類；鏈接信息

中圖分類號(hào)：TP301．6文獻(xiàn)標(biāo)志碼：A

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

0引言

網(wǎng)頁分類作為一種傳統(tǒng)的機(jī)器學(xué)習(xí)任務(wù)，通常采用有指導(dǎo)學(xué)習(xí)，通過對(duì)一系列訓(xùn)練樣本的分析來預(yù)測未知網(wǎng)頁的類別歸屬。實(shí)際應(yīng)用中，未分類的網(wǎng)頁隨處可得，已分類的網(wǎng)頁卻很少。因?yàn)閷?duì)網(wǎng)頁分類需要借助領(lǐng)域?qū)＜业慕?jīng)驗(yàn)，并且要花費(fèi)大量的人力、物力，代價(jià)昂貴。為了解決這一矛盾，人們嘗試用半指導(dǎo)學(xué)習(xí)的方法進(jìn)行分類。半指導(dǎo)學(xué)習(xí)就是利用少量已標(biāo)志的數(shù)據(jù)和大量未標(biāo)志數(shù)據(jù)構(gòu)造分類器，對(duì)未標(biāo)志數(shù)據(jù)進(jìn)行分類。由于半指導(dǎo)學(xué)習(xí)只需要少量的標(biāo)志數(shù)據(jù)，并且能獲得較高的分類精度，近年來受到廣泛關(guān)注。

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

網(wǎng)頁分類中，由于同類型的網(wǎng)頁存在較強(qiáng)的共現(xiàn)模式與依賴性，圖模型可以較好地體現(xiàn)這種關(guān)系。本文提出了一種基于圖的半指導(dǎo)學(xué)習(xí)算法用于網(wǎng)頁分類。為了達(dá)到較高的分類精度，針對(duì)網(wǎng)頁特點(diǎn)，構(gòu)建一個(gè)kNN圖，結(jié)合網(wǎng)頁的內(nèi)容特征和鏈接特征計(jì)算網(wǎng)頁間的相似度，決定其向鄰居節(jié)點(diǎn)傳播的概率。實(shí)驗(yàn)結(jié)果表明采用本文所介紹的學(xué)習(xí)算法能有效利用未標(biāo)志數(shù)據(jù)獲得較高的分類精度。

1圖的構(gòu)造方法

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

實(shí)際應(yīng)用中，根據(jù)相關(guān)領(lǐng)域知識(shí)構(gòu)建圖對(duì)于獲得較高的分類精度具有重要意義。本文采用k近鄰的方法構(gòu)建圖，圖中每個(gè)節(jié)點(diǎn)代表一個(gè)網(wǎng)頁，連接邊的權(quán)值為兩個(gè)網(wǎng)頁間的相似程度。通過多次實(shí)驗(yàn)分析，發(fā)現(xiàn)，在k近鄰圖中取較小k值效果更好。原因在于一方面k值較小計(jì)算更快；另一方面，由于是稀疏圖，大部分網(wǎng)頁節(jié)點(diǎn)間的噪聲鏈接也被去掉了，能獲得較好的效果。

2網(wǎng)頁分類中連接邊的權(quán)重計(jì)算

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

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

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

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

為了更好地捕捉到復(fù)雜鏈接對(duì)象間的相關(guān)關(guān)系，本文從互信息、鏈接距離和鏈接特征三個(gè)方面來衡量鏈接相關(guān)函數(shù)。

假設(shè)Ni代表一個(gè)網(wǎng)頁，pNi是那些鏈接指向Ni的網(wǎng)頁（鏈入網(wǎng)頁）。相應(yīng)地，CNi是那些Ni所指向的網(wǎng)頁（鏈出網(wǎng)頁）。兩個(gè)網(wǎng)頁Ni和Nj的鏈接特征可由式（2）計(jì)算：

3圖模型中類的傳播算法

網(wǎng)頁分類中，構(gòu)建的帶權(quán)圖為G= (N， E)。其中：N為頂點(diǎn)的集合；E表示邊的集合。假設(shè)圖中共有n個(gè)頂點(diǎn)，其中l(wèi)個(gè)節(jié)點(diǎn)已作標(biāo)志，未標(biāo)志的節(jié)點(diǎn)數(shù)為u（u=n-l，一般 l<

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

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

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

a)節(jié)點(diǎn)類別以一定概率向鄰居節(jié)點(diǎn)傳播D= P×D；

b)已標(biāo)志節(jié)點(diǎn)所屬類別概率保持不變；

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

4實(shí)驗(yàn)及結(jié)果分析

為了衡量上述分類算法的效果，本文在數(shù)據(jù)集WebKB上進(jìn)行網(wǎng)頁分類實(shí)驗(yàn)。WebKB數(shù)據(jù)集包含4 000多個(gè)網(wǎng)頁，網(wǎng)頁間的鏈接數(shù)超過11 000個(gè)。這些網(wǎng)頁分別屬于學(xué)生、教員、職員、系、工程、課程等七個(gè)不同的類別。

在本文的實(shí)驗(yàn)中，取k=5，構(gòu)造一個(gè)5NN圖， a= 0.03，b= 0.3，β= 0.2。先采用兩種不同的權(quán)重計(jì)算方法在WebKB數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)：一種采用基于內(nèi)容的方法，按式（1）計(jì)算連接邊的權(quán)值；另一種結(jié)合網(wǎng)頁的內(nèi)容和鏈接信息按式（4）計(jì)算連接邊的權(quán)值。分別在數(shù)量不同的標(biāo)志數(shù)據(jù)集（訓(xùn)練集）上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)中，在數(shù)據(jù)集中隨機(jī)選擇網(wǎng)頁進(jìn)行標(biāo)志，其余的作為未標(biāo)志網(wǎng)頁。對(duì)每種隨機(jī)選取的標(biāo)志數(shù)據(jù)集分別計(jì)算六輪，然后取平均。兩種不同的權(quán)重計(jì)算方法進(jìn)行半指導(dǎo)學(xué)習(xí)的結(jié)果如圖2所示。

從圖2中實(shí)驗(yàn)數(shù)據(jù)可以得出兩個(gè)結(jié)論：

a)結(jié)合鏈接信息的權(quán)重學(xué)習(xí)方法明顯地比單純基于內(nèi)容的學(xué)習(xí)方法取得較高的分類精度。雖然結(jié)合鏈接信息的權(quán)重學(xué)習(xí)方法計(jì)算代價(jià)更大，但合理運(yùn)用鏈接信息確實(shí)可以提高分類精度。

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

網(wǎng)頁分類作為一種典型的應(yīng)用在機(jī)器學(xué)習(xí)領(lǐng)域中被廣泛研究。本文再與兩種典型的半指導(dǎo)學(xué)習(xí)方法transductive SVM[5]和harmonic Gaussian method[7]進(jìn)行比較。圖3顯示了三種分類模型作用在WebKB數(shù)據(jù)集上的結(jié)果。

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

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

b）網(wǎng)頁的鏈接信息為網(wǎng)頁分類提供了有用的信息。

5結(jié)束語

本文提出了一種用于基于圖模型的半指導(dǎo)學(xué)習(xí)算法，并應(yīng)用在網(wǎng)頁分類中。在WebKB數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文討論的模型和提出的算法能有效地利用未標(biāo)志網(wǎng)頁及網(wǎng)頁間的鏈接信息改進(jìn)網(wǎng)頁分類效果。除了用于網(wǎng)頁分類外，基于圖模型的半指導(dǎo)學(xué)習(xí)方法還能用于Web搜索等其他Web相關(guān)應(yīng)用。筆者下一步的工作將繼續(xù)研究如何有效地對(duì)鏈接信息去噪，如何進(jìn)一步優(yōu)化半指導(dǎo)學(xué)習(xí)的計(jì)算方法，以探索圖模型更廣泛的應(yīng)用。

參考文獻(xiàn)：

［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.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”