改進灰狼優化算法的K-Means文本聚類

潘成勝，張 斌，呂亞娜，杜秀麗，邱少明

大連大學 通信與網絡重點實驗室，遼寧 大連116622

隨著大數據時代的不斷推進，各類文字信息充斥于人們視野中，但其中有用的信息不易被發現，聚類方法憑借其聚類速度快、效果明顯等優點廣泛應用于文本信息挖掘[1-2]。文本聚類的目的是將非結構化的文本數據分成多個類簇，其中同類簇文本相似度高，不同類簇文本相似度低[3]。K-Means 算法作為最經典的聚類算法，在文本聚類中應用廣泛；但K-Means 算法也存在局限性，如對初始聚類中心要求過高，算法易收斂到局部最小值等，以致文本聚類結果不可靠[4-6]。

研究人員對K-Means 文本聚類算法作了改進，如：文獻[7]將粒子群算法與K-Means 算法結合進行文本文檔聚類分析，改善了K-Means算法的文本聚類效果不佳的缺陷；文獻[8]使用核函數對K-Means 算法進行改進，并對改進后的K-Means算法進行文本聚類劃分，改善了傳統K-Means算法的部分缺點；文獻[9]對詞語間的相似性計算進行了修正，來改進K-Means 算法，具有一定的文本聚類效果；文獻[10]使用密度峰值對K-Means 算法優化進行文本聚類，但是未從本質上解決K-Means算法容易陷入局部最優的問題，致使文本聚類效果可靠性降低。

Mirjalili等[11]在2014年提出了灰狼優化（Grey Wolf Optimizer，GWO）算法作為一種新型的群智能算法，較粒子群算法、蝙蝠算法等有更優秀的收斂速度與搜索能力，部分研究人員也將GWO 算法與K-Means 算法結合進行聚類分析：文獻[12]開發了一種基于GWO 算法的聚類算法來提高聚類性能；文獻[13]提出了一種具有Powell 局部優化的GWO 聚類算法，在多數數據集上優于其他算法。文獻[14]和文獻[15]將GWO 算法和KMeans相結合，以解決K-Means算法全局搜索能力不足的問題。已有GWO算法聚類算法都是采用UCI數據集進行仿真驗證，但在文本聚類應用上效果未知。

目前，在文本聚類上應用上，部分文章對K-Means算法的改進雖然取得了一定的效果，但K-Means算法在文本聚類過程中仍存在無法跳出局部最優解的問題，造成文本聚類結果不可靠。部分文章將GWO 算法與K-Means算法結合進行聚類分析，針對的都是標準數值型數據集，未在文本聚類實驗中進行驗證。基于以上問題，本文將從以下方面進行K-Means算法在文本聚類上的改進：（1）在GWO 算法迭代過程中，對灰狼種群中的精英個體（適應度較好的個體）進行克隆和變異，對精英個體進行深度挖掘，提高GWO算法的深度探索能力，避免GWO算法早熟收斂現象的發生；（2）為了擴大精英個體自身領域的獵物搜索范圍，發揮精英個體的剩余價值，將粒子群算法單體位置更新思想與原灰狼位置更新進行結合，充分發揮灰狼精英種群的優勢，避免GWO算法陷入局部極值；（3）將改進后的GWO 算法與經典KMeans算法結合，以解決K-Means算法容易陷入局部最優的問題。同時將該算法應用于文本聚類分析中，采用余弦距離相似性計算文本樣本間的相似性，并通過網絡爬蟲得到的文本數據集將本文算法與已有算法進行準確率、召回率以及F值的仿真對比，來驗證所提算法的有效性。

1 基于免疫克隆與粒子群位置更新的灰狼優化算法

1.1 灰狼優化算法（GWO）

GWO算法是對灰狼種群中的社會等級制度和捕食行為的數學表達。GWO 算法的等級制度共分為4 個，即α、β、δ和ω狼。設種群大小為N的灰狼種群為：X={x1,x2,…,xN}。將灰狼種群中候選解的最好值作為α狼，第二優值作為β狼，第三優值作為δ狼，其余的候選解決方案被設定為ω狼。在GWO 算法中，由α、β、δ狼作為領導者在規定范圍內進行最優解搜索，而ω狼在這3只狼的領導下進行位置更新。GWO算法數學模型如下。

在灰狼搜索獵物過程中，每只狼與獵物之間的距離可以用公式（1）表示：

其中，Xp(t)代表獵物的位置向量；X(t)代表灰狼的位置向量；D代表灰狼與獵物間的距離向量；t代表迭代次數。其中，系數A和C的計算公式分別如下：

其中，在包圍過程中a的值從2線性減少到0，并r1與r2是[0，1]內的隨機向量。

灰狼具有判斷獵物位置并和包圍獵物的能力。保存α、β、δ狼為在種群中獲得的前3個最佳解決方案，并迫使其他搜索代理（ω狼）根據α、β、δ狼的位置更新其位置。其他搜索代理與α、β、δ狼距離可以由公式（5）表示：

得到每只狼的距離之后，通過公式（6）和（7）更新灰狼個體的位置：

GWO 算法雖然有較強的搜索能力，但隨迭代次數的上升，種群多樣性在不斷降低，個體間差異越來越小，無法在搜索空間中找到最優值，可能出現過早收斂現象，影響GWO算法的求解性能。因此，基于免疫克隆理論與粒子群位置更新思想來改進GWO 算法，免疫克隆操作從種群中選出精英個體，并對其進行克隆變異操作，增加種群多樣性，避免算法出現過早收斂現象；然后引入單個灰狼個體的位置變化思想，對灰狼位置的變化增加一定的突變能力，以提高算法的全局搜索能力。

1.2 免疫克隆選擇操作

免疫克隆選擇操作[16]本質是按個體適應度值從種群中選出精英個體，并對精英個體進行克隆操作與變異操作構成新種群，再從新種群中選出精英個體進入下一次迭代，直到達到免疫克隆選擇的最大迭代次數。將其應用于灰狼優化算法是對原灰狼種群中的精英個體進行更深入的探索，以擴大搜索范圍并改善種群多樣性。克隆選擇的詳細步驟如下：

步驟1 根據適應度函數值從灰狼種群中選出適應度較好的m個個體形成精英種群（根據文獻[16]將m值設置為灰狼個體數的1/4）。

步驟2 克隆精英種群中的所有灰狼個體，克隆大小與選擇的精英種群數m成正比，形成大小為Nc的臨時種群T，Nc計算公式如下：

其中，round()函數為取整函數；λ是屬于[0，1]之間的隨機數；b是整型常數且b≥1，與原始種群數量N相比，Nc的大小與b的值呈正相關關系；這樣可以確保精英種群中的每個個體都有一定數量的克隆體。

步驟3 對種群中的每個個體實施高頻變異，以在精英個體附近獲得更好的候選解，變異操作如公式（9）～（11）所示：

其中ti是種群T第i次迭代的個體；tnewi是ti在經過變異操作后產生的新的個體；r4、r5、r6是屬于[0，1]之間的隨機數；i代表第i次迭代；imax代表免疫克隆操作的最大迭代次數；η是克隆變異參數。由公式（11）可以看出，迭代次數與克隆變異參數η呈負相關，η在開始時接近1，變異范圍較大，此時執行全局范圍搜索以保證種群多樣性；隨迭代次數的增加，η的值越來越接近0，表示在較小的范圍內執行局部搜索以增加微調能力，確保搜索的準確性。

步驟4 從T中再選擇出較好的m個個體，作為下一次迭代的精英個體種群，直到達到免疫克隆操作的最大迭代次數。

1.3 粒子群位置更新思想

在灰狼優化算法中，從公式（5）可以看出，灰狼的位置變動主要是根據3只頭狼的位置進行獵物位置探索，之后在3 只頭狼（α、β、δ狼）帶領下進行位置更新。由于現在面對的是精英種群，其中每個精英個體的獵物搜索結果中包含的信息，都可能會對獵物的最終位置的搜索結果產生影響，因此為考慮單個精英個體的位置信息，最大化提高精英個體利用率，擴大精英個體周邊獵物的搜索范圍。

本文從粒子群優化算法位置更新思想中得到啟發，考慮將單個灰狼個體的位置變化思想引入到灰狼位置更新中，避免算法出現早熟收斂，將公式（7）的更新策略進行相應的調整，調整如下：

其中，w是[0，1]間的隨機數，經過多次仿真實驗，w取值在[0.6，1]間時，算法有更好的搜索性能，算法尋優結果更準確，當w較大時，具有更好的全局搜索能力，w較小時，局部搜索能力較強，可以有效地避免早熟收斂；r6、r7、r8都是[0，1]間的隨機數，C1、C2、C3由公式（4）得出；X1、X2、X3可由公式（6）得出；X(t)代表當前灰狼的位置。

1.4 基于免疫克隆與粒子群位置更新的灰狼優化算法（IPSGWO）

綜上所述，基于免疫克隆與粒子群位置更新的灰狼優化算法（IPSGWO）如下所示：

begin

初始化種群規模N，精英個數m=N/4，最大迭代次數lmax，狼群初始速度v，以及λ、b和w。

按維度對灰狼種群{xi,i=1,2,…,N}進行初始化。

初始化灰狼種群中前三個最優個體α、β和δ狼，并記錄其位置Xα、Xβ和Xδ。

while (l＜lmax)

while (i≤N)

計算N只狼的適應度值{f(xi),i=1,2,…,N}，并記錄α、β和δ狼的位置；

按適應度值排序，找出最優的m個個體，放入臨時種群temp[m]中；

按式（8）克隆生成Nc個克隆個體，放入精英種群T中；

按式（10）和（11）計算每次迭代的p和η的值；

按式（9）對精英種群T中個體進行變異；

i=i+1；

end while

經過免疫克隆選擇操作，輸出種群大小為Nc的新種群Tnew；

forg=1 to size(Tnew) do

重新計算新種群個體適應度值，選出α、β和δ狼并記錄其位置；

按式（3）和（4）計算A和C的值；

按式（5）和（6）計算X1、X2和X3；

按式（13）計算灰狼個體的位置變化信息；

按式（12）更新個體的位置；

end for

更新α、β和δ狼的適應度值及其相應位置Xα、Xβ和Xδ；

l=l+1；

end while

輸出α狼的位置Xα及α狼的適應度函數值。

end

2 基于IPSGWO算法的K-Means文本聚類

2.1 適合文本聚類同類簇判定的K-Means算法

K-Means 算法是最常用的聚類算法。它采取輸入參數K，并將一組n個對象分為K個類簇，使得同一類簇內相似度較高，而不同類簇間相似度較低。

設樣本數據集為S={s1,s2,…,sn}（si為d維向量），K個類簇為C={c1,c2,…,ck}，K-Means算法步驟如下：

步驟1 從數據集S中隨機的找到K個數據點作為初始中心。

步驟2 分別計算每個數據點si到所選K個數據點之間的距離d(si,cj)，按照距離最近的原則將每個數據點分派到距離它們最近的類簇中。

步驟3 分別計算各個類簇中的數據點的平均值，將其設置為下一次迭代的聚類中心。

步驟4 循環迭代步驟2～4，直到達到最大迭代次數或者滿足一定的聚類精度為止。

其中，上述步驟中數據對象間的距離通過歐氏距離計算，如公式（14）所示：

在進行文本聚類分析時，使用歐氏距離來度量文本之間的相似性會造成很大誤差，因此本文采用經典的文本相似性度量方法：余弦相似度，如式（15）所示：

由于兩篇文檔之間的余弦相似度越高，兩篇文檔屬于相同類簇的概率越大，根據文獻[17]將距離定義修改為公式（16）：

其中，兩篇文檔距離與余弦相似度值呈負相關：當文本相似度最高時，余弦相似度值為1，而兩篇文檔之間的距離值0，為0；當文本相似度最低時，余弦相似度值為0，而兩篇文檔之間的距離值最大，為1。

2.2 IPSGWO與K-Means相結合的文本聚類算法

在對文本數據進行聚類分析時，由于文本文檔屬于非結構化數據，因此在進行文本聚類前需要對文本文檔進行預處理，將文本數據類型轉化為可供IPSGWOKMeans 算法輸入的數值型數據，其中文本預處理的基本步驟為：文本分詞處理，去除停用詞，文本特征選擇以及文本向量化。

本文使用Python中的jieba分詞對文本文檔進行文本分詞及去除停用詞處理，常用的文本表示模型主要有：布爾空間模型（BM）、后綴樹模型（STM）、向量空間模型（VSM）以及概率檢索模型（PM）等。本文采用最經典的文本向量模型（VSM）進行文本向量化，對于文檔D，采用(tf-idf1,tf-idf2,…,tf-idfn)進行向量表示[17]。其中tf-idf的計算公式如公式（17）所示：

其中，ni為包含詞語ti的文檔個數，N為文檔總數；tf(t,d)表示詞語ti在文檔D中出現的次數。

本文采用IPSGWO 與K-Means 算法結合進行文本聚類分析，具體來說是利用IPSGWO算法找出一組最優聚類中心來使文本中各類別中所有文本到該組聚類中心的距離最小，即各文檔的相似度最大。在GWO 算法中，適應度函數是灰狼尋找最優解的目標。在K-Means算法中，類內距離之和是衡量聚類算法優劣的重要指標，其值越小，則聚類性能越好。IPSGWO 與K-Means算法結合的目的就是利用IPSGWO 算法強大的尋優能力，精確找出最優聚類中心，通過該聚類中心對文本文檔進行類別劃分。本文選取文本文檔間的類內距離之和作為IPSGWO 算法的適應度評估函數，如公式（18）所示：

其中，d(si,cj)可由公式（16）計算得出，K代表聚類類別。

IPSGWO 與K-Means 算法結合的文本聚類算法的算法步驟為：

步驟1 對文本D進行分詞、去停用詞、特征選擇和向量化，將文本數據轉換為數值型數據，作為文本聚類算法的原始數據集S。

步驟2 初始化聚類類別數K，并按不同維度對灰狼種群進行隨機初始化（種群中每個個體表示一組K個聚類中心），獲得灰狼種群X={x1,x2,…,xn}。其中xi可由公式（19）產生：

步驟3 按K-Means 算法中的步驟2，按公式（15）計算數值型數據集S中的每一個數據對象到每一個初始灰狼個體代表的K個聚類中心的余弦相似度，并按公式（16）將該數據對象分配到距離最近的類簇中，直到所有數據對象分配完畢。

步驟4 按照公式（18）計算每個灰狼個體的個類簇中所有數據對象的類內距離之和（適應度評估函數值）。

步驟5 按適應度函數值的大小對灰狼種群中每個個體排序，并從中選出適應度函數值較好的m個個體形成精英種群。

步驟6 對精英個體執行免疫克隆選擇操作，輸出新種群。

步驟7 計算IPSGWO 算法的相關參數，并對免疫克隆選擇操作后生成的新種群執行帶有粒子群位置更新思想的灰狼位置更新。

步驟8 判斷IPSGWO-KMeans 文本聚類算法是否達到最大迭代次數或者滿足收斂條件，如果是，記錄下α狼的適應度值及其位置Xα，其中Xα就是最終的聚類中心；反之，循環迭代步驟2～6。

步驟9 輸出文本聚類結果，并將對應的文本文檔數據按最終聚類結果分配到對應類別中。

3 仿真結果及分析

實驗硬件環境為：64位Win10操作系統，500 GB硬盤；軟件環境為：Python3.7，MATLAB2017a。

實驗所用到的文本數據為：微博及新聞短文本數據集，共分為4類數據：女性、體育、文學出版、校園。從大量的文本數據中每類各選取50篇文檔，將共200篇文檔混合在一起打亂順序作為IPSGWO 與K-Means 算法結合的文本聚類測試樣本。

實驗參數設置：文本聚類算法的類別設置為4，IPSGWO-KMeans 算法的迭代次數設置為500，灰狼種群數設置為50，其他對比算法設置相同的迭代次數和種群數量。

實驗結果評估方法：類內距離之和、準確率、召回率和F值。其中，類內距離之和越小代表數據聚合度越高；準確率與召回率都是介于0到1之間，兩者結果越靠近1，代表文本聚類算法的查全率越高；F值大小也在0和1 之間，其值越大，代表聚類效果越真實可靠。并且將本文所提IPSGWO-KMeans 文本聚類算法與傳統KMeans 算 法、IPSK-Means 算 法 以 及GWO-KMeans 算法[15]進行文本聚類實驗對比，其中類內距離之和的收斂情況如圖1 所示；為了更好地驗證所提算法的文本能力，在各個算法穩定狀態時，分別取一次較好的準確率、召回率和F值的實驗結果進行對比，結果記錄如表1所示，加黑字體為實驗較優結果。

圖1 適應度函數收斂曲線

由圖1 可以看出，本文所提IPSGWO-KMeans 文本聚類算法較原始GWO-KMeans 算法和IPSK-Means 算法有更好的收斂速度和尋優能力，在前300 次迭代的過程中，尋找最優聚類中心的有更強的尋優能力，在迭代后期，由于加入了粒子群位置更新思想，IPSGWOKMeans 算法的有更強的突變能力，可以跳出已經找到的較好的聚類中心，從較好的聚類中心附近找到更優解；較傳統的K-Means 算法，IPSGWO-KMeans 文本聚類算法的類內之和減少了2.5 左右，有優秀的尋優能力。

從表1 可以看出，本文所提IPSGWO-KMeans 文本聚類算法較GWO-KMeans 算法、IPSK-Means 算法以及傳統K-Means 算法有更高的準確率、召回率以及F值，文本聚類更準確。相較于傳統K-Means算法，在4類數據中準確率、召回率及F值平均分別提高了33.84%、33%和31.63%。原因在于傳統K-Means 算法易收斂到局部極值，在對文本聚類的過程中，會出現收斂停滯，處于局部最優，從而造成文本聚類結果可靠性不高，IPSGWO-KMeans 算法通過免疫克隆操作以及粒子群位置更新思想與GWO 算法結合來優化K-Means 算法，可以避免算法陷入局部極值，從而提到文本聚類的可靠性。

表1 文本聚類結果

4 結束語

針對傳統K-Means 算法在文本聚類過程中易陷入局部最優，導致文本聚類效果不可靠、不易發現文檔間關系的問題，本文將免疫克隆與粒子群位置更新思想加入到灰狼優化算法中，并用改進后的灰狼優化算法與KMeans 算法結合（IPSGWO-KMeans 算法）去解決KMeans算法存在的問題。通過對文本數據聚類實驗，結果顯示，IPSGWO-KMeans 算法在對4 類文本文檔進行聚類時，較傳統K-Means算法有快的收斂速度以及更優質的尋優能力，同時對文本數據聚類的準確率、召回率以及F值都有明顯的提高，平均提高了33.84%、33%和31.63%。因此，IPSGWO-KMeans 文本聚類算法聚類準確率更高，聚類結果更可靠。

下一步的研究方向，是采用IPSGWO-KMeans 算法對雷災文本數據進行文本聚類分析，找到雷災多發時間以及地區等相關信息。