DOI: 10.11817/j.issn.1672-7207.2015.02.024
基于改进的在线LDA模型的主题演化分析
何建云,陈兴蜀,杜敏,江浩
(四川大学 计算机学院,四川 成都,610065)
摘要:为了解决OLDA模型中的主题混合和新主题不能及时发现的问题,基于OLDA模型提出一种改进的在线LDA模型(improved online LDA,IOLDA)。该模型根据主题强度为每个主题设置不同的遗传度,提出一种新的主题强度度量方法,根据文档-主题分布的集中程度为文档设置不同的权值,该方法可以有效降低宽泛主题的强度得分;利用模型主题对齐的特点,采用Jensen-Shannon距离横向计算话题间的关联。实验结果表明:本文提出的方法能够有效地在线分析主题的演化。
关键词:主题演化;主题遗传;主题强度;LDA模型
中图分类号:TP391 文献标志码:A 文章编号:1672-7207(2015)02-0547-07
Topic evolution analysis based on improved online LDA model
HE Jianyun, CHEN Xingshu, DU Min, JIANG Hao
(College of Computer, Sichuan University, Chengdu 610065, China)
Abstract: To sove the problem of topic mixing and new topic untimely detection in the traditional OLDA, an improved online LDA(IOLDA) model was presented based on OLDA. The different heritability for each topic was set according to the topic intensity. Furthermore, a new method was introduced to evaluate topic intensity. By calculating a weight for each document according to the concentration of the mixture distribution over topics, this method can effectively reduce the score of broad topics. Since the model is able to align topics across the epochs, topic association can be captured easily via Jensen-Shannon Divergence. The results show that the proposed method is efficient for analyzing topic evolution online.
Key words: topic evolution; topic genetic; topic intensity; LDA model
随着互联网的普及,论坛、微博等新兴媒体已成为人们获取和发布信息的主要平台,也成为网络舆情的主要载体。舆情分析的主要工作是及时分析网络中的文本数据,从中发现热点主题并进行演化分析,因此,研究热点主题的发现和演化趋势,具有重大的理论意义和应用价值。与主题处理相关的早期工作主要来自于话题检测与跟踪(topic detection and tracking,TDT)技术,但TDT的早期研究并没有有效利用语料的时间信息,在时间轴上分析话题的分布[1]。近年来,以LDA(latent dirichlet allocation)为代表的主题模型得到了深入研究[2-4]。由于LDA本身具有的话题建模能力,在话题演化领域具有先天的优势。基于LDA的一些扩展模型也在随后被提出,比如反映主题在时间上强度变化的TOT(topic over time)模型[5]、采用状态空间记录主题内容和强度演化信息的DTM(dynamic topic model)模型[6]以及考虑多时间粒度主题演化的MTTM(multiscale topic tomography)模型[7]等。但上述模型都需要全局建模,不具有在线处理新文本的能力。OLDA(online LDA)模型[8]将主题历史分布作为当前时间窗口模型的先验,具有在线处理的能力。但OLDA具有易导致主题混合和主题边界模糊的缺点。楚克明等[9]基于LDA模型做话题演化分析,因为不具有主题对齐特性,该方法需要计算相邻时间片任意两个主题间的相似度。吴永辉等[10]将LDA与AP聚类算法结合,用于发现热点新闻主题,不过没有进行演化分析。崔凯等[11]提出了一种在线主题演化挖掘模型,采用的思想与OLDA相似;胡艳丽等[12-13]基于OLDA进行话题的内容和强度的演化分析,这些研究都没有考虑OLDA模型本身的缺点。针对以上问题,本文作者首先基于OLDA提出一种改进的在线LDA模型(improved online LDA, IOLDA),模型为每个主题计算主题强度,强度低的主题的遗传度也较低,减弱其对下个时间片主题建模的影响。这种调节能有效解决OLDA模型中易出现主题混合的缺点。然后还提出了一种新的主题强度计算方法,该方法能有效降低宽泛主题的得分。
1 LDA模型与OLDA模型介绍
1.1 LDA模型的基本思想
LDA属于文档生成模型(如图1所示)。它假设文档是多个隐含主题上的混合分布,各个主题是一个固定词表上的混合分布。令K表示主题数目,M表示文档数目,Nm表示第m个文档的单词数目,文档的生成过程描述如下:
1) 从参数为β的Dirichlet分布中为每个主题采样主题-单词分布
,即有
。
2) 从参数为α的Dirichlet分布中为每个文档采样文档-主题分布
,即有
。
对文档m第n(
)个词:
1) 从参数为
的多项式分布中采样1个主题
,即有
;
2) 从参数为
的多项式分布中采样1个具体单词
,即有
。
在LDA中,参数α和β是固定值,由用户事先指定。文档中的各个单词
是可观测的数据,文档-主题分布
和主题-单词分布
是隐式参数,需要通过概率推导求解。本文采用Gibbs采样法近似求解隐式参数。
![](/web/fileinfo/upload/magazine/12462/308797/image022.jpg)
图1 LDA的图模型表示
Fig. 1 Graphical model representation of LDA
1.2 主题遗传与OLDA模型
在文本处理过程中,存在“主题遗传”现象。“主题遗传”是指主题具有持续性和稳定性。以固定时间片大小划分文本流,那么在历史时间片中出现的主题很可能在当前时间片中继续存在,并保持一定的特征,这种特征通过主题-单词分布来体现。因此,历史时间片中的后验数据可以为当前时间片主题分布的先验提供指导。
OLDA模型根据历史时间片中的主题-单词分布计算当前时间片的先验参数。历史信息保存在矩阵
中,并提供一个权重向量
,以平衡各个历史时间片的数据对当前建模过程的影响,其中
表示时间窗口的大小。因此,在OLDA中,时间片t中的主 题-单词分布服从以下Dirichlet分布:
(1)
OLDA模型按照文本产生的时间先后依次对各时间片中的文档建模,适合在线的话题演化分析。此外,通过后验知识的传递,OLDA模型可以自动对齐各个时间片中推断出的主题,因此,可以方便地跟踪1个主题的强度和内容随着时间的变化。
2 改进的在线LDA模型
在OLDA模型中,历史时间片中的主题权重ω是一个固定值,无法根据主题的动态变化做出调整。而且同一时间片中各个主题共用1个相同的权重,没有考虑主题间的差异,ω的选取比较困难。若ω设置过小,则前后主题不能对齐;若ω设置过大,则会导致一些并非同一事件的主题由于共词的出现而被强制对齐在一起。特别是当t时间片有新主题出现时,该主题容易与某个旧主题混合在一起共同与t-1中的相关主题对齐,造成新主题检测的困难。此外,OLDA维持1个增量更新的词表,每个时间片中的新词都被加入词表中。最终会因词表太大而导致内存溢出,并且处理维数的增加也导致运行时间增多。
为解决以上问题,本文作者提出了一种改进的在线LDA模型(如图2所示)。它基于以下观察:在每个时间片发现的主题中,强度越高的主题越可能在下一个时间片出现并遗传较多的主题特征;相反,强度较低的主题则很可能在下一个时间片消亡并突变为其他主题。因此,可以根据当前时间片中主题的强度排名控制主题遗传度。调整之后较强的主题在前后时间片中依然能够保持连续,冷门主题则可能在下一个时间片消失并对齐一个新的主题。
![](/web/fileinfo/upload/magazine/12462/308797/image032.jpg)
图2 IOLDA的图模型表示
Fig. 2 Graphical model representation of IOLDA
模型假设t时间片主题分布的先验只受t-1时间片建模结果的影响,与更早的历史时间片无关,是一种类马尔可夫链模型。首先定义1个均衡向量
,且
,|Vt|表示时间片t中的词表Vt的大小。则时间片t中主题-单词分布的Dirichlet先验满足:
(2)
其中:
是时间片t-1中主题k的遗传因子,主题k的强度越高,
越大,主题遗传度越高。当
时退化为传统的LDA模型。注意在初始时间片t=1时,与LDA模型一样,先验参数
由1个常量β进行初始化;当t>1时,
由式(2)计算得出。
令a和b分别表示遗传因子的上、下限,对于强度排名为
的主题,遗传因子
计算如下:
(3)
在计算
时,由于
是词表
之上的分布,需要转换为当前词表Vt上的分布。为解决词表不断增大带来的内存增加和运行时间增加的问题,本模型只在相邻时间片的词表的交集范围内传递参数。此时传递的单词分布之和
,由于单词消失而丢失的分布值
平均分配给本时间片内新出现的单词。为了表示的简洁,式(2)中直接使用
作为从t-1继承的主题-单词分布。
经过以上计算后,
的各分量之和为1。在LDA模型中,参数β一般取经验值0.1,此时可以取得较优的主题建模效果。为提高模型的准确性,对
进行如下调整:首先平滑各个分量使其接近均值,避免参数各维的值差距过大;接着乘以放大因子
,使
各维的均值等于常量β(本文取0.1)。调整公式如下:
(4)
综上,IOLDA算法的具体过程如下。
算法1:IOLDA
输入:α;β
t=1
loop
获取文档集合Dt,对应词表为Vt
if t=1 then
![](/web/fileinfo/upload/magazine/12462/308797/image068.gif)
else
定义向量
,
for k=1 to K
由
计算遗传度![](/web/fileinfo/upload/magazine/12462/308797/image040.gif)
计算![](/web/fileinfo/upload/magazine/12462/308797/image075.gif)
对
进行调整
end for
end if
[
]
Gibbs Sampling(
,
,
)
计算主题排名![](/web/fileinfo/upload/magazine/12462/308797/image088.gif)
t=t+1
end loop
3 主题演化分析
主题演化分为强度演化和内容演化[1]。主题强度演化需要计算一个主题在各时间片中的强度,本文采用一种新的主题强度计算方法。在内容演化上,利用IOLDA模型具有主题对齐的特点,采用Jensen-Shannon距离横向计算相邻时间片同一编号主题的相似性,跟踪主题的发展趋势。
3.1 主题强度度量
描述某个确定话题的文档往往在一个或少数几个主题上有较高概率分布值,而在其他主题上分布值很低或没有分布。相反,若1个文档在各个主题上的分布比较平均,则该文档谈论的内容比较宽泛,没有明确的主题倾向。本文根据文档的分布情况为各个文档赋予1个权值,具有明确主题倾向的文档得分较高,内容过于宽泛的文档得分较低。
采用熵衡量文档-主题分布的集中程度,再由熵计算文档权重:
(5)
(6)
式中:
表示文档m在第k个主题上分布的估计值。当文档只属于1个主题时,权重取最大值1;当文档在K个主题上均匀分布时,权重达到最小值0,此时认为文档对各个主题都不能提供支持。得到各个文档权重后,主题强度根据式(7)计算:
(7)
3.2 主题相似性度量
主题相似性计算一般采用KL距离(Kullback-Leibler divergence)[14],它度量2个主题在词集上分布的差异性。对于相邻时间片中编号为k的2个主题分布
和
,KL距离定义如下:
(8)
KL距离是不对称的,但2个主题的距离应该是对称的概念。本文采用Jensen-Shannon距离度量2个主题分布的差异性。Jensen-Shannon距离由KL距离定义,对于主题分布
和
,JS距离为
![](/web/fileinfo/upload/magazine/12462/308797/image105.gif)
(9)
计算时需要将2个主题-单词分布映射到同一个词集上。实验中设置1个阈值ε,若JS距离小于ε,则当前主题是前一主题的延续,否则认为主题发生了改变。
4 实验及结果分析
本文采用从天涯社区的“天涯杂谈”板块抓取的帖子做话题发现与演化分析。实验数据集包含2013-06-19—2013-07-08共67 832篇帖子,以1 d作为时间片划分数据集。
预处理阶段只保留文档中的名词和动词,并筛选TF-IDF得分最高的前75%的单词做降维处理。实验中设置主题数目K=100,遗传度的上、下限取经验值0.6与0.1,相似度阈值ε=0.35。
4.1 基于IOLDA模型的主题发现
OLDA模型的主题边界比较模糊,不容易检测主题的产生与消失,而且新主题容易出现混合对齐的现象。表1所示为几个突发主题比较IOLDA和OLDA的主题检测效果。
表1 OLDA与IOLDA的主题检测结果
Table 1 Topic discovering results of OLDA and IOLDA
![](/web/fileinfo/upload/magazine/12462/308797/image108.jpg)
从表1可以看出:OLDA有2个主题未及时发现,另外3个主题也出现不同程度的混合现象。比如主题“女孩被藏獒咬死”就是因为“警方”、“调查”等词的共现而与“警方调查色情行业”的主题混合在一起。而在IOLDA模型中,趋于消亡的主题的遗传度会被降低,新词汇的权重相对就高一些,因此新主题更易与前一个时间片的冷门主题(一般在本时间片消亡)对齐,而不会出现强制混合对齐的现象。
实验进一步比较了IOLDA模型和OLDA模型的困惑度(Perplexity)[2]。困惑度衡量主题模型对于未观测数据的预测能力,困惑度越小,模型预测能力越强,模型的推广性越高。困惑度定义如下:
(10)
其中:Dtest为测试集;wd为文档d中的可观测单词序列;Nd为文档d的单词数目。实验在每个时间片随机选择10%的文档作为测试集,其余90%文档作为训练集。计算得到的OLDA与IOLDA的困惑度如图3所示。
![](/web/fileinfo/upload/magazine/12462/308797/image112.jpg)
图3 OLDA与IOLDA模型的困惑度对比
Fig. 3 Comparisons of perplexities of OLDA and IOLDA
从图3可以看出:IOLDA模型的困惑度更小,模型的推广性更好。
4.2 主题强度度量及演化分析
以文献[1,11,15]中的方法作为baseline方法,该方法用主题在同一时间片各文档中分布值的平均值来度量主题强度。表2所示为使用2种强度计算方法得到的6月20日前5名的主题编号。各主题编号对应的主题词如表3所示。
把不能明显看出描述对象或事件的主题叫做宽泛主题。表中“高考相关”、“健康相关”和“消费相关”主题都属于宽泛主题。这类主题一般在各个时间片都会出现,不应作为关注重点。由于属于宽泛主题的文档本身往往没有明确的主题倾向,所以,根据文档在主题描述上的集中程度赋予文档1个权重,可以有效降低宽泛主题的得分。本文方法计算的前5名的主题中,只有1个宽泛主题且排名靠后;而baseline方法出现了3个宽泛主题,且排名靠前。
表2 前5名的主题编号
Table 2 Numbers of the top 5 topics
![](/web/fileinfo/upload/magazine/12462/308797/image113.jpg)
表3 各个主题的主题词
Table 3 Keywords of the topics
![](/web/fileinfo/upload/magazine/12462/308797/image114.jpg)
计算主题强度得分后,可进一步观察各个主题的强度发展趋势。图4所示为主题强度的演化。从图4可以看出:网络中大部分热点主题具有“迅速成为热点并快速消亡”的特点:事件发生后当天或短时间内就成为一个热点,在之后2~3 d内逐渐消亡。不过也有个别主题伴随着事件的进行长期存在,比如“棱镜门事件”。
4.3 主题内容演化分析
同一个主题在发展过程中侧重点会有所变化,具体到主题模型中就是主题在词语上的概率分布会发生变化。表4所示为“神十发射”主题在连续时间片中概率分布最高的10个主题词。从表4可以看出,该主题开始时侧重于王亚平太空授课,接着是航天技术的讨论,最后是神十返回地面。
通过Jensen-Shannon距离可以检测到主题的改变。以“巴基斯坦游客遇袭”主题为例,该主题在2013-06-23出现,2013-06-29消亡。图5所示为从2013-06-23开始相邻时间片的主题距离计算结果。从图5可以看出:2013-06-23和2013-06-29的主题距离显著高于阈值(虚线表示),说明主题在这2 d中发生了改变。
![](/web/fileinfo/upload/magazine/12462/308797/image116.jpg)
图4 主题强度的演化
Fig. 4 Topic intensity evolution
表4 “神十发射”主题的内容演化
Table 4 Content evolution for topic “launch of Shenzhou-10”
![](/web/fileinfo/upload/magazine/12462/308797/image117.jpg)
![](/web/fileinfo/upload/magazine/12462/308797/image119.jpg)
图5 主题变化的检测
Fig. 5 Topic change detection
5 结论
1) 基于OLDA模型提出了一种改进的在线LDA模型(IOLDA),模型根据主题强度决定每个主题的遗传度,改善了OLDA中易出现主题混合和新主题不易检测的缺陷。在天涯论坛语料上的实验结果表明:本文模型具有更低的困惑度和更优的主题检测效果。
2) 采用了一种新的主题强度计算方法,该方法根据文档-主题分布的集中程度为文档设置不同的权值,可以有效降低宽泛主题的强度得分。
3) 利用模型具有主题对齐的特点,可以方便地分析主题的强度演化和内容演化。网络主题具有“迅速成为热点并快速消亡”的特点。
参考文献:
[1] 单斌, 李芳. 基于LDA话题演化研究方法综述[J]. 中文信息学报, 2010, 24(6): 43-49, 68.
SHAN Bin, LI Fang. A survey of topic evolution based on LDA[J]. Journal of Chinese Information Processing, 2010, 24(6): 43-49, 68.
[2] Blei D M, Ng A Y, Jordan M I. Latent Dirichlet allocation[J]. Journal of Machine Learning Research, 2003(3): 993-1022.
[3] 徐戈, 王厚峰. 自然语言处理中主题模型的发展[J]. 计算机学报, 2011, 34(8): 1423-1436.
XU Ge, WANG Houfeng. The development of topic models in natural language processing[J]. Chinese Journal of Computers, 2011, 34(8): 1423-1436.
[4] 范云满, 马建霞. 利用LDA的领域新兴主题探测技术综述[J]. 现代图书情报技术, 2012(12): 58-65.
FAN Yunman, MA Jianxia. Review on the LDA-based techniques detection for the field emerging topic[J]. New Technology of Library and Information Service, 2012(12): 58-65.
[5] Wang X, McCallum A. Topics over time: A non-Markov continuous-time model of topical trends[C]// Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Philadelphia, USA, 2006: 424-433.
[6] Blei D M, Lafferty J D. Dynamic topic models[C]//Proceedings of the 23rd International Conference on Machine Learning. Pittsburgh, Pennsylvania, USA, 2006: 113-120.
[7] Nallapati R M, Ditmore S, Lafferty J D, et al. Multiscale topic tomography[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Jose, California, USA, 2007: 520-529.
[8] AlSumait L, Barbará D, Domeniconi C. On-Line LDA: Adaptive topic models for mining text streams with applications to topic detection and tracking[C]// Proceedings of the 8th IEEE International Conference on Data Mining. Pisa, Italy, 2008: 3-12.
[9] 楚克明, 李芳. 基于LDA话题关联的话题演化[J]. 上海交通大学学报, 2010, 44(11): 1496-1500.
CHU Keming, LI Fang. Topic evolution based on LDA and topic association[J]. Journal of Shanghai Jiaotong University, 2010, 44(11): 1496-1500.
[10] 吴永辉, 王晓龙, 丁宇新, 等. 基于主题的自适应、在线网络热点发现方法及新闻推荐系统[J]. 电子学报, 2010, 38(11): 2620-2624.
WU Yonghui, WANG Xiaolong, DING Yuxin, et al. Adaptive on-line web topic detection method for web news recommendation system[J]. Acta Electronica Sinica, 2010, 38(11): 2620-2624.
[11] 崔凯, 周斌, 贾焰, 等. 一种基于LDA 的在线主题演化挖掘模型[J]. 计算机科学, 2010, 37(11): 156-159, 193.
CUI Kai, ZHOU Bin, JIA Yan, et al. LDA-based model for online topic evolution mining[J]. Computer Science, 2010, 37(11): 156-159, 193.
[12] 胡艳丽, 白亮, 张维明. 网络舆情中一种基于OLDA的在线话题演化方法[J]. 国防科技大学学报, 2012, 34(1): 150-154.
HU Yanli, BAI Liang, ZHANG Weiming. OLDA-based method for online topic evolution in network public opinion analysis[J]. Journal of National University of Defense Technology, 2012, 34(1): 150-154.
[13] 胡艳丽, 白亮, 张维明. 一种话题演化建模与分析方法[J]. 自动化学报, 2012, 38(10): 1690-1697.
HU Yanli, BAI Liang, ZHANG Weiming. Modeling and analyzing topic evolution[J]. Acta Automatica Sinica, 2012, 38(10): 1690-1697.
[14] 宗成庆. 统计自然语言处理[M]. 北京: 清华大学出版社, 2008: 22-22.
ZONG Chengqing. Statistical natural language processing[M]. Beijing: Tsinghua University Press, 2008: 22-22.
[15] Griffiths T L, Steyvers M. Finding scientific topics[J]. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101: 5228–5235.
(编辑 赵俊)
收稿日期:2014-03-16;修回日期:2014-07-02
基金项目(Foundation item):国家科技支撑计划项目(2012BAH18B05);国家自然科学基金资助项目(61272447)(Project (2012BAH18B05) supported by the National Key Technology R&D Program of China; Project (61272447) supported by the National Natural Science Foundation of China)
通信作者:陈兴蜀,博士,教授,从事信息安全、云计算等研究;E-mail:chenxsh@scu.edu.cn