改進(jìn)灰狼優(yōu)化算法的K-Means文本聚類

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

大連大學(xué) 通信與網(wǎng)絡(luò)重點實驗室，遼寧 大連116622

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

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

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

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

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

1.1 灰狼優(yōu)化算法（GWO）

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

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

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

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

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

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

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

1.2 免疫克隆選擇操作

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

步驟1 根據(jù)適應(yīng)度函數(shù)值從灰狼種群中選出適應(yīng)度較好的m個個體形成精英種群（根據(jù)文獻(xiàn)[16]將m值設(shè)置為灰狼個體數(shù)的1/4）。

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

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

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

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

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

1.3 粒子群位置更新思想

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

本文從粒子群優(yōu)化算法位置更新思想中得到啟發(fā)，考慮將單個灰狼個體的位置變化思想引入到灰狼位置更新中，避免算法出現(xiàn)早熟收斂，將公式（7）的更新策略進(jìn)行相應(yīng)的調(diào)整，調(diào)整如下：

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

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

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

begin

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

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

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

while (l＜lmax)

while (i≤N)

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

按適應(yīng)度值排序，找出最優(yōu)的m個個體，放入臨時種群temp[m]中；

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

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

按式（9）對精英種群T中個體進(jìn)行變異；

i=i+1；

end while

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

forg=1 to size(Tnew) do

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

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

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

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

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

end for

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

l=l+1；

end while

輸出α狼的位置Xα及α狼的適應(yīng)度函數(shù)值。

end

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

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

K-Means 算法是最常用的聚類算法。它采取輸入?yún)?shù)K，并將一組n個對象分為K個類簇，使得同一類簇內(nèi)相似度較高，而不同類簇間相似度較低。

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

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

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

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

步驟4 循環(huán)迭代步驟2～4，直到達(dá)到最大迭代次數(shù)或者滿足一定的聚類精度為止。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟4 按照公式（18）計算每個灰狼個體的個類簇中所有數(shù)據(jù)對象的類內(nèi)距離之和（適應(yīng)度評估函數(shù)值）。

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

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

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

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

步驟9 輸出文本聚類結(jié)果，并將對應(yīng)的文本文檔數(shù)據(jù)按最終聚類結(jié)果分配到對應(yīng)類別中。

3 仿真結(jié)果及分析

實驗硬件環(huán)境為：64位Win10操作系統(tǒng)，500 GB硬盤；軟件環(huán)境為：Python3.7，MATLAB2017a。

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

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

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

圖1 適應(yīng)度函數(shù)收斂曲線

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

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

表1 文本聚類結(jié)果

4 結(jié)束語

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

下一步的研究方向，是采用IPSGWO-KMeans 算法對雷災(zāi)文本數(shù)據(jù)進(jìn)行文本聚類分析，找到雷災(zāi)多發(fā)時間以及地區(qū)等相關(guān)信息。