图情大数据，文本聚类分析步骤和算法

聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法，同时也是数据挖掘的一个重要算法。文本聚类主要可以应用在如下方面：自然语言处理任务；搜索引擎中使用聚类对返回结果聚类；用户文档聚类；改善文本分类效果；数字图书馆服务；文档集合的自动整理等。聚类分析是由若干模式组成的。通常，模式是一个度量的向量，或者是多维空间中的一个点。聚类分析以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。在商业上，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体，并且概括出每一类消费者的消费模式或消费习惯。它作为数据挖掘中的一个模块，可以作为一个单独的工具以发现数据库中分布的一些深层信息，并且概括出每一类的特点，或者把注意力放在某一个特定的类上以作进一步的分析；聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。文本聚类过程可以分为3个步骤。

①文本表示（text representation）：把文档表示成聚类算法可以处理的形式。所采用的技术请参见文本分类部分。

②聚类算法选择或设计（clustering algorithms）：算法的选择，往往伴随着相似度计算方法的选择。在文本挖掘中，最常用的相似度计算方法是余弦相似度。聚类算法有很多种，但是没有一个通用的算法可以解决所有的聚类问题。因此，需要认真研究要解决的问题的特点，以选择合适的算法。

③聚类评估（clustering evaluation）：因为没有训练文档集合，所以评测聚类效果是比较困难的。常用的方法是：选择人工已经分好类或者做好标记的文档集合作为测试集合，聚类结束后，将聚类结果与已有的人工分类结果进行比较。常用评测指标也是查全率、查准率及F1值。

常用的聚类算法有以下几种：

1）基于层次聚类

这种方法对给定的数据集进行层次似的分解，直到满足某种条件为止。具体又可分为“自底向上”和“自顶向下”两种方案。例如，在“自底向上”方案中，初始时每一个数据记录都组成一个单独的组，在接下来的迭代中，把那些相互邻近的组合并成一个组，直到所有的记录组成一个分组或者满足某个条件为止。层次聚类方法可以是基于距离的或基于密度或连通性的，它的一些扩展也考虑了子空间聚类。层次聚类方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤销。这个严格规定的优点在于不用担心不同选择的组合数目，它将产生较小的计算数量；但它的缺点是不能更正错误的决定。另外，有层次聚类可以得到层次化的聚类结果，但是计算复杂度比较高，不能处理大量的文档。

基于层次聚类的常用方法有：BIRCH算法、CURE算法、CHAMELEON算法。

2）基于划分方法

先给定一个有N 个元组或者记录的数据集，分类法将构造K 个分组，每一个分组就代表一个聚类，K＜N。而且这K 个分组满足下列条件：

①每一个分组至少包含一个数据记录。

②每一个数据记录属于且仅属于一个分组。

对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的记录越远越好。而K-means算法是最常见的划分方法。给定簇的个数k，选定k个文本分别作为k个初始簇，将其他的文本加入最近的簇中，并更新簇的中心点，然后再根据新的中心点对文本重新划分；当簇不再变化时或经过一定次数的迭代之后，算法停止。K-means算法复杂度低，而且容易实现，但是对例外和噪声文本比较敏感。另外一个问题是，没有一个好的办法确定k的取值。

基于划分方法的算法特点是计算量大，很适合发现中小规模的数据库中的球状簇。常用的算法有：K-means算法、K-medoids算法、CLARANS算法。(www.xing528.com)

3）基于网格和密度的方法

基于网格和密度的聚类方法伴随着新近处理大规模数据集、可伸缩的聚类方法的开发，其在空间数据挖掘研究子域日趋活跃，在以空间信息处理为代表的众多领域有着广泛应用。基于密度的聚类算法通过数据密度（单位区域内的实例数）来发现任意形状的类簇，把密度大于某个阈值的点加到与之相近的聚类中。基于网格的聚类方法将数据空间划分成有限数目的单元格，把需要分析的数据的统计信息汇总到其所在的单元格中，通过分析单元格间的聚类特性完成对原始数据的聚类。由于聚类算法最终通过分析单元格来完成，而单元格的数量通常都远远小于原始数据的数量，所以其运算速度非常快。

基于网格的聚类算法具有较好的伸缩性，经常会与其他聚类方法结合以取得更好的效果，与基于密度的聚类算法的结合尤其常见，结合后同时具备了基于网格聚类的高效性与基于密度聚类的鲁棒性，被广泛地应用于空间信息处理等领域。以下介绍几种基于网格与密度的算法。

①GFDBSCAN（grid-based fast DBSCAN）算法是使用网格的方式缩小，首先将数据点映射到网格化的空间中，再定义每个网格的外围（将作为邻域搜索的外延），将中心网格与其外围网格一起定义为一个分区。然后在每个分区之内运行DBSCAN算法，再将每个分区内产生的簇进行合并。由于GFDBSCAN方法只在分区内查找邻域对象，而不是在全数据域中查找，从而降低了邻域查找的计算复杂度。

②SKNN（shared strict K-nearest neighbors）算法参考Jarvis等提出的共享最近邻概念，定义严格近邻集SKNN（x）=｛y｜y∈KNN（x），x∈KNN（y）｝，任意两个互为严格近邻的点x、y的相似度Similarity（x，y）=size（SKNN（x）∩SKNN（y）），则x点的密度为Density（x）=∑Similarity（x，y）。然后弃除密度低的点，并将密度高的点作为代表点，从代表点出发查找并删除权值（即两个点间的相似度）低于阈值的边。最终形成子图集，每个子图是一个簇。只有互相为严格k-最近邻的点间才会有一条边，噪声点不会与簇中的点有边，因为簇中的点的k-最近邻不会包含噪声点。另外，由于计算k-最近邻集时，计算的是各个数据点的最近邻居，并未限制邻居的距离，所以SKNN方法也可以很好地适应簇密度不一样的数据集。在SKNN算法中，利用网格的思想缩小查找k-最近邻集的范围，而不是在整个数据值域中计算k-最近邻集，从而大大地降低了算法的计算复杂度。

③GDILC（grid-based density-isoline clustering）算法由Zhao和Song于2001提出，算法的思想来自地图中的等高线，等高线描述了地理位置的水平高度，而在GDILC中，使用密度等值线描述数据的密度分布。可以指定一个阈值，当密度等值线的值大于此阈值时，等值线所包含的数据点形成一个簇。

④ASGC（an axis-shifted grid-clustering algorithm）算法使用了移动网格的思想，不需要将网格的大小定得非常小，并且可以解决两个簇距离过近而无法识别的问题。

⑤优化网格分割算法（Opti Grid）是面对高维数据聚类的算法，在OptiGrid中，利用基于密度函数的切面将数据空间根据数据的密度分割成不同形状大小的网格。OptiGrid算法基于坚固的数据理论，效率很高，可以处理高维数据。

4）基于模型的方法

为每簇假定了一个模型，寻找数据对给定模型的最佳拟合，这一类方法主要是指基于概率模型的方法和基于神经网络模型的方法，尤其以基于概率模型的方法居多。这里的概率模型主要指概率生成模型（generative model），同一“类”的数据属于同一种概率分布，即假设数据是根据潜在的概率分布生成的。其中最典型也最常用的方法就是高斯混合模型（Gaussian mixture models，GMM）。基于模型的方法对“类”的划分不那么“坚硬”，而是以概率形式表现，每一类的特征也可以用参数来表达，但其执行效率不高，特别是在分布数量很多并且数据量很少的时候。

5）其他聚类方法

①Affinity Propagation聚类算法，简称AP，是2007年发表在Science上一个比较新的算法。AP算法的基本思想是将全部样本看作网络的节点，然后通过网络中各条边的消息传递计算出各样本的聚类中心。聚类过程中，共有两种消息在各节点间传递，分别是吸引度（responsibility）和归属度（availability）。AP算法通过迭代过程不断更新每一个点的吸引度和归属度值，直到产生m 个高质量的质心（exemplar），同时将其余数据点分配到相应的聚类中。

②ACODF聚类算法。2004年，Tsai等人提出一个新颖的具有不同偏好的蚁群系统（novel AS）——ACODF（a novel data clustering approach for data mining in large databases），用来解决数据聚类问题［当时未见用于数据聚类的ACO（ant colony optimization）算法的报道］。设计一种不需要求解任何硬子问题（any hard sub-problem），但能给出近似最优解的聚类算法，是人们所期待的，ACODF能够快速获得最优解。