基于在線層次化非負矩陣分解的文本流主題檢測

涂 鼎, 陳 嶺, 陳根才, 吳 勇, 王敬昌

(1.浙江大學 計算機科學與技術學院,浙江 杭州 310027； 2.浙江鴻程計算機系統有限公司,浙江 杭州 310009)

?

基于在線層次化非負矩陣分解的文本流主題檢測

涂 鼎1, 陳 嶺1, 陳根才1, 吳 勇2, 王敬昌2

(1.浙江大學 計算機科學與技術學院,浙江 杭州 310027； 2.浙江鴻程計算機系統有限公司,浙江 杭州 310009)

針對文本流主題檢測中存在的主題結構扁平問題,提出在線的層次化非負矩陣分解方法,在每個時間片中根據歸一化累計折損增益選擇主題節點進行分解,接著反復將文檔分配給最相關的主題節點構建主題層次,該過程中假設主題在由不同時間片中相似主題節點構成的序列中連續再演化,在當前時間片對主題節點進行分解時考慮過去時間片中主題節點的分解結果.該方法不僅能在線的發現和更新文本流中的主題,而且還可揭示主題間的結構關系.在Nist TDT2數據集上的實驗結果表明,該方法在NMI、Micro F1、MAP和NDCG等指標下均顯著超過了其他動態NMF方法,并在時間效率上顯示出一定優勢.

動態主題模型；層次聚類；非負矩陣分解

在持續的文本流中去檢測潛在的主題是典型的主題發現和跟蹤場景(topic detecting and tracking, TDT)[1-6].自動從大量文檔流中去發現其中一些有意義的主題模式或者跟蹤其中主題內容的變化在許多應用領域具有重要意義,如社交網絡、新聞熱點分析等.

近年來,對于文本主題的發現和跟蹤受到國內外研究者的廣泛關注.其中比較重要的一類方法是基于主題模型的方法[7-9],這類方法通常將主題描述為在詞表上的一個多項式分布,而文檔則是這些主題的一個混合.傳統主題模型通常是靜態模型,因而無法滿足在流式數據中挖掘主題的需要.針對該問題,學術界提出了各種動態主題模型,旨在準確捕捉文本流內容的動態演化特征.根據建模方法的不同,現有動態主題模型方法主要可分為2類：第1類方法基于概率模型去發現文本流中的主題[1-3].第2類方法則是基于字典學習(dictionary learning)或者非負矩陣分解(nonnegative matrix factorization, NMF)[4-6].與基于概率模型的方法相比,基于矩陣分解的方法通常消耗更少的時間.

現有大多數基于NMF的動態主題模型方法將各個潛在主題視為獨立的元素,忽略了各個主題的交集和其間的關系,因而限制了這些模型的表達能力.層次結構是克服這一缺陷的可行方案[10-14].然而,現有層次主題模型[10-14]中大部分方法都是靜態模型,無法滿足檢測文本流中主題的要求.目前,僅有Hu等[14]對在線層次主題模型進行探索,但該文中生成的主題層次不滿足傳統主題層次中子節點是父節點的子集這一假設.

針對上述問題,本文提出了一種在線層次NMF框架(online hierarchical NMF,OHNMF).OHNMF在每個時間片中根據歸一化累計折損增益選擇主題節點進行分解,接著反復將文檔分配給最相關的主題節點來構建主題層次,該過程中對主題節點進行分解時考慮過去時間片中主題節點的分解結果,實現主題在由不同時間片中相似主題節點構成的序列中的連續演化.該層次化劃分方法不僅能對文檔流中潛在主題的變化進行在線跟蹤,也能發現各個主題之間的結構關系的變化.

1 基于OHNMF的在線主題檢測

假設某個時間片t內輸入的m×n維文檔矩陣為Xt,其中m為整個詞表的維度,n為整個矩陣中文檔的數量.基于矩陣分解的主題模型中的一個常見假設是一個潛在主題可以看作是在詞表上的分布,即一個主題就是在Rm空間里的一個列向量w.通過將k個主題向量水平組合起來可以得到一個m×k維的主題-詞矩陣Wt,k為主題數目.每一列代表一個主題.除主題-詞矩陣之外,模型中另一個矩陣就是主題-文檔矩陣Ht.Ht中的每一列表示一個文檔在所有主題上的分布.在基于矩陣分解的主題模型方法中,通常使用WtHt去近似文檔矩陣Xt.由于在Wt和Ht中出現負數將無法解釋各項分布的物理含義,在求解Wt和Ht時需要加上非負約束.這樣,一個主題檢測問題就可以轉化為一個非負矩陣分解問題：給定一個主題數目k和一個時間片內的m×n維文檔矩陣Xt,目標是找到一個m×k維主題詞矩陣Wt和一個k×n主題-文檔矩陣Ht,滿足以下條件:

(1)

1.1 在線稀疏NMF

本文所提方法是基于在線稀疏非負矩陣分解(online sparse NMF,ONMF),由在線稀疏字典學習(online sparse dictionary learning)[4]加上非負約束后擴展而成.稀疏NMF與基本NMF的區別在于稀疏NMF在目標函數中引入了稀疏性約束.引入稀疏性約束可增強分解結果的可分離性.通常稀疏性約束是加在主題-文檔矩陣Ht,即保證每篇文檔在各個主題上的分布只集中在少數主題上.加入稀疏約束后,原目標函數變為

(2)

這里是將Ht的L1范數作為稀疏約束加入到目標函數中,λ為稀疏約束的權重系數.通過引入稀疏性約束,目標函數可以保證從所有可能分解結果中找到高質量的具有較少重合的那些潛在主題.層次化劃分方法通常假設同一父節點的子節點的數據是完全分離的或者具有較少重合.通過引入稀疏性約束,NMF的結果可以更好地滿足構建主題層次的需求.

動態主題模型的特點是可根據當前新到的數據Xt對原有主題Wt-1進行調整,使得當前主題Wt既能滿足歷史數據X0-Xt-1的分布,也能適應現有數據Xt的情況,即滿足如下目標函數：

(3)

式中:j為t之前的任意時間片,這里Hj為第j個時間片的主題-文檔矩陣,Xj為第j個時間片的文檔矩陣.該目標函數在求解Wt時既考慮了對當前時間片文檔集的擬合,也考慮了對以前所有時間片文檔集的擬合,保證了主題-詞矩陣Wt-1和Wt的平滑過渡.σ(t,j)為時間尺度函數,其根據t和j之間的時間間隔來調整j時間片數據在當前分解過程中的權重.通常其是一個指數函數,如σ(t,j)=αt-jα≤1.過去越久的數據會獲得更小的權重.

式(3)中的目標函數可用更新算法1來求解.在第3步,使用LARS-Lasso得到當前最優的hi.第4步中根據xi和hi更新輔助矩陣A和B.A和B矩陣是分解輔助矩陣,可看作用于存儲過去分解過程的中間結果,即與xi和hi相關歷史信息.β為時間尺度系數,替代σ(t,j).其意義為每新到一個文檔,之前所有文檔的權重變為原來的β倍,β的取值范圍為0～1.第5-12步根據A和B更新W每一列直到收斂為止.算法收斂性分析可見[4].如果沒有之前分解結果,可隨機初始化W,并將A和B初始化成全為0的矩陣.通過算法1中的優化更新規則,可動態得到最新的W,然后通過LARS-Lasso計算得到當前時間片的H.

算法1 在線更新主題-詞矩陣

輸入: 文檔矩陣Xt=[x1, x2, x3,…, xn],上一次分解結果中的m×k維主題-詞矩陣Wt-1,L1正則化約束的系數λ,分解輔助矩陣A∈Rkxk,B∈Rmxk

1. W←Wt-1

2. For xi∈Xt

3. 使用LARS-Lasso [4]找到滿足條件的hi

5. W=[w1, w2, w3,…, wk] A=[a1, a2, a3,…, ak]

B=[b1, b2, b3,…, bk],target=1

6. While target沒有收斂

7. Forj=1 tok

8. wj=(bj-Waj)/A[j,j]+wj

10. End For

11. target=Tr(WTWA)/2-Tr(WTB)

12. End While

13. End For

輸出：當前時間片的主題-詞矩陣W

1.2 OHNMF整體流程

圖1 OHNMF整體流程Fig.1 Overall process of OHNMF

基于ONMF的OHNMF方法的整體流程如圖1所示.在時間片t=1,系統執行一個基本的層次化NMF方法并且生成一個主題層次.在層次化NMF的過程中,系統首先將該時間片內的所有文檔X放到根主題節點中并進行一次矩陣分解.將生成的主題-詞矩陣Wr的每一列作為該根主題節點子節點的主題向量,并且根據Hr將文檔分配到各個子主題節點中.對于文檔xi,存在對應的文檔-主題向量hi∈Hr,hi中最大值所對應的主題節點即xi被分配到的節點.然后找到可分性(2.3節)最高的葉節點進行同樣的分解過程,該過程反復迭代直到滿足特定終止條件：1)葉節點的數量達到預先定義的主題數目k,該條件一般用以防止層次化過程迭代過多；2)所有葉節點均不可分,即該節點中所有文檔都集中于某一個主題.

所有文檔將沿著主題層次中的路徑劃分到各個葉主題節點中.主題層次中的每個主題節點都可以表達為一個主題向量w,并且包含一個集合D記錄所有劃分路徑經過該主題節點的文檔.在生成主題層次的同時,系統還為每個主題節點存儲了輔助矩陣來記錄該主題節點的歷史分解信息,即算法1中的輔助矩陣A和B.

在下一個時間片,參考上一時間片分解的歷史信息生成一個新的主題層次,該階段OHNMF算法偽代碼如算法2所示.在根主題節點處,所有當前時間片的文檔矩陣Xt將結合上個時間片根節點的Wt-1,At-1,和Bt-1進行分解(1～4步).對于非根節點w的分解過程(9～13步),其首先找到在上一個時間片最相關的主題節點wr(10步).然后結合wr過去分解的信息對w進行在線分解(11步).例如,在圖1中,w2在分解時考慮了在上個時間片與其最相似的w1的分解信息.相似的關系也存在于w3和w2之間.整個流程可以看作主題w1在一個由D1、D2和D3組成的文本流中經過w2演化成w3.這樣,本文方法可以追蹤主題的演化過程.對于那些在過去時間片未能找到相關主題的主題節點,將被視為新出現的主題并進行獨立的分解.

算法2 在線更新主題層次

3. W=ONMF (Xt,λ,A,B); 并將W存儲在數組lw,將W和當前的輔助矩陣保存到SW′和輔助矩陣的集合 SA′, SB′中

4. 計算W子節點的mNDCG乘積并存儲在數組lm

5.n=n+1;

6. Whilen0

7. 找到下一個待分解主題節點w,其子節點mNDCG乘積最大.并從lw中取得其主題-詞矩陣W和所屬文檔矩陣X

9. For wi∈w1, w2

10. 生成當前節點摘要si,找到在上一個時間片擁有最相似摘要sj的主題節點wj

11. 重復2～4步.如果沒有找到相似節點,則視其為一個全新節點的分解.

12. EndFor

13.n=n+1;

14. End While

輸出:t時間片的所有節點的主題-詞矩陣的集合SW′和輔助矩陣的集合 SA′, SB′

1.3 OHNMF細節

每個節點處的主題-文檔矩陣W的維度被設置為m×2,即每個主題節點包含2個子主題節點,這樣設置有以下幾點好處：1)在二叉樹中將數據劃分給某個子節點會比比較容易.2)整個計算過程將會被加速.通常NMF的優化求解時間至少與潛在主題數目k成線性相關.通過分析可以得到在這種設定下,每個主題節點的分解過程將被加快.假設一個新文檔的在ONMF的分解過程中消耗k個時間單位,那么在有k個葉節點的OHNMF中其過程將消耗2(log2k+1)個時間單位.如果最終整個葉節點的數目較大,那么節省的時間比例是相當可觀的,即(k-2 log2k-2)/k.

在每一次迭代過程中,OHNMF選擇可分性最高的葉節點作為下一個分解的節點.這里使用經過修改的歸一化累計折損增益[10](modified normalized discounted cumulative gain,mNDCG)作為衡量節點可分性的標準.NDCG可以比較一個系統生成的排序與目標排序之間的一致性.根據每個主題向量中各個詞的權重可以生成主題中詞的一個排序,這樣可以通過比較父主題節點和子主題節點中詞的排序來得到其間的一致性.假設父節點的排序為

fP=f1,f2,f3, …,fm,2個子節點的排序為fL=fl1,fl2,fl3, …,flm,fR=fr1,fr2,fr3, …,frm那么其mNDCG可計算為

g(fi)=

log (m-i+1)/log (m-max (i1,i2)+1).

(4)

(5)

mNDCG(fS)=mDCG(fS)/mIDCG.

(6)

式中：mDCG為改進的累計折損增益(modified discounted culmulative gain), mIDCG為改進的理想累計折損增益(modified idea discounted culmulative)i1,i2即父節點中排序在第i個位置的詞在2個子節點中的排序.fS可以是fL或fR.mIDCG即父節點的mDCG值.mNDCG除考慮了父節點與子節點的相似度之外,還引入了2個子節點之間的差異性.算法在每生成一個新的主題節點時,都會對其進行一次預分解以獲得其mNDCG值,并將2個子節點mNDCG的積作為評價分數,越大的可分性越高.2個子節點之間差異越大且都與父節點相似的那些父節點將獲得更高的分數.如果該節點中所有文檔幾乎都分到同一個子節點中,其分數將被設為-1,即新節點主要由一個主題的文檔構成且不需要進一步分解.

為了跟蹤主題的演化過程,在2個時間片t和t-1中具有高相關性的主題wi、wj被視為在2個不同時間片里的同一個主題.如果wi、wj的相似度大于特定閾值,那么t時間片里的主題節點wi可能由t-1時間片的主題節點wj演化而來.為了描述連續時間片中2個不同主題節點wi、wj的相似度,首先需要得到這些主題節點的摘要以減少平凡詞的影響.一個主題的摘要s由與該主題最相關的nr個詞的詞頻信息所構成.詞與主題節點w的相關程度由該詞在該主題節點所有文檔的TF-IDF值決定.這樣主題節點的摘要即TF-IDF最高的前nr個詞詞頻的平均值.其他詞的詞頻被設置為0.給定2個主題節點的摘要si,sj,其之間的相關程度可以由余弦值得到

(7)

如果t-1時間片中存在與當前主題節點wi相似度大于一定閾值的主題點節點,即可認為當前主題節點是由t-1時間片中與當前節點相似度最大的主題節點wj演化而來,可利用其分解結果指導當前節點wi的分解過程.

基于NMF的方法中,矩陣初始化一直是影響分解結果的關鍵因素.由于ONMF在初始幾次迭代中將以較大的步幅更新W,其對于初始的幾個文檔數據分布比較敏感,可以通過恰當的初始化解決這種問題.在分解一個節點的數據X時,如果沒有找到之前相似的節點,則首先對其進行kmeans聚類來得到2個類,然后將這2個類的中心作為初始的主題-詞矩陣W0,同時設置A0=t0I,B0=t0W0,t0是常量,這里可以看作當前分解是在另一次分解之后進行的,該次分解得到的主題-詞矩陣是W0,且記錄的分解輔助矩陣是A0和B0.因為A0和B0決定了更新時的步幅,這樣設置避免了ONMF對于初始數據敏感的問題.

2 實驗與分析

在實驗部分本文方法將與其他現行方法進行比較,并且采用多種標準來衡量實驗結果以驗證本文方法的有效性.所有實驗均運行在MATLAB R2014a 環境中,運行機器配置為Intel Pentinum G3220處理器和24G內存.

2.1 數據集

本文實驗是在Nist主題檢測和跟蹤文檔集(nist topic detection and tracking corpus, TDT2)上進行的[15].該文檔集中包含1998年上半年從6個數據源中所采集到的11 201個文檔,包括2個新聞專線(APW,NYT),2個廣播節目(VOA,PRI),和2個電視節目(CNN,ABC).所有文檔被劃分到96個語義類別中.在本文實驗中,所有屬于2個及以上類別的文檔都被去除并且只保留最大的30個類別,共9 394個文檔.去除停用詞后詞表大小大約為36 000.

對于每一個不同的主題數目k,實驗中都會在此設定下生成50個TDT2的采樣子集.比如當k=2時,所有方法將會在只包含2類文檔的50個采樣子集上運行一遍并比較結果.為了滿足實驗對時序性的要求,所有采樣子集中的數據都根據時間進行了重新排序(原始數據是根據類別標簽排序).為了提高性能并且加速運行過程,在預處理時對文檔進行了降維.對于每一個子集,詞表大小被壓縮到原來大小的40%,如每一個子集在去除掉頻率為0的詞之后詞表的大小大約為10 000～20 000,按照TF-IDF值對所有詞進行排序,取最大的前40%作為最終的詞表.所有文檔都根據其長度進行了歸一化以減少文檔大小對實驗建模的影響.

2.2 實驗評價標準

采用4種標準評價實驗中各種方法的效果：

歸一化互信息(NMI)：NMI是一個廣泛使用的聚類質量評價標準.在生成的聚類數目與真實聚類數目不同時具有一定優勢,并且可以用于決定最優的聚類數目.對于數據的2個不同劃分而言,越高的互信息值代表著這2種劃分之間有更高的相似度,其計算公式為

(p(x)p(y)))/(H(X)+H(Y))

(8)

式中:X,Y分別為對數據集的2個不同劃分,H(X)為分布X的熵.p(x)、p(y)和p(x,y)分別為x的分布概率、y的分布概率和x、y的聯合分布概率.

微平均F1值(Micro averaged F1,MicroF1)：這是另外一個廣泛使用的用于衡量聚類質量的評價標準.與歸一化互信息相比較,微平均F1在聚類數目較大時能夠更準確地衡量聚類方法的性能.假設在聚類結果中一共生成了k個聚類且所有文檔的真實標簽為1到l,即真實聚類為l個.那么對于每一個真實聚類Ci可以從聚類結果中發現一個結果Cri,滿足Cri與Ci的交集所含數據點最多,那么最終的微平均F1可以通過如下公式計算得到

(9)

(10)

F1=2PR/(P+R).

(11)

式中：R和P分別為召回率和準確率.召回率和準確率的計算與微平均F1中相同.

中間平均準確率(mean average precision, MAP)：微平均F1值從單點值的角度衡量聚類性能.而中間平均準確率則是從宏觀角度去評估聚類方法的性能,計算公式為

(12)

最終所有50個數據子集的實驗結果被用于計算中間平均準確率.

歸一化累計折損增益(normalized discounted cumulative gain, NDCG)：歸一化累計折損增益通常用于衡量發現的主題的質量.對于每一個真實主題都可以生成一個所有屬于該主題的文檔向量的平均向量.然后從生成的聚類結果中找到一個與真實主題交集最大的聚類,計算真實主題平均向量與屬于該聚類的主題向量之間的NDCG值,越大說明發現的主題質量越高.主題中概率最大的前N個詞的NDCG為

NDCG=DCG/IDCG

(13)

式中：r(j)為第j個詞與真實主題分布的相關性,DCG為累計折損增益(discounted culmulative agin), IDCG為理想累計折損增益(idea discounted culmulative gain), IDCG即可能的最大DCG值.

2.3 實驗對比方法

為了能夠更好地評估本文所提方法,實驗中選取了5種基準方法：

fix-NMF-L1: fix-NMF-L1只在第1個時間片的數據上執行NMF分解并且在后來的時間片中不再改變各個潛在主題向量的分布.該NMF算法的實現是基于L1稀疏約束和乘法更新規則的[16].

t-NMF-L1:t-NMF-L1使用與fix-NMF-L1相同的NMF實現.區別在于t-NMF-L1在時間片t使用Wt-1作為初始化矩陣,即用上一個時間片的主題-詞矩陣Wt-1作為t時間片的初始化主題-詞矩陣.

Hie-NMF-L1：Kuang等[10]提出的Hie-Rank2方法可以通過反復執行rank2-NMF實現文檔的層次化聚類.rank2-NMF是一種基于活動集(active-set)的快速NMF算法,其秩k設為2.為了提高Hie-Rank2算法的效果,rank2-NMF被替換成了NMF-L1.在每一個時間片都會執行一次Hie-NMF-L1.

JPP: JPP[6]是一個基于時間的協同矩陣分解算法,可以發現文本流之中的潛在主題.其在目標函數中考慮了之前時間片的分解結果和當前時間片分解結果之間的差異.通過在目標函數中加入這種約束,其可以實現平滑的主題發現.

ODL: ODL[4]是一個在線字典學習方法.在本實驗中其目標函數里加上了非負限制.

實驗中每個時間片窗口大小被設為500個文檔,本文方法在時間尺度函數上使用的是基于文檔數的權重調整,所以在實驗中將文檔數目固定比較好觀察不同時間尺度函數參數的影響.其基本與每個子集中一個月內的文檔數量相同.對于所有添加了L1約束的方法,其系數λ均被設為0.01.根據文獻[17],λ最好設置為m-1/2,即在本實驗中設置為0.01.所有方法的最大迭代次數都被設為1 000.

OHNMF中每一個聚類所能包含的最小文檔數設為5.ODL和OHNMF中的時間尺度參數β被設為0.999 5,即第(n-500)文檔的分解結果對第n個文檔分解的權重約為0.8.摘要詞表的大小nr被設為100.主題相關度的閾值被設為0.7,即前后2個時間片如果存在相似度超過0.7的主題節點即可認為這2個節點在時間上是連續變化的.原因是該值要大于0.5且小于1,所以本文選擇了一個略小于0.5和1的平均值的值.JPP和Hie-NMF-L1中其他參數的設置均與各自論文中設置相同.余下所有實驗的參數設置如無特別說明均與以上參數設置相同.所有方法均使用kmeans方法得到初始的主題-詞矩陣.

2.4 主題質量

本實驗中對比了不同k(k=5、10、15)設定下各種方法發現主題的質量.實驗數據的詳細信息如表1所示.實驗中所對比的6種方法的結果如表2所示.

表1 抽樣后的Nist TDT2數據統計信息

表2 各主題檢測方法在Nist TDT2上的主題質量對比

從表2可以看出：fix-NMF-L1在6個方法中表現最差,原因很簡單：在不同時間片之間主題-詞的分布和主題-文檔的分布是不斷變化的,用固定的模型去檢測構成文檔的潛在主題自然不會取得較好的效果.在某種程度上t-NMF-L1可以看作是一個在線分解模型,因為相鄰2個時間片的主題-詞矩陣之間存在一些“一致性”(從下一個實驗中可以看到這一點).但是這種相鄰2個主題-詞矩陣之間的“一致性”并沒有像其他在線方法那樣嚴格的定義到目標函數中,所以其效果不如其他3個在線分解方法.

3個在線分解方法：JPP,ODL和OHNMF在本實驗中表現出了較好的性能.JPP方法獲得了較高的MAP值,而ODL獲得了較高的微平均F1值.在所有對比方法中,本文所提方法獲得了最好的效果,原因是本文方法在層次劃分過程中將屬于不同主題的文檔的主要部分較好地分隔開了,減少了他們之間在在線分解時可能存在的影響,從而提高了所獲得的主題的精度.由于這樣所獲得的結果比較穩定,所以不會出現ODL或者JPP這樣只在某項指標上會表現比較好的情況.

在層次化NMF類的方法的對比中,OHNMF要優于Hie-NMF-L1.原因是OHNMF可以用過去時間片的分解結果來指導當前時間片的分解過程,可以獲得全局更優的分解結果.而Hie-NMF-L1只能根據當前時間片的文檔來進行分解過程.實驗中同樣評估了Hie-NMF-L1的原始形式Hie-Rank2.在本文實驗場景中Hie-Rank2沒有取得很好的效果,相比于Hie-NMF-L1,其各項指標的分數下降0.1.對于OHNMF而言,如果不添加L1稀疏性約束,其在某些指標上同樣會出現0.05的下降.原因是層次化過程中將會放大劃分時的錯誤.所以在每個主題節點的分解過程應該越準確越好.通過加入L1正則化約束,OHNMF可以找到更稀疏的主題表達,這樣屬于不同主題的文檔就能夠被更好的劃分開.

實驗中同樣可以觀察到NMI的值基本上隨著k的增大而增大(MicroF1和MAP在隨著k的增大而減小),部分說明在聚類數據較大時NMI不能較好的衡量聚類效果.

2.5 主題平滑度

本實驗中評估了相鄰2個時間片中主題-詞矩陣之間的平滑度.Wt-1和Wt之間的平滑度可以通過如下方法計算：

(14)

(15)

(16)

表3 各主題檢測方法在Nist TDT2上的主題平滑度對比

因為在主題檢測的過程中主題-詞矩陣一直沒有發生變化,所以fix-NMF-L1方法的主題平滑度是1.排除在線學習因素的影響,扁平分解方法相對于層次分解方法能獲得更高的主題平滑度.原因可能是對于一些處于主題聚類邊界上的文檔,扁平分解能夠獲得較高的一致性,而層次分解可能根據當前數據對其有一定的調整.t-NMF-L1表現的比Hie-NMF-L1好的另外一個原因是t-NMF-L1是一種半在線的方法,其每次使用上一個時間片的主題-詞矩陣作為當前分解的初始化矩陣.OHNMF獲得了第2高的主題平滑度,時間參數β和主題相關度的閾值將會影響到主題平滑度.額外實驗表明本文方法設置更大的β和更小的閾值都可獲得更加平滑的主題.

2.6 運行時間

本實驗對比了各個方法的運行時間.所有方法的默認數據設置是文檔數n=2 000,主題數k=10,詞表大小m=4 000.運行時間為10次運行的平均時間.所有方法中的窗口大小均設置為與文檔數目n相同.各個方法在不同m、k和m設置下的運行時間t如圖2～4所示.

圖2 各方法在不同文檔數目下的運行時間Fig.2 Computation time of all methods under different document numbers

圖3 各方法在不同主題數目下的運行時間Fig.3 Computation time of all methods under different topic numbers

圖4 各方法在不同詞表大小下的運行時間Fig.4 Computation time of all methods under different vocabulary sizes

從實驗結果中可以看出ODL和OHNMF花費了最少的運行時間.從圖2中可以看出,隨著文檔數n的增長運行時間的變化,Hie-NMF-L1和JPP的時間增長的最快,OHNMF與ODL增長最慢.從圖3中可以看出,隨著主題數k的增長運行時間的變化,t-NMF-L1增長的最快,OHNMF最慢,其他3種方法趨勢差不多,這與本文前面分析相符.從圖4中可以看出,隨著數據維度m的增長運行時間的變化,Hie-NMF-L1和JPP的時間增長的最快,OHNMF增長的最慢.綜上所述,OHNMF在時間效率上是所有對比方法中最優的,在數據規模增長時的可擴展性是最強的.

3 結 語

對文本流中的潛在主題進行檢測和跟蹤是當前數據挖掘領域的一個熱點.本文提出了一種層次化的在線稀疏非負矩陣分解方法且將本文方法與其他當前方法在Nist TDT2數據集上進行比較,實驗證明本文提出的方法在更短的運行時間內取得了更好的結果.未來后續工作主要有以下幾個方向,1)目前方法對于周期性出現的話題沒有較好地擬合2)本文方法能夠捕捉到發現的主題之間的結構關系,可進一步根據這些結構關系去生成更加可理解的主題層次.

[1] BLEI D M, JOHN D L. Dynamic topic models [C]∥Proceedings of the 23rd International Conference on Machine Learning. Pittsburgh, Pennsylvania: ACM, 2006: 113-120.

[2] WANG C, BLEI D M, HECKERMAN D. Continuous time dynamic topic models [C]∥Uncertainty in Artificial Intelligence. Helsinki, Finland: AUAI Press, 2008:579-586.

[3] WANG X, ANDREW M. 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, PA： ACM, 2006: 424-433.

[4] MAIRAL J, FRANCIS B, JEAN P, et al. Online learning for matrix factorization and sparse coding [J]. Journal of Machine Learning Research. 2010, 11: 19-60.

[5] SAHA A, VIKAS S. Learning evolving and emerging topics in social media: a dynamic nmf approach with temporal regularization [C]∥Proceedings of the Fifth ACM International Conference on Web Search and Data mining. Seattle, Washington: ACM, 2012: 693-702.

[6] VACA C K, AMIN M, ALEJANDRO J, MARCO S. A Time-based collective factorization for topic discovery and monitoring in news [C]∥Proceedings of the 23rd International Conference on World Wide Web. Seoul： ACM, 2014: 527-538.

[7] BLEI D M, NG A Y, JORDAN M I. Latent dirichlet allocation [J]. Journal of Machine Learning Research, 2003, 3: 993-1022.

[8] THOMAS H. Probabilistic latent semantic analysis [C]∥Uncertainty in artificial intelligence. Stockholm, Sweden: Morgan Kaufmann, 1999: 289--296.

[9] GAUSSIER E, GOUTTE C. Relation between PLSA and NMF and implications [C]∥Acm Sigir Conference on Research & Development in Information Retrieval. Salvador, Bahia, Brazil: ACM, 2005: 601-602.

[10] KUANG D, HAESUN P. Fast rank-2 nonnegative matrix factorization for hierarchical document clustering [C]∥Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. Chicago, Illinois： ACM,2013: 739-747.

[11] JENATTON R, MAIRAL J, OBOZINSKI G, et al.. Proximal methods for sparse hierarchical dictionary learning [C]∥International Conference on Machine Learning. Haifa, Israel: Omnipress, 2010: 487-494.

[12] 景麗萍,朱巖,于劍.層次非負矩陣分解及在文本聚類中的應用[J].計算機科學與探索,2011, 5(10): 904-913.

JING Li-ping, ZHU Yan, YU jian. Hierarchical non-negative matrix factorization for text clustering [J]. Journal of Frontiers of Computer Science & Technology, 2011, 5(10): 904-913.

[13] BLEI D M, GRIFFITHS T L, JORDAN M I, et al. Hierarchical topic models and the nested chinese restaurant process [C]∥Proceedings of the 17th Annual Conference on Neural Information Processing Systems. Vancouver, British Columbia, Canada: MIT Press, 2003: 17-24.

[14] HU L, LI J-Z, ZHANG J, et al. o-HETM: an online hierarchical entity topic model for news streams [C]∥ Proceedings of the 19th Pacific-Asia Conference on Knowledge Discovery and Data Mining. Ho Chi Minh City, Vietnam: Springer, 2015: 696-707.

[15] CAI D, MEI Q, HAN J, et al. Modeling hidden topics on document manifold [C]∥Proceedings of the 17th ACM conference on Information and knowledge management. Napa Valley, California: ACM, 2008: 911-920.

[16] CICHOCKI A, ZDUNEK R, PHAN A H, et al. Nonnegative matrix and tensor factorizations: applications to exploratory multi-way data analysis and blind source separation [M]. Hoboken, New Jersey. John Wiley & Sons, 2009: 131-139.

[17] RITOV Y, BICKEL P J, TSYBAKOV A B. Simultaneous analysis of lasso and dantzig selector [J]. Annals of Statistics, 2009, 37(4):1705-1732.

Hierarchical online NMF for detecting and tracking topics

TU Ding1, CHEN Ling1, CHEN Gen-cai1, WU Yong2, WANG Jing-chang2

(1.CollegeofComputerScienceandTechnology,ZhejiangUniversity,Hangzhou310027,China;2.ZhejiangHongchengComputerSystemsCompanyLimited,Hangzhou310009,China)

An online hierarchical non-negative matrix fraction method was proposed to address the problem of flat topic structure of text stream topic detecting methods. At every time slot, the topic nodes were oplited-splited according to the normalized discounted cumulative gain and a topic hierarchy was built by iteratively assigning documents to the most related topic nodes. The hierarchy construction process refers the previous topic hierarchy. The underlying assumption is that the topics are evolving among the similar topic nodes in different time slots. The method can detect and track topics in stream in an online way, which reveals many useful relationships between the topics. Experiments on Nist TDT2 dataset show that our method outperforms the contrasting methods under different metrics, e.g. NMI, Micro F1, MAP and NDCG, and uses less execution time.

dynamic topic modeling; hierarchical clustering; nonnegative matrix factorization

2015-07-12.

國家自然科學基金資助項目(60703040，61332017)；浙江省科技計劃資助項目(2011C13042，2015C33002);“核高基”國家科技重大專項資助項目(2010ZX01042-002-003)；中國工程科技知識中心資助項目(CKCEST-2014-1-5).

涂鼎，(1987—)，男，博士，從事非結構化數據管理、數據挖掘等研究.ORCID: 0000-0001-8579-2737. E-mail：tututu111@yeah.net

陳嶺，男，副教授.ORCID: 0000-0003-1934-5992. E-mail：lingchen@cs.zju.edu.cn

10.3785/j.issn.1008-973X.2016.08.026

TP 311

A

1008-973X(2016)08-1618-09

浙江大學學報(工學版)網址： www.journals.zju.edu.cn/eng