基于CFS-GA 特征選擇算法的中文網(wǎng)頁(yè)自動(dòng)分類

喻春萍，黃曉霞

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

0 引言

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

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

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

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

1.1 CFS

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

假設(shè)屬性為Y，y為Y 的每一個(gè)可能的取值，則Y 的熵的計(jì)算方法為

已知屬性X，計(jì)算Y 的熵的方法為

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

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

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

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

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

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

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

圖1 CFS-GA 算法描述

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

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

1.3 分類評(píng)估標(biāo)準(zhǔn)

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

2 實(shí) 驗(yàn)

2.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

2.3 實(shí)驗(yàn)步驟

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

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

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

2.4 對(duì)比實(shí)驗(yàn)結(jié)果

為了驗(yàn)證文中CFS-GA 特征選擇算法的有效性，將CFS-GA 與IG和CHI 算法進(jìn)行比較，分類算法采用weka 的NaiveBayesMultinomial 算法.實(shí)驗(yàn)結(jié)果見(jiàn)表1和2.

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

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

2.5 實(shí)驗(yàn)結(jié)果分析

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

3 結(jié)束語(yǔ)

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

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

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

［2］馮是聰，張志剛，李曉明.一種中文網(wǎng)頁(yè)自動(dòng)分類方法的實(shí)現(xiàn)及應(yīng)用［J］.計(jì)算機(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］.長(zhǎng)沙理工大學(xué)學(xué)報(bào):自然科學(xué)版，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)頁(yè)分類上的效果比較［J］.計(jì)算機(jī)工程與應(yīng)用，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)絡(luò)和CFS 特征選擇的網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)［J］.計(jì)算機(jī)工程與科學(xué)，2010，32(6):38.

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

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

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

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

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