閔鈺麟，黃永峰

（1.清華大學 電子工程系 信息認知與智能系統(tǒng)研究所，北京100084；2.清華大學 信息科學與技術國家實驗室，北京100084）

0 引 言

互聯(lián)網(wǎng)時代用戶的個性化需求越來越高，在實際應用場景下，不同用戶的需求通常存在差異，他們希望在其特定領域及方向上進行 “定制化”的主題爬行。傳統(tǒng)的聚焦爬蟲在開始工作之前需要對指定主題進行建模和訓練，在缺乏相應主題訓練集的情況下無法完成任務，不能滿足用戶 “個性化”需求。本文設計并實現(xiàn)的定制主題聚焦爬蟲不依賴于主題訓練集，僅在用戶提供少量未知主題的種子url（同一主題）的情況下完成主題爬行，得到針對該主題較高的收獲率 （havest rate）。

1 相關工作分析

聚焦爬蟲通過對url的優(yōu)先級進行計算和排序，優(yōu)先訪問較高概率指向相同主題網(wǎng)頁的url，從而得到較高的收獲率［1］。目前改進聚焦爬蟲的思路主要有4 種：第1 種是基于網(wǎng)頁鏈接分析的方法，在論文［2］中，Hati定義了鏈接距離的計算方法并使用其對鏈接排序，Taylan在其論文中提出了基于樸素貝葉斯分類器的鏈接評分方法［3］。第2種思路是基于網(wǎng)頁文本分析的方法，主要思路是計算網(wǎng)頁文本或錨文本與主題的相關度，并使用相關度作為url排序的基準，例如G.Almpanidis提出了基于內容和鏈接分析的方法［4］，Hong Wei Hao的 研 究［5］表 明，在 主 題 相 似 度 計 算中使用潛在語義索引 （latent semantic indexing）比TFIDF有更好的表現(xiàn)。第3 種為基于本體領域的方法，Yang提出了支持本體的網(wǎng)站模型［6］并將其用于聚焦爬蟲，Punam利用特定領域的本體概念語義擴大搜索話題，模仿人類的認知搜索模式從SBS （social bookmarking site）找到潛在相關的網(wǎng)絡資源［7］。第4 種方法基于用戶日志，Sotiris Batsakis利用隱馬爾科夫模型 （HMM）學習用戶瀏覽行為并預測不同網(wǎng)頁聚類之間的聯(lián)系［8］，Yajun Du提出了基于用戶日志的形式概念分析 （CFA）方法并將其用于網(wǎng)頁語義排名［9］。這些方法從不同角度出發(fā)提高聚焦爬蟲的效率，但是他們一個共同的局限性就是需要事先構造主題訓練集。

以基于網(wǎng)頁內容的方法為例?；诰W(wǎng)頁內容的方法通常使用best－first策略對url進行排序。best－first策略的基本思想是如果一個頁面和主題的相關度越高，則處于該頁面上的鏈接指向的網(wǎng)頁也屬于該主題的概率就越大。bestfirst策略實現(xiàn)方法如下：

（1）構建具有一定規(guī)模的訓練集，該訓練集由網(wǎng)頁文本構成，至少應該有兩類，一類是與主題相關的網(wǎng)頁文本，另一類是與主題不相關的網(wǎng)頁文本。該訓練集用于提取文本特征和主題建模。

（2）使用信息增益、χ2分布等方法提取該主題的特征，并統(tǒng)計特征詞的IDF權重，特征詞的IDF權重可以由總文件數(shù)目除以包含該詞語之文件的數(shù)目，再將得到的商取對數(shù)得到

（3）利用VSM （vector space modle）模型將訓練集中的主題映射到特征空間上，得到文本向量vt，其中n為文本特征維數(shù)，xt，i（i＝1，2，...，n）為TF·IDF特征權重

（4）對于一個新爬取的網(wǎng)頁，同樣使用VSM 模型將解析出的網(wǎng)頁文本映射為向量vw

（5）使用余弦相似度評價網(wǎng)頁文本與主題的相關度

（6）將該頁面上的url加入隊列，并按照url所在頁面與主題的相關度Sim（vw，vt）進行排序，這樣聚焦爬蟲每次從隊列中取出的url均為與主題最相關的頁面中的url。

通過分析可以發(fā)現(xiàn)，基于網(wǎng)頁內容的聚焦爬蟲需要提供該主題的訓練集才能完成對特征提取以及主題向量的計算。實際上，幾乎所有的聚焦爬蟲均需要事先構建一個針對該主題的訓練集，而對于個性化的用戶需求來說，主要面對的問題是用戶的需求千變萬化，爬蟲可能會因為缺乏用戶需求主題的訓練集而無法完成任務。

針對以上問題，本文提出基于聚類算法的自適應主題模型，用于指導聚焦爬蟲在只有少量未知主題的url的情況下完成主題爬行。

2 自適應主題模型

2.1 主題建模

為了使模型能夠準確地描述主題，本文引入文本聚類算法k－means的思想。k－means算法的目的是將一個文本庫中的文本分為k類。對于一個含有n （n＞k）個文本的它首先 隨 機 選 定k 個 文 本 作 為 初 始 類 的 中 心Mi＝1，..，k（xMi，1，xMi，2，...，xMi，m），其中m 為文本特征維數(shù)；對于剩下的每個文 本vt（xt，1，xt，2，...，xt，m），計算它到每個類中心的歐氏距離

并把這個文本加入距離最近的類Mi，然后使用式 （6）更新該類的中心位置，為該類文本數(shù)目

算法不斷重復這一過程，直到滿足某一收斂條件。

基于這一思想，對于用戶給定的n個url，因為屬于同一主題，我們可以認為這些url指向的網(wǎng)頁已經(jīng)聚為一類Mu，那么我 們 可 以 使 用 這n個 網(wǎng) 頁 文 本vui（i＝1，..，n）（xui，1，xui，2，...，xui，m）的中心位置來代表用戶定制主題的向量

2.2 模型修正

在上一小節(jié)中我們基于聚類的主題模型得到了表征用戶定制主題的向量，但是該模型存在著初始向量過少的問題。這些向量如果在特征空間上分布不均勻，那么它們的中心位置就不能很好地代表該主題。

為了能夠簡單直觀地說明這個問題，我們以三維的特征空間為例。

如圖1所示，假設該主題的所有文本映射到特征空間后聚類形狀為球形，那么這個球的中心，即圖中 “O”所示位置，就可以代表這個主題 （類）的中心。

圖1 初始向量在特征空間上不均勻分布

如果用戶給定鏈接對應的網(wǎng)頁文本映射到特征空間后為圖中 “＋”所示位置，則使用式 （7）計算后得到的主題中心位于圖中的 “Δ”所在的位置?？梢院苊黠@地看到，通過計算得到的用戶定制主題中心和實際的主題中心存在偏差。

為了解決這個問題，需要在爬行過程中尋找屬于高相關度的網(wǎng)頁來不斷修正用戶定制主題中心?；舅悸肥敲肯螺d一個網(wǎng)頁，提取網(wǎng)頁文本內容后映射為向量vw，使用式 （4）計 算 該 向 量 與vui（i＝1，..，n）的 余 弦 相 似 度Sim（vw，vui），vui（i＝1，..，n）為 初始鏈 接 對 應 的 網(wǎng) 頁 文 本 向 量。在VSM模型中，兩個向量的余弦相似度越接近于1，那么這兩個向量所對應的話題就越相似。當Sim（vw，vui）大于某閾值時，我們可以認為該網(wǎng)頁和用戶提供的某個網(wǎng)頁屬于同一話題，即這個網(wǎng)頁屬于該主題，那么我們就能使用向量vw來更新用戶定制主題中心。

用Mp（xp，1，xp，1，...，xp，m）表 示 更 新 前 的 主 題 中 心Mn（xn，1，xn，1，...，xn，m），表 示 更 新 后 的 主 題 中 心，vw（xw，1，xw，2，...，xw，m）表示用來更新主題中心的向量，那么更新公式可表達為

式中：n——用戶給出的鏈接個數(shù)，UpdateCount——已更新次數(shù)。

使用該方法更新用戶定制主題中心可以在一定程度上解決主題中心偏移的問題。

2.3 特征提取

在建模過程中需要解決的一個實際問題是特征的提取與特征權重的計算。

問題分析：初始信息只有用戶給定的一組鏈接，無法使用傳統(tǒng)的方法完成特征提取和IDF特征權重統(tǒng)計。

解決辦法：利用初始頁面的詞頻 （TF）作為特征的選取標準，特征權重也使用TF代替TF·IDF。

特征詞一般選擇最能夠代表該主題的一類詞，詞頻高低在一定程度上也能體現(xiàn)一個詞在主題中的重要程度，單純使用詞頻作為特征選擇標準和特征權重會使一些常用但是沒有具體意義的詞 （又叫做停止詞），例如“的” “了” “和”等詞具有較高的權重。所以統(tǒng)計完詞頻之后需要先進行停止詞的過濾再執(zhí)行特征降維。去除掉停止詞后可以大幅提高TF 作為特征權重的計算精度。

2.4 url排序策略

在得到用戶定制主題的模型之后，我們可以在基于best－first的策略上進行改進。我們使用url所在頁面對應的文本向 量vw（xw，1，xw，2，...，xw，m）與 用 戶 定 制 主 題 中 心 點Mu（xu，1，xu，1，...，xu，m）的余弦相似度Sim（vw，Mu）來作為url優(yōu)先級的衡量標準

Sim（vw，Mu）越接近1，則頁面vw與主題就越接近，該頁面上的url在隊列中排序越靠前。

3 用戶定制主題爬蟲實現(xiàn)

基于自適應主題模型，我們實現(xiàn)了用戶定制主題聚焦爬蟲。

系統(tǒng)框架如圖2所示，使用java語言實現(xiàn)。

圖2 用戶定制主題爬蟲結構

系統(tǒng)輸入為同一主題的初始url，由用戶自行指定。

系統(tǒng)框架中，下載模塊基于httpclient實現(xiàn)download函數(shù)，可以根據(jù)url下載網(wǎng)頁。

解析模塊負責將該網(wǎng)頁中的文本和鏈接解析出來交給策略模塊處理。主要實現(xiàn)了兩個函數(shù)extract＿urls和extract＿content。這兩個函數(shù)均使用了第三方java包jsoup。jsoup可以通過css選擇器的語法來取得html文檔樹中的特定節(jié)點。extract＿urls函數(shù)選擇所有含有href屬性的＜a＞節(jié)點，并過濾掉其中href屬性值結尾為exe、jpg等非html頁面，最后返回這些鏈接和對應的錨文本。extract＿content函數(shù)選擇首先判斷網(wǎng)頁類型是topic型還是hub型，判斷依據(jù)是所有錨文本的長度占整個頁面文本長度的比例，如果該比值大于0.6，則認為該頁面是hub型網(wǎng)頁，否則認為該頁面是topic類型；整個頁面文本的提取過程為選擇html文檔樹中所有節(jié)點，去掉其中＜script＞、＜iframe＞等特殊的節(jié)點，最后替換掉剩下節(jié)點的文本中換行符、空白符等無意義的符號，即得到了整個頁面的文本；對于hub型網(wǎng)頁，extract＿content返回頁面中的所有錨文本，對于topic型網(wǎng)頁，extract＿content返回頁面文本去掉錨文本以后剩下的文本。

策略模塊模塊實現(xiàn)兩個功能，一是依據(jù)自適應主題模型對初始url建模。過程為首先下載用戶給出的初始鏈接，調用extract＿content函數(shù)提取文本內容并完成特征提取，基于VSM 模型把網(wǎng)頁文本轉換為文本向量，然后計算這些文本向量的中心作為初始主題中心，并在后續(xù)的流程中更新主題中心。策略模塊另一個功能是分析網(wǎng)頁文本，對其中的未爬取url進行優(yōu)先級評估，加入url隊列并排序。具體做法為提取下載網(wǎng)頁的文本和url，轉換網(wǎng)頁文本為文本向量，計算該向量和定制主題中心的距離，把該頁面上的url去重后加入隊列，并根據(jù)該距離對隊列中的url進行排序。

系統(tǒng)工作流程如圖3所示。

圖3 用戶定制主題爬蟲工作流程

4 實 驗

4.1 評價體系

通常情況下使用收獲率 （HavestRate）來評價一個聚焦爬蟲的性能

式中：Na——爬取網(wǎng)頁的總量，Nr——爬取網(wǎng)頁中和主題相關網(wǎng)頁的數(shù)量。HavestRate 越高，則爬取相同數(shù)量網(wǎng)頁的情況下，相關網(wǎng)頁的數(shù)量就越高。在帶寬一定的情況下，HavestRate 較高的聚焦爬蟲能夠在相同的時間內獲取更多主題相關的網(wǎng)頁，效率也就更高。

4.2 實驗結果

為了客觀評價該聚焦爬蟲的性能，我們以使用bestfirst策略和width－first（寬度優(yōu)先）策略的爬蟲作為對比。

3個爬蟲都給定相同的10個體育新聞鏈接作為初始種子，基于best－first策略的爬蟲事先使用搜狗語料庫［10］進行主題的訓練。

在3個爬蟲各爬取了3000 個網(wǎng)頁后對爬行過程中HavestRate 的變化統(tǒng)計如圖4所示。從圖中可以看到使用width－first策略的爬蟲的效率最低，在爬行了3000個網(wǎng)頁之后HavestRate降到40%以下。使用best－first策略的爬蟲的效率最高，穩(wěn)定以后HavestRate 基本能保持在75%以上?；谧赃m應主題模型的策略效率比best－first策略略低，在70%上下浮動，但也遠遠高于使用width－first策略的爬蟲。比best－first策略效率低的原因是基于best－first策略的爬蟲使用了語料庫進行了訓練，在特征提取和特征權重的計算上具有優(yōu)勢，并且擁有更多的數(shù)據(jù)來確定主題向量。

圖4 實驗結果

5 結束語

為解決傳統(tǒng)聚焦爬蟲無法對未知主題爬行的問題，本文提出了基于聚類算法的自適應主題建模方法和修正方法，并基于該模型實現(xiàn)用戶定制主題聚焦爬蟲。通過對比實驗驗證，在沒有使用訓練集的情況下，該爬蟲達到了和使用訓練集主題爬蟲相當?shù)男?。在用戶只提供少量同一主題url的情況下，該爬蟲就可以完成未知主題的爬行，這點是傳統(tǒng)主題爬蟲無法比擬的優(yōu)勢，具有實際的應用價值。

［1］PENG Tao.Reseach on topical web crawling technique for topic－specific search engine ［D］.Changchun：Jilin University，2007 （in Chinese）.［彭濤.面向專業(yè)搜索引擎的主題爬行技術研究 ［D］.長春：吉林大學，2007.］

［2］Hati D，Kuma A.UDBFC：An effective focused crawling approach based on URL distance calculation ［C］／／Computer Science and Information Technology，2010.

［3］Taylan D，Dogus Univ，Poyraz M，et al.Intelligent focused crawler：Learning which links to crawl［C］／／Innovations in Intelligent Systems and Applications，2011.

［4］Almpanidis G，Kotropoulos C，Pitas I.Combining text and link analysis for focused crawling－an application for vertical search engines ［J］.Information Systems，2007，32 （6）：886－908.

［5］Hong Weihao，Cui Xiamu，Xu Chengyin.An improved topic relevance algorithm for focused crawling ［C］／／Systems，Man，and Cybernetics，2011.

［6］Yang SY.A focused crawler with ontology－supported website models for information agents［C］／／Expert Systems with Applications，2010.

［7］Punam Bedi，Anjali Thukral，Hema Banati.Focused crawling of tagged web resources using ontology ［J］.Computers and Electrical Engineering，2013，39 （2）：613－628.

［8］Sotiris Batsakis，Euripides GM Petrakis，Evangelos Milios.Improving the performance of focused web crawlers［J］.Data＆Knowledge Engineering，2009，68 （10）：1001－1013.

［9］Du Yajun，Hai Yufeng.Semantic ranking of web pages based on formal concept analysis ［J］.Journal of Systems and Software，2013，86 （1）：187－197.

［10］Sogou corpus ［EB／OL］.http：／／www.sogou.com／labs／dl／c.html，2013 （in Chinese）. ［Sogou語料庫 ［EB／OL］.http：／／www.sogou.com／labs／dl／c.html，2013.］