基于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