基于LDA模型和AP聚类的主题演化分析

倪丽萍，刘小军，马驰宇

(1.合肥工业大学 管理学院，安徽 合肥 230009；2.教育部过程优化与智能决策重点实验室，安徽 合肥 230009)

基于LDA模型和AP聚类的主题演化分析

倪丽萍1,2，刘小军1,2，马驰宇1,2

(1.合肥工业大学 管理学院，安徽 合肥 230009；2.教育部过程优化与智能决策重点实验室，安徽 合肥 230009)

随着互联网的高速发展，网络信息呈现爆炸性增长态势，主题演化分析能够帮助人们从海量的互联网数据中获取更有价值的信息。分析主题的演化发展轨迹有利于人们了解主题事件发生的前因后果，并对主题事件发展趋势进行更好地预测，进而辅助管控。针对单个主题演化分析方法中阈值设定和主题漂移的问题，提出一种LDA-AP主题演化模型。该方法利用LDA模型对不同时间窗口内的新闻文本分别进行建模，得到相应的主题。利用AP聚类算法对不同时间窗口内的多个主题进行聚类，其中计算主题相似度采用加入时间衰减因子的JS散度来度量。最后对多个主题内容进行演化分析。通过相关的实验分析和对比，结果表明该方法可以改善主题演化的性能，并能较好地分析多个新闻主题事件随时间的演化趋势。

多主题演化；时间窗口；LDA模型；AP聚类算法；JS散度

0 引 言

随着互联网的发展，社会化媒体如网络新闻、微博等已成为发布事件的主要载体，有效挖掘和分析其中的事件信息有利于帮助用户及时掌握事件动态，了解事件趋势。因此，从社会事件发生和传播中有效地挖掘和分析网络中的事件信息，具有重大的理论意义和实际价值。

美国国防高级计划研究署(DARPA)于1996年提出了话题的检测与追踪(TDT)研究。Allan J等[1]将TDT技术应用到网络新闻报道流的划分，并且根据需要不断建立新的话题类，这是一种无监督的增量聚类方法。针对TDT技术新闻报道中只存在单个话题的假设，并且没有考虑时间因素的问题，国内外研究学者提出了大量的改进方法。Wang等提出了TOT(Topic Over Time)模型[2]，将时间信息加入到可观测的变量中，使得词的生成不仅受到主题限制，还受时间属性的影响。这种模型在不同时间窗口上的主题强度演化方面取得了较好的结果，但是TOT模型没有考虑到主题内容在时间窗口上的演化。随后Al-Sumait等提出OLDA(Online Latent Dirichlet Allocation)模型[3]，该模型使用演化矩阵来记录以前的模型结果，而演化矩阵能够记录主题的变化，并且通过计算连续时间窗口内主题的相对熵来表现话题内容上的变化，但是OLDA容易导致主题混合和主题边界模糊。Elshamy等提出了ciDTM(continuous-time infinite Dynamic Topic Models)模型[4]，该模型提出在连续时间序列上的可变主题数和可变主题结构的主题演化模型，解决了OHDP(Online-Hierarchical Dirichlet Process)只依赖文档到达顺序而不能通过文档时间戳进行建模的缺点。

国内学者近年来在主题演化方面的研究也取得了一定的进展。胡艳丽等定义了子话题的产生、消亡、继承、分裂和合并，并对不同模型的困惑度进行了对比分析[5]。单斌等将基于LDA的话题演化技术分为三种:直接把时间作为观测变量引入模型、按时间后离散和先离散方法[6]。李保利等提出过滤无意义话题，避免无意义话题对主题演化产生负面影响，并借助启发式规则从主题强度和内容进行分析，研究科技文献随时间的演化趋势[7]。

综上，上述研究方法存在以下不足：通常是对单一事件演化的检测，即上述方法往往根据主题词的概率进行相似度关联，因此通常都是对单个主题的演化分析；在相似度判断上往往需要设定阈值。

针对以上问题，文中将聚类思想引入LDA主题模型演化中，并以新闻文本为实验材料，阐述了如何使用LDA模型和AP聚类算法对新闻文本主题特征演化进行分析。

1 基于LDA-AP的主题演化模型构建

随着事件的动态发展，事件主题的内容往往会发生迁移，如何描述多个主题的演化关系以及内容变化是目前的研究热点。潜在狄利克雷分布(Latent Dirichlet Allocation，LDA)模型本身具有主题建模能力，在主题演化方面具有先天优势。基于LDA模型和AP聚类的主题演化模型的基本思想是：首先通过LDA模型从不同时间窗口内的大量新闻数据中获取抽象的主题信息，再利用AP聚类算法对不同新闻主题发表时间窗口中提取的特征词汇构建关联。其中用JS散度对新闻主题内容相似度进行衡量，利用AP算法将相似度大的新闻聚为同一簇主题，并利用主题强度的衰减性连续性地在不同时间窗口中分析主题的强度变化和主题内容的覆盖情况。最后通过实验验证方法的有效性。

1.1 基本框架

(1)把新闻文本集Dm按时间窗口t划分为多个子文本集DSi(i=1,2,…,T)；

(2)基于Gibbs抽样对DSi求LDA模型参数，确定每个时间窗口的主题个数和主题-词概率；

(3)利用AP聚类算法建立主题关联，使用JS散度度量不同时间窗口间的主题距离，并加入衰减因子；

(4)根据聚类结果，分析主题的强度变化及内容演化的过程；

(5)利用TDT评测方法对文中方法和基准方法的主题演化结果进行评测。

文中时间窗口t设置为1天，在每个时间窗口内进行LDA主题建模，然后按照时间顺序把时间窗口的主题进行关联分析。基于LDA和AP聚类算法的主题演化步骤如图1所示。

图1 主题演化检测框架

1.2 LDA主题模型

LDA模型由Blei等在2003年首次提出，基本思想是将每一篇文档看作为一些相互关联的话题所构成的概率分布，而将每一个话题看作为一些单词所构成的概率分布，使用隐含的话题将文本与词进行相互关联，从而使文本从高维的词汇空间降到低维的话题空间，解决了传统的向量空间模型的维数灾难问题[8]。

令k表示主题数目，M表示文档数目，Nm表示第m个文档的单词数目。LDA模型生成文档的过程如下:

(1)对于每个主题j，根据Ψ～Dir(β)采样得到主题j上的单词多项式分布向量Ψj。

(2)对于语料库中第m个文档dm，根据N～Poisson(ξ)分布，得到文档的单词数目N，根据θ～Dir(α)分布，得到文档的主题分布概率θ。

(3)对于文档dm中的第n个词:

①多项式分布Zn～Multinomial(θ)中选择一个潜在主题Z=k;

②根据多项式条件概率分布p(Wn|Zn;β)生成一个单词Wm,n。

对于给定的模型参数α、β，文档d随机变量θ，z和w的联合分布表示为：

(1)

其中，α、β是固定参数，α反映语料库中潜在主题的相对强弱，β刻画所有潜在主题词的概率分布；超参数θm和ψk分别表示文档-主题分布和主题-词分布；wm,n表示观测到的文档的词向量。

LDA中参数推断方法主要有两类：变分贝叶斯推理方法和Gibbs抽样方法。对于联合分布维度较高的情况，使用Gibbs抽样简单且更容易实现，并且Griffiths指出Gibbs抽样在困惑度与运行速度等方面均优于变分贝叶斯推理算法，成为主题模型中最常用的参数估计方法[9]。

1.3 AP聚类算法

仿射传播聚类算法(Affinity Propagation,AP)是Frey等于2007年提出的。其基本思想是首先将每个点作为潜在的聚类中心，然后通过更新迭代每个点的吸引度和归属度产生最终的聚类中心，最后将其余的点分派到聚类中心形成最终的聚类结果[10]。

假设m维空间上的数据集D包含n个数据点，即D={X1,X2,…,Xn}。则在AP算法中n个点的吸引度和归属度可以定义为n*n矩阵。其中，吸引度矩阵R中的元素r(i,k)表示由点xi发送到候选聚类中心点xk的消息，即元素值的大小说明点xk适合作为点xi的聚类中心的程度；归属度矩阵A中的元素a(i,k)是由候选聚类中心点xk发送到点xi的消息，即元素值大小表示点xi选择xk作为聚类中心的程度。r(i,k)越大说明xk作为聚类中心的可能性越大，a(i,k)越大说明点xi选择点xk作为其聚类中心的可能性越大。通过吸引度和归属度的不断更新迭代最终产生聚类中心。R和A的更新公式分别表示为：

(2)

(3)

其中，S是初始的相似性矩阵；s(i,k)是xi和xk间的相似度，通常可以用距离来度量。

以欧氏距离为例，相似度可以定义为：

s(i,k)=-‖xi-xk‖2,i≠k

(4)

式(4)说明xi和xk的距离越小两者的相似性程度越高。s(i,i)取p时，反映了点i作为聚类中心的偏好。一般由用户自定义，可以选择样本相似度的最大值、最小值或均值。

由于AP算法在聚类过程中容易产生震荡，因此在R和A进行下一次迭代之前需要对其进行缩放。缩放的方法是引入阻尼因子lam，具体如式(5)所示。

(5)

其中，lam为一设定的值；Rold和Aold表示上一次迭代的结果。

综上，AP聚类算法的过程为：

Step1：初始化相似度矩阵S、吸引度矩阵R和归属度矩阵A(R和A初始化为0)，以及偏好值P，阻尼因子lam。

Step2：设置最大迭代次数n，以及聚类中心稳定次数m。

Step3：迭代执行Rold=R，Aold=A；根据式(2)和式(3)计算R和A；根据式(4)对R和A进行缩放。

Step4：如果迭代次数大于n或者聚类中心稳定次数大于m时，则结束迭代操作，执行Step5。

Step5：当r(i,i)+a(i,i)>0时，选取该点作为聚类中心。

Step6：将剩下的数据点与聚类中心相比，并将它们分配到最近的聚类中心。

从上面的算法过程中可知，相似度矩阵S是AP算法的重要参数，文中如果相似度矩阵S能够准确地反映出主题之间的相似关系，则AP算法就能较好地发现主题的关联关系。

1.4 主题演化分析

主题演化可以从主题强度和主题内容两个方面来分析。其中主题强度是反映主题在时间轴上的活跃度变化情况；主题内容演化是指主题内容在时间轴上的演化趋势。

1.4.1 主题内容的演化分析方法

在之前的研究中，主题内容之间的相似性通常采用KL距离(Kullback-Leibler divergence)来度量，通过LDA可得到主题词的分布，KL距离可用来度量两个主题词分布的差异性。对于相邻时间片中主题z1和z2的主题分布p(wi|z1)和p(wi|z2)，KL距离定义为：

(6)

由于KL距离是不对称的，而具有演化关系的两个话题具有语义相关性，因此文中采用JS散度(Jensen-Shannon)作为AP聚类的相似度公式来判定不同时间窗口的新闻主题内容之间是否具有相关性。JS散度的计算公式为：

(7)

一般来讲主题报道会持续一段时间，所以两个主题之间的时间距离越小，它们属于同一事件的可能性越大；反之时间距离越大则两个主题属于同一事件的可能性越小。因此，文中在JS距离中引入时间衰减模型来设计聚类机制，定义一个衰减因子λ使主题概率的相似度随时间衰减，衰减因子定义为：

(8)

其中，Timez1和Timez2分别表示主题z1和z2的报道时间，当两个主题间隔的时间越长，λ值越小。

最终相似度计算公式为：

(9)

JS散度的区间为(0,1]，两个主题的JS散度越小，相似度就越大，关联的可能性也越大。即根据AP算法将相似的两个主题聚为一个簇，就判定不同时间窗口内的两个主题在内容上具有继承关系。如果一个时间窗口内的主题在下一个时间窗口没有相同的聚簇，则认为该主题事件在上一个时间窗口消亡。反之，如果一个时间窗口内的主题在上一个时间窗口没有相同聚簇，则判定该事件在这个时间窗口是新生事件。

1.4.2 主题强度的度量

(10)

其中，M表示新闻报道数。

根据θt计算每个时间窗口内文本中的主题强度值，绘制主题强度随时间的变化趋势图。

2 实验及结果分析

2.1 实验环境

实验是在CPU为Intel@Core(TM)i5-4590 3.30 GHz、内存为4 GB、操作系统为Windows 7旗舰版(Service Pack 1)的PC机上运行。

2.2 数据描述

文中使用的新闻数据抓取自新浪新闻、网易新闻、中国新闻网、人民网、凤凰资讯。抓取工具使用Python编写的网络爬虫程序，抓取了从2013年11月01日到2013年11月30日共计约30万条新闻正文内容，并将新闻语料库时间间隔设置为1天，划分到30个时间窗口。

2.3 实验设置

由于新闻文本数据字符集较大,词长较短的特点，采用Python的结巴分词；针对新闻实验语料库的特点，文中将哈工大停用词表进行扩充，加入一些新闻语料库特有的词，如“记者”“报道”等出现频率高且对实验结果没有意义的词语，通过去除这些停用词提高后续分析的准确性。

对新闻文本主题建模时，采用Gibbs抽样算法推导LDA后验参数ψk和θm。首先需确定LDA主题模型中3个变量(Dirichlet分布中的超参数α、β及主题数目T)的最佳值。相关文献表明β=0.01时实验效果较好，α=50/T[12]。根据困惑度确定最优主题数，实验表明当主题数设为10时困惑度值最小，因此每个时间窗口最优主题数目为10，同时设定每个主题下关键词的提取个数为10。

2.4 主题内容聚类演化结果与分析

根据图1的主题演化基本框架进行计算，可得到如表1所示的主题演化结果。限于篇幅，此处仅列举11月9日到11月12日的部分活跃主题，其中活跃主题中的主题词概率从大到小依次输出，并选取每个主题包含的概率排在Top8的关键词作为主题的代表。

表1 新闻主题演化结果

2.5 主题强度的结果与分析

通过LDA模型可以获得不同时间窗口中新闻主题的主题-词汇概率分布以及主题在不同文档上的概率分布，从而分析主题强度随时间的演化情况。以主题“恒大俱乐部夺冠”、“淘宝双十一购物节”、“台风海燕”为例，按照1.4.2节中主题强度的计算方法分析其2013年11月的演化情况，如图2所示。

图2 主题强度演化图

图中展现了主题强度随时间的变化趋势。从图中可以看到，恒大夺冠的主题是在11月份一直存在，而在11月9日恒大俱乐部夺冠后出现顶峰，在夺冠后强度缓慢减弱但没有消亡，说明恒大俱乐部在11月份不断被关注。双11购物节每年在固定时间发生，持续时间较短，从图2中可以看到“淘宝双11购物节”在11月10日和11日比较热门，在11月12日之后迅速减弱，持续时间较短。而台风“海燕”在11月8日之前基本没有报道，而在11月8日台风海燕登陆菲律宾后才突然出现报道，之后再在11月11日登陆广西，在11月14日出现的只有菲律宾，慢慢减弱。从图中不难发现，恒大俱乐部属于持续较长的事件，而双11购物属于定点时间出现高峰并迅速减弱的事件，而台风海燕属于突发事件，这与上述分析的主题内容演化趋势也是基本吻合的。

2.6 演化结果评价方法

为了测试文中提出的分析方法的有效性，将LDA-AP模型(称“LDA-AP-衰减”方法)与Baseline方法进行对比。其中Baseline方法采用LDA进行主题建模，用KL距离进行主题关联，距离阈值设为0.5，如果相邻时间窗口内的主题间距离小于0.5，就认为存在演化关系。测评方法采用了TDT的评测方法，即漏报率Pmiss、误报率Pfa以及归一化追踪代价开销(Cdet)norm三个性能指标。计算公式分别为[13-14]：

(11)

(12)

(Cdet)norm=

(13)

其中，a为关联的相关新闻主题数；b为关联的不相关新闻主题数；c为未关联的相关新闻主题数；d为未关联的不相关新闻主题数；Cmiss、Ptarget、Cfa、Pnontarget都是预先设定好的值，设定为1.0、0.02、0.1、0.98[13-14]；(Cdet)norm作为评测系统性能的指标，值越小说明系统性能越好。

为了检验文中提出方法的有效性，对LDA的主题建模结果进行人工标注，根据上述评测方法，评测结果如图3所示。

图3 实验对比结果

从图3中可以看出，文中方法与Baseline方法相比，漏报率、误报率以及归一化开销都有了一定程度的降低，体现出一定的有效性。

以“淘宝双十一”主题为例，Baseline方法和文中算法演化内容见表2。

表2 “双十一购物节”的主题内容演化对比

从表2中可以看到，文中的LDA-AP-衰减方法和Baseline方法都是从11月8日开始检测到双十一购物主题事件，而Baseline方法在11月9日得到的主题演化结果中并没有关联到“淘宝双十一”的主题事件，而文中的LDA-AP-衰减方法在11月9日关联到了关于互联网购物方面的主题。可以看出11月9日也是议论关于互联网购物节的主题，只是出现“双十一”和“淘宝”关键词的概率较小，导致Baseline方法未能关联到，而文中方法通过AP聚类可以关联到Baseline方法没有进行关联的主题，反映出该方法在主题演化方面的有效性。

3 结束语

利用LDA模型抽取不同时间窗口的主题，提出结合JS散度和AP聚类算法对不同时间窗口上多个主题进行聚类从而进行主题关联演化的方法，改善了只能进行单个主题强度和内容的演化问题，并且避免了人工设定阈值造成的误差，同时加入时间衰减因子后有效地降低了主题演化的漏报率和误报率。但是文中提出的LDA-AP演化模型只考虑到主题随时间衰减问题，在考虑增量主题的变化上还有不足，因此下一步将考虑改进增量式聚类算法，使主题演化效果达到更好。

[1]AllanJ,PapkaR,LavrenkoV.On-lineneweventdetectionandtracking[C]//Proceedingsofthe21stannualinternationalACMSIGIRconferenceonresearchanddevelopmentininformationretrieval.[s.l.]:ACM,1998:37-45.

[2]WangX,McCallumA.Topicsovertime:anon-Markovcontinuous-timemodeloftopicaltrends[C]//Proceedingsofthe12thACMSIGKDDinternationalconferenceonknowledgediscoveryanddatamining.[s.l.]:ACM,2006:424-433.

[3]Al-SumaitL,BarbaráD,DomeniconiC.On-linelda:adaptivetopicmodelsforminingtextstreamswithapplicationstotopicdetectionandtracking[C]//2008eighthIEEEinternationalconferenceondatamining.[s.l.]:IEEE,2008:3-12.

[4]ElshamyW.Continuous-timeinfinitedynamictopicmodels[D].Manhattan:KansasStateUniversity,2013.

[5] 胡艳丽,白 亮,张维明.一种话题演化建模与分析方法[J].自动化学报,2012,38(10):1690-1697.

[6] 单 斌,李 芳.基于LDA话题演化研究方法综述[J].中文信息学报,2010,24(6):43-49.

[7] 李保利,杨 星.基于LDA模型和话题过滤的研究主题演化分析[J].小型微型计算机系统,2012,33(12):2738-2743.

[8]BleiM,NgAY,JordonMI.LatentDirichletallocation[J].JournalofMachineLearningResearch,2003(3):993-1022.

[9]GriffithsT.GibbssamplinginthegenerativemodeloflatentDirichletallocation[D].Stanford:StanfordUniversity,2002.

[10]FreyBJ,DueckD.Clusteringbypassingmessagesbetweendatapoints[J].Science,2007,315(5814):972-976.

[11] 李湘东,张 娇,袁 满.基于LDA模型的科技期刊主题演化研究[J].情报杂志,2014,33(7):115-121.

[12] 贺 亮,李 芳.基于话题模型的科技文献话题发现和趋势分析[J].中文信息学报,2012,26(2):109-115.

[13] 郑 燕,鲁 燃,赵爱华.基于反馈报道的话题模型动态修正方法[J].计算机应用,2012,32(5):1343-1346.[14] 魏景璇,鲁 燃,张艳辉.基于动态阈值和命名实体的双重过滤话题追踪[J].计算机应用研究,2015,32(4):982-985.

Topic Evolution Analysis Based on LDA Model and AP Clustering

NI Li-ping1,2,LIU Xiao-jun1,2,MA Chi-yu1,2

(1.School of Management,Hefei University of Technology,Hefei 230009,China;2.Key Laboratory of Process Optimization and Intelligent Decision Making,Hefei 230009,China)

With the rapid development of Internet,the network information presents explosive growth,and the topic evolution analysis can help people get more valuable information from the massive Internet data.Evolutionary trajectory analysis of the topic is helpful for people to understand the antecedents and consequences of the event and to better predict the development trend of theme events,assistance of control.Aiming at the problem of threshold setting and topic shift in the method of a single event evolution analysis,a new LDA-AP model is proposed.In this method,the LDA model is used to model the news texts in different time windows,and the topic of different time windows is obtained.Then the AP clustering algorithm is used to analyze the multiple topic in different time windows,in which topic similarity calculation using the JS divergence with attenuation factor to measure.Finally the evolution analysis of multiple topic is conducted.Through experimental comparison with the reference method,the results show that the proposed method can effectively improve the performance of the topic evolution,and the evolution trend of multiple news events with time is better analyzed.

multiple topic evolution;time window;LDA model;AP clustering algorithm;JS distance

2016-02-20

2016-05-25

时间：2016-11-22

国家自然科学青年基金(71301041，71271071)

倪丽萍(1981-),女,博士,副教授,研究方向为金融数据分析、数据挖掘、人工智能等；刘小军(1990-),男，硕士,研究方向为数据分析、软件工程等。

http://www.cnki.net/kcms/detail/61.1450.TP.20161122.1227.026.html

TP181

A

1673-629X(2016)12-0006-06

10.3969/j.issn.1673-629X.2016.12.002