话题发现范文

话题发现范文（精选6篇）

话题发现 第1篇

关键词：民航领域,网络热点发现,single-pass聚类,网络热点话题

1 引 言

互联网新闻媒体已经被公认为是继报纸、广播、电视之后的“第四媒体”, 虽然互联网进入我国的时间不长, 但是发展十分迅速。CNNIC在2010年7月发布的《第26次中国互联网络发展状况统计报告》显示:截至2010年6 月底, 我国网民规模达4.2亿人, 互联网普及率持续上升增至31.8%。我国当前正处于社会转型期, 各种社会矛盾时有涌现, 互联网本身所具有的匿名性和自由性使得网络成为人们表达自己的意愿, 发泄自身情感的一个最佳场所。近几年来很多具有广泛影响力的公众事件都是最早在网络上被曝光进而引起全社会关注的。通过这些事件的研究表明, 加强对网络舆情的监控和监管力度, 建立合适的疏导机制, 对于构建和谐社会, 稳定社会发展有着至关重要的作用。

热点事件的发现和跟踪是网络舆情监控中非常重要的一个环节, 但是目前对于热点事件发现的研究主要集中在面向全体公众的热点事件的研究, 很少有学者针对某个特定的行业领域的热点事件进行研究。事实上不同领域的从业人员可能更关注本领域的热点事件, 而且面向全体公众和面向特定领域的热点事件研究在信息源的获取和后期处理方法上均有不同之处。本文提出利用single-pass聚类方法, 结合民航领域特点, 实现对网络上关于民航领域热点事件的及时发现。

2 文本聚类

基于互联网新闻报道流的话题发现过程就是一个无指导的文档聚类过程。文档的聚类实际上就是将相似文档划入同一组、不相似的文档划入不同组的选择过程, 其算法的输出一般为不同类文档集合的划分。在所有的文档聚类算法中最常用的是基于层级的聚类和基于划分的聚类。层级式聚类可以表示为树形结构, 树的叶子节点代表了初始的聚类样本, 树的非叶子节点代表了所聚成的类。根据层级分解是自底向上的还是自顶向下形成的, 层级式聚类方法可以进一步分为凝聚的 (agglomerative) 和分裂的 (divisive) 层级式聚类。划分式聚类不同于层级式聚类, 其类别结构简单, 一般没有清晰的层次关系, 算法通过不断的迭代来完成样本数据的最优分配, 但其本质是一种贪心算法, 容易陷入一种局部最优解。这类算法的典型代表是K-means聚类算法、KNN聚类算法等。

热点话题发现的信息源是互联网上连续不断的新闻, 因此除了一般的聚类所必须满足的条件之外, 话题发现中使用的聚类算法还需要满足以下要求:

第一, 快速聚类。

虽然我们采集的对象仅是网上信息很少的一部分, 但其数量依然较大, 而且网上的新闻是不断产生的, 所以算法的效率是一个必须考虑的问题。

第二, 增量式聚类。

网上的新闻是以一种流式的方式到来, 如果每来一条信息就将以前所有的信息和新的信息放在一起重新聚类显然是不可取的, 因此选取的聚类算法必须是一种增量式的聚类, 即新信息的聚类无须对已聚好的类进行更改。

为了满足以上两个特点, 我们采用single-pass聚类算法, 其实质是求与当前文档距离最近的一个类, 在single-pass聚类中一般用类的中心代表该类, 而类的中心定义为该类中所有文档的平均向量。其算法的具体步骤描述如下:

①选择某个文档作为初始类的中心;②按照某种次序, 从尚未分配的文档集合中选择一个新的文档;③计算该文档与当前所有类的距离, 从而得到一个距离最近的类及其与该类的距离值;④如果该距离值小于某个给定的阈值, 则将文档划入该类中, 并更新类的中心;否则以该文档为中心建立一个新类;⑤重复步骤②～步骤④, 直到文档集合中的所有文档都已经被分配给某个类。

single-pass聚类是一种增量式的聚类算法, 具有线性的时间复杂度。single-pass聚类结果的好坏与文档选择的顺序直接相关, 可以通过设置不同的阈值, 来获得不同粒度大小的文档划分。

3 面向民航领域的热点话题发现模型

3.1 基于民航专业词库的网页过滤

从专业的民航网站上抓取的网页基本都是和民航相关的, 因此无须进一步的过滤。但是从普通的网站抓取的网页中大部分都是和民航无关的, 因此在进一步的处理之前必须首先过滤掉无关网页, 否则会产生大量的噪声数据。为了便于过滤我们收集了一个民航专业词库, 该词库共计549个词条, 主要由五个部分组成:民航专业术语、民航机构、航空公司及其缩写、机场及其缩写、民航业内领导及知名专家。

在抓取到普通网站的网页后, 将其网页的内容和民航专业词库进行匹配, 如果发现在网页中出现过3次以上民航专业词则认为它和民航相关, 予以保留, 其余的则不作进一步的处理。这种处理方法虽然比较的简单, 但是在处理大量的网页时非常的有效, 准确率也较高。

3.2 热点话题的量化

话题需要量化后才能进行排序, 也就是说需要采用一定的指标对话题进行打分排序, 进而才能将最热点的事件推荐给读者。通常一个热点话题的发展趋势如图1所示, 也就是说任何一个热点话题都会经过发生、发展、高潮、衰落四个阶段, 因此在选取衡量热度的指标时必须考虑到时间的约束。

根据热点事件发展的特点我们利用如下的指标来考虑一个事件的热度:

•一段时间内同话题i相关的报道数RNi;

•单位时间内同话题i相关的报道数RFi;

•同话题i相关报道的网页访问量VNi;

•同话题i相关报道的评论数CNi。

由于各个指标之间的数量跨度相差很多, 报道数可能只有几十条, 而访问量却有可能达到几千甚至上万, 如果直接采用绝对数值来计算必然会导致很大的误差, 因此在计算之前必须采取某种方式将各个指标的度量统一起来。设抓取到总的网页数为TOTALRN, 单位时间内抓取到的总的网页数为TOTALRF, 总的网页访问数为TOTALVN, 总的评论数为TOTALCN, 某个话题第一次出现的时间为TFIRSTi, 当前时间为TNOWi, 单位时间以1天来计算。结合上述的指标可得话题i的热度计算公式如下:

undefined

公式中充分考虑了上面的四个指标及时间在热点话题发现中的作用, 并且将各个指标的具体数值用其在各自指标中所占百分比来代替, 以此达到消除各个指标之间数量跨度较大的问题, 式中的α和β是两个可调参数, 分别代表当天的报道数和所有的报道数对于话题热度的影响, 这里我们认为当前的报道更能体现话题当前的热度, 因此设置α=0.6, β=0.4。

3.3 热点话题发现模型

图2是本文的热点发现模型, 主要由信息采集、预处理、聚类和热度计算几个部分组成。

(1) 选取特定的网站作为系统的监控源, 由于该监控系统是面向民航领域的, 因此将网站又细化为普通网站和民航类网站。利用Nutch的爬虫模块从网上采集到原始的网页。

(2) 原始的网页需要进行一定的预处理, 对于民航类的网站直接利用HtmlParser解析出网页内容后, 利用中科院的ictclas4j进行分词, 然后利用向量空间模型对网页内容进行表示, 其中权重的计算采用TF-IDF。而对于普通类的网站则首先利用民航专业词库从所有网页中提取出和民航相关的网页, 再完成后续的处理。所有处理后的结果保存在文本文件中。

(3) 利用上述介绍的single-pass算法进行聚类, 得到所有的话题。

(4) 利用上述的热度计算公式分别对每个话题计算热度, 按照得分的高低进行排序, 输出最终的结果。

4 实验与结果分析

4.1 实验数据

我们采集的信息源主要包括两个部分, 民航类网站主要包括民航局官方网站、民航资源网、中国民航信息网等。普通类网站主要包括国内的三大门户网站sohu、sina和163在内的知名网站。

对于民航热点事件并没有一个权威的统计标准, 为了能衡量我们的效果, 我们采用民航业内比较权威的民航资源网上的48小时热点民航新闻作为热点新闻的一个标准。为了方便对比, 我们也采集48小时的数据来和该网站上的进行对比。

最终我们从网上采集到2010年9月28号到9月29号的相关新闻共1967条, 去除不相关网页后剩余273条, 这将作为我们后续实验的数据来源。

4.2 实验结果及分析

通过single-pass聚类一共从273条新闻中得到话题31个, 采用我们的热度计算公式对这些话题分别计算热度, 利用话题中权重最高的3个关键字来代表该话题, 最终得到的热度排行如表1所示:

民航资源网上2010年9月28号到9月29号这48小时的热点新闻如表2所示:

对比表1和表2不难发现, 我们模型得到的热点话题和民航资源网上的热点新闻基本一致, 表2中的10个热点新闻中有7个主题和表1中的话题是吻合的, 这说明我们提出的模型准确率是比较高的。3个未出现的话题主要是由于我们的模型在热度计算方式上和表2中的计算方式不同, 表2中热点的计算主要是依靠点击量和回复数, 而我们除了考虑这两个因素之外还考虑了其他一些指标, 更加的全面和合理。

5 结 论

研究特定领域的热点发现既有学术价值, 也有很广泛的应用前景。本文对面向民航领域的热点事件发现进行了初步的研究, 得到的效果基本令人满意, 但是在民航相关网页过滤上过于简单, 后续的研究中会考虑利用自然语言处理技术更加准确的过滤无关网页。在聚类算法上single-pass基本能满足要求, 但是要想进一步的提高话题发现的准确度必须对single-pass算法进行改进, 尽可能避免其前期聚类错误会不断累积的问题, 这也将在后续的研究中做进一步的探索。

参考文献

[1]孙学刚, 陈群秀, 马亮.基于主题的Web文档聚类研究[J].中文信息学报, 2003, 17 (3) :2-26.

[2]CNNIC.CNNIC发布《第26次中国互联网络发展状况统计报告》[EB/OL]. (2010-07-15) .http://www.cnnic.net.cn/ht-ml/Dir/2010/07/15/5921.htm.

发现为话题 第2篇

漫步在樱花铺满的大道，春风将那莺啼与飘香一同送到我的身边。花瓣不时飘落几片，落在小池中，漾起一圈又一圈的涟漪。蝴蝶与蜜蜂仿佛是一对恋人，在树间跳着华丽的双人舞。远处不时传来几声嬉笑。

我在树丛间寻寻觅觅，只为找到那花彼岸花。看！就在那边！我仿佛是一群海盗的首领找到宝藏似的，两眼放光。当我将要靠近时，却听到了脚步声踏踏我凑前一看，是位老人，一位蹲着的老人。

老人身旁杵着拐杖，他那抚摸着花的手布满了岁月的痕迹；衣服是黑色，仔细看袖口还能看到几处油污；眉宇间也被时光无情地踏了个遍，眼睛却透漏出那种一见钟情般的热切。

来！再拍一张！伴随着几声快门的声音，这喊声令得我和老人看了过去一匹大牛正两脚踩在树杈之间，把那树当成了自己的床般躺了下去！老人顿时嘴角向下一歪，连拐杖都没拿便跑了过去。

老人站在那男人底下，驼着背，右手指着他吼道：你在干什么？男人眼一斜，不屑的说：你个老头管这么多干嘛？我们在拍照！看不见吗？老人带着一副仿佛随时都要用那老骨头干一架的气势喊道：再不走我就喊管理员了！这是违法的！那男人一听，没了先前的理直气壮：真是怕了你了走走走。老人一直瞪着他们离开了视线，才转过头来对着这饱经折磨的树说道：真是辛苦你了。

夕阳的余辉映在老人身上，给他镀上了一层金色的袍。远去，才见老人那上弯的嘴角、深邃的眼眸。

世间的一切美好都要发现。黑夜发现了月光，黑夜不再如此可怕；小路发现了路灯，也不再变得孤寂；人们发现了情感，便有了这个绚丽多彩的世界而我，发现了这个充满温情的世界。

话题发现 第3篇

互联网是继电视媒体、平面媒体之后的又一大舆论传播途径, 而随着网民数量的不断增长, 互联网上的信息也以指数级形式增加, 一方面信息规模急剧增长;另一方面这些信息又杂乱无序[1]。在如此情况下, 传统的人工分类寻找新话题的方法已显得杯水车薪, 代价高且效率低下。话题识别与跟踪系统 (TDT) 就是在这种情况下应运而生[2]。

TDT (Topic Detection and Tracking) 的概念最早产生于1996年, 当时美国国防高级研究计划署 (DARPA) 根据自己的需求, 提出要开发一种新技术, 能在没有人工干预的情况下自动判断新闻数据流的主题。

LDC为TDT方向的研究提供了五期语料, 分别是TDT预研语料、TDT2、TDT3、TDT4和TDT5[3]。TDT语料是选自大量新闻媒体的多语言新闻报道集合。其中, TDT5只包含文本形式的新闻报道, 而其它语料同时包含文本和广播两种形式的新闻报道。

TDT-Pilot标注过程没有涉及话题的定义, 而是由标注人员从所有语料中人工识别涉及各种领域的25个事件作为检测与跟踪对象。TDT2收集了1998年前六个月的中英文两种语言形式的新闻报道。其中, LDC人工标注了200个英文话题和20个中文话题。TDT3收集了1998年10月到12月中文、英文和阿拉伯文三种语言的新闻报道。其中, LDC对120个中文和英文话题进行了人工标注, 并选择部分话题采用阿拉伯文进行标注。TDT4收集了2000年10月到2001年1月英文、中文和阿拉伯文三种语言的新闻报道。其中, LDC分别采用三种语言对80个话题进行人工标注。TDT5收集了2003年4月到9月的英文、中文和阿拉伯文三种语言[4]。

2 TDT话题定义及任务

2.1 话题定义

话题 (topic) 是话题识别与跟踪研究中的一个最基本的概念, 它的含义与语言学上使用的概念有所不同。在研究的最初阶段, 话题的定义与事件相同。话题是由某些条件引起, 发生在特定时间、地点, 并产生某些必然结果的事件。而目前话题的定义相对广泛, 它包括一个核心事件或活动以及所有与之直接相关的事件和活动。如果一篇报道讨论了某个话题的核心事件, 那么就认为该报道与此话题相关.

2.2 研究任务

NIST为TDT研究设立了五项基础性的研究任务, 各个子任务的解决将有助于最终目标的实现。这五个子任务包括[5]:

新闻报道的切分 (Story Segmentation Task) :将原始数据流切分成具有完整结构和统一主题的报道[6];

首次报道检测任务 (First Story Detection Task) :从具有时间顺序的报道流中自动锁定未知话题出现的第一篇相关报道。在TDT中, 新话题的识别都要从检测出该话题的第一篇报道开始[7];

话题跟踪 (Topic Tracking Task, 简称TT) 的主要任务是跟踪已知话题的后续报道[8]。其中, 已知话题没有明确的描述, 而是通过若干篇先验的相关报道隐含地给定;

话题检测 (Topic Detection Task, 简称TD) 的主要任务是检测和组织系统预先未知的话题, TD的特点在于系统欠缺话题的先验知识[9];

关联检测 (Link Detection Task, 简称LDT) 的主要任务是裁决两篇报道是否论述同一个话题。与TD类似, 对于每一篇报道, 不具备事先经过验证的话题作为参照, 每对参加关联检测的报道都没有先验知识辅助系统进行评判。

3 系统设计

3.1 网络语料的采集

本论述主要利用网络爬虫 (Net Crawl) 工具定时采集指定时间、指定站点内的新闻网页。网络爬虫是一个自动从网络上下载网页的程序, 通过网页的链接地址来寻找网页, 从某个初始网页的URL开始, 读取网页的内容, 同时解析出网页中所有URL, 通过URL过滤器将不满足条件的URL过滤掉, 将满足条件的URL加入到待下载的URL队列中, 如此循环, 直到待下载URL队列为空, 或者满足了系统的某个停止条件。

3.2 语料的预处理

3.2.1 正文抽取

通过网络爬虫下载得到的网页大多数都是HTML文档, 在一个HTML文档中一般包含两类信息:提供给浏览器用的HTML标签和提供给用户阅读的文字。而我们所需要的新闻文本是去除各种无用信息后的文字。本论述利用开源项目HTML Parser来抽取新闻语料正文。

3.2.2 藏文分词

藏文分词从应用的角度看, 主要有三种方法:一类是基于字典的分词方法;一类是基于统计的分词方法;一类是基于规则和统计的分词方法。目前藏文分词还有基于格助词和接续特征的分词、切分与格框架等方法[10]。

3.2.3 去除停用词

去除停用词, 主要是去掉一些对文档内容没有什么表现力的字词, 通常采用实词词典和停用词词典进行处理。根据实词词典和停用词词典, 去除那些出现频率高, 对于表达意义的贡献却不大的虚词和停用词。

3.2.4 命名实体识别

命名实体识别 (NE) 是指识别文本中具有特定意义的实体, 主要包括人名、地名、机构名、专有名词等[11]。

4 两层聚类策略

4.1 相似度计算

在对文档进行聚类时, 必定要计算文档与文档或文档与类之间的相似度。文本相似度一般定义为界于[0,1]之间一个值。如果两个文本之间相似度为1, 则说明两个文本对象完全相同, 若为0, 则说明两文本没有相似之处[12]。

在向量空间模型中, 文本相似性的度量有内积法、余弦法和距离函数法等。基中余弦法是较常用的一种方法, 由于文档向量采用词作为向量的特征单元, 因此这个相似度就是这两个文档在内容上的相似度, 计算公式如下[13]:

其中和分别表示文档di和dj向量的模, D (di, dj) 表示文档di与dj之间的相似度, wi, k表示第i篇文档中第k个特征项的权值, n为文档特征项数。D值越大表示两个文本越相似, D值越小则表示两个文本区别越大。

由于事件一般都具有明显的时间特征, 两篇文档即使内容非常相似, 但如果两篇文档中所描述的事件发生的时间间隔太远, 可以认为这两篇文档并不是在描述同一个事件。因此在计算文档与文档之间的相似度时还加入了时间衰减函数T[14]

其中t=|s (di) -s (dj) |, 在文本中, s (di) 被认为就是文件di的创建时间, 而m指的是时间衰减因子, 这样最终得到文档相似度计算公式为:

4.2 两层聚类策略

由于本系统处理的语料规模非常大, 且时间顺序是很重要的特征, 因此系统采用两层聚类策略进行聚类, 主要过程如下[15]:

第一步:对每天下载的新闻语料处理后形成一个按天分组的新闻语料库;

第二步:对于每组内语料采用凝聚聚类算法生成微类, 并利用事先设定的阈值控制生成的微类数量;

第三步:选取用户选择的时间段内所有天的微类, 保持类间的时间顺序, 采用增量式聚类算法对各微类进行聚类。

5 实验结果与分析

实验选择从三个门户网中国西藏信息中心网、西藏家牧经济信息网、中国西藏新闻网三大新闻网站中新闻网页来获取Web资源, 利用计算机自动处理资源, 由于对于计算机获得的热点事件目前没有一个统一的评测标准, 本论述试图通过与权威媒体评测出来的热点事件进行对比, 以此对本系统做出的评测, 与中国网络媒体2010年度新闻风云榜相比, 本系统得到的热点事件中有6个相似。因为权威媒体在评判热点新闻时人为因素比较大, 而本系统在热点事件评判中客观性强, 所以结果必然会存在着一定的差异。

6 结束语

本论述利用两层聚类策略设计了一个事件发现系统, 利用该系统能自动发现网络上任意一段时间内的热点事件, 且能最大限度的减少人工因素对结果的影响, 取得了较好的结果。

在一个事件刚出现时就能预测其以后的发展趋势, 这对于舆论的调控将产生重大的现实意义, 因此建立更加完善的事件发展监控体系也是下一步的重点研究目标。

摘要：针对互联网上新闻网站和论坛、博客等发布的海量自然语言文本, 本文设计了一个面向藏文的话题发现系统, 将大量藏语文本分类整理并聚合成各个话题。本文采用两层聚类策略对文本进行聚类, 实验结果表明文本聚类取得了不错的结果, 具有较高的应用价值。

发现话题作文 第4篇

记得那一次，爸妈不在家。我急匆匆走进学校，发现此时的天已是灰蒙蒙的，弄得我快喘不过气来。那时的我并没有带伞，哪想到会下雨。我心不在焉地听课，望着窗外的树摇摇晃晃，心里有些着急：“快下雨了！真糟糕！我这脑袋，出门也不带伞以防后患。爸妈也不在家，阿弥陀佛千万不要下雨”

天有不测风云，一会儿功夫，老天爷就扯下了脸，发起脾气来，猛然间，天空变得十分阴森，乌云像被撕破了一样，“哗啦”天上就把雨“泼”下来，不，那不是“泼”，那是“倒”下来。雷公电母也来凑热闹，“霹！咔！”窗外，已是一片朦胧，隐约能看见树木扭动的身姿。

我就这样挨着。终于挨到了放学。

可我没有伞，只能眼睁睁地看着同学们一个个撑着伞回家了，最后只剩下孤独的我。我不时望着学校门口，企盼“救星”的到来。

终于，雨中出现了一个娇小身影。我定睛细看，“是你？”她是我的同学，她家里并不富裕，可能连把好伞都没有。“你快回去啊！来这干什么。”她低下头摆弄着又旧又破的伞说：“我看见你没带伞嘛，所以回家去拿！喏！”她指着伞，“伞有点破，但还是能用的。”她说着抓起一缕湿漉漉的头发拧一把，水就被挤出来，她的全身湿透了。看着她这样，心里好心疼，又不忍心拒绝，只好说：“我拿伞，你怎么办？”“没什么的啦！我身子壮啦！”你身子明明很“”行了！走啦！“她打断的我的话，一把搂住我，撑着伞冲进雨中。

一路上，她老是杷把伞往我这边推，她的胳膊肘连同袖子都湿了，我停下脚步，说：”我撑伞，你那样很累。“可她好像知道我的用意，就是不肯：”不用啦！一个人累比两个人累好，这样，是会吃亏的，而且，我就陪你走会儿，就回家。“”你没伞啊！不如，到我家喝杯茶，我给你把伞，你再回家。“她不在乎地说：”不要啦！家里还有活要干的。拜拜！“”你"还没等我说完，她就搭着双手扣到头上跑进雨里，还不忘回头向我摆手。

我愣了，眼里蓄满泪水，默默地站在那看着她的身影越来越小，直至无影无踪。

话题发现 第5篇

传统的话题检测与追踪 (TDT) 技术的研究对象主要针对篇幅较长的新闻报道。然而微博文具有本内容短小, 特证词少且稀疏, 规模庞大等特点, 所以传统的TDT技术不能有效地适用于微博消息。为此本文提出了结合潜在狄利克雷分配 (Latent Dirichlet Allocation, LDA) 模型和Map Reduce编程模型的微博数据处理与微博热点话题发现方法, 在确保聚类精度的情况, 有效的提高了聚类算法的效率。

1 基于Map Reduce编程模型的微博热点话题发现

1.1 隐主题建模

LDA (隐含狄利克雷分配) 是一种三层树状贝叶斯概率生成模型, 它基于此假设:文档集中所有文档均按照一定比例共享隐含主题集合, 而隐含主题集则是由一系列相关特征词组成。更多关于的LDA模型的介绍请参考文献[1,2]。通过LDA主题模型建模, 有效的降低了微博数据的维度, 将原来高维的单词空间降维到由一组主题构成的相对较小的主题空间上。

本文采用的是Gibbs LDA++对微博数据集建模, 通过运算后, 可以得到如下5个文件:*.others输入参数、*.phi词汇-主题分布矩阵、*.theta主题-文档分布矩阵、*.tassign主题分配情况和*.twords主题。

1.2 对建模结果进行初步聚类

然后本文采用CURE[3]算法对建模后的微博数据进行初步聚类, 该算法可以得到K-means算法的输入参数:聚类个数及其对应的初始类中心, 从而缓解K-means初始聚类中心的随机性和先验性导致聚类结果波动的问题。其过程如下:

⑴从上一步中得到的主题-文档分布矩阵中, 随即抽取样本S;

⑵将样本S划分成等大的n份, 对每个划分进行局部聚类;

⑶通过随机取样剔除孤立点, 去除增长较慢或者不增长的簇;

⑷对局部簇进行聚类;

⑸用相应的簇标签标记相应的簇;

⑹分别对每个类别的所有样本求其平均值, 得到相应的类中心。

1.3 对建模结果进行聚类

1.3.1 Map Reduce基本思想

Map Reduce[4,5,6]是Google开发的一种用于处理大规模数据集的并行编程模型和高效的任务调度模型。Map Reduce主要通过Map和Reduce两个步骤来并行处理大规模数据, Map是一个分解的过程, 它先将大数据集分解为成百上千的相护独立的小数据集 (splits) , 然后把每个 (或若干个) 数据集分配给集群中的1个节点 (一般就是一台普通的计算机) 进行处理;而Reduce是一个合并的过程, 它将分开的数据整合到一起并返回输出。

1.3.2 基于Map Reduce编程模型的K-means聚类

K-means算法的并行化思想:对算法的每次迭代启动一次Map Reduce计算过程, 即在每次迭代内部实现并行计算, 其中Map函数的主要任务是计算每个记录到类中心点的距离并标记或重新标记其所属的类别。Reduce函数的主要任务是根据Map函数得到的中间结果, 计算新类的中心点, 并把该中心点集传给下一次Map Reduce使用。该算法步骤如下:

⑴把CURE算法得到的k个簇类的中心点作为初始簇中心;

⑵Repeat

⑶执行Map函数, 计算每个点到簇质心的距离, 标注或重新标注其所属的类别;

⑷执行Reduce函数, 计算新的簇质心, 并用新计算的簇质心替代原簇中心

⑸计算两轮簇质心的距离的平方和D

⑹Until D小于给定阈值

2 实验分析与结果

实验一:通过腾讯微博API随机获取了2013年4月20日的21324条微博, 对其按照本文方法进行聚类, 得到最热门的3个话题为“雅安地震”、“禽流感”、“复旦研究生投毒”, 通过对比腾讯话题排行榜, 这三个话题均在排行榜前十名中。所以本方法基本可以准确反映出当日的热点微博。

实验二:随机获取了腾讯微博2013年4月13日到2013年4月21日共9天的182162条微博文本, 然后依次使用1~5节点测试基于Map Reduce编程模型的分布式Kmeans文本聚类效率, 通过实验可得, 随着集群中节点的增多, 其运行时间在逐渐减少, 其加速比也在逐渐变大, 说明基于Map Reduce编程模型的Kmeans算法能够提有效的高聚类效率, 并且具有较好的加速比。

3 结论

本文研究了如何从海量微博消息中快速精准得发现热点话题, 文中利用隐主题建模的方法, 有效解决了短文本数据集稀疏性的问题, 然后使用CURE算法, 有效解决了K-Means算法对初始点选择敏感的问题, 最后利用基于Map Reduce并行化的Kmeans算法, 在一定程度上提高了聚类效率。

摘要：针对微博数据文本内容短小、特征词稀疏以及规模庞大的特点, 提出了一种基于Map Reduce编程模型的发现微博热点话题的方法。该方法首先利用隐主题分析技术解决了微博内容短小、特征词稀疏的问题, 然后利用CURE算法缓解了Kmeans算法对初始点敏感的问题, 最后采用基于Map Reduce编程模型Kmeans聚类算法, 对海量微博短文本数据进行快速聚类。实验结果表明该方法可以有效提高微博热点话题发现的效率。

关键词：微博,Map Reduce,Kmeans,聚类,话题发现

参考文献

[1]Blei D M, Ng A Y.Latent Dirichlet Allocation[J].The Journal of Machine Learning Research.2003, 3:993-1022.

[2]石晶, 李万龙.基于LDA模型的主题词抽取方法[J].计算机工程.2010, 19:81-83.

[3]Guha S, et al.CURE:An efficient clustering algorithm for large databases.In:Proc of the ACM SIGMOD Int’l Conf on Management of Data.1998.

[4]Dean J, Ghemawat S.Map Reduce:Simplified Data Processing on Large Clusters[J].Communications of the ACM.2005, 51 (1) :107-113.

[5]江务学, 张璟, 王志明.Map Reduce并行编程架构模型研究[J].微电子学与计算机.2011, 06:168-170+175.

话题发现 第6篇

微博,来源于英文单词Micro-blog。微博用户使用约140字符的文字和图片、链接来更新信息和即时分享,具有发布内容碎片化、传播速度快、简单方便、受众范围广、交互性强的特征。例如在2008年的印度孟买恐怖袭击案件和2009年的美航坠河事件报道中,Twitter都赢得了先机。2009年8月“新浪微博”开始融入到进入网络用户的工作、生活和学习中。2013年4月20日8时03分,四川芦山地震发生一分钟后“@中国地震台网速报”根据中国地震台网自动测定信息,向公众发布“雅安地区附近发生5.9级左右地震,最终结果以正式速报为准”,虽然最后被修订为7级,但是使远离震中的亿万网民能够初步了解了地震的基本情况。

微博作为一种新型的、开放性的互联网应用平台,主要特点如下:

(1)信息覆盖面广。据统计,2012年底Twitter用户已经超过5亿,活跃用户超过2亿,每日发布的消息数量达2亿条;截止2013年底,国内新浪微博用户超过5亿,活跃用户超过6000万,每天转发、评论和原创的微博总数也超过1亿条;微博用户涵盖了社会政府机构、各行各业的权威人士和草根,便于网友之间相互交流并很容易形成热点话题。

(2)传播速度快。由于微博内容简短、信息的生产、发布、转载和反馈,几乎是零时间或者趋向于零时间,充分的体现了“及时”特点。

(3)互动性强。微博的互动性体现在用户之间的关注与被关注关系,并分为单向、双向关注两种。这种关系能够实现信息的即使分享和交流,弱化了互动角色之间的主体地位。微博的独特的信息传播机制,既不同于人际之间点对点的对话交流(例如QQ/MSN),又不同于点对面的大众传播(例如各种媒体或论坛),而是树状、环状交织并不断扩展的裂变传播方式。

(4)元数据内容丰富。指为微博开发者提供的通过API接口方式获得的一些微博结构化数据,包括微博文本元数据和用户信息。微博元数据由“type(类型)”、“attribute(属性)”、“value(值)”组成。其中微博文本元数据包含作者、发布时间、内容、评论数、转发数等标签;用户元数据则包含标识、关注数、粉丝数等[1]。微博的元数据反应了微博的社会关系网络,有助于进行热点话题发现。

对微博进行热点话题发现的研究,在网络舆情预测与分析、关键人挖掘和SEO(Search Engine Optimization,搜索引擎优化)方面具有十分重要的作用。

2 相关概念

话题发现与趋势分析TDT(Topic Detection and Tracking)产生于1996年,由美国国防高级研究计划署DARPA提出要开发一种新技术来自动判别新闻流主题。美国国际标准技术研究所NIST(National Institute of Standards and Technology)每年举办话题检测与跟踪会议来为研究提供支持,IBM、卡耐-基梅隆大学、北京大学、中科院计算所等机构陆续开展了这方面的研究与评测。涉及的具体技术包括分词、形态分析、高维向量空间的降维和聚类等。

文献[2]认为话题(Topic)是一个核心事件或活动以及与之直接相关的事件或活动;事件(Event)是由某些原因、条件引起,发生在特定时间、地点,与某些人或物相关,也可能伴随某些必然结果。例如:“2014年7月1日,日本修改宪法解禁集体自卫权是一个事件”。由于话题可以包含多个事件,所以“日本解禁集体自卫权”是一个话题,这个话题可以包含“2014年7月1日,日本修改宪法解禁集体自卫权”和“中国7月1日外交部回应,不得损害中国国家主权和安全,不得损害地区的和平稳定”等等一系列事件和人们对此的谈论内容。K.K.Bun将热点话题(Hot Topic)定义为在一个时间周期之内出现频率较高的话题,其中,判定条件是话题出现的次数和时间。主题是比话题含义更广的概念,具有抽象的含义,可以看做是涵盖多个类似的具体的事件或者根本是多个具体事件的抽象。如“争端”和“灾害”都是一个主题,“中日钓鱼岛争端”、“中菲黄岩岛争端”、“俄日北方四岛争端”都可以归为“争端”这一主题。

本文研究的话题指的是公众一段时间讨论、交流的中心;微博热点话题的构成通常包含几个要素:一是有大量微博用户参与讨论和交流的事件,符合话题的传播周期;二是包含相当数量的微博条目、评论和转发。图1显示了主题、话题和事件之间的关系:

3 微博热点话题发现

3.1 微博预处理

在单位时间和范围内,微博用户最为关心的热点问题,称为微博热点话题,通常使用用户发布、回复或者评论的微博数量超过预设的阈值来度量。从互联网上采集到的海量微博数据不能直接用于话题发现,需要进行数据过滤、分词和词性过滤、建立倒排索引、微博语义扩展等,预处理从微博的内容信息、用户信息两个维度对数据进行,因此微博热点话题MBHT(Micro-blog Hot Topic)可以形式化描述为[3]:MBHT=(MS,US,T,FS)。其中MS(Micro-blog Set)表示热点话题所涉及的微博和评论的集合;US(User Set)表示所涉及的微博用户集合;T表示热点话题从产生到消亡的时间窗口;FS(Feature Set)表示能够代表热点话题的特征项集合。

3.2 微博特征项建模

微博客作为一种新型的网络媒体数据,数据量巨大,表述不规范,导致其文本数据的特征空间非常稀疏。如果将预处理后的所有词汇都作为特征项,会造成特征空间巨大,并对热点话题发现形成干扰。从话题发现的过程分析,相似度计算是其非常重要的一个步骤,对结果的好坏有着直接的影响作用。文献[4]指出在处理短文本过程中,使用基于文本向量化的方法会丢失内部隐藏的语义信息,并且降噪和降维能力诸多缺陷。文献[5]在指出传统单纯依靠词频的文本向量化的不足,并考虑使用主题模型来进行弥补。本文在对两种模型进行了深入研究的基础上,分析了VSM(Vector Space Module)和LDA(Latent Dirichlet Allocation隐式狄利克雷分布)模型的优缺点,首先采用VSM模型进行微博的向量化,使用TF-IDF(Term Frequency-Inverse Document Frequency)进行权重计算,同时采用LDA模型进行建模,得到每个文本的主题分布向量,挖掘出潜在的语义信息,将词频和语义信息进行加权计算,从而完成微博的相似度计算。

3.2.1 微博文本的VSM建模

向量空间模型VSM的基本思想:将文本信息的处理转化为数学上的向量计算,通过将一组微博看作是向量空间的多个向量,每个特征项使用一个坐标轴来表示。具体如下:微博中第i个特征项使用Ti表示,该特征项的权值采用Wi来表示,因此该微博可以使用向量来表示。通过以上的转化,将微博消息的相似度或相关计算转换成向量的计算,即计算向量空间两个不同点之间的距离。

使用VSM进行微博消息表示的优点:表示方法简单、具有可操作性和可计算性,并且实现了语言问题向数学问题的转化,为文本相似度的计算增加了新的手段。该模型的缺点:未考虑特征项之间的联系,造成语义信息的丢失,同时由于向量空间维数高,如果没有进行降维处理,计算量比较大,当有新微博加入时,必须重新计算特征项权值,维护成本高。

当一条微博消息被向量化后,需要确定该特征在微博信息的重要性。TF-IDF算法通常用来评估特征项对于语料库中的语料的重要程度。其中TF(特征项频率)指的是某一个特征项在语料库中出现的频率,该频率是对特征项总数(terms count)的归一化,以防止它偏向长语料。IDF(反文档频率)反映了特征项在语料库的类别区分能力,主要用于对TF进行权值调整,调整权值的目的在于增强重要特征项,弱化次要特征项。本文采用TF-IDF的乘积来作为微博特征向量空间权值Wi的取值测度,其基本公式如(1)(2)(3)所示:

在上述公式中,ni,j表示特征项ti在微博语料dj中的出现次数,分母是语料dj中所有特征项的出现次数之和。|D|:语料库中的语料总数,分母是包含该词条的语料数目[6]。例如:如果一篇微博100有个词条,而词条“数据挖掘”出现了3次,那么TF=3/100=0.03,假设语料库有10000000篇微博,其中有1000篇微博出现了“数据挖掘”这个词条,那么IDF=log(10000000/1000)=4,TF*DF=0.03*4=0.12;同时类似“的”这样的词条在上述微博可能出现10次,那么TF=10/100=0.01,并且在上述语料库每篇都会出现,所以IDF=log(10000000/10000000)=0,TF*IDF=0。通过对比可得到“数据挖掘”是特征项词语。

3.2.2 微博文本的LDA建模

LDA[7]由Blei等人在2003年提出的文档-主题-单词这样一个三层的贝叶斯层次模型(Bayes Hierarchy Model)。它假设每篇文本内部隐含着若干主题,并且可按照一定的比例使用这些隐主题来表示;每个主题由该文本的特征项构成,并且可由这些特征项的概率分布来体现。

其基本思想:每篇文本的语义都是按照一定概率选择了某个主题,并从选定的主题中再以一定概率选择某些词语。该思想通过在文本和词语之间增加了主题层,将VSM模型的文档-词矩阵的两层模型转化为文档-主题和主题-词语的三层贝叶斯模型,既降低了维度又避免了语义特征的丢失,更好的表现了原文档特征。在LDA中,文档信息可以形式化表示成词频向量,并由词语-主题和主题-文档的概率组成,具体LDA模型的概率使用公式(4)表示:

这个概率公式如果用矩阵表示如图2所示:

图2的LDA主题模型由两个矩阵A和B构成。矩阵A的“主题-词语”表示每个主题中每个单词出现的概率,矩阵B的“文档-主题”表示每个文档中每个主题出现的概率,矩阵C的“文档-词语”表示每个文档中每个单词即出现的概率,亦是词频。通过微博的预处理可得到每个微博中每个单词的词频,继而得到左边矩阵C,然后通过主题模型对矩阵C进行训练,可以学习出矩阵A和B。

为了通过矩阵C得到矩阵A和B,假设语料库中M篇微博文档表示为{d1,d2,….dM},其中包含N个特征项表示{w1,w2,...wN},在M篇微博文档中分布的K个主题表示为{z1,z2,...,zK},因此矩阵A、B、C分别表示为M×K、K×N、M×N。

LDA模型中的每篇文档的主题分布是多项式分布,可用参数θ表示,具体如公式(5)所示:

同样,每个主题下特征项的分布也是多项式分布,可用参数φ来表示,具体如公式(6)所示:

由于上述两个多项式分布的概率满足对称Dirichlet分布,为了推导参数θ和φ,可用参数α和β表示为公式(7)和(8):

LDA模型的文档生成方式如下所示:

(1)从Dirichlet分布中通过参数α得到文档-主题的多项式分布θ(d i),然后从主题分布中抽取一个主题zk;

(2)从Dirichlet分布中通过参数β得到主题-特征项的多项式分布φ(zi),从上述被抽取的主题zk抽取特征项wi;

(3)循环上述过程,直至遍历完语料库中的所有文档di和词语wi:

在LDA模型的计算过程中,参数θ和φ的求解是个关键问题,但是对于上述两参数的求解是个非常复杂的数学问题,所以一般采用不精确的模型推导方法。常用的有Blei[7]提出的变分法,即主要根据变分推断和EM算法(Expectation Maximization Algorithm,最大期望算法);后来有人提出了采用Gibbs抽样算法(Gibbs sampling)[8]来进行LDA的求解,Gibbs抽样是MCMC(Markov chain monte carlo,马尔可夫链蒙特卡尔)理论中用来获取一系列近似等于指定多维概率分布(比如2个或者多个随机变量的联合概率分布)观察样本的算法。本文亦采用Gibbs抽样算法,通过构建收敛的马尔可夫链,抽取最接近与概率分布的样本。

利用Gibbs抽样算法对参数θ和φ的值进行计算的过程如图3下:

通过Gibbs抽样算法能够计算LDA模型的关键参数θ和φ的值。其中参数θ由矩阵A计算得出,表示微博语料库文档-隐主题的概率分布;参数φ由矩阵B计算得出,表示微博隐主题-特征项的概率分布。

3.3 热点话题发现方法

目前,微博的热点话题发现方法主要是将其看做短文本来处理,一般采用基于词频统计的方法;本文融合了微博的特点和社会关系来进行微博聚类能有效的解决热点话题发现问题。

3.3.1 微博向量相似度计算

微博文本的聚类首先需要向量相似度计算。在基于向量空间模型中,微博文档di和dj间基于词频空间上的余弦相似度如公式(9)所示,其中n为VSM的维度。

在基于LDA的模型中,K为微博空间主题的个数,微博文档di和dj间基于主题空间的余弦相似度为[9]:

本文提出的将上述VSM与LDA模型相结合的方法中,微博文档di和dj向量的相似度计算通过使用λ加权,计算公式如(11)所示:

3.3.2 融合微博社会关系的话题发现算法

本文拟采用融合微博社会关系的热点话题发现方法,该方法根据微博发布用户的状态进行分类,同时基于微博社区结构及社会关系[10,11],将微博文档分为评论、转发、原文等。基于社会关系的思想能弥补诸多传统文本话题检测的不足之处,例如用户A发微博说:“XXX在飞机上殴打空姐……”,用户B回复A说:“嗯,他被停职检查,不再担任广州越秀区武装部政委”。虽然他们谈论的是同一个话题“方大国殴打空姐”,但是由于用户AB所发的两篇微博之间可能没有任何共同词汇,因此语义相似度为0,所以说仅依靠语义来度量话题之间的关系是远远不够的。此时,微博中丰富的社会化关系(例如评论、转发等)可以成为文档之间关系度量的重要依据。

基本思路:在传统聚类算法Single-pass的基础上,提出了融合微博的社会关系理论的SPWSR(Single-Pass With Social Relation)算法。该算法将用于微博互动的转发评论关系,微博用户之间的关注关系增加到话题发现中,并且预设微博向量相似度阈值A,最终判断微博语料或者建立新话题类别或者归入已有类别。算法的具体流程如下:

(1)微博文本预处理。包括对微博进行分词、去除停用词、权重计算、语义扩展、建立初始微博向量,并为首条微博向量建立话题类别等。

(2)依次处理微博向量,判断当前读入的微博M同话题类别Ci中的微博{M1,M2…Mn}是否存在评论转发关系。如果存在,则将当前微博M归入话题Ci,并调整该话题质心向量;如果不存在,则通过公式(10)计算微博M同话题类别集合{C1,C2…Cn}之间的相似度sim(M,Ci),如果sim(M,Ci)>A,则将其归入话题类别Ci,并更新Ci的话题向量,同时转步骤(4);否则继续进行步骤(3)。

(3)比较当前微博M同话题类别Ci的相似度sim(M,Ci)与相似度阈值A的大小,如果sim(M,Ci)<A并且当前Ci是最大相似度的微博话题类别,进一步判断微博M和max(Sim(M,Ci))中的类别Ci是否存在关注关系,如果存在则将其归入类别Ci,但更新微博话题向量,如果不存在将其归入类别Ci后不更新微博话题向量,转步骤(4)。

(4)判断微博是否处理完毕,如果不是转入则转入步骤(3);若是处理完毕则结束该算法。

4 实验

4.1 实验评价方法

由于研究的具体问题和语料不同,话题发现的评价方法也不同,基于此实验以NIST为话题发现所建立的评价指标体系为基础,通过漏检率、误检率,准确率、召回率等基本性能指标的求解,以反映准确率和召回率的综合指标F1-measure、漏检率和误检率的综合指标CDet为话题发现评价的重点,并将CDet进行归一化处理得到Norm(CDet)。上述各指标计算公式如下:

参数说明:在微博语料库中,a为模型检测到的相关微博数,b为检测到的不相关微博数,c为相关未检测到的微博,d为不相关未检测到的微博,其中Cmiss和CFA为漏检和错检的代价系数,漏检的代价一般较高,Ptarget是先验目标概率,表示某话题的微博出现的概率,其与Pnon-target概率和是1。

4.2 实验过程

本文以新浪微博为实验语料,采集了马航失联、昆明暴恐、招远血案、昭通地震、斯诺登事件等5个热点话题共80560条微博数据,除数据本身外,还包括上述微博的用户信息与微博元数据信息。实验首先进行微博预处理,每个话题筛选100条微博分别进行VSM和LDA建模,并根据新浪微博的特殊符号以及结构特点,例如“//@、#”,进行微博转发评论、用户关注关系等信息的提取,用作SPWSR算法的基础。

对于评价指标Norm(CDet),文献[12]认为Cmiss=1,CFA=0.1,Ptarget=0.02,Pnon-target=0.98[15]结果较好。为了将公式(11)的加权系数调到最佳,分λ对的不同取值(精度为0.1)来测试上述算法的F1-measure值。通过大量的实验证明当λ=0.4,F1-measure取得最大值为0.86。

为了测试和评价SPWSR算法的性能,进行了下列对比实验。实验采用话题检测常用的层次聚类算法和K-means聚类算法用来进行对照,层次聚类算法采用自下而上的合并聚类方法;K-means聚类算法根据微博数量来决定初始微博类别的设置。实验采用5个话题的平均性能作为各个算法的性能指标,实验结果使用折线图表示如下所示。

从图4的比较结果可以看出,同传统的层次聚类和K-means聚类算法相比,SPWSR算法在各项指标上都有较大的提高,部分性能指标提高将近20%。原因之一在于该算法考虑了微博的结构特点和特征项之间隐含的语义信息,同时联合了多种模型进行相似度计算,提高了微博之间相关性的判断;原因之二由于微博用户之间的关注关系和微博之间的转发评论关系,同层次聚类和K-means聚类算法相比,能够较大的提高算法的指标。因此,虽然引入微博的结构化信息增加了算法的复杂度,但却是必要的。

5 结束语

微博作为即时信息的发布和传播途径,随着微博用户数量的急剧增加,被人们越来越重视,并成为当前移动互联网时代舆情发布和传播的重要途径。本文充分考虑了微博的结构化特点和社会关系,融合了VSM和LDA模型,设计了SPWSR热点话题发现算法,提高了话题发现的效率。

摘要：针对现有话题检测技术的不足,提出了一套适用于微博的热点话题发现方法。通过分析话题检测和微博的相关概念、特点及传播规律,对微博进行预处理和特征项的选择。利用VSM和LDA模型对其进行混合建模并进行微博相似度计算,融合微博社会关系提出了SPWSR聚类算法进行热点话题发现。实验结果表明,在NIST的评价指标体系下,该方法各指标平均提高了10%到20%。

关键词：微博,向量空间模型,LDA模型,话题发现,社会关系。

参考文献

[1]张静.基于微博的网络热点发现模型及平台研究[D],武汉:华中科技大学,2010.

[2]张辉,周敬民,王亮等.基于三维文档向量的自适应话题追踪器模型[J].中文信息学报,2010,(5):70-76.

[3]唐果,陈宏刚.基于BBS热点主题发现的文本聚类方法[J].计算机工程,2010,(7):79-81.

[4]FERN X Z,BODLEY C E.Cluster ensembles for high dimensional data clustering:An empirical study[R].School of Electrical and Computer Engineering,Purdue University,2004,(6):212-226.

[5]崔凯.基于LDA的主题演化演技与实现[D].长沙:国防科技大学,2010.

[6]李勇,张克亮.基于微博的网络舆情分析系统设计[J].计算技术与自动化.2013,(2):125-126.

[7]DAVID M.BLEI,ANDREW Y.Ng.Latent Dirichlet Allocation[J].Journal of Machine Learning Research,2003,(3):993-1022.

[8]STUART G,DONALD G.Stochastic relaxation gibbs distributions and the Bayesian restoration of images[J].IEEE Trans Actions on Pattern Analysis and Machine Intelligence,1984,(6):7212-7411.

[9]黄波,基于向量空间模型和LDA模型相结合的微博客话题发现算法研究[D].成都:西南交通大学,2012.

[10]王晓光.微博社区交流结构极其特征研究[D].上海:华东师范大学.2011.

[11]LIMEI C,YUNGANG W,Bo S,et al.MicroBlog Social Network Analysis[C].Proceedings of 2010 2nd International Symposium on Information Engineering and Electronic Commerce(IEEC).IEEE.2010:l-3.