分类号 密级 U D C

工程硕士学位论文 基于改进CURE算法的短文本聚类 研究与实现

研 究 生 姓 名 罗姗姗 指导教师姓名、职称 龙华教授 学 科 专 业 电子与通信工程 研 究 方 向 信息处理技术 论 文 工 作 起 止 日 期 2011年1月～2012年4月 论 文 提 交 日 期 2012年4月 昆明理工大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下（或我个人……）进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在论文中作了明确的说明并表示了谢意。本声明的法律结果由本人承担。

学位论文作者签名： 日 期： 年 月 日 „„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„ 关于论文使用授权的说明

本人完全了解昆明理工大学有关保留、使用学位论文的规定，即：学校有权保留、送交论文的复印件，允许论文被查阅，学校可以公布论文的全部或部分内容，可以采用影印或其他复制手段保存论文。、、、、、、、、、、、、、、、、、、、、、

（保密论文在解密后应遵守）

导 师 签 名： 论文作者签名： 日 期： 年 月 摘要

I 摘要

在网络作为媒体传播信息日渐频繁的今天，如何从海量的网络文本中，特别是类似新浪微博、twitter这些信息量大、更新速度快的平台所产生的短文本中得到当下热点话题或者是焦点问题显得十分必要。文本聚类这一技术近年来一直被用于信息检索和舆情发现，结合其自身优势，并考虑到网络短文本数据量大、更新速度快等特点，可将文本聚类运用于分析网络短文本话题。 本文首先深入了解并分析了现有各种聚类算法的特性、适用范围以及优缺点。根据网络短文本的特性，选定了CURE算法作为基础进行聚类。保留了CURE算法中通过引入系数错误！未找到引用源。来选取代表点以表示类的形状等步骤，再考虑到网络文本集中孤立点较多的特殊情况，特别加入对孤立点的预处理过程，保证了在聚类前就去除掉大部分孤立点，从而减少聚类中一些不必要的计算同时降低了孤立点对聚类结果的干扰。在验证算法的过程中，还发现在文本表示中所使用的TFIDF公式并不十分适宜于短文本的聚类，所以也将其进行了改进，从而大大提高了聚类准确率。 本文提出了网络短文本聚类算法实现设计，为了验证文中提出的改进算法的聚类效果，从语料库中整理出网络短文本，通过该设计实现了对语料的聚类结果输出。并通过对由查准率和查全率构成的F-measure聚类评价指标和孤立点数量的统计，证明了改进后的算法在F-measure性能指标上优于改进前，并且能更好的避免孤立点对聚类的影响。 关键词：聚类；短文本；CURE；TFIDF 昆明理工大学工程硕士学位论文

II ABSTRACT

III ABSTRACT The network as media becomes more and more frequent day by day, how to dig the Talking Point from a large amount of web short text, especially the similar micro-blog, twitter become very necessary. In recent years, text clustering has been used in information retrieval and public opinion discovery. Considering its own advantages and the amount of short text in network is large and updated frequently, we can apply the text clustering into the analysis of network short text topic. This paper deeply analyzes the characteristics such as application scope, advantages and disadvantages of the existing clustering algorithms. According to the characteristics of web short text, we selected the CURE algorithm as a basis for clustering. Retaining in the representative points of CURE algorithm we add the process of Handling Outliers to filter the large amount of outliers. Ensure the most of outliers can be removed before cluster. By this means, we can reducing the number of unnecessary calculation in clustering, at the same time reducing the interference of outliers in the clustering result. In the process of validating the algorithm, we also found that the TFIDF formula is not very suitable for short text clustering, so we will improve it to greatly improving the clustering accuracy. This paper presents a network short text clustering system design. In order to prove the improvement effect of the algorithm in this paper, we analyze a series of web shot text which selected from the corpus through the system. By the statistics of F-measure of clustering, it is proved that the improved algorithm is better than before. Keywords：Clustering; short text; CURE; TFIDF 昆明理工大学工程硕士学位论文

IV 目录

V 目录 摘要................................................................ I ABSTRACT ......................................................... III 第一章 绪论......................................................... 1 1.1课题研究背景与意义........................................... 1 1.2 相关内容的研究现状 .......................................... 2 1.3 本文研究内容及组织结构 ...................................... 2 第二章 文本聚类相关技术及算法 ...................................... 5 2.1 文本预处理 .................................................. 5 2.1.1分词................................................... 5 2.1.2停用词过滤............................................. 6 2.1.3文本表示模型........................................... 7 2.2 特征值权重计算 .............................................. 8 2.3文本相似度的度量............................................. 9 2.4 聚类分析算法 ............................................... 10 2.4.1 主要聚类算法 ......................................... 11 2.5 聚类分析的相关应用 ......................................... 14 2.6 网络短文本聚类 ............................................. 15 2.7 本章总结 ................................................... 16 第三章 网络短文本聚类相关技术研究及改进 ........................... 17 3.1 TFIDF公式的分析与改进...................................... 17 3.1.1 TFIDF公式的构成原理.................................. 17 3.1.2 TFIDF公式的缺陷分析.................................. 18 3.1.3 对TFIDF公式的改进 ................................... 21 3.2 基于CURE算法的网络短文本聚类算法 .......................... 27 3.2.1 CURE算法简述......................................... 27 3.2.2孤立点................................................ 28 3.2.3 基于孤立点预处理的cure改进算法 ...................... 28 3.3 本章小结 ................................................... 30 第四章 网络短文本聚类算法实现 .................................... 31 4.1语料........................................................ 31 4.2 算法实现 ................................................... 34 4.2.1停用词的处理.......................................... 34 4.2.2 特征值计算 ........................................... 35 4.2.3 孤立点预处理 ......................................... 36