适用于新媒体事件聚类模型的混合算法研究

孙玲芳，李金海

（江苏科技大学 经济管理学院，江苏 镇江 212003）

0 引 言

从2003年的SARS事件开始，新媒体事件逐步呈现在公众的视野中，并在近几年里爆发频率不断提高，使得人们认识到了新媒体事件的严重性，对新媒体事件的预警研究也成为网络安全领域的热点。对新媒体事件的预警就是在新的新媒体事件未爆发之前，依据某种策略对它进行分类，分在不同类中的新媒体事件有着不同的处理措施，确保新媒体事件的及时发现以及妥善的处理。

目前常用的聚类方法有：层次法、划分法、网格法以及密度法。其中被学者广泛认可的K＿Means算法是一种基于划分的聚类算法；而另一种启发式全局寻优算法即遗传算法（genetic algorithm，GA）近几年也被大量学者研究。文献［1］采用K＿Means算法作为聚类模型的主要算法，提出了一种运算速度快，准确性高的数据挖掘方法［1］；文献［2］将遗传算法和最近邻算法动态结合，得到了一种更优秀的聚类算法［2］；文献［3］发现遗传算法与蚁群算法的融合，较单独的遗传算法或蚁群算法，有着更好的聚类效果［3］。可见算法融合已经成为构建更为优秀的聚类算法的方法，为本文的研究提供了理论依据。

1 聚类分析的原理

聚类分析是将多个样本对象组成的集合，按相似性分成多个簇，性质相近的归为同一个簇，使得分在同一簇中的对象具有最大的同质性，而分在不同簇中的对象具有最大的异质性的过程。聚类分析的一般过程如图1所示。

聚类算法的选择需要依据聚类的目的以及样本表示的数据类型来判断，而且在有些聚类问题中单个算法已不能满足算法的精度要求，这时就需要将两个或两个以上的算法相结合以达到更佳的效果。

图1 聚类分析的一般过程

1.1 K＿Means的原理

聚类算法有动态与静态之分，动态聚类算法与静态聚类算法的主要区别在于通过不断的迭代来完成聚类，且在迭代过程中允许样本从一个簇中转移到另一个簇中。K＿Means算法就属于动态聚类法，因此它也具有动态聚类法的迭代特点［4］。动态聚类法过程如图2所示。

图2 动态聚类法过程

K＿Means算法是一种基于划分的常见的聚类算法，一般采用误差平方（均方差）作为标准测度函数。具体算法描述为：

Data［n］，k；

（1）C［1］＝data［1］，c［2］＝data［2］…c［k］＝data［k］；／随机选取k个初始中心；

（2）对于data［1］，data［2］…data［n］，分 别 与c［1］，c［2］…c［k］比较，若与c［i］差值最小，就标记为i；

（3）对于所有标记为i的样本，重新计算c［i］＝｛∑所有标记为i的data／标记为i的个数｝；

（4）重复（2）、（3），直到所有c［i］值的变化小于给定阀值。

标准测度函数为

式中：Di——c［i］中的Xk与相应的聚类中心的度量即欧几里德距离［5］。D——欧几里德距离之和，聚类的目的是使得非相似性（或距离）指标的目标函数达到最小，即D最小。

虽然K＿Means算法应用广泛，但该算法也有一定的局限性，该方法最终结果受初始值影响较大，结果较易陷入局部最优，且对孤立点敏感。

1.2 遗传算法的原理

在预警系统中，新媒体信息来源广泛、内容繁多，一般的聚类算法不能较好的处理，通过研习大量的文献发现，遗传算法适合新媒体事件的聚类分析。早在20世纪70年代就有人提出了遗传算法，算法原理是模拟自然界生物的遗传变异的进化过程，通过遗传算子来体现遗传算法的思想，是一种启发式全局寻优算法［6］。遗传算法的思想是基于遗传规律与自然选择。

遗传算法处理的对象是染色体，每条染色体都是问题的一个解，算法的最终目的是选出最适应环境的染色体，即最优解。遗传算法中的样本组成了群体，个体对环境的适应程度称为适应度。在执行遗传算法前，需要进行编码操作：把搜索空间中的数据转换成遗传空间中的染色体；在执行遗传算法后，需要进行译码操作：把染色体转换为问题原来的数据类型。

虽然遗传算法具有很好的处理约束，能很好的跳出局部最优，最终得到全局最优解以及全局搜索能力强等诸多优点；但遗传算法全局搜索的特点也使得算法时间复杂度较大，不符合新媒体事件预警系统的及时性。

2 聚类算法的改进

在分析K＿Means与遗传算法的基础上，发现K ＿Means算法以及遗传算法都较适用于新媒体事件的聚类模型构建，而它们各自存在的不足也正好被另一种算法所填补，若能将二者合理的结合，克服各自的劣势，发挥各自的优势，必是一个优秀的适应新媒体事件聚类的算法。基于此，本文提出了混合K均值遗传算法（genetic algorithm with K＿Means，GAWKM）的概念。此算法是基于K＿Means算法和遗传算法原理的设想，结合K－Means算法的局部搜索能力与遗传算法的全局搜索能力，最终得到全局最优解，并且算法的时间复杂度在规定范围之内。

2.1 混合K均值遗传算法的原理

在混合K均值遗传算法中，选择过程通过轮盘赌算法实现，并采用最优保存策略保留上代中个体适应度达种群平均适应度1.5倍或以上（若种群规模较大，可适当增大倍数，可加快算法的收敛速度）的个体进入下一代的父代，缺少的子代则以随机方式产生，最大程度保证了混合K均值遗传算法的收敛［7］。交叉操作则采用单点交叉。通过仿真实验发现，变异是遗传算法能跳出局部最优的关键操作，而变异概率决定着变异的效果，因此，让变异概率随着群体的平均适应度不断向最优个体的适应度接近时，就自适应地动态增大。

2.2 混合K均值遗传算法的具体流程

混合K均值遗传算法的具体流程如下：

设样本总数为n；聚类簇即聚类中心数为k（2≤k≤n－1）；交叉概率Pc，变异概率Pm，最大遗传代数genmax，已迭代数gen，适应度阀值F。

（1）选择编码策略：在混合K均值遗传聚类算法中，每一条染色体都必须表示所有个体应属于哪类，所以染色体采用自然数编码为佳［8］；设染色体Y＝（G1，G2，…，Gn），Y为1×n维向量，Gi为Y 上第i位的基因，其中：

RandomGi，

／基因Gi为k类中的某类

／基因的取值覆盖所有聚类号，保证每条染色体都有效

在模型中，运用式（1）随机产生Gi，运用式（2）循环判断，若条件式（2）未满足时，须重置Gi。

（2）定义适应度函数：适应度函数的好坏很大程度上影响遗传算法的迭代次数与效果。本文采用“界限构造法”［9］

为适应度函数（fitness function）；其中

将求最小极值问题转化为求最大极值问题，可以在选择操作中直接使用轮盘赌算法。

／保留初始群体中适应度最大的个体

（3）用K＿Means算法对每个个体进行优化gen＋＋；

／每迭代一次，已迭代数gen加一操作

／Yj为第j条染色体

优化后，得到新的Yj＝（G1，G2，…，Gn）。

／a为采用最优保存策略保留的进入下代个体数｝通过轮盘赌算法选择剩下的父代：

／r为0至1的随机数

int c；c＝random（1，n）；

／在染色体中随机选择第c位的基因作为交叉点

在交叉操作中采用“基于最短距离基因匹配的算术交叉。”［10］

需要注意的是，在这个学习过程中，无论语言也好还是文学作品也好，其中都包含了很多来自西方国家的价值取向，包括价值观、人生观的不同观念影响，学生在整体的学习过程中很容易将其混淆，形成一种盲目崇拜和向往的思想，进而影响到自己对于价值观、人生观、世界观的基础判断。因此，在英美文化教学开展的过程中，融入对于思想政治教育的强调，使其引领英美文化教学进一步开展是极为必要的[2]。

图3 传统交叉操作

而基于最短距离基因匹配的算术交叉，就能够弥补传统交叉操作的这一不足。操作过程如下：

minAj；

／比较出最短距离，并记录是最短距离的那位基因j

j∈m；

这种交叉方法能够改进遗传算法的收敛性，防止无意义个体的产生，加快聚类速度。

（6）变异操作（Mutation）

采用单点变异，变异概率Pm随着群体的平均适应度不断向最优个体的适应度接近时，就自适应地动态增大［11］，设定

按新的变异概率Pmi，选择染色体Yai，在Yai上随机选择一个基因位c，并按式（5）变异

／保留新一代群体中适应度最大的个体

（7）判断算法是否结束

／达到最大代数或满足适应度要求

to（8）；

／执行步骤（8）

else continue（3）；

／否则跳到步骤（3）

（8）用K＿Means算法对最优个体优化

／找出每代最优个体中适应度最大个体

Y＝（G1，G2，…，Gn），其中Data［n］＝Y

／Y为fmax对应的染色体

优化后，得到新的Y＝（G1，G2，…，Gn）

／得到的Y 即为最终的最优个体

（9）输出结果：Y＝（G1，G2，…，Gn）

／将基因值译码成类的编号

3 仿真实验

我们运用MATLAB7.0编译混合K均值遗传算法，实验数据选取百度百科收录的，近几年（2009、2010、2011年）发生的新媒体事件50个，作为训练样本，并按时间顺序从1－50进行标记。具体样本文件信息如图4所示。

图4 样本文件信息

经统计，上述50个新媒体事件的时间分布如表1所示。

表1 时间分布

通过对上述50个以及其它的新媒体事件的分析发现，新媒体事件大致分为以下四类：

（1）对社会的发展与稳定有利的事件；

（2）属于广大网民自娱自乐的事件；

（3）对社会的发展与稳定有一定负面影响的事件；

（4）严重影响社会的发展与稳定的事件。

因此本文设定聚类数K＝4；样本总数n＝50；交叉概率Pc＝0.7，变异概率Pm＝0.01，最大遗传代数genmax＝200，已迭代数gen，适应度阀值F＝0.05。

其中新媒体事件的文本信息通过向量空间模型转换为计算机能够识别形式［12］，表示为：

其中，X为新媒体事件的影响度值，Ti表示第i个特征项的值，Wi表示特征项Ti的向量权重，特征项为文本中重要的词语，向量权重通过词频加权法计算得来，即某一特征项在文本中出现次数越多，Wi越大。向量空间模型经过特征降维降为5维，这5个特征项是文本中出现次数最多的5个词，Ti的具体数值与它的语义强度直接相关。有关转换向量空间模型的具体过程这里不再详述。50个新媒体事件的影响度在坐标轴上的分布如图5所示。

图5 样本分布

横轴表示样本的序号，纵轴表示样本的影响度值。

将算法及样本数据输入MATLAB7.0，得到最优解Y＝（1，3，3，1，4，4，3，4，4，3，4，3，2，3，3，4，2，3，4，4，4，3，2，2，2，2，2，3，2，3，4，3，4，3，3，3，4，2，4，3，3，1，4，2，1，3，4，3，3，3）；

聚类之后的样本分布图如图6所示。

图6 样本聚类分布

具体聚类结果见表2。

表2 聚类结果

通过对聚类结果进行分析，发现第6，23，31，36，40，50个新媒体事件的分类结果，与各大媒体最终对这些新媒体事件的评价有所不同。如分在第三类的40。郭美美事件，本身是一个炫富事件，应该说对社会的发展与稳定影响不大，但由于之后关联了红十字的一系列问题，使得国内一时陷入了慈善荒，最终使事件升级为第四类新媒体事件。经过试验后的再次分析，发现这6个事件的误判，是由于新媒体事件文本信息的不完善以及语义强度判断算法还不够精确所致。

第一类新媒体事件属于对社会的发展与稳定有利的事件，此类事件不需要有关部门的刻意引导，适当的褒奖可以弘扬社会风气；第二类新媒体事件属于广大网民自娱自乐的事件，一般此类事件不需要特别的关注，它们会随着时间的流逝，让公众逐渐淡忘；第三类新媒体事件属于对社会的发展与稳定有一定负面影响，这类事件就需要有关部门及时做出正确的引导，防止发展成为第四类事件；而第四类新媒体事件的爆发则会严重影响社会的发展与稳定，轻则扰乱社会治安，重则造成人员伤亡，对于这类事件，及时正确的官方引导是重点，而给予那些恶意煽动民意的幕后黑手相应的处罚则是辅助措施。经过对四类新媒体事件的分析，我们发现某个事件的从属关系，并不是一成不变的，有关部门及时正确的引导能够让事件走向良性的发展方向，反之亦然。

本次仿真试验的结果正确率约为88%，应该说还较为理想。而导致误差的大部分原因将在今后的研究中不断完善。

4 结束语

通过将遗传算法与K＿Means算法有效结合，提出了混合K均值遗传算法，并合理运用界限构造法、最优保存策略、基于最短距离基因匹配的算术交叉以及变异概率的自适应改变等方法，在一定程度上解决了遗传算法的收敛较慢、不适于处理复杂数据，以及K＿Means算法易于陷入局部最优解、对孤立点敏感的不足。通过仿真试验，发现试验结果正确率较为理想，说明混合K均值遗传算法适用于新媒体事件的聚类模型构建，但此算法在前期的数据收集以及文本信息向计算机能识别的数据转换精确度方面还不够完善，在后期的研究中还有待改善。

［1］ZHOU Lijuan，SHI Qian，GE Xuebin，et al.Cluster－based evaluation in fuzzy－genetic data mining［J］.Computer Engineering and Applications，2010，46（13）：118－121（in Chinese）.［周丽娟，石倩，葛学彬，等.基于聚类的模糊遗传挖掘算法的研究［J］.计算机工程与应用，2010，46（13）：118－121.］

［2］LU Linhua.A novel dynamic clustering algorithm based on genetic algorithm［J］.Computer Simulation，2009，26（7）：122－125（in Chinese）.［陆林花.一种新的基于遗传算法的动态聚类算法［J］.计算机仿真，2009，26（7）：122－125.］

［3］ZHU Feng，CHEN Li.Research on clustering algorithm based on fusion of ant colony and genetic algorithm［J］.Journal of Northwest University（Natural Science Edition），2009，39（5）：745－749（in Chinese）.［朱峰，陈莉.蚁群与遗传算法融合的聚类算法研究［J］.西北大学学报（自然科学版），2009，39（5）：745－749.］

［4］Nazim Dugan，Sakir Erkoc.Genetic algorithm application to the structural properties of si－ge mixed clusters［J］.Materials and Manufacturing Processes，2009，24（3）：250－254.

［5］LIU Hailin.Research of web user clustering model based on genetic algorithm［D］.Tianjin：Tianjin University of Technology，2007：7－14（in Chinese）.［刘海琳.基于遗传算法的Web用户聚类模型的研究［D］.天津：天津理工大学，2007：7－14.］

［6］QIN Junhua，ZHANG Hongwei，ZHAO Shizheng.Fuzzy clustering analysis based on genetic algorithm and its application［J］.Computer Applications，2007，27（1）：52－55（in Chinese）.［覃俊华，张洪伟，赵世政.基于遗传算法的模糊聚类研究及其应用［J］.计算机应用，2007，27（1）：52－55.］

［7］SU Liangyu，SU Liangbi.Cluster analysis based on genetic algorithm［J］.Computer Development and Application，2011，24（2）：7－9（in Chinese）.［苏良昱，苏良碧.基于遗传算法的聚类分析［J］.电脑开发与应用，2011，24（2）：7－9.］

［8］SHENG Weiguo，Allan Tucker，LIU Xiaohui.A niching genetic k－means algorithm and its applications to gene expression data［J］.Soft Computer，2010，14（11）：9－19.

［9］LOU Yuansheng，TAO Zhenhong.Web service composition algorithm for QoS global optimization［J］.Computer Engineering and Applications，2011，47（8）：207－210（in Chinese）.［娄渊胜，陶振宏.Web服务组合QoS全局优化算法［J］.计算机工程与应用，2011，47（8）：207－210.］

［10］LI Long1ong，WANG Mei1i.Research on an adaptive genetic algorithm based on weighted binary tree［J］.Computer Technology and Development，2010，20（11）：95－99（in Chinese）.［李龙龙，王美丽.基于加权二叉树的自适应遗传算法研究［J］.计算机技术与发展，2010，20（11）：95－99.］

［11］ZHENG Yu，CHEN Zhuangzhuang，LI Yajuan，et al.New automatic alignment technology for single mode fiberwaveguide based on improved genetic algorithm［J］.Optoelectronics Letters，2009，5（3）：165－168.

［12］JING Liping，Michael K Ng，Joshua Z Huang.Knowledgebased vector space model for text clustering［J］.Knowledge and Information Systems，2010，25（1）：35－55.