增量文本軟聚類(lèi)速度改善算法設(shè)計(jì)及仿真

劉 艷，周 斌,2

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

1 引言

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

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

2 增量文本軟聚類(lèi)算法

2.1 語(yǔ)義序列特征分析

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

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

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

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

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

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

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

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

(6)

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

2.2 基于群體智能的增量文本軟聚類(lèi)

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

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

圖1 增量聚類(lèi)算法流程圖

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

(7)

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

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

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

(8)

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

(9)

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

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

初始化網(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()；

}

}

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

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

圖2 語(yǔ)義序列相似度分析

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

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

圖3 聚類(lèi)效果分析

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

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

圖4 不同文本量大小時(shí)聚類(lèi)加速比分析

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

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

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

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

對(duì)比三種算法聚類(lèi)時(shí)的算法性能，分析結(jié)果如表1所示。

表1 聚類(lèi)效果分析

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

4 結(jié)論

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