基于極限學習機的網(wǎng)頁分類應(yīng)用

陳先福，李石君，曾 慧

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

1 引言

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

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

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

2 極限學習機

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

已知訓練樣本 (xi，yi)，i=1，2，…，M，隱層節(jié)點個數(shù)為N，且激勵函數(shù)為f(x)的標準單隱層前饋神經(jīng)網(wǎng)絡(luò)：

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

步驟1隨機設(shè)置輸入權(quán)值wi以及偏置bi，i=1，2，…，N。

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

步驟3根據(jù)公式：

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

可見，相比于傳統(tǒng)的SLFNs，ELM 在訓練的過程中不需要調(diào)整輸入權(quán)值wi以及偏置bi，只需根據(jù)相應(yīng)算法來調(diào)整β值，便可獲得一個全局最優(yōu)解，參數(shù)選擇的過程相對容易，訓練速度顯著提升。

3 基于極限學習機的網(wǎng)頁分類方法

本章給出基于極限學習機的中文網(wǎng)頁自動分類系統(tǒng)模型ELMWebC2S，如圖1所示，詳細介紹分類過程中涉及到的關(guān)鍵技術(shù)，包括中文網(wǎng)頁的預處理、特征詞選擇、特征權(quán)重的計算和極限學習機輸入編碼的結(jié)構(gòu)設(shè)計等。

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

圖1 分類系統(tǒng)模型的結(jié)構(gòu)圖

3.1 網(wǎng)頁特征提取

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

3.1.1 文本內(nèi)容特征提取

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

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

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

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

3.1.2 鏈接特征提取

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

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

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

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

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

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

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

另外，網(wǎng)頁的文本信息和鏈接信息都是內(nèi)嵌于網(wǎng)頁的結(jié)構(gòu)編碼中的，那么如果能夠有效地表示網(wǎng)頁的結(jié)構(gòu)特征，將更有助于網(wǎng)頁特征的描述，更進一步有助于網(wǎng)頁的分類。

3.1.3 頁面結(jié)構(gòu)特征提取

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

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

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

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

之所以非葉子節(jié)點權(quán)重采用其所有葉子節(jié)點權(quán)重總和的方式主要基于以下考慮：首先，依據(jù)非葉子節(jié)點和其葉子節(jié)點的層次關(guān)系，非葉子節(jié)點的重要性由其葉子節(jié)點的重要性來決定。其次，越上層的非葉子節(jié)點，其權(quán)重越大，有利于網(wǎng)頁結(jié)構(gòu)特征的刻畫；并且該特征通過其節(jié)點權(quán)重與網(wǎng)頁內(nèi)容信息相關(guān)聯(lián)。此外，該方法便于實現(xiàn)。

網(wǎng)頁特征樹的具體構(gòu)建可參考文獻[11]。需要注意的是本文所定義的特征樹只有兩類節(jié)點；并且在構(gòu)造中需要根據(jù)本文所定義的權(quán)重計算方法為節(jié)點賦值。

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

那么以上代碼產(chǎn)生如圖2所示的特征樹。

圖2 特征樹

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

3.2 特征編碼

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

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

由于特征編碼是由本文所定義的特征樹轉(zhuǎn)換而來，因此，特征編碼包含網(wǎng)頁結(jié)構(gòu)的特征信息、文本內(nèi)容特征信息和鏈接特征信息。

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

圖3 特征編碼

4 實驗與結(jié)果分析

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

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

表1 數(shù)據(jù)來源及類別

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

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

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

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

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

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

5 結(jié)束語

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

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

[2]范焱，鄭誠.用Naive Bayes方法協(xié)調(diào)分類Web網(wǎng)頁[J].軟件學報，2001，12（9）：1386-1392.

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

[4]張乃洲，李石君，余偉，等.用聯(lián)合鏈接相似度評估爬取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]魯明羽，沈抖，陸玉昌，等.面向網(wǎng)頁分類的網(wǎng)頁摘要方法[J].電子學報，2006，34（8）.

[9]許世明，武波，馬翠，等.一種基于預分類的高效SVM中文網(wǎng)頁分類器[J].計算機工程與應(yīng)用，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]//全國第八屆計算語言學聯(lián)合學術(shù)會議，2005：435-441.