3 数据处理模型

3.1  向量空间模型

在向量空间模型下，n个文档，m个术语被表示成为一个m $\times$ n的term-document矩阵，每一个文档是一个m维的向量。

3.2 基于短语的模型

考虑短语“the dog chased a cat”和“the cat chased adog”。如果转化为向量的话，都是{chase，cat，dog} 但是它们的意义明显不一样。所以有的人就假设将单词的次序信息加入到聚类中能改善聚类的准确率。

下面我们介绍一种基于短语的模型。

文档索引图（DIG）在2004年由K. M.Hammouda 和 M. S.Kamel[18]提出，是基于单词次序匹配来定义相似度的。

DIG是一个多路有向图，每一个顶点表示一个单词。图的边表示单词的序列，每一个顶点都维护出现该词的文档列表，以及通过记录边的连续性来维护句子信息。如果一个单词在一个文档中出现多次，那么它在图中对应顶点的频率次数也相应增加。如图1是一个DIG例子。

图1：文档1包含“catchased rat” 和 “dogchased cat”。文档2包含“angrydog chased fat mailman” 和 “mailman ran”。文档3包含“littledogchased rat”。有向边表示一个句子。

   DIG将单词作为顶点存储，并在每个顶点维护频率信息,从而避免存储冗余信息。DIG不是一种聚类算法，只是一个利用有向边存储单词次序信息的文档模型。在这种模型下，基于重叠子图的相似度可以得到计算进而获得一个相似度矩阵。这种相似度矩阵可以利用任何一种谱算法或者区分算法进行聚类。

   结合单词次序信息与单词频率可以改进聚类的精确性，根据研究大概有20%的提高。然而，应该指出是关联这两种信息是有一定的花销的。如果可以预计算相似性矩阵，那么这种混合方法在效率上是相当于传统方法。另一方面，如果联机检索文档，DIG的建立是有一点昂贵的。

4 区分算法

区分算法是基于文档向量两两相似度的一类算法，其中层次聚类算法和划分算法是主要的聚类方法。

层次聚类算法又称为树聚类算法[3,4,19]，它使用数据的联接规则，透过一种层次架构方式，反复将数据进行分裂或聚合，以形成一个层次序列的聚类问题解。层次算法的计算复杂性为 $O(n^2 \log n)" style="font-family:宋体;font-size:12px;text-indent:28px;$ ，适合于小型数据集的分类。层次聚类算法又可以分为凝聚的方法(agglomerative)，也称自底向上（bottom-up）和分裂的方法（divisive），也称自顶向下（top-down）。图2是对层次聚类的表示。

层次方法应用于需要层次结构的应用，能够产生较高质量的聚类。

但是层次算法的时间复杂度 $O(n^2 \log n)$ 和空间复杂度 $O(n^2)$ 很高，严重限制了数据集的大小；缺乏全局目标函数；所有合并都是最终的，无法撤销，对于噪声、高维数据可能造成问题。

图2：层次聚类

划分式聚类算法需要预先指定聚类数目或聚类中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果。如对包含n个文档的文本集合，划分将生成k个分组，k<=n，每一个分组代表一个聚类。划分算法比层次算法要有更好的性能。典型的划分方法包括k-means及其变形等。

图3：k-means聚类过程

K-means中相似度是根据欧氏距离，而对于文档聚类中cosine相似度要好于欧式距离，这种算法称作sphericalkmeans[5]。

k-means实现简单，可用于多种类型，空间需求适度，时间复杂度也适度，复杂度是 $O(nkl)$ ，n是文档的数目，k是聚类数目，l是迭代次数。

kmeans算法有着一些问题：它依赖于随机的初始化；它可能收敛于局域最小值；易受到离群点和噪音的影响；对数据点的分布有一定的假设，不适合用于发现非凸形状（非球形）的聚类，或具有各种不同大小（不同尺寸、不同密度）的聚类。

5 生成算法

生成算法，基于模型方法为每个聚类假设一个模型，然后再去发现符合相应模型的数据对象。一个基于模型的算法可以通过构造一个描述数据点空间分布的密度函数来确定具体聚类。它利用迭代过程在模型估计与文档分配步骤之间交替变换。

每一种模型都提供了文档属于每一个类的概率计算（密度函数）方法。通常使用的模型有高斯模型和冯米塞斯费舍尔模型。

为了最大化总概率我们通常利用em算法[6]。EM算法是一种高效的解决模型中最大似然函数的迭代过程。它包含两个过程：E-step和M-step。E-step利用已知的数据和模型（聚类）的当前评估来计算丢失的数据（计算概率），M-step最大化似然函数，并调整参数。

在生成算法中，E-step只要是利用模型中给出的文档属于每一个类的概率（等式11和等式17）来计算似然概率P，M-step只要是调整参数来得到最大化概率的效果。

基于模型的算法根据标准统计方法并考虑到“噪声”或异常数据，可以自动确定聚类个数；模型多种多样，可供选择性高；可以发现不同大小和椭球形状簇；许多实际的数据是随机的，因此很大程度上满足模型的统计假设。

EM算法可能很慢，对于具有大量分量的模型不适合；当簇只包含少量数据点，或者数据点近似协线性时，也无法很好处理；如何选择正确模型存在问题。