改進二進制麻雀搜索的特征選擇及文本聚類

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

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

0 引言

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

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

1 相關研究

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

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

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

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

2 算法詳細設計

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

2.1 構建基于矢量空間模型VSM的文本表示模型

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

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

(1)

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

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

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

2.2.1 特征選擇模型

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

2.2.2 解的表示

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

(2)

2.2.3 適應度函數

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

(3)

(4)

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

傳統的麻雀搜索算法SSA主要是用于解決連續型優化問題的元啟發式算法,而文本特征選擇是一種求解離散優化的問題。本節主要介紹麻雀搜索算法、離散化技術以及用于求解特征選擇問題的改進麻雀搜索算法IBSSA。

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

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

(5)

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

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

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

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

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

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

(7)

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

(8)

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

(9)

(10)

2.3.2 改進隨機游走策略

當二進制麻雀搜索算法迭代進入停滯狀態導致種群無法獲取最優適應度值時,隨機游走策略可以通過對二進制麻雀種群中最優麻雀個體的擾動,幫助算法跳出局部最優解。基于隨機游走策略改進的最優麻雀個體的更新公式如式(11)所示。

(11)

算法：隨機游走策略

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

2.cur_iter #當前迭代的次數

3.Initial PI with cur_iter

4.lb=lb/PI

5.ub=ub/PI

6.forjin range (Dim):# Dim對應搜索的維數

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

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

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

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

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

17.end if

18.end for

傳統隨機游走算法中,步長A的公式如下。

Aij=2*(Randij>0.5)-1

(12)

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

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

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

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

(13)

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

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

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

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

3 實驗對比及分析

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

3.1 算法性能分析

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

(14)

(15)

(16)

(17)

(18)

(19)

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

圖2展示了5種優化算法在6個基準函數上的收斂曲線,橫坐標表示優化算法迭代次數,縱坐標為算法所對應的適應度值。

圖2 不同算法在基準函數的收斂曲線

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

3.2 測試文本數據集

采用表1所示的5種基準文本數據集進行實驗,測試基于二進制麻雀搜索算法IBSSA的特征選擇算法的性能。該算法是基于滾動方向機制的隨機游走策略及圓周方向搜索機制改進發現者的麻雀搜索算法RW-DBO-SSA經轉移函數TF轉換所得,適用于解決特征選擇問題?；鶞饰谋緮祿捎嬎阒悄軐嶒炇襆ABIC提供。數據集包括:文本數量、文本特征數、聚類數。對比算法選擇基于粒子群的特征選擇及文本聚類算法PSO-FS和基于遺傳算法的特征選擇及文本聚類算法GA-FS,以及未使用任何文本特征選擇方法的k-means++ 算法。

表1 測試文檔數據集

3.3 算法評估指標

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

1) 查準率P

(20)

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

2) 查全率R

(21)

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

3)F度量

F-measure可用于度量聚類結果的性能,其結果為查準率和查全率的調和平均值。

(22)

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

(23)

式中:n為文檔總量。

4) 準確率

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

(24)

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

5) 特征數量

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

6) 收斂性

該指標用來評估算法對有效特征的尋優能力及速度。

3.4 實驗分析

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

圖3 特征縮減率

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

圖4 算法收斂時間

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

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

圖5 不同算法在5種數據集上的收斂性曲線

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

4 結論

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