文本聚类中的贝叶斯后验模型选择.doc

文本聚类中的贝叶斯后验模型选择摘要：作者：姜宁 - 被引用次数：24 - 相关文章关键词：类别：专题技术来源：牛档搜索（Niudown.COM）本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！11-10文本聚类中的贝叶斯后验模型选择方法姜宁史忠植（中国科技大学研究生院计算机学部 北京 100039）（中国科学院计算技术研究所 北京 100080）（ , ）摘要 文章对聚类分析中的模型选择特别是混合模型方法进行了较全面地介绍与总结，对其中的关键技术逐一进行了讨论。在此基础上，文中提出了贝叶斯后验模型选择方法，并把它与文档产生特征序列的物理模型相结合，给出了一个用于聚类分析的概率模型。对真实文本数据的测试中该模型取得了非常好的效果。同时本文对不同贝叶斯估计方法取得的效果进行了对比。关键词 文本聚类、贝叶斯后验模型选择、混合模型、期望最大化、贝叶斯估计中图法分类号 TP181Bayesian Posterior Model Selection for Text ClusteringJIANG NingSHI Zhong-Zhi(Dept. Of Computer Science, Graduate School, University of Science & Technology of China, Beijing 100039)(Institute of Computing Technologies, Chinese Academy of Sciences, Beijing, 100080)( , )Abstract Model selection has been shown as an efficient technique for clustering analysis, in particular used with the mixture model. In this paper, the authors propose a new model selection approach, Bayesian posterior model selection, which greatly reduces computational complexity of using mixture models and improves accuracy of Chinese text clustering. To estimate parameters in a posterior model, we compare two different Bayesian estimation techniques, Maximum Likelihood Estimation and Conditional Expectation Estimation. This paper also describes a hierarchical clustering algorithm for text clustering based on posterior model selection. Results of high accuracy have been achieved in experiments for real-world text clustering.Keywords Text Clustering, Bayesian Posterior Model Selection, Mixture Model, Expectation Maximization, Bayesian Estimation1. 引言与结构化的信息相比，非结构化的文本信息更加丰富与繁杂。随着互联网络的发展， Web上的文本资源在几年间呈现爆炸式的增长。这些文本信息数据量大、内容繁杂而且处在不断变化之中。随着信息资源的日益丰富，如何充分有效的利用信息成为人们关注的焦点。聚类分析作为一种数据挖掘的重要手段，在文本挖掘中也扮演着非常重要的角色。在最近几年的研究文献中 H.H. Bock, Probabilistic Models in Cluster Analysis, Computational Statistics and Data Analysis, 1996, 23, pp.528，一类基于概率模型的聚类分析技术逐渐被研究者所关注。研究人员通过分析数据与各种概率模型之间的匹配问题，提出了一系列新的聚类算法。同时这方面的研究也表明，许多传统的聚类算法都可以解释为某种概率模型的近似。常用的K均值算法和Wards方法也可以用特定情形下的多元正态模型加以解释 Chris Fraley and Adrian E.Raftery, Model-Based Clustering, Discriminate Analysis, and Density Estimation, Technical Report NO.380, Department of Statistics, University of Washington, October 2000。本文介绍了基于模型选择进行聚类分析的理论，和相关的基本算法。在此基础上讨论了一种特征序列的“随机发生”模型，给出了一个基于贝叶斯后验概率的模型选择方法。其中对于参数的学习，我们采用了两种不同的贝叶斯估计策略，最大后验估计和条件期望估计，并进行了比较。基于本文的后验模型，结合层次聚类算法进行试验。通过测试，新的算法取得了令人满意的效果，对正式文本数据的测试准确率达到了85%。值得一提的是，新算法对目标聚类数目不敏感，即使应用选择的目标个数不是最佳的，也能获得较好的精度，这大大提高了算法的应用价值。两种不同的贝叶斯估计策略进行对比显示出采用随机化的条件期望估计能更好的适应稀疏数据的情况。2. 贝叶斯模型选择模型选择的原理模型选择问题可以表述为在给定的数据样本和相关参数信息的条件下，寻求具有最大后验概率的模型。在给定的样本下，某一模型的后验概率与的先验概率和似然函数的乘积成比例，因而模型选择问题可以表示成下面的优化问题：(21)贝叶斯方法下的模型选择通过选取适当的模型先验分布，可以将人类专家的知识和给定的样本数据中提供的信息结合在一起 Petri T. Kontkanen, Petri J. Myllymaki and Henry R. Tirri, Comparing Bayesian Model Class Selection Criteria by Discrete Finite Mixtures, Information, Statistics and Induction in Science (Proceedings of the ISIS96 Conference in Melbourne, Australia, August 1996), 1996, pp.364374。在没有任何先验信息的情况下，可以采用贝叶斯假设将看作均匀分布。这种情况下模型选择问题可以进一步化简为似然函数的优化问题：(22)为了比较不同模型的优劣，通常采用贝叶斯因子（bayes factor）2：(23)混合模型在基于概率模型的聚类分析中，通常认为数据是通过多个相互独立的过程产生的，其中每个产生过程对应着一个类别。数据产生的概率可以用混合模型表示。混合模型(mixture models)假设数据的分布是一些简单分布的线性组合。如果已知分类类别数为，混合模型可表示为个分量分布的混合：(24)其中是混合模型，表示与第个类别相对应的模型分量。分量分布表示类别产生数据的概率，表示分量的权重，可以理解为从数据全集中（而不是给定的样本中）取出一个数据恰好是类别的先验概率。分量分布的选择很大程度上决定了混合模型对数据的适应能力，选择适当的分布族对于混合模型的效果有很大影响。由于数学处理方便等原因，通常选择多元正态分布（multivariate normal）作为分量分布，在这种形式下混合模型的分布为超椭圆分布（hyper ellipsoidal） An Introduction to Cluster Analysis for Data Mining，from /classes/Spring-2000/csci5980-dm/cluster-survey.pdf 。如果假定样本数据的实例都是相互独立的，上面的混合模型对样本的似然函数可以表示为：(25)混合模型的期望最大化前面已经指出，模型选择问题可以转化为对的优化问题。中通常包含某些与相关的参数需要确定，一般可以采用最大似然估计，既。通常要通过解析方法求解混合模型的最大似然估计值非常困难，需要采用某种数值方法，如期望最大化算法（EM, expectation maximization）。EM算法是一种常用的求解最大似然估计和最大后验估计的方法，特别是在似然函数形式较复杂时非常有效。EM算法的推广形式，如Monte Carlo EM 高等数理统计，超星图书馆，，pp.442444(Advance Mathematical Statistics (in Chinese), ，pp.442444)和CEM2等也较为常见。混合模型应用EM算法的关键在于确定条件期望的表达式，为此我们重新书写混合模型的形式，并省去以简化书写。记为模型的参数集，为与模型的分量相关联的参数：(26)为使用EM算法，为每个数据添加一个指示类别的潜在矢量，并且：，这使得的值域是一个离散有限集合。在给定的样本数据和给定的参数上的条件期望可以表示为：(27)其中，表示模型在添加数据（由所有的构成的矩阵）下的对数似然。表示在给定当前参数下的分布。此式的详细化简过程可以参照文献 Jeff A. Bilmes, A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models, Technical Report TR-97-021, Computer Science Division Department of Electrical Engineering and Computer Science, U.C. Berkeley, April 1998 中的叙述。一般在给出具体的分布形式之后，的更新，可以通过拉格朗日乘数法进行计算。采用高斯分布时具体的表达式可以在文献6中找到。采用多项分布的情况可以参考3。EM算法处理混合模型存在一些限制2，对于混合模型，算法的收敛速度变得非常慢，而且算法得到的往往是一个局部极大值而不是最大值。样本中属于某个类别的对象较少时，算法产生较大的误差。即使这样，EM算法仍然被广泛地用于混合模型的最大似然估计，并且取得了不错的效果。证据在贝叶斯分析中，当中存在未知的参数时，可以通过期望最大化找到其最大似然估计值。这种方法仅当每个类别都有足够的样本点时，才能获得较理想的效果。一般来说对参数进行随机化处理，引入参数的先验分布，可以使结果更具稳健性。对中的参数应用全概率公式有：(28)上式中是似然函数中的参数，表示在给定参数下的似然函数，是模型中参数的先验分布。此时的称为的边界似然（Marginal Likelihood）或积分似然（Integrated Likelihood） R.E. Kass and A.E. Raftery, Bayesian Factors and Model Uncertainly. Technical Report 571, Dept. of Statistics, Carnegie-Mellon University, Dec. 1993或者称为证据（Evidence） I.J. Good, Weight of Evidence: A Brief Survey. Bayesian Statistics2, pp.249269, Elsevier, New York, 1985。与多层先验相类似，随机化处理是边界似然比点估计能得到更好的稳健型。在高维的参数空间下，计算混合模型的边界似然是非常困难的，需要采用某种近似形式。常用的近似方法有BIC (Bayesian Information Criterion)和AIC (Akaike Information Criterion) 3 贝叶斯统计推断，超星图书馆，(Bayesian Inferential Statistics (in Chinese), )：(29)(210)其中是独立参数的个数，是最大对数似然估计值，是样本数据的个数。此外在AutoClass P. Cheeseman, and J. Stutz, Bayesian Classification (AutoClass): Theory and Results. Knowledge Discovery in Data Bases II. Menlo Park, Calif.: AAAI Press / The MIT Press, 1995.中给出了一种通过完整数据（即添加了潜在变量之后的数据）的证据估计不完整数据（原始数据）的证据的近似方法： (211)这里的潜在变量通常就是上一节所提到的期望最大化中的添加数据，和分别表示完整数据和不完整数据的最大似然估计值，可以用EM算法得到。3. 贝叶斯后验模型选择采用混合模型，特别是EM算法导致计算上的复杂性同时会引起较大的计算误差，本文尝试寻找适当的概率模型，以便用解析方法避免这些问题。贝叶斯后验模型聚类算法中的模型选择的核心是对不同的分类方案的后验概率进行比较，找出有最大后验概率的分类方案。与通常的化简方法不同，我们没有将最大化后验概率近似为最大化似然函数，而是通过给出的一个具体的形式，来直接得到后验概率的形式。为了表示分类方案，我们考虑每一篇文章都有一个对应的概率矢量，是预期的类别数。这样与数据对应着一个行列的矩阵，它的每一个元素表示文章在多大程度上属于类别，从而可以表示任意的分类方案。可以将的后验概率表示为：(31)符号表示“左右两边成比例”，其大小只相差一个常系数，在这里系数是。我们假设每篇文章的产生过程是相互独立的，相应的每篇文章的类别矢量也是相互独立的，则可以表示为：(32)通常情况下由全概率公式可以给出，这正是文档的混合模型，上式在数学上很难处理。幸运的是由于我们采用非模糊聚类，聚类算法所考虑的每一个潜在划分方案都是将每个文档划入特定的类别中的，也就是说中类别矢量只能有一个分量为1，其他的分量都为零：。在这种情况下的取值只有下面几种可能：(33)对于满足的类别矢量显然有，这里表示类别矢量中唯一不为0的分量。这样我们就可以给出每一个潜在的划分方案的后验概率为：(34)与相比，就非常容易计算了。变换一下形式可以得到：(35)后面将看到，与通常的似然模型相比，采用这一后验模型大大降低了参数学习的复杂度，可以直接求解精确的最大后验估计，避免了似然模型采用EM算法估计最大似然概率引起的复杂性和计算量。进而在这一点上，避免了EM算法陷入局部极大值引起的误差。特征序列产生过程的表示为了得到的具体形式，我们通过描述一个文档中特征词的产生过程，来给出一个合理的文档特征序列的随机发生模型。按照矢量空间模型（VSM）的观点，每一篇文章都可以用一个特征空间中的矢量表示。矢量的每一个维度表示一个特征词，其数值表示特征词在文章中出现的次数。这种表示法忽略了文章的结构性信息，使得聚类完全依赖于文档中特征的出现频率。在VSM中：文档的特征矢量表示为，,其中表示特征空间中第维的特征词出现的频数。文档类是文档全集中一个文档的集合，其特征矢量可以表示为其中，表示文档中特征词出现的频数。考虑到VSM模型的特点，每个文档仅由各个特征的频数表示，而与特征出现的顺序无关，可以将文档类直观的看作一个特征的发生器，不同的文档类中每个特征有不同的发生概率。我们将文档类看作一个特征（符号）的发生器，通过观察所产生的一段特征序列来获得文档。由于VSM忽略了特征出现的顺序，我们可以考虑每个特征出现频数的是独立同分布（i.i.d.）的随机变量。文档类产生的概率可以表示为中出现的频率，即(36)我们定义文档类的参数是与分布相联系的一个连续概率矢量：，并且，且。实际上就表示文档类产生特征词的概率。文档类产生文档中的每个特征词是个相互独立的过程。如果用表示文档中出现的第个特征词，文档类产生长度为的特征词序列的概率可以表示为(37)其中表示产生长度为的序列的概率。我们认为文章的长度与类别无关，因而将其视为一常数。由此可以给出的最终形式：(38)这样基于这一模型，潜在的划分方案的后验概率可以表示为：(39)式中表示类别中的文档个数。其中隐含有约束条件，且和。模型参数的学习上式中先验概率和文档类的特征词分布矢量都是从文档全集中获得的，是未知参数，需要从样本数据中进行估计。为了书写简便，我们记参数，后验概率改写为：(310)和混合模型中处理似然函数的做法相似，此处对于未知参数的处理也可以采用两种不同的策略：1. 采用点估计，可以采用贝叶斯方法中的最大后验估计来学习参数。2. 参数随机化方法，实际上就是贝叶斯方法中的条件期望估计。最大后验估计从的意义上看它们之间在文档全集中没有必然的联系，我们假设这组参数矢量相互独立。这样可以给出各个参数的最大后验估计：(311)(312)这样我们可以给出最大后验估计值：(313)条件期望估计在贝叶斯决策中条件期望估计是损失函数为平方损失时，使损失为最小的估计方式。由于平方损失是最常用的损失函数，条件期望估计在贝叶斯估计中有特殊的地位9。对参数集的条件期望为：(314)类似最大后验估计的做法，可以假设这组参数矢量相互独立。于是参数的先验密度函数有如下的形式：(315)相应的条件期望估计可以表示为：(316)为先验分布、选择适当的分布族，可以采用共轭分布法。共轭分布使得参数的先验与后验属于相同的类型，使得经验知识与样本提供的信息保持了某种一致性。如果我们用过去的知识和现有的样本提供的信息作为历史知识，也就是以这里的后验分布，作为下一步实验的先验知识，那么在新的数据下，我们得到新的后验分布仍然可以保持相同的类型。我们得到共轭分布为狄利克雷分布。显然共轭分布使得参数的后验分布总能够保持相同的类型。这里我们选择狄利克雷分步的密度函数作为先验密度：其中(317)(318)其中，；，为超参数。这样我们得到潜在分类方案在给定数据下后验概率的条件期望估计如下式。(319)4. 基于后验模型的层次聚类算法层次聚类又被称作系统聚类，通过将已有的类别两两比较，找出最相近的类别合并，最终所有的数据都被聚到单一的类别中。由于有较大的搜索空间，层次聚类比平面划分法容易获得较高的精度，其代价是算法的速度下降了许多。将层次聚类算法与模型选择相结合在许多领域都取得了成功 F. Murtagh and A.E.Raftery, Fitting straight lines to point patterns, Pattern Recognition 17, 1984, pp.479483, J.D. Banfield and A.E. Raftery, Model-based Gaussian and non-Gaussian clustering, Biometrics 49, 1993, pp.803821。一方面层次聚类限制搜索范围，在速度与准确度之间找到了较好的折衷；另一方面在层次聚类的局部目标函数中使用对数似然比（或贝叶斯因子），消去相同项后，可以大幅度降低后验概率的计算量。层次凝聚算法的基本思路如下：1. 在初始化阶段，对于给定的文档集合，将D中的每个文档作为一个独立的类别，即。2. 根据相似性度量，将最相似的两个类别合并为一个类别。重复步骤2)直到只有一个类别，或达到某种可接受的标准时算法停止。文档2345678910111213步骤图 41 凝聚方式的层次聚类过程对于我们的后验模型，由于前面给出了两种不同的参数估计方法，对应着两种相似性度量的目标函数。采用最大后验估计的层次聚类算法层次聚类中的每一步是基于前一步的选择进行局部优化。第步的分类方案和第步的分类方案之间显然有函数关系存在。当算法执行到步时前一步分类方案为，相应的后验概率是已经确定的常数，显然有：(41)化简后得到局部目标函数为：(42)其中，表示特征词在整个类别中的出现频率。为了引用方便，此算法在后面的讨论中被称作MSBP (Model Selection Based algorithm with maximum Posterior)采用条件期望估计的层次聚类算法类似前面的做法，局部目标函数为：(43)其中。上式中前两项对于聚类过程每一阶段的局部优化函数而言是常数（因为是常数），实际计算中可以忽略。由于超参数的选择对结果没有显著的影响，在式中我们选择了统一的超参数以简化计算：令都为1，相应的，上式在实际计算过程中需要计算大量的形如的项。为了提高算法的速度，在计算较大的n时（大于1000），我们采用了stirling近似公式，取对数后为：(44)为了引用方便，此算法在后面的讨论中被称作MSBE (Model Selection Based algorithm with conditional Expectation)算法复杂度分析个对象进行层次聚类的平均复杂度为,最坏复杂度为。考虑到特征的因素，在个特征词构成的空间中，对个文档特征矢量进行聚类的平均复杂度为,最坏复杂度为。两个算法有相同的复杂度，条件期望估计中每一步的计算量较大，且涉及更多的对数运算，在实际测试中采用最大后验估计的算法处理相同数据使用的时间要少许多。5. 试验比较方案设计我们选用的测试数据是一组体育方面的文章，六个类别共计485篇中文文章，是通过spider从FM365网站上搜集的。经过切词处理，去掉停用词（stop words）后保留了2719个特征词。足球篮球排球乒乓球网球棋牌篇数12010077416384表 51衡量传统信息检索系统的性能参数召回率（Recall）和精度（Precision）也是衡量分类算法效果的常用指标。然而聚类的过程中并不存在自动分类类别与手工分类类别确定的一一对应关系，因而无法像分类一样直接以精度和召回率作为评价标准。为此本文选择了文献 Iwayama Makoto, Tokunaga Takenobu, Hierachical Baysian Clustering for Automatic Text Classification, technical report, Department of Computer Science Tokyo Institute of Technology, 1995中的平均准确率 (Averaged Accuracy, AA) 作为评价的标准。平均准确率通过考察任意两篇文章之间类属关系是否一致来评价聚类的效果。任意两篇文章之间的关系，按照手工分类的标准和自动聚类的标准可以有以下四种情况：两篇文档之间关系手工分类中属于同一类是否自动聚类中属于同一类是ab否cd表 52平均准确率定义为积极准确率（Positive Accuracy，PA）与消极准确率（negative accuracy，NA）的算术平均值，即：(51)积极准确率PA定义为：(52)消极准确率NA定义为：(53)结果分析为了考察算法的效果，我们用K-means，Wards method