基于極限學習機的網頁分類應用

陳先福，李石君，曾 慧

武漢大學 計算機學院，武漢 430072

1 引言

隨著互聯網的快速發展，Web信息呈現出海量化的趨勢。人們需要一個快速、智能化的工具有效地進行信息處理。網頁分類是Web信息挖掘的重要研究內容之一，與普通文本分類不同，網頁中存在多種噪音信息，例如廣告、導航等，分類的難度更大。目前國內外研究者進行了許多相關研究，提出了一些效果較好的網頁分類方法。國內方面，2001年，李曉黎等提出基于支持向量機與無監督聚類相結合的中文網頁分類方法[1]；范焱等提出了使用Naive Bayes方法協調分類Web網頁方法[2]；2007年，張茂元等提出了一種基于變調整學習規則的模糊網頁分類方法[3]；2010年，張乃洲等[4]在使用聯合鏈接相似度評估爬取Web資源過程中使用樸素貝葉斯分類器和支持向量機分別對普通頁面和結果頁面進行分類。從以上的研究現狀中可以看出，Web頁面自動分類的共同特點是采用基于機器學習模型（有監督或者無監督）學習網頁分類模式，然后進行自動分類。因此新的機器學習方法的提出，必然導致新的網頁分類方法。

隨著神經網絡的發展，多層前向神經網絡獲得廣泛應用，特別是成功地應用于復雜的模式識別和函數逼近問題。一般地，多層前向神經網絡采用BP算法進行學習。Funahashi，Cybenko等雖然證明含隱層的前向BP網絡具有任意連續函數到任意精度的能力，但該算法收斂速度很慢且易陷入局部極小點。為了有效解決算法所帶來的問題，最近提出一個新的學習算法，稱為極限學習機（ELM），其中廣義單隱層前饋網絡（SLFNs）的所有隱藏節點參數隨機地和分析地決定了SLFNs輸出權重。其只需要設置隱藏層節點個數，而在算法學習過程中不需要更新網絡中神經節點的輸入權值以及隱元的偏置，卻能產生唯一的最優解，因此具有學習速度快且泛化性能好的優點。

本文將極限學習機應用到中文Web網頁分類過程中，首先對中文網頁進行預處理，然后根據極限學習機輸入編碼定長的特征，提出一種新穎的定長特征向量編碼來表示網頁特征，最終給出一個基于極限學習機的中文網頁自動分類系統模型，稱為ELMWebC2S。下面在對極限學習機進行簡介之后，對基于極限學習機的中文網頁自動分類方法進行詳細介紹。

2 極限學習機

在應用神經網絡到具體的應用場景當中時，需要首先使用有效訓練集對網絡結構中的參數進行訓練，這個過程由學習算法來完成。后向傳播（BP算法）是前饋神經網絡最常用的學習算法。但是BP學習算法的學習過程時間消耗過長，因此限制了其應用范疇。2004年新加波南洋理工大學的黃廣斌教授[5]針對單隱層前饋網絡（SLFNs）首次提出了極限學習算法，稱之為極限學習機。該算法首先對神經網絡中的輸入權值和隱層節點偏置進行隨機賦值，只通過一步計算即可解析地求出網絡的輸出權值，極大地提高了神經網絡的學習速度，并以較強的泛化性能實現機器學習任務。其算法可簡單描述如下：

已知訓練樣本 (xi，yi)，i=1，2，…，M，隱層節點個數為N，且激勵函數為f(x)的標準單隱層前饋神經網絡：

的ELM學習算法[6]過程分為三步：

步驟1隨機設置輸入權值wi以及偏置bi，i=1，2，…，N。

步驟2計算隱層輸出矩陣H；其中H是一個關于wi，xj和bi的N×M矩陣，表示如下：

步驟3根據公式：

計算輸出權值β。其中，為隱層輸出矩陣H的Moore-Penrose廣義逆解[7]。β不僅可使訓練誤差最小，而且由文獻[7]可知β模最小。

可見，相比于傳統的SLFNs，ELM 在訓練的過程中不需要調整輸入權值wi以及偏置bi，只需根據相應算法來調整β值，便可獲得一個全局最優解，參數選擇的過程相對容易，訓練速度顯著提升。

3 基于極限學習機的網頁分類方法

本章給出基于極限學習機的中文網頁自動分類系統模型ELMWebC2S，如圖1所示，詳細介紹分類過程中涉及到的關鍵技術，包括中文網頁的預處理、特征詞選擇、特征權重的計算和極限學習機輸入編碼的結構設計等。

整個中文網頁分類過程分為訓練過程和實際分類過程。因此，整個系統通過存放網頁的文件夾名字來區分訓練網頁的類別和待分類網頁。例如：將已經分類的手機類網頁放入到以“手機”命名的文件夾內；將體育類網頁放入到以“體育”命名的文件夾內；將待分類網頁放入到以“待分類”命名的文件夾內，等等。將這些文件夾統一到一個目錄下，例如“ELMWEB”，這樣便于實現本文提出的基于極限學習機的中文網頁自動分類系統。ELMWebC2S將非“待分類”文件夾內的網頁作為訓練網頁，然后對“待分類”文件夾內的網頁進行分類，放入到“ELMWEB2”文件夾內，同樣以子文件夾的名字為分類結果，供用戶檢查。檢查合格后可以將這些分類正確的網頁放入到文件夾“ELMWEB”內，作為新的訓練集。具體分類過程如圖1。

圖1 分類系統模型的結構圖

3.1 網頁特征提取

文本分類的關鍵是如何提取特征信息，考慮到腳本結構與網站的風格有一定的聯系，同時網頁內容信息內嵌在網頁腳本當中。因此，預處理過程也大致分為兩類，一是綜合衡量腳本結構信息和內容信息[1-2]，二是只衡量內容信息[3-4，8-9]。本文采用綜合衡量網頁結構信息、文本內容信息和鏈接信息。下面詳細介紹所涉及到的具體問題。

3.1.1 文本內容特征提取

通過網頁特征樹表示后的網頁文本內容只存在于特征樹下的葉子節點中。對于一個葉子節點中的文本由一組中文單詞向量表示。網頁文本內容提取主要提取網頁中的中文信息，并不包含阿拉伯數字、英文和其他符號。通過去除停用詞、分詞和詞性標注，選擇名詞和動詞構成的向量作為網頁特征樹葉子文本，其定義如下：

定義1（節點文本向量） 集合T={w1/v1，w2/v2，…，wi/vi}，其中wi為葉子文本中出現的中文詞，vi為wi在節點文本中的權重。

為了減少計算復雜度，在計算節點文本時采用一元模型假設，即不考慮詞在文檔中的順序關系，詞與詞在文檔中的出現是相互獨立的。vi值的計算公式如下：

其中tfwi為節點文本中單詞wi出現的次數，N為文檔總個數，ni為包含單詞wi的文檔個數，D為節點文本分詞后的所有單詞集合。該公式是經驗公式，但實踐表明它是特征表示方法中的一個簡單、費用較低的工具[1]。

3.1.2 鏈接特征提取

鏈接特征包含兩個部分，http超鏈接和描述該超鏈接的文本。定義如下：

定義2（鏈接特征向量）為一個二元組L=(URL，T)，其中URL為超鏈接，T為超鏈接文本向量，其處理方法同第3.1.1節。

例1 ＜a href=http：//tech.sina.com.cn/geo/science/news/2011-09-08/0953893.shtml target=_blank＞ 人 與 機器人：人機嫁接技術或把人類引向永生＜/a＞

假設鏈接文本向量為{人/0.5，機器人/0.3，技術/0.25}。則使用鏈接特征向量表示后為：（http：//tech.sina.com.cn/geo/science/news/2011-09-08/0953893.shtml，{人/0.5，機器人/0.3，技術/0.25}）。

實際上網頁中包含的大量鏈接信息，既有與自身主題相關的相似網頁鏈接，也有毫不相干的廣告鏈接。因此，將鏈接特征提取出來后必然也導致噪音信息的引入。為了減少噪音對分類準確性的影響，需要對鏈接節點與包含該鏈接節點網頁進行相似性比較，以確定是否為該網頁的相關鏈接。

sim(，Tj)表示鏈接節點文本向量與宿主網頁中文本節點特征向量Tj的相似程度。該相似度計算公式如下：

公式（7）表示鏈接文本向量中相同單詞的個數與單詞總數的比值。

另外，網頁的文本信息和鏈接信息都是內嵌于網頁的結構編碼中的，那么如果能夠有效地表示網頁的結構特征，將更有助于網頁特征的描述，更進一步有助于網頁的分類。

3.1.3 頁面結構特征提取

網頁的頁面結構更能體現網頁的風格，而風格與網站的類型、網頁的內容有著密切關聯。因此，有效地提取重要網頁特征信息將有助于網頁主題的分類。在網頁結構特征提取方面，文獻[10]提出了一種Style樹來移除網頁中的噪音信息的方法，但是需要多個網頁比較計算才能得到，這不適合于單個網頁的分類任務。使用學習機可以自動獲得蘊含在網頁中的結構信息，并且具有一定的魯棒性。因此，本文將文檔樹進行精簡、改進來描述網頁的結構特點。改進后的文檔樹稱之為網頁特征樹，定義如下：

定義3（網頁特征樹T-Tree）一種精簡Dom樹，其滿足以下條件：

（1）該樹的葉子節點類型只有兩種，非空節點文本向量和非空鏈接特征向量。

（2）該樹的每個非終結點只包含兩種信息，節點類型和節點權重。其中節點類型為Dom樹中關于該節點類型的描述；節點權重為該非終結點包含的所有葉子節點中單詞權重的總和。

之所以非葉子節點權重采用其所有葉子節點權重總和的方式主要基于以下考慮：首先，依據非葉子節點和其葉子節點的層次關系，非葉子節點的重要性由其葉子節點的重要性來決定。其次，越上層的非葉子節點，其權重越大，有利于網頁結構特征的刻畫；并且該特征通過其節點權重與網頁內容信息相關聯。此外，該方法便于實現。

網頁特征樹的具體構建可參考文獻[11]。需要注意的是本文所定義的特征樹只有兩類節點；并且在構造中需要根據本文所定義的權重計算方法為節點賦值。

例2 以下html來自于http：//tech.sina.com.cn/mobile/n/2011-09-08/10576040001.shtml腳本。這里只列出部分代碼，說明網頁特征樹。

那么以上代碼產生如圖2所示的特征樹。

圖2 特征樹

網頁特征樹包含文本信息、超鏈接和超鏈接文本。雖然圖片內容也有助于網頁主題的理解，但是由于解析圖片技術較為困難，暫不加入到網頁特征樹信息中。

3.2 特征編碼

鑒于極限學習機的本質是神經網絡的特點，網頁特征樹是不能作為極限學習機的輸入。因此需要將網頁特征樹轉化為定長的編碼，以對應神經網絡中的神經節點。假設極限學習機的輸入端有N個神經節，那么網頁特征編碼最大由N個數字組成。另一方面，希望網頁特征樹的葉子節點數據放到編碼的前端，以防N值過小時主要的內容信息數據被裁掉。因此，在特征樹向特征編碼轉換的過程中，本文采用樹的后序遍歷方法來產生特征編碼。

定義4（特征編碼）由網頁特征樹后序遍歷得到長度為L的實數編碼，每個實數可以看成網頁的特征屬性。其中漢字和字母使用16位Unicode編碼；權重為實數，放在相應節點后面。如果后序遍歷編碼總長度小于L則補零，反之剪枝。

由于特征編碼是由本文所定義的特征樹轉換而來，因此，特征編碼包含網頁結構的特征信息、文本內容特征信息和鏈接特征信息。

例3圖2中的特征樹按照后序遍歷后的部分特征編碼如圖3所示。

圖3 特征編碼

4 實驗與結果分析

本文的中文網頁自動分類系統模型，ELMWebC2S采用Java和MATLAB相結合的方式來實現。使用java來完成頁面的抓取、頁面特征的提取和頁面特征編碼；MATLAB使用現有的ELM算法[12]。需要說明的是文獻[12]中的算法包對輸入數據有一定的要求，輸入數據介于[-1，1]之間。因此在使用頁面特征編碼作為ELM算法[11]輸入之前，需要對編碼進行規范化處理。將16位的Unicode編碼看成無符號整型，規范化公式如下：

另外，考慮到網頁包含信息較多的特點，設置單個特征編碼長度L=1 000，以保證足夠的網頁特征信息被輸入。ELM 輸入端神經元數量選擇分別為N=50、100、150、200、250、300。實驗數據來源于多個網站的不同類別欄目，具體如表1所示。

表1 數據來源及類別

實驗評估方法為文本分類系統常用的指標，準確率（Precision）和召回率（Recall），其數學定義可參見文獻[9]。首先，使用十折交叉驗證（10-fold cross-validation）檢驗ELMWebC2S模型在各個N值情況下準確率情況；此時訓練樣本個數M=420。然后，采用文獻[13]中SVM多類別分類算法作為比較算法，在N=300時進行分類比較。實驗結果如圖4、圖5所示。

圖4 各種N值情況下準確率

圖5 各種N值情況下召回率

圖6 兩種算法準確率比較（N=300）

圖7 兩種算法召回率比較（N=300）

從圖4中可以看出隨著N值的增加，分類精度逐步提高；與此同時，從圖5中可以看到網頁的召回率也在逐漸提高。這說明隨著N值的增加，編碼所包含的網頁信息就越多，更有利于分類任務。圖6、圖7將本文提出的ELMWebC2S與傳統的SVM進行比較，可以看出本文算法在分類精度和召回率上均略有提高。

5 結束語

本文提出了提取網頁特征方法、特征編碼方法以及基于極限學習機的網頁分類方法，并且在此基礎上將極限學習機的高效學習能力、神經網絡的容錯能力應用到含有噪音數據的網頁分類任務中。實驗結果表明該方法具有一定的有效性。

[1]李曉黎，劉繼敏.基于支持向量機與無監督聚類相結合的中文網頁分類器[J].計算機學報，2001，24（1）：62-68.

[2]范焱，鄭誠.用Naive Bayes方法協調分類Web網頁[J].軟件學報，2001，12（9）：1386-1392.

[3]張茂元，鄒春燕，盧正鼎.一種基于變調整學習規則的模糊網頁分類方法研究[J].計算機研究與發展，2007，44（1）：99-104.

[4]張乃洲，李石君，余偉，等.用聯合鏈接相似度評估爬取Web資源[J].計算機學報，2010，33（12）：2267-2280.

[5]Huang G B，Zhu Q Y，Siew C K.Extreme learning machine：a new learning scheme of feedforward neural network[C]//Proc of Int’l Joint Conf on Neural Networks，2004.

[6]Huang G B，Zhu Q Y，Siew C K.Extreme learning machine：theory and applications[J].Neurocomputing，2006，70（1/3）：489-501.

[7]Serre D.Matrices：theory and applications[M].New York：Springer-Verlag，2002.

[8]魯明羽，沈抖，陸玉昌，等.面向網頁分類的網頁摘要方法[J].電子學報，2006，34（8）.

[9]許世明，武波，馬翠，等.一種基于預分類的高效SVM中文網頁分類器[J].計算機工程與應用，2010，46（1）：125-128.

[10]Yi L，Liu B，Li X.Eliminating noisy information in web pages for data mining[C]//Proc of KDD2003.Washington，USA：ACM Press，2003：296-305.

[11]Ji X，Zeng J，Zhang S，et al.Tag tree template for Web information and schema extraction[J].Expert Systems with Applications，2010，37（12）：8492-8498.

[12]MATLAB codes of EML algorithm[EB/OL].[2013-10-11].http：//www.ntu.edu.sg/home/egbhuang/ELM_Codes.htm.

[13]朱慕華，朱靖波，陳文亮.面向文本分類的多類別SVM組合方式的比較[C]//全國第八屆計算語言學聯合學術會議，2005：435-441.