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

1、8- 辛宀姜宁文本聚类中的贝叶斯后验模型选择方法史忠植中国科技大学研究生院计算机学部北京100039)(中国科学院计算技术研究所北京100080)摘要文章对聚类分析中的模型选择特别是混合模型方法进行了较全面地介绍与总结，对其中的关键技术逐一进行了讨论。在此基础上，文中提出了贝叶斯后验模型选择方法，并把它与文档产生特征序列的物理模型相结合，给出了一个用于聚类分析的概率模型。对真实文本数据的测试中该模型取得了了非常好的效果。同时本文对不同的贝叶斯估计方法的效果进行了讨论。关键词文本聚类、贝叶斯后验模型选择、混合模型、期望最大化、贝叶斯估计BayesianPosteriorModelSelectio

2、nforTextClusteringAbstractAcompleteintroductionofthemodelselectioninclusteringanalysisisincludedinthepaper,andkeytechnologiesinitarediscussedseriatim,adhocmixturemodel.Basedonthese,theauthorintroducestheBayesianposteriormodelselection.Thispaperalsodescribesaposteriormodelbasedhierarchicalclusteringa

3、lgorithm,withtheanalysisofthedomainitself.Resultsofhighaccuracyhavebeenachievedinexperimentsforrealworldtextclustering.KeywordsTextClustering,BayesianPosteriorModelSelection,MixtureModel,ExpectationMaximization,BayesianEstimation1.引言与结构化的信息相比，非结构化的文本信息更加丰富与繁杂。随着互联网络的发展，Web上的文本资源在几年间呈现爆炸式的增长。这些文本信息数据

4、量大、内容繁杂而且处在不断变化之中。随着信息资源的日益丰富，如何充分有效的利用信息成为人们关注的焦点。聚类分析作为一种数据挖掘的重要手段，在文本挖掘中也扮演着非常重要的角色。在最近几年的研究文献中1，一类基于概率模型的聚类分析技术逐渐被研究者所关注。研究人员通过分析数据与各种概率模型之间的匹配问题，提出了一系列新的聚类算法。同时这方面的研究也表明，许多传统的聚类算法都可以解释为某种概率模型的近似。常用的K均值算法和Wards方法也可以用特定情形下的多元正态模型加以解释2。本文介绍了基于模型选择进行聚类分析的理论，和相关的基本算法。在此基础上讨论了一种特征序列的“随机发生”模型，并给出了一个基于

5、贝叶斯后验概率的模型选择算法。其中对于参数的学习，我们采用了两种不同的贝叶斯估计策略，最大后验估计和条件期望估计，并进行了比较。基于本文的后验模型，我们设计了采用层次聚类的算法进行测试。通过测试，新的算法取得了令人满意的效果，对正式文本数据的测试准确率达到了85%。值得一提的是，新算法对目标聚类数目不敏感，即使应用选择的目标个数不是最佳的，也能获得较好的精度，这大大提高了算法的应用价值。另外，MSBE与MSBP的对比也表明了采用随机化的条件期望估计能更好的适应稀疏数据的情况。2.贝叶斯模型选择模型选择的原理模型选择问题可以表述为在给定的数据样本和相关参数信息的条件下，寻求具有最大后验概率的模型

6、。在给定的样本D下，某一模型M的后验概率与M的先验概率和似然函数的乘积成比例，因而模型选择问题可以表示成下面的优化问题：argmaxP(M|D)argmaxP(D|M)P(M)(2-1)MM贝叶斯方法下的模型选择通过选取适当的模型先验分布p(m)，可以将人类专家的知识和给定的样本数据中提供的信息结合在一起3。在没有任何先验信息的情况下，可以采用贝叶斯假设将p(M)看作均匀分布。这种情况下模型选择问题可以进一步化简为似然函数P(D|M)的优化问题：argmaxP(MID)二argmaxP(DIM)(2-2)MM为了比较不同模型的优略，通常采用贝叶斯因子B(bayesfactor)2：12P(DI

7、M)B=112P(DIM)2(2-3)混合模型在基于概率模型的聚类分析中，通常认为数据是通过多个相互独立的过程产生的，其中每个产生过程对应着一个类别。数据产生的概率可以用混合模型表示。混合模型(mixturemodels)假设数据的分布是一些简单分布的线性组合。如果已知分类类别数为K，混合模型可表示为K个分量分布的混合：P(dIM)=P(M)P(dIM)(2-4)kkk=1其中M是混合模型，m表示与第k个类别Mk相对应的模型分量。分量分布P(dIM)表示类别kk产生数据d的概率，P(M)表示分量P(dIM)的权重，可以理解为从数据全集中(而不是给定的样本中)取出一个数据恰好是类别k的先验概率。

8、分量分布的选择很大程度上决定了混合模型对数据的适应能力，选择适当的分布族对于混合模型的效果有很大影响。由于数学处理方便等原因，通常选择多元正态分布(multivariatenormal)作为分量分布，在这种形式下混合模型的分布为超椭圆分布(hyperellipsoidal)4。如果给定的数据d=ddd是一个随12N机样本，其中的每一个实例d,d都是相互独立ij的。上面的混合模型M对样本D的似然函数可以表示为：L(DIM)=口P(M)P(dIM)(2-5)kkdGDk=1混合模型的期望最大化前面已经指出，模型选择问题通常转化为对argmaxL(DIM)的优化冋题。L(DIM)中通常包M含某些与M

9、相关的参数需要确定，一般可以采用最大似然估计既L(DIM)=maxL(DI0)。通常0要通过解析方法求解混合模型的最大似然估计值非常困难，需要采用某种数值方法，如期望最大化算法(EM,expectationmaximization)0EM算法是一种常用的求解最大似然估计和最大后验估计的方法，特别是在似然函数形式较复杂时非常有效。EM算法的推广形式，如MonteCarloEM和CEM2等也较为常见。本文将要介绍的算法通过选择适当的模型，能够通过解析方法直接得到参数，避免了这种复杂性。这里仅对混合模型的EM算法作一个简单介绍。基本的EM算法是一个迭代的过程，它交替的执行E步和M步，直到参数的估计稳

10、定为止，以达到使似然函数值最大的目的。它的迭代过程可描述如下：E步，基于当前的参数估计，计算添加潜在数据后似然函数对潜在数据的条件期望Q(0,0)；M步，基于E步的期望值，最大化当前的参数估计0=argmaxQ(0,0)；0混合模型的EM算法关键在于确定q(0,0)的表达式，为此我们重新书写混合模型的形式，并省去M以简化书写。记0为模型M的参数集，b=P(M)，0为P(dIM)与模型的分量Mkkkkk相关联的参数：P(d10)=P(d10)(2-6)kkk=1为使用EM算法，为每个数据d添加一个指示类别的潜在矢量屮(d)=仰(d)M(d)，M(d)，并12K且：屮(d)=|1ifdGck，这使

11、得屮(d)的值域是一k0else离散有限集合。模型M在添加数据屮(由所有的屮(d)构成的矩阵)下的对数似然表示为：logL(DI屮,0)=ElogbP(d10)(2-7)c(d)c(d)dGD式中我们用c(d)表示屮(d)为文档d所指派的类别，也就是屮(d)中仅有的为1的分量。在给定当前参数0下屮的分布可以表示为：P(屮ID,0)=nP(屮(d)Id,0)(2-8)dGD其中：.&P(dIO)P(屮(d)Id,0)=c(d兗&P(dIO)kk(2-9)k=1计算logL(DI屮,0)在给定的样本数据d和给定的参数0上的条件期望：Q(0,0)=ETogL(DI屮,0)ID,0=工logL(DI屮

12、,0)P(屮ID,&)屮K(2-10)=LLlog(CT)P(d,TI0)+kkk=1dgDKLLlogP(d10)P(d,TI0)kkk=1dgD此式的详细化简过程可以参考文献6的叙述。再EM的迭代过程中，更新的&总可以使模型对给定数据的似然函数值得到改善。一般在给出具体的分布形式之后，0=argmaxQ(0,0)0的更新，可以通过拉格朗日乘数法进行计算。采用高斯分布时具体的表达式可以在文献6中找到。采用多项分布的情况可以参考3。EM算法处理混合模型存在一些限制2，对于混合模型，算法的收敛速度变得非常慢，而且算法得到的往往是一个局部极大值而不是最大值。样本中属于某个类别的对象较少时，算法产生

13、较大的误差。即使这样，EM算法仍然被广泛地用于混合模型的最大似然估计，并且取得了不错的效果。证据在贝叶斯分析中，当P(D|M)中存在未知的参数时，可以通过期望最大化找到其最大似然估计值。这种方法仅当每个类别都有足够的样本点时，才能获得较理想的效果。一般来说对参数进行随机化处理，引入参数的先验分布，可以使结果更具稳健性。对P(DIM)中的参数应用全概率公式有：P(DIM)=fL(DI0,M)兀(0IM)d0(2-11)上式中0是似然函数中的参数，l(DI0,M)表示在给定参数下的似然函数，兀(0IM)是模型M中参数的先验分布。此时的P(dim)称为M的边界似然(MarginalLikelihoo

14、d)或积分似然(IntegratedLikelihood)7或者称为证据(Evidence)8。与多层先验相类似，随机化处理是边界似然比点估计能得到更好的稳健型。在高维的参数空间下，计算混合模型的边界似然是非常困难的，需要采用某种近似形式。常用的近似方法有BIC(BayesianInformationCriterion)和AIC(AkaikeInformationCriterion)：BIC:2logP(DIM)2logL(DI0,M)-vlog(n)(2-12)AIC:logP(DIM)logL(DI0,M)-n(2-13)其中v是独立参数的个数，L(D|0,M)是最大对数似然估计值，n是样

15、本数据的个数。此外在AutoClass10中给出了一种通过完整数据(即添加了潜在变量之后的数据)的证据估计不完整数据(原始数据D)的证据的近似方法：P(DIM)-P(DIM)*三(2-14)这里的潜在变量屮通常就是上一节所提到的期望最大化中的添加数据，l(D,屮|0,M)和L(D|0,M)分别表示完整数据和不完整数据的最大似然估计值，可以用EM算法得到。3.贝叶斯后验模型选择采用混合模型导致了计算上的复杂性同并会引起较大的计算误差，本文尝试寻找适当的概率模型，以便用解析方法避免这些问题贝叶斯后验模型聚类算法中的模型选择的核心是对不同的分类方案Q的后验概率进行比较，找出有最大后验概率的分类方案。

16、与通常的化简方法不同我们没有将最大化后验概率argmaxP(QID)近似Q为最大化似然函数argmaxP(DIQ)，而是通过给Q出Q的一个具体的形式，来直接得到后验概率P(QID)的形式。为了表示分类方案Q，我们考虑每一篇文章d都有一个对应的概率矢量屮(d)，屮()=(屮(d),屮(d),，屮(d),L屮(d)=112KkK是预期的类k=1别数。这样与数据D对应着个IDI行K列的矩阵屮，他的每一个元素屮(d)表示文章d在多大程k度上属于类别ck，从而屮可以表示任意的分类方案。可以将Q的后验概率表示为:了EM算法陷入局部极大值引起的误差。P(屮)P(DI屮)jP(屮)P(DI屮)特征序列产生过程

17、的表示(3-1)我们假设每篇文章的产生过程是相互独立的，相应的每篇文章的类别矢量也是相互独立的，贝lPwID)可以表示为：p(qId)xnp(屮(d)p(dI屮(d)(3-2)dgD通常情况下由全概率公式可以给出为了得到P(dIc)的具体形式，我们通过描k述一个文档中特征词的产生过程，来给出一个合理的文档特征序列的随机发生模型。按照矢量空间模型(VSM)的观点，每一篇文章都可以用一个特征空间中的矢量表示。矢量的每一个维度表示一个特征词，其数值表示特征词在文章中出现的次数。这种表示法忽略了文章的结构性信息，使得聚类完全依赖于文档中特征P(dI屮(d)=屮(d)p(dIc)，这正是文档的混合模kk

18、k1型，上式在数学上很难处理。幸运的是由于我们采用非模糊聚类，聚类算法所考虑的每一个潜在划分方案都是将每个文档划入特定的类别中的，也就是说中类别矢量屮(d)只能有一个分量为1，其他的分量都为零：的出现频率。在VSM中：文档d的特征矢量表示为d(n,n,n,n,n)，1m0(k)0。实际上0(k)就表示文档类c产生特征mmk词t的概率P(tIc)。mmk文档类产生文档中的每个特征词是个相互独立的过程。如果用w表示文档d中出现的第i个特征词，文档类c产生长度为N的特征词序k(3一11)列d的概率可以表示为P(dIc)=兀(NIc)p(d10(k)kk=兀(NIc)flp(w10(k)ki(3-7)

19、0(k)=(其中兀(NJ表示c产生长度为N的序列kk的概率。我们认为文章的长度与类别无关，因”(c,：)1”(ck)”(c,：)2”(ck)M)”(ck)这样我们可以给出最大后验估计值：(3一12)而将其视为一常数。由此可以给出P(d|c)的最k终形式：P(G*D)=flk=1cI(k)IckDflm=1”(ck)(m)”(ck)(3一13)条件期望估计(3-8)P(dIC)=p(dI0(k)=flp(tI0(k)nmkmm=1=flM(0(k)mm=1这样基于这一模型，潜在的划分方案G*的后验概率可以表示为：P(G*|D)=flflIP(屮)flM(0(k)Ikmk=1dgc上m=1丿(3一

20、9)=flp(t)IckIflfl(0(k)”md)kmk=1dgcm=1k式中Ic丨表示类别c中的文档个数。其中隐kk含有约束条件0(k)=1，且10(k)0和mmm=1P(t)=1。kk=1模型参数的学习上式中先验概率P(t)和文档类的特征词k分布矢量0(k)都是从文档全集中获得的，是未知参数，需要从样本数据D中进行估计。为了书写简便，我们记参数b=p(t)，kkb=(b,b,Q)，后验概率改写为：12KP(G*D)=flKbckflflM(0(k)”m(d)(3一10)kmk=1dgcm=1k和混合模型中处理似然函数的做法相似，此处对于未知参数的处理也可以采用两种不同的策略：采用点估计，

21、可以采用贝叶斯方法中的最大后验估计来学习参数。参数随机化方法，实际上就是贝叶斯方法中的条件期望估计。最大后验估计从b,0,0的意义上看它们之间在文档全1k集D中没有必然的联系，我们假设这K+1组参数矢量间相互独立。这样可以给出各个参数的最大后验估计：在贝叶斯决策中条件期望估计是损失函数为平方损失时，使损失为最小的估计方式。由于平方损失是最常用的损失函数，条件期望估计在贝叶斯估计中有特殊的地位9。P(0,G*ID)对参数集0的条件期望为：P(G*ID)=fP(0,G*ID)兀(0)d0(3-14)类似最大后验估计的做法，可以假设这K+1组参数矢量间相互独立。于是参数的先验密度函数有如下的形式：兀

22、(0)=n(b)fln(0(k)(3一15)k=1相应的条件期望估计可以表示为：P(G*D)=fflKkk=1(3一16)flKfflM(0(k)”m(ck)n(0(k)c)d0(k)mkk=1m=1为先验分布n(b)、n(0(k)Ic)选择适当的分k布族，可以采用共轭分布法。共轭分布使得参数的先验与后验属于相同的类型，使得经验知识与样本提供的信息信息保持了某种一致性。如果我们用过去的知识和现有的样本提供的信息作为历史知识，也就是以这里的后验分布P(0,G*D)n(0)，作为下一步实验的先验知识，那么在新的数据下，我们得到新的后验分布仍然可以保持相同的类型。我们得到共轭分布为狄利克雷分布。显然

23、共轭分布使得参数的后验分布总能够保持相同的类型。这里我们选择狄利克雷分步的密度函数作为先验密度：Kb=1n(b)=邙0)fl其中k=(3-17)flr(卩k)k=卩k=pok=1k=1一r(a(k)时一l兀(o(k)ic)=0(o(k)a*-1kMmnr(a(k)m二1mm-1(3-18)艺0(k)-1其中m-1m艺a(k)-a(k)m0m-1其中b,a(k)为超参数。这样我们得到潜km在分类方案在给定数据下后验概率的条件期望估计如下式。nr(|c|+b)r(B)kk0k-1nKr(B)r(|D|+B0)kk-1nr(n(ck)+a(k)r(a(k)mm0m-1nr(a(k)r(n(ck*+a

24、0k*)mm-14.基于后验模型的层次聚类算法+log将层次聚类算法与模型选择相结合在许多领域都取得了成功11,12。一方面层次聚类限制搜索范围，在速度与准确度之间找到了较好的折衷；另一方面在层次聚类的局部目标函数中使用对数似然比(或贝叶斯因子)，消去一些项后，可以大幅度降低后验概率的计算量。对于我们的后验模型，由于前面给出了两种不同的参数估计方法，这里将在层次聚类的框架内分别对局部目标函数进行优化。采用最大后验估计的层次聚类算法层次聚类中的每一步是基于前一步的选择进行局部优化。第k步的分类方案Q和第k+1k步的分类方案Q之间显然有函数关系k+1Q-Q-c,c+coc存在。当算法执行到k+1k

25、xyxyk+1步时前一步分类方案为Q-c,c,c，k12|D|-k相应的后验概率P(QID)是已经确定的常数，显k然有：argmaxP(Qk+1Qk+1ID)-argmaxlogQk+1P(QID)k(4-1)化简后得到局部目标函数为：(c,c)-xyargmaxIcIlog(IcI)-IcIlog(IcI)-IcIlog(IcI)zzxxyyc,cxy+(n匕)logf匕)-n(cx*logf匕)-n(cy*logf(cy*)mmmmmmm-1(4-2)其中c=cuc，f表示特征词t在整个类别中zxymm的出现频率。为了引用方便，此算法在后面的讨论中被称作MSBP(ModelSelectio

26、nBasedalgorithmwithmaximumPosterior)采用条件期望估计的层次聚类算法类似前面的做法，局部目标函数为：(3-19)12IDI-k1log+logr(M)IDIk1-r(IcI+1)+log(cm,cn)ir(IcI+1)r(IcI+1)mn(c,c)-argmaxmr(M+n(cm)r(M+n(J)(4-3)r(M+n(cl)+lognr(1+n(ci)j-1r(1+njUr(1+njU其中c-cuc。上式中前两项对于聚类过lmn程每一阶段的局部优化函数而言是常数(因为k是常数)，实际计算中可以忽略。由于超参数的选择对结果没有显著的影响，在式中我们选择了统一的超

27、参数以简化计算：令aB都为1，相应的a-M，ij0B0k+1-IDI-k-1，B0k-IDI-k上式在实际计算过程中需要计算大量的形如logn!的项。为了提高算法的速度，在计算较大的n时(大于1000)，我们采用了stirling近似公式，取对数后为：lnn!-丄ln2兀+(n+丄)lnn一n(4-4)22为了引用方便，此算法在后面的讨论中被称作MSBE(ModelSelectionBasedalgorithmwithconditionalExpectation)算法复杂度分析n个对象进行层次聚类的平均复杂度为O(n2),最坏复杂度为O(n3)。考虑到特征的因素，在m个特征词构成的空间中，对n

28、个文档特征矢量进行聚类的平均复杂度为O(n2m)，最坏复杂度为O(n3m)。两个算法有相同的复杂度，条件期望估计中每一步的计算量较大，且涉及更多的对数运算，在实际测试中采用最大后验估计的算法处理相同的数据使用的时间要少许多。5.试验比较方案设计我们选用的测试数据是一组体育方面的文章,六个类别共计485篇中文文章,是通过spider从FM365网站上搜集的。经过切词处理，去掉停用词(stopwords)后保留了2719个特征词。足球篮球排球乒乓球网球棋牌篇数12010077416384表5-1衡量传统信息检索系统的性能参数召回率(Recall)和精度(Precision)也是衡量分类算法效果的常

29、用指标。然而聚类的过程中并不存在自动分类类别与手工分类类别确定的一一对应关系，因而无法像分类一样直接以精度和召回率作为评价标准。为此本文选择了文献13中的平均准确率(AveragedAccuracy,AA)作为评价的标准。平均准确率通过考察任意两篇文章之间类属关系是否一致来评价聚类的效果。任意两篇文章之间的关系，按照手工分类的标准和自动聚类的标准可以有以下四种情况：两篇文档之间关系属于同类类是否自动聚类中是AB否CD表5-2平均准确率定义为积极准确率(PositiveAccuracy,PA)与消极准确率(negativeaccuracy,NA)的算术平均值，即：PA+NAAA二2积极准确率PA

30、定义为：a(5-1)(5-2)PA二消极准确率NA定义为：NA一(5-3)b+d结果分析为了考察算法的效果，我们用K-means，Wardsmethod，著名的混合模型的模型选择算法AutoClass10，和一种采用非混合模型模型选择的层次聚类算法HBC(HierarchicalBayesianClustering)13，与本文提出的两种算法(MSBP,MSBE)共同作了测试(K-means,Wardsmethod使用SPSSv10.0进行的测试)。使用K-means算法聚类，聚类目标为6时最大的类别包括了446篇文章，准确率为53.28%。使用Wardsmethod进行聚类，准确率最高为61

31、.41%。AutoClass由于降文档划分为了20个类别，准确率也不高。所以我们只与HBC算法作进一步对比。下图显示了三种算法在聚类过程中平均准确的变化过程。0.9)vcarucQAe身r确准均平体育类文章聚类准确率变化(局部)0.80.70.60.5460464468472476480484聚类步骤图5-1聚类准确率随聚类过程的变化(局部)明显的HBC、MSBP和MSBE的准确率依次提高，显示出了极好的适应性。分为六个类别时MSBE算法准确率相对HBC算法提高了7.6个百分点，而MSBE算法更有11.9个百分点的改进，这是相当令人满意的结果。采用条件期望估计的算法如我们所预期的那样比采用最大

32、后验估计的算法效果更好。对其他不同数据的测试显示，样本集合越小，这一差距越明显。这也表明了条件期望估计有较好的稳健性。注意到区间460,475步上，MSBE算法有一段相对平坦的区域取得了较高的准确率，在对其它数据的测试中也存在类似现象。这一特性意味着算法对聚类目标的分类数不敏感，在聚类目标类别数难以判断的情况下，具有很大的实用价值。即使应用程序选择的分类数不太合理，聚类结果对应用仍具有较好的指导意义。6.结论在本文介绍的贝叶斯后验模型中，我们将参与模型选择的分类方案严格限制在0、1型的分类方案中，即文章要么完全属于某个类别，要么不属于，不存在中间状态。更普遍的情况是文章以不同的隶属度属于多个类

33、别，可以按照隶属度最大的类别进行分类。这样做的问题是会使模型的搜索范围变为无限大（采用连续概率矢量描述隶属度），成倍增加参数的数目，使数学处理非常的困难甚至是不可能的。如何在准确率与数学近似和计算复杂度之间寻找一个平衡点，是今后采用模型选择的聚类算法所面临的关键问题。7.参考文献H.H.Bock,ProbabilisticModelsinClusterAnalysis,ComputationalStatisticsandDataAnalysis,1996,23,pp.528ChrisFraleyandAdrianE.Raftery,Model-BasedClustering,Discrimin

34、ateAnalysis,andDensityEstimation,TechnicalReportNO.380,DepartmentofStatistics,UniversityofWashington,October2000PetriT.Kontkanen,PetriJ.MyllymakiandHenryR.Tirri,ComparingBayesianModelClassSelectionCriteriabyDiscreteFiniteMixtures,Information,作者简介StatisticsandInductioninScience(ProceedingsoftheISIS96ConferenceinMelbourne,Australia,August1996),1996,pp.364374AnIntroductiontoClusterAnalysisforDataMining，from HYPERLINK /classes/Spring-2000/csci5980-d /classes/Spring-2000/csci5980-dm/cluster-survey.pdf5高等数理统计，超星图书馆，pp.442444JeffA.B