宋 麗，張震雷，楊新凱

(上海師范大學(xué) 信息與機電工程學(xué)院，上海 200234)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的蓬勃發(fā)展，網(wǎng)絡(luò)中的文本正以指數(shù)級的速度增長。因此，提取大數(shù)據(jù)量下的有效信息，提高文本分類的高效性和準(zhǔn)確性、提高高質(zhì)量和智能化的文本分類、滿足用戶所需要的信息服務(wù)具有重要的意義。特征選擇和特征降維是實現(xiàn)特征研究的關(guān)鍵步驟。文中主要研究的是特征選擇技術(shù)。文本特征選擇技術(shù)[1]是實現(xiàn)文本分類的關(guān)鍵問題之一[2]。常用的方法[3]是降低短文本特征維數(shù)和去除冗余無關(guān)的特征[4]。文中通過常用的文本特征選擇方法[5]進行預(yù)選；提出了一種基于云模型[6]優(yōu)化的特征選擇方法，預(yù)選的特征子集作為第二次特征選擇的原始特征空間，解決了特征子集規(guī)模大小難以確定的問題。

1 研究現(xiàn)狀

最原始的文本分類依賴于人工，該分類方式對參與文本分類工作人員的要求較高，需要他們對各領(lǐng)域的知識都有良好的認(rèn)知和掌握。該分類方法效率極低、成本較高，不適用于大規(guī)模文本分類的場景。20世紀(jì)50年代末，相關(guān)學(xué)者開始對文本分類方法進行研究。1961年，Maron等[7]發(fā)表了一篇關(guān)于文本分類的具有里程碑意義的文章，推動了文本分類的進展。20世紀(jì)70年代初，Rocchio[8]將線性分類器應(yīng)用于文本分類領(lǐng)域，該方法通過用戶的反饋信息不斷地修正分類器的權(quán)重參數(shù)，來提高線性分類器的學(xué)習(xí)與分類效果。90年代末，相關(guān)研究學(xué)者[9]將機器學(xué)習(xí)方法應(yīng)用于文本分類任務(wù)中。20世紀(jì)末，Yoav和Robert[10]提出了提升樹分類算法，進而形成強分類器，這一算法的提出將文本分類算法推向了高峰。國內(nèi)關(guān)于文本分類方法的研究起步較晚。目前，研究學(xué)者分別從特征選擇、權(quán)重、分類模型等角度對其進行研究。對特征選擇的研究，主要集中于特征擴展、特征選擇、特征權(quán)重計算和分類算法設(shè)計這幾個方面。常見的特征選擇方法大都是基于常用方法，包括模式匹配法、詞頻法、卡方統(tǒng)計法、互信息法等。例如，姚旭等[11]分析了特征選擇方法的框架，從搜索策略和評價準(zhǔn)則兩個角度[12]對特征選擇方法進行分析和總結(jié)，分析出對特征選擇的影響因素，并指出了實際應(yīng)用中需解決的問題；徐剛等[13]提出一種根據(jù)速度信息自適應(yīng)調(diào)整參數(shù)的粒子群優(yōu)化算法，該算法可解決復(fù)雜非線性優(yōu)化時搜索失敗的問題。

以上研究主要依賴于傳統(tǒng)的特征選擇、特征提取及特征技術(shù)的組合使用，云模型的應(yīng)用相對較少。文中主要通過傳統(tǒng)特征選擇技術(shù)進行預(yù)選，提出一種基于云模型的粒子群優(yōu)化方法進行二次選擇。

2 參數(shù)優(yōu)化模型

2.1 粒子編碼

粒子編碼一般有UTF-8編碼、二進制編碼、GBK、實數(shù)編碼等形式。粒子群優(yōu)化算法離不開編碼問題的設(shè)置。其中，二進制是最常用的編碼方式，二進制編碼具有易實現(xiàn)，編、解碼簡單操作等優(yōu)勢，得到了廣泛應(yīng)用。文中也采用二進制編碼，用0、1表示粒子的位置信息，1表示該粒子被選中，0表示該特征被丟棄；用特征模糊熵值初始化粒子群的初始化種群，如：含200個特征的文本集，5個種群數(shù)，生成一個初始矩陣[5*200],矩陣形式如下所示。

1 2 3 4 … 199 200

2.2 粒子群技術(shù)

在特征選擇的過程中，特征子集空間規(guī)模的確定成為一個難點。一般采用最優(yōu)化的方法，對特征集空間進行全局尋優(yōu)。文中采用粒子群算法(PSO)。PSO是一種全局優(yōu)化方法，將優(yōu)化問題的每個解作為搜索空間的一個“粒子”，每個粒子由優(yōu)化函數(shù)決定的適應(yīng)度來評價粒子當(dāng)前位置的優(yōu)劣。每個粒子有一個速度來決定各自移動的方向和距離。在每次迭代中，粒子跟蹤兩個“極值”來更新自己：一個是個體極值(pBest)，一個是全局極值(gBest)。

第i個粒子找到上述兩個極值，更新自己的速度和位置：

(1)

(2)

慣性權(quán)重：

(3)

其中，wmax為最大慣性權(quán)重；wmin為最小慣性權(quán)重；itermax為最大迭代次數(shù)；t為當(dāng)前迭代次數(shù)。

2.3 基于云模型的粒子群方法

針對粒子群算法[9]存在早熟和不收斂的問題，通過權(quán)重生成策略來改變慣性權(quán)重的方法，保證收斂速度與全局收斂之間的折中。

2.3.1 適應(yīng)度函數(shù)

特征選擇主要是剔除不相關(guān)或無用的特征來對文本進行預(yù)處理。文本分類的三個評價指標(biāo)中，準(zhǔn)確率最能衡量特征與類別的關(guān)系程度。因此這里的適應(yīng)度函數(shù)用準(zhǔn)確率這一評價指標(biāo)，公式如下：

(4)

其中，m為總類數(shù)；N為總的文本數(shù)；ni為類別i被正確分類的文本數(shù)。

2.3.2 權(quán)重生成策略

結(jié)合云模型的優(yōu)點，提出一種基于云模型的粒子群優(yōu)化算法，以動態(tài)確定慣性權(quán)重來避免粒子群的早熟收斂問題。

(1)fi>fpg:當(dāng)粒子的適應(yīng)度值大于當(dāng)前全局最優(yōu)值時，表示該粒子在群中是最好的，解與全局最優(yōu)值很接近。為了加快全局收斂速度，縮短運行時間，這種情況下使慣性權(quán)重最小。此時慣性權(quán)重為：

w=wmin

(5)

(2)favg

(6)

從公式中可以得到，w與適應(yīng)度函數(shù)值成反比，實現(xiàn)了較優(yōu)的粒子與較小的w值的對應(yīng)。經(jīng)實驗驗證，式中c1=c2=4。

(3)fi

w=wmax

(7)

通過閱讀文獻資料，總結(jié)出慣性權(quán)重通常取[0.4,0.95]這個區(qū)間時，粒子的優(yōu)化性能飛速提高。因此，wmin=0.4,wmax=0.95。

2.3.3 基于云模型的粒子群技術(shù)

基于云模型的特征選擇方法由兩階段完成。第一階段采用AFECE對原始的特征集進行預(yù)選；第二階段將第一階段預(yù)選出的特征子集作為第二階段的原始集，采用云模型特征選擇方法來進行第二次特征選擇。

算法描述如下：

輸入：原始特征集X'

輸出：特征子集

(1)特征預(yù)選

(2)初始化粒子群各參數(shù)

(3)計算慣性權(quán)重，更新粒子的速度和位置

else∶fpg=fpi

(6)根據(jù)結(jié)束條件來判斷是否滿足。否則返回到(3)

算法的結(jié)束條件是根據(jù)在全局尋優(yōu)的過程中，不斷變化的閾值來判斷的。圖1為算法的流程框圖。

圖1 CPSO特征選擇方法

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

利用從http://kdd.ics.uci.edu網(wǎng)站上下載的reuters-21578數(shù)據(jù)集進行仿真，訓(xùn)練集占80%，測試集占20%。

3.1 預(yù)選的特征子集性能

reuters-21578數(shù)據(jù)集，經(jīng)MI、CHI、ECE、AFECE四種特征選擇方法進行特征預(yù)選，效果如圖2和圖3所示。

圖2 不同特征選擇方法在不同特征維數(shù)下的精確率

圖3 不同特征選擇方法在不同特征維數(shù)下的F1值

3.2 基于云模型的粒子群優(yōu)化方法

在預(yù)選特征子集的基礎(chǔ)上進行二次特征選擇，初始化各參數(shù)如表1所示。

表1 初始化各參數(shù)

表1是二次特征進行選擇時各參數(shù)大小的設(shè)置。第一階段的特征子集空間選擇400作為第二階段的原始特征空間。這里的種群數(shù)與類別數(shù)是一一對應(yīng)的。其他各參數(shù)是通過數(shù)據(jù)訓(xùn)練的調(diào)試及經(jīng)驗進行設(shè)置的。表2是第二階段的三種特征選擇方法與第一階段的AFECE特征選擇方法所得的實驗結(jié)果。可以得出，SPSO所需的特征維數(shù)最少，就能達到較好的分類效果，但它的性能是四種方法里最低的。AFECE特征選擇方法性能優(yōu)于PSO、SPSO，但它是以犧牲空間換來的。CPSO特征選擇方法性能有所改善，在精確率方面提高了4.4%，且所需的特征空間小。

表2 reuters-21578語料上各參數(shù)優(yōu)化方法的 對比實驗結(jié)果

4 結(jié)束語

基于特征子集空間規(guī)模大小難以確定的問題，提出了一種基于云模型的特征選擇算法，由以下2個階段組成:第一階段比較MI、CHI、ECE、AFECE四種特征選擇方法在性能上的優(yōu)缺點，得到AFECE特征選擇方法性能最好；第二階段通過AFECE特征選擇方法選出的特征子集作為這一階段的原始特征空間，提出基于云模型的粒子群算法進行二次特征選取，避免了粒子過早收斂達到局部最優(yōu)而不是全局最優(yōu)的不足。實驗結(jié)果證明了該方法的有效性和可行性。文中在特征選擇方面做了一定程度的研究，在分類器設(shè)計方面沒有進行嘗試。因此提出適合的分類方法和改進分類器參數(shù)的確定將是今后研究的工作之一。除此之外，將該方法應(yīng)用于產(chǎn)品智能推薦研究領(lǐng)域也是下一步重點研究的工作。