作者：张毅
随着互联网的普及，论坛、微博、微信等新媒体已经成为人们获取和发布信息的重要渠道，而网络中的这些文本数据，由于文本数目和内容的不确定性，给网络舆情聚类分析工作带来了很大的挑战。非参数贝叶斯模型为我们提供了一种很好的解决方法，它是一种定义在无限维参数空间上的贝叶斯模型，由于参数的维数可以根据数据集的大小自适应调整，因此不需要事先确定聚类数目。本文中介绍的狄利克雷过程( Dirichlet process，DP)就是一种非常流行的非参数贝叶斯模型，近年来广泛应用在贝叶斯模型验证、密度估计和基于混合模型的聚类等领域。
由于狄利克雷过程混合模型( Dirichlet process mixturemodel，DPMM)的提出，使得狄利克雷过程的应用得到了长足的发展。Andreas等人将DPMM用于自然语言处理中的基于语义的动词聚类上面，利用成对约束这一特性，指导DPMM将动词聚到指定的类别中。Fox等人利用DPMM的聚类性质，结合数据中的关联特性，在目标跟踪上面实现了目标数量的确定。Zhang等人将DPMM过程混合模型应用在多元有监督学习的回归问题上，通过MCMC采样，得到了良好的统计学和计算效果。
基于以上工作，本文提出了基于DPMM的文本聚类模型，该模型使用狄利克雷过程中的中国餐馆过程( Chineserestaurant process，CRP)构造方式，结合多项式分布与狄利克雷分布共轭的特性，实现了基于中国餐馆过程的狄利克雷过程混合模型，然后利用吉布斯采样算法对模型近似求解。实验发现，该模型能够有效解决自动确定聚类数目这一问题，而且在聚类过程中可以利用类簇中聚类一词语的多项式分布来计算每个词语在相应类簇下出现的概率，然后利用每个类簇下面概率排名比较高的词语去表示这个类簇。在本文提出的文本聚类模型中，每个类簇可以当做一个主题，可以在聚类的同时去发现数据集中的主题数目和主题内容。
1狄利克雷过程及其构造方式
1.1狄利克雷过程的定义
狄利克雷过程是一种基于非参数贝叶斯模型的随机过程，它是由Ferguson于1973年提出。狄利克雷过程的定义如下。
假设Go是测度空间上的随机概率分布，参数ao是一个正实数。对于测度空间@的任意有限划分A1…，Ar，如果存在如下的关系：
那么G服从由基分布Go和集中参数ao组成的狄利克雷过程，即G:DP(ao，Go)。对于测度空间O中的任意子集Ak，我们可以得到：
因为狄利克雷分布和多项式分布具有共轭的特性，所以如果G:DP(ao，Go)并且观测值θ1…，θn：G服从多项式分布，则狄利克雷过程对测度空间@有限划分后的后验分布也服从狄利克雷过程，即：
由于G是测度空间0上的概率分布，观测值θi同样是在测度空间@中取值，所以这里的nk=≠#{i:θi∈Ak}，表示观测值θi属于Ak的数目。由公式(3)可以看出，任意狄利克雷过程的先验分布的后验分布依然服从狄利克雷过程，即
其中δ（θ=θi)是狄拉克函数，当且仅当θ=θi时函数值等于1，其他情况都等于O。
1.2 CRP的构造
按照上面对狄利克雷过程的定义，无法实现对狄利克雷过程的采样，在实际应用中往往采用其他构造方式，包括截棍构造方式( Stick-breaking construction)、Polya罐子模型( Polya urn scheme)构造方式以及中国餐馆过程(CRP)构造方式，本文将采用CRP来对狄利克雷过程进行构造：CRP利用了一个隐喻：假设有一个餐馆，可以容纳无数张桌子，每张桌子（相当于聚类组）分配参数p1…，pk:Go，pk表示第k张桌子的参数，我们分配桌子给每一个顾客（相当于数据点）Zl，…,zn：crp (ao)，指示变量Zi表示分配给第i位顾客的桌子。每位新到的顾客可以坐在已有颐客的桌子或者新开一张桌子。具体算法的流程如下：
1)初始化一个空的餐馆；
2)第一个人进入餐馆，选择一张桌子坐下，然后点菜，其他坐在这张桌子上的人共享该道菜；
3)第二个人进入餐馆，以概率可
选择一张新的桌子，然后点菜，或者以概率
选择和第一个人共享同一张桌子（相当于进入相同的组）；
4)第n+l个人进入餐馆，以p(zn+1=k|Z1:n)=
的概率坐到第k张桌子，或者以a|…0的概率新开一张桌子，nk表示第k张桌子的顾客数目。
图1给出了CRP的构造过程。
由上面的描述可知，越多的顾客坐某一张桌子，那么下一个顾客选择这张桌子的概率越大，说明CRP具有很好的聚类性质。其次，参数ao的值越大，那么顾客选择新桌子的概率也就越大，这说明ao能够控制聚类数目的大小。
2狄利克雷过程混合模型( DPMM)与基于狄利克雷过程混合模型的文本聚类算法( DCA-DPMM)
2.1狄利克雷过程混合模型
从上面的描述中可以看出，狄利克雷过程具有良好的聚类性质。但是狄利克雷过程只能实现具有相同值的数据聚类，无法进行数据之间相似性很大但值不同的聚类。针对这个问题，研究者在狄利克雷过程的基础上，提出了狄利克雷过程混合模型。不同于有限混合模型，狄利克雷过程混合模型可以看作是具有无限分布分量的无限混合模型，是具有狄利克雷过程先验假设的有限混合模型的极限形式。这使得在对数据进行建模时，聚类的数
目可以动态调整。狄利克雷过程混合模型的定义可以表述为以下形式：
观测值θi服从参数为F(θi）的分布，参数θi服从概率测度G，而G则可以通过狄利克雷过程构造。θi既可以是单个参数，也可以是多个参数构成的向量，如果两个观测值xi和xi服从混合分布中的同一个分布，那么它们的分布变量相同，即θi=θio狄利克雷过程混合模型可以用如图2所示的图模型表示。
2.2 DCA-DPMM聚类算法
本文采用CRP构造的狄利克雷过程混合模型进行文本聚类，该模型需要分别对文本集中的聚类以及每个聚类中的词语进行建模。基于CRP的狄利克雷过程混合模型定义如下：
每个聚类（主题）z被表示成一个在词典上的多项式分布0：。每个文档xi对应聚类（主题）都有一个特定的多项式分布。一个文档的生成过程如下：
1)采样p：Dir(ao)；
2)对于文档xi，本文采取以下方法：
(1)采样一个类别标签ZI：Mult(PI,)；
(2)生成文档XI中的每一个词Xi:0z。
文档的生成过程采用概率图模型表示，如图3所示。
该模型使用多项式分布作为生成分布，使用狄利克雷分布作为它的先验分布。e表示活跃的聚类数目，n表示文本数目。
在DCA-DPMM聚类算法中，每个文本分配给一个聚类，即每个文本属于一个话题．同一类簇中的听有文本都属于同一个话题，那么第二个话题中第i个词语出现的概率θzj为：
关于狄利克雷过程混合模型中隐变量的推断问题，本文使用了坍塌的吉布斯采样算法，它是蒙特卡罗采样算法的一种变形，具有简单高效的特点。由于观测数据之间能够相互交换，可以把观测数据xi当作最后一个观测值。指示变量zi的后验分布为：
其中Z-I表示第i个观测数据xI外其他所有观测数据的指示变量。上面的推导过程利用了贝叶斯规则，公式(12)右边的第一项是先验，可以用狄利克雷过程中的CRP来表示：
公式( 12)右侧的第二项是似然函数，如果指示因子zIi值k在已有的类别当中，那么：
如果指示变量是新的聚类，那么：
结合上面吉布斯采样的公式，可以得出基于DPMM文本聚类算法( DCA-DPMM)的流程如下：
3实验结果与分析
为了对本文提出的聚类算法的有效性进行评估，本文使用复旦大学标准语料库进行聚类分析。常用的聚类有效性评估方法主要有外部评价法和内部评价法，外部评估方法主要是比较聚类算法对数据集的分类结果和已知分类的相似程度，本文使用聚类纯度( Purity)以及F-score作为外部评估聚类算法的指标，内部评估方法主要通过判断类间的疏离程度和类内的紧密程度来评估一个聚类算法的有效性，文本使用轮廓系数( silhouette coefficient)怍为内部评估聚类算法的有效性的指标。
3.1评估指标
1)聚类纯度
为了计算纯度，本文算出每个类别i中被正确分配的文本数，然后将各个类别的文本数累加，再除以文本总数，即可得到聚类纯度，计算公式如下：
其中Ni表示文本数目，K表示聚类数目，Ci表示类别k中最具代表性的类别的文本数目。
2) F-measure指标
F-measure综合了文本检索中的查准率(precision)和查全率( r-ecall)这两种评价指标，对于一个聚类i和一个事实类别j的查准率和查全率的定义如下：
其中N1表示在聚类i中属于事实类别i的数目，N2为聚类i中所有文本的数目，N3为事实类别j中所有文本的数目。文本采用的F-measure是查准率和查全率的调和平均值，也被称为F1值，F1值的定义如下：
假设把具有n个文本的数据集X划分成k个聚类C1，C2…,，Ck，对于类簇中的每一个文本x∈X，a(x)表示数据点x和x所在类簇其他数据点之间的平均距离，b(x)表示数据点x和所有x不属于的类簇之间的最小平均距离。假设x∈Ci（1≤i≤k），那么a(x)和b(x)分别表示为：
数据点z的轮廓系数的定义如下：
x的轮廓系数取值区间是[-1,1]，越靠近+1，说明类间距越大，类内紧密程度越好，聚类的质量越好。本文计算所有数据点的平均轮廓系数。
3.2实验结果与分析
本文采用的实验数据集是复旦大学中文语料库，本文将其分为三个子数据集，每个子数据集有10个类别，表1展示了实验数据集。如表1所示，预处理时只保留文档中的动词和名词，在使用K-means聚类算法时，手动设定K-means的聚类数目为10，用TF-IDF对文本向量化，在使用DCA-DPMM聚类算法时，分别设置ao=l.0，β=1.0和K=50。表2展示了DCA-DPMM聚类算法和K-means聚类算法在对数据集进行聚类后的纯度对比，从表2中可以看出，无论在哪个测试数据集上，本文提出的算法在纯度上都要略好于经典的K-means算法，两种聚类算法在数据集1上的纯度略差，原因是在数据集1上部分类簇的相似度很大，如文学、历史、艺术这三个类簇，文本的特征向量相似度很高，在聚类时没有将它们很好地划分开。表3展示了DCA-DPMM聚类算法和K-means聚类算法在对数据集进行聚类后的F1值对比，F．值是查全率和查准率的加权调和平均，F1值越高说明聚类算法越有效，从表3中可以看出，本文提出的文本聚类算法F1值要好于K-means聚类算法。
在使用轮廓系数评估DCA-DPMM聚类算法的有效性时，本文首先用DCA-DPMM聚类算法对数据集聚类，得到聚类数目K后，设定K-means的聚类数目为K1为了验证DCA-DPMM聚类算法的聚类数目的有效性，K-means的聚类数目在K值的__KF浮动，分别计算出轮廓系数。在数据集1上的实验结果如图4所示。
从图4中可以看出，DCA-DPMM聚类算法在数据集1上确定的聚类数目为7，此时的轮廓系数为- 0.17；而当K-means聚类算法的聚类数目为7时，轮廓系数为- 0.19，在聚类数目相同时，本文提出的文本聚类算法在类内的紧密程度和类间的疏离程度要略优于K-means聚类算法。为了验证本文提出的文本聚类算法的有效性，设定K-means聚类算法的聚类数目在7上下浮动，从图4中可以看到，K-means算法的聚类质量都略差于聚类数目为7的情况，
这说明本文提出的文本聚类算法能够有效确定聚类数目，在数据集2上得到的轮廓系数与在数据集l的结果相似，如图5所示。
在DCA-DPMM聚类算法中，同一个类簇下面的词语能够表示成主题一单词多项式分布，通过公式( 12)可以计算出同一主题下词语出现的概率，表4列举了数据集1中部分话题的高频（按出现概率排名）词语。从表4中可以看出，通过若干个高频词语即可表示出话题内容。
4结束语
本文基于狄利克雷过程混合模型实现了对文本的主题聚类，狄利克雷过程是一种非参数贝叶斯框架，它的构造方式CRP具有良好的聚类性质。利用这一性质，本文构造了基于中国餐馆过程的狄利克雷过程混合模型，并利用吉布斯采样算法来近似求解该模型。实验结果表明该聚类算法不仅可以动态确定聚类数目，而且在聚类的有效性上优于经典的K-means聚类算法。
本文中控制聚类数目的先验参数ao只是选择了经验值，但是它的大小会影响到混合分量的数目，可以给先验参数ao分配一个先验伽马分布，然后在吉布斯采样过程后验推断ao。在DCA-DPMM聚类算法中，每个文档只属于一个主题，但在话题模型中，如Latent Dirichlet Allcation( LDA)中，每个文档服从关于话题的多项式分布。下一步研究可以让随机过程G服从一个先验狄利克雷过程分布，这样便可以实现多文档之间的主题共享。
5摘要：
随着互联网的普及，论坛、微博、微信等新媒体已经成为人们获取和发布信息的重要渠道，而网络中的这些文本数据，由于文本数目和内容的不确定性，给网络舆情聚类分析工作带来了很大的挑战。在文本聚类分析中，选择合适的聚类数目一直是一个难点。文章提出了一种基于狄利克雷过程混合模型的文本聚类算法，该算法基于非参数贝叶斯框架，可以将有限混合模型扩展成无限混合分量的混合模型，使用狄利克雷过程中的中国餐馆过程构造方式，实现了基于中国餐馆过程的狄利克雷混合模型，然后采用吉布斯采样算法近似求解模型，能够在不断的迭代过程中确定文本的聚类数目。实验结果表明，文章提出的聚类算法，和经典的K-means聚类算法相比，不仅能更好的动态确定文本主题聚类数目，而且该算法的聚类质量（纯度、F-score和轮廓系数）明显好于K-means聚类算法。
