基于頁面分塊與信息熵的評論發現及抽取

摘 要：提出了一種新穎的REA（Review Extract Algorithm）算法進行評論信息的發現與抽取。算法采用了頁面分塊與信息熵的迭代計算技術實現了評論塊的自動發現與抽取。其中，頁面分塊技術的運用有效地去除了噪聲信息；基于塊的熵值計算精確定位了每一個用戶評論。實驗結果證明該算法具有較高的查全率與查準率。

關鍵詞：評論抽取；自動；語義塊；熵

中圖法分類號：TP311.13文獻標識碼：A

文章編號：1001—3695(2007)02—0269—03

隨著電子商務的迅猛發展，越來越多的商家開始進行網上銷售，并且也有越來越多的人選擇網上購物。為了能讓潛在用戶了解已購買過某產品用戶的滿意程度與購買經驗，多數商家都會要求用戶對所購買的商品進行評價，以便為潛在用戶提供購買參考。結果使得Web上關于某類產品的評論信息迅猛增長，潛在用戶難以閱讀這些眾多的評論信息，從而難以幫助他們進行購買取向的決策。對產品的評論信息進行抽取與分析的工作就顯得非常必要。近年來，眾多研究者對評論抽取技術作出了深入研究，提出了具有重要價值的有效算法。然而，針對目前復雜多樣的Web頁面，進行評論抽取工作主要存在以下問題：①網頁頁面結構復雜，頁面中含有大量的與主題無關的信息，這些無關信息稱作噪聲信息。這些噪聲信息的存在將大大影響信息抽取的質量。②一個網站內部各個網頁的結構大致相同，但各個網站之間的網頁結構卻千差萬別。這就要求采用一種更為通用的信息抽取方法，能夠對這些千差萬別的網頁進行統一處理，從而使算法適用于所有頁面。

一般地，針對Web頁面的信息抽取方法主要包括手工抽取和自動抽取。手工抽取是通過觀察一個網頁的源代碼，找出其具體模式，然后手工編寫代碼對目標信息進行抽取。這種方法面對現在數量驚人的Web頁面顯得費時費力，是完全不可行的。自動抽取的方法主要利用Wrapper（Wrapper是一個從網站上抽取目標信息的程序），該方法主要利用了監督學習的思想。首先將一些手工標記的網頁作為訓練集，通過對訓練集的學習生成抽取規則；然后利用學習到的規則對新頁面進行信息抽取。這種方法在一定程度上具有自動抽取的能力，但是這種方法仍然需要大量的人工去準備訓練集，并且一個Wrapper只能適用于一種形式的頁面，所以它仍然浪費大量的人力和時間。Wrapper的系統包括Softmealy[6]，WIEN[7]等。

基于以上原因，筆者提出了一種基于頁面分塊和信息熵的評論發現與抽取算法——REA（Review Extract Algorithm）。REA算法充分考慮了信息抽取的自動性與通用性，利用頁面分塊與信息熵的迭代計算技術實現了對各種評論頁面中評論信息的自動抽取。

1 相關工作

1.1 頁面分塊

通常，一個Web頁面包含了不同的語義塊，這些語義塊都是不相關的，因此將整個頁面看作一個不可再分的整體是不合適的。于是，國內外很多專家學者開始進行頁面分塊的研究，即將頁面分割成多個語義塊，使塊內主題盡可能地相關于同一主題。對頁面進行分割以后：①可以直接去除一些無用信息塊，如導航信息和版權信息等；②對語義相關的塊進行操作，而不是整個頁面，這將大大提高信息檢索的質量。

針對頁面分塊，使用較多的是基于DOM（Document Object Model）樹的方法[4，9，10]。然而，由于HTML語法的靈活性，很多頁面并沒有遵循W3C規范，因此在構建DOM樹時就有可能產生錯誤。此外，DOM樹最初的引入是為了便于在瀏覽器中顯示，并不能描述頁面的語義結構。VIPS算法[1]的提出彌補了DOM分割的不足，在原有DOM方法的基礎之上結合了視覺信息對頁面進行語義塊劃分。本文利用了VIPS算法對頁面進行分塊處理，VIPS的工作主要分為三步：（1）將Web頁面解析成DOM樹結構，之后從DOM樹中抽取所有合適的塊。

（2）從抽取的塊中找出分離因子，進行頁面的劃分。

（3）構建整個頁面的內容結構。

VIPS算法的過程是這三步的一個循環過程。頁面首選被分為幾個大的語義塊，并且記錄下此層分割的層次結構。對每一個大的語義塊，相同的分割算法循環調用，直到最終語義塊的DOC值大于預先設定的PDOC值為止。DOC與PDOC的定義如下：

定義1 DOC（Degree of Coherence）用來測量每個可視塊的相關程度。DOC值越大說明塊中內容與主題越相關。

定義2 PDOC（Permitted Degree of Coherence）為分塊程序預先設定的許可相關度，用于為不同應用設置不同的分塊粒度。PDOC值越小，頁面內容結構越粗糙；否則頁面內容結構越精細。

1.2 信息熵理論

熵理論是由美國數學家香農（C.E.Shannan）提出的一種理論方法，他是從不確定性和概率測度的角度給信息下定義的。香農從信息源具有隨機性不定度出發，為信源推出一個與統計力學的熵相似的函數，稱為信息熵；這個熵就是信源的信息選擇不定度的測度，從而可以認為信息表征信源的不定度。為行為方便起見，先給出幾個定義與性質。

定義3 自信息量。任意隨機事件的自信息量定義為該事件發生概率的對數的負值。

設該事件xi的概率為p(xi)， 那么其自信息定義式為

定義4 平均自信息量。集X上，隨機變量I (x)的數學期望定義為平均自信息量。

集X的平均自信息量又稱作是集X的信息熵，簡稱熵。

性質1 Shannon不等式。熵值具有極值性與非負性，即

0≤H=-ni=1pi log2 Pi≤ log2 n

其中，Pi表示事件I的概率。

2 評論抽取的方法

本文提出了一種新穎的方法來發現并抽取頁面中的用戶評論，稱為REA算法。本算法主要對具有用戶評論的頁面進行評論信息的抽取。算法主要分為三個步驟：

（1）使用VIPS算法將頁面分為若干個語義塊；

（2）對每一個塊進行熵值計算，以確定哪些塊是評論塊，哪些塊是非評論塊；

（3）對信息塊迭代進行前兩步的操作，直至抽取出頁面中所有的評論信息。

通過步驟(2)的分析判斷，評論塊的坐標與屬性信息已經被記錄下來，故可以直接完成評論的抽取工作。

2.1 頁面分塊

一個Web頁面中的內容并非全部都是有用信息，其中還會包含一些導航信息、鏈接信息、版權信息等噪聲信息，這些信息的存在會大大影響信息抽取的效果。通過對頁面的分塊處理可以去除這些噪聲信息，同時各個塊的坐標與大小等屬性也均被記錄，這將便于信息的抽取。由于不同的頁面構造不同，欲想得到合適的分割粒度，即正好將每個用戶的評論信息單獨分割出來，就需要相應地對VIPS調整PDOC值。如圖1所示的是PDOC＝10時將各個用戶評論分割出來的頁面；圖2所示的是PDOC＝6時將各個用戶評論分割出來的頁面。

REA算法旨在適用于各種類型的評論頁面，使算法處理不同架構的Web頁面時，均能自動獲得合適的分割粒度。首先預設PDOC=5，然后循環調用VIPS，并使PDOC值逐漸增大，直至取得合適的PDOC值。

2.2 熵值的計算

評論塊的發現是通過計算各內容塊的熵值來完成的。通過熵值的趨向，可將內容塊分為評論塊與非評論塊，評論塊就是本文所要抽取的目標。

2.2.1 抽取各塊中的特征詞

熵值計算的目的是為了發現頁面中的信息塊。為了計算各塊的熵值，首選在各塊中抽取出一些特征詞，先分別計算各特征詞的熵值，最后將塊中包含的所有特征詞的熵值累加即可得到各塊的熵值。因此筆者首先進行各塊中特征詞的抽取。本文中特征詞的選擇是將塊內具有實際意義的形容詞定義其為表示用戶觀點評論的特征詞。

識別各塊中的形容詞/詞組，筆者所采用的方法是Part-Of-Speech (POS)標記(源于自然語言處理)。使用了NLProcessor 語言解析器對每個句子進行解析，標記出每個單詞的詞性(單詞是名詞，動詞還是形容詞等)，還能識別出簡單的名詞/動詞詞組。

NLProcessor系統的結果以XML格式輸出，如＜WC＝′NN′＞表示名詞，＜NG＞表示名詞詞組。由于用戶多用形容詞來表述自己對某產品的評價，所以僅抽取其中的形容詞作為特征詞。被POS標記的每一句話都保存在評論數據庫中。

通過計算每個特征詞的熵值，即可用來度量各特征詞表示評論的信息量大小。此熵值越大，說明此特征詞為評論詞的概率越大。同理，如果一個塊的熵值越大，表示塊內所載評論信息量越大，即成為評論塊的概率越大。

2.2.2 計算各塊的熵值

在抽取出頁面中的特征詞之后，首先計算各特征詞的熵值。為了使信息熵理論能夠很好地應用于評論抽取算法中，筆者對信息熵的公式及傳統的TF，IDF定義進行了變形與拓展。在我們的方法中，一個特征詞的熵值是由它在各塊中的分布情況確定的，即定義熵值公式中的Pi為其權重，而不是出現的次數，這是因為考慮到某些特征詞出現得越多，其區分貢獻反而越小，故用TF×IDF來代替TF。此外，筆者用塊的概念代替傳統的文檔，即TF是指每個特征詞在各塊中出現的次數，DF是指頁面中含有該特征詞的塊數。

定義5 權重。任意特征詞的權重等于此特征詞的TF與IDF的乘積，即Wi＝Pi＝TF×IDF。 

為了方便熵值的比較，可以將熵值的上下限平滑到0，1之間。

性質2 熵值的極值平滑。任意特征詞Fi的熵值可以通過將文檔數d作為對數的底來實現將熵的極值平滑到0，1之間。

計算出各特征詞的熵值后，即可計算出各內容塊的熵值。

定義6 內容塊的熵值。內容塊CBi的熵值等于塊內包含的所有特征詞的熵值相加。

其中k等于塊CBi內包含的特征詞個數。

最后根據塊的熵值H（CBi），可將塊分為以下兩類：

（1）如果熵值H（CB）大于預定閾值或趨向于1，則可定義其為評論塊。

（2）如果熵值H（CB）小于預定閾值或趨向于0，則可定義其為非評論塊。

2.3 評論抽取

評論抽取的關鍵在于評論塊的定位，本文提出的方法是對上述頁面分塊與熵值計算這兩步進行迭代計算，直到抽取出所有的評論塊。

REA算法描述了利用VIPS分塊結果與熵值信息進行評論抽取的完整步驟。程序從根節點出發（第1行），對輸入的每個頁面進行VIPS分塊算法(預設PDOC為5)，對得到的每一個塊進行熵值計算，標記出信息塊，并存入信息隊列當中。當PDOC值為5時，所分得的所有塊都計算完畢之后，PDOC增1，在信息塊中循環進行VIPS以及熵值計算，直至每個信息塊到達不可再分為止，從而抽取出頁面中的所有評論。

算法REA（BLOCK，PDOC）

預設PDOC值為5，運用VIPS對輸入頁面進行分塊（將頁面看作一個大的BLOCK）。

3 實驗與討論

實驗的目的是驗證基于頁面分塊的評論抽取算法的有效性。實驗是在一臺P4 2.0GHz CPU，512MB內存，運行Windows Professional的機器上執行，算法是用Microsoft Visual C++ 6.0實現的。

實驗選擇評論抽取的查全率與查準率作為評估ERA算法的指標，數學公式分別如下：

查全率（Precision）= 判斷正確的評論塊判斷的總塊數

查準率（Recall）=判斷正確的評論塊實際頁面的總塊數

F1值則是綜合考慮了查全率與查準率的復合評估指標，數學公式如下：

F1值＝ 查準率×查全率×2查準率+查全率

本文的實驗是在100個評論頁面上進行的。筆者一共從五個大型的評論站點（如amazon.com， ebay.com， c|net.com，epson.com等）上下載評論頁面， 每個站點上各下載20個網頁。為了不失一般性，下載的20個網頁包含了書刊、DVD、數碼、服裝和食品五個類別的用戶評論。

對每一站點的頁面，筆者先手工標記評論塊的個數，由于頁面中的評論塊信息非常明確，所以手工就能很容易地正確標記出評論塊個數。之后再用REA算法對每個頁面進行評論抽取，最后統計抽取評論塊的查準率、查全率及F1值。

表1給出了詳細的實驗結果。由于篇幅限制，僅給出了前15個評論頁面的抽取情況。表的第1，2列是測試評論頁面的部分URL序號與地址；第3列是對每個頁面手工預先標記出的評論塊個數；第4列是查找正確的評論塊數；第5列是運用REA算法后所找到的評論塊數。表格的最后一行分別統計了頁面中包含的所有評論塊數、REA算法所找到并是正確的評論塊個數及REA算法找到的評論塊總數。

表2給出了100個頁面的抽取結果。第1列是100個頁面中手工標記出的所有評論塊數，第2列是REA算法抽取出的評論塊數；第3列是正確抽取的評論塊數；最后給出了查全率、查準率與F1值。可以看出筆者的算法具有很高的效率。

4 結論

本文提出了一種新穎高效的技術來自動抽取頁面中的評論信息。筆者的算法主要基于頁面分塊和熵值計算，能夠實現對評論信息的自動發現和抽取，并且能適用于各種評論頁面。對抽取出的評論信息，可進一步對其進行挖掘分析，可輔助商家作出更有效的智能推薦系統。實驗表明，該算法對于評論信息的抽取具有很高的效率。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。