基于遺傳算法優化綜合啟發式的中文網頁特征提取

沈高峰 ，谷淑敏

(1.鄭州輕工業學院 計算機與通信工程學院,河南 鄭州 450002； 2.中原工學院信息商務學院 基礎學科部,河南 鄭州 450007)

特征提取在自然語言處理領域有著非常廣泛的應用，是信息檢索、文本分類、文本聚類以及自動文摘生成等技術的關鍵。由于互聯網資源時刻都在不斷更新，中文文本呈現出“爆炸式”增長。然而，采用傳統人工方式進行特征提取的方法耗時較長，且具有一定的主觀性，因此快速準確地實現中文特征提取成為中文文本處理的關鍵。

目前，國內外學者已提出3類特征提取方法：基于概率統計的特征提取方法、基于傳統機器學習理論的特征提取方法以及基于自然語言理解的特征提取方法。基于概率統計的特征提取方法利用文本特征的統計信息進行關鍵詞提取，如TFIDF[1]、詞共現[2]等，該類方法具有簡單、通用的特點，不需要復雜的訓練過程，但準確率不高。基于傳統機器學習理論的特征提取方法通過對大規模語料庫進行學習，采用決策樹[3]、貝葉斯算法[4]、最大熵模型[5]等方法對訓練集進行訓練，從而得到相關模型，然后再利用該模型對關鍵詞進行提取，但該類方法較為復雜。基于自然語言理解的特征提取方法通常需要對中文文本從詞、句、語義、篇章等層級進行分析，從而獲得相關關鍵詞，這類方法更加符合關鍵詞提取的標注過程，但如何對文章進行準確的語言學分析還沒有得到有效解決，該方法的抽取性能非常有限。

針對上述傳統特征提取方法的特點和不足，提出了一種基于遺傳算法優化綜合啟發式的中文網頁特征提取方法。該方法首先對文本文檔的分詞結果進行詞性標注，然后計算文檔詞語的詞性、位置、TFIDF以及聚集特征等綜合啟發式，并用遺傳算法優化各啟發式的權重參數，最終提取獲得中文網頁特征詞。

1 基礎知識簡介

1.1 頻率

TFIDF是一種常用的信息檢索方法[6]。設N表示給定文檔集合Ω中的總文檔數目。對于給定文檔d，采用TFIDF算法得到該文檔中詞條t的權重wt為

(1)

式中：TF表示t在文檔d中出現的頻率。IDF表示文檔d在文檔集中出現的文檔數目，n表示文檔集中出現特征t的文檔數目。

從式(1)可知，如果特征t在文檔d出現的次數較多而在其他文檔中出現次數較少的話，那么特征t的權值就較大，表明該特征對文檔d的區分能力就較強，就可以作為文檔特征的候選之一。

1.2 關聯度

詞語的關聯表現為詞與詞之間構成的復雜網絡[7]。復雜網絡方面的研究表明，漢語語言的詞語之間的關聯度具有高度的局部聚集性和全局連接性，能夠用于表征文本特征[8]。

設V={v1,v2,…,vn}表示文檔特征的集合，(vi,vj)表示特征vi和特征vj之間的一條邊。G(V,E)表示的是一個圖，其中V為圖的頂點集合，E?{(vi,vj):vi,vj∈V}為圖的邊集。對于頂點vi，其度定義如下：

Di=|{(vi,vj):(vi,vj)∈E,vi,vj∈V}|

(2)

頂點vi的聚集度Ki為

Ki=

| {(vj,vk) :(vi,vj)∈E(vi,vk)∈E,vi,vj,vk∈V} |

(3)

頂點vi的聚集度系數Ci為

(4)

由式(3)和式(4)可得特征關聯度為

(5)

根據式(3)～(6)，詞語網絡中節點的度和聚集度系數可以描述特征在文本中的連接特性，處于重要位置的特征往往具有較高的關聯度。

1.3 詞性

詞性是一種淺層語言學知識的表示，該因素的獲取不需要對文本進行復雜的語言學標注和分析，從而能有效避免傳統采用語言學方法的缺陷。一般而言，中文文本特征的詞性往往集中在名詞、動詞、形容詞等實詞中。根據人工標注結果，對特征的詞性分布進行了統計分析，其結果如表1所示。

表1 特征詞性分布

從特征詞性統計分布可以看到，詞性能夠有效表征文檔的中文特征。排名前4位的名詞、動詞、形容詞和副詞達到關鍵詞總數的95.5%。因此，論文引入詞性作為特征提取的重要因素之一。該因素能夠有效區分停用詞等，克服了傳統基于統計方法無法解決高頻但無實際意義的中文詞語，從而提高特征提取的性能。

1.4 位置

位置是文本特征提取的一個重要因素。根據特征所在的位置，主要包括標題、摘要和正文3種。根據詞語所在的具體位置，還可細分為小標題、起始段、中間段、末尾段、起始句、中間句、末尾句等[9]。由于網絡文本一般不存在摘要，本文主要考慮特征位于標題、起始段以及其他3種情況。通常特征位于標題和起始段的概率較高，因此根據文本中特征所在的位置，按照標題、起始段、其他的順序分別賦給不同的權重。

2 論文所提方法

2.1 綜合啟發式

僅僅根據單詞頻率進行特征提取的TFIDF方法雖然簡單，但是也存在一定的缺陷，如數據集偏斜[10]，類間、類內分布偏差[11]等。而單純依靠復雜網絡中詞語之間關聯度的特征提取方法，則忽略了特征本身的頻率，容易造成特征提取聚集到某些無意義的高頻詞，如“的”等，從而導致特征提取出現偏差。研究顯示，融合頻率和關聯特征[12]能夠有效避免單一方法的缺陷，從而提高特征提取的效率。

此外，僅僅依靠統計知識容易造成特征提取偏差，特別是一些高頻詞如“是”、“和”等容易成為特征的候選。盡管這些詞可以通過建立“停詞表”對其進行過濾，但是構建合適的詞表非常困難，因此引入特征的詞性以及位置對特征進行進一步選取。

綜合以上因素，論文采用特征的頻率、關聯度、詞性以及位置4個因素來衡量待選特征。對于文本中的每個特征w，其權重計算公式為

score(w) =α×WFreq+β×WLoc+

γ×WCF+δ×WPOS

(6)

式中：WFreq表示特征的TFIDF啟發式，WPOS表示特征的詞性啟發式，WCF表示特征的關聯度啟發式，WLoc表示特征的位置啟發式。每個啟發式的具體描述如表2所示。

表2 特征各啟發式描述

2.2 特征提取流程

特征提取的基本流程如圖1所示，其中虛線部分為訓練模塊。對于給定的輸入本文，特征提取具體過程如下。

圖1 本文方法特征提取基本流程Fig.1 Flow of feature extraction in this paper

1)預處理。將網絡文本去除HTML格式，保留文本詞語的位置信息，并對文本進行分詞和詞性標注。

2)各啟發式計算。計算文本中每個詞語的TFIDF、關聯度、位置和詞性等啟發式。

3)啟發式融合。根據多啟發式融合模型，對詞語的4個啟發式進行融合，并計算得到綜合得分。

4)輸出結果。最后根據各特征得分的大小進行排序，選擇最優的特征并輸出。

2.3 遺傳算法優化權重參數

本文方法中各啟發式的參數權重選擇是一個典型的組合優化問題。由于遺傳算法簡單、易理解、易實現，且在解決組合優化問題有強大的優勢[13]，因此，論文采用遺傳算法對式(6)中的參數權重進行優化，從而得到一定范圍的最佳組合參數權重。這里限定4個參數權重的取值范圍為(0,1)，并且滿足α+β+γ+δ=1。然后根據經驗選取適當的初始值，并經過迭代計算，得到每個啟發式的參數權重。利用遺傳算法獲取各特征參數權重具體過程描述如下：

1)依據經驗，初始化各特征參數權重α=0.2，β=0.2，γ=0.4，δ=0.2；

2)采用十進制編碼對染色體進行編碼。首先把各參數都乘以10或100使它們變成整數，然后再對它們進行編碼，具體格式如下：L=αβγδ。 其中各參數均用3位十進制數來表示，例如：α=0.2，β=0.2，γ=0.4，δ=0.2，則先把它們轉化為α=020，β=020，γ=040，δ=020，則相應染色體編碼為：L=020020040020。

3)利用各參數權重計算相應召回率，以召回率作為染色體的適應度函數，召回率計算公式為

recall =n/N

式中：n代表同所標注的特征相符的特征的數目，N代表文檔集中所標注的特征總數目。

4)交叉和變異操作：遺傳算法的收斂速度以及解的質量在很大程度上取決于交叉概率和變異概率。為了防止算法陷于局部最優以及加快算法搜索效率，僅讓種群中較優個體參與交叉和變異，而當前種群最優個體則不參與。具體交叉概率和變異概率計算公式如下：

(8)

(9)

式中：a1、a2、a3、a4為0～1的隨機數，fmax是當前群體中最優個體的適應度值，favg是當前群體的平均適應度值，fc是參加交叉操作的個體中較大的適應度值，fm是變異個體的適應度值。

5)終止條件：當代種群最佳染色體適應度值和前代種群最佳染色體適應度值之差絕對值不超過10-5。

采用遺傳算法優化選擇各啟發式的參數權重，能夠有效避免通過主觀經驗來確定參數的主觀性，從而實現參數能夠依據訓練數據自適應地調優。下面的實驗驗證結果表明，采用該遺傳算法獲得參數權重能夠使本文特征提取方法獲得良好的提取效果。

3 實驗驗證

3.1 實驗總體設置

以Intel Core2 Duo CPU T6500、2.4 GHz、 2 GB內存和Windows XP 2SP2操作系統的PC機作為實驗平臺，以MATLAB7.0為仿真工具，進行2組實驗：

第1組實驗數據來自互聯網抓取的1 500個中文文檔，論文根據該數據集的來源將這些文檔分為5個類別，分別包括新聞、財經、科技、體育和娛樂，各類文檔數目分布均勻，都包含300篇文檔。實驗中選擇每個類別的200篇文檔作為訓練集，剩下的100篇作為測試集。

第2組實驗數據采用復旦大學計算機信息與技術系國際數據庫中心自然語言處理小組構建的中文文本分類語料庫作為實驗數據，其下載網址為：http://www.nlp.org.cn/categories/default.php?cat_id=16。該語料庫由20個類別的14 378篇文檔組成，其中6 164篇為測試文本，8 214篇為訓練文本；各類別的測試文本集和訓練文本集之間互不重疊，也即一篇文檔僅屬一個文本集并且每篇文本僅屬于一個類別。該語料庫各類別訓練文檔數分布極其不均勻，其中訓練文檔數較小的類別占大多數，約為11個類別，它們的訓練文檔數均少于100篇，如通信類文檔數僅有25篇。

由于所選語料庫是中文性質的，所以這2組實驗都采用中科院計算技術研究所的“漢語詞法分析系統ICTCLAS”對它進行分詞處理；分類工具軟件都采用紐西蘭的Waikato大學開發的Weka工具；因KNN分類器簡單、易實現而被廣泛應用，這2組實驗選它作為實驗分類器 (其中距離采用向量夾角余弦來度量，K=20)。

為了對論文所提方法性能進行全面考查，論文對這2組實驗分別做了不同方面的實驗內容：第1組實驗主要做特征詞選擇和召回率方面的實驗；第2組主要做耗時和分類性能方面的實驗。

3.2 第1組實驗(各類別數據分布均勻)

在該組實驗中，論文對比了基于頻率的特征提取方法、基于關聯度的特征提取方法以及本文方法性能。

3.2.1 特征詞選擇實驗結果

分別采用上面3種方法計算全部詞語的4個啟發式值，并根據不同啟發式權重進行排序，最后提取得分最高的前10個詞語作為最后的關鍵詞。表4為實驗對比結果。其中，基于頻率的方法用TFIDF來表示，基于關聯度的方法用CF來表示，本文方法用Multi來表示。

表3 3種方法下召回率對比結果

從表4可以看出，對于“都”、“隨后”這類詞，本文方法能夠有效地濾除。由于這類單詞在文本中通常具有較高的頻率，很難通過統計的方法有效去除。而且本文方法召回率能夠達到70%，表現出較好的提取性能。此外，比較特征詞自動提取和人工選擇，3種提取方法都得到了 “進口”這個特征詞，但人工標注卻忽略了這個詞語。通過查看原文，“進口”確實應該標注為特征詞，反映出人工選擇帶有較強的主觀性，這種主觀性很容易產生實驗誤差。同樣也反映出特征詞自動提取能夠在一定程度上克服這種主觀性的缺點。

3.2.2 召回率實驗結果

針對測試集的不同類別，論文分別對比不同特征詞提取方法的性能。由于不同類別的多啟發式融合參數不同，論文利用每個類別的訓練語料分別訓練得到各個類別的多啟發式融合參數。各特征詞提取方法性能采用該類別測試集上的平均召回率表示，實驗結果如圖2所示。

圖2 各特征提取方法在各類別下的召回率對比結果Fig.2 Comparison results of recall rate on feature extraction methods

從圖2可以看出，采用本文方法在各個測試集上的平均召回率均高于基于關聯度的方法和基于頻率的方法的性能，這說明該方法提取特征詞的性能穩定，在各個類別的提取效果均得到明顯提高。

3.3 第2組實驗(各類別數據分布極其不均勻)

在這組實驗中，采用宏平均F1值和微平均F1值作為分類性能評價標準，使用3種經典的特征提取方法:信息增益(IG)、x2統計量(CHI)、互信息(MI)與本文所提特征提取方法作比較。

3.3.1 耗時實驗結果

在實驗中，記錄了各特征提取方法從開始執行到執行結束整個過程所消耗的時間，其結果如圖3。

圖3 各方法消耗的時間Fig.3 Comparison results of consuming time

由于本文方法采用了多個指標以及組合方法，耗時有所增加。從圖3可以看出，在該組實驗中，本文方法在消耗時間方面劣于互信息方法和信息增益方法，但優于最耗時的x2統計量方法，但它們耗時相差不大，這也使得本文方法有一定的實用價值。

3.3.2 宏平均和微平均實驗結果

從各個特征提取方法所獲得的特征集(其中的特征已按權重逆序進行了排序)中，分別選取相應數目的特征對實驗數據進行宏平均F1和微平均F1計算，具體結果如圖4和圖5所示。

圖4 宏平均F1實驗結果Fig.4 Comparison results of macro-averageF1

圖5 微平均F1實驗結果Fig.5 Comparison results of micro-averageF1

利用特征數目的變化來考查分類器的性能，可以比較準確地反映出該分類器數對據樣本變化是否敏感。圖4表明：隨著特征數目的遞增，宏平均F1值不斷增加，但是由于實驗數據中各類別樣本分布極其不均勻而有所波動；圖4表明：隨著特征個數的不斷增加，微平均F1值也遞增并趨于一個相對較穩定的值。

從圖4和圖5可以看出：在本文方法所選的前1 500個特征上KNN分類器性能最佳，宏平均F1值約為84%，微平均F1值約為92%；在CHI方法所選的前1 500個特征上KNN分類器性能最佳，宏平均F1值約為74%，微平均F1值約為86%；在MI方法所選的前1 500個特征上KNN分類器性能最佳，宏平均F1值約為70%，微平均F1值約為84%；在IG方法所選的前2 000個特征上KNN分類器性能最佳，宏平均F1值約為61%，微平均F1值約為67%。這表明在該組實驗中，這4個特征提取方法的優劣依次為本文方法、CHI、MI、IG。原因在于：本文方法在選擇特征時，不但考查了特征的詞性和詞頻還考查了特征的位置和關聯度，從而有效地對待選特征進行全面考查，這使得本文方法受類別分布影 響較小，因此所選特征集較具代表性。CHI方法在選擇特征時不但考查了特征在文檔中存在的情況而且還考查了特征不在文檔中的情況，MI方法僅考查了特征在文檔中存在的情況，但它們都沒能有效地消除冗余特征。因此，這2個方法要劣于本文方法，但是CHI方法要優于MI方法；由于實驗中所用語料庫中各類別樣本分布相差較大，而IG方法對類別樣本分布極其敏感，因此，在此情況下IG方法所選擇的特征集代表性最差。

4 結束語

基于統計方法和基于語言學的特征提取方法已經被廣泛應用于特征詞提取。本文結合2種方法的優點，提出了一種基于遺傳算法優化綜合啟發式的中文網頁特征提取方法。該方法能夠有效利用詞語的內在屬性和詞語之間的鏈接關系，通過多種啟發式表征中文文本的特征，對特征詞進行較全面的考查。實驗結果表明該方法能夠有效融合不同因素的優點，與傳統方法相比，該方法具有一定的優勢，從而使得該方法在文本挖掘方面有一定的實用價值。

由于不同類別的文檔的因素分布不盡相同，論文接下來的工作將繼續研究不同領域內采用該方法的特征詞提取的性能。另外通過實驗發現，對于人工標注的結果，主觀性因素的影響依然存在。論文還將進一步研究合理的標注方式，對現有網頁數據進行處理，減少主觀因素帶來的實驗誤差。

另外，本文方法雖然采用了十進制編碼以及自適應交叉變異操作等措施來確保遺傳算法的性能，進而保證本文特征抽取方法的性能，但是目前有些智能優化算法比遺傳算法優秀，例如粒子群優化算法、蜂群優化算法等，如果把它們用于本文方法的參數權重優化，效果可能會優于遺傳算法。為此，作者下一步研究工作就是嘗試把其他智能優化算法用于本文方法的參數權重優化，以進一步提高本文方法的性能。

參考文獻:

[1]GHEYAS I A, SMITH L S. Feature subset selection in large dimensionality domains[J]. Pattern Recognition, 2010, 43(1): 5-13.

[2]NGUYEN M H, TORRE F D. Optimal feature selection for support vector machines[J]. Pattern Recognition, 2010, 43(3): 584-591.

[3]ZHAO Zheng, WANG Lei, LIU Huan. On similarity preserving feature selection[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(3): 619-632.

[4]JAVED K, BABRI H A, SAEED M. Feature selection based on class-dependent densities for high-dimensional binary data[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(3): 465-477.

[5]WU Xindong, YU Kui ,DING Wei. Online feature selection with streaming features[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(5): 1178-1192.

[6]LEE S, PARK C, KOO J Y. Feature selection in the Laplacian support vector machine[J]. Computational Statistics and Data Analysis, 2011, 55(1): 567-577.

[7]SONG Qinbao, NI Jingjie, WANG Guangtao. A fast clustering-based feature subset selection algorithm for high-dimensional data[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(1): 1-14.

[8]CHUANG L Y, YANG C H, LI J C. Chaotic maps based on binary particle swarm optimization for feature selection[J]. Journal of Applied Soft Computing, 2011, 11 (1): 239-248.

[9]李綱,戴強斌. 基于詞匯鏈的關鍵詞自動標引方法[J]. 圖書情報知識, 2011,12(3): 67-71.

LI Gang, DAI Qiangbin. Keywords automatic indexing based on lexical chains[J]. Document, Information and Knowledge, 2011, 12(3): 67-71

[10]朱顥東, 李紅嬋. 基于互信息和粗糙集理論的特征選擇[J].計算機工程, 2011, 37 (15): 181-183.

ZHU Haodong, LI Hongchan. Feature selection based on mutual information and rough set theory[J]. Computer Engineering, 2011, 37 (15): 181-183.

[11]JEONG Y S, KANG I H, JEONG M K. A new feature selection method for one-class classification problems[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2012, 42(6): 1500-1509.

[12]LIU Z, LIU Q. Balanced feature selection method for Internet traffic classification[J]. Networks, 2012, 1 (2): 74-83.

[13]MAHROOGHY M,YOUNAN N H, ANANTHARAJ V G. On the use of the genetic algorithm filter-based feature selection technique for satellite precipitation estimation[J]. Geoscience and Remote Sensing Letters, 2012, 9(5): 963-967.