倪麗萍，劉小軍，馬馳宇

(1.合肥工業(yè)大學 管理學院，安徽 合肥 230009；2.教育部過程優(yōu)化與智能決策重點實驗室，安徽 合肥 230009)

基于LDA模型和AP聚類的主題演化分析

倪麗萍1,2，劉小軍1,2，馬馳宇1,2

(1.合肥工業(yè)大學 管理學院，安徽 合肥 230009；2.教育部過程優(yōu)化與智能決策重點實驗室，安徽 合肥 230009)

隨著互聯網的高速發(fā)展，網絡信息呈現爆炸性增長態(tài)勢，主題演化分析能夠幫助人們從海量的互聯網數據中獲取更有價值的信息。分析主題的演化發(fā)展軌跡有利于人們了解主題事件發(fā)生的前因后果，并對主題事件發(fā)展趨勢進行更好地預測，進而輔助管控。針對單個主題演化分析方法中閾值設定和主題漂移的問題，提出一種LDA-AP主題演化模型。該方法利用LDA模型對不同時間窗口內的新聞文本分別進行建模，得到相應的主題。利用AP聚類算法對不同時間窗口內的多個主題進行聚類，其中計算主題相似度采用加入時間衰減因子的JS散度來度量。最后對多個主題內容進行演化分析。通過相關的實驗分析和對比，結果表明該方法可以改善主題演化的性能，并能較好地分析多個新聞主題事件隨時間的演化趨勢。

多主題演化；時間窗口；LDA模型；AP聚類算法；JS散度

0 引 言

隨著互聯網的發(fā)展，社會化媒體如網絡新聞、微博等已成為發(fā)布事件的主要載體，有效挖掘和分析其中的事件信息有利于幫助用戶及時掌握事件動態(tài)，了解事件趨勢。因此，從社會事件發(fā)生和傳播中有效地挖掘和分析網絡中的事件信息，具有重大的理論意義和實際價值。

美國國防高級計劃研究署(DARPA)于1996年提出了話題的檢測與追蹤(TDT)研究。Allan J等[1]將TDT技術應用到網絡新聞報道流的劃分，并且根據需要不斷建立新的話題類，這是一種無監(jiān)督的增量聚類方法。針對TDT技術新聞報道中只存在單個話題的假設，并且沒有考慮時間因素的問題，國內外研究學者提出了大量的改進方法。Wang等提出了TOT(Topic Over Time)模型[2]，將時間信息加入到可觀測的變量中，使得詞的生成不僅受到主題限制，還受時間屬性的影響。這種模型在不同時間窗口上的主題強度演化方面取得了較好的結果，但是TOT模型沒有考慮到主題內容在時間窗口上的演化。隨后Al-Sumait等提出OLDA(Online Latent Dirichlet Allocation)模型[3]，該模型使用演化矩陣來記錄以前的模型結果，而演化矩陣能夠記錄主題的變化，并且通過計算連續(xù)時間窗口內主題的相對熵來表現話題內容上的變化，但是OLDA容易導致主題混合和主題邊界模糊。Elshamy等提出了ciDTM(continuous-time infinite Dynamic Topic Models)模型[4]，該模型提出在連續(xù)時間序列上的可變主題數和可變主題結構的主題演化模型，解決了OHDP(Online-Hierarchical Dirichlet Process)只依賴文檔到達順序而不能通過文檔時間戳進行建模的缺點。

國內學者近年來在主題演化方面的研究也取得了一定的進展。胡艷麗等定義了子話題的產生、消亡、繼承、分裂和合并，并對不同模型的困惑度進行了對比分析[5]。單斌等將基于LDA的話題演化技術分為三種:直接把時間作為觀測變量引入模型、按時間后離散和先離散方法[6]。李保利等提出過濾無意義話題，避免無意義話題對主題演化產生負面影響，并借助啟發(fā)式規(guī)則從主題強度和內容進行分析，研究科技文獻隨時間的演化趨勢[7]。

綜上，上述研究方法存在以下不足：通常是對單一事件演化的檢測，即上述方法往往根據主題詞的概率進行相似度關聯，因此通常都是對單個主題的演化分析；在相似度判斷上往往需要設定閾值。

針對以上問題，文中將聚類思想引入LDA主題模型演化中，并以新聞文本為實驗材料，闡述了如何使用LDA模型和AP聚類算法對新聞文本主題特征演化進行分析。

1 基于LDA-AP的主題演化模型構建

隨著事件的動態(tài)發(fā)展，事件主題的內容往往會發(fā)生遷移，如何描述多個主題的演化關系以及內容變化是目前的研究熱點。潛在狄利克雷分布(Latent Dirichlet Allocation，LDA)模型本身具有主題建模能力，在主題演化方面具有先天優(yōu)勢?；贚DA模型和AP聚類的主題演化模型的基本思想是：首先通過LDA模型從不同時間窗口內的大量新聞數據中獲取抽象的主題信息，再利用AP聚類算法對不同新聞主題發(fā)表時間窗口中提取的特征詞匯構建關聯。其中用JS散度對新聞主題內容相似度進行衡量，利用AP算法將相似度大的新聞聚為同一簇主題，并利用主題強度的衰減性連續(xù)性地在不同時間窗口中分析主題的強度變化和主題內容的覆蓋情況。最后通過實驗驗證方法的有效性。

1.1 基本框架

(1)把新聞文本集Dm按時間窗口t劃分為多個子文本集DSi(i=1,2,…,T)；

(2)基于Gibbs抽樣對DSi求LDA模型參數，確定每個時間窗口的主題個數和主題-詞概率；

(3)利用AP聚類算法建立主題關聯，使用JS散度度量不同時間窗口間的主題距離，并加入衰減因子；

(4)根據聚類結果，分析主題的強度變化及內容演化的過程；

(5)利用TDT評測方法對文中方法和基準方法的主題演化結果進行評測。

文中時間窗口t設置為1天，在每個時間窗口內進行LDA主題建模，然后按照時間順序把時間窗口的主題進行關聯分析?；贚DA和AP聚類算法的主題演化步驟如圖1所示。

圖1 主題演化檢測框架

1.2 LDA主題模型

LDA模型由Blei等在2003年首次提出，基本思想是將每一篇文檔看作為一些相互關聯的話題所構成的概率分布，而將每一個話題看作為一些單詞所構成的概率分布，使用隱含的話題將文本與詞進行相互關聯，從而使文本從高維的詞匯空間降到低維的話題空間，解決了傳統(tǒng)的向量空間模型的維數災難問題[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抽樣在困惑度與運行速度等方面均優(yōu)于變分貝葉斯推理算法，成為主題模型中最常用的參數估計方法[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發(fā)送到候選聚類中心點xk的消息，即元素值的大小說明點xk適合作為點xi的聚類中心的程度；歸屬度矩陣A中的元素a(i,k)是由候選聚類中心點xk發(fā)送到點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進行下一次迭代之前需要對其進行縮放?？s放的方法是引入阻尼因子lam，具體如式(5)所示。

(5)

其中，lam為一設定的值；Rold和Aold表示上一次迭代的結果。

綜上，AP聚類算法的過程為：

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

Step2：設置最大迭代次數n，以及聚類中心穩(wěn)定次數m。

Step3：迭代執(zhí)行Rold=R，Aold=A；根據式(2)和式(3)計算R和A；根據式(4)對R和A進行縮放。

Step4：如果迭代次數大于n或者聚類中心穩(wěn)定次數大于m時，則結束迭代操作，執(zhí)行Step5。

Step5：當r(i,i)+a(i,i)>0時，選取該點作為聚類中心。

Step6：將剩下的數據點與聚類中心相比，并將它們分配到最近的聚類中心。

從上面的算法過程中可知，相似度矩陣S是AP算法的重要參數，文中如果相似度矩陣S能夠準確地反映出主題之間的相似關系，則AP算法就能較好地發(fā)現主題的關聯關系。

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)

一般來講主題報道會持續(xù)一段時間，所以兩個主題之間的時間距離越小，它們屬于同一事件的可能性越大；反之時間距離越大則兩個主題屬于同一事件的可能性越小。因此，文中在JS距離中引入時間衰減模型來設計聚類機制，定義一個衰減因子λ使主題概率的相似度隨時間衰減，衰減因子定義為：

(8)

其中，Timez1和Timez2分別表示主題z1和z2的報道時間，當兩個主題間隔的時間越長，λ值越小。

最終相似度計算公式為：

(9)

JS散度的區(qū)間為(0,1]，兩個主題的JS散度越小，相似度就越大，關聯的可能性也越大。即根據AP算法將相似的兩個主題聚為一個簇，就判定不同時間窗口內的兩個主題在內容上具有繼承關系。如果一個時間窗口內的主題在下一個時間窗口沒有相同的聚簇，則認為該主題事件在上一個時間窗口消亡。反之，如果一個時間窗口內的主題在上一個時間窗口沒有相同聚簇，則判定該事件在這個時間窗口是新生事件。

1.4.2 主題強度的度量

(10)

其中，M表示新聞報道數。

根據θt計算每個時間窗口內文本中的主題強度值，繪制主題強度隨時間的變化趨勢圖。

2 實驗及結果分析

2.1 實驗環(huán)境

實驗是在CPU為Intel@Core(TM)i5-4590 3.30 GHz、內存為4 GB、操作系統(tǒng)為Windows 7旗艦版(Service Pack 1)的PC機上運行。

2.2 數據描述

文中使用的新聞數據抓取自新浪新聞、網易新聞、中國新聞網、人民網、鳳凰資訊。抓取工具使用Python編寫的網絡爬蟲程序，抓取了從2013年11月01日到2013年11月30日共計約30萬條新聞正文內容，并將新聞語料庫時間間隔設置為1天，劃分到30個時間窗口。

2.3 實驗設置

由于新聞文本數據字符集較大,詞長較短的特點，采用Python的結巴分詞；針對新聞實驗語料庫的特點，文中將哈工大停用詞表進行擴充，加入一些新聞語料庫特有的詞，如“記者”“報道”等出現頻率高且對實驗結果沒有意義的詞語，通過去除這些停用詞提高后續(xù)分析的準確性。

對新聞文本主題建模時，采用Gibbs抽樣算法推導LDA后驗參數ψk和θm。首先需確定LDA主題模型中3個變量(Dirichlet分布中的超參數α、β及主題數目T)的最佳值。相關文獻表明β=0.01時實驗效果較好，α=50/T[12]。根據困惑度確定最優(yōu)主題數，實驗表明當主題數設為10時困惑度值最小，因此每個時間窗口最優(yōu)主題數目為10，同時設定每個主題下關鍵詞的提取個數為10。

2.4 主題內容聚類演化結果與分析

根據圖1的主題演化基本框架進行計算，可得到如表1所示的主題演化結果。限于篇幅，此處僅列舉11月9日到11月12日的部分活躍主題，其中活躍主題中的主題詞概率從大到小依次輸出，并選取每個主題包含的概率排在Top8的關鍵詞作為主題的代表。

表1 新聞主題演化結果

2.5 主題強度的結果與分析

通過LDA模型可以獲得不同時間窗口中新聞主題的主題-詞匯概率分布以及主題在不同文檔上的概率分布，從而分析主題強度隨時間的演化情況。以主題“恒大俱樂部奪冠”、“淘寶雙十一購物節(jié)”、“臺風海燕”為例，按照1.4.2節(jié)中主題強度的計算方法分析其2013年11月的演化情況，如圖2所示。

圖2 主題強度演化圖

圖中展現了主題強度隨時間的變化趨勢。從圖中可以看到，恒大奪冠的主題是在11月份一直存在，而在11月9日恒大俱樂部奪冠后出現頂峰，在奪冠后強度緩慢減弱但沒有消亡，說明恒大俱樂部在11月份不斷被關注。雙11購物節(jié)每年在固定時間發(fā)生，持續(xù)時間較短，從圖2中可以看到“淘寶雙11購物節(jié)”在11月10日和11日比較熱門，在11月12日之后迅速減弱，持續(xù)時間較短。而臺風“海燕”在11月8日之前基本沒有報道，而在11月8日臺風海燕登陸菲律賓后才突然出現報道，之后再在11月11日登陸廣西，在11月14日出現的只有菲律賓，慢慢減弱。從圖中不難發(fā)現，恒大俱樂部屬于持續(xù)較長的事件，而雙11購物屬于定點時間出現高峰并迅速減弱的事件，而臺風海燕屬于突發(fā)事件，這與上述分析的主題內容演化趨勢也是基本吻合的。

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作為評測系統(tǒng)性能的指標，值越小說明系統(tǒng)性能越好。

為了檢驗文中提出方法的有效性，對LDA的主題建模結果進行人工標注，根據上述評測方法，評測結果如圖3所示。

圖3 實驗對比結果

從圖3中可以看出，文中方法與Baseline方法相比，漏報率、誤報率以及歸一化開銷都有了一定程度的降低，體現出一定的有效性。

以“淘寶雙十一”主題為例，Baseline方法和文中算法演化內容見表2。

表2 “雙十一購物節(jié)”的主題內容演化對比

從表2中可以看到，文中的LDA-AP-衰減方法和Baseline方法都是從11月8日開始檢測到雙十一購物主題事件，而Baseline方法在11月9日得到的主題演化結果中并沒有關聯到“淘寶雙十一”的主題事件，而文中的LDA-AP-衰減方法在11月9日關聯到了關于互聯網購物方面的主題?？梢钥闯?1月9日也是議論關于互聯網購物節(jié)的主題，只是出現“雙十一”和“淘寶”關鍵詞的概率較小，導致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].小型微型計算機系統(tǒng),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] 賀 亮,李 芳.基于話題模型的科技文獻話題發(fā)現和趨勢分析[J].中文信息學報,2012,26(2):109-115.

[13] 鄭 燕,魯 燃,趙愛華.基于反饋報道的話題模型動態(tài)修正方法[J].計算機應用,2012,32(5):1343-1346.[14] 魏景璇,魯 燃,張艷輝.基于動態(tài)閾值和命名實體的雙重過濾話題追蹤[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