文本聚类算法初探

西安外事学院工学院 马军红

1.引言

随着信息技术的发展，各种科技文献以及互联网上的信息爆炸式的出现在人们面前，如何自动处理大量的数字化文本已经成为文本挖掘、信息过滤和信息检索等方面的研究成为当前研究的热点。快速高质量的文本聚类技术可以将大量文本信息组成少数有意义的簇，能够提供导航和浏览机制，通过聚类驱动的降维或权值调整来改善检索性能，是文本信息挖掘技术中的核心技术。

2.文本聚类的应用与研究

2.1 文本聚类的应用

聚类是一种非监督学习，其类别不是人为指定的而是分析数据的结果，完全由计算机自动进行，不需要人工干预。

文本聚类一般可以用于以下几个方面：

1）提供对一个大的文本集内容的概括；

2）识别隐藏的共同点；

3）使找到相近或相关的浏览程序简单化。

通过比较数据的相似性和差异性，能发现数据的内在特征及分布规律，从而获得对数据更深刻的理解与认识。

2.2 文本聚类算法的特点

文本聚类是在传统聚类分析的基础上发展而来的，是传统聚类算法在文本挖掘领域的应用。可以说它既是一种知识获取技术，也是一种文本处理过程。

文本聚类是基于“聚类假设”，即：相关文本之间的相似性比无关文本之间的相似性更大。它把一个文本集分成若干称为簇（cluster）的子集，每个簇中的文本之间具有较大的相似性，而簇之间的文本具有较小的相似性。但是，应用传统聚类算法得到的文本聚类结果在实践中并不十分理想。目前，文本聚类的区别于其他领域的特点主要是集中在以下几个方面：

1）文本数据是半结构化的数据。

在这里的半结构化是指文本数据既不是完全结构化的，也不是完全无结构化的。这就使得一些基于数据库的算法不能适用于文本聚类，所以文本聚类首先应该考虑文本的表示问题。

2）文本数据的高维化问题。

文本集合所采用的向量空间模型表示法会使向量空间的维度非常高，一般在103-104的量级上，高维数据和以往的聚类对象最重要的区别在于：在高维空间中，如果仍然采用距离作为衡量对象之间相似度的标准，经计算，有时距离很近的对象反而比距离很远的对象之间的差别大。这意味着基于距离的距离算法不再那么有效，大量采用距离尺度的传统聚类算法将很难取得令人满意的聚类效果。因此，特征集的缩减成为文本聚类中必不可少的一步。

3）文本聚类与语义的结合问题。

文本聚类是文本信息处理领域的一个重要分支，文本信息处理的根本目标是使机器能够“一定程度上理解并自动处理”文本信息，而文本聚类的目的也不外乎是使机器能够在“一定程度上理解并自动组织”文本信息。换句话说，处理只是手段，自动组织才是最重的目标。如果在文本中出现“足球”和“体育”两个名词，按照传统的聚类思想，这两个词是毫无相关的，但是众所周知“足球”是“体育”的一项运动。它属于“体育”的范畴，并非毫无相干。那么，在聚类是如何识别？因此，在语义问题上文本聚类还有很大研究空间。

4）聚类算法中的参数确定问题。

目前大多数算法都需要预先输入一些参数，这些参数设置的准确与否直接影响到文本聚类的效率和结果，预先输入的参数是在这样一个前提下：人们已经知道这些参数或知道大致范围。而实际上在大多数情况下，做到这一点非常困难。

3.常用聚类算法及其分析

3.1 基于划分的算法

给定n个对象的数据集，基于划分方法构建数据的k个划分，每个划分表示一类，并满足：每个划分至少包含一个对象；每个对象必须属于并且只属于一个划分。其基本思想是给定要构建的划分数目k，首先创建一个初始划分，然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。其典型算法是K-means，其原理是：

首先从数据集合X={X1，X2，……Xn}中随机地选取k个对象，每个对象初始地代表了一个簇的中心。对于X中任意对象Xi，计算它到各个簇中心的距离(采用欧式距离或者余弦相似度)，根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的中心(计算簇中数据的平均值)。这个过程不断重复，直到簇中心不再发生改变或准则函数收敛。

K－means算法的优点是：

1）对数值属性有很好的几何和统计意义；

2）对顺序不太敏感；

3）对凸型聚类有较好结果；

4）可在任意范数下进行聚类。

缺点是：

1）对初始聚类中心选取较敏感，往往得不到全局最优解，而常常得到的是次优解；

2）关于K值的确定没有可行的依据；

3）聚类结果有时会失衡；

4）对“噪声”和孤立点数据是敏感的，少量的该数据能对平均值产生很大的影响。

3.2 层次聚类算法

层次聚类算法是对给定的对象集合进行层次的分解。其基本思想是将模式样本按距离准则逐步聚类，直到满足分类为止，其聚类过程可表示为一棵二叉层次树，叶节点表示一个样本，中间节点便是将数据分成两个不同的类，或者是一个类由它的两个子类合并而成。根据层次的分解形成原理，层次的方法可分为凝聚方法和分裂方法。

如果给定文档集合是D={d1；d2；……dn}，层次凝聚法的具体步骤如下：

Step1.将D中的每个文档di试看作是一个具有单个成员的类ci={di}，这些类构成了的一个聚类C={C1；C2；……Cn}；

Step2.计算C中每对类{Ci，Cj}之间的相似度Sim（Ci，Cj）；

Step3.选取具有最大相似度的类对argmax Sim（Ci，Cj），并将Ci和Cj合并为一个新的类，从而构成了的一个新的聚类C={C1；C2；……Cn-1}；

Step4.重复以上步骤，直至C中剩下一个类或者达到一终止条件。

层次聚类算法的优点是适用于任意形状，适用于任意形式的相似度或距离形式，固有的对聚类粒度的灵活性。缺点是终止条件不很精确，一旦聚类结果形成，一般不再重新构建提高聚类性能，并且难以适应动态数据集，计算复杂度非线性。

3.3 基于模型的方法

基于模型的方法为每个簇假设一个模型，寻找数据对给定模型的最佳拟合。它试图优化给定的数据和某些数学模型之间的适应性。这样的方法经常是基于这样的假设：数据是根据潜在的概率分布产生的。基于模型的方法主要有两类：统计学方法和神经网络方法。

除了以上介绍的几类聚类算法，还有许多其他的聚类算法。

4.分析与总结

文本聚类是典型的高维数据的聚类，因而也具有一般高维聚类的特点。以前的研究着重于层次聚类算法，随着web文档的高速增长，由于传统的层次聚类时间复杂度的非线性，它难以处理日益增多的数据量。出于效率考虑，当前人们更多研究的是如何改进平面划分算法（比如k-means、SOM算法）。

目前，各种算法的融合问题也是比较热门的研究方向。通过对各种聚类算法的研究分析，发现聚类算法的优缺点，将其他算法引入聚类算法中以达到优化改进聚类算法的某一过程，从而达到提高聚类算法性能的目的。

[1]冯少荣,肖文俊.基于语义距离的高效文本聚类算法[J].华南理工大学学报,2008,36(5).

[2]丘志宏,宫雷光.利用上下文提高文本聚类的效果[J].中文信息学报,2007,21(6).

[3]尉景辉,何丕廉，,孙越恒.基于k-means的文本层次聚类算法研究[J].计算机应用,2010(10).