一種基于云模型的特征選擇參數(shù)優(yōu)化研究

宋 麗，張震雷，楊新凱

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

0 引 言

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

1 研究現(xiàn)狀

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

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

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

2.1 粒子編碼

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

1 2 3 4 … 199 200

2.2 粒子群技術(shù)

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

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

(1)

(2)

慣性權(quán)重：

(3)

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

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

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

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

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

(4)

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

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

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

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

w=wmin

(5)

(2)favg

(6)

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

(3)fi

w=wmax

(7)

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

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

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

算法描述如下：

輸入：原始特征集X'

輸出：特征子集

(1)特征預(yù)選

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

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

else∶fpg=fpi

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

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

圖1 CPSO特征選擇方法

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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