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

(1.河北大學計算機科學與技術(shù)學院,河北保定　071002；2.河北大學數(shù)學與信息科學學院,河北保定　071002)

?

基于LDA模型和T-OPTICS算法的中文新聞話題檢測

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

(1.河北大學計算機科學與技術(shù)學院,河北保定071002；2.河北大學數(shù)學與信息科學學院,河北保定071002)

摘要：給出了一種針對大量新聞數(shù)據(jù)的話題檢測方法.首先通過LDA(latent dirichlet allocation)模型從語義層面抽取新聞數(shù)據(jù)主題,有效降低數(shù)據(jù)分析維度,更合理地體現(xiàn)新聞主題特征.然后改進OPTICS(ordering point to identify the cluster structure)密度聚類算法,基于新聞話題的時間延續(xù)性給出了T-OPTICS算法.該算法繼承了OPTICS算法對參數(shù)不敏感的特性,降低了參數(shù)選擇對聚類結(jié)果的影響.改進了OPTICS算法中文本間相似度的計算方法,體現(xiàn)了話題的時間延續(xù)性.基于TDT4數(shù)據(jù)集的實驗表明,該方法能夠快速有效地發(fā)現(xiàn)新聞中的話題.

關(guān)鍵詞：LDA模型；T-OPTICS；聚類；降維

近些年,隨著互聯(lián)網(wǎng)的快速發(fā)展和網(wǎng)絡(luò)終端的多樣化,網(wǎng)絡(luò)新聞的影響力不斷提高.網(wǎng)絡(luò)新聞相比傳統(tǒng)媒體新聞有更強的時效性和便捷性,已經(jīng)成為人們獲取新聞的主要渠道.新聞話題檢測的主要任務是從大量新聞中自動檢測出潛在的話題.同時該任務也可以對突發(fā)事件進行檢測并全面了解事件的發(fā)展情況.話題檢測對輿情監(jiān)測、信息安全、商業(yè)金融等領(lǐng)域都有重要作用.

在傳統(tǒng)文本處理中,常使用向量空間模型(vector space model,VSM)進行文本表示.向量空間模型以詞作為文本的特征項,將文本標識為一個高維、稀疏的矩陣.在對大量數(shù)據(jù)進行分析時,由于VSM維度過高,時間效率很低甚至無法實際應用.針對于VSM的不足,研究人員提出更多快速分類主題模型,其中潛在語義索引(latent semantic indexing,LSI)[1]是一種根據(jù)詞項的共現(xiàn)規(guī)律來發(fā)現(xiàn)詞與詞之間的語義聯(lián)系的方法,LSI方法降維效果明顯,但部分出現(xiàn)頻率很低卻對分類作用明顯的詞項可能被忽略掉,使分類效果有所降低.

LDA(latent dirichlet allocation)[2]模型是一種非監(jiān)督的文本概率生成模型,用多個潛在主題上的概率分布表示文本特征,對于其中每個主題則用詞項的概率分布來表示.LDA主題模型既避免LSI模型低頻特征項丟失的問題,有效降低了矩陣的維度,是目前流行的文本主題建模技術(shù),被廣泛應用于信息檢索[3]、社區(qū)挖掘、文本分割[4]等領(lǐng)域.本文采用LDA模型抽取文本主題.

事件由特定原因、條件引起,發(fā)生在特定時間、特定地點,并可能伴隨某些必然的結(jié)果.話題是一個核心事件或活動以及與其相關(guān)的事件或活動[5].話題檢測的主要任務是從大量的報道中檢測并組織預先未知的話題,本質(zhì)上是一種特殊文本的聚類過程.在以主題作為維度的高維坐標系上,事件或活動表示為一系列稠密的新聞點,話題則表示為多個相鄰或密度相連的稠密區(qū)域，同時話題的發(fā)展方向是不確定和不均勻的,所以話題形成的稠密區(qū)域的形狀是不規(guī)則的.

傳統(tǒng)的話題檢測技術(shù)大都使用基于劃分的聚類方法,如K-means算法,其基本原理是通過對比文章與聚類中心點的距離的方法對所有文檔進行劃分,從而實現(xiàn)話題檢測的目的.基于劃分的聚類算法只能發(fā)現(xiàn)球形等規(guī)則形狀的簇,對于不規(guī)則形狀的簇檢測效果不佳.

在近期的研究中,賀敏等[6]采用動量模型將有意義串作為文本的特征,借鑒動力學中的動量定義對特征建模,這種方法可以降低文本維度并體現(xiàn)話題的核心特征,但部分能夠體現(xiàn)類間聯(lián)系的非核心特征則可能被忽略.Ding等[7]將主題模型與詞共現(xiàn)模型、共引模型進行了比較,實驗證明在話題檢測追蹤中主題模型在敏感性和持久性上都優(yōu)于另外2種模型.馬彬等[8]采用了線索樹雙層聚類的方法,在解決數(shù)據(jù)稀疏方面取得了較好的效果,但該算法不能自動確定聚類個數(shù),使算法的話題檢測效果受到一定程度的影響.

本文在基于密度的OPTICS(ordering point to identify the cluster structure)[9]聚類算法的基礎(chǔ)上,充分考慮話題的時間延續(xù)性,給出了T-OPTICS算法.相比基于劃分的K-means算法,基于密度的聚類算法能夠根據(jù)話題稠密區(qū)域的形狀進行聚類,可以發(fā)現(xiàn)任意形狀的簇,更好地體現(xiàn)話題中新聞的疏密關(guān)系,更加契合話題中新聞聯(lián)系的特征,提高話題檢測的有效性.并且OPTICS算法克服了DBSCAN算法對參數(shù)極為敏感的缺點,并不直接產(chǎn)生明確的數(shù)據(jù)集聚類,而是輸出對象的有序隊列,降低了參數(shù)選擇對聚類效果的影響.而有序結(jié)果序列可以提取基本的聚類信息,體現(xiàn)內(nèi)在聚類結(jié)構(gòu),最終能夠提供聚類的可視化表示.便于用戶直觀的理解實驗結(jié)果,達到實用性目的.本文的T-OPTICS算法在OPTICS聚類的基礎(chǔ)上充分考慮時間因素對聚類結(jié)果的影響,體現(xiàn)了新聞話題的時間延續(xù)性,更加符合新聞話題的演化規(guī)律,進一步提高了新聞話題檢測的效果.

1基于LDA模型和T-OPTICS聚類的中文新聞話題檢測

1.1基本思想與框架

通過構(gòu)建文本的LDA模型,將文本由多個潛在主題上的概率分布進行表示,有效地降低文本數(shù)據(jù)的維度,通過稀疏調(diào)整,減少文本的稀疏性.然后使用T-OPTICS算法將文本聚類成多個不同的話題.

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

1.2LDA建模

LDA是一種完全的文本生成模型,其本質(zhì)是3層貝葉斯模型.本文用該模型將新聞文本用主題的概率分布表示,主題用詞項的概率分布進行表示.模型的生成圖[2]如圖2所示.其中α和β是超參數(shù),θ是文本在主題上的概率分布,ψ是主題在詞項上的概率分布,ω是詞項,z是w的主題標號.α→θ→z的過程表示生成第m篇文檔的過程,而β→ψ→ω的過程表示生成第m篇文檔第n個詞的過程.

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

在參數(shù)估計的過程中采用了吉布斯抽樣的方法,根據(jù)經(jīng)驗取α=0.5,β=0.1,主題個數(shù)選擇30.經(jīng)過建模形成如下2個矩陣,為聚類提供基礎(chǔ).

1)矩陣θ,是一個M×K的矩陣,K是潛在主題的個數(shù),M是文章的數(shù)量.該矩陣表示每篇文章的潛在主題概率分布.

2)矩陣ψ,是一個K×V的矩陣,V是詞袋中詞項的個數(shù),該矩陣表示每個主題的詞項概率分布.

1.3T-OPTICS聚類算法

基于密度的OPTICS聚類算法從一個隨機選定的點開始,向著密度高的區(qū)域擴張,最終形成一個反映所有語料對象可達距離的可視化有序序列,這個有序隊列是所有分析對象的線性表,且代表了數(shù)據(jù)基于密度的聚類結(jié)構(gòu).這個簇排序可以用來提取基本的聚類信息,導出內(nèi)在的聚類結(jié)構(gòu),方便提供聚類的可視化表示.

有序隊列的可達距離圖可以直觀呈現(xiàn)對象的分布.如圖3所示[9]56,以有序隊列的點作為橫軸,點的可達距離為縱軸.其中距離相近的點相互靠近,距離遠的點相互遠離,每一個波谷為一個聚類,每一個波峰為聚類邊界.通過圖像中的下降區(qū)間和上升區(qū)間即可發(fā)現(xiàn)聚類.

圖3　OPTICS算法可達圖Fig.3　OPTICS reachability-plots

話題檢測研究的對象具有時間性,它們都有發(fā)生的先后順序.另外,話題都只持續(xù)一段時間,隨后消失或報道減少[10].所以新聞話題具有時間延續(xù)性,時間間隔越小的新聞談論相同話題的概率越大,時間間隔越大的新聞談論相同話題的概率越小.所以在進行聚類時,充分考慮時間因素對聚類結(jié)果的影響提出了T-OPTICS算法,提高基于密度的聚類算法在新聞話題檢測中的效果.在T-OPTICS算法中,將時間因素加入距離計算公式,如公式(1).

(1)

公式中θ1、θ2為2篇文章的主題概率分布向量,n為2篇新聞發(fā)布時間間隔的天數(shù).利用指數(shù)的變化特點,使新聞間向量距離隨時間間隔變大而增大,并且變化速度隨著時間間隔變大而逐漸變快.這樣就使距離計算公式更加契合新聞話題的時間延續(xù)規(guī)律,利用話題的時間延續(xù)性有效地區(qū)分了內(nèi)容相近但從屬于不同話題的新聞報道.

2實驗設(shè)計及結(jié)果分析

2.1實驗語料及預處理

采用了LDC的TDT4語料庫.TDT4語料庫共包括中文新聞27 142篇,其中2002年被標注的新聞有657篇,涵蓋了37個新聞話題(記作TDT4-2002數(shù)據(jù)集)；2003年被標注的中文新聞有564篇,涵蓋了31個新聞話題(記作TDT4-2003數(shù)據(jù)集).采用中科院的ICTCLAS分詞系統(tǒng)對語料進行分詞操作,并去除停用詞.

2.2實驗設(shè)計

實驗中對文本分別使用LDA和VSM模型建模.使用LDA對文檔進行建模時,迭代400次,將文本表示為30個潛在主題上的概率分布.

實驗分為5組進行,如表1.前4組基用LDA和VSM模型分別使用K-means和OPTICS算法進行聚類,最后1組基于LDA模型使用T-OPTICS算法進行聚類.

表1　實驗分組詳情

2.3評估方法

本文使用準確率PPrecision、召回率PRecall、F1值(F1Measure)作為標準對實驗結(jié)果進行評測.計算公式(2)如下：

(2)

其中,準確率PPrecision表示檢測出的話題中話題隸屬關(guān)系正確的新聞數(shù)與所有檢測出的新聞數(shù)的比值.召回率PRecall表示檢測出的話題中話題隸屬關(guān)系正確的新聞數(shù)與測試集中所有話題的新聞數(shù)的比值.F1值(F1Measure)是準確率和召回率的調(diào)和平均數(shù),綜合了準確率和召回率的效果.

2.4結(jié)果分析

實驗1和實驗2選取數(shù)據(jù)集中話題的實際數(shù)量為聚類數(shù)K,分別對VSM和LDA模型進行10次K-means聚類,取準確率、召回率和F1值的平均值為最終結(jié)果.在實驗4和實驗5中,由于構(gòu)建LDA模型的過程存在抽樣運算,結(jié)果會有小幅浮動,所以進行5次實驗,取平均值作為最終結(jié)果.實驗3、實驗4和實驗5中,參數(shù)MinPts取數(shù)據(jù)集中最小話題包含的新聞數(shù)4.通過實驗產(chǎn)生的可達圖(圖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組實驗的結(jié)果匯總.由表2可以看出,無論在TDT4-2002數(shù)據(jù)集還是TDT4-2003數(shù)據(jù)集中,實驗3的準確率、召回率和F1值好于實驗1,實驗4的準確率、召回率和F1值好于實驗2.由此表明基于密度的OPTICS聚類算法比K-means聚類算法能夠獲得更好的話題檢測性能.

表2　K-means、OPTICS算法效果

2.4.2對VSM模型和LDA模型進行對比

由表2可知,在TDT4-2002數(shù)據(jù)集中,實驗2比實驗1的F1值降低了0.3%,實驗4比實驗3的F1值提高了3.66%；在TDT4-2003數(shù)據(jù)集中,實驗2比實驗1的F1值降低了0.2%,實驗4比實驗3的F1值提高了4.56%.由此可知LDA模型與VSM模型的實驗效果基本相當.但由于LDA模型相對于VSM模型的降維作用明顯,同時OPTICS算法的時間復雜度是O(Kn2),其中K是數(shù)據(jù)維度,由此可知LDA模型比VSM模型時間復雜度得到了明顯降低,算法的運算效率明顯提高.

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

2.4.3對T-OPTICS和OPTICS算法結(jié)果進行對比

為了體現(xiàn)新聞的時間延續(xù)性,實驗5使用了T-OPTICS聚類算法,在實驗4的基礎(chǔ)上加入了時間參數(shù).為了合理的選擇時間參數(shù)的值,選擇區(qū)間1.05～1.2,以間隔0.01分組,共15組系數(shù)分別進行實驗,從結(jié)果圖(圖8、圖9)的2個圖表中可以看出,當選擇適當?shù)臅r間參數(shù)時,帶有時間參數(shù)的實驗效果都好于無時間參數(shù)實驗的結(jié)果.表3是實驗5與實驗4的結(jié)果對比,從表3可以看出,TDT4-2003數(shù)據(jù)集中加入時間參數(shù)后準確率提高了11.9%,召回率提高了2.4%,綜合F1值提高了6.5%,說明時間參數(shù)的加入,使話題檢測的性能得到了較明顯的提高；TDT4-2002數(shù)據(jù)集在加入時間參數(shù)的算法處理后準確率提高了4.1%,召回率下降了0.99%,但代表算法綜合效率的F1值提高了1.35%,說明時間參數(shù)的加入使算法性能得到了一定的提高.

圖8　時間參數(shù)對比圖(TDT4-2002) 圖9　時間參數(shù)對比圖(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實驗結(jié)果總結(jié)

表4是5組實驗的最終結(jié)果.對比可知,使用LDA模型替代VSM模型,在維持實驗性能的同時大幅降低了數(shù)據(jù)維度,從而降低了算法的空間復雜度和時間復雜度,提高了算法的效率.OPTICS算法比傳統(tǒng)的K-means算法在話題檢測中體現(xiàn)了新聞之間聯(lián)系的結(jié)構(gòu),使話題檢測性能大幅提升.對加入時間參數(shù)的T-OPTICS算法的實驗中,實驗性能也得到了一定的提高.實驗表明,本文采用的LDA+T-OPTICS聚類算法與傳統(tǒng)的VSM模型+K-means聚類的方法進行對比,TDT4-2002數(shù)據(jù)集中準確率提高了16.4%,召回率提高了8.1%,F1值提高了11.9%；TDT4-2003數(shù)據(jù)集上準確率提高了34.1%,召回率提高了27.5%,F1值提高了30.7%,大幅提高了話題檢測的性能.

表4　實驗結(jié)果匯總

3結(jié)束語

給出了一種基于LDA模型和T-OPTICS聚類方法的話題檢測算法.本方法通過LDA模型對文本進行表示,體現(xiàn)了文本之間的語義聯(lián)系.同時引入時間參數(shù)的T-OPTICS聚類算法相比傳統(tǒng)基于劃分的聚類算法更加體現(xiàn)了語料中文本之間的邏輯結(jié)構(gòu).算法中時間參數(shù)的加入更好地利用了話題的時間延續(xù)性特點.經(jīng)實驗驗證,使用LDA模型與T-OPTICS的方法相比傳統(tǒng)的檢測方法性能明顯提高.

參考文獻：

[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]卜質(zhì)瓊,鄭波盡.基于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]賀敏,杜攀,張瑾,等.基于動量模型的微博突發(fā)話題檢測方法[J].計算機研究與發(fā)展,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—),男,河北保定人,河北大學教授,主要從事數(shù)據(jù)挖掘與社會計算研究.

中圖分類號：TP391.1

文獻標志碼：A

文章編號：1000-1565(2016)01-0106-07

第一作者：李琮(1987—),男,河北保定人,河北大學碩士研究生,主要從事數(shù)據(jù)挖掘研究.E-mail:licongche@hotmail.com

E-mail：yuanfang@hbu.edu.cn