曹琨

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

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

曹琨

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

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

網絡爬蟲；算法；改進

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

1 HMM主題爬蟲框架

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

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

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

2 改進HMM模型聚類策略

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

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

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

3.1 頁面與主題相關度判定

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

將網頁頁面分成4個部分：頁面標題、副標題、重點強調文字和普通正文。權重分配如下：

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

3.2 HMM爬蟲建模方法改進

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

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

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

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

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

本文在假設條件（5）和（6）的基礎上對HMM的學習算法Forward和Backward算法進行了改進，此算法是在模型λ下計算產生觀察序列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)=

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

4 結語

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

［1］李光敏.文獻搜索引擎中特征項及權重的應用［J］.計算機系統應用，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-），女，講師，碩士，研究方向：計算機科學與技術。