中文文本聚类

一、文本聚类的目的：

对文本数据进行细粒度的分类，具体的，给每一个聚类一个标签就完成了分类。

二、聚类的原理：

2.1分类与聚类的区别：

在分类中，我们有已知的类标签的数据，我试图了解是什么区分了这些组（即，分类函数），以正确地分类未来的数据。

在聚类中，我们查看数据，其中数据类别是未知的和未定义的，我尝试学习数据本身，以及它们的区别。

以k-means聚类举例子：

1. means聚类：将数据集划分为K个不同的、不重叠的聚类的简单方法。

1.要执行K-means集群：请指定所需的集群数量K.

2.然后K-means算法将每个观测值精确地分配给K个簇中的一个。

文本聚类其实也就是在文本方向上的应用,首先我们要把一个个文档的自然语言转换成数学信息,这样形成高维空间点之后再去计算点与点之间的距离,然后将这些距离比较近的聚成一个簇,这些簇的中心成为簇心.而我们做的就是保证簇内点的距离足够近,簇与簇的距离足够远。

2.2文本聚类过程：

图1 ：文本聚类过程

主要的过程如图1所示,其实主要的部分有三个:

第一部分,分词处理,我们要把中文文章要进行分词,这一点中文文章和英文文章有一些区别,因为英文单词是单个构成的,也就不需要分词了,而我们中文是需要分词的,并且中文之间有一些词尽管大量出现,但是对于文章的分类结构起不到太大的意义,比如”的”,”了”,”么””应该”,这些词去计算他们既浪费空间又浪费时间,出于+1s的因素,我们也要节约时间啊,首先我们就加入一个停用词表,在进行分词的时候进行去掉。

第二部分:分词后将分词转换为词向量

关于词向量我们有一些比较常用的模型,比如one-hot,BOW词袋模型,连续词袋模型(CBOW)和Skip-Gram模型和Word2vec模型,在这次任务中我是用的是BOW词袋模型,在转换为词向量值我们要将其转换成tf-idf矩阵,tf-idf其实可以看作是提取的特征的一次加权,是根据一个单词在当前文章中出现的频率和该单词在所有语料中出现的频率评估一个单词的重要性，当一个单词在这篇文章中出现的次数很多的时候，这个词语更加重要；但如果它在所有文章中出现的次数都很多，那么它就显得不那么重要。

第三部分:选择聚类算法

这里的算法大家常用的是K-means和DBSCAN,这两种算法用的最多,但是在高维空间里边K-means似乎并不是很好,究其原因是因为维度太高,簇与簇之间的距离太小了,如果直接去聚类,这一部分似乎效果不太好,这时候就需要用到主成成分分析PCA,大致的思路是大致意思就是取这个高维向量中方差最大的方向经过一些数学变换将有用的部分保留，没用的部分舍弃，这种办法同样适合分类算法中寻找最大的特征。

2.3常见聚类算法以及区别：

聚类分为：基于划分、层次、密度、图形和模型五大类:

K-means算法：K-means算法应该算是最常见的聚类算法，该算法的目的是选择出质心，使得各个聚类内部的inertia值最小化。但是在高维空间中，欧式距离的值可能会呈现迅速增长的趋势，所以在进行K-means之前首先进行降维操作，如PCA等，可以解决高维空间中inertia快速增长的问题，也有助于提高计算速度。

K-means算法可以在足够长的时间内收敛，但有可能收敛到一个局部最小值。聚类的结果高度依赖质心的初始化，因此在计算过程中，采取的措施是进行不止一次的聚类，每次都初始化不同的质心。
sklearn中可以通过设置参数init='kmeans++'来采取k-means++初始化方案，即初始化的质心相互之间距离很远，这种方式相比于随机初始质心，能够取得更好的效果。另外，sklearn中可以通过参数n_job，使得K-means采用并行计算的方式。

DBSCAN算法：DBSCAN算法的主要思想是，认为密度稠密的区域是一个聚类，各个聚类是被密度稀疏的区域划分开来的。也就是说，密度稀疏的区域构成了各个聚类之间的划分界限。与K-means等算法相比，该算法的主要优点包括：可以自主计算聚类的数目，不需要认为指定；不要求类的形状是凸的，可以是任意形状的。

DBSCAN中包含的几个关键概念包括core sample，non-core sample，min_sample，eps。
core samle是指，在该数据点周围eps（Eps 表示数据点的邻域半径）范围内，至少包含min_sample个其他数据点，则该点是core sample，这些数据点称为core sample的邻居。与之对应的，non-sample是该点周围eps范围内，所包含的数据点个数少于min_sample个。从定义可知，core sample是位于密度稠密区域的点。

一个聚类就是一个core sample的集合，这个集合的构建过程是一个递归的构成。首先，找到任意个core sample，然后从它的邻居中找到core sample，接着递归的从这些邻居中的core sample的邻居中继续找core sample。要注意core sample的邻居中不仅有其他core sample，也有一些non-core smaple，也正是因为这个原因，聚类集合中也包含少量的non-core sample，它们是聚类中core sample的邻居，但自己不是core sample。这些non-core sample构成了边界。

在确定了如何通过单一core sample找到了一个聚类后，下面描述DBSCAN算法的整个流程。
首先，扫描数据集找到任意一个core sample，以此core sample为起点，按照上一段描述的方法进行扩充，确定一个聚类。然后，再次扫描数据集，找到任意一个不属于以确定类别的core sample，重复扩充过程，再次确定一个聚类。迭代这个过程，直至数据集中不再包含有core sample。这也是为什么DBSCAN不用认为指定聚类数目的原因。

DBSCAN算法包含一定的非确定性。数据中的core sample总是会被分配到相同的聚类中的，哪怕在统一数据集上多次运行DBSCAN。其不确定性主要体现在non-core sample的分配上。一个non-core sample可能同时是两个core sample的邻居，而这两个core sample隶属于不同的聚类。DBSCAN中，这个non-core sample会被分配给首先生成的那个聚类，而哪个聚类先生成是随机的。

sklearn中DBSCAN的实现中，邻居的确定使用的ball tree和kd-tree思想，这就避免了计算距离矩阵。

RIRCH聚类算法原理

BIRCH算法比较适合于数据量大，类别数K也比较多的情况。它运行速度很快，只需要单遍扫描数据集就能进行聚类，当然需要用到一些技巧，下面我们就对BIRCH算法做一个总结。

BIRCH的全称是利用层次方法的平衡迭代规约和聚类（Balanced Iterative Reducing and Clustering Using Hierarchies），它是用层次方法来聚类和规约数据。

BIRCH只需要单遍扫描数据集就能进行聚类，那它是怎么做到的呢？

BIRCH算法利用了一个树结构来帮助我们快速的聚类，这个树结构类似于平衡B+树，一般将它称之为聚类特征树(Clustering Feature Tree，简称CF Tree)。这颗树的每一个节点是由若干个聚类特征(Clustering Feature，简称CF)组成。

聚类特征树：每个节点包括叶子节点都有若干个CF，而内部节点的CF有指向孩子节点的指针，所有的叶子节点用一个双向链表链接起来。但是如果数据特征的维度非常大，比如大于20，则BIRCH不太适。

均值聚类k-means是基于划分的聚类， DBSCAN是基于密度的聚类，Brich是基于层次的聚类。区别为：

k-means需要指定聚类簇数k，并且且初始聚类中心对聚类影响很大。k-means把任何点都归到了某一个类，对异常点比较敏感。DBSCAN能剔除噪声，需要指定邻域距离阈值eps和样本个数阈值MinPts，可以自动确定簇个数。

K均值和DBSCAN都是将每个对象指派到单个簇的划分聚类算法，但是K均值一般聚类所有对象，而DBSCAN丢弃被它识别为噪声的对象。

K均值很难处理非球形的簇和不同大小的簇。DBSCAN可以处理不同大小或形状的簇，并且不太受噪声和离群点的影响。当簇具有很不相同的密度时，两种算法的性能都很差。

K均值只能用于具有明确定义的质心（比如均值或中位数）的数据。DBSCAN要求密度定义（基于传统的欧几里得密度概念）对于数据是有意义的。

K均值算法的时间复杂度是O(n)，而DBSCAN的时间复杂度是O(n2)。

DBSCAN多次运行产生相同的结果，而K均值通常使用随机初始化质心，不会产生相同的结果。

K均值DBSCAN和都寻找使用所有属性的簇，即它们都不寻找可能只涉及某个属性子集的簇。

K均值可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN会合并有重叠的簇。

K均值可以用于稀疏的高维数据，如文档数据。DBSCAN通常在这类数据上的性能很差，因为对于高维数据，传统的欧几里得密度定义不能很好处理它们。

补充：

1、TF-IDF算法介绍

TF-IDF（term frequency–inverse document frequency，词频-逆向文件频率）是一种用于信息检索（information retrieval）与文本挖掘（text mining）的常用加权技术。

TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。

TF-IDF的主要思想是：如果某个单词在一篇文章中出现的频率TF高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。

（1）TF是词频(Term Frequency)

词频（TF）表示词条（关键字）在文本中出现的频率。

这个数字通常会被归一化(一般是词频除以文章总词数), 以防止它偏向长的文件。

公式：

即：

其中 ni,j 是该词在文件 dj 中出现的次数，分母则是文件 dj 中所有词汇出现的次数总和；

（2） IDF是逆向文件频率(Inverse Document Frequency)

逆向文件频率 (IDF) ：某一特定词语的IDF，可以由总文件数目除以包含该词语的文件的数目，再将得到的商取对数得到。

如果包含词条t的文档越少, IDF越大，则说明词条具有很好的类别区分能力。

公式：

其中，|D| 是语料库中的文件总数。 |{j:ti∈dj}| 表示包含词语 ti 的文件数目（即 ni,j≠0 的文件数目）。如果该词语不在语料库中，就会导致分母为零，因此一般情况下使用 1+|{j:ti∈dj}|

即：

（3）TF-IDF实际上是：TF * IDF

某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF。因此，TF-IDF倾向于过滤掉常见的词语，保留重要的词语。

公式：

注：TF-IDF算法非常容易理解，并且很容易实现，但是其简单结构并没有考虑词语的语义信息，无法处理一词多义与一义多词的情况。

2、TF-IDF应用

（1）搜索引擎；（2）关键词提取；（3）文本相似性；（4）文本摘要

参考：

(135条消息) Python实现TF-IDF提取关键词（sklearn库的使用）_tfidf关键词提取python_明日何其多_的博客-CSDN博客

三、实验：

3.1原始数据：

3.2K-means算法demo:

3.3结果：

图2：DBscan聚类图

图3：Birch聚类图

图4：K-means聚类算法图

图5：文本分类结果展示

四、聚类的评价指标：

1.Rand Index

Rand Index（兰德指数）是一种衡量聚类算法性能的指标。它衡量的是聚类算法将数据点分配到聚类中的准确程度。兰德指数的范围从0到1,1的值表示两个聚类完全相同，接近0的值表示两个聚类有很大的不同。需要注意的是，Rand Index只能用于评估将样本点分成两个簇的聚类算法。对于将样本点分成多个簇的聚类算法，需要使用其他的指标来评估其性能。

它的公式如下:

2.Adjusted Rand Score

Adjusted Rand Score（调整兰德指数）是一种用于衡量聚类算法性能的指标，它是Rand Index的一种调整形式，可以用于评估将样本点分为多个簇的聚类算法。它考虑了机会的概率，取值范围为，其中值越接近1表示聚类结果越准确，值越接近0表示聚类结果与随机结果相当，值越接近-1表示聚类结果与真实类别完全相反。

1. Mutual Information-based Score

基于互信息的分数（Mutual Information-based Score）是一种用于衡量聚类算法性能的指标，它衡量的是聚类结果与真实标签之间的相似性。基于互信息的分数可以用于评估将样本点分为多个簇的聚类算法。

基于互信息的分数的取值范围为，其中值越接近1表示聚类结果越准确，值越接近0表示聚类结果与随机结果相当，值越小表示聚类结果与真实类别之间的差异越大。基于互信息的分数是一种相对指标，它的取值受到真实类别数量的影响。当真实类别数量很大时，基于互信息的分数可能会受到偏差。