基于改进人工蜂群算法的网络突发事件预测∗

蒲国林 刘笃晋 李 杰

（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）资助。

蒲国林，男，博士，教授，研究方向：人工智能、模式识别。刘笃晋，男，博士，讲师，研究方向：人工智能、数字图像处理。李杰，男，硕士，实验师，研究方向：大数据，人工智能。