基于群體智能的跨語言網絡輿情文本聚類模型

韓 楠,喬少杰,黃 萍,彭 京,周 凱

(1.成都信息工程大學 a.管理學院; b.軟件工程學院，成都 610225；2.四川省公安廳，成都 610014)

網絡輿情分析需要對網絡社會中群體所表達的情緒、態度、信念等信息進行實時準確的分析和挖掘，以掌握社情民意，應對網絡突發的公共事件等[1]。隨著互聯網的飛速發展，跨語言(多語言)互聯網文本信息在我國非常普遍，如藏族同胞經常采用藏文和中文混合使用的方式在網絡上發表自己的觀點。然而，目前的輿情分析系統主要針對單一語言進行挖掘和預測，跨語言的網絡輿情分析的研究成果在國內外鮮有報道，國內目前沒有同類技術和相關應用軟件出現。因此，研發跨語言的網絡輿情分析系統對于分析處理當前快速增長的大規模網絡信息具有重要的科學價值及應用意義，也是迫切需要投入人力和物力開發的。

跨語言輿情分析系統旨在滿足客戶檢測網絡輿情動態并獲得敏感信息的需求，主要功能包括：提取半結構化和無結構化網頁、博客、論壇等文本中的主題信息，存儲到數據庫中；實現跨語言文本信息的預處理，包括分詞、提取特征詞、建立存儲結構等；對提取的半結構化信息進行聚類或分類處理；分析海量的數據中發現主題、檢測熱點、追蹤專題等。

分詞是網絡輿情分析系統的關鍵環節，在數據存儲和數據分析中起著承前啟后的作用。近年來，分詞方法的研究備受學者關注，出現了多種具有應用前景的分詞方法，其中基于字典的分詞方法[2]應用十分廣泛，尤其適用于多語言環境下的文本挖掘研究。基于字典的分詞具有3個要素：分詞字典、文本掃描順序和匹配原則。這3個要素互相組合生成了許多種分詞方法，包括正向最大匹配法、逆向最大匹配法、雙向掃描法、逐詞遍歷法、最佳匹配法等。綜合上述方法的優缺點及通用性，本文采用的是正向最大匹配法對爬取的半結構和無結構的文本進行分詞，然后進行文本聚類。

文本聚類分析是網絡輿情分析的關鍵步驟，旨在將散亂的抽象對象的集合劃分為多個分組，生成的每個分組由相似的對象組成。本文研究的目的在于設計一種高效、準確、支持多語言環境的網絡輿情文本聚類模型，為下一步的輿情分析做準備。

為了實現大規模半結構和無結構文本數據的聚類分析，各種聚類算法被廣泛提出。隨著大數據時代的來臨，聚類算法不但要考慮結果的準確性，更重要的是算法如何更加高效地適應實時更新的網絡環境。簡單傳統的聚類算法，如k-means[3]、k-mediods聚類算法，在局部環境的聚類中表現出較好的聚類效果，但運用于復雜和大規模文本數據中效率低下[4]。基于群體智能的聚類算法以其自身的自適、啟發等特點，具有分布式處理大數據的優勢[5]。

群體智能(swarm intelligence,SI)[6]作為一個新興的研究領域，最早來自于對自然界中昆蟲群居生活的觀察和模擬。群居性生物就個體而言并不具有較高的智能，而是通過種群個體之間相互協作，共同完成復雜的工作，群體智能算法成功地解決了組合優化、計算機、機器人、電力系統等眾多領域問題。目前，常見的群體智能算法有遺傳算法(genetic algorithm,GA)[7]、蟻群算法(ant colony optimization,ACO)[8]、細菌覓食算法(bacterial foraging algorithm,BFA)[9]、人工魚群算法(artificial fish swarm algorithm,AFSA)[10]、粒子群算法(particle swarm optimization,PSO)[11]、人工蜂群算法(artificial bee colony,ABC)[12]等。

本文借鑒蟻群算法的工作原理，生成智能體并將其隨機放置于二維文本空間中，根據信息素的存量指定移動朝向進而實現文本聚類。此外，提出了多種優化策略，改進群體智能算法運行的網格環境和智能體(本文稱為agent)。所提的新型群體智能算法具備啟發式和自適性的特點，可以實現大規模跨語言文本聚類。

1 基本概念

本節首先給出模型中使用的重要定義，并給出基于群體智能文本聚類的概念。

定義1文本向量。文本被表示成一個多維向量，向量的每一維對應文本中的一個特征詞，向量每一維的取值對應特征詞在文本中的權重值，即該特征詞在文本中的重要程度。一個文本d可以轉換成一個多維文本向量，如式(1)所示。

d=〈(t1,w1),(t2,w2),…,(ti,wi),…,(tn,wn)〉

(1)

其中：ti表示向量空間中的特征詞；wi表示在文檔d中ti對應的權重。將所有的文本文檔轉化為文本向量，所有的文本向量構成一個特征向量空間。

定義2基于群體智能的文本聚類。假設具有n維向量文本數據集的m個對象{t1,t2,…,tm}以及L個智能體，基于群體智能文本聚類的基本思想是：L個智能體根據簇內相似度高、簇間相似度低的原則，將這m個對象劃分到k個簇中，使得評價函數值最小。

利用智能體對文本進行聚類，生成智能體并將其隨機放置于二維文本空間中，根據信息素的存量指定移動朝向，若當前網格的信息素存量相同，則隨機指定移動朝向。這里給出文本拾起和放下的概念[5]。

定義3文本拾起概率。智能體利用式(2)計算拾起所在區域文本對象的概率

(2)

其中：kp表示智能體拾起文本對象的概率值；f(ti)表示文本對象ti與鄰近文本相似度的平均值。

定義4文本放下概率。智能體利用式(2)計算放下所在區域文本對象的概率：

(3)

其中:kd表示智能體放下樣本對象的概率;f(ti)表示文本對象ti與鄰近文本相似度的平均值。

定義5文本相似度。文本相似度定義為

(4)

其中：s2代表局部環境范圍；d(ti,tj)表示文本對象ti和tj之間的距離；α因子用來控制環境相似度的取值范圍，決定了相鄰對象之間的辨識度。α取值過小會導致簇過于緊湊且空間中出現多個小簇。

為了實現跨語言文本聚類，需要將分詞后文本進行特征詞提取生成多維文本向量，然后計算所有文本向量之間的相似度生成文本相似度矩陣，計算文本向量相似度利用夾角余弦公式。本文將式(4)修改為

(5)

將1-d(ti,tj)/α修改成為sim(ti,tj)/α。標準的群體智能聚類算法是根據對象之間的距離算出相似度，修改后的公式適應于文本聚類過程中文本相似度的計算。通過式(5)可以發現，文本向量ti與相鄰的文本向量tj之間的相似度越高，說明ti的局部相似度越高。

2 基于群體智能的文本聚類算法

基于群體智能的跨語言網絡輿情文本聚類模型的工作原理如圖1所示：① 參數初始化，主要包括文本空間網格大小、信息素、拾起和放下文本的概率值kp和kd等參數的設置。② 計算智能體所在網格內文本對象相對于其他文本對象的相似度，將其作為文本拾起的概率，當智能體拾起文本的概率大于隨機概率閾值，則拾起該文本。如果智能體本身拾有文本，計算當前文本與其所在網格相鄰的8個不同區域，即：上、下、左、右、左上、左下、右上、右下中文本的相似性，作為文本對象放下的概率值；如果其值大于隨機概率值，智能體便選擇放下這一文本。大量的智能體在網格中向不同區域移動，重復上述步驟最終使得評估函數代價最小，完成文本向量聚類的任務。

圖1 基于群體智能的文本聚類算法工作原理

算法1基于群體智能的跨語言文本聚類算法

輸入：多語言文本特征向量集合T

輸出：文本類簇集合C={c1,c2,…,cp}

1.initialTex(); //將文本向量隨機分布到網格中

2.initialAgent(); //智能體及網格環境初始化

3.fori=1 toNdo //迭代N次

4. forj←agentNum do //遍歷每個智能體

5.r=agent.getLocation(); //r獲取智能體所在位置

6. fortk∈T

7. if(ajis unloaded &&ris occupied bytk)

//智能體aj無負載且r處有文本對象tk

8. computef(tk)andppick(tk);

//計算群體相似度f(tk)和拾起概率ppick(tk)

9. if(ppick(tk)>pr) //pr表示隨機概率值

10.ajpicks uptk; //智能體拾起文本對象

11. else if(ajhastkandris empty)

//智能體負載對象tk且r處為空

12. computef(tk)andpdrop(tk);

//計算群體相似度和放下概率pdrop(tk)

13. if(pdrop(tk)>pr)//pr表示隨機概率值

14.ajdrops offtk; //放下文本對象

15. end if

16. end for

17.aj.randomMove(); //智能體選擇隨機移動

18. end for

19.end for

20.outputC={c1,c2,…,cp}; //輸出聚類結果

算法復雜性分析:通過分析可以得到算法的時間復雜度為O(A×N×M)，其中：A表示智能體的數量；N表示算法的迭代次數；M表示文本的數量。

3 優化策略

標準的基于群體智能的文本聚類算法主要存在如下幾個方面的不足：

1)算法1是基于網格空間的聚類算法，文本被隨機放置于網格空間中，算法經若干次迭代后，文本向量在網格空間中的分布呈現出聚類結構，即相似的文本向量對象被聚到一起。但是網格空間中的聚類結構并不穩定，智能體在移動的過程中不斷形成新的聚類結構，同時也在不停地破壞智能群體的分布。

2)在標準的群體智能本文聚類算法中引入信息素機制，借助信息素引導和控制智能體的移動，可以加快聚類收斂，極大地提高算法的收斂速度，但同時也帶來了局部對象過多、智能體容易陷入局部最優等問題。智能體會被引導到信息素濃度較高的區域，由于智能體與環境的正反饋作用，局部的文本向量集中于該區域。

3)利用群體智能實現文本聚類的優越性表現在自組織、啟發式和魯棒性等方面，聚類結果需要從網格空間結構中迭代獲取，網格中的聚類效果越明顯，越容易獲取較好的結果。

優化標準群體智能算法，需要改進算法運行的網格環境和智能體，保證群體智能算法具備啟發式和自適應性的特點。本文提出如下優化策略：

策略1在算法運行過程中，逐漸弱化智能體拾取文本對象的能力，以達到網格中聚類結構趨于穩定的目的。具體做法是在迭代的過程中利用梯度下降法逐步降低kp值，使得智能體拾取概率ppick降低，當kp縮小到智能體不再具有拾取對象的能力時，網格中的聚類結構趨于穩定，kp值也無需進一步降低。

策略2添加信息素引導智能體的移動，信息素能夠提高智能體與環境的交互能力[13]，基本思路為：在智能體搬運和搜索食物時，每個智能體會在所經過路徑上留下一定量的信息素。智能體在選擇下一步之前會感應周圍環境中的信息素以指導下一步走向，同時信息素以一定速度揮發，最終的結果是環境中形成一條由高濃度信息素構成的路徑，最終找到最優路徑。智能體在網格環境中移動，會在網格環境中留下大小為σ的信息素，信息素會隨著時間的流逝而揮發，揮發因子為η。算法每經過一次迭代，網格環境中的信息素都會按照揮發因子消失一部分。第k+1次迭代后，網格環境中某個位置的信息素由σk變為σk+1，計算方法如式(6)所示。

σk+1=(1-η)*σk

(6)

式中η的取值范圍為[0,1]。

針對信息素揮發過快的問題，本文對式(6)進行改進，智能體在經過某一位置時，該位置的信息素σl變為σl+1，計算方法如式(7)所示。

σl+1=σl+(η+N/A)

(7)

式中：N表示算法執行的次數；A表示智能體數量。式(7)中增加了執行次數和智能體數量的比值，可以有效地避免信息素揮發過快的問題。

策略3智能體根據當前位置選擇下一位置需要考慮兩個因素：信息素感應濃度和方向權重因子。

智能體移動的步長均為1，因此智能體的下一步移動方向為(1,Δθ)，其向各個方位移動的概率是不同的，每個方位的權重值都是由智能體當前移動方向決定的，上一步的位置為(x*,y*)，經過移動方向(1,Δθ)，移動到了(x,y)，可以利用公式(8)計算得到智能體在(x,y)處的移動方向狀態θ值。

(8)

網格環境中信息素響應濃度利用如下公式求取：

(9)

其中參數β表示對信息素刺激的敏感程度，用來決定響應函數W(σ)。β控制隨機移動的程度，依據這個參數，智能體沿著信息素梯度方向移動。低于β值的信息素濃度并不會很大程度地影響智能體的移動概率，而高于β值的信息素濃度會使智能體更確定地沿著信息素濃度的梯度方向移動。1/γ描述了智能體對信息素的感知能力，即在高濃度情況下對信息素減少的感知能力。參數β和1/γ共同決定了信息素的痕跡。因此，信息素濃度的響應函數由σ、β和1/γ三個參數共同決定。

因此，感應信息素濃度和方向權重因子決定了智能體的下一步移動方向。智能體移動下一步選擇臨近網格信息素為σ的概率p可用式(10)計算。

(10)

通過上述分析可以發現：實現基于信息素的群體智能文本聚類算法，僅需要將算法1中第17行的智能體隨機移動方法改為基于式(6)～(10)的感應信息素移動方法，進而實現對本文所提基于群體智能的文本聚類算法的優化。

4 實驗及算法性能分析

4.1 實驗數據集及參數設置

實驗數據為利用筆者開發的跨語言網絡爬取器從中文、英文及藏文門戶網站抓取的半結構化和無結構化的文本，并保存到數據庫中。對存入數據庫的文本信息利用正向最大匹配法進行分詞，去噪和提取關鍵字等操作后得到初始數據集。藏文數據如圖2所示。

圖2 藏文數據表結構示例

圖2為輸入數據表，包括7個屬性：id，title，content，url，words，num，date。其中:id表示文本編號;title是文本主題;content是文本內容;url是文本的爬取鏈接;words是經過分詞和提取關鍵字后的關鍵字序列;num是對應關鍵字在文本中出現的頻數。本文進行跨語言(如藏文和中英文)文本聚類時，主要利用了圖2中title、content和words三個涉及文本內容的屬性。

本文的實驗環境為：奔騰雙核2.0 GHz CPU，2 GB內存，開發語言為Java，使用Eclipse SDK1.6。

實驗中分別使用k-means、標準群體智能文本聚類算法(swarm-intelligence-based text clustering model，簡稱SI-Cluster)和應用第3節介紹的優化策略的群體智能文本聚類算法SI*-Cluster算法對多語言文本數據集進行聚類。通過比較聚類算法的準確性和收斂速度，證明本文所提算法的性能優勢。

SI-Cluster算法參數設置如表1所示。在如表1所示參數設置下，群體智能算法性能較好。實驗中當文本數量增加時，僅需改變網格空間大小和智能體數量即可，無需進行其他人為設置。

表1 基于群體智能的文本聚類算法參數設置

4.2 聚類準確性對比

實驗中對聚類的有效性利用查準率P、查全率R和F-measure值[14]進行評價，定義如下:

已知TP表示利用聚類算法正確聚類出的文本；FP為不在本簇被錯誤聚類出的文本；FN表示包含在本簇但未被聚類到這個簇中的文本；TN表示不在本簇且未被聚類到本簇的文本，于是：

P=TP/(TP+FP)

(11)

R=TP/(TP+FN)

(12)

F-measure = 2PR/(P+R)

(13)

實驗選用1 200條數據作為基本測試數據集。這些數據集主要從新浪中英文網站中的3個欄目中爬取的，即體育(sports)、新聞(news)和視頻(video)，并自動加上標簽用于聚類準確性的判別。對比SI-Cluster和SI*-Cluster算法，聚類準確性結果如表2～4所示。

表2 k-means算法聚類準確性

表3 SI-Cluster算法聚類準確性

表4 SI*-Cluster算法聚類準確性

通過表2～4可以發現：應用優化策略的群體智能文本聚類算法SI*-Cluster的F-measure平均值相比于標準算法SI-Cluster提高13.6%，相比于k-means算法提高44.1%，證明了本文所提出應用優化策略的基于群體智能的文本聚類算法的準確率較傳統算法有顯著提升，主要原因在于：

1)傳統k-means算法需要根據初始聚類中心來確定一個初始劃分，然后對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇不合適，可能無法得到有效的聚類結果。此外，k-means 算法中k是事先給定的，k值的選定非常難以確定。而本文提出的基于群體智能的文本聚類算法，一旦初始參數確定，算法可以自適應訓練，通過一定的改進和優化，可以保證找到最優聚類結果。

2)改進的群體智能文本聚類算法SI*-Cluster明顯優于標準的SI-Cluster算法，原因在于SI*-Cluster算法通過改進網格環境和智能體，保證了群體智能算法具有啟發式和自適應性的特點。在算法運行過程中，逐漸弱化智能體拾取文本對象的能力，以達到網格中聚類結構趨于穩定的目的。此外，添加信息素引導智能體的移動，信息素能夠提高智能體與環境的交互能力。

為了進一步驗證本文所提算法可以處理多語言文本，如藏文，實驗中對藏文文本數據集進行實驗，驗證k-means、SI-Cluster和SI*-Cluster算法的聚類準確性。實驗文本數量分別選取150、300、450、600、750、800、950、1 100。由于采集的數據集分類不均衡，因此利用F-measure方法來評價聚類效果，結果如圖3所示。

圖3 藏文文本聚類準確性F-measure值對比

通過圖3可以發現：對于藏文文本，本文提出的群體智能文本聚類算法明顯優于k-means算法。從F-measure值的變化可以看出，3種算法在文本數量較少的情況下，聚類效果都比較好。隨著文本數量增加到450，算法的F-measure值不斷減小。然而當文本數量增加到一定的程度(當文本數量為600時)，SI-Cluster算法和SI*-Cluster算法的聚類準確性不斷提升，說明基于群體智能的文本聚類算法不會受到文本數量的影響，具有比較高的穩定性和自適應性。

4.3 聚類運行收斂性及運行時間對比

本節比較SI-Cluster和SI*-Cluster的算法收斂性并對比收斂時的運行時間，進而說明本文所提出應用優化策略的群體智能文本聚類算法的性能優勢。實驗中選用4.2節中1 200條中英文半結構化文本數據，為了保證實驗結果的客觀性和可比性，每組實驗對1 200條文本數據集訓練10次取F-measure的平均值。實驗參數設置如表1所示，SI*-Cluster算法應用第3節優化策略1將kp值設置為0.01～0.001變化，下降梯度設置為0.000 1，實驗結果如圖4所示。

圖4 基于群體智能的本文聚類算法收斂性對比

表5 基于群體智能的文本聚類算法收斂次數及時間

通過圖4和表5可以發現：

1)基于群體智能的文本聚類算法會在運行若干步之后達到收斂，即F-measure值達到一定的水平。SI-Cluster算法隨著迭代次數的增加，F-measure值的變化波動較大，而SI*-Cluster算法的F-measure曲線相對平滑，而且穩定時的F-measure值明顯高于SI-Cluster算法。主要原因在于SI*-Cluster算法應用了第3節優化策略3，智能體移動時根據當前位置選擇下一位置結合了信息素感應濃度和方向權重因子，智能體穩定地沿著信息素梯度增加的方向移動，避免了陷入局部最優的問題，具有較高的穩定性。

2)SI*-Cluster算法的F-measure曲線能夠平滑且較快地收斂并達到穩定值。原因在于SI*-Cluster算法應用第3節優化策略2，通過添加信息素并有效避免信息素揮發過快的問題，引導智能體快速地找到最優解，具有較快的收斂速度。

5 基于群體智能的文本聚類過程模擬

為了進一步觀察應用本文提出3種優化策略前后的文本聚類效果，筆者開發了一個基于群體智能的跨語言文本聚類系統。系統模擬過程中采用第4.2節介紹的3個欄目的中英文文本共90條數據作為待聚類數據，每類含有30個文本向量(相同的顏色表示屬于相同的類)，被隨機放置在網格環境中。SI-Cluster和SI*-Cluster算法運行結果如圖5～6所示。

圖5(a)為初始化數據后的網格結構圖，圖中網格表示網格環境，不同顏色的正方形代表不同類的文本向量。圖5(b)是SI-Cluster算法迭代300次之后的網格布局。圖5(c)是SI-Cluster算法迭代600次之后的網格布局。可以看出，算法在迭代300次之后所有的文本向量已經被大致劃分為11個類，有一定的聚集效果。再次迭代300次之后網格中又出現了一個全新的聚類結構。算法由于沒有應用優化策略，所以經過900次迭代后的聚類效果并不好，沒有達到收斂，很多不同顏色的文本被錯分到一個類簇中。

圖6(a)為初始化數據后的網格結構圖，圖6(b)是SI*-Cluster算法迭代300次之后的網格布局，圖6(c)是SI*-Cluster算法迭代600次之后的網格布局，圖6(d)是SI*-Cluster算法迭代900次之后的網格布局。可以看出，算法在迭代了300次之后所有的文本向量已經被大致分為11個類，相比于SI-Cluster算法，聚類效果具有顯著的提升。迭代了600次之后聚類結構與迭代300次時的聚類結構布局相似且相對收斂，證明了本文所提的優化策略具有較好的穩定性。算法迭代900次之后類簇結構比較明顯，網格中構建了9個簇，不同的類之間的重合區域比較少，只需要將聚類結構繼續聚合，便可方便地得出最終的聚類結構，進一步說明應用本文提出的優化策略，算法聚類效果好，具有較高的收斂速度。

圖6 SI*-Cluster算法不同迭代次數下聚類結果展示

6 結束語

隨著Web2.0技術快速發展，Internet網上信息交流變得更加方便和快捷，不同語言和民族的個體可以通過論壇、微博、社交網站及時發表個人觀點，研發跨語言的網絡輿情文本挖掘技術對于分析和處理當前日益增長的大規模網絡本文信息具有重要的科學價值及應用意義。本文充分考慮群體智能算法的啟發性、自適應性和魯棒性，提出了一種基于群體智能的跨語言文本聚類模型。為了克服傳統群體智能算法的不足，所提算法應用了3種策略，即：應用梯度下降法弱化智能體拾取文本對象的能力避免陷入局部最優解，添加信息素引導智能體移動并有效避免信息素揮發過快的問題，智能體從當前位置選擇下一位置考慮信息素感應濃度和方向權重因子。大量實驗證明本文所提算法具有較高的聚類準確性和較快的收斂速度。

未來工作將從以下幾個方面展開研究：① 將所提的文本聚類方法應用于大規模網絡輿情文本挖掘，通過分析網絡文本預測可能潛在的突發事件；② 借鑒蜂群等其他更加智能的群體算法，進一步提高文本聚類的準確性；③ 對算法進一步優化，提高群體智能尋找最優解的速度，及算法收斂速度。