基于LDA模型和T-OPTICS算法的中文新闻话题检测

李琮,袁方,刘宇,李欣雨

(1.河北大学计算机科学与技术学院,河北保定　071002；2.河北大学数学与信息科学学院,河北保定　071002)



基于LDA模型和T-OPTICS算法的中文新闻话题检测

李琮1,袁方2,刘宇2,李欣雨1

(1.河北大学计算机科学与技术学院,河北保定071002；2.河北大学数学与信息科学学院,河北保定071002)

摘要：给出了一种针对大量新闻数据的话题检测方法.首先通过LDA(latent dirichlet allocation)模型从语义层面抽取新闻数据主题,有效降低数据分析维度,更合理地体现新闻主题特征.然后改进OPTICS(ordering point to identify the cluster structure)密度聚类算法,基于新闻话题的时间延续性给出了T-OPTICS算法.该算法继承了OPTICS算法对参数不敏感的特性,降低了参数选择对聚类结果的影响.改进了OPTICS算法中文本间相似度的计算方法,体现了话题的时间延续性.基于TDT4数据集的实验表明,该方法能够快速有效地发现新闻中的话题.

关键词：LDA模型；T-OPTICS；聚类；降维

近些年,随着互联网的快速发展和网络终端的多样化,网络新闻的影响力不断提高.网络新闻相比传统媒体新闻有更强的时效性和便捷性,已经成为人们获取新闻的主要渠道.新闻话题检测的主要任务是从大量新闻中自动检测出潜在的话题.同时该任务也可以对突发事件进行检测并全面了解事件的发展情况.话题检测对舆情监测、信息安全、商业金融等领域都有重要作用.

在传统文本处理中,常使用向量空间模型(vector space model,VSM)进行文本表示.向量空间模型以词作为文本的特征项,将文本标识为一个高维、稀疏的矩阵.在对大量数据进行分析时,由于VSM维度过高,时间效率很低甚至无法实际应用.针对于VSM的不足,研究人员提出更多快速分类主题模型,其中潜在语义索引(latent semantic indexing,LSI)[1]是一种根据词项的共现规律来发现词与词之间的语义联系的方法,LSI方法降维效果明显,但部分出现频率很低却对分类作用明显的词项可能被忽略掉,使分类效果有所降低.

LDA(latent dirichlet allocation)[2]模型是一种非监督的文本概率生成模型,用多个潜在主题上的概率分布表示文本特征,对于其中每个主题则用词项的概率分布来表示.LDA主题模型既避免LSI模型低频特征项丢失的问题,有效降低了矩阵的维度,是目前流行的文本主题建模技术,被广泛应用于信息检索[3]、社区挖掘、文本分割[4]等领域.本文采用LDA模型抽取文本主题.

事件由特定原因、条件引起,发生在特定时间、特定地点,并可能伴随某些必然的结果.话题是一个核心事件或活动以及与其相关的事件或活动[5].话题检测的主要任务是从大量的报道中检测并组织预先未知的话题,本质上是一种特殊文本的聚类过程.在以主题作为维度的高维坐标系上,事件或活动表示为一系列稠密的新闻点,话题则表示为多个相邻或密度相连的稠密区域，同时话题的发展方向是不确定和不均匀的,所以话题形成的稠密区域的形状是不规则的.

传统的话题检测技术大都使用基于划分的聚类方法,如K-means算法,其基本原理是通过对比文章与聚类中心点的距离的方法对所有文档进行划分,从而实现话题检测的目的.基于划分的聚类算法只能发现球形等规则形状的簇,对于不规则形状的簇检测效果不佳.

在近期的研究中,贺敏等[6]采用动量模型将有意义串作为文本的特征,借鉴动力学中的动量定义对特征建模,这种方法可以降低文本维度并体现话题的核心特征,但部分能够体现类间联系的非核心特征则可能被忽略.Ding等[7]将主题模型与词共现模型、共引模型进行了比较,实验证明在话题检测追踪中主题模型在敏感性和持久性上都优于另外2种模型.马彬等[8]采用了线索树双层聚类的方法,在解决数据稀疏方面取得了较好的效果,但该算法不能自动确定聚类个数,使算法的话题检测效果受到一定程度的影响.

本文在基于密度的OPTICS(ordering point to identify the cluster structure)[9]聚类算法的基础上,充分考虑话题的时间延续性,给出了T-OPTICS算法.相比基于划分的K-means算法,基于密度的聚类算法能够根据话题稠密区域的形状进行聚类,可以发现任意形状的簇,更好地体现话题中新闻的疏密关系,更加契合话题中新闻联系的特征,提高话题检测的有效性.并且OPTICS算法克服了DBSCAN算法对参数极为敏感的缺点,并不直接产生明确的数据集聚类,而是输出对象的有序队列,降低了参数选择对聚类效果的影响.而有序结果序列可以提取基本的聚类信息,体现内在聚类结构,最终能够提供聚类的可视化表示.便于用户直观的理解实验结果,达到实用性目的.本文的T-OPTICS算法在OPTICS聚类的基础上充分考虑时间因素对聚类结果的影响,体现了新闻话题的时间延续性,更加符合新闻话题的演化规律,进一步提高了新闻话题检测的效果.

1基于LDA模型和T-OPTICS聚类的中文新闻话题检测

1.1基本思想与框架

通过构建文本的LDA模型,将文本由多个潜在主题上的概率分布进行表示,有效地降低文本数据的维度,通过稀疏调整,减少文本的稀疏性.然后使用T-OPTICS算法将文本聚类成多个不同的话题.

本文模型基本框架如图1所示.

1.2LDA建模

LDA是一种完全的文本生成模型,其本质是3层贝叶斯模型.本文用该模型将新闻文本用主题的概率分布表示,主题用词项的概率分布进行表示.模型的生成图[2]如图2所示.其中α和β是超参数,θ是文本在主题上的概率分布,ψ是主题在词项上的概率分布,ω是词项,z是w的主题标号.α→θ→z的过程表示生成第m篇文档的过程,而β→ψ→ω的过程表示生成第m篇文档第n个词的过程.

图1　算法框架 图2　LDA模型 Fig.1　Algorithm frame Fig.2　LDA Model

在参数估计的过程中采用了吉布斯抽样的方法,根据经验取α=0.5,β=0.1,主题个数选择30.经过建模形成如下2个矩阵,为聚类提供基础.

1)矩阵θ,是一个M×K的矩阵,K是潜在主题的个数,M是文章的数量.该矩阵表示每篇文章的潜在主题概率分布.

2)矩阵ψ,是一个K×V的矩阵,V是词袋中词项的个数,该矩阵表示每个主题的词项概率分布.

1.3T-OPTICS聚类算法

基于密度的OPTICS聚类算法从一个随机选定的点开始,向着密度高的区域扩张,最终形成一个反映所有语料对象可达距离的可视化有序序列,这个有序队列是所有分析对象的线性表,且代表了数据基于密度的聚类结构.这个簇排序可以用来提取基本的聚类信息,导出内在的聚类结构,方便提供聚类的可视化表示.

有序队列的可达距离图可以直观呈现对象的分布.如图3所示[9]56,以有序队列的点作为横轴,点的可达距离为纵轴.其中距离相近的点相互靠近,距离远的点相互远离,每一个波谷为一个聚类,每一个波峰为聚类边界.通过图像中的下降区间和上升区间即可发现聚类.

图3　OPTICS算法可达图Fig.3　OPTICS reachability-plots

话题检测研究的对象具有时间性,它们都有发生的先后顺序.另外,话题都只持续一段时间,随后消失或报道减少[10].所以新闻话题具有时间延续性,时间间隔越小的新闻谈论相同话题的概率越大,时间间隔越大的新闻谈论相同话题的概率越小.所以在进行聚类时,充分考虑时间因素对聚类结果的影响提出了T-OPTICS算法,提高基于密度的聚类算法在新闻话题检测中的效果.在T-OPTICS算法中,将时间因素加入距离计算公式,如公式(1).

(1)

公式中θ1、θ2为2篇文章的主题概率分布向量,n为2篇新闻发布时间间隔的天数.利用指数的变化特点,使新闻间向量距离随时间间隔变大而增大,并且变化速度随着时间间隔变大而逐渐变快.这样就使距离计算公式更加契合新闻话题的时间延续规律,利用话题的时间延续性有效地区分了内容相近但从属于不同话题的新闻报道.

2实验设计及结果分析

2.1实验语料及预处理

采用了LDC的TDT4语料库.TDT4语料库共包括中文新闻27 142篇,其中2002年被标注的新闻有657篇,涵盖了37个新闻话题(记作TDT4-2002数据集)；2003年被标注的中文新闻有564篇,涵盖了31个新闻话题(记作TDT4-2003数据集).采用中科院的ICTCLAS分词系统对语料进行分词操作,并去除停用词.

2.2实验设计

实验中对文本分别使用LDA和VSM模型建模.使用LDA对文档进行建模时,迭代400次,将文本表示为30个潜在主题上的概率分布.

实验分为5组进行,如表1.前4组基用LDA和VSM模型分别使用K-means和OPTICS算法进行聚类,最后1组基于LDA模型使用T-OPTICS算法进行聚类.

表1　实验分组详情

2.3评估方法

本文使用准确率PPrecision、召回率PRecall、F1值(F1Measure)作为标准对实验结果进行评测.计算公式(2)如下：

(2)

其中,准确率PPrecision表示检测出的话题中话题隶属关系正确的新闻数与所有检测出的新闻数的比值.召回率PRecall表示检测出的话题中话题隶属关系正确的新闻数与测试集中所有话题的新闻数的比值.F1值(F1Measure)是准确率和召回率的调和平均数,综合了准确率和召回率的效果.

2.4结果分析

实验1和实验2选取数据集中话题的实际数量为聚类数K,分别对VSM和LDA模型进行10次K-means聚类,取准确率、召回率和F1值的平均值为最终结果.在实验4和实验5中,由于构建LDA模型的过程存在抽样运算,结果会有小幅浮动,所以进行5次实验,取平均值作为最终结果.实验3、实验4和实验5中,参数MinPts取数据集中最小话题包含的新闻数4.通过实验产生的可达图(图4、图5、图6、图7)可知LDA模型中取ε=0.5时可达图刚好显示所有对象的可达距离,VSM模型中取ε=0.8时可达图刚好显示所有对象的可达距离.

图4　OPTICS聚类可达图(TDT4-2002、LDA) 图5　OPTICS聚类可达图(TDT4-2002、VSM)　Fig.4　OPTICS reachability-plots of use LDA Model on Fig.5　OPTICS reachability-plots of use VSM Model onTDT4-2002 datasetTDT4-2002 dataset

图6　OPTICS聚类可达图(TDT4-2003、LDA) 图7　OPTICS聚类可达图(TDT4-2003、VSM) Fig.6　OPTICS reachability-plots of use LDA Model on Fig.7　OPTICS reachability-plots of use VSM Model onTDT4-2003 dataset TDT4-2003 dataset

2.4.1对使用K-means聚类和OPTICS聚类算法的话题检测效果进行对比

表2为前4组实验的结果汇总.由表2可以看出,无论在TDT4-2002数据集还是TDT4-2003数据集中,实验3的准确率、召回率和F1值好于实验1,实验4的准确率、召回率和F1值好于实验2.由此表明基于密度的OPTICS聚类算法比K-means聚类算法能够获得更好的话题检测性能.

表2　K-means、OPTICS算法效果

2.4.2对VSM模型和LDA模型进行对比

由表2可知,在TDT4-2002数据集中,实验2比实验1的F1值降低了0.3%,实验4比实验3的F1值提高了3.66%；在TDT4-2003数据集中,实验2比实验1的F1值降低了0.2%,实验4比实验3的F1值提高了4.56%.由此可知LDA模型与VSM模型的实验效果基本相当.但由于LDA模型相对于VSM模型的降维作用明显,同时OPTICS算法的时间复杂度是O(Kn2),其中K是数据维度,由此可知LDA模型比VSM模型时间复杂度得到了明显降低,算法的运算效率明显提高.

表3　T-OPTICS、OPTICS算法效果对比

2.4.3对T-OPTICS和OPTICS算法结果进行对比

为了体现新闻的时间延续性,实验5使用了T-OPTICS聚类算法,在实验4的基础上加入了时间参数.为了合理的选择时间参数的值,选择区间1.05～1.2,以间隔0.01分组,共15组系数分别进行实验,从结果图(图8、图9)的2个图表中可以看出,当选择适当的时间参数时,带有时间参数的实验效果都好于无时间参数实验的结果.表3是实验5与实验4的结果对比,从表3可以看出,TDT4-2003数据集中加入时间参数后准确率提高了11.9%,召回率提高了2.4%,综合F1值提高了6.5%,说明时间参数的加入,使话题检测的性能得到了较明显的提高；TDT4-2002数据集在加入时间参数的算法处理后准确率提高了4.1%,召回率下降了0.99%,但代表算法综合效率的F1值提高了1.35%,说明时间参数的加入使算法性能得到了一定的提高.

图8　时间参数对比图(TDT4-2002) 图9　时间参数对比图(TDT4-2003)Fig.8　Comparison chart of different time parameter Fig.9　Comparison chart of different time parameter(TDT4-2002)(TDT4-2003)

2.4.4实验结果总结

表4是5组实验的最终结果.对比可知,使用LDA模型替代VSM模型,在维持实验性能的同时大幅降低了数据维度,从而降低了算法的空间复杂度和时间复杂度,提高了算法的效率.OPTICS算法比传统的K-means算法在话题检测中体现了新闻之间联系的结构,使话题检测性能大幅提升.对加入时间参数的T-OPTICS算法的实验中,实验性能也得到了一定的提高.实验表明,本文采用的LDA+T-OPTICS聚类算法与传统的VSM模型+K-means聚类的方法进行对比,TDT4-2002数据集中准确率提高了16.4%,召回率提高了8.1%,F1值提高了11.9%；TDT4-2003数据集上准确率提高了34.1%,召回率提高了27.5%,F1值提高了30.7%,大幅提高了话题检测的性能.

表4　实验结果汇总

3结束语

给出了一种基于LDA模型和T-OPTICS聚类方法的话题检测算法.本方法通过LDA模型对文本进行表示,体现了文本之间的语义联系.同时引入时间参数的T-OPTICS聚类算法相比传统基于划分的聚类算法更加体现了语料中文本之间的逻辑结构.算法中时间参数的加入更好地利用了话题的时间延续性特点.经实验验证,使用LDA模型与T-OPTICS的方法相比传统的检测方法性能明显提高.

参考文献：

[1]DEERWESTER S.Indexing by latent semantic analysis[J].Journal of the American Society of Information Science,1990,26(4):147-157.DOI:10.1002/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9.

[2]JORDAN M I,BLEI D M,NG A Y.Latent Dirichlet Allocation[J].Journal of Machine Learning Research,2003,3:993-1022.DOI:10.1109/MLSP.2011.6064562.

[3]卜质琼,郑波尽.基于LDA模型的Ad-hoc信息检索方法研究[J].计算机应用研究,2015,32(5)：1369-1372.DOI:10.3969/j.issn.1001-3695.2015.05.022.

BU Zhiqiong,ZHENG Bojin.Ad hoc information retrieval method based on LDA[J].Application Research of Computers,2015,32(5):1369-1372.DOI:10.3969/j.issn.1001-3695.2015.05.022.

[4]石晶,胡明,石鑫,等.基于LDA模型的文本分割[J].计算机学报,2008,31(10)：1865-1873.DOI:10.3321/j.issn:0254-4164.2008.10.022.

SHI Jing,HU Ming,SHI Xin,et al.Text segmentation based on model LDA[J].Chinese Journal of Computers,2008,31(10):1865-1873.DOI:10.3321/j.issn:0254-4164.2008.10.022.

[5]洪宇,张宇,刘挺,等.话题检测与跟踪的评测及研究综述[J].中文信息学报,2007,21(6)：71-87.DOI:10.3969/j.issn.1003-0077.2007.06.011.

HONG Yu,ZHANG Yu,LIU Ting,et al.Topic detection and tracking review[J].Journal of Chinese Information Processing,2007,21(6):71-87.DOI:10.3969/j.issn.1003-0077.2007.06.011.

[6]贺敏,杜攀,张瑾,等.基于动量模型的微博突发话题检测方法[J].计算机研究与发展,2015,52(5):1022-1028.DOI:10.7544/issn1000-1239.2015.20131549.

HE Min,DU Pan,ZHANG Jin,et al.Microblog bursty topic detection method based on momentum model[J].Journal of Computer Research and Development,2015,52(5):1022-1028.DOI:10.7544/issn1000-1239.2015.20131549.

[7]DING W,CHEN C.Dynamic topic detection and tracking:A comparison of HDP,C-word,and cocitation methods[J].Journal of the Association for Information Science & Technology,2014,65(10):2084-2097.DOI:10.1002/asi.23134.

[8]马彬,洪宇,陆剑江,等.基于线索树双层聚类的微博话题检测[J].中文信息学报,2012,26(6):121-128.DOI:10.3969/j.issn.1003-0077.2012.06.017.

MA Bin,HONG Yu,LU Jianjiang,et al.A thread-based two-stage clustering method of microblog topic detection[J].Journal of Chinese Information Processing,2012,26(6):121-128.DOI:10.3969/j.issn.1003-0077.2012.06.017.

[9] ANKERST M.OPTICS:Ordering points to identify the clustering structure[C]// Proc 1999 ACM SIGMOD International Conference on Management of Data(SIGMOD-99)1999：49-60.DOI:10.1145/304181.304187.

[10]张小明,李舟军,巢文涵.基于增量型聚类的自动话题检测研究[J].软件学报,2012,23(6)：1578-1587.DOI:10.3724/SP.J.1001.2012.04111.

ZHANG Xiaoming,LI Zhoujun,CHAO Wenhan.Research of automatic topic detection based on incremental clustering[J].Journal of Software,2012,23(6):1578-1587.DOI:10.3724/SP.J.1001.2012.04111.

(责任编辑：孟素兰)

Chinese news topic detection based on LDA and T-OPTICS

LI Cong1,YUAN Fang2,LIU Yu2,LI Xinyu1

(1.College of Computer Science and Technology,Hebei University,Baoding 071002,China;2.College of Mathematics and Information Science,Hebei University,Baoding 071002,China)

Abstract:A method of topic detection from large-scale news dataset is proposed.First,latent dirichlet allocation(LDA) is used to reduce the dimension of data by express the news to probabilistic distribution on a set of topics.Then,T-OPTICS algorithm,one algorithm proved based on OPTICS(ordering point to identify the cluster structure) algorithm,is used to cluster news to topics.Because of the OPTICS algorithm is not sensitive to parameters variation,the influence of parameters choice is reduced.The calculation method of text similarity is proved by considering the effect of time parameters.The experimental results show that the algorithm can detect the topics in the TDT4 data set quickly and effectively.

Key words:LDA model;T-OPTICS;cluster;dimensionality reduction

DOI：10.3969/j.issn.1000-1565.2016.01.017

收稿日期：2015-09-20

基金项目：河北省软科学研究计划项目(13455317D；12457206D-11)

通信作者：袁方(1965—),男,河北保定人,河北大学教授,主要从事数据挖掘与社会计算研究.

中图分类号：TP391.1

文献标志码：A

文章编号：1000-1565(2016)01-0106-07

第一作者：李琮(1987—),男,河北保定人,河北大学硕士研究生,主要从事数据挖掘研究.E-mail:licongche@hotmail.com

E-mail：yuanfang@hbu.edu.cn