劉 艷,周 斌,2
(1. 武漢工程科技學(xué)院信息工程學(xué)院,湖北 武漢 430200;2. 華中科技大學(xué)軟件學(xué)院,湖北 武漢 430200)
相對于普通文本而言,增量文本包含的數(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)算法計算過程。
由于增量文本存在一定數(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)增量文本聚類。 群體智能(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)。 通過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)聚類。 本文研究基于群體智能的增量文本軟聚類算法,通過語義序列特征分析得到增量文本特征,依據(jù)該特征,選取基于群體智能的蟻群算法,設(shè)計增量文本軟聚類算法,并通過Python語言構(gòu)建SCAST程序,實現(xiàn)聚類算法的計算過程。同時采用仿真形式進行實驗,得出本文算法具備較低的聚類執(zhí)行時間,能夠改善聚類效果。在未來研究階段,可依據(jù)現(xiàn)有聚類分析繼續(xù)優(yōu)化,實現(xiàn)多種形式文本的聚類。2.2 基于群體智能的增量文本軟聚類
3 實驗分析
4 結(jié)論