基于改進人工蜂群算法的網絡突發事件預測?

蒲國林 劉篤晉 李 杰

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

基于改進人工蜂群算法的網絡突發事件預測?

蒲國林1劉篤晉1李 杰2

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

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

網絡突發事件；人工蜂群算法；搜索公式；熱點事件

1 引言

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

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

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

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

2 人工蜂群算法

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

2.1 人工蜂群算法基本原理

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

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

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

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

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

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

2.2 兩個新的搜索方程

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

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

式（5）和（6）中，其參數r，k，i是互不相同的整數，且 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參數r的隨機性，相比RXi，j更能保證全局范圍多樣性搜索，式（6）中跟隨蜂是在雇傭蜂提供信息基礎上搜索蜜源的，因而跟隨蜂是以GABC中第一項RXi，j為基礎，第二項中以不同于 RXi，j的 RXr，j和柯西變異因子 λ促進觀望蜂擺脫局部最優，因此本改進算法中 pi，j，μi，j可以保證以此算法搜索網絡突發事件時即能快速搜索到所有可能突發事件又能獲得全局最優中的最可能突發事件。

3 雙搜索方程人工蜂群算法的網絡突發事件預測原理

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

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

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

根據群體智能涌現原理，其具體算法如下：

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

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

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

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

5）讓雇傭蜂、跟隨蜂和偵察蜂根據各自的搜索方程繼續尋優；

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

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

8）跟隨蜂若發現更優蜜源，則升級為雇傭蜂；

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

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

11）根據所得的所有局部最優值，則是網絡群體中每個類型中的關注度最高的消息，全局最優蜜源對應消息，是整體群體中關注度最高的消息，即可能是網絡突發事件。

4 實驗結果與分析

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

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

表1 三種算法的開放實驗數據

表2 三種算法的封閉實驗數據

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

5 結語

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

［1］蔣玉婷.數據挖掘技術在網絡輿情預測中的應用［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］于雪晶，麻肖妃，夏斌.動態粒子群優化算法［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，Fateen 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）資助。

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