基于微博舆情监测的K-Means算法改进研究，本文主要内容关键词为：舆情论文,算法论文,Means论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
1 问题的提出
随着我国微博井喷式的发展，近两年的大事件中几乎都有微博在发生着作用，网民爆料的首选媒体也更多地转向微博[1]。目前，微博网站仅根据评论数和转发数统计出热门话题。显然，人工审视加简单的统计工具进行统计的方法准确度较低，引入Web文本挖掘对信息进行去重、筛选、聚类分析非常必要[2]。因此，需要一种更适合微博文本处理的聚类算法，识别出微博用户关注的热点话题，引导政府及时捕捉微博中敏感的舆情信息，将负面的微博舆情影响控制在警戒线以下，帮助政府管理者实行舆情疏导，加强微博舆情的预警和监管。
在国外，Sasa和Miles等将话题检测技术应用于Twitter，提出了一种改进的新话题检测算法，能够在不失精度的前提下，快速处理大于1.6亿条Twitter消息[3]。Liu Zitao等人基于Part-of-speech和HowNet来扩展单词语义特征，进而改进微博短文本聚类效果[4]。M.Cataldi等提出基于时序和社会关系评价的Twitter中新热点话题检测方法[5]。S.Phuvipadawat等对Twitter中爆炸性新闻检测进行了研究。他们提出一套对Twitter中爆炸性新闻进行收集、分组、排序的方法，并且设计了一个名为“Hotstream”的程序，给使用者提供这些爆炸性新闻。不过这种方法在实际应用过程中对Twitter中信息的利用度不高[6]。
在国内，将聚类算法研究应用于微博的研究成果较少，与此相关的文献大多是从微博信息分类的角度开展研究。崔争艳设计了一种基于语义的微博短信息分类方法，这种分类方法能对较短的微博信息高效准确地加以分类[2，7]。
一般而言，话题发现、舆情监测等理论研究中使用的聚类算法包括K-Means算法、Single-Pass算法、DBSCAN算法等。聚类算法研究很多，然而将聚类算法应用到微博舆情监测中，并实现了舆情监测功能的却很少，这充分说明了理论研究走向实际应用之间的距离和困难。究其原因有3个方面：①算法准确度有限；②响应时间偏长；③对用户介入的要求较高。因此，本文拟选择应用最广泛的K-Means算法，进行适当改进，以实现微博文本的聚类。
2 K-Means算法的局限性
K-Means算法的基本思想如下：在给定的初始数据集中随机地选择k个数据对象作为k个组的初始中心点。分别计算剩余的其他数据对象与各个组的初始中心点的距离，并根据距离进行归类，距离最近某中心点最近的数据对象则放到该中心点所在的组中，待所有数据对象全部归类后，再重新计算每个组的平均值作为新的中心点，重复迭代过程，直到完成指定的迭代次数，或聚类准则函数E收敛。如公式(1)所定义：
图1数据显示对于图1(a)所示的数据进行聚类，图1(b)所示理想的聚类结果，K=4的默认的簇数。然而，由于聚类中心的初始随机选取，并不保证算法可以聚类产生预期的效果，如图1(c)所示的情况发生存在可能性。
图1 K-Means示意图
K-Means算法既有明显的优点，如聚类的速度快(对于大规模的网络数据集而言，运算速度快是必备的)，同时，该算法也有一些缺点，如容易迭代过程中达到局部最优。因此，在进行初始聚类时确定数据的中心非常重要，如果中心选择有偏差，很可能就得不到想要的结果，即使继续迭代下去也无用，前面所做的工作也将前功尽弃，下面将针对聚类初始中心的选择开展改进研究。
3 K-Means算法的改进
本研究对聚类初始中心的选择进行了一些改进，通过每个文本的相似程度进行平均值计算并排序，作为初始聚类算法聚类中心的选择标准。
因为具有这样的特性使得余弦公式非常适合计算网络上不同长度的文本的相似程度，也因此得到广泛的应用。
在计算文本集中一个文本与文本集中其他所有文本之间的相似度后，计算其平均值作为该文本的平均相似度。然后根据计算的平均文本相似度进行排序以确定文本相似度较大的文本作为初始聚类中心。
只有确定好初始中心，K-Means算法才能达到理想又稳定的效果，通常，希望初始中心点为相互之间距离较远的点，但是，基于距离因素找到的孤立点作为中心点的代表性不强，导致聚类的结果不稳定。只有确定初始中心，K-Means算法才能实现了良好、稳定的结果，通常在它们之间的距离越远越好。
通常，选择初始聚类中心分为三大类方法：①随机选择(此方法随意性较大)；②在原有数据集基础上进行直观地分类，通过平均值计算公式计算每个类的中心(此方法也有一定的随机性)；③通过主观检查，凭历史经验选定最具有代表性的点作为初始聚类中心。
一般而言，初始聚类中心至少具有两个特性：首先，作为中心的数据可以较好地代表数据集一部分数据，与一部分数据具有紧密的相关性；其次，稀疏的中心点分布，即作为中心的数据之间距离尽可能远，分布较散，不集中于某个区域。
首先构建一个矩阵M，定义如下：
是指求一个文本与其他文本(n-1个)的文本相似度取平均值。
K-Means算法改进后首先计算平均文本相似度，然后对集合P进行排序，从中选择最大的作为中心点并删除与选中文本簇相关的文本，多次重复上述步骤，直到有k个中心点，如果P为空集且中心点个数小于k时，然后把之前被删除的内容重新添加到集合中，选择中心点。在获得的k个中心点确定为初始中心点之后，执行K-Means算法。
算法流程如下：
1)基于公式(4)，计算文本相似度，构建矩阵M。
2)基于公式(5)构建一个集合P，并对其进行排序，按照升序的方式即可。
3)建立初始中心点集I和删除集，均设置为空集。
4)在集合P中选择最大的一个所对应的文本d[，j]作为一个中心点，并将其加入初始中心点集中，即
。
6)判断是否P=ф、i＜k，如果条件为真，则将Delete中的数据覆盖到P中，即P=Delete。
7)除非满足终止条件，即i=k，否则重复执行3)、4)、5)、6)，最终得到k个初始聚类中心点。
8)根据余弦公式计算每个类簇的中心文本与其他文本的文本相似度，根据相似度大小，将与类簇中心相似度最大的文本放到该簇中。
9)计算
，重新得出各个类簇的中心。
10)除非满足终止条件，否则重复执行8)、9)。
综上所述，K-Means算法改进的重点就是初始中心的选择。在初始中心选择上必须注意的是要根据平均文本相似度排序情况依次选择相似度最大的文本，只有这样才能保证选出的中心点与数据集中的数据有较大的相关性，能更优地代表一部分数据，保证了中心点分布的均匀。
4 聚类性能的实证对比
4.1 实验数据的获取
新浪微博数据采集的内容包括一段时间内微博用户发布的博文内容和发布时间。首先，需要设置采集规则，包括：在新浪微博的用户列表页面上，采集用户微博主页地址的种子URL的正则表达式；在新浪微博用户的微博主页上，获取博文的作者、正文文本和发布时间的正则表达式。然后，根据预先设置的正则表达式，通过http协议应用多线程并行采集种子URL对应的html网页，再对采集到的网页进行匹配，获得作者、正文文本、发布时间等数据并存储到数据库中，形成结构化的数据集。微博数据采集属于微博热点话题检测的前期准备工作，因此，本研究选用专业的网络数据采集处理软件LocoySpider来完成新浪微博数据的采集。
从采集的数据中选取文档内容长度适合话题检测的微博共2188条。针对新浪微博页面中内容对象的抽取示例如表1所示。
表1中序号为2、3、4、5的微博文本均是原创微博，序号为1、6的微博文本中包含字符串“//@”，这是表征回复关系的符号，称为回复符号。回复符号之前是本帖文本内容，之后是被回复帖的文本内容，如序号为6的微博文本与序号为5的微博文本为回复关系。如果能满足微博字符限制(通常140个字)，一个微博文本可以包含多个回复符号，即包含多个被回复的微博文本，如序号为1的微博文本。
4.2 实验数据处理
4.2.1 对微博文本集的向量空间表示 通过分词系统对存储的微博文本进行分词、词性标注处理，并借助维护的停用词表对文本中的词汇进行过滤后文本信息量将下降到原信息量的55%～80%，在此基础上利用前面章节论述的特征项的选择、权值计算方法进行特征项选取和权值计算，然后基于计算的权值结果，构造微博文本的特征项矩阵，在数据库中以临时表的形式存在，如图2所示。
4.2.2 对微博文本的聚类 在Visual Studio 2005平台中实现了改进的K-Means聚类算法，将微博文本的特征项矩阵作为输入，得到测试集中各微博的文本聚类结果。聚类结果如图3所示。
图2 微博文本特征项矩阵的存储
图3 聚类实验结果
4.3 聚类性能对比
聚类性能对比是为了检验改进的聚类算法相比原有的聚类算法在性能上是否得到提升，是否基本满足本课题研究的需要，本研究基于已经通过人工标注并分好类的数据分别用改进的和原有的聚类算法重新聚类，并比较聚类后的精度，即通过人工标注的属于某一类的数据在聚类后是否仍在一个类簇中。
笔者选用复旦大学的李荣陆提供的文本分类语料库，以及本研究进行人工标注的已分好类的微博文本集作为两个数据集，并在此基础上进行聚类性能对比。其中复旦大学的文本分类语料库共包含20个类别，从中选取10个类别，每个类别选取100个文本；对于微博文本数据集则设定6个类别，每个类别包含80个文本。见表2。
本实验使用“Ground Truth”方法的常用度量值——精度(Precision)作为评价聚类性能的评价标准。通过对以上两个分好的数据集用改进的和原有的聚类算法进行聚类分析，并计算精度，为了更好更准确地评价聚类性能，本研究共聚类5次，以比较算法精确性和稳定性。
表3和表4分别列出了利用不同聚类算法对数据集1和数据集2进行5次聚类后得到的精度。通过分析表3可以发现，除了第3次聚类，其他4次聚类分析中，改进的K-Means均比原有K-Means算法的精度高。因此，从整体上看改进的K-Means的精度要比原有的K-Means算法高。
图4和图5为改进的K-Means与传统K-Means算法数据集1和2聚类结果稳定性的比较。这两个图显示，改进的K-Means算法精度值均为0.81，而原有的K-Means算法的精度始终低于0.81这个数值，且数值忽高忽低。所以改进的K-Means聚类具有较好的稳健性。
图4 数据集1聚类结果的稳定性比较
由于对原有K-Means算法进行了一些改进，最初的聚类中心点由原有的任意选取变为根据文档的相似程度通过特定的计算得出的。在初次聚类中的中心点较分散，在所有文档中具有典型性，改进的聚类算法使得相同的数据集每次选定的中心是相同的。因此，即使修改现有的数据集中的数据，计算出的精度仍然保持在同一个数值上。改进后的算法的初始中心点已得到改善，相比原有K-Means算法的任意选取中心点，改进的聚类算法显示了出色的稳健性和精确度。
图5 数据集2聚类结果的稳定性比较
5 结束语
基于K-Means算法的舆情监测，参数简单，运算快捷，但也存在稳定性较差的问题，所以本文在研究了该算法的具体机理后对其进行了改进。根据微博中用语灵活的特点，选择用向量空间模型表示微博文本，继而提出了基于文本平均相似度的K-Means算法，保证了文本聚类的质量。越来越多的微博平台允许用户发布图片、音乐或视频等非文本形式的内容，加之通信技术的不断发展，人们渐渐地倾向于图文并茂、影音配合地发布信息。本文只研究了针对文本处理技术，今后可以结合图像、声音和视频的分析处理技术，对微博中的所有元素进行舆情监测。
标签：k-means论文; 聚类论文; 舆情监测论文; 网络舆情监测论文; 文本分类论文; 舆情分析论文; 文本分析论文; 自然语言处理论文; k-means算法论文; 算法论文;