文本聚类分析效果评价笔记

（1）可增长性，新文档的加入不会导致聚类结果剧烈变化

（2）稳定性，对于文档描述的错误只会带来很小的变化

（3）方法应该和文本对象的输入顺序无关。

目前文本聚类分析研究中存在的挑战有：

（1）一个文档可能包含多个主题，文本聚类算法如何体现这种特征，允许包含多个主题的一个文档分入不同主题的簇，在这种情况下如何形成高质量的簇。

（2）高维诅咒问题，过高的维度会使聚类分析的质量和稳定性下降。

（3）大规模文档的处理效率问题，针对大规模的文档数据，尤其是源源不断到来的新闻报道文本，如何从中快速发现有用的话题

（4）如何评价聚类效果以便进行算法选择与参数选择，比如层次聚类中达到第几个层次结束，K-MEANS中该选择什么样的K值和迭代目标。

影响文本聚类分析效果的因素是多方面的，文本聚类分析全过程的每个步骤都有可能对聚类结果造成影响。

原始样本-》特征抽取（领域知识）-》样本矩阵-》聚类算法（无领域知识参与）-》聚类谱系图-选取阈值（领域知识）-》聚类方案

聚类流程三个步骤的实际处理内容为：

（1）文本聚类分析首先将文本标识成机器可计算的形式。不论是抽取文本特征形成一个向量还是抽取文本特征形成一个特殊的结构，对文本的这种机器表示过程简称为文本标识。文本标识过程显然需要领域知识参与，文本中哪些因素可以构成特征，特征中哪些在聚类中可用以及如何使用时文本聚类第一步骤文本表示考察的内容。

（2）文本聚类分析的第二步骤是算法。不同的算法有不同的特征，对相同的数据输入，不同的算法会产生出不同的聚类结果。聚类分析算法可以从不同的角度进行比较，比如是否产生层次聚类结构、是否需要参数、是否能够产生模糊聚类、能够识别出不规则形状的簇等等。目前在文献中出现的聚类分析算法数目众多，但在文本数据上效果孰优孰劣仍然没有得到有效的研究。这个步骤中算法的时空效率、聚类结果质量是研发中选择算法的主要标准。该步骤还有一个关键因素就是对象距离（或者相似度）如何定义。

（3）第三个步骤是算法中参数的选择。不同的算法对参数的敏感性不同，但是基本上参数的好坏对结果的影响都比较显著。

从这三个步骤可以看出影响文本聚类分析效果的因素主要是4个：文本标识模型、距离度量方法、算法模型、参数优化。参数的设定主观性比较强，如何设定才是一个好的参数缺乏有效的方法，可以通过指标的变化曲线图寻找算法的最佳参数。

1、文本表示模型

在实际的文本聚类分析研究，将实际文本内容变换成机器内部表示结构的方法多种多样，可以用词、字、短语、n-gram、显著性短语等形成向量、树结构。在经典的研究中通常利用特征（term，包括字、词、词组等）的词频信息建立文本向量，通过文本向量与文本向量之间的相似度来进行聚类分析。

文本标识包括两个问题：表示与计算。表示特指特征的提取（特征提取包括特征的定义和筛选，可以利用N-GRAM、PAT树提取特征，可利用LSI降维转化特征、利用语义词典wordNet或者HOwNet定义更复杂的特征结构），计算指权重的定义和语义相似度的定义（可以选取不同的模型，如向量空间模型、概率模型、语言模型等）。

接下来主要介绍信息检索和文本分析处理中经常用到的几个检索模型，它们根据不同的理论假设推到，定义了不同的特征权重计算方法与语义相似度计算方法，是文本表示模型的重要组成部分。

1.1布尔模型

主要用于信息检索，是二值的，向量中每个分量权重为0或者1。它只能用于信息检索中计算用户查询与文档的相关性，而无法利用该模型计算两个文档更深层面的相似度。于是在此基础上提出了扩展布尔类型，比图fuzzy set，waller-kraft，p-norm与infinite-one。

1.2向量空间模型-VSM模型（vector space model）

A)它将文档表示成一个向量，向量的每一维表示一个特征，这个特征可以是一个字、一个词、一个n-gram或者某个复杂的结构。表示时，需要对文档进行切分（中文分词、英文通过词的分界符识别单词）、停用词处理、英文词的词形还原或者提取次干。每个文档可以用文档中的词来表示，这些词及其对应的权重构成一个向量。

B)权重的经典定义是TF-IDF公式。

C)相似度度量

通常用夹角余弦值。

D)变种

随着研究的发展以及TREC评测的推动，实际上向量空间模型还存在多个变种，应用中需要针对不同变种的运行结果进行评测，选择最合适的表示方法。著名的信息检索系统smart中提出过一套针对VSM模型中特征权重计算变种的命名体系，该命名体系中综合了TF-IDF中的多种变化，将文档某个特征的权重计算归结为三个组成部分：TF正则化因子，IDF正则化因子和基于文档长度的正则化因子。因此，将文档的特征权重定义为：

特征权重W=TF正则化因子*IDF正则化因子*长度正则化因子（详情可百度）

1.3概率检索模型

概率模型是一系列模型的简称，这类模型有自己的假设天气，有比较完整的推理过程，将相似度看成一个概率。在信息检索中，主要计算P(Revelent|Document，query)并利用概率排序规则PRP（Probabilistic Ranking principle）来判断不同文档与同一个查询相关的成都。

P(Revelent|Document，query)表示给出一个查询Query，文档Document与该查询相关的概率。根据不同的假设进行推理求P的计算公式，可以衍生出不同的概率检索模型，包括BIR、BII、INQUERY等。实际上最广泛的是OKAPI模型，它的权重定义公式成为BM25公式（详情可百度）

向量空间模型和概率模型都是对原始文本的表示模型，在实践中这两者的应用最为广泛。其主要的不同点在于对语义相似度度量的定义上，向量空间模型在欧拉几何空间通过向量的夹角余弦来定义的，概率模型在概率测度空间上通过概率来衡量两个文本的语义相似度，概率模型基于概率值而不是几何测量值来衡量语义相似度。这两个模型存在许多相同点，两者的特征权重都基于词频并且都假设了特征间的相互独立性。

1.4语言模型

语言模型，本质上也是一种基于概率和统计的模型。它认为每个文档都是一个语言模型，整个语料集也是一个语言模型，查询也看成一个语言模型。通过计算语言模型与语言模型之间的距离计算查询与文档的相关性、计算文档与文档之间的相关性。

统计语言模型认为语言就是字母表上的一种概率分布，通过概率分布计算任何一个字母序列成为该语言一个句子或者其他语言单元（文章、段落等）的可能性。关键问题是语言模型的估计与平滑。

1.5其他

文档聚类分析中的文档标识是一个关键的研究点，在以往的研究中，有学者尝试过不同的做法来完成，比如考虑用概念作为特征来聚类而不是用简单的词作为特征来聚类，或者利用文档中每个次的互信息向量来聚类而不是利用权重向量等等，也有从效率考虑用两次聚类，先用一字词聚类，再用二字词进一步聚类来提高聚类精度，这些都是可研究的方面，需要在具体的应用中去考虑不同做法及其效果。

2、距离的定义

文本聚类中，除对文本进行表示外，还必须对文本进行相似度度量。不同的相似度度量方法出现不同的聚类结果。聚类分析中，要区分三个相似度度量（或者距离度量）：

（1）文本与文本之间的相似度度量

（2）文本与文本簇之间的相似度度量

（3）文本簇与文本簇之间的相似度度量

不同的聚类算法应用了这三种类型的度量方法中的某种或者某几种。比如凝聚是层次聚类算法使用了三种，K-Means算法中就用到1、3.

这三种距离中不同的定义方式会对结果产生不同的影响，衍生出算法的不同变种。

2.1、文本与文本相似度的度量。

向量形式表示的文档，除了可以用cos相似度度量之外，还可以用传统的聚类分析中存在的其他距离度量方法，如明氏距离、马氏距离与兰氏距离。语言模型中，可以用KL距离来计算。

2.2、文本簇与文本醋之间的相似度度量

聚类分析中，衡量簇与簇之间的相似度，实现簇的合并与拆分。常见的有最小距离、最大距离、类平均、质心法、离差平方和、代表点。

2.3、文本与文本簇相似度的度量

文本与文本簇相似度的度量仿效前面的度量公式计算。把要计算距离的文本看成一个只包含一个文本的文本簇，那么可以采用2中的度量公式度量。如果把簇用其中心向量表示，又可以用1中的公式度量。

3、聚类分析方法

可以划分为层次聚类和划分聚类两大类，在文本分析中也最广泛。

3.1簇的充要条件

从一般意义上而言，簇往往要求簇内部足够的凝聚、熵值足够小，可区分于其他簇。传统研究中也有定义（详情可百度）

必要条件定义：C表示所有样本的集合。任意si、sj属于C并且定义两者距离为D（SI,SJ）。如果G属于C成为一个粗，其必要条件是对于G的任何一个非空的划分G=G1uG2，C-G1中与G1最相近的点必然在G2中。

3.2 Q聚类和R聚类

对象本身的聚类，结果中各个簇是某些对象的集合，成为Q型聚类；对象特征的聚类，结果簇是一些特征的集合，成为R型聚类。在文档聚类分析中，这两种类型的聚类分析都有相关的研究，也可以在一个算法中同时采用者两种聚类，R型聚类用于降维，Q型聚类用于产生文档簇。

3.3基本算法思想与算法

层次聚类：凝聚式层次聚类（算法复杂度高，往往用于小规模的聚类分析，或者用于复合聚类分析算法的组成部分）、分裂式层次聚类、其他层次聚类

划分聚类：K-Means聚类（缺点是必须给出K、对于顺序敏感、不适于发现大小很大的簇、对噪声和孤立点敏感）、K-Medoids聚类、最近邻聚类（对参数敏感、容易产生大量的小簇）、基于样本最大距离聚类（简洁、高效、但是改进变化余地小，受样本影响比较大）、基于密度的聚类（速度快，能处理噪声和发现任意形状的簇，对顺序不敏感）、基于网格或者子空间的聚类。

文本聚类是高维空间上的聚类分析，数据经常呈现奇怪的特征，例如噪声比例的增加、网格单元个数的指数增加、数据空间的稀疏性、聚类的密度降低等，在数据挖掘中成为维度祸根。有许多聚类分析算法，如DBSCAN\STING\WAVECLUSETER随着维数增加算法空间和时间复杂性增加，很难实用化。传统的聚类算法应用于文本聚类中除了要调整好参数使聚类效果有意义意外，还要尽量避免高维度特征所带来的影响。

对于大规模文档聚类分析问题，往往根据上面提到的若干基本聚类分析思想进行组合，充分利用分而治之的分批处理策略，采样聚类，分阶段多层次处理策略来降低规模与处理的复杂度。

4、文本聚类效果评价指标体系与应用特性

在聚类有效性分析研究中，评价聚类算法得到的聚类结果C的方法主要有三类：第一类称外部标准，用实现判定的聚类结构来评价C；第二类是内部标准，用参与聚类的样本来评价C，如误差平方和；第三类是相对标准，用同一算法的不同结果（不同参数得到）来评价C，通过与其他结果的比较来判断C的优劣。4.1节中借鉴传统有效性分析三类方法中的思想，参考现有文献中对文本聚类结果评价提出的一些指标，分析了如何针对文本聚类分析效果进行评价。

4.1文本聚类效果评价概述

在文本聚类分析中，存在两种相互联系的评价标准：（1）聚类结果中，团内越紧密、团间越分离越好（衍生出类内凝聚度和类间分离度的指标）；（2）聚类结果与人工判断结果越吻合越好（衍生出基于人工判定的指标）。

基于人工判定的指标，更适合于对文本聚类结果的效果进行评价，评判聚类算法及中间的各种处理过程是否能满足应用的需求。该系列指标可用于对不同算法横向比较、对算法的性能进行分析以及研究参数的优化，让聚类结果更符合人的主观判定。

基于函数的指标适用于聚类算法计算目标的选择，成为算法爱本身的一部分而不是作为评价算法的标准。

4.2基于人工判定的指标

基于人工判定的指标要求进行聚类的语料存在一个人工判定的类结构P，依靠类结构P来评价该语料上的某个聚类结果。比如对于语料集合X={x1,x2,x3,x4,x5}，存在人工判定的类结构{{x1,x3}，{x2,x4,x5}}，那么久可以针对某个聚类结果C定义评价指标。

4.2.1平均准确率及相关指标

构造矩阵

   聚类结果C

   同类 不同类

人工判定同类 a       c

 不同类 b       d

根据a\b\c\d可以定义出不同的评价指标，其中a+b+c+d=M,M=N*(N-1)/2,N表示X中所有样本的总数，常见的指标有：

Rand statistic                     R=（a+d）/M

jaccad coefficient               J=a/(a+b+c)

Fowlkes and mallows index FM=开根号（a/(a+b)*a/(a+c)）

上面3个指标，只在传统聚类有效性分析的文献中出现，而不曾鉴于文本聚类分析的实际研究中，R.J.FM三个统计量越大表名C和P的吻合成都越高，C的聚类效果越好。

积极准确率PA                       a/(a+c)

消极准确率NA                     d/(b+d)

平均准确率AA                       (PA+NA)/2

使用平均准确率作为评价指标的文本聚类研究并不多，该指标强调准确率，尤其考虑了消极准确率，该指标在实际实验分钟可以起到一定的作用，指标值相对较大。

4.2.2基于人工标注类的准确率、召回率与F-measure值

对数据C中每个人工标注的主题Pi，假设在聚类算法形成的类层次结构中存在一个与之对应的团Ci。为了发现C，遍历聚类结果C={C1,C2..Cm}中m各簇，计算准确率、召回率和F值，从中挑选最优指标值及其对应的簇，以该最有的指标值来判定Pi的质量。

Class_F指标强调以人工标注的类为基准，聚类的结果尽量地逼近事先确定的人工标注结构，该指标是一个非常有用的指标，并且使用的也比较频繁。对聚类结果优劣的整体区分能力比较强，是一个推荐使用的指标。

4.2.3基于簇的准确率、召回率与F-Measure值

上面是针对每个人工标注类进行评价，是一个整体的效果评价。实际应用中，更多的时候我们只需要得到可以理解的簇就可以，并不一定要求该簇一定要和人工标注好的类别一样，模仿Class_F值指标，本节定义了一个基于簇的F值评价指标，对簇进行独立评价而不是对原来的类的整体进行评价。

但是该指标对于大类现象并不敏感，对聚类结果质量变化的反应不如其他指标明显。

4.2.4基于文档的准确率、召回率与F-Measure值

4.2.5熵

熵不仅仅可以单独评价一个簇，也可以利用簇大小进行加权平均对整个聚类结果进行评价。特点是偏好小类，如果每个文档独立成为一类，那么该结果从熵的意义上来讲是一个最好的结果，因此实际评测中使用熵的同时必须结合基于类的F值这种整体评价指标，从评价的实际需要对结果进行分析。

它是一个非常优秀的指标，也是我们推荐使用的指标，原因有3点：首先该指标评价簇中文档来源分布的均衡程度，来源越均衡混乱度越高质量越差，其二该指标可以突破上面几个指标无法应用于模糊聚类结果评价的限制，用于评价一个文档属于多个簇的聚类结果；第三该指标有很好的横向可比性。

4.2.6检测代价

在话题检测与跟踪（TDT）研究和评测之中，检测代价是评测一个系统检测到一个话题（簇）的能力的指标，代价越大，性能越差。话题检测在大量文档中自动的找出能够组成一个新话题的一系列文档，本质上是一种文档聚类，它与普通文档聚类的区别在于TDT中的每个文档带有时间标签。因此检测代价是一个可以借鉴用于评价文本聚类效果的指标。

4.2.7小结

平均准确率、RS、Jasccard、FM指标强调聚类整体结果的准确性，如果应用需要考察整体上的准确程度，那么我们可以考虑采用这些指标，尤其是平均准确率或者FM指标进行评价。

基于类、基于簇、基于文档的F值与文本信息处理中的传统评价指标相衔接与吻合，同时考虑了准确率和召回率；检测代价指标强调了召回率。这些指标在文本聚类效果的评价中都比较合适。

在所有这些基于人工判定的指标中，我们推荐使用基于类的F值和熵作为文本聚类结果效果评价的指标。

4.3基于目标函数的指标

聚类的另一种评价指标是类内越凝聚且类间越分离越好，由此衍生的指标成为基于目标函数的指标。基于目标函数的指标可以作为算法的一部分应用于算法中，不断地评价当前的聚类结果，通过该指标值来衡量当前的中间结果是否可以成为最终结果，或者通过该指标来选择聚类算法的下一步寻优迭代方向。基于目标函数的指标有很多，这里只简单地列出2个。

4.3.1误差平方和

K-Means算法自身的迭代过程就是寻找一个满足误差平方和越来越小的聚类效果的过程，通过这个标准我们可以通过多次尝试，选择K-Means中合适的K。

4.3.2紧致性与分离性效果函数

4.4应用文本聚类评价指标

从前面讨论可以看出，文本聚类两个系列的评价指标都可以在研发过程中发挥作用：

（1）在工程应用中事先制作人工判断测试语料，利用基于人工判定的指标进行评价，进行算法选择和参数调优。

（2）在科研中针对不同的算法进行有效的横向比较，尤其对影响文本聚类分析的四个因素进行深入的分析探讨

（3）如果算法中存在难以确定的参数，可以不断改变该参数的值得到不同的评价值，画出曲线，从曲线中发分析算法的性能以及算法的特征。从指标值的极值点、乖点得到参数的有花枝。比如K的选取等。

（4）基于目标函数的指标可以作为算法的一部分，充当算法寻优的方向来改进算法，也可以利用这些指标对临时的簇进行Rank，进行有效的合并、拆分、效果呈现。