喻春萍，黃曉霞

(上海海事大學 信息工程學院，上海 201306)

0 引言

自進入信息化時代以來，因特網(wǎng)上的網(wǎng)頁數(shù)量增長迅猛.為了提高信息的檢索效率，很有必要對因特網(wǎng)上的一些網(wǎng)頁進行分類.盡管目前有Google，Yahoo，搜狐等分類目錄式的中文網(wǎng)站目錄，但由于其均為人工編纂，效率低下，而且更新速度慢，無法滿足當前因特網(wǎng)對信息實時性的要求.［1］因此，網(wǎng)頁自動分類的研究對基于內容的信息檢索、Web 數(shù)據(jù)挖掘具有深遠的意義.

中文網(wǎng)頁分類一般包括預處理、特征選擇和構造分類器等3個階段.［2］預處理包括文本標記(html標簽和JavaScript 代碼)的處理、分詞處理和停用詞處理.對中文網(wǎng)頁中的海量信息進行預處理后所形成的特征向量的維數(shù)高達幾萬、甚至幾十萬，這無疑會造成維災難.這些高維數(shù)據(jù)中含有大量的噪聲以及與類別不相關的信息，用其直接進行分類既降低分類效率又影響分類的精確度，因此特征選擇成為中文網(wǎng)頁分類中的一項關鍵技術.［3］特征選擇是一個NP 難題.［4］按照分類算法評價標準可以將特征選擇算法分成兩大類:過濾型(filter)和封裝型(wrapper).過濾型不考慮具體的學習算法，而是直接從原始數(shù)據(jù)出發(fā)得到各個特征的貢獻評價;封裝型則考慮具體的學習算法，由分類器的結果評價特征好壞.過濾型算法可以很快從原始特征集合中選出較優(yōu)的特征子集，但是該特征子集并不是最小的，且其中還可能含有與類別信息不相關的噪聲，從而與后續(xù)的分類算法產生較大偏差.封裝型算法具有很好的降維效果，選擇結果較好，但因其與特定的學習算法有關，特征選擇過程耗時較長.［5-6］

常用的文本分類算法有信息增益(IG)、χ2統(tǒng)計(CHI)、互信息(MI)和文檔頻率(DF)，其中IG和CHI 的性能較好［7-8］.基于關聯(lián)的特征選擇(Correlation-based Feature Selection，CFS)作為一種過濾型算法，是以屬性與類別之間的相關性以及屬性與屬性之間的冗余度為衡量依據(jù)的［9-11］，該算法雖然具有較好的降維能力，但其所得到的解不一定是全局最優(yōu)的.在文本分類中，遺傳算法(Genetic Algorithm，GA)因其具有全局搜索特性常被作為一種封裝型算法對特征進行降維處理.［12-14］本文將CFS 與GA 相結合，以CFS 的相關度度量作為GA 的適應度函數(shù)評價遺傳算法中的每個新個體.實驗證明，利用該算法進行特征選擇，可以有效降低特征向量的維度、減少學習分類器所需的數(shù)據(jù)量，具有泛化能力強、可找到全局最優(yōu)解等優(yōu)點.

1 基于CFS-GA 的中文網(wǎng)頁分類

1.1 CFS

CFS是一種經(jīng)典的過濾型特征選擇算法，其啟發(fā)式地評價單一特征對應于每個類別的作用，從而得到最終的特征子集.其評估方法如下:

假設屬性為Y，y為Y 的每一個可能的取值，則Y 的熵的計算方法為

已知屬性X，計算Y 的熵的方法為

差值H(Y)-H(Y|X)(即特征Y 的熵的減少量)可反映特征X 提供給特征Y 的附加信息，被稱為信息增益.信息增益可反映屬性X 提供給屬性Y 的信息的多少，因此信息增益值越大，那么X 與Y 的相關度就越高.由于信息增益是一種對稱性的測量方法，其缺點是傾向于選擇那些有更多取值的屬性.因此，為確保各個屬性可相互比較，使不同的屬性選擇產生相同的效果，需要對信息增益進行歸一化.這里使用對稱不確定性方法將其歸一到［0，1］.

1.2 基于CFS-GA 的中文網(wǎng)頁分類

在運用GA 進行特征選擇時，常將其自身設計成封裝型特征選擇算法.GA 在運行中基本上不需要外界信息，只需要依據(jù)適應度函數(shù)控制種群的更新，因此適應度函數(shù)的設計對特征子集的選擇至關重要，關系到特征選擇時的收斂速度和找到的最優(yōu)解.在基于GA 的封裝型特征選擇中，常采用學習算法的分類精度和最終選擇出的特征子集的大小作為適應度函數(shù).盡管該方法可以利用GA 的全局搜索能力找到全局最優(yōu)解，但是在處理大規(guī)模數(shù)據(jù)時效率極其低下，且復雜度較大.因此，考慮將GA 設計成一種過濾型的特征選擇算法，即將適應度函數(shù)設置成一種過濾型的算法，從而使其具有GA 的全局最優(yōu)特性和過濾性算法的高效率特性.接著就是考慮選用何種過濾型算法進行特征選擇.

在遺傳算法的遺傳操作中，比較優(yōu)秀的個體需要滿足兩個特性:(1)個體對分類的貢獻要盡可能大;(2)個體中包含的特征數(shù)要盡可能小(要使這樣的個體能夠遺傳到下一代，就要使其適應度值比較大).因此，需要選擇滿足上述兩個特性的過濾型算法作為適應度函數(shù).

在常用的文本特征選擇算法中，IG和CHI 的性能較好，且兩者性能大體相當.［7-8］IG 通過信息增益度量屬性與屬性之間的相關性，盡管能起到一定的降維作用，但其所選特征未必對分類的貢獻大，且其分類性能受樣本分布的影響;而CHI 只統(tǒng)計某個特征項是否出現(xiàn)，卻不考慮該特征項出現(xiàn)的次數(shù)，因此該算法對低頻詞有一定的夸大作用.綜合看，這兩種效果好的過濾型算法都不能滿足上述兩個特性.

文獻［9］提出的CFS 通過計算屬性與屬性之間的冗余度以及屬性與類別之間的相關度來度量所選特征的優(yōu)劣.屬性與類別的相關度越大(即對分類的貢獻越大)、屬性與屬性的冗余度越小(即所選特征數(shù)量越小)，CFS 的啟發(fā)值就越大.從CFS 的特性來看，它完全滿足比較優(yōu)秀個體的特性.因此，本文將GA 與CFS 相結合(CFS-GA)，將特征子集看作GA中的個體，利用CFS 的啟發(fā)值作為GA 的適應度函數(shù).啟發(fā)值越大的個體被遺傳到下一代的概率就越大，而CFS 啟發(fā)值越大表明特征與類別的平均相關性越大、特征與特征之間的平均冗余度越小，因此將CFS 啟發(fā)值大的個體遺傳到下一代就可保證所選個體中特征與類別的相關性大、特征維度小.結合GA 的全局搜索特性，本文算法可以得到全局最優(yōu)解.

CFS-GA 算法設計主要包括編碼方案、選擇算子、交叉算子和變異算子等4個問題.編碼方案中采用經(jīng)典的二進制編碼:假設有n個候選特征，則染色體長度為n，用n 位的0和1 構成的字符串表示一種特征組合;第i 位為1表示存在該詞，第i 位為0表示不存在該詞.對特征子集進行選擇時，采用經(jīng)典的輪盤賭選擇算子，每個個體被選中的概率與其適應度值成正比.在進行交叉時，采用單點交叉，即在屬性對中隨機產生交叉點，然后互換交叉點后的部分結構，產生新個體.變異采用基本位變異算子，即在二進制編碼中，0 變1，1 變0.在交叉率和變異率的選擇方面，為了產生較多的新個體，同時不致過多地破壞較好的特征子集，交叉率一般在0.40～0.99之間選取，變異率一般在0.000 1～0.100 0 之間選取.CFS-GA 算法描述和基于CFS-GA 的分類模型流程見圖1和2.

圖1 CFS-GA 算法描述

圖2 基于CFS-GA 的分類模型流程

基于CFS-GA 的特征選擇算法的網(wǎng)頁分類的時間復雜度是由特征選擇算法的復雜度和分類算法的復雜度兩部分組成的(這里沒有考慮預處理部分).若原始特征數(shù)為s，經(jīng)過特征選擇后的特征數(shù)為t(t≤s)，那么特征選擇的時間是一個關于s 的函數(shù)g(s)，分類的時間是一個關于t 的函數(shù)h(t)，則整個分類模型的時間為g(s)+h(t).

1.3 分類評估標準

網(wǎng)頁分類中一般采用的性能指標是準確率P(precision)和召回率R(recall)［15］.準確率為分類的正確網(wǎng)頁數(shù)與應有網(wǎng)頁數(shù)的百分比，即該類樣本被分類器正確識別的概率.準確率體現(xiàn)系統(tǒng)分類的準確程度.召回率為分類的正確網(wǎng)頁數(shù)與分到該類的網(wǎng)頁數(shù)的百分比.召回率體現(xiàn)系統(tǒng)分類的完備性.準確率和召回率分別反映分類質量的兩個不同的方面，是互補的.為了獲得比較高的召回率通常要犧牲準確率;同樣，為了獲得較高的準確率就要犧牲召回率.因此，需要有一種綜合考慮召回率和準確率的方法對分類器進行評價.F1值是常用的一種組合評價方式:F1=2RP/(R+P).

2 實 驗

2.1 實驗數(shù)據(jù)

實驗的數(shù)據(jù)集采用搜狗實驗室提供的中文網(wǎng)頁數(shù)據(jù)集.由于原數(shù)據(jù)集總的大小達500 G，且其中含有詞性標注等信息，本文使用該數(shù)據(jù)集的mini 版.考慮到實驗機器的性能問題，從原語料庫中抽取5個類共288 篇文檔，其中:IT 類59 篇，教育類61 篇，醫(yī)學類53 篇，體育類56 篇，交通類59 篇.

2.2 實驗環(huán)境與參數(shù)設置

硬件平臺為:操作系統(tǒng)Windows XP Professional SP3，CPU Intel?Celeron?M processor 1.30 GHz，512 MB內存，80 G 硬盤.實現(xiàn)語言為Java，實現(xiàn)平臺為eclipse+jdk1.6，在代碼中分類調用開源的數(shù)據(jù)挖掘平臺的weka中的分類算法(由新西蘭的Waikato 大學開發(fā)的一款開源的數(shù)據(jù)挖掘平臺，集成一系列的機器學習算法，實現(xiàn)語言是Java)分詞工具為中國科學院的imdict-chinese-analyzer，它是開源項目ICTCLAS 的Java 版本，其算法是基于隱馬爾科夫模型，其開源代碼可以在開源中國社區(qū)獲得.GA中的相關參數(shù):初始化種群規(guī)模為20;交叉率為0.6;變異率為0.033;種群迭代次數(shù)為100.

2.3 實驗步驟

(1)對原始數(shù)據(jù)集進行初步整理后，調用imdict-chinese-analyzer中的ChineseAnalyzer 類進行分詞，并擴充停用詞表，對特征集合進行粗降維.

(2)調用weka.jar中的TextDirectoryLoader，將*.txt 文件轉化成weka 能接受的*.arff 文件，然后利用weka.jar中的StringToWordVector 類構建向量空間模型.考慮到GA中要求文檔編碼是0-1 編碼，在StringToWordVector中設置屬性值為0-1 編碼形式，即將m_OutputCounts 的值設置為false.

(3)按圖1 的算法描述，根據(jù)weka 接口利用Java 語言編寫GA，然后按圖2 進行特征選擇，并調用weka中的分類算法進行分類，采用3 折交叉驗證的方式得到最終的分類結果.

2.4 對比實驗結果

為了驗證文中CFS-GA 特征選擇算法的有效性，將CFS-GA 與IG和CHI 算法進行比較，分類算法采用weka 的NaiveBayesMultinomial 算法.實驗結果見表1和2.

表1 各特征選擇算法的分類正確率、特征維度比較

表2 各特征選擇算法所得到的P，R，F(xiàn)1值比較

2.5 實驗結果分析

從表1和2可知:(1)經(jīng)過特征選擇后，分類正確率顯著提高，因此特征選擇在中文網(wǎng)頁分類中意義重大;(2)CFS-GA 降維能力好，其分類性能也優(yōu)于IG和CHI，這是因為在選擇特征時，本文算法不僅考慮特征與類別之間的相關性，而且考慮特征與特征之間的冗余性，從而能有效降低最優(yōu)特征空間的維度;(3)IG 與CHI 性能大體相當，這與文獻［7-8］所得的結論基本一致.總之，本文提出的算法對中文網(wǎng)頁自動分類具有一定的實用價值.

3 結束語

特征選擇的目的是降低特征向量空間的維度，提高分類效率.本文將CFS 與GA 相結合，用CFS 評價作為GA 適應度函數(shù)來評價個體.實驗證明，這種特征選擇算法能有效降低特征空間的維度，且其分類性能與當前比較成熟的特征選擇算法相比也有所提高.

進一步工作可以考慮網(wǎng)頁的結構特征.網(wǎng)頁含有豐富的結構信息，除純文本之外，還有其他一些對分類有貢獻的信息:如用Head和Title 標注網(wǎng)頁的標題和段落子標題，meta 標記中的name 屬性和content 屬性值是對網(wǎng)頁主題的描述，網(wǎng)頁中的超鏈接指向的內容有可能是與該網(wǎng)頁主題相關的內容.在下一步的工作中，可以利用這些信息提高分類的準確率.

［1］劉超.中文網(wǎng)頁自動分類研究及分類算法的設計與實現(xiàn)［J］.中國科技論文在線，2003:1-2.

［2］馮是聰，張志剛，李曉明.一種中文網(wǎng)頁自動分類方法的實現(xiàn)及應用［J］.計算機工程，2004，30(5):19-20.

［3］CUI Zifeng，XU Baowen，ZHANG Weifeng，et al.CLDA:feature selection for text categorization［C］//ICSC 07＇Proc Int Conf on Semantic Computing.Washington，DC，USA，2007:703-704.

［4］葉吉祥，龔希齡.一種快速的Wrapper 式特征子集選擇新方法［J］.長沙理工大學學報:自然科學版，2010，7(4):69.

［5］ELALAMI M E.A filter model for feature subset selection based on genetic algorithm［J］.Knowledge-Based Systems，2009，22(5):357-358.

［6］HUANG Cheenjung，YANG Dianxiu，CHUANG Yita.Application of wrapper approach and composite classifier［J］.Expert Systems with Application，2008，34(4):2871.

［7］單松巍，馮是聰，李曉明.幾種典型特征選取方法在中文網(wǎng)頁分類上的效果比較［J］.計算機工程與應用，2003，39(22):147.

［8］YANG Yiming，PEDERSEN J O.A comparative study on feature selection in text categorization［C］// Proc ACM SIGIR Conf on Res ＆ Dev in Inform Retrieval(SIGIR01)，2001.

［9］HALL M A.Correlation based feature selection for machine learning［D］.Hamilton，New Zealand:Univ of Waikato，1999:51-69.

［10］HALL M A，SMITH L A.Featrue selection for machine learning:comparing a correlation-based filter approach to the wrapper［C］//Proc Twelfth Int FLAIRS Conf.Florida，USA，1999:247-254.

［11］孫寧青.基于神經(jīng)網(wǎng)絡和CFS 特征選擇的網(wǎng)絡入侵檢測系統(tǒng)［J］.計算機工程與科學，2010，32(6):38.

［12］鄭濱，金永興.基于屬性約簡的海事人為失誤致因分析［J］.上海海事大學學報，2010，31(1):92-93.

［13］任江濤，孫婧昊，黃煥宇，等.一種基于信息增益及遺傳算法的特征選擇算法［J］.計算機科學，2006，33(10):194.

［14］宋淑彩，龐慧，丁學鈞.GA-SVM 算法在文本分類中的應用研究［J］.計算機仿真，2011，28(1):223-225.

［15］熊忠陽，劉道群，張玉芳.用改進的遺傳算法訓練神經(jīng)網(wǎng)絡構造分類器［J］.計算機應用，2005，25(1):32-33.

［16］黃曉霞，程論.綜合評價與數(shù)據(jù)挖掘的比較［J］.上海海事大學學報，2007，28(4):55-56.