网络舆情热点发现与话题跟踪技术研究（可编辑）

网络舆情热点发现与话 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 跟踪技术研究（可编辑） 网络舆情热点发现与话题跟踪技术研究 硕士学位论文 网络舆情热点发现与话题跟踪技术研究 RESEARCH ON HOT TOPI C DETECTION AND TRACKING IN INTERNET PUBLIC OPINION 韩 威 哈尔滨工业大学 2012 年7 月 国内图书分类号:TP391.2 学校代码:10213 国际图书分类号:681.37 密级:公开 工学硕士学位论文 网络舆情热点发现与话题跟踪技术研究 硕士研究生:韩 威 导 师:赵铁军教授 申 请 学 位:工学硕士 学 科:计算机科学与技术 所 在 单 位:计算机科学与技术学院 答 辩 日 期:2012 年7 月 授予学位单位:哈尔滨工业大学 Classified Index: TP391.2 U.D.C: 681.37 Dissertation for the Master Degree in Engineering RESEARCH ON HOT TOPI C DETECTION A IN INTERNET PUBLIC OPINION Candidate : Han Wei Supervisor : Prof. Zhao Tiejun Academic Degree Applied for : Master of Engineering Speciality : Computer science and Technology Affiliation : School of Computer science and Technology Date of Defence : July, 2012 Degree-Conferring-Institution : Harbin Institute of Technology 摘 要 摘 要 随着互联网的快速发展，网络已经成为人们 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达情绪和态 度的重要“场所”， 不论是正面的、还是负面的网络舆情都对社会的稳定产生重要的 影响。因此， 国家相关部门对网络舆情的重视与日俱增，相应的互联网舆情监 测系统也应运 而生。它实时地采集互联网信息，智能地分析信息的内容，为相关部门监测网 络舆情，引导正向舆情，处理舆情危机提供了良好的支持。 本文对构建网络舆情监测系统相关技术，如自然语言处理技术、信息挖掘 技术进行了研究，同时对目前已有的舆情监测系统进行研究，在此基础上构建 舆情监测系统。 本文重点对网络舆情监测系统的关键技术――热点话题发现与跟踪进行研 究分析，在已有的技术手段上对其进行改进以适应现实监测环境。本文的贡献 主要体现在以下3 个方面: 1(提出一种改进的 Single-Pass 增量聚类方法 应用于热点话题发现。本文 研究了热点话题发现的具体流程，将文本聚类作为其实现的关键技术之一。通 过分析几种已有的文本聚类算法的原理及步骤，从五个方面对比分析了各算法 的优缺点，最终选取 Single-Pass 增量聚类作为话题发现的实现方法。但是， Single-Pass 算法存在对文本输入顺序敏感等缺点，在对该算法进行分析的基础 上本文对其进行了改进，在算法精度、响应时间上有所提高，使其能适应大规 模文本聚类。最后，经过对比实验证明，本文提出的算法具有良好的实际应用 效果。 2 (提出一种改进的SVM 算法应用于话题跟踪。本文研究了话题跟踪的具 体流程，将文本分类作为其实现的关键步骤。通过分析文本分类方法和实验对 比，选择了SVM 算法作为其具体实现。但 SVM 算法比较适合二值分类问题， 因此本文对其进行了改进，使其适应现实中多分类的要求，最终通过实验证明 其有较好的实际应用效果。 3 (在对相关技术研究的基础上，本文设计了网络舆情监测系统的物理构建 框架与逻辑实现框架，详细介绍了舆情监测系统各个模块的实现及功能，最终 实现部署该系统。通过系统的实际运行，证明本文所提出的设计 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 具有功能 全面、速度较快、性能稳定等特点，为用户对网络舆情的监测与 分析提供了有 效的支持。 关键词 舆情监测;热点话题发现;话题跟踪;文本分类;自动 聚类 - I - Abstract Abstract With the rapid development of Internet, it has become an important "place" for people to express their emotions and att itudes. Whether positive or negative network public opinion has an important influence on social stability. Therefore, relevant departments of the State increase emphasis on the Internet public opinion, and the Internet public opinion monitoring system has come into being. It collects Internet information in real time, and intelligently analyzes the content of information. The monitoring system provides good support for monitoring network public opinion, guiding the positive opinion and dealing with the cri sis of public opinion to the relevant departments. We conduct our study on related technologies to build the network public opinion monitoring system in this paper, such as natural language processing, data mining technology. At the same time, we have studied the existing public opinion monitoring systems. On this basis, we constructed a public opinion monitoring system. Our study is focused on the key technologies of the Internet public opinion monitoring system, including topic detection and tracking. These algorithms in this paper are improved to adapt to reality monitoring environment. The contribution of this paper lies in the following three aspects: 1. This paper presents an improved Single-Pass incremental clustering method for topic detection. A specific process of topic detection is studied in this paper, and then we choose the text clustering as a key technology for its implementation. We analyze the principles and steps of several existing text clustering algorithm s, and compare the advantages and disadvantages of each algorithm . Finally, this paper selects Single-Pass algorithm for topic detection's implementation. However, the Single-Pass algorithm has some shortcomings, for example it's sensitive to text input sequence. On the basis of the analysis of the algorithm, it is improved on the accuracy and response time, so it is able to adapt to large-scale text clustering. Finally, the comparative experiment prove s that the proposed algorithm has a good practical application. 2. An improved SVM algorithm applied to topic tracking is presented in this paper. A specific process of topic tracking is studied in this paper, and then we choose text classification as a key technology for its implementation. Through the analysis of text classification methods and experimental comparison, we choose the SVM algorithm for its concrete realization. SVM algorithm is adapted to binary classification problems, so SVM is improved to solve multi-classification problem. - II - Abstract Finally, the comparative experiment prove s that the proposed algorithm has a good practical application. 3. On the basis of the related technologies, we design the physical and logic al framework of Internet public opinion monitoring system. The detailed implementation and function of system's each module is described in this paper. Finally, we complete the system. The actual running of the system proves that the proposed design has a full -featured, fast, stable performance and so on. It provides effective support for the monitoring and analysis of Internet public opinion. Keywords: public opinion monitoring , hot topic detection , topic tracking, text Classification, automatic clustering - III - 目 录 目 录 摘 要..........................................................................................................................I ABSTRACT ................................................................................................................ II 第 1 章 绪 论........................................................................................................... 1 1.1 本文研究的目的和意 义......................................................... .................... 1 1.2 网络舆情监测相关技术研究现 状.............................................................. 2 1.2.1 网络爬虫技 术.............................................................................................3 1.2.2 信息预处理技 术........................................................................................ 5 1.2.3 文本挖掘技 术.......................................................................................... 10 1.2.4 话题检测与跟踪技 术.............................................................................. 11 1.3 国内外舆情监控系统研究现 状............................................................... 12 1.4 本文的主要工 作...................................................................................... 13 1.5 本文的组织结 构...................................................................................... 14 第2 章 网络舆情监测平台系统架构设 计............................................................. 16 2.1 引 言........................................................................................................ 16 2.2 系统总体设计框 架......................................................... ......................... 16 2.2.1 物理设备部 署.......................................................................................... 16 2.2.2 舆情监测系统架 构.................................................................................. 17 2.3 系统各功能模 块...................................................................................... 19 2.3.1 信息入库模 块.......................................................................................... 19 2.3.2 用户定制模 块..........................................................................................21 2.3.3 话题发现模 块..........................................................................................23 2.3.4 话题跟踪模 块..........................................................................................24 2.3.5 信息检索模 块..........................................................................................24 2.3.6 关键词报警模 块......................................................................................25 2.4 本章小 结................................................................................................. 25 第3 章 网络舆情热点话题发现技术研 究......................................................... ....26 3.1 引 言........................................................................................................ 26 3.2 话题发现流 程......................................................................................... 26 3.3 话题发现技 术......................................................................................... 27 3.3.1 文本聚类算法及比 较..............................................................................27 - III - 目 录 3.3.2 改进的增量聚类算 法..............................................................................32 3.3.3 实验及结果分 析......................................................................................36 3.4 本章小 结................................................................................................. 39 第4 章 网络舆情话题跟踪技术研 究.....................................................................40 4.1 引 言........................................................................................................ 40 4.2 话题跟踪流 程......................................................................................... 40 4.3 话题跟踪技 术......................................................................................... 41 4.3.1 文本分类算法及比 较..............................................................................41 4.3.2 改进的SVM 分类算 法...........................................................................47 4.3.3 实验及结果分 析......................................................................................48 4.4 本章小 结......................................................... ........................................ 50 第5 章 网络舆情监测平台实 现............................................................................. 52 5.1 引 言........................................................................................................ 52 5.2 系统运行效 果......................................................................................... 52 5.3 本章小 结................................................................................................. 59 结 论....................................................................................................................... 60 参考文 献................................................................................................................... 61 哈尔滨工业大学硕士学位论文原创性声 明........................................................... 65 哈尔滨工业大学硕士学位论文使用授权 书........................................................... 65 攻读学位期间发表的学术论 文...............................................................................66 致 谢....................................................................................................................... 67 - IV - 哈尔滨工业大学工学硕士学位论文 第1 章 绪 论 1.1 本文研究的目的和意义 中国互联网络信息中心(CNNIC )2012 年 1 月发布的《第29 次中国互联 网络发展状况统计报告》中指出，2010 年至2011 年各网络应用使用率如下: 网络新闻为71.5% ，用户规模3.66 亿;博客/个人空间为62.1% ，用户规模3.18 亿;微博为48.7% ，用户规模2.49 亿;社交网络为47.6% ，用户规模2.44 亿; [1] 论坛/BBS 为28.2% ，用户规模 1.44 亿 。由上面这些数据可以说，互联网已 经成为继广播、报纸、电视之后，全球性的另一个重要媒体。另外，与其他媒 体相比，互联网又有进入门槛低、信息超大规模、信息发布与传播迅速、参与 群体庞大、实时交互性强等综合性特点。由于互联网信息的发布成本极低，信 息的发布者、阅读者和传播者之间已经没有明确的划分，因此在很大程度上它 已经深入人们的日常生活，成为信息传播的主流媒体，同时也成为社会舆情的 晴雨表。尤其是近几年发生的诸如“7.23 动车事故”、“郭美美 事件”等都是首 先在互联网上广泛传播后引起激烈讨论，然后才引起社会与相关部门的重视， 这些事实都反映了网络舆情对整个社会舆情导向起到的重要作用。 那么如何定义网络舆情,网络舆情是指互联网上传播的人们对于某个事 件的全部认知、情感态度和行为倾向的集合，其主要的传播途径有新闻评论、 [2] 论坛、博客、微博、聚合新闻(RSS )等 。正如南开大学徐晓日所说，它有 [3] 以下几个主要特点 : 1(来源的广泛性和匿名性; 2 (突发性; 3 (倾向于揭露问题与批判现实; 4 (容易出现群体极化倾向; 5 (能够形成更大的群体压力。 从网络舆情的这些特点可以看出，网络舆情信息包含了人们对当前社会各 个领域，如政治、经济、科技、军事等中出现的各类现象以及人们热议的问题 所持的态度和观点，它直接、快速地反映了上述各个层面的社会舆情现状与发 展趋势，成为反映上述相关重要领域的社会舆情的重要载体，受到政府相关部 门的高度重视。 同时，我们也应该清醒地认识到，网络舆论继承了网络自由化的特性，这 必将带来一些消极的影响:比如当现实生活中的一些问题被反映到网络上引起 - 1 - 哈尔滨工业大学工学硕士学位论文 人们的广泛关注时，其会很容易造成强大的舆论压力，而这些舆论的导向并不 一定是正确的，当错误的舆论广泛传播时，其造成的破坏是难以想象的，并且 这些破坏是很难控制的。另外，由于互联网的开放性和虚拟性，国内外一些敌 对势力也通过互联网对我进行“西化”和“分裂”。他们对社会上出现的热点 事件、热点人物进行大肆炒作，散布谣言，传播反动言论，蒙骗广大网民，误 导网络舆论。 由此可见，对于社会的和谐稳定、有序发展，网络舆情已经成为众多影响 因素中最重要的一个。如何准确掌握网络舆情动态，提升对舆情的分析能力， 因势利导正确引导舆情发展，是政府及相关部门所面临的严肃课题与严峻挑 战。 另外，由CNNIC 发布的《统计报告》中的数据可以看出，网络舆论具有 参与人数多，信息量大，类别繁多等特点，在这种情况下，单纯由人工进行分 类统计和甄别分析是难以满足网络舆情控制管理需要的。同时，对于网络舆论 中热点话题的发现，以及热点事件的跟踪也不能单纯靠人工进行分析。随着， 超大规模数据库的出现和计算机技术的发展，促使这些问题由人工完成转为计 算机辅助完成。 综上所述，对网络舆情的有效监控将日益成为政府部门工作的一个工作重 点，而对网络舆情分析的相关技术也成为计算机工作者的研究热点。人们可以 通过以下几种技术对网络舆情进行研究分析: 1(热点话题的发现。利用文本聚类技术对广泛的舆论信息进行分析处理， 从而归纳得出热点话题。 2 (主题事件跟踪。利用文本分类技术对新发表文章的主题进行分析，判 断是否属于已知主题集合中的一类。 3 (倾向性分析。分析一篇文章或帖子对于某个话题的观点与倾向性。 4 (趋势分析。对于某个话题，分析人们在不同时间段内对其的关注程度。 5 (舆情预警。对于突发事件、敏感事件能进行及时发现预报。 综上所述，网络舆情分析是一门综合各种学科与技术的技术，国内外很多 科研机构都做出了大量的相关研究，也取得了较大的进展，但是还是存在很多 问题和难点。 1.2 网络舆情监测相关技术研究现状 目前，国内的网络舆情监测技术正处于蓬勃的发展期，舆情监测技术与其 它相关领域的技术相互交叉应用，能够对网络舆情的及时掌握，舆情导向的有 效控制产生重要的作用。其中几项关键技术是目前研究者研究的重点:网络爬 - 2 - 哈尔滨工业大学工学硕士学位论文 虫技术、中文信息处理技术、文本挖掘技术、话题检测与跟踪技术。 1.2.1 网络爬虫技术 网络舆情监测所要操作的对象是互联网上的信息，但是随着互联的日益发 展，Web 信息量不断增长，每天有成千上万的网页增长量，要从这么庞大的数 据中找寻感兴趣的数据，使用通常的搜索引擎、人工寻找是不可能完成的事情。 为解决这个问题，网络爬虫技术便应运而生了。网络爬虫，又被称为网页蜘蛛、 网络机器人，是一个自动获取网页的程序。传统的网络爬虫从一组定制好的称 之为种子的URL 链接开始执行，它访问这些URL ，识别出这些页面中全部的 超链接，然后添加到定制的 URL 列表，可以称作检索前沿。爬虫程序按照某 [4] 种策略不断重复访问这些URL ，直到满足系统预先设定的停止条件 。其实现 原理流程如图 1- 1 所示。 启动爬虫程序， 初始化URL列表 是 队列是否为空 停止爬虫程序 否 下载网页，将等待队列中 的URL移入运行队列 否 将这一URL移入 网页中是否包含未 完成队列 处理URL 是 处理网页中包含的 下一链接 否 是否指向6>Html 报告其他 的链接 链接 是 新链接与前一 否 报告其他 链接是否在同 链接 一服务器 是 将新链接加入等待 队列 图1- 1 网络爬虫原理流程图 目前，网络爬虫获取页面大致有深度优先、广度优先、最佳优先三种策略。 - 3 - 哈尔滨工业大学工学硕士学位论文 深度优先策略实现较为简单，但是在很多情况下该策略会导致爬虫程序的陷入 问题。广度优先策略是指爬虫程序在获取页面时，首先完成当前层次页面的检 索后，再对下一层次页面进行检索。该算法的设计和实现相对简单。目前，为 获取尽可能多的网页，爬虫程序通常使用广度优先策略。该方法的缺点在于， 它所抓取的网页中不仅有有用网页也包含无用网页，而且随着网页数量的增 大，这些无用网页也在增多，这大大降低了算法的效率。最佳优先策略是按照 某种网页分析算法，抓取与目标网页相似或主题相关的网页。该算法存在问题 是，它采用局部优先搜索算法只抓取“有用”的网页，抓取路径上的很多相关 网页往往会丢失，因此需要将该算法结合具体的应用进行改进，以解决这个问 题。 随着网络爬虫技术的不断发展，目前，网络爬虫有以下几种研究方向: 第一种是针对整个互联网的网络爬虫。它首先从一些种子页面开始抓取， 通过这些页面逐步扩展，直到整个互联网。目前，大型搜索引擎网站、各门户 网站等的数据信息采集通常使用这种网络爬虫。由于这类爬虫程序的目标是采 集整个互联网，因此对计算机硬件的要求比较高，对页面采集的顺序要求相对 较低。 第二种是增量式的网络爬虫。与周期性 Web 采集器定期定时采集全网数 据不同的是，增量式的网络爬虫采用增量式更新的方式，即爬虫程序只对未采 集过的页面或者内容改变的页面进行采集，而不采集原有的页面。和传统的信 息采集相比，这种信息采集方式极大地减小了数据的采集量，从 而极大地提高 了爬虫的效率，而减少了对系统的消耗。但是存在的缺点是，算法的复杂性和 技术难度大大增加。 第三种是基于主题的网络爬虫。和前两种爬虫相比，它不采集与预先定义 的主题无关的页面，而是采集与之相关的页面，因此在很大程度上节省了系统 所消耗的资源，同时采集页面的更新速度也更快。此外，它还满足了人们对特 定领域信息抓取的需求，因此成为目前爬虫研究的热门。但是，它也存在自身 的问题，如怎样确定抓取的主题，如何判断抓取的页面与主题是否相关以及系 统搜索精度和广度如何提高等。 第四种是针对用户个性化设定的网络爬虫。目前，通用的搜索引擎对于相 同的检索词通常会给出相同的检索结果，但是不同的用户所希望得到的结果却 并不尽相同。基于用户个性化的网络爬虫通过用户对兴趣的制定以及系统与用 户的交互得到不同的用户模型，然后根据模型再采集信息，从而提供个性化的 采集服务。 第五种是移动的网络爬虫。这种爬虫程序与其他爬虫程序不同的是，它不 - 4 - 哈尔滨工业大学工学硕士学位论 文 在本地机器采集站点服务器上的页面，而是将程序上传到它所要采集的服务器 上，在服务器上采集页面并进行压缩，然后将压缩结果传回到本地。这样做使 得大量的获取工作在页面存在的站点服务器上完成，对于本地和 Web 资源的 消耗将大大降低。 第六种是基于元搜索的网络爬虫。它通过元搜索的方式在多个领域或门户 搜索引擎中检索用户提交的检索请求，并将检索结果整合后反馈给用户。 以上是网络爬虫的策略以及目前的研究方向，那么网络爬虫的工作方式目 前有两种:集中式、分布式。前一种是通过多个线程抓取初始 URL 种子集中 各URL 对应的页面，然后进行分析，提取页面信息，并将页面中包含的其它 URL 提取出来放入列表中继续爬取。第二种可以看作是多个集中式爬虫的组 合。分布式系统的每个节点可以看作是一个集中式网络爬虫，它们协同工作获 取信息。 上述内容是基于网页的网络爬虫，目前，对于微博、社交网络，其网站本 身为方便开发者开发基于网站的各种应用，提供了 Open API ，开发者可以通 过 API 获得感兴趣的数据。其开发的大致流程为:在网站注册应用、获得应 用账户名及密钥、通过网站OAuth 认证获得access_token 、调用API 接口方法、 获得网站提供的各种格式的数据文件。 1.2.2 信息预处理技术 当从互联网上获取到数据信息后，下一步就是要对这些信息进行预处理， 以便为后续的文本分类、文本聚类奠定基础。这些预处理技术包括:中文分词 技术、文本的数字化表示、特征提取技术等。 1)中文分词技术 网络舆情监测的对象大部分为中文网站，其获得的信息也大部分为中文信 息。对于中文信息的挖掘其前提就是中文分词。中文分词是指将 要处理的汉字 序列划分成一个一个独立的词。之所以要进行中文分词，是因为中文在基本语 法上有其自身的特殊性:首先，不同于以英文为代表的拉丁语系，空格便是单 词之间天然的分隔符，在中文里只有字、句和段落有明显的分割标识，而词却 没有实际意义上的分割标识。其次，在中文中，“词”和“短语”认识边界模 糊。中文中大部分词是以二字或多字组成的，但是由于人们的认识不同，其理 解也会发生偏差，例如:“对于随地吐痰者给予处罚”，其中“随地吐痰者” 是一个词还是一个短语，不同的人会有不同的认识。 目前，主要有三种类型的中文分词算法:基于字符串匹配的方法、基于理 解的方法和基于统计的方法;考虑是否与词性标注相结合，又可以将其分为单 - 5 - 哈尔滨工业大学工学硕士学位论文 [5] 纯分词方法、分词与词性标注相结合的一体化方法 。 a (字符串匹配分词。又称为机械分词，它是按照某种匹配原则将待分词 的汉字序列与已经定义好的D足够大‖ 的词典中的词条进行匹配，如果与其中的 某条匹配成功，则说明识别出一个词。按照不同的匹配方向可以 分为正向匹配 (从左到右)与逆向匹配(从右到左)，按照不同的匹配长度可以分为最大匹 配与最小匹配。例如，正向最大匹配法、逆向最大匹配法、双向最大匹配法等。 按照汉语成词的特点，逆向匹配的分词精度要略高于正向匹配，产生的歧义现 象也略少。在实际的分词系统中，字符串匹配的精度往往是不够的，它通常是 作为分词的初始阶段使用，还要结合其它的自然语言处理方法才能获得更精确 的分词效果。 b (理解分词方法。这种分词方法是让分词程序模拟人从句子中识别词语 的方式来进行分词。其基本思想是将句法分析和语义分析加入到分词的过程 中，对于分词的歧义现象通过句法信息和语义信息来处理。该方法通常由分词 子系统、句法语义分析子系统、总控等三个部分构成。通过总控部分的控制， 分词子系统与句法语义分析子系统协同在分词过程中获得单词、句子等的句法 和语义信息，判断歧义分词，从而达到较为准确的分词效果。这种分词方法需 要使用丰富的语言知识和信息，但是由于汉语的笼统性和复杂性，难以将各种 语言信息组织成计算机可识别的形式，因此这种方法实现起来较为困难。 c (基于统计的分词方法。这种方法需要首先给出大量的 已经分好词的文 本，称之为训练集，在训练集上利用统计机器学习模型训练词语切分的规律， 得到词语切分模型，然后在未知文本上使用此模型，从而实现词语的切分。这 种方法的缺点也显而易见，需要大量的训练语料作为支撑，同时在训练分词模 型的过程中时空开销也很大。 上述三种分词方法，各有其优缺点，哪种分词结果更精确，我们不能妄下 定论。对于一个成熟的分词系统，都是综合各种方法实现的，而不是单独使用 某一种方法。如目前成熟的中文分词系统有:中科院的 ICTCLAS[6] 、哈尔滨 工业大学信息检索研究中心发布的语言技术平台、天津海量的D海量中文智能 分词系统‖等。本文采用中科院的 ICTCLAS 作为分词处理方法。例如:如下 一段Web 文本: D1 月 12 日, 中国工程兵大队长李金勇、副大队长高军等前往柬华理事会看 望了柬华人各社团代表及端华学校全体师生,并向他们赠送了电风扇等礼品。‖ 此序列通过ICTCLAS 分词后得到的结果为: D1 月/t 12 日/t ,/w 中国/ns 工程兵/n 大队长/n 李/nr 金勇/nr 、 /w 副/b 大队长/n 高/a 军/n 等/u 前往/v 柬/j 华/j 理事会/n 看 - 6 - 哈尔滨工业大学工学硕士学位论文 望/v 了/u 柬/j 华人/n 各/r 社团/n 代表/n 及/c 端华/nr 学校/n 全体/n 师生/n ,/w 并/c 向/p 他们/r 赠送/v 了/u 电风扇/n 等/a 礼品/n 。/w ‖ 2 )文本的数字化表示 计算机并不能像人一样地去理解非结构化的文本，它只能识别结构化的内 容。 因此，为了能让计算机理解非结构化的文本内容，我们需要将文本转化为 结构化的数据。所谓文本的数字化表示，就是将非结构化的文本 表示成结构化 的数据。目前，文本的数字化表示主要有三种模型:布尔模型、 概率模型、向 量空间模型。 [7,8] 布尔模型 :是一种较容易实现的表示方式，它将文本表 示为一个布尔 表达式。具体形式如下: D W ,W ,W ,......,W (1- 1) 1 2 3 n 其中，D 表示文本，Wn 表示n 个词语特征是否在文档中 出现，其值为 0 或 1，0 表示未出现，1 表示出现。布尔模型的优点是较为容易实现，其缺点 是不能表示相同词语特征在不同文本中所起作用的差异。 [9,10] 概率模型 :它考虑词与词之间的相关性，将文档集分为相关文档与无 关文档两部分(以概率论为算法原理，通过计算为每个特征词赋予一个概率值 p ，通过p 来表示在相关文档和无关文档中这些特征词出现的概率，然后计算 文档间相关的概率，系统据此概率做出决策。 [11,12,13] 向量空间模型(VSM ) :它是目前自然 语言处理常用的文本表示方 式，是20 世纪60 年代末期由G. Salton 等 人提出的。它将文本内容转化为向 量空间中的向量，其表达式如下: D t ,W ;t ,W ;......;t ,W (1-2 ) 1 1 2 2 n n 其中，D 表示文本，tn 表示文本中的词语特征，Wn 表示 词语特征tn 在文 本D 中的权重。Wn 越大，表示词语特征tn 越能表示文本D ， 相反其值越小， [14] 说明词语特征tn 反映文本D 的能力越差。Wn 的值通常使用 TFIDF 函数 来 计算，其表达式如下: tfidfi, j tfi, j ??idfi (1-3 ) 其中，tfidfi,j 表示词语 i 在文本j 中的 tfifd 值，tfi,j 表示词语 i 在文本j 中 的词频，其表达式如(1-4 )所示。idf 表示表示词语i 的 逆向文档频率，其表 i 达式如(1-5 )所示。 n tfi, j i, j (1-4 ) ?k nk , j - 7 - 哈尔滨工业大学工学硕士学位论 文 其中，分子ni,j 表示词语i 才文本j 中 出现的次数，分母表示文档j 中所有 词语出现的次数之和。 | D | idfi log ??0.01 (1-5 ) | j :t i ?d j | 其中，分子|D|表示语料库中的文档总数，分母表示包含词 语i 的文档数。 当分子与分母相等时 idf 值为零，为防止出现这 种情况，通常加入平滑因子 0.01 ，此值可以根据实验情况调整。 通常情况下，为了防止文本的长度对 TFIDF 的影响，我 们还要将TFIDF 值进行归一化处理，使其值保持在[0,1]之内，因此，完整的 TFIDF 函数可表 示为: tfi, j ?idfi tfidfi, j 2 (1-6 ) ? tf ?idf i?j i, j i 其中，分母为归一化因子。 本文的文本表示方式采用向量空间模型 (VSM )，因为其可以过滤掉常 见的词语，保留重要的词语。 3 )特征提取 文本表示的向量空间模型带来的最大问题就是维数过高，即便是一个中小 规模的语料库也有上万个单词，即上万维，这对于很对机器学习算法是相当高 的，这会直接影响算法的效率。同时，维度过高还会出现过拟合问题。为了解 决这些问题，必须对向量空间模型进行降维操作，即特征提取。目前，特征提 取有两种方式:特征抽取和特征选择。 特征抽取，是通过某种形式的变换将原始特征向量从高维空间映射到低维 空间，此时新得到的特征就与原来的特征不相同了，其数学表示形式如式(1-7 ) 所示。特征抽取方法有很多种，例如:单词聚类(Word Clustering )、成分分 析(PCA )、潜在语义索引(LSI )等。 A : X ?Y (1-7 ) 其中，A 为变换规则，通常为某种正交变换。 特征选择，是按照某种规则从获得的特征集中选取最有用的一部分特征来 表示文本。此处的规则通常是一个评估函数，它对每个特征项进 行评估，从而 得到各自的评估值，然后根据评估值对特征进行排序，取前 N 个特征作为特 征子集。选取特征项的个数 N 与评估函数根 据不同的问题确定。其数学表示 形式如式(1-8 )所示。 S : x ,x ,......,x ?F : y , y ,......, y y ?S ,i 1,2,......,n;n ?? N (1-8 ) 1 2 N 1 2 n i - 8 - 哈尔滨工业大学工学硕士学 位论文 目前，大多数机器学习方法都采用特征选择方法，因为它 的技术更加成熟， 实现较为容易。本文也采用此方法。 特征选择的方法也有很多种:文档频数法(Document Frequency ，DF )、 ? ? 检验、信息增益(Information Gain ，IG )、互信息(Mutual Information ， MI )等。对于相同的文本，选择不同的特征选择方法得到的特征集是不相同 的，对机器学习方法的影响也是巨大的，因此选择哪种方法就显得很重要了。 [15] a (文档频数法 。它是较为简单的一种特征选择方法，指的是对于一个 特征项在文本集中有多少文本包含它。该方法设定最低阈值与最高阈值，只保 留两个阈值之间的特征项。该方法的时间复杂度与文本集的大小成线性关系， 为O N ，因此该方法的效率极高。 ? [16] ? b (? 检验 。? 检验其实是数理统计中一种常用的检验两个变量独立性 的方法。在这里我们用来检查一个单词与一个类别的独立性。其过程可概述为， ? ? 计算文本中每个词与某个类别的? 值，并对所有词的? 值从大到小排序，此时 ? ? 值越大越相关，最后按照预设的选取个数选取特征即可。可由 式(1-9 )表 示。 2 AD ?BC 2 ? t, c (1-9 ) A ?B C ?D 其中，t 为特征项，c 为类别，它们之间的关系如表 1- 1 所示。 ? 表 1- 1 ? 检验特征与类 别关系 属于类c 不属于类c 包含t A B 不包含t C D [17] c (信息增益 。它是针对每个特征而言的，我们计算系统 中出现特征 t 时的信息量和没有出现特征t 时的信息量之间的差，这个值就 是t 带给系统的 信息量，即增益。增益越大，特征t 越重要。其表达式如式(1- 10)所示。 n IG T ?? P C log P C ? ? ? ? ? ? ? i 2 i i 1 n ? P t P C |t log P C |t (1- 10) ? ?? ? i ? 2 ? i ? i 1 n ? P t P C |t log P C |t ? ?? ? i ? 2 ? i ? i 1 其中，P Ci 表示类别 Ci 出现的概率，它 的值等于类别总数的倒数。P t 表示特征t 出现的概率，其值等于出现过特征t 的文本数除 以总文本数。P Ci|t - 9 - 哈尔滨工业大学工学硕士学位论 文 表示特征t 出现时，类别Ci 出现的概率，其值等于属于类别 Ci 且出现特征项 t 的文本数除以出现特征t 的总文本数。P t 表示特征项 t 不出现的概率，其 ? ? P C | t 值等于特征项t 没有出现过的文本除以总文本数。 ? i ? 表示特征项t 不出现 时，类别Ci 出现的概率，其值等于没有特征项t 但属于类别 Ci 的文本数除以 没有特征t 的总文本数。 [18] d (互信息 。它根据一个特征项 t 的 出现情况来衡量特征项对类别 Ci 的重要程度。一个特征项t 对于类别Ci 的MI 值可由 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 (1- 11)得出。 P t ?C ? i ? MI ?t ,Ci ? log P t P C ? ? ? ? i (1- 11) D t ,C D t D C ? ? ? ? ? ? p t ?C i , p t ,P C i ? ? ? ? ? ? i i N N N 其中，D t,Ci 表示类别Ci 中出现特征项t 的文本数， D t 表示训练语料库 中出现特征项t 的文本数，D Ci 表示类别Ci 的文本数，N 表 示训练语料库中 的文本总数。 ? 本文经过对几种特征选择方法的比较，选择了效果较好的? 检验作为本文 的特征提取方法。 1.2.3 文本挖掘技术 文本挖掘是指用数据挖掘方法在海量文本集中发现深层次的、可用的模式 或信息。数据挖掘技术中的文本分类和聚类现在广泛用于文本挖掘中，本文将 对它们进行重点研究。 1)文本分类 文本分类是一个有监督的机器学习问题，它的任务是按照一定的规则将一 篇文本归入预先定义好的类别集中的某个或某几个。这个规则是分类程序根据 已有的类别体系，分析归纳出类别的内在规律从而得出类别的判定式。然后当 处理未知文本时，就根据判定式来判别该文本属于哪个类别。 目前，文本分类算法已经较为成熟，比较典型的有:K―近邻(K-Nearest Neighbors ，K-NN )、朴素贝叶斯(Na?ve Bayes ，NB )、决策树(Decision Tree ， DT )、类中心( Rocchio )、支持向量机(Support Vector Machines ，SVM )等， 各算法的简要介绍将在第四章给出。 文本分类结果的评估方法，主要有三个方面:准确率(Precision )、查全 [19] 率(Recall )、F1 值 。其方法主要是与人工分类比较。 准确率是指自动分类结果中与人工分类结果相同的文档在自动分类结果 - 10 - 哈尔滨工业大学工学硕士学位论 文 中所占的比例，可由公式(1- 12)表示: 正确分类的文本数 准确率 Precision (1- 12) ? ? 实际分类的文本数 查全率是指自动分类结果中与人工分类结果相同的文档在 人工分类结果 中所占的比例，可由公式(1- 13)表示: 正确分类的文本数 查全率 Recall (1- 13) ? ? 人工分类中的文本数 F1 值是准确率与查全率的综合考量，可由公式(1- 14) 表示。 2 ?准确率?查全率 F1值 (1- 14) 准确率+查全率 对于不同分类算法的比较，F1 值常作为一个 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的评估 值。 2 )文本聚类 文本聚类是一个典型的无指导的机器学习问题，它的任务是按照一定的规 则将一个文本集分成不同的子集，并且保证在各子集中各文本相似性最大，同 时各子集之间相似性又最小。 目前，存在以下几种文本聚类算法:基于划分的算法、基于层次的算法、 基于密度的算法、基于网格的算法等。典型的有 K-Means 、DBSCAN 、SOM 等，各算法的简要介绍将在第三章给出。 对于文本聚类结果的评估标准，将在第三章实验部分给出。 1.2.4 话题检测与跟踪技术 话题检测与跟踪(Topic Detection and Tracking ，TDT )[20,21]是 1996 年美 国国防高级研究计划署(DARPA )根据自己的需要提出的研究任务。从 1998 年开始到2004 年截至，美国国家标准技术研究所(NIST )在DARPA 的支持 下每年都举办话题监测与跟踪的国际评测会议。 首先，我们给出事件与话题的定义。 定义 1:事件通常是指