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

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

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

?

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

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

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

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

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

0　引言

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

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

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

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

1.1文本預(yù)處理

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

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

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

(1)

其中：Mi_Pf(a,b)為本文改進的組詞方法；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在搜索窗口的匹配值。該組詞算法能有效地提高組全率并降低誤組率，部分組詞實例如圖2所示。

圖2　維吾爾文組詞實例

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

1.2改進的人工魚群算法

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

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

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

(Ⅰ)對特征池中的所有特征從0開始進行編號。

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

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

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

1.2.2覓食行為的改進

visual?visual+0.1，visual<1。

(2)

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

1.2.3群聚行為的改進

(3)

1.2.4追尾行為的改進

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

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

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

(4)

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

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

(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]時，算法效果較好；n為人工魚Xi的維度。

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

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

(6)

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

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

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

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

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

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

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

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

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

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

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

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

表1　樣本集的描述信息

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

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

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

3　結(jié)束語

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

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

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

[3]路永和,曹利朝.基于粒子群優(yōu)化的文本特征選擇方法[J].現(xiàn)代圖書情報技術(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].計算機應(yīng)用與軟件,2013,30(3):294-296.

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

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

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

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

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

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

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

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

國家自然科學(xué)基金項目(61163026)

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

2015-11-11

1672-6871(2016)06-0046-05

10.15926/j.cnki.issn1672-6871.2016.06.010

TP391.1

A