文本聚类算法综述

摘要：随着Internet的发展，作为数据挖掘关键技术的文本聚类也快速的发展起来。本文主要介绍了文本聚类的一些主要的算法以及文本聚类中使用到的关键技术，从而对文本聚类有了更深一步的了解。

关键词：文本聚类；算法；层次；划分；密度；网格；模型

中图分类号：TP391.1 文献标识码：A文章编号：1007-9599 (2011) 05-0000-01

Text Clustering Algorithms

Chen Ronglei

(College of Computer Science,Sichuan University,Chengdu 610065,China)

Abstract:With the Internet's development,as a key technology of data mining clustering also developed rapidly.This paper describes some of the main text clustering and text clustering algorithms to the key technologies used,to have a deeper understanding of text clustering.

Keywords:Text clustering; Algorithm;Level;Division;Density;Grid;

Model

一、文本聚类研究现状

文本聚类是搜索引擎和语义web的基本技术。随着网络信息的快速增长，提供一种有效的机制用来组织网络文本、帮助使用者获得他们想要的信息变得愈加重要。近年来，文本挖掘、信息过滤和信息检索等方面的研究出现了前所未有的高潮。作为一种无监督的机器学习方法，聚类技术可以将大量文本信息组成少数有意义的簇，并提供导航或浏览机制。

到目前为止，聚类分析的研究工作可以分为两大类：一般聚类方法和算法的研究和研究不同类型领域的聚类。

目前第一类研究己经取得了大量的研究成果，这些研究基本上是基于结构化数据的，比如事物数据库，然而却很少有工作研究非结构化数据。第二类研究的成果还相对较少，目前随着多媒体技术和互连网的迅速发展，开展这一领域的研究己成为新的热点，有大量的研究工作需要开展，如并行聚类算法、复杂数据的聚类算法、算法聚类结果的可视化、聚类结果的质量提高等。

二、文本聚类的关键技术

（一）文本的特征向量

文本的特征向量是通过文档的预处理（文本分词和文档特征向量的提取），将文档用一维向量表示，这个一维向量即文档的特征向量。

（二）文本之间的距离

为了定义文本之间的相近或者相似程度，需要定义一些划分类别的计量指标。常用的统计指标有距离和相似系数。“距离”属于相异性测度指标，“相似系数”属于相似性测度指标。距离和相似系数成反比，如 。对于有n个特征属性的文档集合来说，m个文档可以看作n维空间中的m个点。为此，我们可以用点之间的距离来度量文档之间的距离。

（三）权值表示

1.布尔权重（Boolean Weighting）。布尔权重方法是最简单的特征表示方法，如果特征向量的第i个分量在本篇文档中出现，则其权重为1，否则为0。

2.词频权重（Word frequency Weighting）。词频权重也是一种非常简单的特征表示方法，它只是简单地将特征i在文档 k中出现概率 作为其特征值。

3.TFIDF权重（Tfidf Weighting）。前两种方法并没有计算特征 i 在整个训练集合中出现的概率，一个非常有名的特征权重表示方法考虑了这一点，它就是TFIDF方法，计算公式如下：

（四）文本类之间的距离

设 和 是两个文档集合，具有n个特征属性，即n个索引词。常见的度量两个文本类之间距离有最短距离、最短距离、重心距离、类平均距离、离差平方和、代表点等方法。

三、文本聚类的算法

目前存在大量的聚类算法。算法的选择取决于文档集合的类型，聚类的目的和应用。如果聚类分析被用作描述或探查的工具，可以对同样的数据尝试多种算法，以发现数据可能揭示的结果。聚类在本质上是一种通过对对象集合按照某种规则进行划分或覆盖从而发现隐含的潜在有用的信息的一种知识发现的方法。聚类算法通常有以下几类：1.通过构建类别层次或者构造一棵类别树进行聚类的层次聚类算法。2.按其连接分量的密度定义类别的基于密度的聚类方法。3.基于网格（Grid-Based Method）的聚类方法。

（一）基于层次的聚类算法

一个层次的聚类算法将数据对象组织成一棵聚类的树。根据层次分解是自底向上还是自顶向下形成，层次的聚类算法可以进一步分为凝聚的和分裂的层次聚类。凝聚的方法也称作自底向上的方法。以开始将每个对象作为单独的一个组，然后相继地合并相似的对象或组，直到所有的组合并成一个，或者达到一个终止条件。分裂的方法也称作自顶向下的方法。以开始将所有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。

（二）基于密度的聚类算法

基于密度的聚类算法的主要思想是：将簇看成是数据空间中被低密度区域分割开的高密度区域。密度是指单位体积内的点数，簇内部的密度要比簇外大。基于密度的算法又被称为局部聚类。

（三）基于网格的聚类算法

为了减少搜索复杂度，需要考虑多边形分段区域。一个分段区域就是空间中的一个划分的小的超立方体，而利用划分空间进行聚类的方法通常就称为网格聚类算法。每一个分段区域就称为一个单元。网格聚类算法把对于数据的分割转换成对于空间的分割。数据分割通过数据点之间的关系导致的空间的分割而产生，但是空间分割则是基于输入数据累加的空间小超立方体（网格）。提出的基于密度的网格聚类算法，该算法兼有基于密度算法和基于网格算法的双重特性。

四、总结与展望

随着互联网的快速发展，互联网提供的信息也迅速膨胀起来。为了从海量信息中快速的获取有用的信息，数据挖掘技术迅速发展起来。作为数据挖掘技术中的重要技术之一――文本的聚类技术也相应的成熟起来。本文主要介绍了文本聚类的研究现状，文本聚类技术的特点及意义，文本聚类相应的关键技术，文本聚类的流行算法等。使我们对文本聚类技术有了大概的了解。在此基础上，未来可以通过不断地学习，发现现有的文本聚类算法的不足，提出积极地改进意见，为文本聚类技术的发展作出贡献。

参考文献：

[1]吴启明,易云飞.文本聚类综述[J].河池学院学报,VOI.28 No.2,2008

[2]谷波,张永奎.文本聚类算法的分析与比较[J].电脑开发与应用,VOI,16,No.11,2003

[3]潘启蒙.文本聚类算法的研究与实现[D].吉林大学,2008

[4]姚清耕.基于向量空间模型的中文文本聚类方法的研究[D].上海交通大学,2008