基于改進人工蜂群算法的網(wǎng)絡突發(fā)事件預測?

蒲國林 劉篤晉 李 杰

（1.四川文理學院智能制造學院 達州 635000）（2.四川文理學院信息化建設與服務中心 達州 635000）

基于改進人工蜂群算法的網(wǎng)絡突發(fā)事件預測?

蒲國林1劉篤晉1李 杰2

（1.四川文理學院智能制造學院 達州 635000）（2.四川文理學院信息化建設與服務中心 達州 635000）

由于網(wǎng)絡突發(fā)事件預測的復雜性，傳統(tǒng)的網(wǎng)絡突發(fā)事件預測效果并不理想。針對這種情況，對傳統(tǒng)人工蜂群算法（ABC）的尋優(yōu)搜索公式進行了較大改進，將傳統(tǒng)的單一搜索公式擴展為雇傭蜂和跟隨蜂各一個搜索公式，并根據(jù)人工蜂群算法的群體智能涌現(xiàn)原理，將改進的人工蜂群算法（IABC）引入網(wǎng)絡群體環(huán)境中進行突發(fā)事件預測，以此為基礎，提出了一種基于改進人工蜂群的網(wǎng)絡突發(fā)事件預測算法。語料庫測評中以K最近鄰分類（KNN）、ABC、GABC、IABC三種算法進行實驗，實驗結果表明，論文所提算法在網(wǎng)絡突發(fā)事件預測的準確率、召回率、綜合性評價指標上都是最優(yōu)的，因而完全可用于實際。

網(wǎng)絡突發(fā)事件；人工蜂群算法；搜索公式；熱點事件

1 引言

目前網(wǎng)絡突發(fā)事件監(jiān)管的任務極其嚴峻和迫切，若能提前預測到網(wǎng)絡突發(fā)事件，并建立相應的處理方案，對維護社會和諧和穩(wěn)定將起著非常重要的作用。在一些關鍵技術方面已取得了一些進展，如2003年加州大學伯克利分校在對WEB數(shù)據(jù)自動采用給定的算法進行比較分析方面就取得了滿意成果，英國科波拉公司2005年開發(fā)出了可判斷相關資料感情色彩及政治立場文本分析軟件，2011年美國一項專利技術提出可以自動分析匯總互聯(lián)網(wǎng)上的文本信息等，隨后許多學者在此基礎上進行了大量研究，也取得了一定進步，諸如基于網(wǎng)絡分析知識建立的網(wǎng)絡情報系統(tǒng)、網(wǎng)絡重大事件預測系統(tǒng)等等。蔣玉婷［1］等利用灰色模型GM模型對網(wǎng)絡突發(fā)事件進行初步預測，然后采用BP神經(jīng)網(wǎng)絡對GM模型預測結果進行修正，其神經(jīng)網(wǎng)絡參數(shù)以粒子群算法優(yōu)化；對于網(wǎng)絡突發(fā)事件分類監(jiān)測的還有貝葉斯方法［2］、K近鄰算法（KNN）［3］等。這些對網(wǎng)絡突發(fā)事件預測都還不全面，不成熟，在對網(wǎng)絡突發(fā)事件整個周期的發(fā)展規(guī)律進行預測研究進展并不理想。

近年來以粒子群算法［4～5］、布谷鳥算法［6］、人工蜂群算法等為代表的算法有了較快發(fā)展，并取得了一些進步［7～9］，文獻［10］比較了各種群體智能尋優(yōu)算法，認為在群體智能尋優(yōu)中，人工蜂群算法具有更好的收斂和尋優(yōu)能力。

要建立一個健全的網(wǎng)絡突發(fā)事件預測系統(tǒng)，人工蜂群算法具有天然的優(yōu)點，因為人工蜂群算法不僅擁有群體智能的特點，能利用群體智能涌現(xiàn)過程和網(wǎng)絡突然事件發(fā)生過程具有的相似性，建立網(wǎng)絡突發(fā)事件預測系統(tǒng)，而且人工蜂群算法具有優(yōu)秀的全局優(yōu)化能力，原理簡單、參數(shù)少和容易實現(xiàn)，但人工蜂群算法也存在局部收斂和全局收斂不平衡的現(xiàn)象。

本文基于單搜索方程的人工蜂群算法，提出了一種基于雙搜索方程的人工蜂群算法（IABC），并將其運用于網(wǎng)絡突發(fā)事件預測中進行突發(fā)事件預測，所得的各個局部最優(yōu)值就是各個類型的熱點事件，所得的全局最優(yōu)值即對應網(wǎng)絡環(huán)境中關注度最高的事件，若為負面事件即為網(wǎng)絡突發(fā)事件。

2 人工蜂群算法

人工蜂群算法是一種基于多目標函數(shù)尋優(yōu)的群體智能算法，近年來在許多方面都得到了應用［11～13］，特別是在圖像處理領域如圖像邊緣檢測［14］以及醫(yī)用圖像處理［15］方面都發(fā)揮了重要作用。

2.1 人工蜂群算法基本原理

人工蜂群算法是一種元啟發(fā)式算法，通過自然界蜜蜂的智能覓食行為而產(chǎn)生，天然蜂群的食物尋找是三種蜜蜂分工合作的群體行為，這三種蜜蜂包括：雇傭蜂、觀望蜂、偵察蜂，雇傭蜂根據(jù)記憶和蜜蜂特有的舞蹈尋找蜜源并和觀望蜂共享最近找到的食物信息，觀望蜂在雇傭蜂尋找到的蜜源附近尋找更好的食物源，而偵察蜂隨機尋找新的蜜源。

在人工蜂群算法的群體中，雇傭蜂的數(shù)量等于觀望蜂的數(shù)量，也等于人工蜂群算法中解的個數(shù)，初始化時所有食物源被當作解向量RXi，隨機產(chǎn)生RN個可行解，每個可行解的位置RXi，j可表示如下

β∈[-1，1]，u≠k，其中i，u，k=1，2，…，RN，j=1，2，…，D，D表示此問題的維度，RXu，jandRXk，j表示維度j的上界和下界。

在人工蜂群算法中，每個食物源相關的蜜源數(shù)量及質(zhì)量和相關解的適應度值 fiti對應，三種蜜蜂在算法內(nèi)不斷迭代搜索蜜源，并拋棄不能滿足條件的蜜源，否則，根據(jù)相應蜜源適應度值的概率選擇蜜源，其 pi公式如下

其中 fiti是第i個可行解的適應度值，而新舊蜜源位置變化公式如下

這里 k≠ik，i∈｛1，2，…，RN｝，j∈｛1，2，…，D｝，RXi，j與 RVi，j分別表示蜜蜂搜索前后的位置，μi，j∈[-1，1]。

2.2 兩個新的搜索方程

在人工蜂群算法（ABC）中，三種蜜蜂都在不斷重復自己的搜索過程，以尋求全局最優(yōu)，但三種蜜蜂的尋優(yōu)過程中都存在局部最優(yōu)和全局最優(yōu)的平衡問題，經(jīng)常存在的問題是陷入局部最優(yōu)而導致較長時間無法收斂，許多研究者都進行了研究，也取得了一些進步［16～17］，對人工蜂群算法改進具有代表性是GABC算法［18］，GABC算法對人工蜂群算法的改進主要體現(xiàn)在對搜索公式的改進：

在 GABC算法中 RXi，j、RVi，j同式（3）一樣分別表示蜜蜂搜索前后的位置，RXbest，j表示全局最優(yōu)位置（全局最優(yōu)解）的第j個元素，θi，j是一個隨機數(shù)，且 θi，j∈[0，1.5]，ωi，j∈[-1，1]，k，i互不相同且k，i∈｛1，2，…，SN｝，但實驗結果表明，GABC算法對人工蜂群算法的改進性能表現(xiàn)并不明顯，從實驗過程分析得知，人工蜂群算法中三種蜜蜂的實際搜索路徑并不完全相同，ABC算法和GABC算法對三種蜜蜂都采用了同樣的搜索公式，特別是雇用蜂和觀望蜂之間的搜索路徑有著明顯的不同，但卻采用了同一種搜索公式，要改進算法性能，必須要對三種蜜蜂有針對性提出相應的搜索公式，根據(jù)本文中對網(wǎng)絡突發(fā)事件預測需要，基于在人工蜂群算法的基礎上結合粒子群算法及蜂群個體在高維空間的動態(tài)特性，對雇傭蜂和觀望蜂各提出了一個搜索公式，由于偵察蜂是隨機搜索，因此偵察蜂采用本文提出的雇傭蜂搜索公式，雇傭蜂和觀望蜂提出的相應搜索公式如下

式（5）和（6）中，其參數(shù)r，k，i是互不相同的整數(shù)，且 r，k，i∈｛1，2，…，RN｝，j∈｛1，2，…，D｝，pi，j∈[0，2]，μi，j∈[-2，2]，式（5）和式（6）的 RXi，j、RVi，j都表示搜索變化前后的位置，θi，j，ωi，j同式（4），式（5）相比式（4），RXr，j參數(shù)r的隨機性，相比RXi，j更能保證全局范圍多樣性搜索，式（6）中跟隨蜂是在雇傭蜂提供信息基礎上搜索蜜源的，因而跟隨蜂是以GABC中第一項RXi，j為基礎，第二項中以不同于 RXi，j的 RXr，j和柯西變異因子 λ促進觀望蜂擺脫局部最優(yōu)，因此本改進算法中 pi，j，μi，j可以保證以此算法搜索網(wǎng)絡突發(fā)事件時即能快速搜索到所有可能突發(fā)事件又能獲得全局最優(yōu)中的最可能突發(fā)事件。

3 雙搜索方程人工蜂群算法的網(wǎng)絡突發(fā)事件預測原理

網(wǎng)絡突發(fā)事件發(fā)生的各個群體因素組成異常復雜，但基本原理是以互信息理論NMI（normalized mutual information）為基礎［19］，以群體智能涌現(xiàn)原理進行網(wǎng)絡突發(fā)事件預測模擬時，所有網(wǎng)絡個體即所有網(wǎng)絡用戶構成一個虛擬群體，然后在這個虛擬群體中關注度最高的前X條新聞。在采用人工蜂群算法進行網(wǎng)絡突發(fā)事件預測中，假設網(wǎng)絡突發(fā)事件預測系統(tǒng)中群體有N個個體，共需要分析M條消息，每個網(wǎng)絡用戶的個體目標，就是找出自己最關注的多條新聞，而群體目標即找出群體中最受個體關注的消息列表L，根據(jù)這個原理建立群體目標函數(shù)即人工蜂群算法的群體適應度函數(shù)公式如：

式（7）中，CL表示消息列表L中消息的總條數(shù)，H(l)表示網(wǎng)絡突發(fā)事件預測中智能群體對消息l的關程度，因而消息l對整個群體的關注度即群體中所有個體對此消息的關注度總和。根據(jù)群體智能涌現(xiàn)原理，以群體中消息列表L作為環(huán)境介質(zhì)，所有個體都會去關注或修改消息列表L，則對消息l的個體關注度計算公式即個體的適應度公式如下

其中，Dl(t)、Dl(t-1)分別表示群體消息列表L中任一條消息l在N個個體中任一個體對其評價前后的關注度，當群體中所有個體都對消息l評價后，此時Dl(t)=H(l，n)，表示完成評價消息。

根據(jù)群體智能涌現(xiàn)原理，其具體算法如下：

1）在網(wǎng)絡虛擬群體環(huán)境中，首先對人工蜂群進行初始化，隨機產(chǎn)生N只蜜蜂包括雇傭蜂、跟隨蜂、偵察蜂。

2）根據(jù)式（7）計算所有蜜蜂個體的適應度值即消息關注度值；

3）根據(jù)式（8）計算人工蜂群群體的適應度值即群體的消息關注度值；

4）若某個局部最優(yōu)的關注度值大于或等于當前群體消息關注度值，則當前局部最優(yōu)值用全局最優(yōu)值代替；

5）讓雇傭蜂、跟隨蜂和偵察蜂根據(jù)各自的搜索方程繼續(xù)尋優(yōu)；

6）根據(jù)三種蜜蜂的尋優(yōu)結果計算所有蜜蜂個體的適應度值即消息關注度值，獲得的所有局部最優(yōu)值即整體虛擬群體中每個類的關注度最高值；

7）雇傭蜂若發(fā)現(xiàn)關注度值即適應度值更高的蜜源，則拋棄當前的蜜源，引領跟隨蜂繼續(xù)搜索，否則雇傭蜂降為偵察蜂；

8）跟隨蜂若發(fā)現(xiàn)更優(yōu)蜜源，則升級為雇傭蜂；

9）計算適應度值，更新蜜源；

10）重新執(zhí)行3）～7），直到滿足預定的條件；

11）根據(jù)所得的所有局部最優(yōu)值，則是網(wǎng)絡群體中每個類型中的關注度最高的消息，全局最優(yōu)蜜源對應消息，是整體群體中關注度最高的消息，即可能是網(wǎng)絡突發(fā)事件。

4 實驗結果與分析

為了準確評估本文所提的改進人工算法在網(wǎng)絡突發(fā)事件預測中的性能改善程度，采用中文自然語言處理開放平臺提供的語料庫測評，本實驗包括封閉性測試和開放性測試兩部分內(nèi)容［20］，其中封閉性測試是指學習語料作為被實驗文本，對其進行分類實驗，開放性測試是對測試語料進行分類實驗，實驗中2000篇作為訓練文本，另取1000篇文檔作為KNN模型的待測試文本，然后從訓練文本中抽取1000篇進行封閉測試，對1000篇待測試文本進行開放性測試，以本文中KNN算法、ABC算法，GABC算法，IABC算法在實驗文本中進行分類測試，即KNN算法中K個聚類中心消息、ABC算法、GABC算法、IABC算法中所有局部最優(yōu)消息，就是分類測試所得的結果，并依據(jù)分類測試的結果進行網(wǎng)絡突發(fā)事件仿真預測，采用當前典型的評測指標包括準確率、召回率、綜合性評價指標其公式為

其中R、S、E分別表示判斷正確的文本數(shù)量、沒有判斷出的文本數(shù)量以及判斷錯誤的文本數(shù)量，C、P、F分別表示準確率、召回率以及綜合性評價指標，三種算法的實驗結果如表1、表2所示。

表1 三種算法的開放實驗數(shù)據(jù)

表2 三種算法的封閉實驗數(shù)據(jù)

從表1及表2的實驗數(shù)據(jù)來看，本文提出的IABC算法無論在準確率、召回率以及綜合評價指標上，都比ABC算法、ABC算法和KNN算法要好，主要因為IABC算法在人工蜂群算法的局部收斂和全局收斂上做到了很好的平衡，改進人工蜂群算法中雇傭蜂和跟隨蜂各提出的一個新的搜索公式很好保證了整個蜂群在局部尋優(yōu)基礎上快速向全局最優(yōu)收斂，也保證了通過人工蜂群算法在網(wǎng)絡突發(fā)事件發(fā)現(xiàn)基礎上，快速進行突發(fā)事件的跟蹤，即快速尋找到全局最優(yōu)，GABC算法比ABC算法預測效果好些，因為改進的搜索公式增加了多樣性，而ABC算法的預測效果比K最近鄰算法預測效果好，因為人工蜂群算法用于網(wǎng)絡突發(fā)事件預測時，所具有的各個局部最優(yōu)即對應KNN算法的K個分類中心，而人工蜂群算法在局部尋優(yōu)的效率上相比KNN算法的多次迭代聚類，不僅速度較快，而且分類中心也比較明確，因而在網(wǎng)絡突發(fā)事件發(fā)現(xiàn)上比KNN要快，在準確上也比KNN算法要高。

5 結語

本文首次將人工蜂群算法引入網(wǎng)絡突發(fā)事件預測中，在中文自然語言處理開放平臺提供的語料庫測評中做了封閉性測試和開放性測試的初步嘗試實驗，實驗結果表明，本文所提出的改進人工蜂群算法在網(wǎng)絡突發(fā)事件預測中取得了較好的效果。

［1］蔣玉婷.數(shù)據(jù)挖掘技術在網(wǎng)絡輿情預測中的應用［J］.科技通報，2013，29（10）：71-75.JIANG Yuting.Application of data mining technology to the prediction of online public opinion［J］.Science and Technology Bulletin，2013，29（10）：71-75.

［2］Li-guo D，Peng D，Ai-ping L.A New Naive Bayes Text Classification Algorithm［J］.TELKOMNIKA Indonesian Journal of Electrical Engineering，2014，12（2）：947-952.

［3］Ming Yao.Research on Learning Evidence Improvement for kNN Based Classification Algorithm［J］.International Journal of Database Theory and Application，2014：103-110.

［4］韋苗苗，江銘炎.基于粒子群算法的多閾值圖像分割［J］.山東大學學報：工學版，2005，35（6）：118-121.WEI Miaomiao，JIANG Mingyan.Multi thresholds image segmentation based on particle swarm optimization algo?rithm［J］.Journal of Shandong University：Engineering Sci?ence，2005，35（6）：118-121.

［5］于雪晶，麻肖妃，夏斌.動態(tài)粒子群優(yōu)化算法［J］.計算機工程，2010，36（4）：193-197.YU Xuejing，MA Xiaoqi，XIA Bin.Dynamic particle swarm optimization［J］.Computer Engineering，2010，36（4）：193-197.

［6］Bhargava V，F(xiàn)ateen SEK，Petriciolet AB.Cuckoo search：a new nature inspired optimization method for phase equi?librium calculations［J］.Fluid Phase Equilib，2013，337：191-200.

［7］Mohamad Amin Bakhshali，Mousa Shamsi1Faculty.Seg?mentation of color lip images by optimal thresholding us?ing bacterial foraging optimization（BFO）［J］.Journal of Computational Science，2014，5：251-257.

［8］S.Dey，et al.New quantum inspired meta-heuristic tech?niques for multi-level colour image thresholding［J］.Ap?plied Soft Comput，2015.

［9］Karaboga，D.An Idea Based on Honey Bee Swarm for Nu?merical Optimization.Technical report TR-06［R］.Erci?yes University，Kayseri，Turkey，2005：10.

［10］HORNG M H.Multilevel thresholding selection based on the artificial bee colony algorithm for image seg?mentagion［J］.Expert Systems with Application，2011，38（11）：13785-13791.

［11］W.Y.Szeto and Yu Jiang.Hybrid Artificial Bee Colony Algorithm for Transit Network Design.Journal of the Transportation Research Board［J］.Transportation Re?search Board of the National Academies，Washington，D.C.，2012：47-56.

［12］Singh，A.An Artificial Bee Colony Algorithm for the Leaf-Constrained Minimum Spanning Tree Problem［J］.Applied Soft Computing，2009，9（2）：625-631.

［13］Szeto，W.Y.，Y.Z.Wu，and S.C.Ho.An Artificial Bee Colony Algorithm for the Capacitated Vehicle Routing Problem［J］.European Journal of Operational Research，2011，215（1）：126-135.

［14］D.-J.Liu，H.-J.Wang，S.Wang，G.-L.Pu，X.-Y.Deng，X.Hou，Quaternion based improved artificial bee colony algorithm for color remote sensing image edge detection［J］.MathematicalProblemsinEngineering，2015：138930.

［15］Mukesh Saraswat n，K.V.Arya，Harish Sharma.Leuko?cyte segmentation in tissue images using differential evo?lution algorithm［J］.Swarm and Evolutionary Computa?tion，2013，11：46-54.

［16］W.F.Gao，S.Y.Liu，A modified artificial bee colony al?gorithm［J］.Comput Oper Res 39，2012：687-697.

［17］W.F.Gao，S.Y.Liu，L.L.Huang，A novel artificial bee colony algorithm based on modified search equation and orthogonal learning［J］.IEEE Trans Cybern，2013，43：1011-1024.

［18］G.P.Zhu，S.Kwong，Gbest-guided artificial bee colony algorithm for numerical function optimization［J］.Appl Math Computat，2010（217）：3166-3173.

［19］Agogino A，K.Efficient agent-based cluster ensembles［C］//Proc.of International Conference on Autonomous Agents and Multiagent Systems，2006：1079-1086.

［20］奉國和.文本分類性能評價研究［J］.情報雜志，2011，30（8）：66-69.FENG Guohe.Study on performance evaluation of text categorization［J］.Journal of information science，2011，30（8）：66-69.

Prediction of Network Incident Based on Improved Artificial Bee Colony Algorithm

PU Guolin1LIU Dujin1LI Jie2
（1.School of Intelligent Manufacturing，Sichuan University of Arts and Science，Dazhou 635000）（2.Information Construction and Service Center，Sichuan University of Arts and Science，Dazhou 635000）

Because of the complexity of the prediction of network emergencies，the prediction results of traditional network emergencies are not satisfactory.In response to this situation，the traditional search algorithm of artificial bee colony algorithm（ABC）has been improved greatly.The traditional single search formula is extended to a search formula for the employed bees and the follower bees，respectively.According to the swarm intelligence emergence principle of the artificial bee colony algorithm，the improved artificial bee colony algorithm（IABC）is introduced into the network group environment for predicting the occurrence of network emergencies.Based on this，a prediction algorithm for network emergencies based on improved artificial bee colony is pro?posed.The K nearest neighbor classifier（KNN），ABC，GABC、IABC four algorithms are used to evaluate the corpus.The experi?mental results show that the proposed algorithm is optimal in the prediction accuracy，recall rate and comprehensive evaluation in?dex of the network emergency prediction.So it can be used in practice.

network emergent event，artificial bee colony algorithm，search formula，hot spot event

Class Number TP391

TP391

10.3969/j.issn.1672-9722.2017.12.002

2017年6月5日，

2017年7月24日

國家自然科學基金項目（編號：61152003）；四川省教育廳重點項目（編號：16ZA0353）；四川省教育廳項目（編號：17ZB0377）；四川省教育廳項目（編號：16ZB0360）；四川文理學院2015年度特色培育一般項目（編號：2015TP001Y）資助。

蒲國林，男，博士，教授，研究方向：人工智能、模式識別。劉篤晉，男，博士，講師，研究方向：人工智能、數(shù)字圖像處理。李杰，男，碩士，實驗師，研究方向：大數(shù)據(jù)，人工智能。