一种基于空间映射及尺度变换的聚类框架

曾依灵，许洪波，吴高巍，程学旗，白 硕,2

(1. 中国科学院 计算技术研究所，北京 100190； 2. 上海证券交易所，上海 200120)

1 引言

随着互联网内容的指数增长，对有效管理大规模文档的需求日益急切。聚类作为一种重要的文本分析方法，已在信息检索领域得到了广泛应用：它被用于加速信息检索过程[1]，提高信息检索系统的准确率和召回率[2]，组织用户的查询结果[3]等。然而，聚类算法的性能常常受到模型不匹配问题的影响：大部分聚类算法都基于一些潜在的模型假设，当语料特性恰好满足聚类算法的模型假设时算法性能良好，反之性能欠佳。

通常，解决模型不匹配问题可以采取两种策略：1)调整算法模型以适应语料分布[5-6]； 2)通过变换特征空间以修正文本表示层的固有问题[1,7]。其中，第一种策略通常需要基于训练错误进行算法修正，因此主要应用于分类算法之中，通常这类策略只能对训练错误发生的区域进行局部修正，容易忽略语料分布的全局特性；第二种策略通过空间变换以解决当前表示空间的固有问题，然而，空间变换往往立足于自身的假设，这些假设与算法模型未必一致，因此空间变换的性能也会有所折扣。在本文中，我们提出的解决框架也可以看作是一种空间变换，但与以前的空间变换不同，该框架根据算法的模型假设进行空间变换，以使变换后的语料分布更适应当前算法。

本文提出的解决框架被称作M-R框架，具体而言，它是一种基于空间映射(Mapping)及尺度变换(Rescaling)的聚类解决框架。该解决框架统计类簇的分布特性并根据算法的模型假设对其进行归一化，以提升聚类性能。具体而言，M-R框架包含如下两步：

Step1.空间映射(Mapping)：由于文本空间具有高维稀疏特性，在原空间进行语料分布特性统计难以操作。我们选择首先将语料映射到一个低维空间，该低维空间由一组具有区分度的方向构成，并且具有适合分布特性统计的良好特性。

Step2.尺度变换(Rescaling)：根据统计而得的语料分布特性，我们构造尺度变换函数，并以尺度变换的方式归一化语料分布，以使语料分布更加契合算法的模型假设，从而在此之上的聚类策略也更加合理。

对于给定的聚类算法，如上两步通过与算法相互迭代的方式以提高聚类性能，直至达到算法的最终收敛。本文将M-R框架应用到了经典的K-means算法及近年的研究热点谱聚类算法上，并最后在国际标准语料集上验证M-R框架的实际性能。

本文后续章节结构如下：在第2节中，我们首先分析不同聚类算法的隐含假定并介绍关于模型不匹配的已有研究，在第3节中，我们详细介绍M-R框架，在第4节中，我们将M-R框架应用到K-means及谱聚类上，在第5节中，我们通过实验验证M-R框架所带来的性能提升，并在第6节中对全文进行总结。

2 相关工作

聚类是一个被广泛研究了40多年的经典问题[4]，并形成了一系列的经典聚类算法。这些算法建立在不同的模型假设之上：层次式聚类的基本假定是，任何的聚类簇都是由更小的、在语义上类似的子簇或者子话题构成。划分式聚类，以K-means为例，则认为各个簇满足方差相同的、各向同性的高斯分布。由此，在空间特性上，不同簇分布在半径相同的球形区域内。基于密度的聚类和基于网格的聚类则关注于语料分布的局部特征(如在某个邻域或空间小单元内的分布特征)，并用这些特征进行聚类判别。

值得单独一提的是近些年研究较热的谱聚类算法[8]。谱聚类的基本思想是将整个语料看作一个加权图，并用图划分的方式最优化给定的划分权重(如Normalized Cut[9]，Ratio Cut[10]，Min-Max Cut[11]等)，以将语料划成一个个聚类。这些最优化划分目标可以通过特征分解的方式获得，并保证全局最优，因此谱聚类的性能往往好过传统聚类算法。从表面上看，谱聚类对语料分布未作任何限定，并有能力区分不同形状的簇，但这必须建立在一个前提之上——图的划分必须较好地吻合簇与簇的边界。然而，如果谱聚类求解出的图划分不能较好地反映簇与簇的边界，同样会导致模型不匹配问题的产生。

事实上，聚类算法的理想假定或多或少与实际语料的真实分布有所偏差(第3节将以实例分析这些偏差产生的原因)。因此。模型不匹配问题成为文本挖掘领域的一个常见问题。为解决这个问题，研究人员在如下两个方面寻求各种解决途径。

一方面的解决途径是通过修正算法模型来适应语料分布。这方面的研究通常需要基于训练错误进行，因此集中在分类领域。典型的研究有：Wu等[5]根据训练错误，用同样的学习方法对每一个类的训练样本重新训练一个子分类器，强迫子分类器根据训练语料学习需要修正的区域，从而使得分类模型更适应当前语料特征。Tan[6]则提出一种简洁有效的“拉推”策略，通过在线修正分类模型的方式以提高分类结果，使被错分的文档也就更容易被重新分到正确的类中。在聚类领域，由于无法通过标签获取信息，关于模型不匹配问题的研究较为罕见。总的而言，这一类的研究通过局部修正来提高性能，但容易忽略语料的全局分布。

另一方面的解决途径是通过空间映射以使原空间的相关问题在新空间能得以恰当的解决。典型的研究有：Dumais[1]认为VSM模型的一大问题是用非独立的词(term)作为独立的空间维度，于是他们提出LSI以解决此问题导致的空间缺陷，通过LSI分解，文档与文档以及词与词的相关性能在k维表示下进行恰当的计算。核方法[7]是另一种通过空间变换来解决问题的重要方法，此类方法通过核函数k(x,y) =φ(x)·φ(y)来寻求一种隐式的空间映射φ，使得在新的空间中问题更易解。大致而言，这一类研究专注于解决当前特征空间的固有问题，其中大部分研究并未考虑算法的固有假定，而空间变换往往意味着较高的时间复杂度和较大的存贮空间。

在下一节中，我们提出自己的解决框架，面向算法模型所期望的语料分布进行空间变换，以提升聚类性能。

3 M-R框架

3.1 聚类中的模型不匹配问题

本节首先以一个语料为例，分析其在不同算法假设下所遭遇的模型不匹配问题。如下图所示，假定给定的语料集中存在两个固有簇，固有簇中的点分别由“+”和“○”标识，并由虚线圈出。标为“+”的点分布在一个狭长的椭球形区域内，而标为“○”的点分布在一个标准的球形区域内。

图1 K-means的模型不匹配问题

图2 谱聚类的模型不匹配问题

如果我们选择K-means算法对语料进行聚类(如图1所示)，显然，语料的分布特征破坏了K-means关于不同簇分布在半径相同的球形区域内的理想假设。K-means将按照自己的假设对语料进行划分，即沿图中实线标识的球形将所有点分成两个簇。于是，部分标记为“+”的点被错误地与标记为“○”的点划分在了一起。该错误划分是如何产生的？根据K-means的决策准则，一个数据点将被放到最近的簇中。以图中的x为例，假定x到cluster1的簇中心的距离为d1，到cluster2的簇中心的距离为d2。尽管x属于标记为“+”的固有簇，由于d2

如果我们选择谱聚类对语料进行聚类(如图2所示)，谱聚类将计算出最优的划分对语料进行分割。为简化分析过程，我们假设谱聚类将语料转化成图表示时进行了邻域限制，同时，图中点与点的权重采用谱聚类中最常使用的高斯相似度，即s(xi,xj)=exp(-‖xi-xj‖2/2σ2)。同样以点x为例，其有效邻域内有4个点，分别标记为a，b，c，d。从图中可以看出，dxa>dxc，dxb>dxd。根据高斯相似度的定义可知s(x,a)

同一个语料，面对不同的聚类算法皆产生了模型不匹配问题。表面上看，这是面对不同模型假设所产生的不同的模型不匹配问题。但从本质上，这其实是同一个问题：语料中各个簇的不同形状和尺度导致距离度量无法较好地反映数据点的类别归属。假定我们已经知道了语料中各个簇的分布特征，并根据这个分布特征进行空间变换，比如，将左边椭球形的簇转化成和右边一样的标准球形区域。那么，距离度量在新的场景下将发生改变：对于图1将使得d1

3.2 基本原理

基于如上对模型不匹配问题的分析，为了使距离度量更为合理，可以将每一个类簇根据分布特性进行空间变换。然而，文本空间的维度灾难问题和数据稀疏特性使得这样的变换不切实际。对此，我们先将语料映射到一组具有区分度的方向构成的一个新坐标系中。

在上述最优化准则中，需要同时对类间离散度和类内离散度进行最优化。而在我们提出的解决框架中，构建新的坐标系之后将进一步根据固有簇的特征执行尺度变换操作，尺度变换以隐式映射的方式对不同簇的分布进行归一化，以使距离度量更为合理。这种隐式的归一化旨在消除不同簇分布上的差异。于是，在归一化的场景下，类内离散度这个反映类内数据点散布程度的指标得以相应的规范，由类内离散度造成的区分度影响也大为降低。因此，在求解具有区分度方向的过程中，我们将优化准则函数简化，忽略类内离散度，仅考虑类间离散度，最优化准则函数变为：

(1)

根据与Fisher判别类似的推导过程，最优矩阵W的列向量可以通过求解SB的最大特征值对应的特征向量，即求解SBwi=λiwi而得到。由SB的定义知，这些特征向量所张成的空间就是向量mi-m(1≤i≤k)张成的空间，因此，我们不妨直接选择mi-m(1≤i≤k)构成一个新的坐标系。

(2)

因此，M-R坐标系的每一个方向对应着一个固有簇，该方向能以最大化类间离散度的方式区分当前簇和其他簇。于是，在进一步的尺度变换操作中，对于每一个方向，可用对应簇的相关特征作为该维度上尺度变换操作的重要参照。

定义2(M-R距离)：假定M-R坐标系下各个坐标轴对应的尺度变换函数分别为R1(·),…,Ri(·),…,Rk(·)，那么，其下的距离函数可写为：

(3)

公式(3)给出了M-R坐标系中距离的一般形式。根据语料中固有簇的分布特征，我们可以采取不同的尺度变换函数，以使公式(3)给出的距离更为合理。尺度变换函数可以取线性函数，也可以取非线性函数。如果尺度变换函数为线性函数，也就是说，Ri(·)的形式为Ri(x)=ξix+i，那么公式(3)可以进一步写为：

(4)

其中，ξi(1≤i≤k)可看作各个坐标轴的尺度变换系数，通过它对各个维度的坐标值进行扩放或者收缩，以使各个维度的标度更具有可比性。

我们期望各个坐标轴有着可比较的标度，也就是说，各个坐标轴上点的分布有着大致相当的尺度。一个较为直观合理的解决方式是，用一个与各个坐标轴数据点分布尺度相关的统计量作为该坐标轴的尺度变换系数。在所有的统计量中，标准差是一个反映一组数据散布尺度的统计量。因此，我们可以计算对应簇在当前坐标轴上投影分布的标准差，并将其倒数作为当前坐标轴的尺度变换系数，即ξi=1/σi，以使各个轴语料的散布尺度趋于一致。于是，公式(4)可以表示如下

(5)

其中

(6)

通过以标准差为倒数的尺度变换函数，各个簇在对应坐标轴上的投影实现了等方差的归一化，各个坐标轴由此而具有更为可比的尺度，基于此尺度的距离计算也更为合理。值得指出的是，本文采用的标准差倒数只是众多尺度变换函数中的一个特例，我们完全可以根据语料的特定分布情况构造各种更精细更合理的尺度变换函数，以使语料能够更好地转化到更为理想的形式。

3.3 基本框架

当前一个未解决的重要问题是：我们如何获取固有簇的信息？由于没有类别标签，我们无法获取固有簇的精确划分。然而，如果能获得一个大致反应固有簇分布的初始划分，我们依旧能够粗略统计出反映各个簇分布特性的尺度变换系数。因此，我们的解决方案是，调用给定的算法获得一个初始划分，将其作为M-R算法的输入。根据该初始划分，可建立M-R坐标系，并计算出各个轴的尺度变换系数，根据M-R距离得到更为合理的划分结果。在新划分结果的基础上，可继续构造出更为合理的M-R坐标系并计算出更为准确的尺度变换系数，并再一次进行更为精细的重划分。为此，我们将迭代策略引入了M-R算法。通过迭代，能够促使聚类结果和M-R坐标系相互修正，并最终获得一个令人满意的聚类结果。

我们可以将M-R框架按如下方式应用到给定聚类算法上：

1) 调用给定聚类算法产生一个初始划分；

2) 根据当前划分构造M-R坐标系，并计算各个坐标轴的尺度变换系数:

3) 在M-R坐标系下用M-R距离调用给定聚类算法生成新的聚类划分:

4) 判断迭代停止条件是否满足，如果否，转2，如果是，输出结果。

4 基于M-R框架的聚类算法

本节我们将M-R框架应用到两个典型的聚类算法上：经典的K-means算法与近年的研究热点谱聚类算法，以证明M-R框架的与不同聚类算法结合的普适性。

4.1 M-R K-means

我们将M-R框架应用到传统的K-means算法上，得到M-R K-means算法。对于一个含有n篇文档的语料M-R K-means算法流程如下：

1) 调用K-means算法进行r次迭代，以生成一个含有k个簇的粗糙划分；

2) 根据当前划分更新M-R坐标系，同时更新各个坐标系的尺度变换系数；

3) Fori=1 tokdo

3.1 计算xi在M-R坐标系中的坐标值；

3.2 根据M-R距离将xi划入最近的簇中；

4) 重复2)-3)直到停止条件达到。

算法中，参数r控制K-means迭代次数，为保证初始划分的迅速产生，r的取值通常很小(r=2或3)。显然，第一步中，通过K-means迭代产生初始划分的时间复杂度为O(krn)，其中k为簇的个数，r为迭代次数，n为数据点的个数。在M-R K-means的每一次迭代中，存在三种主要运算：重新构建M-R坐标系，计算每个点在新M-R坐标系下的坐标，以及根据M-R距离公式计算点到所有簇中心的距离。每次新的迭代都将重新构建M-R坐标系，对于每个坐标轴，都需要计算语料中心到簇中心的归一化向量，所需时间为O(k)；接着，需要计算所有点在新M-R坐标系下的坐标，对于每个点，将根据公式(2)计算k个点乘，因此，计算所有点的M-R坐标的时间复杂度为O(kn)。接着将在M-R坐标系下根据公式(5)计算所有点到簇中心的M-R距离，由于每个距离计算只涉及k维，相比于原始空间，维度大为降低，因此，相比于前面的高维计算，这部分的计算量可以省略。将三部分运算汇总，一次迭代的总运算量为：O(k)+O(kn)=O(kn)。假定M-R K-means总的迭代次数为T(包括用K-means产生初始划分的r次迭代)，M-R K-means聚类算法的时间复杂度为O(knT)。可见，M-R K-means聚类算法的时间复杂度保持在与K-means算法同一量级。

4.2 M-R Ncut

谱聚类系列算法中，我们选择具有代表性的Normalized Cut(即 Ncut)算法[9]，并将M-R框架应用到其上。然而，在Ncut算法中，构造邻接矩阵用的是高斯相似度，我们所要解决的问题是，如何将M-R坐标系及定义在其上的M-R距离与高斯相似度统一起来。不难发现，高斯相似度其实是基于高斯核的窗函数应用到欧式距离上的结果：s(xi,xj)=exp (-‖xi-xj‖2/2σ2)=exp (-d(xi,xj)2/2σ2)。因此，在M-R坐标系下，我们只需要将高斯相似度中的欧氏距替换成M-R距离即可。也就是说，M-R坐标系下的高斯相似度可类似地定义为：sM-R(xi,xj)=exp(-dM-R(xi,xj)2/2σ2)。M-R Ncut算法流程如下：

1) 调用Ncut算法一次以获得一个初始划分；

2) 根据当前划分更新M-R坐标系，同时更新各个坐标系的尺度变换系数；

3) 根据M-R坐标系下的高斯相似度计算谱聚类中的邻接矩阵；

4) 根据该邻接矩阵再次调度Ncut算法生成新的聚类结果；

5) 重复2)-4)直到停止条件达到。

无论是一开始调用Ncut算法获取初始划分还是在M-R坐标系下迭代执行Ncut算法，都需要对一个n×n的矩阵进行特征分解，相对于特征分解的时间复杂度，计算邻接矩阵，以及在特征向量张成空间中进行K-means聚类的时间复杂度皆可忽略。因此，如果M-R Ncut算法共调用Ncut进行了T次迭代，M-R Ncut的时间复杂度则是Ncut的T倍。

5 实验结果

5.1 语料集

在本节的实验中，我们将用到两个国际标准文本语料库：RCV1-v2[14]及20Newsgroup*http://www.ai.mit.edu/people/jrennie/20Newsgroups/。

RCV1-v2该语料集包含人工采集的来自路透社的800 000余篇新闻专线语料，存贮在103个类别中。我们从RCV1-v2中随机地挑选类别及文档，构造出了一系列的测试语料集：R1、R2、R3、R4和R5，它们的类别数从7类到15类不等，文档数从1 932到3 330不等。

20Newsgroup该语料集包含了来自20个Usenet新闻组中的20 000篇文章，每个类别1 000篇。我们随机挑选20Newsgroup中的类别及文档，构造出了一系列测试语料集N1、N2、N3、N4和N5，它们的类别数从6类到15类不等，文档数从2 112到3 406不等。

我们所构造的两个系列的测试语料集的概况如表1所示。在这两个系列的语料上，我们都保持了类别数和文档数的跨度，其原因是我们想观察M-R框架在不同尺度的语料集上的性能。我们将这10个测试语料集转换成归一化的VSM向量矩阵，以供进一步的实验之用。

表1 实验语料概况

5.2 评价指标

聚类算法的评价指标多种多样，包括准确率、召回率、F-Measure，熵等。其中最为常用的是F-Measure和熵[15]。

F-Measure将准确率和召回率结合在一起。对于语料集中的任何一个类，F-Measure寻找聚类结果中与其最相似的簇，根据该簇计算该类的准确率、召回率及F-Measure。而整个语料集的F-Measure由所有类的F-Measure加权而得，其中，权值是该类在语料集中的比重。

熵是一种衡量聚类簇纯度的指标，值越小表明聚类结果纯度越大。当所有簇的纯度都最高时，熵值最佳。需要注意的是，当所有簇都仅包含一个文档时熵值亦达到最佳值。整个语料的熵值由聚类结果中所有簇的熵值加权累加产生，权值是该簇在聚类结果中的比重。

5.3 M-R框架性能

为了验证M-R框架的真实性能，我们在前文所构建的10个语料集上运行K-means，M-R K-means，Ncut及M-R Ncut算法并比较它们的实验结果。实验中的K-means和M-R K-means用C++实现，而Ncut算法源码则来自华盛顿大学的谱聚类工具箱*http://www.cs.washington.edu/homes/sagarwal/code.html.，M-R Ncut则在Ncut源码基础上修改而成。实验中所用到的所有算法，都涉及到初始点的选择。为避免初始点选择对算法性能的影响，对于同一个语料集，我们每个算法运行10次，并且，对其中的每一次运行，所有算法都采用同样一组随机生成的初始点。最终，对于每一个算法，我们将10次实验的F-measure和熵值进行平均，以供性能比较。对于所有算法，也同样涉及到聚类结果中簇数的设定，在实验中，我们统一将聚类结果的簇数设定为语料集中的类别数。在K-means算法中，我们采用欧氏距离，以同M-R K-means中的M-R距离进行比较。在我们的实验中，K-means的收敛条件是，平方和准则函数(所有点到最近簇中心距离的平方和)在两次迭代中的差值不超过0.001；M-R K-means的收敛条件是，簇与簇之间不存在文档的迁移，或者达到了最大迭代次数(实验中设为20)；Ncut的收敛条件与K-means一致；而对于M-R Ncut，由于算法时间复杂度较大，为了方便实验进行，我们将最大迭代次数设置为5。

对于Ncut和M-R Ncut，还需要确定高斯相似度中的参数σ，Ng[8]和Zelnik-Manor[12]提出了不同的确定参数σ的方法，Ng建议采用使得在谱空间中类簇分布尽量紧凑的σ值，Zelnik-Manor则建议用第k近邻与当前点的距离来估算σ。我们尝试了这两种确定σ参数的方法，Ng的方法尽管需要遍历σ，但能够使Ncut算法发挥更好的性能。Zelnik-Manor的方法易于实现但效果略差。尽管M-R框架在两种σ选择策略下都能取得性能的提升，为了使得Ncut系列和K-means系列也能有个性能比较的参照，我们仅列举出Ng方法的实验结果。

实验结果的F-measure和熵值分别如表2和表3所示。

表2 所有语料集上的聚类结果F值比较

表3 所有语料集上的聚类结果熵值比较

从如上实验结果我们可以得到这样一些结论：

(1) M-R框架在K-means和Ncut上皆取得了性能提升，性能提升全面而稳定，语料集的大小及类簇的个数对性能的提升没有明显影响。我们对两类算法应用M-R框架前后的对比实验结果进行t检验，p-value皆小于0.01，这证实了M-R框架的有效性。

(2) 最好的聚类性能几乎皆由M-R Ncut取得，这是因为一方面Ncut的性能高于K-means，另一方面M-R Ncut基于Ncut取得了较为稳定的性能提升。

(3) M-R框架在K-means上取得的性能提升较Ncut上略高。以F-measure为例，在RCV1系列上，M-R K-means取得的平均性能提升为0.050，M-R Ncut取得的平均性能提升为0.027；在Newsgroup系列上，M-R K-means取得的平均性能提升为0.071，M-R Ncut取得的平均性能提升为0.050。进一步比较可以看出，在语料类簇数较多时，M-R K-means甚至取得了与Ncut可比的性能。M-R框架在K-means上取得的性能更为显著，其原因分析如下：K-means采用点到中心的距离进行聚类判别，而Ncut采用点与点的距离构建邻接矩阵。尽管M-R框架对二者的修正都取得了较为显著的效果，但K-means中点到中心的距离关系到点与簇的全局关系，因此用簇的全局信息(标准差)进行修正更为有效。

5 结论及下一步研究

面向模型不匹配问题，本文提出了一种基于空间映射及尺度变换的聚类框架，简称M-R框架。该框架选择一组具有区分度的方向构造M-R坐标系，并在该坐标系下分析待聚类语料的分布特征，利用这些分布特征构造尺度变换函数，以尺度变换的方式归一化语料的分布，以使距离度量更好地反映文档的类别归属。M-R框架伴随聚类算法迭代执行，以不断提升聚类的性能。本文将M-R框架应用到了K-means和Ncut上，在RCV1语料集及20Newsgroup语料集上的实验表明，M-R框架取得了聚类结果质量的全面提升。

M-R框架最重要贡献是提出了一种基于语料特征并面向算法假设的空间映射，该映射能够将语料归一化到更为接近算法假设的分布形态。显然，M-R框架可以应用到更多的聚类算法上，也适用于分类领域。下一步，我们将对M-R框架的理论进行更为深入的研究，并同时对M-R框架的应用进行更为广泛的探索。

[1] Dumais S. T. LSI Meets TREC: A Status Report[C]// D. Harman (Ed.) Prof. of The First Text REtrieval Conference (TREC1), National Institute of Standards and Technology Special Publication 500-207, 1993: 137-152.

[2] Liu X., Croft W.B. Cluster-Based Retrieval Using Language Models[C]// Proc. of SIGIR, 2004: 186-193.

[3] Zamir O., Etzioni O., Madani O., et al. Fast and Intuitive Clustering of Web Documents[C]// Proc. of KDD, 1997: 287-290.

[4] Han J. and Kamber M. Data Mining: Concepts and Techniques, Second Edition[M]. Morgan Kaufmann Publishes, 2006.

[5] Wu H., Phang T. H., Liu B., et al. A Refinement Approach to Handling Model Misfit in Text Categorization[C]// SIGKDD, 2002: 207-216.

[6] Tan S., Cheng X., Ghanem MM, et al. A Novel Refinement Approach for Text Categorization[C]// Proc. of the 14th ACM CIKM, 2005: 469-476.

[7] Shawe-Taylor J., Cristianini N. Kernel Methods for Pattern Analysis[M]. Cambridge University Press, 2004.

[8] Ng A., Jordan M., Weiss Y. On Spectral Clustering: Analysis and an Algorithm[J]. T. Dietterich, S. Becker, and Ghahramani Z. (Eds.), Advances in Neural Information Processing Systems 14, MIT Press, 2002.

[9] Shi, J. and Malik, J. Normalized Cuts and Image Segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.

[10] Chan P. K., Schlag D. F., Zien J. Y. Spectral K-way Ratio-Cut Partitioning and Clustering[J]. IEEE Trans. Computer-Aided Design, 1994, 13:1088-1096.

[11] Ding C., He X., Zha H., et al. A Min-Max Cut Algorithm for Graph Partitioning and Data Clustering[C]// Proc. of ICDM, 2001: 107-114.

[12] Zelnik-Manor L., Perona P. Self-Tuning Spectral Clustering[C]// NIPS 17. 2005.

[13] Duda R. O., Hart P. E., Stork D. G. Pattern Classification, Second Edition[M].Wiley-Interscience Publishes, 2000.

[14] Lewis D. D., Yang Y., Rose T., et al. RCV1: A New Benchmark Collection for Text Categorization Research[J].Journal of Machine Learning Research, 2004.

[15] 周昭涛. 文本聚类分析效果评价及文本表示研究[D]. 北京: 中国科学院计算技术研究所, 2005.