吳冰冰，哈力旦·阿布都熱依木，阿麗亞·艾爾肯，何　燕

(新疆大學(xué) 電氣工程學(xué)院，新疆 烏魯木齊 830047)

?

人工魚群優(yōu)化的維吾爾文文本特征選擇方法

吳冰冰，哈力旦·阿布都熱依木，阿麗亞·艾爾肯，何燕

(新疆大學(xué) 電氣工程學(xué)院，新疆 烏魯木齊 830047)

特征選擇是文本分類中的關(guān)鍵步驟，對(duì)分類結(jié)果產(chǎn)生直接的影響。本文分析了人工魚群算法的覓食行為、群聚行為和追尾行為等基本原理。結(jié)合維吾爾文文本特征提取原理，提出了一種改進(jìn)的人工魚群算法，并將其運(yùn)用到維吾爾文文本特征提取當(dāng)中。為了加快魚群的收斂速度，引入了主動(dòng)改變視野的策略，同時(shí)，為了避免算法陷入局部最優(yōu)，還在算法中加入了變異策略。將特征選擇后的樣本集輸入到不同的分類器中進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明：改進(jìn)的人工魚群算法能夠使分類的準(zhǔn)確率達(dá)到94.5%。

維吾爾文；文本分類；特征選擇；人工魚群算法

0　引言

文本分類技術(shù)是信息檢索領(lǐng)域研究的重點(diǎn)，也是數(shù)據(jù)挖掘的一個(gè)主要分支[1]。研究維吾爾文文本分類技術(shù)有利于中國(guó)少數(shù)民族文化在互聯(lián)網(wǎng)上的健康傳播。在文本分類過(guò)程中，特征選擇的好壞會(huì)對(duì)分類器的分類效果產(chǎn)生直接的影響，因此，特征選擇一直是文本分類研究的重點(diǎn)。近年來(lái)，隨著智能技術(shù)的迅猛發(fā)展，遺傳算法、蟻群算法和粒子群算法都已經(jīng)應(yīng)用到文本分類中，并取得了較好的成果。文獻(xiàn)[2-3]分別把遺傳算法和粒子群算法應(yīng)用到文本特征選擇中，不僅降低了特征維數(shù)，而且提高了文本的分類性能。文獻(xiàn)[4]用信息增益直接估計(jì)每個(gè)類的特征權(quán)重，進(jìn)而篩選出對(duì)文本分類區(qū)分度大的特征項(xiàng)。文獻(xiàn)[5]采用改進(jìn)的人工魚群算法實(shí)現(xiàn)了數(shù)據(jù)聚類。文獻(xiàn)[6]采用人工魚群算法實(shí)現(xiàn)了對(duì)文本分類器的優(yōu)化，該算法較經(jīng)典支持向量機(jī)算法和基于蟻群算法的直推式支持向量機(jī)算法具有更高的分類性能。文獻(xiàn)[7]采用人工魚群算法選擇出最優(yōu)的特征子集，提高了支持向量機(jī)算法的分類精度。

利用群體智能優(yōu)化算法進(jìn)行特征選擇存在已久，其中，遺傳算法和粒子群算法等經(jīng)典算法均已有成功的應(yīng)用。但是在不同的應(yīng)用場(chǎng)合中，都存在各自不同的缺點(diǎn)。遺傳算法以生物進(jìn)化為原型，具有收斂性好和魯棒性高等優(yōu)點(diǎn)，但是處理文本分類這種高維度的計(jì)算問(wèn)題，容易陷入“早熟”。粒子群算法雖然具有搜索速度快、效率高和算法簡(jiǎn)單等優(yōu)點(diǎn)，但是具有后期全局收斂差的缺點(diǎn)。文獻(xiàn)[8]首次提出了一種基于動(dòng)物自治的優(yōu)化方法，即魚群算法。該算法通過(guò)構(gòu)造人工魚群來(lái)模仿魚群的覓食行為、群聚行為和追尾行為，從而實(shí)現(xiàn)優(yōu)化的目的。本文利用人工魚群算法具有全局收斂性的優(yōu)點(diǎn)，通過(guò)改進(jìn)人工魚群移動(dòng)的3種行為來(lái)改善魚群收斂速度慢和時(shí)間復(fù)雜度高的問(wèn)題。改進(jìn)的人工魚群算法在文本特征選擇中不僅具有良好的全局收斂性能，還具有較快的收斂速度。

1　人工魚群算法在維吾爾文文本特征選擇中的應(yīng)用

采用人工魚群算法對(duì)維吾爾文文本進(jìn)行特征提取的模型如圖1所示。從圖1可以看出：該算法是以類別為單位，對(duì)樣本集中的每一個(gè)類別采用人工魚群算法，計(jì)算出每個(gè)類別各自的特征子集。

1.1文本預(yù)處理

圖1　維吾爾文文本特征提取模型

文本預(yù)處理的主要目的是生成n個(gè)特征池，具體步驟為：

(Ⅰ)維吾爾文組詞計(jì)算。為了使維吾爾文組詞算法具有更高的組全率(組合正確的詞/應(yīng)該被組合的詞)和更低的誤組率(組合錯(cuò)誤的詞/組詞總數(shù))，本文引入了調(diào)解因子α、β，改進(jìn)的維吾爾文組詞算法[10]如下：

(1)

其中：Mi_Pf(a,b)為本文改進(jìn)的組詞方法；MI(a,b)為維吾爾文單詞a和b的互信息值；P(a,b)為詞串a(chǎn)b出現(xiàn)的概率；P(a)和P(b)分別為單詞a和b出現(xiàn)的概率；Pf(a,b)為維吾爾文單詞a和b的頻繁模式匹配值；SWIN(a)·count為單詞a在搜索窗口的匹配值；SWIN(a+b)·count為詞組ab在搜索窗口的匹配值。該組詞算法能有效地提高組全率并降低誤組率，部分組詞實(shí)例如圖2所示。

圖2　維吾爾文組詞實(shí)例

(Ⅱ)特征池的生成。首先，對(duì)經(jīng)過(guò)組詞后的文本進(jìn)行停用詞和低頻詞過(guò)濾；再對(duì)維吾爾文單詞進(jìn)行去重處理；最后，按類別生成相對(duì)應(yīng)的特征池。

1.2改進(jìn)的人工魚群算法

為了簡(jiǎn)化人工魚群算法，提高程序的執(zhí)行效率，本文舍去了算法中對(duì)特征項(xiàng)進(jìn)行編碼的部分，改進(jìn)了人工魚的結(jié)構(gòu)。設(shè)T=[t1,t2,…,tn]為改進(jìn)后的人工魚，其中，ti為特征池中的某一個(gè)特征項(xiàng)，人工魚的n個(gè)變量不能重復(fù)，并且各個(gè)變量是按升序排列的。visual為人工魚的感知距離，其取值為[0,1]，如果兩條人工魚之間相同的變量個(gè)數(shù)大于visual×n，則這兩條魚是相互可見的。Fit=f(X)為目標(biāo)函數(shù)，記錄當(dāng)前人工魚所在位置的食物濃度。tryNum為在覓食行為中人工魚嘗試的次數(shù)。

1.2.1初始人工魚群的產(chǎn)生

初始人工魚群的產(chǎn)生方法有兩種[12-13]：一種是人為給定的初始種群；另一種是隨機(jī)產(chǎn)生的初始種群。本文初始人工魚群個(gè)體的產(chǎn)生方法主要是隨機(jī)產(chǎn)生。初始魚群產(chǎn)生的步驟為：

(Ⅰ)對(duì)特征池中的所有特征從0開始進(jìn)行編號(hào)。

(Ⅱ)假設(shè)每條人工魚由n個(gè)特征構(gòu)成，特征池中有N個(gè)特征項(xiàng)。隨機(jī)生成n個(gè)[0，N-1] 的不重復(fù)整數(shù)。

(Ⅲ)對(duì)這n個(gè)整數(shù)按升序排列。

(Ⅳ)判定新生成的整數(shù)序列是否已經(jīng)存在，如果存在，則重新執(zhí)行步驟Ⅱ和步驟Ⅲ；反之，則成功生成新的人工魚。

1.2.2覓食行為的改進(jìn)

visual?visual+0.1，visual<1。

(2)

如果找到新的狀態(tài)更好，則繼續(xù)增大visual的值，直到嘗試的次數(shù)等于tryNum，則停止覓食行為。

1.2.3群聚行為的改進(jìn)

(3)

1.2.4追尾行為的改進(jìn)

1.2.5適應(yīng)度函數(shù)的設(shè)計(jì)

本文的人工魚群算法是以類別為單位，通過(guò)人工魚的適應(yīng)度值來(lái)衡量與該類別的相似度，即人工魚的適應(yīng)度值越高，則說(shuō)明該人工魚的狀態(tài)越能代表該類的特征子集。因此，適應(yīng)度函數(shù)的設(shè)計(jì)應(yīng)考慮以下兩點(diǎn)：

(Ⅰ)從總體上來(lái)看，采用平均相似度來(lái)衡量人工魚的狀態(tài)與類別的近似程度，其計(jì)算式為：

(4)

其中：sim(Xi,dj)為人工魚Xi與該類別下的第j篇文本的余弦相似度；N為該類別下的文本總數(shù)。

(Ⅱ)從特征項(xiàng)個(gè)體來(lái)看，如果沒有考慮到所選特征間的相關(guān)性，將會(huì)帶來(lái)較大的冗余。為了彌補(bǔ)平均相似度算法的缺點(diǎn)，采用帶懲罰的互信息特征選擇算法來(lái)計(jì)算特征項(xiàng)之間的相關(guān)性，其計(jì)算式為：

(5)

其中：I(C;wj)為人工魚Xi狀態(tài)的j特征與類別C的互信息值；S為預(yù)先選擇好有代表性的少數(shù)特征子集；I(s;wj)為人工魚Xi狀態(tài)的j特征與S集合里的元素s的互信息值；λ為懲罰因數(shù)，當(dāng)λ∈[0.5,1.0]時(shí)，算法效果較好；n為人工魚Xi的維度。

結(jié)合式(4)和式(5)，設(shè)計(jì)出人工魚群算法的適應(yīng)度函數(shù)，其計(jì)算式為:

Fit(Xi)=Sim(Xi)+J(Xi)，

(6)

其中：Sim(Xi)為人工魚的狀態(tài)與類別的平均相似度；J(Xi)為人工魚Xi的內(nèi)部特征相關(guān)性。

1.2.6變異策略的設(shè)計(jì)

1.2.7人工魚群算法的設(shè)計(jì)

改進(jìn)的人工魚群算法的執(zhí)行步驟如下：

(Ⅰ)初始化人工魚群。利用特征池i，隨機(jī)生成N條不重復(fù)的人工魚。同時(shí)在公告板上記錄適應(yīng)度值最高的人工魚。

圖3　改進(jìn)的人工魚群算法執(zhí)行流程

(Ⅱ)魚群移動(dòng)策略。對(duì)魚群中的每條魚都執(zhí)行覓食行為，觀察移動(dòng)后的人工魚是否有進(jìn)步，即人工魚適應(yīng)度值變大。如果有進(jìn)步，則依次執(zhí)行追尾行為和群聚行為；反之，則先執(zhí)行變異策略，然后依次執(zhí)行追尾行為和群聚行為。再觀察人工魚是否有進(jìn)步，如果有進(jìn)步，則更新公告板；反之，再執(zhí)行一次覓食行為，然后再更新公告板。

(Ⅲ)魚群結(jié)束條件。當(dāng)魚群移動(dòng)的次數(shù)達(dá)到了設(shè)定值，則人工魚群算法結(jié)束，并輸出最優(yōu)的人工魚。利用最優(yōu)的人工魚狀態(tài)計(jì)算出所選擇的維吾爾文特征項(xiàng)。

改進(jìn)的人工魚群算法具體執(zhí)行流程如圖3所示。

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

本文實(shí)驗(yàn)中所使用的維吾爾文文本數(shù)據(jù)集均為本實(shí)驗(yàn)室人工收集，數(shù)據(jù)主要來(lái)源于Ulinix網(wǎng)、天山網(wǎng)和新疆政府網(wǎng)等主要維吾爾文門戶網(wǎng)站。文獻(xiàn)[14]指出文本的分類性能受訓(xùn)練集的特征數(shù)、文本數(shù)和類別數(shù)3項(xiàng)數(shù)量指標(biāo)交互影響，在特征數(shù)一定的情況下，各個(gè)類別所包含的文本數(shù)越多，分類性能越好，訓(xùn)練集的類別數(shù)越多，分類性能越差。實(shí)驗(yàn)所需樣本集的描述信息見表1。

實(shí)驗(yàn)采用Java編程語(yǔ)言，eclipse開發(fā)平臺(tái)。采用k最近鄰 (k-nearestneighbor，KNN)分類算法分類器和控制變量法計(jì)算3個(gè)主要參數(shù)對(duì)文本分類的影響。實(shí)驗(yàn)結(jié)果表明：當(dāng)魚群的數(shù)量和迭代次數(shù)較小時(shí)，容易陷入局部最優(yōu)解；但過(guò)大時(shí)，會(huì)提高程序的時(shí)間復(fù)雜度。魚群迭代的次數(shù)呈拋物線狀，當(dāng)?shù)螖?shù)為20時(shí)，對(duì)文本分類的效果最佳。因此，當(dāng)人工魚的維度為100、魚群數(shù)量為80、人工魚的視野取0.7、在覓食過(guò)程中每條人工魚嘗試的次數(shù)為15次、迭代次數(shù)取20時(shí)，人工魚群算法提取出來(lái)的特征最好，能夠使KNN分類器的分類準(zhǔn)確率達(dá)到94.5%。

表1　樣本集的描述信息

為了更好地分析改進(jìn)算法對(duì)分類器性能的影響，本文采用準(zhǔn)確率來(lái)進(jìn)行描述，同時(shí)與當(dāng)前主流的特征選擇算法進(jìn)行了實(shí)驗(yàn)對(duì)比，結(jié)果見表2。

表2　各特征選擇算法的分類準(zhǔn)確率比較 　 %

從表2可以看出：本文提出的改進(jìn)的人工魚群算法比其他幾種特征選擇算法具有更高的分類精度。主要原因?yàn)槿斯~群算法是以尋找出與本文類別最相似的特征子集為尋優(yōu)目的，這樣選取的特征子集能更好地代表該類別。同時(shí)，改進(jìn)的人工魚群算法能達(dá)到良好的全局收斂，其性能優(yōu)于標(biāo)準(zhǔn)人工魚群算法。改進(jìn)的人工魚群算法對(duì)KNN分類器的性能影響最大，其次是貝葉斯分類器，最后是質(zhì)心分類器。

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

基于人工魚群算法的特征選擇方法可選出更能代表該類的特征集，能夠顯著地提高分類器的分類性能，仿真實(shí)驗(yàn)驗(yàn)證此方法具有有效性和可行性。雖然人工魚群算法在理論上已經(jīng)比較成熟，但是在數(shù)據(jù)挖掘和文本分類等領(lǐng)域的應(yīng)用還有很大的研究空間。

[1]蘇金樹,張博峰.基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J].軟件學(xué)報(bào),2006,17(9):1848-1859.

[2]路永和,梁明輝.遺傳算法在改進(jìn)文本特征提取方法中的應(yīng)用[J].現(xiàn)代圖書情報(bào)技術(shù),2014,245(4):48-57.

[3]路永和,曹利朝.基于粒子群優(yōu)化的文本特征選擇方法[J].現(xiàn)代圖書情報(bào)技術(shù),2011(7):76-81.

[4]MALIKH，F(xiàn)RADKIND，MOERCHENF．Singlepasstextclassificationbydirectfeatureweighting[J].Knowledgeandinformationsystems,2011,28(1):79-98.

[5]CHENGYM,JIANGMY,YUANDF.Novelclusteringalgorithmsbasedonimprovedartificialfishswarmalgorithm[C]//ProceedingsoftheSixthInternationalConferenceonFuzzySystemsandKnowledgeDiscovery.2009:141-145.

[6]齊芳,馮昕,徐其江.基于人工魚群優(yōu)化的直推式支持向量機(jī)分類算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(3):294-296.

[7]LINKC,CHENSY,HUNGJC.Featureselectionforsupportvectormachinesbaseonmodifiedartificialfishswarmalgorithm[M]//UbiquitousComputingApplicationandWirelessSensor.Netherlands:Springer,2015:297-304.

[8]李曉磊,邵之江,錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式：魚群算法[J].系統(tǒng)工程理論與實(shí)踐,2002,22(11):32-38.

[9]李敏強(qiáng),哈力旦·阿布都熱依木,閆軻.一種改進(jìn)型局部二值模式的維吾爾文定位算法[J].河南科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,36(3):43-47.

[10]吐爾地·托合提,艾克白爾·帕塔爾,艾斯卡爾·艾木都拉.語(yǔ)義詞特征提取及其在維吾爾文文本分類中的應(yīng)用[J].中文信息學(xué)報(bào),2014,28(4):140-144.

[11]吐爾地·托合提,維尼拉·木沙江,艾斯卡爾·艾木都拉.基于頻繁模式挖掘的維吾爾文智能組詞方法[J].計(jì)算機(jī)應(yīng)用,2012,32(10):2920-2922.

[12]吳昌友,王福林,馬力.一種新的改進(jìn)粒子群優(yōu)化算法[J].控制工程,2010,17(5):359-362.

[13]吳昌友.一種新的改進(jìn)人工魚群優(yōu)化算法[J].智能系統(tǒng)學(xué)報(bào),2015,10(3):1-6.

[14]李湘東,曹環(huán),黃莉.文本分類中訓(xùn)練集相關(guān)數(shù)量指標(biāo)的影響研究[J].計(jì)算機(jī)應(yīng)用研究,2014,33(11):3324-3327.

國(guó)家自然科學(xué)基金項(xiàng)目(61163026)

吳冰冰(1991-),男,四川達(dá)州人,碩士生;哈力旦·阿布都熱依木(1959-),女,維吾爾族,新疆烏魯木齊人,教授,碩士生導(dǎo)師,主要研究方向?yàn)閳D像處理和數(shù)據(jù)挖掘.

2015-11-11

1672-6871(2016)06-0046-05

10.15926/j.cnki.issn1672-6871.2016.06.010

TP391.1

A