曹琨

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

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

曹琨

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

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

網(wǎng)絡(luò)爬蟲；算法；改進(jìn)

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

1 HMM主題爬蟲框架

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

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

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

2 改進(jìn)HMM模型聚類策略

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

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

3 改進(jìn)HMM模型頁面采集方法

3.1 頁面與主題相關(guān)度判定

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

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

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

3.2 HMM爬蟲建模方法改進(jìn)

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

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

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

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

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

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

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

式（7）中，?t(i，j)表示在模型λ中，時(shí)刻為t時(shí)，部分觀察值序列為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爬蟲的基礎(chǔ)上，對K-means算法中的K值的設(shè)置方法做了改進(jìn)。首先，通過訓(xùn)練集聚類策略，解決了用戶通過經(jīng)驗(yàn)來定義K值帶來的諸多問題；其次，在傳統(tǒng)的方法上優(yōu)化了相關(guān)度的判別統(tǒng)計(jì)方法；最后，針對HMM爬蟲爬取來的網(wǎng)頁與主題相關(guān)度不高的問題，對兩個(gè)假設(shè)條件進(jìn)行了修改，從而改進(jìn)了HMM的建模方式。

［1］李光敏.文獻(xiàn)搜索引擎中特征項(xiàng)及權(quán)重的應(yīng)用［J］.計(jì)算機(jī)系統(tǒng)應(yī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-），女，講師，碩士，研究方向：計(jì)算機(jī)科學(xué)與技術(shù)。