基于HMM的主題爬蟲問題研究

曹琨

（新鄉(xiāng)學院計算機與信息工程學院，河南 新鄉(xiāng) 453000）

基于HMM的主題爬蟲問題研究

曹琨

（新鄉(xiāng)學院計算機與信息工程學院，河南 新鄉(xiāng) 453000）

對HMM爬蟲中K-means算法的K值選取方法作出相應改進，然后針對爬取網(wǎng)頁的內(nèi)容與主題相關度不高的問題，對隱馬爾科夫模型的假設條件進行修改，完成改進后的隱馬爾科夫爬蟲設計。

網(wǎng)絡爬蟲；算法；改進

隱馬爾科夫模型（Hidden Markov Model，HMM）應用比較廣泛。最初應用于通信工程領域，進行信號處理，之后被應用到自然語言處理方面，成為自然語言處理和通信系統(tǒng)聯(lián)系的紐帶；再到后來，機器學習比較流行，開始用隱馬爾科夫模型。該模型用于機器學習時，主要用鮑姆-韋爾奇訓練算法。HMM是一種具有統(tǒng)計特性的隨機過程概率模型，在該模型中參數(shù)表示尤為重要，并且是由馬爾科夫鏈和一般隨機過程組成。本文主要利用馬爾科夫鏈的隨機過程模型對網(wǎng)絡爬蟲予以改進。

1 HMM主題爬蟲框架

將HMM引入到主題爬蟲后，增加了爬蟲對網(wǎng)頁主題的識別能力，使用訓練好的HMM可以很好地預測爬取路徑。但是，經(jīng)過對隱馬爾科夫數(shù)學模型和基于隱馬爾科夫主題爬蟲的理論進行分析研究，可以發(fā)現(xiàn)在傳統(tǒng)的HMM模型中有部分不合理的地方。

HMM爬蟲運行主要有3個階段：①初始階段，對相關參數(shù)進行設置，選定初始網(wǎng)頁初始訓練集，進行頁面預處理等；②學習階段，對網(wǎng)頁進行文本相關度計算、類型聚類和構(gòu)建隱馬爾科夫模型訓練優(yōu)化；③運行階段，用優(yōu)化后的隱馬爾科夫模型對查找到的主體相關的站點進行分析，主要包括網(wǎng)頁內(nèi)容相關度判斷和超鏈接分析處理，將分析結(jié)果儲存起來，根據(jù)網(wǎng)址路徑爬取網(wǎng)頁到本地服務器。

經(jīng)過研究發(fā)現(xiàn)，傳統(tǒng)的隱馬爾科夫模型爬蟲存在以下幾個缺點：①和一些經(jīng)典爬蟲算法相比，HMM爬蟲時間消耗較大，其建模方法和算法有待改進；②在HMM爬蟲抓取的網(wǎng)頁中，主題相關度還有待提高；③對訓練集處理過于簡單，影響了爬行過程精確度，導致主題相關度降低很多。

2 改進HMM模型聚類策略

網(wǎng)頁數(shù)據(jù)聚類是將網(wǎng)頁數(shù)據(jù)按照相似性進行分類的過程，不同類中的網(wǎng)頁對象有很大的相異性。具體過程是：首先需要一個給定的分類體系和訓練樣本集，如“天眼輿情分析系統(tǒng)”中的中文網(wǎng)頁分類體系，其將所有網(wǎng)頁分為15個大類，即任何網(wǎng)頁都可以根據(jù)內(nèi)容歸屬到某一類樣本，這種利用已標記樣本集對未知樣本進行類別劃分的方法稱作“有監(jiān)督的學習方法”［1］。

K-means算法對網(wǎng)頁進行聚類的主要思想是認為兩個鏈接越近的網(wǎng)頁其相似度越大，這一思想看似簡單，但要確定劃分類別的數(shù)量K，同類的相似度高，不同類的相似度低。通常K的值是用戶給定的，而K值大小對爬蟲抓取的效率和準確度有很大的影響，很多用戶難以確定K值的大小。目前，很多學者致力于K值獲取方法的改進研究，比如利用圖論、距離代價函數(shù)和遺傳算法等。

3 改進HMM模型頁面采集方法

3.1 頁面與主題相關度判定

在傳統(tǒng)的HMM爬蟲系統(tǒng)中，采用空間向量模型（VSM）進行網(wǎng)頁主題相關度計算，通過計算用戶給出的關鍵字在當前頁面中的權值來判斷與頁面相關度，關鍵字出現(xiàn)在頁面中的位置也是衡量權值的重要因素。

將網(wǎng)頁頁面分成4個部分：頁面標題、副標題、重點強調(diào)文字和普通正文。權重分配如下：

例如，關鍵字“Apple”在某個網(wǎng)頁P的主標題中出現(xiàn)了1次，正文中出現(xiàn)了5次，且強調(diào)字體出現(xiàn)3次，那么關鍵詞“Apple”在網(wǎng)頁P中的權重計算方法為：

3.2 HMM爬蟲建模方法改進

HMM爬蟲基本工作原理是根據(jù)頁面與查詢主題的相關度來抓取網(wǎng)頁，如果相關則抓取，并且提取儲存此網(wǎng)頁的鏈接地址。如果不相關就舍棄，讀取下一個網(wǎng)頁。此方法最大弊端就是爬蟲經(jīng)過判斷丟棄了不相關網(wǎng)頁，而這些網(wǎng)頁中有可能存在著指向與主題相關度很高的超鏈接，這個問題使爬蟲丟失了部分有價值的頁面。這與HMM的假設條件和算法的不合理有關。HMM中存在如下2個假設。

假設1：系統(tǒng)狀態(tài)從t時刻向t+1時刻轉(zhuǎn)移時，其轉(zhuǎn)移概率只與t時刻狀態(tài)有關，與歷史狀態(tài)無關，即：

假設2：系統(tǒng)在時刻t輸出觀察值的概率只取決于當前時刻1所處的狀態(tài)而與之前的狀態(tài)無關，即：由于上述假設將網(wǎng)頁之間的鏈接關系割裂了，所以處理網(wǎng)頁之間的關系并不合理，如果和主題相關的網(wǎng)頁指向該網(wǎng)頁的概率大，那么就認為這個網(wǎng)頁上的鏈接也有很大的概率指向該網(wǎng)頁。為了挖掘出頁面當前狀態(tài)與歷史狀態(tài)之間的聯(lián)系，對上文兩個假設進行如下修改。

假設1：系統(tǒng)狀態(tài)從t時刻向t+1時刻轉(zhuǎn)移時，其轉(zhuǎn)移概率依賴于t和t-1時刻的狀態(tài)，即：

假設2：系統(tǒng)在時刻t輸出觀察值的概率取決于系統(tǒng)當前狀和系統(tǒng)前一時刻的狀態(tài)，即：

本文在假設條件（5）和（6）的基礎上對HMM的學習算法Forward和Backward算法進行了改進，此算法是在模型λ下計算產(chǎn)生觀察序列O=O0,O1…,Oi的概率,即P(O|λ)。

3.2.1 Forward算法。首先定義Forward變量?，如式（7）所示：

式（7）中，?t(i，j)表示在模型λ中，時刻為t時，部分觀察值序列為P(O0,…,Oi)的概率。Forward變量?t(i，j)可以遞歸求解，步驟如下：

3.2.2 Backward算法。類似地定義Backward變量β，如式（8）所示：

式（8）中，1＜t＜T-1，0＜i，j＜N-1，Backward變量β（i，j）遞歸求解步驟如下：

初始化：βT-1(i)=1，0＜i，j＜N-1；

迭代：βt(i,j)=

由此，根據(jù)Forward-Backward算法，在給定模型的情況下，產(chǎn)生觀察值序列的概率為：

4 結(jié)語

在傳統(tǒng)HMM爬蟲的基礎上，對K-means算法中的K值的設置方法做了改進。首先，通過訓練集聚類策略，解決了用戶通過經(jīng)驗來定義K值帶來的諸多問題；其次，在傳統(tǒng)的方法上優(yōu)化了相關度的判別統(tǒng)計方法；最后，針對HMM爬蟲爬取來的網(wǎng)頁與主題相關度不高的問題，對兩個假設條件進行了修改，從而改進了HMM的建模方式。

［1］李光敏.文獻搜索引擎中特征項及權重的應用［J］.計算機系統(tǒng)應用，2014（5）：188-191.

Research on Topic Crawler Based on HMM

Cao Kun
（School of Computer and Information Engineering，Xinxiang College，Xinxiang Henan 453000）

This paper made corresponding improvement on K value selection method of K-means algorithm in HMM crawler,then aiming at the problem that the correlation between the content and theme of the crawled page is not high,improved the assumed condition of the hidden Markov model,and completed the improved hidden Markov crawler designing.

network crawler；algorithm；improvement

TP391.3

A

1003-5168(2016)09-0027-02

2016-08-20

曹琨（1983-），女，講師，碩士，研究方向：計算機科學與技術。