基于語義的聚焦爬蟲算法研究

孫紅光，藏潤強，姬傳德，楊鳳芹，馮國忠

(1.東北師范大學信息科學與技術學院，吉林 長春 130117； 2.智能信息處理吉林省重點實驗室，吉林 長春 130117； 3.吉林大學計算機科學與技術學院，吉林 長春 130012)

0 概述

傳統搜索引擎是通過關鍵字匹配對網頁進行比對[1]，結果將使搜索引擎返回大量無關的頁面而影響用戶使用，忽略了網頁的相關性和網頁的訪問優先次序.主題爬蟲(聚焦爬蟲)的出現正是由于互聯網中所有的信息資源并不都是用戶所感興趣的，因此需要一種機制可以面向用戶的需求而對獲取的資源進行判斷.主題爬蟲可以使用未訪問URLs的主題相關性判定機制確定其主題相關性，因此可以從互聯網中獲取更多用戶感興趣的信息資源.

從主題爬蟲被提出到現在一直有很多學者對其進行了研究，P.D.De Bra等[2]提出“fish-search”將主題爬蟲對于網絡資源的采集過程比作魚群覓食的過程；A.Patel等[3]通過對HTML文檔的標簽和屬性等結構信息進行分析與應用，提出基于應用文檔的主題爬蟲；J.W.Lin等[4]提出在語義上比較標記語料庫中輸入字段的相似性，自動識別爬行過程中遇到的輸入字段；H.Dong等[5]在提出的半監督主題爬蟲SOF中包含網絡信息格式化，是一種基于本體的半監督學習框架和由支持向量機聚合的混合網頁分類方法；杜亞軍等[6]通過改進文檔詞項與主題詞項的相似度計算公式，來改善爬蟲性能的SSVSM；林超等[7]提出主題爬蟲算法主要用于深度網絡資源信息的發現；Ran Yu等[8]提出了一種自適應的聚焦爬行方法，它考慮到種子列表的特征，從而改進了爬蟲和相關排序方法.

但是，基于語義的主題爬蟲仍然存在許多缺點，如主題確定的隨意性，相似度計算模型存在不足，對于主題詞項細化過于苛刻，或者某些詞項會隱藏在一些不相關的詞項之后，會造成抓取的相關頁面數量不足以滿足用戶的需求，如何讓計算機能夠自動解決成為主題爬蟲面臨的一個重要問題之一.為彌補語義主題爬蟲存在的不足，本文提出主題爬蟲算法，首先使用LDA構建主題模型，并將依據本體獲取的語義相似度加入到向量空間模型VSM中，從而對語義相似度計算模型進行改進，另外加入上位詞替換模塊，以保證不出現主題過于細化導致檢索結果過少的情況，最后計算未訪問URLs的全文本和錨文本與主題的相關程度，從而對未訪問URLs的優先級進行排序.

1 相關技術與研究

1.1 基于LDA主題模型的主題構建

頁面文檔和主題文檔的相關性除了詞項間的重復關系外，還與文字的語義信息有關，如挖掘相關聯的語義信息，爬蟲的抓取結果的準確性將進一步增加.主題模型是發現所包含的隱藏主題并對其進行建模[9]，它與傳統信息檢索的文檔相似度計算方法不同，性能更優，并且可以自動發現互聯網資源中大量的文字間語義主題.

首先，用生成模型分別對文檔和主題進行描述.生成模型的主要思想是指文檔中每個詞語都以一定的概率指向一個主題，同時每個主題又都以一定的概率指向某一篇文檔，從文檔出發，找出文檔所對應的主題和主題所對應的詞項構成模型，LDA通過調整參數實現對模型參數的控制[10]，計算公式為

(1)

圖1 文檔中詞語概率圖示

公式(1)概率圖示見圖1.圖1中：左邊方框表示詞語在文章中出現的概率c是已知的；主題中每個詞語出現的概率用Φ矩陣表示，看做是文檔中主題所占的比例；主題模型的構建就是通過訓練大量已知的“詞語-文檔”矩陣，得出未知的“詞語-主題”矩陣Φ和“主題文檔”矩陣Θ.

本文在給定主題爬蟲概念時，首先使用維基百科或百度百科對該概念進行解析，這里假設主題中對于某一個概念的描述是具體的、全面的.模型構建過程是無監督并跨語言、完全自動化的，不需要人工進行標注，自動計算多種概率.

1.2 改進的語義相似度向量空間模型

向量空間模型沒有考慮任何語義信息，只要網頁中詞項不與主題詞項有重復就認為網頁是與主題無關的，不考慮同義詞或近義詞而直接判定為主題無關，這顯然不合理，例如更精確地指導爬蟲獲取與主題相關的網頁集合，此方法不夠完善.對于語義相似度檢索模型，即網頁詞項與主題詞項集集合之間都是同義詞或者重復詞項，該模型雖考慮了語義信息卻忽略了能夠代表網頁與主題信息的詞項出現頻率比較高的事實，按照語義相似度檢索模型將判定此時網頁與主題的相關性度為1，這顯然也是不合理的.最后可能導致網頁與主題間的相似度計算不準確，從而導致主題爬蟲逐步發生主題漂移，繼續檢索返回的結果都是與主題無關的.

為解決上述問題，本文對語義相似度計算方法中使用模型進行改進，提出改進的語義相似度計算模型(SVSM).SVSM主要結合了向量空間模型(VSM)[11]和語義相似度檢索模型(SSRM)[12]的優點，同時彌補了兩者的缺陷.此模型首先構建網頁與主題向量空間模型，并將主題的語義向量的語義值置1，通過計算網頁文本詞項與主題詞項的平均語義相似度后加入到構建的向量空間模型中，形成具有語義與統計信息的語義向量空間模型，采用乘積的方法加入語義信息，對于向量空間模型中的每一個數值，都可以看做該詞項與主題詞項的平均語義相似度.最后，通過計算主題語義向量與頁面主題向量的夾角余弦值確定頁面與主題的相似度.

1.2.1 語義向量構建

同時構建頁面內容和主題的向量空間模型并加入語義信息，從而得到文檔與主題的語義向量.語義向量構建方法主要包括如下步驟(給定文檔d和主題t)：

STEP1：進行預處理，包括分詞和去停用詞等獲取文檔詞項和主題詞項；

STEP2：使用相同詞項構建頁面文檔與主題文檔的向量空間模型，使用TF-IDF計算詞項權重構建文檔與主題向量空間模型；

STEP3：獲取文檔詞項與主題詞項間的語義相似度；

STEP4：計算主題語義向量，這里認為一個主題與它自身的語義相似度為1，即形式上與向量空間模型相同；

STEP5：計算文檔d的語義向量，計算出文檔d中的每一個詞項與主題中每個詞項的語義相似度并求出平均值，最后與對應的詞項權重相乘，構建文檔d的語義向量.

現使用一個具體的例子對上述算法進行描述.經過STEP1后，STEP2構建文檔與主題的向量空間模型的公式為：

DT={term1，term2，…，termn}，d= (Wk1，Wk2，Wkn，0，0，…，0)；
TT={term1，term2，…，termm}，t= (Wt1，Wt2，Wtm，0，0，…，0).

(2)

文檔d的詞項集合用DT表示，主題t的詞項集合用TT表示，文檔d和主題t的向量分別用d和t表示，Wki(1≤i≤n)為在文檔dk中詞項i的TF-IDF值，Wtj(1≤j≤m)為主題t中詞項j的權重，n，m為文檔dk、主題t的詞項總數，主題t中出現而文檔d中未出現的詞項和文檔d中出現而主題t中未出現的詞項集合用0表示.文檔向量與主題向量長度相等，例如一個主題和一篇文檔，公式為：

主題t：TT={平臺，課程，文本}=(0.24，0.1，0.09，0，0，…，0)；

文檔d：DT={章節，部分，步驟}=(1.4，1.1，0.4，0，0，0，…，0).

(3)

獲取文檔詞項與主題詞項間的語義相似度.詞項之間的語義相似度可以通過詞項在HowNet本體的位置信息獲得[13-14]，上例的中文文檔詞項與主題詞項的語義相似度如表1所示.

表1 文檔d和主題t的語義相似度

STEP4中認為一個主題與它自身的語義相似度為1，對于其他文檔而言，主題向量在被賦予語義信息(1，1，1，1，…，1)后沒有發生形式上的改變，所以得到主題語義向量，公式為

STV=(0.24，0.1，0.09，…，0).

(4)

STEP5計算文檔d1的語義向量.首先計算出在文檔d中的詞項“章節”、“部分”，“步驟”與主題中各個詞項的平均語義相似度，其公式為

ST=(0.645，0.089，0.679).

(5)

STEP5計算文檔d的語義向量，其公式為

ST*DT=(0.645，0.089，0.679)*(1.4，1.1，0.4，0，0，…，0)=(0.916，0.039，0.184，0，0，…，0).

(6)

1.2.2 余弦相似度計算

向量空間模型中將文檔和主題向量化，當文檔與主題間的詞項發生重復時，才可以對文檔與主題的相關度通過余弦相似度進行計算.在SVSM 中，即使文檔和主題沒有共同詞項，文檔和主題都是通過向量表示后再附加語義信息，因為加入了語義信息，兩語義向量的余弦相似度是可以計算的.因此可以通過計算文檔dk的語義向量、主題t的語義向量TSV的余弦值，獲取文檔dk與主題t的相似度，其公式為

(7)

(7)式中Sim(d，t) 為文檔dk的主題相似度，文檔詞項與主題詞項權重分別用Wdi和Wtj表示.通過(7)式獲得上一節例子中文檔d和主題t的相似度，其公式為：

STV=TT=(0.24，0.1，0.09，0，…，0)；
SD=(0.916，0.039，0.184，0，0，0)；
Sim(d，t)=STV·SD=0.670.

(8)

SVSM首先使用TF-IDF值對詞項進行加權，加入詞項間的語義信息從而構建文檔與詞項的語義向量，計算兩者語義向量的余弦值并作為網頁的主題相似度.此模型在一定程度上考慮到向量空間模型統計上的優勢，同時加入語義上的特征，使網頁與主題之間相似度的獲取更加合理，并減少計算時間，提高抓取網頁信息的速度，使主題爬蟲能滿足抓取大量主題相關頁面信息的需求.由于加入語義信息，可以獲取與主題語義相關的頁面，最終提升主題爬蟲的抓取速度、抓取網頁數量和抓取結果的質量.

1.3 上位詞替換

1.3.1 知網(HowNet)的結構特點

圖2 上位詞和下位詞圖示

HowNet是用于反映概念之間的相同點與不同點的網狀結構，比如“老師”和“學生”，“人”是它們的共性.一個比較簡單的關系就是上下位關系，就是知網中概念與屬性的描述.其中相對于下位詞的延伸之一就是上位詞(hypernym)，例如：“筆記本電腦”的上位詞可以是“電腦”，“魚”的上位詞可以是“水產”，“交響樂”的上位詞可以是“音樂”.上位詞是針對某一個主題衍生出的概念，也存在其他的關系.等同詞、上位詞、下位詞、同類詞是主題詞的4種變化.上位詞和下位詞之間的關系如圖2 所示.

1.3.2 搜索中上位詞的使用

搜索首先要提煉關鍵詞，要先知道找什么，并對信息之間的共性進行分析，找出與其他信息不同的特性，對具有代表性的關鍵詞進行提煉，這就是選擇搜索關鍵詞的原則，它將影響對定位的速度和查找的準確性.

細化搜索條件：指的是如果你將搜索的條件描述得越詳細，所得到的搜索結果也越精確.對于檢索的細化過于苛刻時，或者某些詞項會隱藏在一些不相關的詞項之后，就像是一個通道，需要穿過這個通道才能找到想要的搜索結果.這種情況的出現，對于用戶而言增加了難度，需要增加相關的專業知識才能夠改變搜索條件，從而獲取更多的搜索結果.

為了讓計算機能夠自動地解決這個問題，本文結合知網的結構特性，提出上位詞替換的主題替換方法.利用本體中的上位/下位關系幫助主題爬蟲進行主題概念詞替換，實現主題重定義.當主題概念詞過于細化而導致搜索結果達不到目標下限時，主題爬蟲將使用該概念詞的上位詞重新進行爬行，重復這一過程直到得到滿意的結果為止.通過上位詞的替換會避免爬蟲出現概念過度細化而導致搜索結果過少的情況，使得爬蟲具備一定的穿越隧道的能力.

1.4 基于主題模型構建的語義主題爬蟲

圖3 基于主題模型構建的語義主題爬蟲框圖

基于主題擴展的語義主題爬蟲，主要利用LDA模型對檢索關鍵詞進行主題模型構建，然后利用SVSM計算網頁各種文本與主題的相似度，從而確定待爬行頁面的全文本與標題和主題的相關性，稱之為基于主題模型構建的語義主題爬蟲，最后改進為語義相似度計算模型并結合上位詞替換策略的聚焦爬蟲ESVSM，將主題與全文本的相關性和主題與錨文本的相關性進行組合，據此對鏈接是否是主題相關進行判斷，完整的流程如圖3所示.

本文提出的基于主題模型構建的語義主題爬蟲可以有效解決以下問題：

因為人為指定時帶有很大的隨意性，并且要求用戶具備一定的專業知識.雖然也有人使用統計的方法對主題詞匯進行擴展，但擴展的準確度僅僅依賴于詞項出現的頻率.本文提出的方法采用LDA模型對主題概念詞的描述文檔進行降維，使得主題概念得到較準確的擴充，為頁面文檔與主題相似度的計算準確性和頁面優先級的計算提供依據，充分體現基于語義的主題爬行算法準確度高的優勢.再利用SVSM 的語義檢索優點，使得該主題爬蟲具備語義理解能力，并且結合知網的結構特性，具有上位詞替換的特性，在保證檢索質量的前提下，具備一定的通道穿越能力，有效地引導主題爬蟲從互聯網中檢索回大量與主題相關的網頁.

當搜索達到某一條件下限時，比如搜索頁面數量少于1 000并且平均搜索時間內頁面數量不繼續增加時，將爬蟲關鍵詞替換成它的直接上位詞，從而使搜索結果得到擴充.當搜索條件是“智能手機”時，如果搜索結果滿足條件下限，“智能手機”將被直接上位詞“手機”替換.關于通道的穿越，一個典型的例子是，當搜索某一所高校的某一個老師發表的論文或著作，使用這個老師的姓名進行檢索時，隱藏在通道后面的該名老師的主頁可能沒有被檢索到，將影響搜索結果，此時，可以退回到該老師姓名的上位概念，例如學校名稱與學院名稱等，從而進入這名老師的主頁，關鍵詞得到匹配從而得到搜索結果，實現通道的穿越.

1.5 計算排序優先值模塊

通過SVSM模型對文檔與主題相似度進行計算，據此來判斷未訪問URLs與主題的相關度.文檔內容包括頁面的全文本和錨文本，本文對于未訪問URLs優先級的計算綜合考慮全文本和錨文本與主題的相似度，將全文本和錨文本與主題相似度進行線性組合作為未訪問URLs的排序優先值，將加權因子設為0.5，計算公式為

(9)

未訪問超鏈接l的優先值用priority(l)表示，也就是鏈接l與主題的相關度，父網頁l全文本fp與主題t的相似度用Sim(fp，t)表示，包含鏈接l的父網頁的總數為N，鏈接l的錨文本a1與主題t的相似度用Sim(at，t)表示，這里將線性組合因子設定為λ1=λ2=1/2.

給定2個加權因子，并使用相似度計算模型獲取網頁與主題的相關度值，然后使用加權因子將2個文檔的相關度進行組合作為未訪問URLs 的排序優先值.此主題爬行方法結合相似度計算和優先級判斷的優勢，使主題爬蟲可以實現語義理解，并且具備一定的通道穿越的能力，在主題爬蟲獲取頁面更準確的情況下縮短了頁面抓取時間，提高主題爬蟲系統整體性能.

2 實驗結果及分析

將本文提出的ESVSM爬蟲與其他4組爬蟲進行對比分析：

(1) 廣度優先爬蟲[15](BF Crawler).在本文實驗中作為基線爬蟲和其他爬蟲的參照，廣度優先爬蟲算法的主要思想是利用圖的廣度優先的策略對網頁進行遍歷.

(2) VSM主題爬蟲(VSM Crawler).VSM主題爬蟲算法的主要思想是通過構建頁面與主題的向量空間模型VSM，并通過頁面與主題的余弦相似度確定與主題的相關性.

(3) SSRM主題爬蟲(SSRM Crawler).SSRM主題爬蟲的主要思想是通過語義相似度檢索模型SSRM計算頁面與主題的相似性，頁面內容包括全文本和錨文本.

(4) SVSM主題爬蟲(SVSM Crawler).SVSM主題爬蟲通過本文提出的語義相似度計算方法計算頁面與主題的相關性，與ESVSM算法不同的是該算法并未使用LDA構建主題模型，主要用于驗證本文提出的主題爬蟲方法中主題模型構建的有效性.

(5) ESVSM主題爬蟲(ESVSM Crawler).ESVSM主題爬蟲算法由本文提出，算法的主要思想是先通過LDA構建主題模型，然后通過本文提出的改進語義相似度計算方法判斷未訪問URLs的爬行優先級，最后加入上位詞替換策略防止由于主題描述過于細致所產生的檢索結果較少的情況.ESVSM主題爬蟲使用頁面的全文本和錨文本計算頁面與主題的相關性，通過本體計算詞項間的語義相似度，設置主題爬蟲ESVSM Crawler的實驗參數，將獲取結果上限設定為5 000，下限設定為1 000.當爬行記錄中結果數量達到5 000時停止，在一定的時間內(設定為15 s)不再增加并且未達到下限時，將進行主題詞匯替換，然后進行主題擴充再繼續檢索.

2.1 數據集

主題爬蟲從相同的主題出發，設置相同的初始種子集.實驗中選定5個不同主題分別為酷睿、計算機、文本挖掘、操作系統、人工智能.用于主題擴展的描述文檔為百度百科文檔，使用百度搜索引擎檢索當前的主題詞項，得到前5個返回結果的URLs作為該主題的初始種子集合.實驗中設定選擇經LDA擴展的主題模型中的前10個子話題，作為主題模型的子話題，每個子話題選擇頻率最高的前20個詞項.

2.2 評價指標

(10)

2.3 實驗結果與分析

2.3.1 主題爬蟲獲取相關頁面數量對比分析

圖4 所有爬蟲主題“作者姓名”獲取相關網頁數量對比

為驗證主題上位詞替換方法的有效性，先進行如下實驗，本文將作者的名字作為主題，使用本文研究的主題爬蟲進行頁面獲取，得到結果如圖4所示.

從圖4中可以看出，由于網絡中不存在更多與作者姓名為主題的相關頁面，因此爬蟲不到500頁時，所有爬蟲的頁面抓取數量都增加緩慢，此時，將主題詞人為地替換為作者所在學校與院系并進行主題擴展，相關頁面數量呈明顯的上升趨勢，證明了主題上位詞替換的有效性，使得ESVSM爬蟲具有一定的穿越通道的能力.但由于網絡中相關頁面數量較少，所以隨著檢索返回頁面數的增加，相關頁面數量沒有繼續增加，此時由于程序設定上位詞只替換一次，直到返回頁面數量達到5 000時退出程序.

2.3.2 主題爬蟲獲取率對比分析

爬蟲檢索相關頁面的速度可以用獲取率表示(見圖5).圖5中由于初始種子集合都是與主題相關的，所以在開始階段VSM爬蟲表現最優，并且在檢索返回頁面達到500時最高，隨后開始下降，并在1 000 以后，緩慢升高.本文提出的ESVSM爬蟲隨著檢索返回頁面數量的增加，一直呈上升趨勢，尤其是返回前1 000 個頁面時，之后上升速度略有降低.本文提出的ESVSM爬蟲與其他爬蟲相比，獲取率高出20%～30%.證明了ESVSM爬蟲的高效性.

2.3.3 主題爬蟲獲取頁面平均相關度對比分析

平均相關度能夠衡量爬行結果的質量(見圖6).在爬行初始階段，各爬蟲爬行結果的平均相關度均較高，當返回頁面數量超過2 500以后，ESVSM爬蟲爬行結果的平均相關度要高于其他爬蟲，并且隨頁面數量的增加呈上升趨勢，平均準確率可達到85%以上.

圖5 主題爬蟲爬行獲取率對比

3 結束語

本文針對聚焦爬蟲算法存在的不足，提出ESVSM主題爬蟲算法，該算法通過LDA進行主題模型構建，并采用基于語義信息的向量空間模型計算文檔與主題的相似性，對于主題描述過于細化的情況，本文提出的主題爬蟲算法通過上位詞替換進行解決.實驗結果表明，本文提出的ESVSM爬蟲算法在爬行速度和爬行質量上都有一定的提升.

將來對網頁中其他的文檔如頁面內容標題等主題的相似度進行判斷，并分析頁面中其他文檔對未訪問URLs與主題相關性的影響.目前爬蟲的上位詞替換需要手動檢索并替換，未來研究工作將實現上位詞的自動替換.

[參 考 文 獻]

[1] RYAN G J，RYAN S W，RYAN C M，et al.Search engine：US，US6421675[P].2002-07-16.

[2] DE BRA P M E，POST R D J.Information retrieval in the World-Wide Web：making client-based searching feasible[J].Computer Networks & Isdn Systems，1994，27(2)：183-192.

[3] PATEL A，TING P.Apparatus，method，and computer program for dynamic processing，selection，and/or manipulation of content：US，US20120209963[P].2012-08-16.

[4] LIN J W，WANG F.Using semantic similarity for input topic identification in crawling-based web application testing[DB/OL].2016[2018-03-23].https：//arxiv.org/abs/1608.06549.

[5] DONG H，HUSSAIN F K.SOF：a semi-supervised ontology-learning-based focused crawler[J].Concurrency & Computation Practice & Experience，2013，25(12)：1755-1770.

[6] DU Y，LIU W，LYU X，et al.An improved focused crawler based on semantic similarity vector space model[J].Applied Soft Computing，2015，36：392-407.

[7] 林超，趙朋朋，崔志明.Deep Web數據源聚焦爬蟲[J].計算機工程，2008，34(7)：56-58.

[8] YU R，GADIRAJU U，FETAHU B，et al.Adaptive focused crawling of linked data[C]// International Conference on Web Information Systems Engineering.Berlin：Springer，2015：554-569.

[9] HOFMANN T.Probabilistic topic maps：navigating through large text collections[C]// Advances in Intelligent Data Analysis.Berlin：Springer，1999：161-172.

[10] BLEI D M，NG A Y，JORDAN M I.Latent dirichlet allocation[J].Journal of Machine Learning Research，2003，3：993-1022.

[11] BRIN S，PAGE L.The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks & Isdn Systems，1998，30(98)：107-117.

[12] KLEINBERG J M，KUMAR R，RAGHAVAN P，et al.The Web as a graph：measurements，models，and methods[C]// Proceedings of the 5th Annual International Conference on Computing and Combinatorics.Berlin：Springer，1999：1-17.

[14] 殷耀明，張東站.基于關系向量模型的句子相似度計算[J].計算機工程與應用，2014，50(2)：198-203.

[15] CHO J，GARCIA-MOLINA H，PAGE L.Efficient crawling through URL ordering[J].Computer Networks & Isdn Systems，1998，30：161-172.

[16] LIU W J，DU Y J.A novel focused crawler based on cell-like membrane computing optimization algorithm[J].Neurocomputing，2014，123：266-280.