基于蚁群算法的中文本聚类研究.pdf

杭州电子科技大学
硕士学位论文
基于蚁群算法的中文本聚类研究
姓名:沈杰
申请学位级别:硕士
专业:计算机软件与理论
指导教师:王小华
20091101
杭州电子科技大学硕士学位论文
摘要
在互联网中,以新闻、电子书以及其它形式存在的信息正在高速增长,如何有效地运用
海量信息成为人们目前面临的一个关键问题。为了梳理各种杂乱的信息,有监督的分类方法
被用于大规模文档分类,但此类方法都有一个内在的缺点,即需要大量的人工干预才能获得
比较好的分类结果。为了解决人工干预问题,本文重点研究在文本数据挖掘中引入无监督的
大规模文本聚类方法。
首先,本文对文本聚类技术的现状和发展进行了简要的回顾。文中分别对文本信息预处
理的相关技术和文本聚类算法作了分析。文本信息预处理主要包括文本分词、文本特征提取
和文本相似度计算等部分。文本聚类算法部分主要介绍了目前已有的各种聚类算法并对其进
行比较分析,包括 K-means 聚类算法、凝聚层次聚类算法、基于密度的聚类算法、基于遗传
算法的聚类算法和基于蚁群的聚类算法等。本文根据文本聚类算法的特殊性,在快速分词的
方法中,采用分级词库的处理方法;在文本信息存储处理中,采用压缩处理的方法。
然后,本文着重研究了基于蚁群算法的文本聚类算法。在改进蚁群算法的同时,将凝聚
聚类算法融入蚁群算法框架,进一步提高聚类的速度。在分析蚁群算法在文本聚类中的优缺
点基础上,针对蚁群算法放置物体时的分散状况,采用了紧凑算法;针对蚁群对选择物体的
随机性问题,提出了基于评估函数的拾起物体算法;针对蚁群算法的终止条件难以估计和不
准确的问题,提出了根据用户输入的预期类数和类内、类间距离相结合的判别方法;针对蚁
群算法在引入随机计算时的复杂度问题,将放置物体的阈值参数修改为动态可变参数。在分
析蚁群算法的框架基础上,利用凝聚聚类算法速度快的特点,融合凝聚聚类算法到蚁群算法,
改进了蚁群算法收敛速度慢的问题。
最后,分别使用标准数据集和两个真实语料库对本文提出的基于蚁群和凝聚的混合聚类
算法进行了实验,并对测试结果进行了比较和分析,采用基于外部度量的总 F-measure 方法
和聚类时间对聚类结果进行评价。实验结果表明,本文提出的混合聚类算法对于处理大规模
文本聚类问题具有较明显的优势。

关键词:文本聚类,蚁群算法,凝聚算法,文本挖掘,中文信息处理
I
杭州电子科技大学硕士学位论文
ABSTRACT
The information amount on such as news, e-books and work information
source is quickly increasing. How to make use of such huge digital information collection
efficiently es one of the important problems we are facing. In order anize the
information, supervised category methods are introduced to classify information. But all these
methods have an intrinsic disadvantage, that is, it needs human intervene in order to obtain qualified
results. To e the ings of these category methods, this thesis mainly focuses on
applying unsupervised clustering methods of text mining to large-scale text data set.
In this thesis, firstly, we present a brief review on text clustering technology development.
Some investigations on Chinese text pre-processing and text clustering algorithms are also
presented. The former part includes word segmentation, text feature extraction and text similarity
measurement, etc. Th