基于改进k-means算法的微博舆情分析研究-谢修娟.pdf

《基于改进k-means算法的微博舆情分析研究-谢修娟.pdf》由会员分享，可在线阅读，更多相关《基于改进k-means算法的微博舆情分析研究-谢修娟.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、CN 43-1258TPISSN 1007130X计算机工程与科学Computer Engineering 8L Science第40卷第1期2018年1月V0140No1。Jan2018文章编号：1007130X(2018)01015504基于改进K-means算法的微博舆情分析研究。谢修娟1，李香菊(1东南大学成贤学院计算机工程系，江苏南京210000；21，莫凌飞2东南大学仪器科学与工程学院，江苏南京210000)摘 要：为避免初始聚类中心选取到孤立点容易导致聚类结果陷入局部最优的不足，提出一种基于密度的K-means(聚类算法)初始聚类中心选择方法。该方法首先计算每个数据对象与其它数据

2、对象间的平均相似度，找出平均相似度高于某固定阈值的对象视作核心对象，再从核心对象中选取彼此间最不相似的作为初始聚类中心。通过自构建的新浪微博抓取工具，分别抓取不同类别的数千条数据，经过分词、预处理及权重计算后，用改进的Kmeans算法对其进行聚类分析，查准全率较传统的Kmeans算法要稳定，聚类的平均时间也得到缩短。实验结果表明，改进后的算法在微博聚类中有更高的准确性和稳定性，有利于从大量的微博数据中发现热点舆情。关键词：微博；聚类中心；Kmeans聚类算法；密度中图分类号：TP301 文献标志码：Adoi：103969jissn1007130X201801023Microblogging o

3、pinion analysis basedon an improved K-means algorithmXIE Xiuj uanl。LI Xiangj u1。MO Lingfei2(1Department of Computer Engineering，Southeast University Chengxian College，Nanjing 210000；2School of Instrument Science and Engineering，Southeast University，Nanjing 210000，China)Abstract：In order to avoid sel

4、ecting isolated points as the initial clustering center which can causeclustering results to fall into local optimum，we propose a new Kmeans(clustering algorithm)initialclustering center selection method based on densityThis algorithm firstly calculates the average similarity between each data objec

5、t and the others，and finds the core objects whose average similarities arehigher than a fixed thresholdThe least similar core object to each other is taken as the initial clusteringcenterWe build a crawler for Sina Microblog to grab thousands of different types of dataAfter dividing words，pretreatme

6、nt and weight calculation，we use the improved Kmeans algorithm for clusteringanalysisCompared with the traditional Kmeans algorithm，our proposal has a more stable precisionfull ratio，and the average clustering time is also shortenedExperimental results show that the improved algorithm has higher acc

7、uracy and better stability in microblog clustering，and can be used in discovering public opinion from a large number of microblog dataKey words：microblog；clustering center；Kmeans clustering algorithm；density引言随着媒体技术的不断进步和信息传播渠道的日趋多元化，当今社会进人了“人人都是新闻传播者”的自媒体时代。广大网民参与言论的热情高涨，特别是微博的兴起，网民可以通过电脑、手机随时随地发表言

8、论。新浪微博Twitter叫类的新收稿日期：2016-0222；修回Et期：2016-0616基金项目：江苏高校哲学社会科学基金2016SJD880186)i江苏省现代教育技术研究课题(2016-R一46509)；“十二五”国家科技支撵计划(2013BAJ058022)通信地址：210000江苏省南京市江宁区天元中路武夷绿洲小区观竹苑29203Address：Room 203，Building 29，Guanzhuyuan Wuyi Lazhou Residential Area，Tianyuan Middle Rd，Jiangning District，Nanjing210000，Jiang

9、su，PRChina万方数据156 Computer Engineering&Science计算机工程与科学2018，40(1)兴网络应用，自2009年推出，截至目前，注册用户已超过5亿，月活跃用户数约为2亿，用户每日发博量突破1亿条口。可见，微博上的舆论已成为网络舆情中极具影响力的一种。如何从海量数据中快速有效地发现网民关注的热门话题?从而引导政府相关部门及时捕捉微博中敏感的舆论信息，合理地控制负面舆论的扩散。目前，很多政府机关采用全人工或是半自动的监测统计方法，效率低，准确度也低口“。因此，迫切需要一种更为有效的微博热点话题发现方法。Kmeans口1是一种最为经典、使用最为广泛的划分聚类算

10、法，经常被用于网络舆情的聚类中。但是，其使用有一定的局限性6。8：(1)需要事先确定聚类数；(2)初始聚类中心的选择方法不一，选取不当，往往导致最终聚类结果陷入局部最优。针对上述情况，研究者从不同角度提出一系列改进的Kmeans算法，文献9利用文档标题的稀疏相似度，确定Kmeans算法的初始聚类中心；文献10提出用凝聚的层次算法干预Kmeans算法的随机选取聚类中心的方式，保证最终的初始聚类中心更具有典型性；文献11提出使用二分思想递归分裂相似度大于给定阈值的簇，合并相似度小于阈值的簇，来获得聚类簇数。本文提出一种基于密度的Kmeans聚类算法，对传统的Kmeans初始聚类中心选择方法进行改进

11、，并将改进后的算法用于新浪微博的聚类中，以期能更快、更准确地对最近的微博数据进行聚类，以便发现微博热门话题。2相关的定义定义1微博文档的表示：采用空间向量模型VSM(Vector Space Model)，b：=(1(6。)，硼2(6：)，硼，(6：)，W。(b，)，Wj(6。)表示第歹个特征项在微博文档b，中的权重，本文权重计算采用TFIDF方法，砌一tfidf，tf指特征项在某微博文档b，中出现的次数，idf是特征项在微博文档集b。中出现频率的量化。为了降低高频特征项对其它中低频特征项的抑制作用，需要对特征向量进行归一化处理，处理后的权重计算公式如下： 毗)一i誓些坐坠堡些：；。tf，(移

12、。)2In2(Nn，+001)其中，f厂，(6，)是指第歹个特征项在b。中出现的次数，N是所有微博文档的个数，n，表示包含第J个特征项的微博文档的个数，n是b：中特征项的总个数，分母为归一化因子。定义2两个微博文档bi和b，之间的相似度similarity(6：，bj)定义为两个向量对象在状态空间方向上正交的可能性，用这两个向量的夹角余弦COS 0。表示，若完全正交，表示两文档毫无相似性，点积为0。夹角余弦COS 0。采用如下的计算公式：COS巩一羔三!垒篓兰：一，6：。6：其中，b；、bjk分别表示文档6，和b，第矗个特征项的权值，1是N。定义3 Kmeans目标收敛函数：E一2，。“J x

13、m：I 2，Kmeans聚类过程中，E的值是变化的，当E趋向一个极小的固定值时，意味着聚类结果趋于稳定，聚类结束。其中，E表示所有聚类文档的误差平方和，X是聚类簇C，中某个聚类文档，m，是每个聚类簇c，内所有聚类文档的均值。定义4密度density：给定文档集合BL，bBL，文档b的密度定义为该文档与其它文档的平均相似度，采用如下的计算公式：density(6)一，BLsimilarity(了，b)Nm其中，分子是文档b与其它文档两两间的相似度之和，分母是BL所包含的文档数。定义5核心文档：若文档b的密度大于或等于给定参考值refSimilarity(大于o)，则该文档是核心文档，refSim

14、ilarity称为密度阈值。通过计算密度得到核心文档，能有效地规避噪声文档，避免初始聚类中心取到孤立点而导致聚类结果陷入局部最优。采用反证法：假设噪声点是核心文档，而其与各个文档间极不相似，根据定义2和定义3，噪声文档的密度约为0，这与核心文档的定义相冲突，因此，核心文档不可能是噪声文档。3改进的K-means聚类算法31基于密度思想的初始聚类簇中心选择算法借鉴DBScAN密度聚类思想，本文提出一种初始聚类簇中心选择算法InitialCenters，首先找出所有核心微博文档，选取K个相互间最不相似的核心文档作为初始聚类中心。InitialCenters算法流程描述如下：输入：微博文档集合blo

15、gList=b。，6。，b。；聚类簇数K；密度阈值vefSimilarity。万方数据谢修娟等：基于改进Kmeans算法的微博舆情分析研究 157输出：初始聚类簇中心centers=cl，C2，CK。Step 1对于给定的微博文档集合blogList，求出任意两个文档间的相似度，保存至相似度矩阵docSimilarity中；Step 2根据相似度矩阵docSimilarity，计算每一个文档与其它文档两两之间的平均相似度，找出平均相似度高于密度阈值的文档，形成核心文档集合coreDocs；Step 3将coreDocs中的第一个核心文档作为第一个初始聚类中心点centers1，并从coreDo

16、cs删除该文档，令计数变量nk一1，同时，将centers1置为当前聚类中心点；Step 4遍历coreDocs剩余核心文档，选择与当前聚类中心点最不相似的文档作为下一个初始聚类中心点，添加到centers中，并从coreDocs删除该文档；Step 5更新当前聚类中心点，并使nk=nk+1，转Step 4；Step 6重复Step 4和Step 5，直至n与聚类簇数K值相等为止，输出centers，算法结束。32改进的K-means聚类算法将InitialCenters算法所得到的初始聚类簇中心，再按照传统的Kmeans算法重复迭代，得到最终的微博数据聚类结果。给定微博文档集合blogLis

17、t=bl，bz，”，b。，初始聚类簇中心点集合centers一C1，C2，CK)，初始化聚类簇clusters一clul，clu2，cluK)，K为聚类数。其具体步骤如下：Step 1计算每个微博文档b。与每个初始聚类簇中心点的相似度，并将b归入到与其最相似的簇clusters中；Step 2重新计算簇中心，若中心发生变化，更新聚类簇中心为centers7=C：，f；，c：)，同时清空clusters，开始下一轮聚类；Step 3重复迭代Step 1和Step 2，直到准则函数E收敛；Step 4输出最终聚类结果。4实验过程与结果分析41实验过程设计本文将使用相同的数据源对传统的Kmeans算

18、法以及改进后的Kmeans算法进行对比实验，以验证本文提出的改进算法在聚类效果上的优越性。首先构建了一个抓取新浪微博的API，选取一些时下比较热门、关注度高的词条作为关键词抓取数据。本实验分别以“春晚”“逼婚”“芈月传”“环卫工”为关键词抓取了每个类别最近发表的1 000条微博数据，为保证数据的有效性，经人工过滤，从每个类中选取200条字符长度在15以上的微博，共计800条数据，作为此次实验的训练测试集。采用中国科学院ICTCLAS分词系统对微博数据进行分词、词性标注处理，并借助停用词表对分词结果中的词汇进行停用词过滤，而后使用定义1提及的TFIDF方法构造微博数据的向量空间模型(VSM特征项

19、矩阵)，来实现微博文本聚类。42实验结果分析本文采用F度量值n21作为聚类结果的评价标准。该方法同时兼顾了查准率(P)和查全率(R)两个指标，P和R分别由下面的计算公式得到。PTP(TP+FP)RTP KTP+FN、其中，TP为正类被划分为正类的文档数，即聚类的正确文档数，FP为负类被划分为正类的文档数，FN为正类被划分为负类的文档数，TP+FP表示实际分类的文档数，丁P+FN表示应有的文档数。为更客观地评价聚类性能，本研究对传统的算法进行多次随机选择初始聚类中心完成聚类，对本文提出的初始中心选择算法，也是选取了多个密度阈值进行聚类，分别取各自最佳的一次结果。参数的取值情况为：传统的Kmean

20、s算法，初始聚类中心为(3，102，456，617)，改进后的K-means算法密度参考值为0036 25。表1是传统的Kmeans算法与改进后的Kmeans算法的F值的实验结果。Table 1 F value comparison between the traditional K-meansalgorithm and the improved K-means algorithm表1与传统的K-means算法的F值比较微博数据类僦蔑”改警毽褫“5从表1中不难发现，改进后的聚类算法F值相对比较稳定，而不像传统算法F值上下波动比较大，此外，改进后的算法总体的聚类准确度有所提高，表1中，除了“逼婚

21、”这一类别偏低，其它三类都比传统算法的F值高。可见，运用改进后的Kmeans算法对四个关键词近4 000条的微博数据进行聚类，所得到的聚类簇基本与事实数据一致，从每个簇中的特征项可以很快获得舆论关注的热点，以“春晚”为例，最近讨论比较多的是“六小龄童”“春晚主持人”“春晚吉祥物”“节目单”等，其中“六小龄童”热度最高。再者是运行时间，虽然改进后的算法在计算初万方数据158 Computer Engineering&Science计算机工程与科学2018，40(1)始聚类中心时有一定时间消耗，但是从几次实验来看，聚类过程中的迭代次数少了，因此最终的运行时间成本反而降低了。为验证改进算法的时间效率

22、，在传统算法以及改进算法的多次实验中，分别选取具有代表性的四次聚类时间进行比较，图1直观地显示了改进后的算法在运行时间上所表现出的优越性。可见，改进后的Kmeans算法不仅提高了微博聚类的正确性、稳定性，而且提高了运行效率，运用改进的Kmeans算法对一段时间内的微博数据进行聚类，能够快速、准确地发现舆情热点话题。13012 5i20兰芎1l 5盅11010510 0一j篡兰手1一一改进后的Knsr- ， ，尸，7- 、i2 3 4四次结果Figure 1 Comparation of time t图1时间t值的比较5 结束语本文借鉴了密度聚类算法DBSCAN的思想，对Kmeans的初始聚类中

23、心选择方法进行优化，提出在平均相似度较高的核心文档中找出相互间最不相似的文档作为初始聚类中心，以消除初始聚类中心选取到孤立点可能导致聚类结果陷入局部最优的不良影响，并将改进后的算法应用于微博数据的聚类中。实验结果表明，改进后的算法在聚类的准确性和时间效率方面都有一定的优势，可以用其对微博数据进行聚类分析，以发现一段时间内的微博舆情热点。参考文献：E132343Yu L I。Asur S，Huberman B ATrend dynamics and attention in Chinese social mediaJAmerican Behavioral Soientist，201 5，59(9

24、)：11 42-1156Wei YangEnterprise negative network public opinion propagation characteristic research based on the sina weiboDHefei：Anhui University，2013(in Chinese)Yi ChenheEmergency evolution law of network public opin-ion and government monitoringDXiangtan：Xiangtan University，2014(in Chinese)Zhang 1

25、ijuanThe countermeasure research of network public opinion guide of the local governmentJChina Management Informationization，2015，】8(18)：203204(in Chinese)5678393101112Takens FDeterming strange attractors in turbulenceMLecture Notes in MathematicsBerlin：Springer Berlin Heideberg，1981：339359Yuan Fang

26、，Zhou Zhiyong，Song XinKmeans clustering algorithm with meliorated initial centerJComputer Engineering，2007，33(3)：6566(in Chinese)Tang Xiaoqin，Dai RuyuanTechnique of cluster analysis indata miningJMicrocomputer Information，2003，19(1)：34，(in Chinese)Yang Zunqi，Zhang QiannanResearch on attention of mic

27、roblog users based on Kmeans cluster analysisJ3Journalof Intelligence，2013，32(8)：142144(in Chinese)Tang Hanqing，Wang Han-junApplication of improved Kmeans algorithm to analysis of online public opinionsJComputer Systems&Applications，2011，20(3)：165168(inChinese)Luo Hui-xiaQu Xiao-lingThe improvement

28、of Kmeansclustering algorithm based on internet public opinionJComputer Development&Applications，2010，23(8)：4-6(in Chinese)Zhang Zhongping，Wang Ai-jieChai XuguangEasy andefficient algorithm to determine number of clustersJComputer Engineering and Applications，2009，45(15)：166168(in Chinese)Zhong Jian

29、g，Liu RonghuiImproved KNN text eategorizationJComputer Engineering and Applications，2012，48(2)：142144(in Chinese)附中文参考文献：2 魏杨基于新浪微博的企业负面网络舆情传播特征研究D合肥：安徽大学，20133易臣何突发事件网络舆情的演化规律与政府监控D湘潭：湘潭大学，20144 张李娟地方政府网络舆情引导的对策研究J1中国管理信息化，2015，18(18)：2032046袁方，周志勇，宋鑫初始聚类中心优化的Kmeans算法J计算机工程，2007，33(3)：65667汤效琴，戴汝源数

30、据挖掘中聚类分析的技术方法J微计算机信息，2003，19(1)：3-48杨尊琦，张倩楠基于Kmeans算法的微博用户推荐功能研究J情报杂志，2013，32(8)：1421449汤寒青，王汉军改进的Kmeans算法在网络舆情分析中的应用J计算机系统应用，2011，20(3)：165168103 罗晖霞，曲晓玲基于网络舆情的KMeans算法的改进研究J电脑开发与应用，20Io，23(8)：4-611张忠平，王爱杰，柴旭光简单有效的确定聚类数目算法J计算机工程与应用，2009，45(15)：166168123钟将，刘荣辉一种改进的KNN文本分类J计算机工程与应用，2012，48(2)：142144作者简介mlnlng谢修娟(1981一)，女，江苏高邮人，硕士，讲师，研究方向为数据挖掘。E-mail：xiujuanxie126cornXIE Xiu-juan，born in 1981，MS，lecturer，her research interest includes data万方数据