高新成,邵國銘,張海洋,周中雨

(1.東北石油大學(xué) 現(xiàn)代教育技術(shù)中心, 黑龍江 大慶 163318;2.東北石油大學(xué) 計算機與信息技術(shù)學(xué)院, 黑龍江 大慶 163318)

0 引言

文本聚類是一種無監(jiān)督學(xué)習(xí)的文本挖掘技術(shù),其目的是將距離相近的文本聚類到相同的目標(biāo)簇中[1]。因此,文本聚類被廣泛地應(yīng)用到網(wǎng)頁挖掘、垃圾郵件過濾、新聞文本聚類等領(lǐng)域[2]。矢量空間模型(vector space model,VSM)作為常用的文本表示模型,可以將文本構(gòu)建成對應(yīng)的詞條權(quán)重向量,用以計算文本間的相似度。由此,文本聚類的效果受到特征維數(shù)以及特征子集冗余性等因素的影響[3]。文本特征包含有效特征和無效特征。其中,無效特征包含噪聲或冗余特征。文本特征選擇的目標(biāo)是通過篩選無效特征選取最優(yōu)特征子集,使文本聚類效果最佳。傳統(tǒng)特征選擇方法存在難以改進以及特征選擇精度較低等問題。

本文中設(shè)計了一種結(jié)合蜣螂優(yōu)化算法DBO[4]改進二進制麻雀搜索算法的特征選擇及文本聚類算法。將麻雀的位置信息建模成文本特征,各麻雀的適應(yīng)度值建模為特征子集的評價指標(biāo),引入蜣螂優(yōu)化算法中圓周方向搜索機制改進麻雀發(fā)現(xiàn)者的位置更新策略,同時融合滾動方向機制的隨機游走策略提升麻雀全局搜索能力,選取最優(yōu)文本特征子集。在文本特征選擇最優(yōu)解的基礎(chǔ)上,選用k-means++聚類算法,得到最優(yōu)文本聚類結(jié)果。通過標(biāo)準(zhǔn)文本數(shù)據(jù)集及評價指標(biāo)對比,最終驗證算法的有效性和可行性。

1 相關(guān)研究

目前常用的特征選擇方法主要有以下3種:過濾式(filter)、封裝式(wrapper)和嵌入式(embedded)。其中,過濾式特征選擇方法[5]未考慮與學(xué)習(xí)算法結(jié)合,本質(zhì)上是一種數(shù)學(xué)統(tǒng)計分析法。封裝式特征選擇算法結(jié)合了學(xué)習(xí)算法,并利用相應(yīng)的搜索策略選取最優(yōu)特征子集。嵌入式方法將特征選擇與學(xué)習(xí)算法結(jié)合成一體,在訓(xùn)練階段已經(jīng)完成了特征選擇工作。

近年來,元啟發(fā)式算法被廣泛應(yīng)用到各個領(lǐng)域以解決優(yōu)化問題[6],包括醫(yī)療領(lǐng)域、環(huán)保領(lǐng)域及農(nóng)業(yè)領(lǐng)域等。在文本挖掘領(lǐng)域中,Janani等[7]提出了基于粒子群算法的文本聚類算法,利用常見的文本數(shù)據(jù)集進行實驗。許召召等[8]提出了融合信息增益比和遺傳算法的混合特征選擇算法,并利用信息增益比的過濾式算法進行特征初選,再利用遺傳算法對特征進行優(yōu)化。張陽等[9]提出了一種基于word2vec和高維生物基因選擇遺傳算法的文本特征選擇算法。王琛等[10]將灰狼覓食的過程模擬成特征選擇的過程,利用k-means算法完成文本聚類。Bae等[11]提出了一種基于和聲搜索算法的特征選擇方法,在聚類的準(zhǔn)確率和精確率上有良好的效果。羅子淦[12]在二進制粒子群優(yōu)化算法的基礎(chǔ)上引入學(xué)習(xí)因子等改進策略,有效縮減了特征數(shù)量。

由此,使用元啟發(fā)式算法可以有效地進行特征選擇,而傳統(tǒng)智能優(yōu)化算法存在尋優(yōu)能力不佳及收斂速度較慢等問題,即使與過濾式特征選擇算法相結(jié)合,其提升效果也不是很明顯。麻雀搜索算法[13]是一種新型智能優(yōu)化算法,優(yōu)點是收斂速度快,算法參數(shù)少且適用于求解大規(guī)模問題。研究表明,麻雀搜索算法的尋優(yōu)能力優(yōu)于PSO[14]、GA[15]和灰狼[16]等優(yōu)化算法,已被廣泛地應(yīng)用在電力系統(tǒng)、圖像處理及網(wǎng)絡(luò)安全等領(lǐng)域。

雖然麻雀搜索算法(SSA)在多個優(yōu)化問題上表現(xiàn)優(yōu)秀,但在處理大規(guī)模離散優(yōu)化問題,例如特性選擇時,SSA存在一些明顯的局限性。具體來說,由于SSA最初被設(shè)計用于處理連續(xù)問題,因此其在處理離散問題時,存在收斂速度較慢及尋優(yōu)精度低的問題,有時可能陷入局部極值。此外,SSA的發(fā)現(xiàn)者位置更新公式具有較大的隨機性,雖然在搜索初期有助于全局搜索并防止算法陷入局部最優(yōu),但在搜索的后期,這種隨機性會阻礙算法進行更精細(xì)的局部搜索,進一步影響尋優(yōu)精度和速度。針對這些局限性和挑戰(zhàn),本文結(jié)合蜣螂優(yōu)化算法DBO,提出了改進的二進制麻雀搜索算法(IBSSA),旨在提升麻雀搜索算法在大規(guī)模離散問題上的尋優(yōu)效率和精度。

2 算法詳細(xì)設(shè)計

傳統(tǒng)的麻雀搜索算法主要被用來解決連續(xù)型優(yōu)化問題,而特征選擇[17]是一種離散優(yōu)化問題。本文將通過二進制麻雀搜索算法實現(xiàn)文本的特征選擇,在去除冗余特征的最優(yōu)子集基礎(chǔ)上,進行文本聚類分析。算法主要分為3個階段:第一階段進行文本預(yù)處理及構(gòu)建矢量空間模型VSM。第二階段利用改進的二進制麻雀搜索算法進行文本特征選擇,得到最優(yōu)文本特征子集。第三階段在最優(yōu)文本特征子集基礎(chǔ)上,利用k-means++實現(xiàn)文本聚類。

2.1 構(gòu)建基于矢量空間模型VSM的文本表示模型

在進行文本特征選擇之前,需要對文本進行預(yù)處理,將其表示為矢量空間模型VSM[18]。其中包括分詞、去停用詞、提取詞干及計算詞條權(quán)重。分詞的主要操作是根據(jù)標(biāo)點符號和空格,將初始文本分割成單獨的詞條。去停用詞是將文本中出現(xiàn)頻率較高但其權(quán)重值較小的詞語進行移除,減少其對聚類結(jié)果的影響。提取詞干操作是通過去除詞匯的前綴與后綴并將詞匯轉(zhuǎn)換為相同詞根的過程。其中,相同詞根被定義為文本的同一個特征。詞條權(quán)重計算是根據(jù)特征詞條在不同文檔中出現(xiàn)的頻率,計算其對應(yīng)的權(quán)重值。特征詞條出現(xiàn)的頻率越高,詞條在文檔中越重要,其擁有的權(quán)重值越大。目前常用的特征詞條計算方法為詞頻-逆文檔頻率TF-IDF,具體公式如下。

wi, j=TF(i,j)×IDF(i,j)=

(1)

式中:wi, j為文檔i中特征詞條j的權(quán)重值;TF(i,j)為文檔i中特征詞條j出現(xiàn)的頻率;n為文檔總數(shù);DF(j)為包含詞條j的文檔數(shù)量;IDF(i,j)為逆文檔頻率,最終構(gòu)建矢量空間模型VSM。

2.2 基于二進制麻雀搜索算法的特征選擇策略

麻雀搜索算法是受到麻雀捕食及反捕食的啟發(fā)而提出的種群智能優(yōu)化算法。它將麻雀的覓食過程抽象為擁有預(yù)警機制的麻雀發(fā)現(xiàn)者以及麻雀加入者模型。在每次迭代搜索前,算法通過計算適應(yīng)度值的大小,將麻雀分為發(fā)現(xiàn)者和加入者。發(fā)現(xiàn)者為麻雀種群尋找食物來源,加入者跟隨發(fā)現(xiàn)者尋找食物,發(fā)現(xiàn)者和加入者之間可以相互轉(zhuǎn)換。在覓食過程中,部分麻雀被選作偵察者以及時發(fā)現(xiàn)危險。

2.2.1 特征選擇模型

在機器學(xué)習(xí)與數(shù)據(jù)挖掘領(lǐng)域中,特征選擇的目標(biāo)是在保持原始特征較高準(zhǔn)確性的前提下,選取樣本的最優(yōu)特征子集。假定初始文本特征集合為F,其可以表示為Fi={fi,1,fi,2,…,fi, j,…,fi,n},其中Fi為文檔i的特征集合,n為特征數(shù)量。令FS為特征選擇之后得到的最優(yōu)特征子集,表示為:FSi={fsi,1,fsi,2,…,fsi, j,…,fsi,m},其中m為特征選擇后新的特征長度,fsi, j={0,1},j=1,2,…,m。當(dāng)fsi, j=1時,文檔i中選取的特征j為有效特征;當(dāng)fsi, j=0時,文檔i中特征j為無效冗余特征。

2.2.2 解的表示

在使用二進制麻雀搜索算法進行文本特征選擇時,每只麻雀在搜索空間中的位置代表一個文檔的特征子集。將一只麻雀s的位置表示為矩陣Xs,則Xs可表示為:

(2)

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

元啟發(fā)式算法的適應(yīng)度函數(shù)主要是用來評估麻雀位置所代表的特征選擇解的適應(yīng)度值。特征詞權(quán)重是衡量文本聚類的重要指標(biāo),權(quán)重越高的特征對聚類的影響越大。平均絕對差MAD可用于衡量文本特征子集的穩(wěn)定性與一致性。本文從文本特征權(quán)重角度出發(fā),通過計算麻雀所選特征子集上下文特征權(quán)重的平均絕對差MAD,將其作為特征選擇的適應(yīng)度函數(shù),使其具備衡量文本特征價值的能力,其公式如下。

(3)

(4)

2.3 改進二進制麻雀搜索算法

傳統(tǒng)的麻雀搜索算法SSA主要是用于解決連續(xù)型優(yōu)化問題的元啟發(fā)式算法,而文本特征選擇是一種求解離散優(yōu)化的問題。本節(jié)主要介紹麻雀搜索算法、離散化技術(shù)以及用于求解特征選擇問題的改進麻雀搜索算法IBSSA。

2.3.1 二進制麻雀個體更新策略

傳統(tǒng)麻雀搜索算法中的發(fā)現(xiàn)者指的是具有較高適應(yīng)度值的一部分麻雀,其位置更新如式(5)所示。

(5)

式中:xi, j為麻雀i在j維上的位置信息,1≤i≤N, 1≤j≤D;t為當(dāng)前迭代次數(shù);α∈(0,1];M為最大迭代次數(shù);R2∈[0,1],表示麻雀的預(yù)警值;ST∈[0.5,1],表示麻雀的安全值;Q為服從標(biāo)準(zhǔn)正態(tài)分布的隨機數(shù);L為1×D的全1矩陣。當(dāng)R2

傳統(tǒng)麻雀發(fā)現(xiàn)者公式雖然簡單易行,有助于跳出局部最優(yōu)解,但是其在搜索空間中的移動缺乏方向性,隨機移動雖然能避免局部最優(yōu),但其也可能使得算法在搜索過程中偏離全局最優(yōu)區(qū)域,其移動距離Q·L也是隨機的。算法可能在一次迭代中移動很大的距離,而在另一次迭代中只移動很小的距離。這種不穩(wěn)定性可能會對算法的收斂性產(chǎn)生負(fù)面影響,且其移動主要基于當(dāng)前位置和隨機數(shù),卻忽略了過去的搜索歷史。因此,它無法有效地利用過去的搜索經(jīng)驗來引導(dǎo)算法進一步搜索。

為了解決麻雀發(fā)現(xiàn)者在搜索空間中移動時缺乏方向性及移動距離不穩(wěn)定的問題,引入一種基于圓周搜索的機制。通過結(jié)合蜣螂優(yōu)化算法,圓周方向搜索機制對麻雀發(fā)現(xiàn)者進行改進后的位置更新策略如式(6)所示。

式中:r是圓周半徑隨機數(shù),表示一個隨機距離,取值范圍為 (0,1);θ是一個隨機角度,表示在一個單位圓上選擇一個隨機方向,取值范圍為 (0,2π);[cos(θ),…,sin(θ)]為一個dim維的位移向量,dim對應(yīng)特征選擇解的維度。若R2

基于圓周搜索機制改進的麻雀發(fā)現(xiàn)者利用[cos(θ),…,sin(θ)]使得算法在搜索空間中的移動有一定的方向性,可以更好地控制搜索方向,避免算法過于隨機地在搜索空間中移動?；趫A周搜索機制,引入圓周半徑因子r可以更好地控制搜索距離,保證算法在每次迭代中的移動距離在一定范圍內(nèi),提高算法的穩(wěn)定性,更好地利用先前搜索經(jīng)驗引導(dǎo)搜索過程。

麻雀搜索算法中的加入者指的是具有較低適應(yīng)度的大部分麻雀,其位置更新如式(7)所示。

(7)

麻雀警戒者主要由麻雀種群隨機選取產(chǎn)生,一般選取15%左右的麻雀作為警戒者,其位置更新如式(8)所示。

(8)

轉(zhuǎn)移函數(shù)TF是一種可以按一定概率將實數(shù)轉(zhuǎn)換為0或1的方法。本文借鑒Agrawal等[19]提出的基于改進二進制優(yōu)化算法的公式,將傳統(tǒng)麻雀搜索算法改進為解決離散特征選擇問題的二進制麻雀搜索算法,其公式如下。

(9)

(10)

2.3.2 改進隨機游走策略

當(dāng)二進制麻雀搜索算法迭代進入停滯狀態(tài)導(dǎo)致種群無法獲取最優(yōu)適應(yīng)度值時,隨機游走策略可以通過對二進制麻雀種群中最優(yōu)麻雀個體的擾動,幫助算法跳出局部最優(yōu)解?；陔S機游走策略改進的最優(yōu)麻雀個體的更新公式如式(11)所示。

(11)

算法：隨機游走策略

1.PI#根據(jù)參數(shù)PI改變上下界ub、lb的范圍,迭代次數(shù)越大,范圍越小,用以調(diào)整搜索范圍。

2.cur_iter #當(dāng)前迭代的次數(shù)

3.Initial PI with cur_iter

4.lb=lb/PI

5.ub=ub/PI

6.forjin range (Dim):# Dim對應(yīng)搜索的維數(shù)

7.ai, j:確定每一個維度的搜索下界

8.bi, j:確定每一個維度的搜索上界

11.生成一個步長A:[-1,1]之間

13.更新第j個維度的位置

14.{xmin,xmax}:[-1,1]

17.end if

18.end for

傳統(tǒng)隨機游走算法中,步長A的公式如下。

Aij=2*(Randij>0.5)-1

(12)

式中:Randij是在[0,1)間均勻分布的隨機數(shù)。

傳統(tǒng)隨機游走算法步長的生成完全隨機,沒有考慮到搜索過程中的方向性,導(dǎo)致搜索過程可能過于單一,不能充分探索搜索空間。搜索結(jié)果可能在正負(fù)方向上來回振蕩,效率較低。

本文中提出了一種改進的步長生成方法,即引入了一個滾動方向因子direction,用于決定搜索方向。步長A的改進公式為:

Aij=direction*(2*(Randomij>0.5)-1)

(13)

式中:direction是 {-1,1} 中隨機選取的值。引入滾動方向機制后,算法搜索更有可能沿著某個方向進行,減少了在正負(fù)方向上的振蕩。并且,由于滾動方向因子是隨機選擇的,搜索的全局性依然能得到保證,不會因為引入方向因子而導(dǎo)致搜索能力下降。

本節(jié)中提出了改進的二進制麻雀搜索算法(IBSSA)。首先,通過轉(zhuǎn)移函數(shù)TF將傳統(tǒng)麻雀搜索算法改進為解決特征選擇問題的二進制麻雀搜索算法BSSA。其次,傳統(tǒng)麻雀發(fā)現(xiàn)者存在缺乏方向性等問題,通過引入圓周搜索機制,使得算法在特征選擇搜索空間中的移動具有一定的方向性,同時能夠更好地控制搜索距離,提高算法的穩(wěn)定性。再次,在二進制麻雀搜索算法基礎(chǔ)上引入傳統(tǒng)隨機游走策略雖然在一定程度上有助于特征選擇時跳出局部最優(yōu)解,但其存在步長缺乏方向性等問題,通過引入滾動方向因子,可以使得搜索結(jié)果更有可能沿著某一方向進行,有利于算法減少正負(fù)方向震蕩,提高搜索效率。

圖1為改進二進制麻雀搜索的特征選擇及文本聚類整體流程。該流程主要分為3個關(guān)鍵階段:左側(cè)為整體流程第一階段,首先將原始文檔數(shù)據(jù)進行預(yù)處理,包括清洗、標(biāo)準(zhǔn)化和分詞等操作,然后構(gòu)建特征詞條并計算基于TF-IDF的詞條權(quán)重,最后生成矢量空間模型(VSM)。該階段為后續(xù)的特征選擇和文本聚類建立了基礎(chǔ)的數(shù)據(jù)表示。第二階段,應(yīng)用改進的二進制麻雀搜索算法進行特征選擇。在傳統(tǒng)的二進制麻雀搜索算法基礎(chǔ)上,引入基于圓周搜索的麻雀發(fā)現(xiàn)者更新策略和融合滾動方向因子的隨機游走改進策略以改善特征選擇的效率和穩(wěn)定性。此外,采用基于平均絕對差(MAD)的適應(yīng)度函數(shù)對搜索過程進行引導(dǎo),以確保尋找的特征子集能夠最大化聚類性能。第三階段,在尋找的最優(yōu)特征子集基礎(chǔ)上,利用k-means++算法進行文本聚類,得到最終聚類結(jié)果。

圖1 特征選擇及文本聚類流程框圖

3 實驗對比及分析

通過基準(zhǔn)函數(shù)驗證了結(jié)合蜣螂優(yōu)化算法DBO改進的麻雀搜索算法的優(yōu)化性能,并使用改進的二進制麻雀搜索算法IBSSA對文本數(shù)據(jù)進行特征選擇,迭代尋找有效特征的最優(yōu)特征子集。最終,使用k-means++算法對最優(yōu)特征子集進行聚類,并通過計算多個評價指標(biāo),觀察基于二進制麻雀搜索算法特征選擇后的文本聚類結(jié)果性能。

3.1 算法性能分析

為驗證結(jié)合蜣螂優(yōu)化算法DBO改進的麻雀搜索算法的優(yōu)化性能,參考孫林等[20]的實驗方法,選取6個基準(zhǔn)函數(shù),如式(14)—式(17)所示。其中,F1—F4為單峰函數(shù)。單峰函數(shù)可用于測試優(yōu)化算法的局部搜索能力及收斂速度。F5—F6為多峰函數(shù),對應(yīng)式(18)—式(19),多峰函數(shù)可用于測試算法的全局搜索能力及跳出局部最優(yōu)的能力。選取的基準(zhǔn)函數(shù)分別對粒子群算法PSO、遺傳算法GA、原始麻雀搜索算法SSA、基于傳統(tǒng)隨機游走策略的麻雀搜索算法RWSSA、融入滾動方向機制的隨機游走策略、圓周方向搜索機制改進發(fā)現(xiàn)者的麻雀搜索算法RW-DBO-SSA 5種算法進行對比實驗。為確保實驗結(jié)果的公平性,所有優(yōu)化算法的參數(shù)均保持一致,種群數(shù)為30、空間維度20、最大迭代次數(shù)100,所有算法均運行20次。實驗環(huán)境為Windows 10、CPU Intel i7 和8 GB內(nèi)存,算法使用python編寫。

(14)

(15)

(16)

(17)

(18)

(19)

式中:單峰函數(shù)F1—F4對應(yīng)搜索空間輸入范圍為[-100,100],最優(yōu)值為0。雙峰函數(shù)F5對應(yīng)搜索空間輸入范圍為[-5.12,5.12],F6對應(yīng)搜索空間輸入范圍為[-32,32],最優(yōu)值均為0。

圖2展示了5種優(yōu)化算法在6個基準(zhǔn)函數(shù)上的收斂曲線,橫坐標(biāo)表示優(yōu)化算法迭代次數(shù),縱坐標(biāo)為算法所對應(yīng)的適應(yīng)度值。

圖2 不同算法在基準(zhǔn)函數(shù)的收斂曲線

由圖2(a)—圖2(d)可知,求解本節(jié)中4種單峰函數(shù)時,RW_DBO_SSA算法的尋優(yōu)精度及收斂速度優(yōu)于其他4種優(yōu)化算法。由圖2(e)和圖2(f)可知,在求解多峰函數(shù)問題時,RW_DBO_SSA算法相比其他4種優(yōu)化算法具有更優(yōu)的全局搜索能力及收斂性能。綜上,結(jié)合蜣螂優(yōu)化算法的滾動方向機制優(yōu)化隨機游走策略和圓周方向搜索機制改進麻雀發(fā)現(xiàn)者策略得到的改進麻雀搜索算法有較好的收斂速度及尋優(yōu)能力。

3.2 測試文本數(shù)據(jù)集

采用表1所示的5種基準(zhǔn)文本數(shù)據(jù)集進行實驗,測試基于二進制麻雀搜索算法IBSSA的特征選擇算法的性能。該算法是基于滾動方向機制的隨機游走策略及圓周方向搜索機制改進發(fā)現(xiàn)者的麻雀搜索算法RW-DBO-SSA經(jīng)轉(zhuǎn)移函數(shù)TF轉(zhuǎn)換所得,適用于解決特征選擇問題。基準(zhǔn)文本數(shù)據(jù)集由計算智能實驗室LABIC提供。數(shù)據(jù)集包括:文本數(shù)量、文本特征數(shù)、聚類數(shù)。對比算法選擇基于粒子群的特征選擇及文本聚類算法PSO-FS和基于遺傳算法的特征選擇及文本聚類算法GA-FS,以及未使用任何文本特征選擇方法的k-means++ 算法。

表1 測試文檔數(shù)據(jù)集

3.3 算法評估指標(biāo)

采用準(zhǔn)確率Accuracy(Acc)、查準(zhǔn)率Precision(P)、查全率Recall(R)和F度量F-measure(F)作為評估聚類效果的方法。此外,為進一步驗證基于二進制麻雀搜索的特征選擇算法的性能,引入特征數(shù)量縮減率和適應(yīng)度值收斂性2個指標(biāo)。

1) 查準(zhǔn)率P

(20)

式中:ni, j為聚類j中屬于分類i的成員數(shù)量;nj為聚類j的成員數(shù)量。

2) 查全率R

(21)

式中:ni, j為聚類j中屬于分類i的成員數(shù)量;ni為聚類i的成員數(shù)量。

3)F度量

F-measure可用于度量聚類結(jié)果的性能,其結(jié)果為查準(zhǔn)率和查全率的調(diào)和平均值。

(22)

式中:P(i,j)為聚類j中分類i的查準(zhǔn)率;R(i,j)為聚類j中分類i的查全率。所有聚類的F度量為:

(23)

式中:n為文檔總量。

4) 準(zhǔn)確率

準(zhǔn)確率Accuracy是用來計算真實文檔被分為正確類別的比例,如式(24)所示。

(24)

式中:P(i,j)為聚類j中分類i的查準(zhǔn)率;K為聚類總數(shù);n為文檔總數(shù)。

5) 特征數(shù)量

該評估指標(biāo)表示基于改進二進制麻雀搜索算法后,得到的有效特征數(shù)量,特征的有效選取對于文本聚類的性能和準(zhǔn)確度具有重要的影響。特征數(shù)量的優(yōu)化和選擇是一項關(guān)鍵指標(biāo)。

6) 收斂性

該指標(biāo)用來評估算法對有效特征的尋優(yōu)能力及速度。

3.4 實驗分析

圖3是5種測試數(shù)據(jù)集使用遺傳算法、粒子群算法、二進制麻雀搜索算法以及改進的二進制麻雀搜索算法得到的特征縮減率的情況。其中,遺傳算法的特征縮減率在45%～55%,相對較差。粒子群算法的特征縮減率在50%～65%,表現(xiàn)一般。二進制麻雀搜索算法的特征縮減率在65%～75%,表現(xiàn)較好。改進的二進制麻雀搜索算法的特征縮減率在70%～75%,相對其他3種算法,改進的二進制麻雀搜索算法可以更好地降低無效特征,說明改進的二進制麻雀搜索算法在求解特征選擇問題上是有效可行的。

圖3 特征縮減率

圖4是4種優(yōu)化算法在完成特征選擇后的收斂時間,相比粒子群算法以及遺傳算法,二進制麻雀搜索算法的收斂時間較短,迭代完成速度較快。改進的二進制麻雀算法的收斂時間優(yōu)于傳統(tǒng)二進制麻雀搜索算法,其迭代速度最優(yōu)。

圖4 算法收斂時間

圖4也表明,在進行文本特征選擇時,算法的運行時間與文本的特征數(shù)量及文檔數(shù)量密切相關(guān),文檔數(shù)越多,特征數(shù)量也越多,算法進行特征選擇的時間越長。

圖5是5種測試文本數(shù)據(jù)集特征選擇收斂性曲線,由式(3)計算適應(yīng)度值,并通過若干次迭代,選取其最優(yōu)適應(yīng)度值。由圖5可知,二進制麻雀搜索算法在迭代300次時收斂,較粒子群算法以及遺傳算法收斂速度更快。改進的二進制麻雀搜索算法相比傳統(tǒng)二進制麻雀算法有更好的適應(yīng)度值,表明其更好的收斂速度及尋優(yōu)能力。

圖5 不同算法在5種數(shù)據(jù)集上的收斂性曲線

表2是4種優(yōu)化算法在5種文本數(shù)據(jù)集上測試得到的聚類準(zhǔn)確率、查準(zhǔn)率、查全率和F度量值。其中,k-means++算法的聚類指標(biāo)相對較低,主要原因是文本中存在大量無效冗余特征,k-means++算法沒有使用任何特征選擇機制。由PSO-FS及GA-FS的聚類結(jié)果可知,經(jīng)過傳統(tǒng)元啟發(fā)式算法進行特征選擇后,文本聚類的性能得到了提高。表2中, BSSA-FS相比傳統(tǒng)優(yōu)化算法,聚類性能得到進一步提升。IBSSA-FS在前4個文本數(shù)據(jù)集中,聚類性能最優(yōu),這表明改進的二進制麻雀搜索算法具有較好的尋優(yōu)能力,可以有效地進行文本特征選擇任務(wù)。

4 結(jié)論

針對文本中存在無效冗余特征導(dǎo)致文本聚類性能較低等問題,提出了結(jié)合蜣螂優(yōu)化算法改進二進制麻雀搜索算法的特征選擇及文本聚類算法,引入了蜣螂優(yōu)化算法中圓周方向搜索機制和滾動方向機制,對麻雀發(fā)現(xiàn)者位置及隨機游走中步長公式進行改進。針對文本數(shù)據(jù)集,首先對其進行預(yù)處理,利用特征詞權(quán)重作為目標(biāo)函數(shù),選取最優(yōu)特征子集。對于麻雀搜索算法不能解決離散問題,結(jié)合轉(zhuǎn)移函數(shù)對麻雀的位置進行更新,利用改進的二進制麻雀搜索算法進行文本特征選擇。最終,改用k-means++聚類算法對選取的最優(yōu)特征子集進行聚類。實驗結(jié)果表明,提出的改進二進制麻雀搜索算法能夠選取有效特征,較好地提高文本聚類的性能。