文本聚类算法之K-means算法的python实现

一、文本聚类定义

       文本聚类主要是依据著名的聚类假设：同类的文档相似度较大，而不同类的文档相似度较小。作为一种无监督的机器学习方法，聚类由于不需要训练过程，以及不需要预先对文档手工标注类别，因此具有一定的灵活性和较高的自动化处理能力，已经成为对文本信息进行有效地组织、摘要和导航的重要手段。

二、算法分类

1、划分法（基于划分的聚类算法）

       给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K<N。而且这K个分组满足下列条件：（1）每一个分组至少包含一个数据纪录；（2）每一个数据纪录属于且仅属于一个分组（注意：这个要求在某些模糊聚类算法中可以放宽）；对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的记录越远越好。

       使用这个基本思想的算法有：K-Means算法、K-MEDOIDS算法、CLARANS算法。

       K-means算法是一种典型的基于划分的聚类算法，该聚类算法的基本思想是在聚类开始时根据用户预设的类簇数目k随机地在所有文本集当中选择k个对象，将这些对象作为k个初始类簇的平均值或者中心，对于文本集中剩余的每个对象，根据对象到每一个类簇中心的欧几里得距离，划分到最近的类簇中；全部分配完之后，重新计算每个类簇的平均值或者中心，再计算每篇文本距离这些新的类簇平均值或中心的距离，将文本重新归入目前最近的类簇中；不断重复这个过程，直到所有的样本都不能再重新分配为止。

       K-means算法优点：（1）对待处理文本的输入顺序不太敏感（2）对凸型聚类有较好结果（3）可在任意范围内进行聚类。

       缺点：（1）对初始聚类中心的选取比较敏感，往往得不到全局最优解，得到的多是次优解（2）关于算法需要预先设定的k值，限定了聚类结果中话题的个数，这在非给定语料的应用中并不可行（3）该算法容易受到异常点的干扰而造成结果的严重偏差（4）算法缺少可伸缩性

2、层次法（基于层次的聚类算法）

       这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案，即合并聚类（由下而上）和分裂聚类（由上而下）。

       合并层次聚类是将语料库中的任一数据都当作一个新的簇，计算所有簇相互之间的相似度，然后将相似度最大的两个簇进行合并，重复这个步骤直到达到某个终止条件，因此合并聚类方法也被称为由下而上的方法。

       分裂聚类恰好与合并聚类进行相反的操作，它是一种由上而下的方法，该方法先将数据集中所有的对象都归为同一簇，并将不断地对原来的簇进行划分从而得到更小的簇，直到满足最初设定的某个终止条件。

       层次聚类法的优点：（1）适用于发现任意形状的簇（2）适用于任意形式的相似度或距离表示形式（3）聚类粒度的灵活性

       缺点：（1）算法终止的条件很模糊，难以精确表达并控制算法的停止（2）一旦聚类结果形成，一般不再重新构建层次结构来提高聚类的性能（3）难以处理大规模数据，也不能适应动态数据集的处理。

       由于层次聚类算法简单，因此针对它的研究也比较多，也提出了不少改进算法，主要方向就是将该策略与其他聚类策略相结合从而形成多层聚类。

       代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等。

三、K-Means算法简介

      算法接受参数k，然后将事先输入的n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得的一个“中心对象”来进行计算的。

       基本思想：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。

       算法描述：

       （1）适当选择c个类的初始中心

       （2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类。

       （3）利用均值等方法更新该类的中心值。

       （4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。

       该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式

四、实验

实验数据集来自于网上，数据文件新建文本文档.txt 中的内容如下：

初始设置了k=4个质心

画出的图如下所示：