Week 8 Document Clustering(文本聚类)

一、Document Clustering

1、定义

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

2、过程

 

3、第一部分：分词处理

我们要把中文文章要进行分词，这一点中文文章和英文文章有一些区别，因为英文单词是单个构成的，而我们中文是需要分词的。另外需要加入一个停用词表，在进行分词的时候进行去掉。

4、第二部分：分词后将分词转换为词向量

关于词向量我们有一些比较常用的模型，比如one-hot，BOW词袋模型，连续词袋模型(CBOW)和Skip-Gram模型和Word2vec模型。

 

5、第三部分：选择聚类算法

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

二、用于文本分类的聚类算法

1 基于层次的聚类

层次聚类将文本对象组织成树，每个叶子节点是一个簇，该树称为一个聚类谱系图。根据树形成是自底向上还是自顶向下的，可以划分为凝聚式和分裂式层次聚类。层次聚类算法复杂度高，可根据需要获得不同粒度的类。比较有代表性的有BIRCH (Balanced Iterative Reducing and Clustering using Hierarchy)、CURE(Clustering Using REpresentatives)、Chameleon等都是基于层次思想的组合算法。BIRCH是一个增量式动态聚类分析算法，通过数据结构CF（Clustering Feature）树对数据进行聚类。Chameleon是一个两阶段的聚类分析算法。第一阶段是构建相似度矩阵，从矩阵中再构建K最近邻图，然后对于图进行划分得到小的簇；第二阶段是对小簇进行动态和并，合并时采用互连性与近似度来度量簇与簇之间的相似性。

2 基于划分的聚类

基于划分的聚类分析不需要建立起类之间的层次结构，只需要将数据集进行划分，形成一个平面的类结构。比较典型的方法有：

(1) K-Means聚类

K-Means聚类分析算法是一种简单效率高的聚类分析算法。K-Means将聚类对象划分成为K个簇（K是事先必须确定的参数），K-Means中每个簇用一个中心表示，该中心定义为簇中对象的平均值。K-Means聚类的缺点是必须事先给出K、对数据输入顺序敏感、不适于发现大小很大的簇、对于噪声和孤立点敏感等。在文本聚类中如果不进行特征选择，特征维度过高的话容易扎堆成几个大类和众多小类。

(2) K-Medoids聚类

K-Medoids聚类是与K-Means类似的一种聚类分析方法，其主要区别在于K-Means使用所有点的均值来代表簇，而K-Medoids则采用类中某个数据对象来代表簇。PAM（Partitioning Around Medoid）是最早提出的K-Medoids算法之一。与标准的K-Means相比，PAM通过反复计算随机选择的点与原有K个中心的交换代价来决定如何形成新的中心点。PAM算法复杂度高，对于大数据集合没有好的可伸缩性，因此由PAM演化出了CLARA（Clustering Large Applications）以及CLARANS（Clustering Large Application based upon Randomized Search）用于大规模空间数据的聚类分析。CLARA从原始对象随机采样得到K个中心点，可以进行多次采样得到更优的K个中心；而CLARANS比CLARA更进一步，每一次应用PAM时不是一个固定的采样样本。如果对于K-Medoids的簇中心重新定义，比如采用类似CURE的代表点的方式来代表一个簇，可以演化出新的算法。

(3) 最近邻聚类

最近邻聚类是一种简单的聚类分析。该算法认为，如果某个待处理的对象与现有的所有簇的最小距离小于给定阈值，那么将该对象归入该簇，否则将该对象作为一个新的簇。最近邻聚类不需要事先决定结果类数，适合于类内距离小，类间距离大的情况。结果与样本的输入顺序有关，也与阈值T有关。随着样本集的增大，产生的结果类数可能越来越多，处理的速度会越来越慢。

3. 基于密度的聚类

基于密度的聚类算法将簇看成是数据空间中被低密度区域分割开的高密度区域。密度定义为单位体积内的点数，簇的内部密度大。由于密度是一个局部概念，这类算法又称为局部聚类（Local Clustering）；基于密度的聚类算法通常只扫描一遍数据库，所以又称为单遍扫描聚类（Single Scan Clustering）。基于密度的聚类中比较典型的算法有DBScan（Desity-based Clustering）、OPTICS（Ordering Points to Identify the Clustering Structure）与DENCLUE（Density-based Clustering）。

对于空间中的一个对象，如果在给定半径Eps的邻域中的对象个数大于给定的数值Minpts，该对象称为核心对象（core point），否则称为边界对象。由一个核心对象可达的所有对象构成一个簇。DBSCAN在研究中得到比较多的关注，GDBSCAN（Generalized DBSCAN），DBCLASD（Distribution Based Clustering of Large Spatial Database），FDC（Fast Density-based Clustering）都是对DBSCAN的进一步扩展和优化。

4. 基于网格的聚类

基于网格的聚类首先把数据空间划分为一定数目的单元，以后所有的操作都针对这些单元，通过对单元的操作来产生结果簇。这种方法的优点是处理速度快，处理时间独立于数据对象的数目，仅仅依靠于网格空间的维度。基于网格的代表性例子有STING，它利用存储在网格中的统计信息；WaveCluster，它利用小波变换来聚类对象；CLIQUE，属于高维空间中基于网格和密度的方法。

5. 基于模型的聚类

基于模型的方法为每一个簇假定了一个模型，寻找数据对给定模型的最佳拟合。基于模型的方法有统计学方法COBWEB和自组织映射（SOM）神经网络方法等。其中自组织特征映射方法首先对文档降维，把特征维度降低到足够小，然后进行SOM聚类。该算法的意图是把SOM算法扩展到处理高维数据对象的领域，适合于用户对文档内容所属领域不太了解的情况。

与普通的聚类场景相比，文本聚类属于高维空间上的聚类分析。高维空间的数据经常呈现奇怪的特征，例如噪声的比例增加、网格单元的个数指数级增加、数据空间的稀疏性大、聚类的密度低等，这在数据挖掘中称为“维数祸根”。许多聚类分析的算法，例如DBSCAN、STING、WaveCluster，随着维数的增加，算法的空间和时间的复杂性往往增长得很快，所以很难实用化。对于传统的聚类算法来说，当应用在文本聚类的场景中时，除了要调整好参数以外，还要尽量避免高维特征所带来的影响。

三、EM算法用于文本聚类

1、Generative Model and Generating Words

2、Complete Data、Incomplete Data