文本聚类算法介绍

转载请注明出处：http://blog.csdn.net/xiaojimanman/article/details/44977889

      本博客通过对当前比较成熟的聚类算法分析，介绍如何对非结构的数据（文档）做聚类算法，第一大部分的内容来源百度百科，第二部分是对文本聚类算法思想的介绍。这里因为各种原因就不给出具体的代码实现，如若有兴趣，可以在后面留言一起讨论。

###################################################################################
#####以下内容为聚类介绍，来源百度百科，如果已经了解，可以直接忽略跳到下一部分
###################################################################################

聚类概念
      聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法，同时也是数据挖掘的一个重要算法。聚类（Cluster）分析是由若干模式（Pattern）组成的，通常，模式是一个度量（Measurement）的向量，或者是多维空间中的一个点。聚类分析以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。

算法用途
      在商业上，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯。它作为数据挖掘中的一个模块，可以作为一个单独的工具以发现数据库中分布的一些深层的信息，并且概括出每一类的特点，或者把注意力放在某一个特定的类上以作进一步的分析；并且，聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。
聚类分析的算法可以分为划分法（Partitioning Methods）、层次法（Hierarchical Methods）、基于密度的方法（density-based methods）、基于网格的方法（grid-based methods）、基于模型的方法（Model-Based Methods）。

算法分类
      很难对聚类方法提出一个简洁的分类，因为这些类别可能重叠，从而使得一种方法具有几类的特征，尽管如此，对于各种不同的聚类方法提供一个相对有组织的描述依然是有用的，为聚类分析计算方法主要有如下几种：

划分法
      划分法(partitioning methods)，给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K<N。而且这K个分组满足下列条件：
（1） 每一个分组至少包含一个数据纪录；
（2）每一个数据纪录属于且仅属于一个分组（注意：这个要求在某些模糊聚类算法中可以放宽）；
      对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的纪录越远越好。
      大部分划分方法是基于距离的。给定要构建的分区数k，划分方法首先创建一个初始化划分。然后，它采用一种迭代的重定位技术，通过把对象从一个组移动到另一个组来进行划分。一个好的划分的一般准备是：同一个簇中的对象尽可能相互接近或相关，而不同的簇中的对象尽可能远离或不同。还有许多评判划分质量的其他准则。传统的划分方法可以扩展到子空间聚类，而不是搜索整个数据空间。当存在很多属性并且数据稀疏时，这是有用的。为了达到全局最优，基于划分的聚类可能需要穷举所有可能的划分，计算量极大。实际上，大多数应用都采用了流行的启发式方法，如k-均值和k-中心算法，渐近的提高聚类质量，逼近局部最优解。这些启发式聚类方法很适合发现中小规模的数据库中小规模的数据库中的球状簇。为了发现具有复杂形状的簇和对超大型数据集进行聚类，需要进一步扩展基于划分的方法。
使用这个基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法；

层次法
      层次法(hierarchical methods)，这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。
例如，在“自底向上”方案中，初始时每一个数据纪录都组成一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一个组，直到所有的记录组成一个分组或者某个条件满足为止。
      层次聚类方法可以是基于距离的或基于密度或连通性的。层次聚类方法的一些扩展也考虑了子空间聚类。层次方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤销。这个严格规定是有用的，因为不用担心不同选择的组合数目，它将产生较小的计算开销。然而这种技术不能更正错误的决定。已经提出了一些提高层次聚类质量的方法。
代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等；

密度算法
      基于密度的方法(density-based methods)，基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。
      这个方法的指导思想就是，只要一个区域中的点的密度大过某个阈值，就把它加到与之相近的聚类中去。
代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等；

图论聚类法
      图论聚类方法解决的第一步是建立与问题相适应的图，图的节点对应于被分析数据的最小单元，图的边（或弧）对应于最小处理单元数据之间的相似性度量。因此，每一个最小处理单元数据之间都会有一个度量表达，这就确保了数据的局部特性比较易于处理。图论聚类法是以样本数据的局域连接特征作为聚类的主要信息源，因而其主要优点是易于处理局部数据的特性。

网格算法
      基于网格的方法(grid-based methods)，这种方法首先将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很快，通常这是与目标数据库中记录的个数无关的，它只与把数据空间分为多少个单元有关。
代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法；

模型算法
      基于模型的方法(model-based methods)，基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。
通常有两种尝试方向：统计的方案和神经网络的方案。

###################################################################################
#####以下内容为文本聚类方法分析
###################################################################################

文本聚类
      目前针对聚类算法的研究多数都是基于结构化数据，很少有针对非结构化数据的，这里就介绍下自己对这方面的研究。由于源码目前牵扯到一系列的问题，所以这里就只介绍思想，不提供源码，如有想进一步了解的，可以在下方留言。
      文本聚类（Text clustering）文档聚类主要是依据著名的聚类假设：同类的文档相似度较大，而不同类的文档相似度较小。作为一种无监督的机器学习方法，聚类由于不需要训练过程，以及不需要预先对文档手工标注类别，因此具有一定的灵活性和较高的自动化处理能力，已经成为对文本信息进行有效地组织、摘要和导航的重要手段。
我们本次的介绍重点就是介绍如何对非结构化的文本做聚类。

文本聚类思想
      由于目前对结构化的数据的聚类研究已经十分成熟，所以我们就要想办法把这种非结构化的数据转化为结构化的数据，这样也许就会很好处理。
      由于自己的工作方向是搜索引擎，所以自己的一些算法思想也都是基于它来的，对于如何将非结构话的数据转化为结构化的数据，可以参照下博客《基于lucene的案例开发：索引数学模型》。
下面给出具体的算法说明：
第一步：记录分词
这里为了简化模型，我们就直接默认一篇文本只有一个属性。在这一步中，我们需要对所有的文档做初始化分析，过程中我们需要统计如下几个值：第N篇文档包含哪些词元、第N篇文档中的词元M在文档N中出现的次数、词元M在多少篇文档中出现、词元M在所有文档中出现的次数。在这一步中，需要使用到分词技术，当处理中文的时候，建议使用IK等中文分词器，其他通用分词器处理的效果不是太好。这一步将文档转化为Document = {term1, term2, term3 …… termN}；
第二步：计算权重
这里的计算权重方法和之前的稍微有一点区别，具体计算公式如下：

通过这一步的处理，我们就将Document = {term1, term2, term3 …… termN}转化为DocumentVector = {weight1, weight2, weight3 …… weightN}
第三步：N维空间向量模型
我们将第二步得到的DocumentVector放到N维空间向量模型中（N是词元的总数），文档D在m坐标上的映射为文档D中的m词元的权重，具体如下图：

第四步：最相近的文档
在N维空间向量模型中，我们规定夹角越小，两篇文档就越相似。这一步，我们需要找到两个夹角最下的两个向量（即最相似的两篇文档）；
第五步：合并文档
将第四步得到的两篇文档视为一篇文档（即将这两篇文档当作一个类别）；
第六步：验证
判断这时的文档数目是否满足要求（目前剩余的文档数是否等于要聚类的类别数），如果满足要求结束本次算法，不满足要求，跳到第二步循环2、3、4、5、6。

算法评估

      目前在自己工作笔记本（配置一般，内存4G）上的测试结果是聚类1W篇文档耗时在40s~50s，下图是对10条数据的聚类效果截图：