下载掌阅APP，畅读海量书库
立即打开
聚类方法可以分为判别式与生成式两类。
判别式方法基于数据的相似性（或距离）进行聚类，例如K均值聚类算法以及层次聚类算法；生成式方法通过特定的模型表征簇，使得数据与模型的拟合最优，例如自组织地图（SOM）与混合模型（Mixture Models）聚类。其中混合模型聚类的基本思想是将聚类问题转化为数学建模问题，即利用简单概率分布的组合模拟复杂概率分布的统计建模方法，一个概率分布代表一个簇的特征分布，概率分布的组合即代表整个数据集的特征分布，核心环节是数据建模与模型推理。
基于混合模型的文本聚类研究，其流程见图5-10。混合模型文本聚类的主要模块有：（1）文本建模，即假定文本集符合某种统计模型，如多元伯努利混合模型（Bernoulli Mixture，BM）、多项式混合模型（Multinomial Mixture，MM）和vMF混合模型（von Mises Fisher Mixture）等；（2）模型推理，即将基于BM等模型的数据似然（或后验概率）作为优化准则，通过EM算法、变分推理以及马尔科夫链-蒙特卡洛（Markov chain Monte Carlo，MCMC）方法等推理算法得到模型参数的估计值以完成聚类；（3）聚类评估，常用指标有准确率、召回率以及F值等。除了这些主要模块之外，部分研究中还涉及参数建模（由于仅在部分研究中出现，图5-10中呈现为虚线），即对混合模型的参数进行建模，旨在实现模型优化，常用方法有狄利克雷分布以及狄利克雷过程等。
图5-10 混合模型文本聚类流程图
（一）混合模型
混合模型是利用简单的概率分布的组合模拟复杂概率分布的统计建模方法。由于混合模型参数估计的复杂性，混合模型的研究发展一直十分缓慢。直到Dempster等人
（1977）提出EM算法，很大程度上简化了极大似然估计方法的模型推理过程，这才极大地刺激了混合模型的应用研究。在混合模型的具体应用中，需要根据数据集的类型选择特定的概率分布函数p（·），例如一般情况下使用最为广泛的高斯混合模型，在混合模型文本聚类中常用的模型有以下几种。
（1）多元伯努利混合模型
BM只考虑词项在文本中是否出现，因此文本每个特征维度的取值d
nw
∈{0，1}，取1表示词项w在文本n中出现，否则反之。根据文本集的特征维度W，对应的即为W元伯努利混合模型，第k个多元伯努利分布的参数为θ
k
={θ
k1
，θ
k 2
，…，θ
kw
}，θ
kw
代表类k中词项w出现的概率，文本及整个文本集的生成概率可表示为
：
（2）多项式混合模型
MM与BM不同的是，考虑了文本中词项w出现的频次，d
nw
表示文本n中词项w出现的频次。令第k个多项式分布的参数为θ
k
={θ
k
1
，θ
k
2
，…，θ
kw
}，θ
kw
代表类k中词项w出现的概率且∑
w∈W
θ
kw
=1，文本及整个文本集的生成概率为
：
伯努利分布与多项式分布都是离散型分布多项式模型偏好高频词，因而频次较高的一般词项会造成影响，而多元伯努利模型只考虑词项是否出现，在这种情况下更为稳健。但总体而言，两种模型结构较为简单，计算效率较高，能够得到较好的结果。
（3）vMF混合模型
Salton等实证
表明，归一化处理能够解决文本长度造成的偏差问题，提供更好的聚类结果；Dhillon等人
的研究证明，基于余弦相似性相比基于欧氏距离的k均值算法（spkmeans）更加适用于文本聚类。据此，Banerjee
认为文本特征向量具有方向性数据（directional data，即‖d
n
‖=1）的特性，把它作为方向性数据进行建模会有较好效果，率先使用了vMF分布对文本建模：
参数θ k =（μk，κk），其中μk为均值向量，κ为聚集参数（concentration parameter），表示单位向量d在均值向量周围的集中程度，κ值越大则说明d在均值向量方向上的集中程度越高，当κ=0，密度函数降为一个均匀分布，κ → ∞，密度函数趋向于一个点密度。
除了上述三种模型之外，早期对于混合模型的研究都是以高斯混合模型（Gaussian Mixture Model，GMM）进行建模，目前仍然应用广泛。
不过，因为文本的高维与稀疏特征不符合高斯分布，除了Liu等
利用GMM进行的探索性工作，在文本聚类中鲜见该模型。此外，用到的还有泊松分布
、朗之万分布
等。
（二）文本建模
文本表示，指文本中抽取出用于表征文本主题的特征并赋予权值，将自然文本转化为结构化形式；考虑到文本数据高维稀疏的特性，需要使用特征降维方法对特征空间进行浓缩。
（1）文本表示
在混合模型文本聚类中，文本一般表示为向量空间模型，以词项为特征维度，词项频次（或者其变体，如TF-IDF）为特征值表示文本，该模型在文本表示中采用独立性假设，即认为特征项与特征项之间相互独立。但是，一元词项对于主题的表征能力有限，学者对此进行了一定的探索。
从语义层面构建新的特征，通过词项组合、主题等从语义层面表征文本，从而达到改善聚类效果的作用，例如Liu等
同时使用了词项、命名实体以及词组三项构建文本特征的向量。Zhang等
为基于模型的文本聚类提出了一种语义平滑，用于削弱一般词项，起到增强核心词项的作用。多词短语的语义较为明确，不像独立词项的分布，大部分多词短语的分布取决于主题，因此更有助于文本聚类。与简单背景平滑、拉普拉斯平滑的实验比较也证明了这一点。
总体而言，混合模型文本聚类中的文本表示仍是基于词袋模型的思想，研究者已经发现一元项对主题的表征能力有限，吴夙慧等对此进行了系统的梳理
。在混合模型文本聚类中，多数研究者仍主要采取一元模型，文本表示的相关探索甚少，但是已有的研究表明，在混合模型文本聚类中可以借鉴传统聚类通过短语、词项共现、主题等从语义层面揭示文本内容、提高文本表征准度的做法。
（2）特征降维
文档集往往都是高维度数据，聚类算法不得不处理维数诅咒（curse of dimen-sionality）的问题，因而在实际中需要借助降维技术减少特征维度，改善聚类效果，提高运算效率，得到更加简单、更加易于理解的模型。降维技术一般可分为特征抽取与特征选择。
特征抽取是指通过某种映射把原始的特征空间转换为完全不同的子空间，通常称为隐性子空间，这种方法能够更低维度、更加本质地表征文档，其根本在于利用特征维度之间的共现关系，挖掘特征维度之间的关联；特征选择的思想认为簇之间的差异仅仅是针对一些本质特征，基于特定的准则为每个词项计算一个分值，这个分值代表该词项在特征集中的质量，或者说重要性。根据分值对词项排序，筛选出排名最高的一定数量的词项，在实际操作中，使用哪种评估分数以及最终选择特征的数量规模，都需要根据具体的问题通过实验来调整。
（三）参数建模
从建模对象来看，上述模型都是对文档特征进行建模，用概率分布表示文档的特征分布。在此基础上，可以引入参数的先验分布，进一步对上述模型的参数进行建模。
狄利克雷分布是多项式分布的共轭分布，通常作为多项式分布参数的先验分布应用在贝叶斯估计中，在文档建模中已有较多应用。
Madsen等
利用DCM（Dirichlet Compound Multinomial）复合概率分布对文档建模，首先基于狄利克雷分布抽取多项式分布，如公式（5-34），然后基于该多项式分布反复抽取词项从而生成文档，如公式（5-35），这一处理将参数θ
k
的估计转换为对超参数α的估计。
其中
是狄利克雷分布的参数，他提出这一模型的目的是弥补多项式模型本身无法识别词项爆发（burstiness）的缺陷，即一个文档在词项中出现一次后趋向于再次出现，参数α
w
的值越小，词项越趋向于突发，该模型在文档分类的研究中呈现了较好的效果。Elkan
在前者的研究基础上提出了一种近似于DCM的指数分布EDCM，由于文档词项频次分布的稀疏性，实际的词项频次与
值均较 小，在这种情况下
与
高度近似，从而可以实现很大程度的简化。EDCM克服了DCM直觉式、无法快速估计的缺点，基于EDCM的EM算法相对于DCM的EM算法更为高效，且聚类的准确度更高。
狄利克雷过程（Dirichlet Process，DP）是狄利克雷分布在连续空间上的扩展，通常表示为G~DP（α，G 0 ），其中G 0 是基分布，α（α >0）是集中度参数，G表示基于DP在基分布和集中度参数基础上产生的某随机分布。直观而言，G 0 是DP的均值，α是逆方差，且α越大，表示G与G 0 的相似性越高。
Huang等
从CRP的角度运用DP，基于多项式模型先后提出了DPMFS和DPMFP模型，还采用简化的DMA模型解决了DPM无法快速估计参数的问题。DPMFP与DMA、EM-MN、K-MEANS、LDA以及EDCM等模型相比，DPMFP在K值未知的条件下更为稳健。Nguyen等
采用stick-breaking基于vMF提出了DPMvMF模型，DPMvMF在与基于多项式的聚类算法、基于vMF的软分配算法、基于vMF的DA算法、CLUTO等四个模型的对比实验中也得到了与Huang等研究的类似结果。
DPM作为一种非参数贝叶斯模型，具有无须预先给定簇数目K以及建模更具灵活性与适应性等优点，在模式识别领域已有较多的研究与应用，相对而言在文本聚类的领域仍处于拓展阶段，存在较多值得探索的方向，例如经典DPM聚类算法属于硬分配算法，无法处理簇重合的情况
；上述实验中使用的DPM为扁平式方法，无法揭示文本集的层次主题结构
；此外，在模式识别领域中有较多DP与语言模型结合的例子，例如句法分析
、语音分段
等，对于文本聚类研究有较强的借鉴意义。
随着互联网信息的快速增长，用户在信息检索上的时间成本也越来越大。如何高效地从海量的信息中获取所需的信息，成为学者们关注的重点。在改进策略方面，第一种方式是多样化地呈现结果（diversification）
，同时考虑结果的相关性和不同结果间的不相似性，从检索结果集的层面进行检索效果的优化
；第二种方式是对结果聚类（search results clustering）
，方便用户提供聚类标签定位所需的结果，并更好地调整查询策略。
检索结果聚类和文本聚类都需要考虑类中元素间的相似性和聚类标签的质量，此外，检索结果聚类还需考虑重叠聚类、速度和片段容忍
（即基于信息较少的网页片段snippet完成聚类）。
检索结果聚类的过程包括片段获取、预处理、特征选择、标签生成、聚类结果显示。Zamir等
对网页文档和网页片段的聚类结果进行了比较，发现片段中去掉了可能影响聚类的“噪声”信息，包含有助于聚类的项，相较于原始文档，片段的聚类准确率下降了约15%。对于聚类结果的展示，可以通过扁平划分、层次划分（常用树形式）、图三种方法。
根据侧重点不同，聚类算法可以分为两类
：一是以数据为中心，更关注算法，如1992年基于K均值聚类算法的Scatter/Gather系统，该系统存在的不足包括标签可理解性差、网络聚类适应性差等；二是以描述为中心，更关注对聚类标签，如1999年Zamir等提出的后缀树聚类算法（Suffix Tree Clustering，STC）
和lingo算法
，给予高频短语的共现生成聚类标签。基于以上两类聚类算法，目前这方面的研究主要有两个方向：一是对经典算法进行优化来适应聚类的要求；二是根据网页片段的特性，对包含STC等在内的基于标签的算法进行改进。两种算法的改进情况如图5-11所示。
图5-11 检索结果聚类算法改进的概貌
（一）经典聚类算法的改进
Xu
和Rokach
等对聚类方法的内涵、特征、各种指标进行了阐述，我们对聚类结果的改进工作进行梳理。
（1）重叠聚类（软聚类）
大部分经典算法中都不能产生重叠聚类，但在实际的应用中，存在一个文档中包含多个主题的情况，因此重叠聚类的实现是有必要的。相关研究从以下几个方面对这个问题进行了探索：
设定相似度阈值。Wang等
在K均值聚类算法中设定了相似度阈值，当片段与类簇中心的相似度超过该阈值时，将片段归入该类，从而产生了重叠类。
最小化目标函数。Wang等
通过最小化目标函数[公式（5-36）]，在模糊c-means（FCM）算法中实现了重叠聚类。
公式（5-36）中，m表示权重指数，m越大，模糊划分越显著。u ij 是片段i对类j的隶属度，v j 是第j个类簇的中心，‖x i -v j ‖是片段i和类j中心的欧式距离，表示片段与类的相似性。通过迭代优化u ij 和v j [公式（5-37）]
直到满足不等式（5-38），其中k为迭代次数，ε是终止条件，介于0到1。
（2）优化特征选择
高频短语。Zamir等
的研究目标，高频短语比以项为特征的聚类效果更好，聚类准确率能够提升20%，解决了难以满足聚类需求的问题。在特征选择上，主要包括以下几个方面的研究。
共现信息。Di Marco和Navigli等
提出把词义归纳（Word Sense Induction，WSI）应用于检索结果聚类。WSI是指在粗语料中进行词义自动发现，使用基于图的算法在用户查询的共现图中计算出最大生成树以识别出查询词的意义，完成聚类。基于Google Web1T语料库的测试表明，该算法的准确率达到了85.24%，而STC算法仅54.29%。Sha等
的工作思想与Di Marco和Navigli
的有相似之处，即以片段集中的项w为节点集，定义
为边
的标注，定义与
共现的项数量作为
的度（degree），通过不同项的度和边的相似性发现项关系并进行节点的合并，以形成类簇，该算法的平均F值为0.7，而STC和K均值聚类算法的平均F值大约是0.6和0.4。
链接信息。网页之间的链接关系能够为检索过程提供很多有用的信息。
Wang等
使用网页的入链和出链，以链接的共引关系为聚类特征，将基于链接的特征应用于聚类算法。
词汇相关度（lexical affinity，LA）。词汇相关度从相关度的角度发现项，因此能发现不相邻的项，在结构上比短语更加灵活。
外源性知识。Hu等
以维基百科和WordNet的背景知识作为外部特征，以层次化短语作为内部特征来确定聚类中心，结果表明改进后的K均值聚类算法F值可提高30.39%，平均准确度提高7.83%。
多特征融合。张刚等
提出融合DF、查询日志、查询词上下文等特征的类别标签抽取算法，来生成更加有意义的类别标签。
（3）优化聚类数K
设定阈值。大多聚类算法都需要提前设定阈值，如层次聚类法需要设定终止条件，K均值聚类算法需要设定K值。由于网页内容的不同，初始阈值往往很难设定。
AP算法。为解决FCM类簇数的选择问题，Wang等
引入了AP（Affinity Propagation）算法，即先设定一个较大的初始聚类数，使用AP算法优化类的数量，通过迭代运算获得最终的聚类数。
链接信息。夏斌等
通过网页间的链接信息，将多个权威网页作为初始的聚类中心，避免了确定初始K值，同时也提高了聚类的准确性。
检索结果数量。Cheng等
提出了一种K值的确定方法[公式（5-39）]，对新闻领域的检索结果进行聚类。公式中的N表示谷歌新闻检索结果数量，|C
i
|代表类簇C
i
中项的数量。
（二）基于标签的算法
基于标签的算法主要是寻找能够唯一表征该类特征的标签，根据这一特征将文本片段分配到不同的类别中。如Zamir等提出的后缀树聚类算法（Suffix Tree Clustering，STC）
，根据后缀树发现共现短语，作为文本聚类和生成类别标签的重要依据。
后缀树聚类算法以高频词序列为特征，将包含同一高频词序列的文本划分为一个基类。文档集重叠太多的基类被不断地合并，直到无法合并为止。合并计算使用了一种称为二进制相似度的度量方法，即定义基类B n 和B m ，如果|B m ∩B n |/|B m |>0.5并且|B m ∩ B n |/|B n |>0.5，则二者的相似度为1，表示可以合并。
从聚类结果中选择得分较高的K个类，类得分通过score（B）=|B|*f（|P|）计算，其中|B|为类B中的文档数，|P|为类B的标签短语中有意义项的数量，即短语P的长度，f随|P|线性增长，如果短语长度大于6则f保持不变（公式5-40）。
后缀树聚类算法具有以下不足：由于该模型是在英语语境中被提出的，因此在处理中文语料时，会出现关键短语抽取错误的问题，生成一些无意义的短语；该模型以高频词序列为特征进行文档聚类，会导致一些不包含高频词的相关文档难以被分配到类簇中；以短语为特征构建后缀树时，容易忽略一些长度较长的短语，造成误差；构建好的后缀树会占用很大的内存，且对于基类的计分方法过于简单。针对这些问题，学者们也提出了以下解决方法。
（1）优化计分算法
后缀树聚类算法对重叠文档会出现重复计分的问题，Daniel Crabtree等
提出了ESTC算法，即将基类B的每个文档得分记为s/|B|，将类中所有文档得分的均值作为该类的总分，把F值作为评价指标，当阈值大于0.5时，ESTC算法比STC提高50%。
（2）优化合并算法
Janruang J等
对后缀树聚类算法的合并运算进行了改进，见公式5-41，发现了更为真实的常用短语标签，聚类的平均准确率比STC高10%。其中A和B是两个基类，A（d）和B（d）分别是A类和B类中的片段，{a
0
，a1，…，a
n
}是出现在A类中的一系列标签短语。
Maslowska
提出HSTC算法，通过计算|C
i
∩C
j
|/|C
j
|≥α，α∈（0.5;1]，发现了类之间的包含关系，增加了最终聚类导航的层次性。
（3）优化候选标签
标签是后缀树聚类算法的基础与质量保证。Hu等
将题名中的项引入聚类标签的选择过程。骆雄武等
将一些启发式规则应用于候选标签的选择上。Zhang等
通过比较高频项的上下文，基于项的长度和频率定义项的重要性，结合互信息完成项的选择。针对类簇中难以获得准确有意义的标签的问题，Zeng等设计了SRC系统
整合TFIDF、项长度n、簇内相似性、类熵以及项独立性计算标签权重，用真实数据作为训练文档，利用训练结果优化候选标签，将无监督的检索结果聚类问题转换为有监督的突出短语排序问题。
（4）优化数据结构
张健沛等
将PAT-tree和STC进行了整合，利用PAT-tree在线性时间内确定关键词频率的特点，弥补了STC处理中文语料的不足。
Wang等
结合STC和语音模型N-gram，提出了一种新的后缀树，设定N可以将一些较长的项过滤掉，经过实验发现，在N=3的情况下，10767个STC短语经过过滤，得到了5765个短语，该算法得到的标签比传统的STC更短，但量级更轻，减少了内存占用，运算速度更快。Zhang等
提出的SHOC（semantic hierarchical online clustering）算法，采用了后缀数组（suffix array）代替后缀树，同样减少了对内存的占用。
通过对聚类算法的优化方法进行梳理，总结出以下几点结论：（1）后缀树聚类算法构建后缀树的时间复杂度与句子的数量呈线性关系；（2）基于标签的聚类算法实现了软聚类；（3）后缀树聚类算法族在准确率方面总体优于以K均值聚类算法为代表的经典算法；（4）相较于聚类质量的提高，时间上的延迟仍是可以接受的。
（三）检索结果聚类的问题与未来
由目前检索结果聚类的研究来看，仍存在一些不足之处，如聚类结果的类簇粒度不均匀、聚类层次不足、聚类标签与内容不一致、对检索结果的预见性不足等。因此，检索结果聚类在未来的研究可以从以下几方面着手。
（1）提高聚类结果输出的有效性
已有研究大多集中于改进聚类算法，而缺乏对输出结果的关注。
有一些研究提出对后者的解决思路：提供类簇中内容的预览
；针对结果的表现力，使用多文档自动摘要的形式呈现
；Stein等
引入长尾理论对检索结果进行相关性排序，对尾部文档进行聚类，并将其与相关性较高的文档相结合，以展示检索结果。在对结果的展示方面，文献结果
为了适应逐渐增加的移动需求，Rivadeneira等
研究了聚类交互界面，设计了面向移动端的聚类和展示结构。同时，可视化的结果展示能够带来更好的用户体验
，因此，未来的研究可以关注可视化在聚类结果展示方面的应用。
（2）特征选择
在对各种聚类算法进行优化的方法中，优化特征选择是一个重要的方面。在进行特征选择时，对影响特征选择的元素（如文档片段）进行优化，有助于选择更有意义的特征。
获取到类簇的特征之后，需要对特征进行描述，可以使用超链接
、多特征融合
等方法得到具有说服力的特征描述。Navigli等
利用搜索词的共现关系生成了一系列诱导词，将诱导词应用于增强聚类准确性。此外，利用各种外部知识源（如维基百科以及WordNet等）也有助于提高聚类准确性，将聚类结果与排名列表相结合，对于提高聚类质量也具有明显的价值。
（3）挖掘用户行为研究成果
在优化检索结果聚类的路径中，利用对用户行为的研究成果具有很大的意义。Koshman等
对Vivisimo为期两周的日志进行了分析，发现了以下几点：大部分搜索行为只包含两个项；大部分搜索会话仅有一次搜索且时间不超过一分钟；11.1%的查询会话是多任务的，查询会话中包含多个查询主题；将近一半的用户只浏览单一的类簇，类簇树展开的情况极少。通过这些研究可以看出，在当前研究已涉及大量文本特征的情况下，加入用户行为特征的分析无疑会对优化检索结果有很大帮助，除了能够提高检索系统的可用性之外，还能够为用户提供个性化的检索结果，进一步提升用户体验。
（4）多途径的协同研究
多种途径协同作用的方法具有较好的聚类效果。Maiti等
、张刚等
的研究表明，融合多种特征和算法能够有效提高聚类的准确率。Vadrevu等
调整了聚类框架，从离线聚类（offline clustering）、增量聚类（incremental clustering）以及实时聚类（realtime clustering）三个过程进行了聚类研究；Fred和Jain的研究表明在非预定义结构的情况下合并多个聚类结果有助于类簇识别
；基于图划分的聚类
和利用LSI改进的聚类算法
在聚类准确性等方面有所提高。