基于鏈接的Ｗｅｂ網頁分類
2008-12-31 00:00:00郭景峰張健鄒曉紅
計算機應用研究 2008年11期
(燕山大學 信息科學與工程學院， 河北 秦皇島 066004)
摘要：基于鏈接的特點，提出了獲取鏈接信息的模型，將得到的鏈接信息結合對象本身的屬性來共同訓練分類規則。針對網頁鏈接的特殊性，對鏈接有向圖重新建模。實驗證明鏈接信息的加入可以有效地改善分類的結果，鏈接有向圖的重新建模同樣提高了分類的準確性。
關鍵詞：鏈接挖掘； 基于鏈接的分類； 邏輯回歸模型
中圖分類號：TP311文獻標志碼：A
文章編號：1001-3695(2008)11-3271-04
Web page classification based on link
GUO Jing-feng， ZHANG Jian， ZOU Xiao-hong
(College of Information Science Engineering， Yanshan University， Qinhuangdao Hebei 066004， China)
Abstract:Based the properties of link， this paper proposeda model to gain the link information. Then combined link information with the object attributes in order to train the rule of classification. Because of the particularity of Web pages， remo-deled the graph which formed according to the link structure. The experiments show that using of the link information can improve the result of classification， and after the remodel of the graph， the result of classification is improved too.
Key words：link mining; link-based classification; logistic regression model
0引言
傳統的數據挖掘任務(如關聯規則挖掘、購物籃分析)習慣將數據集中的數據看做是單關系且相互獨立的事件。挖掘豐富的、具有結構特點的異種數據集是數據挖掘的重要挑戰，這些數據集的典型特點是多關系的。關系數據集用關系數據庫來描述。在這些領域里，數據對象間總是以某種方式鏈接著，有的鏈接如URL是直接鏈接的，還有的如數據庫中表之間的連接操作一樣，是結構化的。
視事件為獨立的傳統統計推論程序，會導致不合適的結論[1]，潛在的相關關系必須要考慮到。事實上，鏈接關系也是需要挖掘的內容，同時鏈接信息可以改善學習模型的精度：鏈接著的對象，它們的屬性也總是相關的(當兩個對象具有某些相同屬性時，它們之間更可能存在著鏈接)。
鏈接挖掘是新出現的研究領域，正處在多個學科的交叉點：鏈接分析[2]、超文本和Web挖掘[3]、關系學習和歸納邏輯程序設計[4]、圖挖掘[5]。鏈接挖掘隸屬于多關系數據挖掘的范疇，研究的重點是鏈接。
對鏈接的描述性和預測性建模是鏈接挖掘的主要任務?；阪溄拥姆诸惡途垲惗技毙栊滤惴ǖ闹С?。隨著鏈接問題的深入，新的研究任務也出現了，如預測鏈接的強度、預測鏈接的存在、聯合引用的發現和子圖模式的挖掘等。
本文介紹了基于鏈接分類的相關工作及獲取鏈接信息的方法、分類模型和分類訓練數據的使用。針對網頁的鏈接，對有向圖進行了重新建模。
1相關工作
鏈接是對象間存在的某種關系，如網頁間的超鏈接、著作間的引用?；阪溄拥姆诸愂擎溄油诰虻囊粋€極其重要的研究方向。Web挖掘和超文本挖掘是基于鏈接的分類的最主要的應用領域。Web page的分類是此次研究的內容。
基于鏈接的分類在分類時依據兩方面的內容，即對象自身的屬性和相鄰對象的屬性。例如，基于鏈接的分類應用到網頁分類時，要考慮的不僅僅是網頁本身的內容，其相鄰網頁的類標記也是依據。
基于鏈接的分類的三個基本原理是：
a)鏈接特征的解釋。對相鄰對象的特征進行描述，并利用其幫助預測待分類對象的類。
b)集體分類。對于鏈接對象集合，由于對象間相關聯，在分類時需要考慮相鄰對象的類，即對象的分類過程不能看做是獨立的，要力求在整體上得到分類的最佳結果。
c)無類標記數據的使用。無類標號數據的使用對基于鏈接的分類來說非常重要。而且集體分類也支持有類標記和無類標記數據的聯合使用。
明確了這三點要素，提出一種統計模型來獲取鏈接信息并對其性質進行深入的研究。這種統計模型是對經典統計模型的擴展，更加復雜且具有極強的結構性質。
研究過程中，發現無法直接對鏈接本身建立模型，因此轉而對鏈接的分布建立模型。對象周圍的鏈接反映了它與相鄰對象的關系，鏈接的分布情況能夠反映出鏈接的相互關系。掌握了鏈接的分布，筆者提出了基于鏈接分類的算法。為了獲取鏈接的聯合分布，使用logistic回歸模型，同時應用在內容和鏈接上。
確定了學習模型，下一步要做的是如何使用模型分類。不同于傳統的統計模型，基于鏈接的模型詳細說明了鏈接分布和內容屬性。直觀地講，對于鏈接的對象，當一個類更新時，會影響到與它有鏈接關系的相鄰對象的類標號，由此產生的分類算法也變得更加復雜。針對超文本分類[6，7]和關系學習[8~11]已經提出了反復迭代算法和推論算法，這里也使用反復迭代算法。不同的是，以往試圖假設鄰接對象類標號對分類的影響(如鏈接著的對象很可能屬于同一個類)，現在傾向于研究鏈接分布是怎樣影響分類結果的。
2獲取鏈接的模型
21定義
通常認為基于鏈接的對象集合本質上是一個有向圖。
定義鏈接的對象集合轉換成有向圖時，節點表示對象，邊表示對象間的鏈接。
O表示對象集合，O={X1，…，XN}，Xi是一個對象或圖中的一個節點，O是圖中節點的集合；
L表示對象間鏈接的集合，Li→j表示對象Xi與Xj間的一條鏈接，L是圖中邊的集合；g(O，L)是定義在O和L上的有向圖。
對對象的分類是建立在對象特征和鏈接性質上的。對象的類標號是一個有限集合{c1，…，ck}，c(X)表示類c的一個對象X。
鏈接可定義為如下幾種：
a)In(Xi)。對象Xi的入度集合即指向Xi的鏈接，{Xj｜Lj→i∈L}。
b)Out(Xi)。對象Xi的出度集合即Xi指向其他對象的鏈接，{Xj｜Li→j∈L}。
c)Co-In(Xi)。對象Xi的聯合引用集合，{Xj｜Xj≠Xi ，第三個對象Xk具有指向Xi和Xj的鏈接}。也可以這樣理解Co-In links，即Xi和Xj都存在來自于Xk的in-links(入度)。
d)Co-Out(Xi)。對象Xi的聯合引用集合，{Xj｜Xj≠Xi，Xi和Xj具有指向第三個對象Xk的鏈接}。也可以這樣理解Co-Out links，即Xi和Xj都存在指向Xk的out-links(出度)。
22對象特征
對象的屬性提供了對象最基本的描述。傳統的分類算法是以對象屬性為基礎的，基于鏈接的方法也不例外。此外，如果鏈接本身具有特性，也會被使用。在本文中，用符號OA(X)表示對象X的屬性。舉例說明，在網頁中對象的特征由標題、概要、作者身份和內容多種信息組成。
23鏈接特征
為了捕獲鏈接模式，本文引入鏈接特征的概念作為捕獲那些明顯的鏈接特征的方法。為此筆者嘗試了多種簡單的機制，都是以統計計算為基礎的。當描述有限數據集時，統計計算比存儲關聯矩陣要簡潔得多。另外，當有新對象進入時，這些模型可以自適應，所以可應用的范圍更廣泛。
筆者考察了多種創建鏈接特征的方法，都是在已確定類標號的鏈接對象集上創建的。本文用LD(X)表示對鏈接的描述。三種模型定義如下：
a)Mode-link是最簡單的統計計算模型，只計算單一的特征：in-links、out-links、co-links(co-in links、co-out links)。
b)Count-link利用了鏈接對象所屬類的發生次數。在此模式中，由于將對象看做是彼此相關的，丟失了對象作為個體的信息，但記錄了不同類的發生次數。
c)Binary-link介于mode-link和count-link之間，是一種簡單的二元特征矢量。對于任意的類，如果至少存在一條與此類中對象的鏈接，則返回的特征值為1；如果不存在任何一條鏈接，則其值為0。
圖1為用這三種模型計算某一對象與各個類的鏈接結果(in-links、out-links、co-in links、co-out links)。
3分類模型
筆者試用了不同的分類模型，如樸素貝葉斯模型、SVMs、logistic回歸模型。經考察，logistic回歸模型的表現最優，所以集中研究logistic回歸模型。作為預測模型，使用一種logistic規則回歸模型。給定有類標記的訓練數據集(xi，ci)（i=1，2，…，n；ci∈{-1，+1}），計算條件概率P(c｜w，x)，找到使模型達到最佳判別力的參數w，結果等同于由下面的logistic規則回歸公式求得結果[12]：
w＾=arginfw 1/n ∑ni=1 ln(1+exp(-wTxici))+λw2P(w)=exp(λw2)
最簡單的模型是平面模型，即在對象屬性和鏈接特征上使用logistic單回歸模型。但這種模型的表現不佳，經比較發現logistic的結構模型最佳，即在對象屬性和鏈接特征上分開使用logistic回歸模型(規則參數不同)，結果大大優于平面模型。此時MAP對分類的估計變為
C＾（X）=argmaxc∈C(P(c｜OA(X))∏t∈{in，out，co-in，co-out}P(c｜LDt(X))/P(c))
對于不同類型的鏈接t，OA(X)是對象特征，LDt(X)是鏈接特征，假設它們是獨立的。P(c｜OA(X))和P(c｜LDt(X))定義如下：
P(c｜OA(X))=1/(exp(-wT0OA(X)c)+1)
P(c｜LDt(X))=1/(exp(-wT1LDt(X)c)+1)
其中：w0和w1分別是P(c｜OA(X))和P(c｜LDt(X))的logistic規則回歸模型參數。
4有類標記和無類標記數據的使用
數據集D由具有類標記的數據Dl和無類標記的數據Du組成，定義Du的后驗概率為
P(c(X):X∈Du｜D)=∏X∈DuP(c(X)｜OA(X)，LDin(X)，LDout(X)，LDco-in(X)，LDco-out(X))
筆者應用EM-like反復迭代算法，使用有類標記的數據Dl={(xi，c(xi)):i=1，…，n}和無類標記的數據Du={(x*j，c(x*j)):j=1，…，m}學習模型。
首先，對有類標記的數據Dl創建logistic的結構回歸模型，訓練分類器。
然后，用得到的分類器對無類標記的數據Du分類：
c(x*j)=argmaxc∈C(P(c｜OA(x*j))∏tP(c｜LDt(x*j))/P(c))；j=1，…，m
最后，利用剛才被分好類的無類標記數據聯合原來有類標記的數據重新訓練新的分類器。
a)初始化，僅使用有類標記的數據集，依據內容和鏈接特征創建logistic結構模型，訓練分類器。
b)反復迭代，當隨著無類標記數據的增加，其后驗概率不再增加時，結束反復迭代過程。
(a)將a)訓練好的分類器用在無類標記的數據上，對其進行分類。
(b)重新計算每個對象的鏈接特征，重新估計logistic回歸模型的參數。
在上面的算法中，由于原來有類標記的數據和無類標記的數據間存在著鏈接，當對無類標記的數據分類后，整個數據集的鏈接描述變化了。在b)中需要重新計算每個對象的鏈接特征，并重新估計logistic回歸模型的參數。
5鏈接有向圖的重新建模
對于網頁分類來說，鏈接挖掘技術大大提高了分類的準確率。相比其他的領域，網頁間的鏈接關系更加復雜多樣。鏈接挖掘最關鍵的內容是對鏈接信息的提取，這一步決定了其后分類的結果。鏈接信息提取的正確，能夠提高分類的準確性和精度。
鏈接形成的有向圖是提取鏈接信息的基礎。但網頁間的鏈接數量極大，由此形成的有向圖，邊的數量也是海量的。同時網頁間也存在著許多無意義和無目的鏈接，這些鏈接信息對于分類來說并無益處。如果在提取鏈接分布之前對有向圖進行預處理，刪去圖中無用的鏈接(邊)會大大提高執行效率，同時也避免錯誤鏈接信息對分類結果的誤導。
a)鏈接有向圖簡化思想其實就是一個去粗取精的過程。首先需要為邊設定一個度量標準，這里引入邊的權。權的值作為衡量一條邊重要與否的標準，接下來的工作就是如何定義權的具體含義，同樣也是簡化思想的關鍵所在。
b)網頁間，鏈接存在隨機性，許多鏈接著的對象之間并沒有聯系。例如，一個用戶從他的網站鏈接瀏覽了多個網頁，但并無目的性，有的網頁以后都不會再次瀏覽了。而具有目的性的鏈接往往會重復多次。當一個網頁擁有另一個網頁感興趣的內容時，它們之間的鏈接總是重復發生的。
c)由于Google和PR(PageRank)的影響，高質量、高PR的網頁在某種程度上處于對自身PR值的保護，不輕易鏈接其他網頁。
基于上述的特點不難發現，鏈接重復的次數是反映鏈接重要性的一個指標。鏈接著的對象的重要程度也衡量著鏈接本身的重要性。當兩個重要網頁間的鏈接發生時，就算頻率不高，也不能認為其不重要。所以衡量標準應該是兩方面的，即鏈接的頻率和鏈接本身的度(度在此指重要性)。如果找到了這兩方面合適的表示方法，那么權的定義標準也就找到了。
鏈接的頻率選擇在有限時間段內鏈接重復的次數。為了使得到的結果更具有普遍意義，會選取多個時間段，時間間隔盡量不要太短；然后取多次結果的平均值。
鏈接的度選擇網頁的PR值作為標準，每條鏈接的度為其鏈接著的兩端節點(網頁)的PR平均值。
選取PR值作為標準的原因如下：
a)PageRank算法[13]本身就是鏈接挖掘的一個最著名的例子。其核心思想是，一個網頁的鏈入數量越多，網頁的PR值越高，鏈出數量越少，PR越高。所以PR算法本身就是以鏈接為基礎的。
b)鏈接的方向本身決定著其鏈接著的兩個網頁的PR值的變化。例如，當網頁A是網頁B的鏈入網頁，那么更希望B也能夠成為A的鏈入網頁。因為PR反饋更有利于提高網頁A的PR，當鏈接的方向發生變化，影響到的是兩網頁的PR值，所以鏈接的度取這兩個網頁PR平均值更合理。
確定了這兩方面的含義，定義：
權=鏈接頻率×鏈接度(類似于重量=密度×體積)
對于鏈接有向圖來說，無意義和無目的的邊是低頻率的，而且無意義和無目的的邊總是來自于不重要的網頁之間。所以，根據權的定義，這樣的邊的權值相對于其他邊，值是非常小的。只需要把所有邊的權值計算出來，排序后刪除掉那些權值相對而言極小的邊就可以了。鏈接頻率保護了普通網頁間的重要鏈接，鏈接度則保護了重要網頁間的鏈接。
6實驗結果
實驗數據來自Cora數據集[14]和WebKB數據集[15]，評估了基于鏈接的分類算法和有向圖重新建模后對分類結果的影響。數據集CoraⅠ、WebKBⅠ、WebKBⅡ來自于Cora和WebKB。
被正確分類的網頁用TP(true positive)表示，錯誤地用FP(1 positive)、TN(true negative)、FN(1 negative)表示。Accuracy指正確度，是被正確標記的網頁所占的百分比，即(TP+TN)/(TP+TN+FP+FN)。Precision指精度，被標記為同一個類的網頁中，標記正確的所占的百分比，TP/(TP+FP)。Recall指理想現實比，在本應該被標記為同一個類的網頁中，確實被標記為此類的所占的百分比，TP/(TP+FN)。
表1~3顯示了content、mode、binary和count模型在CoraⅠ、WebKBⅠ、WebKBⅡ的結果。
結果表明，對于這三個數據集，基于鏈接的模型優于僅內容的模型。Count模型整體表現最好，同時mode和count的表現優于binary。
對于鏈接有向圖的重新建模，本文選擇三種權定義的模式，PR(PageRank)、Fre(frequency)、PR-F(PR×Fre)、Nor(無化簡)，模型選擇count。
表4~6，顯示了基于不同加權策略重新建模后與建模前所得到的結果。
結果表明，只考慮鏈接頻率和PR值的策略表現很差，原因在于這兩種策略在作刪除時，往往會刪除重要的信息。三個數據集中，當圖重新建模后，有兩個有明顯提高。經過分析，發現數據集越大，簡化后的分類結果提高越多。而且重新建模后的圖，在提取鏈接信息時耗時明顯減少。
7結束語
現實世界中，許多數據集都具有復雜的結構，鏈接無處不在。基于鏈接的分類核心在于對鏈接信息的提取和使用，以及如何利用得到的鏈接信息改善分類的結果。
由于網頁間鏈接的獨特性，筆者找到了有針對性的改善分類結果的方法(對有向圖的重新建模)，但如何將這種方法普及，則需要做更多的努力。鏈接挖掘具有極其深遠的研究價值，是機遇亦是挑戰。
參考文獻：
［1］JENSEN D. Statistical challenges to inductive inference in linked data[C]//Proc of the 7th International Workshop on Artificial Intelligence and Statistics. Fort Lauderdale， Florida: [s.n.]，1999.
[2]FELDMAN R. Link analysis:current state of the art[C]//Proc of KDD ’02. Edmonton， Alberta:[s.n.]， 2002:23-26.
[3]CHAKRABARTI S. Mining the Web[M]. [S.l.]: Morgan Kaufman，2002.
[4]DZEROSKI S， LAVRAC N. Relational data mining[M].Berlin:Kluwer， 2001.
[5]COOK D， HOLDER L. Graph-based data mining[J].IEEE Intelligent Systems and Their Applications， 2000，15(2):32-41.
[6]CHAKRABARTI S， DOM B， INDYK P. Enhanced hypertext categorization using hyperlinks[C]//Proc of ACM SIGMOD International Conference on Management of Data. Seattle， Washington:[s.n.]， 1998:307-318.
[7]NIGAM K D. Using unlabeled data to improve text classification[D]. Pittsburgh: Carnegie Mellon University，2001.
[8]JENSEN D， NEVILLE J， GALLAGHER B. Why collective inference improves relational classification[C]//Proc of the 10th ACM SIG-KDD InternationalConfererence on Knowledge Discovery and Data Mining. 2004.
[9]TASKAR B， ABBEEL P， KOLLER D. Discriminative probabilistic models for relational data[C]//Proc of UAI’02. Edmonton:[s.n.]，2002:485-492.
[10]TASKAR B， SEGAL E， KOLLER D. Probabilistic classification and clustering in relational data[C]//Proc ofthe 17th International Joint Conference on Artificial Intelligence. Seattle: Bernhard Nebel，2001:870-878.
[11]NEVILLE J， JENSEN D. Iterative classification in relational data[C]//Proc of AAAI-2000 Workshop on Learning Statistical Models from Relational Data. 2000:13-20.
[12]ZHANG Tong， FRANK J O. Text categorization based on regularized linear classification methods[J].Information Retrieval，2001，4(1):5-31.
[13]PAGE L， BRIN S， MOTWANI R， et al. The page rank citation ran-king:bring order to the Web[R]. Palo Alto， California: Stanford University， 1998.
[14]McCALLUM A， K NIGAM， J RENNIE， et al. Automating the construction of Internet portals with machine learning[J].Information Retrieval， 2000，3(2):127-163.
[15]CRAVEN M， DIPASQUO D， FREITAG D，et al. Learning to extract symbolic knowledge from the world wide Web[C]//Proc ofthe 15th Conference of the American Association for Artificial Intelligence. Madison: AAAI Press， 1998:509-516.
