第３６卷第９期 湖北科技学院学报 Ｖ０１．３６．Ｎｏ．９ ２ ０ １ ６年９月 Ｊｏｕｒｎａｌ ｏｆ Ｈｕｂｅｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｓｅｐ．２０１６ 文章编号：２０９５—４６５４（２０１６）０９—０００１—０３ 基于微博热点分析的改进聚类算法 宋华明 （咸宁市公安局 公安科学技术信息规划建设部，湖北 咸宁４３７１００） 摘要：微博中热点话题的自动发现对于舆情监测与研判具有重要的价值和意义，已有的研究 一直在速度与效率之间缺乏有效的平衡。本文在ＫＭｅａｎｓ聚类算法的基础上，提出了一种改进 的ＫＭｅａｎｓＰｌＵＳ算法来试图发现微博的热点话题。通过随机选取的１０ ０００条微博语料对比实 验分析表明，与传统的ＫＭｅａｎｓ算法相比较，ＫＭｅａｎｓＰｌｕｓ算法能够在很大程度上有效提高计算 的速度。 关键词：微博聚类算法；ＫＭｅａｎｓ算法 中图分类号：ＴＰ３１１ 文献标识码：Ａ 一、问题的提出 具系统ＩＣＴＣＬＡＳ２０１５对微博的文本进行分词，并 微博对信息即时分享的特质，使其成为舆情 使用开源工具Ｌｕｃｅｎｅ建立索引库。考虑到本文 观察与研判的最佳窗口，具有相当强的时效性。 主要研究的是微博热点的聚类，所以主要采集的 同时，对微博进行信息分析可以发现社会群体关 信息是微博用户发表或转载的短文本，采集的方 注的热点话题是什么以及受众在这些话题上的倾 式有两类：（１）通过关键词查询的方式来爬取语 向和态度。相关的研究工作已经有不少，如文献 料，分别为用户发布微博内容和以关键字查找的 ［１］提出一种改进的ＣＵＲＥ算法来试图发现微博 方式来爬取数据；（２）通过Ｐｙｔｈｏｎ爬取网页的 中的热点问题；文献［２］则是提出了一种多标签传 ＨＴＭＬ源代码。 播聚类方法；文献［３］结合微博的语言特征，从语 ２．特征向量的提取与筛选 义的角度对微博里面的热话题自动发现技术进行 （１）信息增益 了全面的研究，提出一种基于改进Ｈ—Ｋ聚类算 法的话题发现方法；文献［４］提出一种基于主题词 微博的文本一般较为短小，通常字数被限定 的中文微博热点话题发现方法；文献［５］提出一种 在汉语字符１４０以内，这种短字符集的特征给文 基于离散ＰＳＯ（ＤＰＳＯ）的热点话题发现算法。可 本里面特征词的提取带来了一定的困难，因此我 以看到的是尽管在微博的热点发现问题上已经具 们选择了通过信息增益的方法来进行特征词的提 有各种方法的应用，取得了一定的成果，但也存在 取。与分类中的信息增益不同的是，聚类中的信 一定的不足与局限：在算法设计上效率和速率之 息增益不会去区分每一个类的具体特征。对于某 一间缺乏很好的平衡，基于此本文试图提出一种改 给定的微博文本而言，可以将每一个特征词都 进的微博热点自动发现的聚类算法。 看作是一个类，所以对于信息增益法，进行了以下 二、数据采集与文本的预处理 的改进，如式（１）至（６）所示： １．数据采集 ＩＧ （ ）：ｌｏｇ２（ ＋０．Ｏ１）×ＩＧ（ ） （１） 本文中我们选取了模拟登陆的数据爬取方 其中， 指的是在文本集中出现过ｔ 的文本 式，对新浪微博的语料数据进行采集。在对语料 总数目，ＩＧ（ｔ ）即ｔ 对于聚类对象的信息增益值。 进行了清洗和预处理之后，使用了中科院分词工 ＩＧ（ｔ ）＝Ｈ（Ｄ）一Ｈ（ＤＩｔ ） （２） ・收稿日期：２０１６—０６—２９ ２ 湖北科技学院学报 第３６卷 其中，文档集合Ｄ的信息熵为： Ｈ（Ｄ）＝一∑ｄｉｅｄ（ｐ（ｄ ）×ｌｏｇ２（Ｐ（ｄ ））） （３） 算每个词的信息增益时适当考虑加大其Ｈ（ＤＩｔ ） 的值，降低其ＩＧ 的值；而多字词则是需要增大其 词条ｔ 的条件熵： Ｈ（ Ｉｔ ）＝一∑ｄｉ（Ｐ（ Ｉｔ ）×ｌｏｇ２（Ｐ（ｄ ｌｔ ）））（４） Ｐ（ｄ Ｉｔ ）是特征词ｔ 出现之时，文档ｄ 出现 的条件概率，Ｐ（ｄ ）表示文档 出现的概率。 Ｐ（ｄ ）的计算公式为： Ｐ（ｄ ）＝ＩＷｏｒｄ（ｄｉ）Ｉ／∑ 。ｌＷｏｒｄ（ｄｉ）ｌ 的数目。 ＩＧ 的值，减小其Ｈ（ＤＩｔ ）的值。前期的实验研究 表明，ＩＧ 的阈值设为ＩＧ ＞１．２５的时候结果较 为理想。同时也要对特征向量的信息增益值设置 阈值，选取阈值之内的特征向量。 （３）特征向量权重的计算 （５） 在进行了特征向量的提取与筛选以及特征权 重的计算之后，本文运用了向量空间模型ＶＳＭ （Ｖｅｃｔｏｒ ｓｐａｃｅ ｍｏｄｅ１）将提取到的特征词转化为机 Ｗｏｒｄ（ｄ ）表示的是在文档ｄ 中的不同词条 Ｐ（ｄ ｌｔ ）的计算公式为： Ｐ（ｄ ｌｔ ）＝ｌ Ｗ０ｒｄ（ｄ ）ｌ／∑“ＤＩＷｏｒｄ（ｄ Ｉｔ ）Ｉ （６） 器可以识别的语言，并使用了ＴＦＩＤＦ算法对每个 特征词进行权重计算。假设待聚类的微博文本有 ， ，…， 篇，在经过了信息增益法对特征向量 １ｗｏｒｄ（ｄ Ｉｔ ）Ｉ代表出现词条ｔ 的文档ｄ 中 不同词条的数目。Ｈ（Ｄｌｔ ）代表已知文本集中有 词条ｔ 时，其他所有词的信息量，用整个文本集的 信息量Ｈ（Ｄ）与Ｈ（Ｄｌｔ ）相减，即可以知道词条ｔ 在文本集中的信息量。 （２）特征向量的筛选 进行了提取和筛选之后，有ｔ，，ｔ：，…ｔ 个特征词， 对每个特征词在微博文本中的特征权重进行计 算，设其为 ¨则微博文本的向量空间模型如表１ 所示： 表１微博文本集的向量空间模型 由于不是所有的特征项都具有文本区分的能 力，因此在进行信息增益的计算之时，需要对前期 ＩＣＴＣＬＡｓ２０１５分词器分出的所有词都进行信息增 益值的计算，同时也要对这个特征向量集进行一 定程度的降维处理。 经过预处理的分词文本中有单字构成的词， 也有多字词，相比较的话单宇词一般而言的多义 性更强。因此对于字长小于等于１的词条，在计 Ｉｎｐｕｔ：ｓｅｅｄ值（种子数），文本集 ，目标簇ｋ的个数 Ｏｕｔｐｕｔ：ｋ个簇集 Ｓｔｅｐｓ： 三、微博热点的聚类算法研究 １．ＫＭｅａｎｓ算法 ＫＭｅａｎｓ算法是一种经典的聚类算法，其算法 流程可以参考文献［６］，如表２所示： 表２ ＫＭｅａｎｓ算法流程 １．待聚类文本集 中随机选取ｋ个文本作为初始簇的中心，Ｓ（｛ｓ …一，Ｓ …“，Ｓ ｝； ２．度量已处理文本与未处理文本的见得距离ｄ （Ｘ ，ｓ，）； ３．形成新的簇集Ｇ＋｛Ｃ …一，Ｃ …一，Ｃ ｝，对文本和距离其最近的中心点进行匹配； ４．重新计算ｋ个簇的中心； 将虫！Ｉ 点定义 初始 强点．ｒｅｐｅａｔ ２至４步骤．直到中心点稳定 ２．ＫＭｅａｎｓＰ１ＵＳ算法 不再根据ｓｅｅｄ值随机选择ｋ个点作为初始点，这 种改进、加强版的ＫＭｅａｎｓ算法优化了初始点选择 由于ＫＭｅａｎｓ算法给定的生成簇的个数的条 件下需要初始的ｓｅｅｄ值，并且对初始点的选择也 较为敏感，初始值的不同通常会形成不一样的聚 类结果。在具体的研究中如果要提高聚类结果的 准确度，一般需要对初始点的选取进行参数优化。 为了解决这一问题我们提出了ＫＭｅａｎｓＰｌｕｓ算法， 的问题。它的基本思想是：增大了初始中心点是 真实中心点的概率，使各初始聚类中心之间的距 离尽可能的远，以此来提高聚类结果的准确率。 ＫＭｅａｎｓＰｌｕｓ在初始点选择上的算法步骤如表３所 示： 第９期 宋华明 基于微博热点分析的改进聚类算法 表３ ＫＭｅａｎｓＰｌｕｓ算法 ３ Ｉｎｐｕｔ：：目标簇的个数ｋ，ｓｅｅｄ值（种子数）ｓ，文本集ｘ Ｏｕｔｐｕｔ：：初始中心点集 Ｓｔｅｐｓ： 根据ｓｅｅｄ值在待聚类文本集 中选取一个文本作为初始中心点集的第一个中心点； 计算剩余的文本与当前中心点的距离ｄｉｓ（Ｘ ，Ｓ）； 将ｄｉｓ（Ｘ ， ）最大的点作为下一个中心点； 重复２至３步骤，直到找出ｋ个初始点。 四、实验与讨论 次聚类算法的时间要高于Ｋ—ＭＥＡＮＳ算法的运 行时间。因此，与层次聚类算法相比较的话， ＫＭｅａｎｓＰｌｕｓ算法具有更好的性能。 表４层次聚类算法聚类结果 １．算法评估标准 本文采用Ｆ值作为聚类性能的评价标准，公 式如式（７）所示： ＝ （７） Ｐ为信息检索中的查准率（Ｐｒｅｃｉｓｉｏｎ），Ｒ为信 息检索中的查全率（Ｒｅｃａｌ１）， 为参数。Ｆｌ值统 筹度量了查准率和查全率，Ｆ１值表征了算法效率 值。 ２．Ｋ—ＭＥＡＮＳ聚类与层次聚类比较 这部分我们结合了统计与人工识别的方法， 从抽取的微博语料中随机选取了１０ ０００条数据进 表５ ＫＭｅａｎｓＰｌｕｓ算法聚类结果 行算法测试，并通过人工的方式对这１０ ０００条数 据进行了话题的再分类。以六个话题类别作为标 签，也就是将参数的初始值设定为６，分类的主题 分别是：“国考”、“双十一”、“春节”、“考研”、“雾 霾”、“踩踏事件”。运用凝聚层次聚类与 ＫＭｅａｎｓＰｌｕｓ聚类算法对数据进行聚类，并对二者 的聚类结果采用算法评估标准中的查准率（Ｐ）、 查全率（Ｒ）以及Ｆ１值进行评估，从而更直观的比 较二者的聚类效果。聚类比较结果如表４、表５所 示。图１为二者运行时间的比较图。 ’●啪● 五、结语 本文提出了一种基于传统ＫＭｅａｎｓ算法的改 进聚类算法——ＫＭｅａｎｓＰｌｕｓ算法，这种算法提出 的意义主要在于能够对初始聚类中心的选择进行 了优化，以此能够显著提高聚类结果的准确度。 同时，实验结果也表明Ｋ—ＭＥＡＮＳ算法的聚类效 ｌ２ｏｏ ｌ∞Ｏ 锄 ●删， 棚 … ，＼ 一－ 一 ｜ 入 产● 一一… 果略优于层次聚类算法的聚类效果，并且随着特 征项数目的增加，Ｋ—ＭＥＡＮＳ算法聚类的时间复 杂度远低于层次聚类算法的时间复杂度。 参考文献： ｊ∞ ，。 ” ｌ聃 ２２— ２３２ ２４２ ２｛２ ２４２ ［１］杨长春，周猛，叶施仁，等．基于改进ＣＵＲＥ 图１ 层次聚类与ＫＭｅａｎＰｌｕｓ聚类运行时间比较分析 算法的微博热点话题发现［Ｊ］．计算机仿真， ２０１３，３０（１１）：３８３—３８７． 对比两种算法实验的结果，层次聚类算法和 ＫＭｅａｎｓＰｌｕｓ聚类算法在微博文本聚类方面，在查 ［２］陈羽中，方明月，郭文忠．面向微博热点话题发 现的多标签传播聚类方法研究［Ｊ］．模式识别与 人工智能，２０１５，２８（１）：１—１０．（下转第５２页） 准率、查全率以及Ｆｌ值等几个指标上差距较小， 具体数据见表４、表５。但随着特征项的增加，层 ５２ 湖北科技学院学报 第３６卷 ｓｔｏｎｅ，ａｎｄ ｔｈｅ ｐｏｅｔｒｙ ｉｎｓｃｒｉｐｔｉｏｎ ｗａｓ ｅｎｇｒａｖｅｄ ｗｉｔｈ ａ ｃｏｐｙ ｖｅｒｓｉｏｎ ｏｆ Ｃｈａｉｒｍａｎ Ｍａｏ’Ｓ．Ｍａｏ’Ｓ ｃａｌｌｉｇｒａｐｈｙ ｉｓ ｎａｔｕｒａｌ，ｕｎｓｔｒａｉｎｅｄ ａｎｄ ｐｉｔｈｙ．Ｉｎ ｔｈｉｓ ｐｏｅｍ， Ｃｈａｉｍａｎ Ｍａｏ ｄｅｐｉｃｔｅｄ ｇｒｒａｎｄ ｓｃｅｎｅｒｙ ｏｆ ｌａｔｅ ａｕｔｕｍｎ ｉｎ Ｃｈａｎｇｓｈａ，ｄｅｃｌａｒｉｎｇ ｈｉｓ ｐａｔｒｉｏｔｉｓｍ ａｎｄ ｗｉｌｌ ｔｏ ｉｆｇｈｔ ｆｏｒ Ｃｈｉｎｅｓｅ ｐｅｏｐｌｅ． 株潭含有岳麓山景区（５Ａ）、刘少奇故居和纪念馆 （５Ａ）、韶山毛泽东故居和纪念馆（５Ａ）、杨开慧故 居和纪念馆、炎陵县红色旅游景区（４Ａ）等八大红 色旅游景区。这些景区在湖南红色旅游景区中影 响力极大，其相关的英文介绍也比较多，为翻译实 践基地的建立和实践操练提供了丰富的研究资 通过比较试译的译文与网站提供的译文，我 们可以清楚地看到两者的区别。网站提供的译文 仅仅翻译了词碑位置、制作材料和碑文来源，漏译 了字体的特点，没有增补任何关于《沁园春・长 沙》诗词的文化内涵和赞扬诗人的爱国之情。同 时，该译文在一些表达方面欠佳，如“毛主席”译成 “Ｐｒｅｓｉｄｅｎｔ Ｍａｏ”，“Ｐｒｅｓｉｄｅｎｔ”常用于西欧国家的 总统，如克林顿总统“Ｐｒｅｓｉｄｅｎｔ Ｃｌｉｎｔｏｎ”，虽都是国 家的最高领导人，但“毛主席”的称呼已成为国人 心中的一座永远铭记的丰碑，不容被随意更改，所 以我们仍沿用“Ｃｈａｉｒｍａｎ Ｍａｏ”这一译名。该词碑 上的碑文是毛泽东１９６１年１０月１６日手书水印 木刻《沁园春・长沙》复制稿制作而成，“水印木 刻”是我国的一种独特印刷方法，专门用来复制画 料。经实地调研和网站信息搜集，我们发现红色 旅游景区文本翻译存在大量的问题。翻译人员的 不规范化、公示语翻译中的胡译乱译、机器式英语 表达和文化误译、翻译文本印刷错误和英语翻译 资料的缺乏等都阻碍了红色文化的对外宣传。 目前，很多高校在红色旅游景区设立了爱国 教育基地，定期组织教师和学生去参观学习，进行 爱国教育。如果各高校与红色旅游景区进行互帮 互助，在景区建立红色旅游文本翻译实践基地，以 红色旅游景区的文本翻译资料作为翻译实践素 材，基于任务式和翻译工作坊式的翻译教学方法 开展实践操练，并定期修正和更新红色旅游景区 的文本翻译资料。教师在翻译教学中结合高校的 优质资源与红色旅游景区的第一手资料，不仅有 利于提高学生的实践翻译能力，更有利于将红色 旅游爱国教育引进课堂，提高红色文化的对外宣 传。 三、结语 作、诗词等手迹艺术品，印刷复制制作的成品，能 保持原作的风格，被誉为“再创造的艺术”。对于 “水印木刻”这一词语很难用一个贴切的词汇表 达，即使用注释法补充说明也让人晦涩难懂，但其 本义就是指该碑文上的字迹不是诗人的真迹而是 其复制品，所以我们直接译为“ａ ｃｏｐｙ ｖｅｒｓｉｏｎ ｏｆ Ｃｈａｉｍａｎ ｒＭａｏ—Ｓ’。除此之外，我们借鉴了翻译大 师许渊冲对该诗词名的翻译名，并增补了该诗词 要表达的意境和寓意。因此，我们的试译文比网 站提供的译文严谨，更加符合红色旅游文本对外 宣传的要求。 （三）红色旅游文本翻译实践基地的建立 在湖南省八大国家级红色旅游景区群中，长 红色旅游文本翻译是对外宣传红色文化的主 要途径，优质的红色旅游文本翻译不仅维护了我 国对外宣传的形象，也有利于目的语接受者客观 地了解中国的革命发展史和红色文化软实力的对 外宣传。在英语翻译教学中渗透红色旅游文本翻 译，能让更多的英语人才参与红色文化的宣传，既 能培养学生的爱国情怀、提高学生的实践翻译技 能，更能实现红色旅游文本翻译又快又好地发展。 （上接第３页） ［３］豆康康．基于改进Ｈ—Ｋ聚类算法的热点话 题发现方法［Ｄ］．哈尔滨：哈尔滨工程大学， ２０１４． ［５］马慧芳，吉余岗，李晓红，等．基于离散粒子 群优化的微博热点话题发现算法［Ｊ］．计算机 工程，２０１６，（３）． ［６］沈睐基于微博文本的话题聚类研究与实现［Ｄ］． 石家庄：河北科教大学，２０１４． ［４］叶成绪，杨萍，刘少鹏．基于主题词的微博热点话 题发现．［Ｊ］．计算机应用与软件，２０１６，（２）：４６～５０．