劉 艷，周 斌,2

(1. 武漢工程科技學(xué)院信息工程學(xué)院，湖北 武漢 430200；2. 華中科技大學(xué)軟件學(xué)院，湖北 武漢 430200)

1 引言

相對于普通文本而言，增量文本包含的數(shù)據(jù)信息量較大，在以往的增量文本聚類算法中，通常在計算時會存在較高的時間復(fù)雜度，導(dǎo)致計算性能下降，且不適用于動態(tài)變化文本集聚類，同時，硬聚類方法只將一個文本劃分一個類別[1-3]，無法全面展示文本信息，而軟聚類能夠依據(jù)主題的類別劃分信息，使相同類別的文本信息分配到同一處中[4，5]。

目前，有較多學(xué)者研究文本的聚類算法，例如馬武彬等[6]，研究基于改進NSGA-Ⅲ的文本空間樹聚類算法，但該算法計算時間復(fù)雜度較高，會使聚類計算時的聚類時間延長。除此之外，還有學(xué)者研究基于語義簇的中文文本聚類算法，但該算法僅能夠處理中文文本，在對增量文本進行聚類時依然需要大量的時間。因此，本文研究基于群體智能的增量文本軟聚類算法，通過劃分語義序列特征，構(gòu)建基于蟻群算法的增量軟文本聚類計算，并采用Python語言構(gòu)建SCAST程序?qū)崿F(xiàn)算法計算過程。

2 增量文本軟聚類算法

2.1 語義序列特征分析

由于增量文本存在一定數(shù)量的長文本，且具有多主題特性，因此，通過計算語義序列相似關(guān)系對序列集合的覆蓋度進行計算，并對得到的結(jié)果進行聚類能夠有效降低增量文本向量空間維數(shù)，縮短文本軟聚類的計算時間[7]。

在語義序列中并不存在文本集中的全部信息[8]，僅存在文本自身信息，因此，有效分析語義序列，能夠得到增量文本中更加詳細(xì)的共同點。分析語義序列的基本概念：

設(shè)需要聚類的增量文本集合為D={d1，…，dk，…，dn}(1≤k≤n)，其中，dk表示每個文本，dk中的某個詞匯序列由s描述，即s=w1w2…wm，而s中e(1≤e≤m)區(qū)域內(nèi)的詞匯由we描述。通過以下流程設(shè)定語義序列，使其能夠應(yīng)用于增量文本集。

1)設(shè)定s內(nèi)區(qū)域e中的詞匯距離σ(e)為詞匯we到詞匯wh之間的詞匯數(shù)量，設(shè)為σ(e)=e-h，詞匯we=wh，同時we≠wk(1≤h

2)設(shè)ρ(e)=1/σ(e)，即s內(nèi)區(qū)域e中的語義密度ρ(e)為此處詞匯距離的倒數(shù)。

在現(xiàn)實中，可將單個文本看作長度較長的詞匯序列，而詞匯序列s內(nèi)區(qū)域e中的詞匯距離即為σ(e)，若σ(e)較短，則可以表示文本中某段落內(nèi)的詞匯we出現(xiàn)次數(shù)較多，即該詞匯we的密度很高，所以，由此可認(rèn)定在局部區(qū)域中，密度較高的詞匯能夠描述出該區(qū)域內(nèi)的局部語義特性[9，10]。

3)設(shè)語義序列為s[e]=we1we2…wer，該序列為s中的子序列，在該序列中，e=[e1，e2，…，er](1

|s[e]|>1

(1)

0

(2)

ρ(ek)≥δ，1≤k≤r

(3)

(e1-ε≤eh

(er

(4)

(?wek，wel∈s，ek≠el)→wek≠wel，

1≤k≤r，1≤l≤r

(5)

上述公式中，δ、ε均表示閾值。

當(dāng)剔除s中的低密度詞匯之后，留下的一個連續(xù)詞匯序列即為s[e]，連續(xù)的含義為：s[e]內(nèi)鄰近的兩個詞匯在初始文本s中的位置差應(yīng)不高于已設(shè)定的閾值ε。已設(shè)定的條件為：s中的非空子序列構(gòu)成s[e]；在該語義序列中的詞匯間應(yīng)存在連續(xù)性；s[e]內(nèi)的詞匯均應(yīng)為局部頻繁狀態(tài)；需保證s[e]前后距離存在一段低密度范圍，以保障s[e]不會出現(xiàn)無限擴展；確保s中不會出現(xiàn)重復(fù)詞匯。

4)熵重疊。熵重疊能夠描述出文本集合D的每個類Cq中的文本全部候選類中的劃分情況，可通過式(6)計算

(6)

式(6)中，當(dāng)dk為某個指定聚類的概率時通過pk=1/fk描述，而dk中存在的語義序列數(shù)量由fk描述。文本集合D的聚類結(jié)果集合為C={C1，…，Cq，…，Ct}(1≤q≤t)，其中，Cq表示每一個類。若Cq中的每個dk只能夠表明一個語義序列，則熵重疊為0，當(dāng)fk逐漸增加，熵重疊也會上升，由此可知，熵重疊值越低，聚類純度越好，這是由于熵重疊主要衡量語義序列分辨文本的能力。依據(jù)該特征，構(gòu)建文本軟聚類算法，實現(xiàn)增量文本聚類。

2.2 基于群體智能的增量文本軟聚類

群體智能(Swarm Intelligence)是現(xiàn)階段應(yīng)用較為廣泛的人工智能技術(shù)，隨著該技術(shù)的發(fā)展已逐漸應(yīng)用于社會、經(jīng)濟等各個領(lǐng)域[11]。群體智能算法中包含粒子群算法與蟻群算法等，本文選取蟻群算法實現(xiàn)增量文本軟聚類。在蟻群算法中，由于蟻群的移動存在一定的隨機性，因此，通過信息素操控螞蟻移動能夠加快算法的收斂，使聚類速度得到提升。在本文軟聚類算法中，依據(jù)上述分析得到的文本語義詞序特征，將其擺放在二維平面中，并為每個信息隨機分配初始區(qū)域，全部螞蟻均可通過隨機形式在網(wǎng)格中爬行，之后計算群體相似度，得到計算結(jié)果后，采用概率轉(zhuǎn)換函數(shù)繼續(xù)計算，將相似度調(diào)整為螞蟻抓取或丟棄的概率。通過大量螞蟻的爬行，可以使相同屬性的增量文本信息匯集在相同范圍內(nèi)。

通過圖1表示基于蟻群算法的增量文本軟聚類過程。在圖1中，通過f(Oi)描述群體相似度；Ppick描述抓取的概率；Pdown描述丟棄的概率；Pr表示隨機函數(shù)。

圖1 增量聚類算法流程圖

某個待聚類文本與當(dāng)前區(qū)域內(nèi)全部其它文本的綜合相似性，即為群體相似度，通過式(7)計算該相似度

(7)

式(7)中，局部環(huán)境由Oj∈Neights×s(r)描述；通過b×b設(shè)定單元r的鄰域面積；而對象屬性空間內(nèi)Oi、Oj的間距由u(Oi，Oj)描述；相似度因子為α，同時α表示群體相似系數(shù)，α能夠直接對聚類數(shù)量造成影響，因此，α為比較重要的參數(shù)，當(dāng)α越大，則會導(dǎo)致群體相似度f(Oi)變大，使得并不存在相似性的對象歸類到同一處，以此降低聚類數(shù)量并提升收斂速度，若α取值越低，則會使收斂時間變長以及聚類數(shù)量增大。

與群體相似度f(Oi)存在關(guān)聯(lián)的函數(shù)，即為概率轉(zhuǎn)換系數(shù)，通過概率轉(zhuǎn)換，能夠使群體相似度調(diào)整為文本對象的抓取概率與丟棄概率。

其中，抓取操作是在螞蟻不存在負(fù)載的情況下，抓取螞蟻鄰域內(nèi)的文本對象，確定該文本對象可以抓取的概率可通過式(8)計算

(8)

而丟棄操作是指在螞蟻負(fù)載文本情況下，若發(fā)現(xiàn)空閑網(wǎng)格，則螞蟻可丟棄該文本對象，確定丟棄的概率可通過式(9)計算

(9)

式中，可變動的參數(shù)為kd、kp，文本對象Oi與鄰近對象之間的平均相似度測量結(jié)果為f(Oi)。

本文通過Python語言構(gòu)建SCAST程序，聚類算法的計算過程，具體設(shè)計如下：

初始化網(wǎng)格grid與螞蟻列表antList；

for(迭代次數(shù))i∈iterationdo{

for(eachant∈antList)do{

if((ant＿tv==null)&&(xy＿tv！=null))

{Computer f(Oi)；

P＿pick←Computer Ppick(Oi)；

if(P＿pick>r)then

{抓取Oi；}

}

else if((ant＿tv！=null)&&(xy＿tv==null)){

Computer f(Oi)；

P＿drop←Computer Pdrop(Oi)；

if(P＿drop>r)then

{丟棄Oi；}

for(i=0；i

C.add(cov(S[e]))；

for(k=i+1；k

}

}

next＿step＿random()；

}

}

主要通過以下步驟實現(xiàn)該算法：

1)依據(jù)配置文件，對網(wǎng)格與螞蟻列表進行初始化。

2)設(shè)iteration為迭代次數(shù)，計算螞蟻迭代次數(shù)，依據(jù)現(xiàn)階段環(huán)境與螞蟻是否負(fù)載信息判定螞蟻抓取或丟棄增量文本。

3)通過Computer函數(shù)對文本相似度進行計算，將螞蟻所在位置是否存在增量文本向量采用xy＿tv描述，螞蟻是否負(fù)載由ant＿tv描述。若螞蟻所處位置存在增量文本向量且負(fù)載為空，則對抓取概率與群體相似度進行計算，若計算得到的抓取概率高于隨機值，則抓取增量文本。

4)計算S[e]的熵重疊值并存儲，同時選出最小熵重疊值的語義序列集，將該序列集與S[e]進行交換，之后再次計算熵重疊值并存儲。

5)將螞蟻ant隨機爬行至下一網(wǎng)格的函數(shù)通過next＿step＿random描述。分析該算法的復(fù)雜度，若現(xiàn)階段螞蟻總量為m，共進行n次迭代，則可計算得出時間復(fù)雜度O(m·n)。

3 實驗分析

通過VC6.0構(gòu)建仿真環(huán)境進行實驗，在實驗環(huán)境中構(gòu)建增量文本集，并選取基于改進NSGA-Ⅲ的文本空間樹聚類算法(算法1)和基于語義簇的中文文本聚類算法(算法2)進行對比實驗。

對比三種算法，分析不同文本向量空間維數(shù)下，語義序列的相似度計算能力，分析結(jié)果如圖2所示。

圖2 語義序列相似度分析

根據(jù)圖2可知，隨著特征向量維度的不斷增加，三種算法計算得到的語義序列相似度值也有所上升，其中，算法1的相似度值始終最低，算法2計算得到的相似度雖然有所上升，但依然低于本文算法，本文算法在特征向量維度為100時，相似度值達到了0.88，由此可知采用本文算法計算語義序列相似度值較高，相似度計算能力強。

從該增量文本庫中選取三類文本集，分析不同文本數(shù)量下，不同文本集的聚類召回率，分析結(jié)果如圖3所示。

圖3 聚類效果分析

由圖3可知，三類文本集在文本數(shù)量逐漸上升的情況下召回率均有所降低，其中，由于醫(yī)學(xué)類詞匯較為復(fù)雜，因此醫(yī)學(xué)類文本集的召回率在三種文本集中保持最低，而計算機類文本集召回率最高，在三種文本集的聚類過程中，召回率均保持在80%以上，說明本文算法聚類時具有較高的召回率。

分析本文算法在不同計算節(jié)點數(shù)下，計算2GB、8GB、以及16GB文本量情況下的計算加速倍數(shù)，分析結(jié)果如圖4所示。

圖4 不同文本量大小時聚類加速比分析

由圖4可知，當(dāng)計算節(jié)點數(shù)不斷增長，加速比也隨之增加，其中16GB文本量的聚類加速倍數(shù)最高，而2GB文本量的加速倍數(shù)相對較低，說明數(shù)據(jù)量越大，在進行聚類時的加速倍數(shù)就越高，同時，三種大小的文本量最終加速倍數(shù)均保持在5以上，因此，本文算法聚類時的加速效果較好。

蟻群算法中螞蟻觀察半徑是影響聚類效果的關(guān)鍵因素，選取不同螞蟻個數(shù)，分析在不同螞蟻觀察半徑下，螞蟻觀察到的文本數(shù)量，分析結(jié)果如5所示。

圖5 觀察得到文本數(shù)量分析

根據(jù)圖5可知，由于螞蟻個數(shù)的不斷增多，不同觀察半徑下觀察到的文本數(shù)量也隨之增加，其中，觀察半徑為2時觀察到的文本數(shù)量較低，而觀察半徑為6時，觀察得到的文本數(shù)量最高在9000個以上，說明觀察半徑越大，觀察到的文本數(shù)量就越多，同時，采用本文算法觀察到的文本數(shù)量均在2000個以上，說明本文算法具有較高的文本觀察能力。

對比三種算法聚類時的算法性能，分析結(jié)果如表1所示。

表1 聚類效果分析

根據(jù)表1可知，三種聚類算法中，算法2的聚類時間較長，且對異常文本并不敏感，同時聚類時內(nèi)存占比較大，算法1的聚類時間消耗過長，通過對比可知，采用本文算法能夠更好地實現(xiàn)聚類。

4 結(jié)論

本文研究基于群體智能的增量文本軟聚類算法，通過語義序列特征分析得到增量文本特征，依據(jù)該特征，選取基于群體智能的蟻群算法，設(shè)計增量文本軟聚類算法，并通過Python語言構(gòu)建SCAST程序，實現(xiàn)聚類算法的計算過程。同時采用仿真形式進行實驗，得出本文算法具備較低的聚類執(zhí)行時間，能夠改善聚類效果。在未來研究階段，可依據(jù)現(xiàn)有聚類分析繼續(xù)優(yōu)化，實現(xiàn)多種形式文本的聚類。