基于在線層次化非負(fù)矩陣分解的文本流主題檢測(cè)

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

(1.浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,浙江 杭州 310027； 2.浙江鴻程計(jì)算機(jī)系統(tǒng)有限公司,浙江 杭州 310009)

?

基于在線層次化非負(fù)矩陣分解的文本流主題檢測(cè)

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

(1.浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,浙江 杭州 310027； 2.浙江鴻程計(jì)算機(jī)系統(tǒng)有限公司,浙江 杭州 310009)

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

動(dòng)態(tài)主題模型；層次聚類；非負(fù)矩陣分解

在持續(xù)的文本流中去檢測(cè)潛在的主題是典型的主題發(fā)現(xiàn)和跟蹤場(chǎng)景(topic detecting and tracking, TDT)[1-6].自動(dòng)從大量文檔流中去發(fā)現(xiàn)其中一些有意義的主題模式或者跟蹤其中主題內(nèi)容的變化在許多應(yīng)用領(lǐng)域具有重要意義,如社交網(wǎng)絡(luò)、新聞熱點(diǎn)分析等.

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

現(xiàn)有大多數(shù)基于NMF的動(dòng)態(tài)主題模型方法將各個(gè)潛在主題視為獨(dú)立的元素,忽略了各個(gè)主題的交集和其間的關(guān)系,因而限制了這些模型的表達(dá)能力.層次結(jié)構(gòu)是克服這一缺陷的可行方案[10-14].然而,現(xiàn)有層次主題模型[10-14]中大部分方法都是靜態(tài)模型,無(wú)法滿足檢測(cè)文本流中主題的要求.目前,僅有Hu等[14]對(duì)在線層次主題模型進(jìn)行探索,但該文中生成的主題層次不滿足傳統(tǒng)主題層次中子節(jié)點(diǎn)是父節(jié)點(diǎn)的子集這一假設(shè).

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

1 基于OHNMF的在線主題檢測(cè)

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

(1)

1.1 在線稀疏NMF

本文所提方法是基于在線稀疏非負(fù)矩陣分解(online sparse NMF,ONMF),由在線稀疏字典學(xué)習(xí)(online sparse dictionary learning)[4]加上非負(fù)約束后擴(kuò)展而成.稀疏NMF與基本NMF的區(qū)別在于稀疏NMF在目標(biāo)函數(shù)中引入了稀疏性約束.引入稀疏性約束可增強(qiáng)分解結(jié)果的可分離性.通常稀疏性約束是加在主題-文檔矩陣Ht,即保證每篇文檔在各個(gè)主題上的分布只集中在少數(shù)主題上.加入稀疏約束后,原目標(biāo)函數(shù)變?yōu)?/p>

(2)

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

動(dòng)態(tài)主題模型的特點(diǎn)是可根據(jù)當(dāng)前新到的數(shù)據(jù)Xt對(duì)原有主題Wt-1進(jìn)行調(diào)整,使得當(dāng)前主題Wt既能滿足歷史數(shù)據(jù)X0-Xt-1的分布,也能適應(yīng)現(xiàn)有數(shù)據(jù)Xt的情況,即滿足如下目標(biāo)函數(shù)：

(3)

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

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

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

輸入: 文檔矩陣Xt=[x1, x2, x3,…, xn],上一次分解結(jié)果中的m×k維主題-詞矩陣Wt-1,L1正則化約束的系數(shù)λ,分解輔助矩陣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沒(méi)有收斂

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

輸出：當(dāng)前時(shí)間片的主題-詞矩陣W

1.2 OHNMF整體流程

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

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

所有文檔將沿著主題層次中的路徑劃分到各個(gè)葉主題節(jié)點(diǎn)中.主題層次中的每個(gè)主題節(jié)點(diǎn)都可以表達(dá)為一個(gè)主題向量w,并且包含一個(gè)集合D記錄所有劃分路徑經(jīng)過(guò)該主題節(jié)點(diǎn)的文檔.在生成主題層次的同時(shí),系統(tǒng)還為每個(gè)主題節(jié)點(diǎn)存儲(chǔ)了輔助矩陣來(lái)記錄該主題節(jié)點(diǎn)的歷史分解信息,即算法1中的輔助矩陣A和B.

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

算法2 在線更新主題層次

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

4. 計(jì)算W子節(jié)點(diǎn)的mNDCG乘積并存儲(chǔ)在數(shù)組lm

5.n=n+1;

6. Whilen0

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

9. For wi∈w1, w2

10. 生成當(dāng)前節(jié)點(diǎn)摘要si,找到在上一個(gè)時(shí)間片擁有最相似摘要sj的主題節(jié)點(diǎn)wj

11. 重復(fù)2～4步.如果沒(méi)有找到相似節(jié)點(diǎn),則視其為一個(gè)全新節(jié)點(diǎn)的分解.

12. EndFor

13.n=n+1;

14. End While

輸出:t時(shí)間片的所有節(jié)點(diǎn)的主題-詞矩陣的集合SW′和輔助矩陣的集合 SA′, SB′

1.3 OHNMF細(xì)節(jié)

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

在每一次迭代過(guò)程中,OHNMF選擇可分性最高的葉節(jié)點(diǎn)作為下一個(gè)分解的節(jié)點(diǎn).這里使用經(jīng)過(guò)修改的歸一化累計(jì)折損增益[10](modified normalized discounted cumulative gain,mNDCG)作為衡量節(jié)點(diǎn)可分性的標(biāo)準(zhǔn).NDCG可以比較一個(gè)系統(tǒng)生成的排序與目標(biāo)排序之間的一致性.根據(jù)每個(gè)主題向量中各個(gè)詞的權(quán)重可以生成主題中詞的一個(gè)排序,這樣可以通過(guò)比較父主題節(jié)點(diǎn)和子主題節(jié)點(diǎn)中詞的排序來(lái)得到其間的一致性.假設(shè)父節(jié)點(diǎn)的排序?yàn)?/p>

fP=f1,f2,f3, …,fm,2個(gè)子節(jié)點(diǎn)的排序?yàn)閒L=fl1,fl2,fl3, …,flm,fR=fr1,fr2,fr3, …,frm那么其mNDCG可計(jì)算為

g(fi)=

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

(4)

(5)

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

(6)

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

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

(7)

如果t-1時(shí)間片中存在與當(dāng)前主題節(jié)點(diǎn)wi相似度大于一定閾值的主題點(diǎn)節(jié)點(diǎn),即可認(rèn)為當(dāng)前主題節(jié)點(diǎn)是由t-1時(shí)間片中與當(dāng)前節(jié)點(diǎn)相似度最大的主題節(jié)點(diǎn)wj演化而來(lái),可利用其分解結(jié)果指導(dǎo)當(dāng)前節(jié)點(diǎn)wi的分解過(guò)程.

基于NMF的方法中,矩陣初始化一直是影響分解結(jié)果的關(guān)鍵因素.由于ONMF在初始幾次迭代中將以較大的步幅更新W,其對(duì)于初始的幾個(gè)文檔數(shù)據(jù)分布比較敏感,可以通過(guò)恰當(dāng)?shù)某跏蓟鉀Q這種問(wèn)題.在分解一個(gè)節(jié)點(diǎn)的數(shù)據(jù)X時(shí),如果沒(méi)有找到之前相似的節(jié)點(diǎn),則首先對(duì)其進(jìn)行kmeans聚類來(lái)得到2個(gè)類,然后將這2個(gè)類的中心作為初始的主題-詞矩陣W0,同時(shí)設(shè)置A0=t0I,B0=t0W0,t0是常量,這里可以看作當(dāng)前分解是在另一次分解之后進(jìn)行的,該次分解得到的主題-詞矩陣是W0,且記錄的分解輔助矩陣是A0和B0.因?yàn)锳0和B0決定了更新時(shí)的步幅,這樣設(shè)置避免了ONMF對(duì)于初始數(shù)據(jù)敏感的問(wèn)題.

2 實(shí)驗(yàn)與分析

在實(shí)驗(yàn)部分本文方法將與其他現(xiàn)行方法進(jìn)行比較,并且采用多種標(biāo)準(zhǔn)來(lái)衡量實(shí)驗(yàn)結(jié)果以驗(yàn)證本文方法的有效性.所有實(shí)驗(yàn)均運(yùn)行在MATLAB R2014a 環(huán)境中,運(yùn)行機(jī)器配置為Intel Pentinum G3220處理器和24G內(nèi)存.

2.1 數(shù)據(jù)集

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

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

2.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

采用4種標(biāo)準(zhǔn)評(píng)價(jià)實(shí)驗(yàn)中各種方法的效果：

歸一化互信息(NMI)：NMI是一個(gè)廣泛使用的聚類質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn).在生成的聚類數(shù)目與真實(shí)聚類數(shù)目不同時(shí)具有一定優(yōu)勢(shì),并且可以用于決定最優(yōu)的聚類數(shù)目.對(duì)于數(shù)據(jù)的2個(gè)不同劃分而言,越高的互信息值代表著這2種劃分之間有更高的相似度,其計(jì)算公式為

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

(8)

式中:X,Y分別為對(duì)數(shù)據(jù)集的2個(gè)不同劃分,H(X)為分布X的熵.p(x)、p(y)和p(x,y)分別為x的分布概率、y的分布概率和x、y的聯(lián)合分布概率.

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

(9)

(10)

F1=2PR/(P+R).

(11)

式中：R和P分別為召回率和準(zhǔn)確率.召回率和準(zhǔn)確率的計(jì)算與微平均F1中相同.

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

(12)

最終所有50個(gè)數(shù)據(jù)子集的實(shí)驗(yàn)結(jié)果被用于計(jì)算中間平均準(zhǔn)確率.

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

NDCG=DCG/IDCG

(13)

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

2.3 實(shí)驗(yàn)對(duì)比方法

為了能夠更好地評(píng)估本文所提方法,實(shí)驗(yàn)中選取了5種基準(zhǔn)方法：

fix-NMF-L1: fix-NMF-L1只在第1個(gè)時(shí)間片的數(shù)據(jù)上執(zhí)行NMF分解并且在后來(lái)的時(shí)間片中不再改變各個(gè)潛在主題向量的分布.該NMF算法的實(shí)現(xiàn)是基于L1稀疏約束和乘法更新規(guī)則的[16].

t-NMF-L1:t-NMF-L1使用與fix-NMF-L1相同的NMF實(shí)現(xiàn).區(qū)別在于t-NMF-L1在時(shí)間片t使用Wt-1作為初始化矩陣,即用上一個(gè)時(shí)間片的主題-詞矩陣Wt-1作為t時(shí)間片的初始化主題-詞矩陣.

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

JPP: JPP[6]是一個(gè)基于時(shí)間的協(xié)同矩陣分解算法,可以發(fā)現(xiàn)文本流之中的潛在主題.其在目標(biāo)函數(shù)中考慮了之前時(shí)間片的分解結(jié)果和當(dāng)前時(shí)間片分解結(jié)果之間的差異.通過(guò)在目標(biāo)函數(shù)中加入這種約束,其可以實(shí)現(xiàn)平滑的主題發(fā)現(xiàn).

ODL: ODL[4]是一個(gè)在線字典學(xué)習(xí)方法.在本實(shí)驗(yàn)中其目標(biāo)函數(shù)里加上了非負(fù)限制.

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

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

2.4 主題質(zhì)量

本實(shí)驗(yàn)中對(duì)比了不同k(k=5、10、15)設(shè)定下各種方法發(fā)現(xiàn)主題的質(zhì)量.實(shí)驗(yàn)數(shù)據(jù)的詳細(xì)信息如表1所示.實(shí)驗(yàn)中所對(duì)比的6種方法的結(jié)果如表2所示.

表1 抽樣后的Nist TDT2數(shù)據(jù)統(tǒng)計(jì)信息

表2 各主題檢測(cè)方法在Nist TDT2上的主題質(zhì)量對(duì)比

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

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

在層次化NMF類的方法的對(duì)比中,OHNMF要優(yōu)于Hie-NMF-L1.原因是OHNMF可以用過(guò)去時(shí)間片的分解結(jié)果來(lái)指導(dǎo)當(dāng)前時(shí)間片的分解過(guò)程,可以獲得全局更優(yōu)的分解結(jié)果.而Hie-NMF-L1只能根據(jù)當(dāng)前時(shí)間片的文檔來(lái)進(jìn)行分解過(guò)程.實(shí)驗(yàn)中同樣評(píng)估了Hie-NMF-L1的原始形式Hie-Rank2.在本文實(shí)驗(yàn)場(chǎng)景中Hie-Rank2沒(méi)有取得很好的效果,相比于Hie-NMF-L1,其各項(xiàng)指標(biāo)的分?jǐn)?shù)下降0.1.對(duì)于OHNMF而言,如果不添加L1稀疏性約束,其在某些指標(biāo)上同樣會(huì)出現(xiàn)0.05的下降.原因是層次化過(guò)程中將會(huì)放大劃分時(shí)的錯(cuò)誤.所以在每個(gè)主題節(jié)點(diǎn)的分解過(guò)程應(yīng)該越準(zhǔn)確越好.通過(guò)加入L1正則化約束,OHNMF可以找到更稀疏的主題表達(dá),這樣屬于不同主題的文檔就能夠被更好的劃分開(kāi).

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

2.5 主題平滑度

本實(shí)驗(yàn)中評(píng)估了相鄰2個(gè)時(shí)間片中主題-詞矩陣之間的平滑度.Wt-1和Wt之間的平滑度可以通過(guò)如下方法計(jì)算：

(14)

(15)

(16)

表3 各主題檢測(cè)方法在Nist TDT2上的主題平滑度對(duì)比

因?yàn)樵谥黝}檢測(cè)的過(guò)程中主題-詞矩陣一直沒(méi)有發(fā)生變化,所以fix-NMF-L1方法的主題平滑度是1.排除在線學(xué)習(xí)因素的影響,扁平分解方法相對(duì)于層次分解方法能獲得更高的主題平滑度.原因可能是對(duì)于一些處于主題聚類邊界上的文檔,扁平分解能夠獲得較高的一致性,而層次分解可能根據(jù)當(dāng)前數(shù)據(jù)對(duì)其有一定的調(diào)整.t-NMF-L1表現(xiàn)的比Hie-NMF-L1好的另外一個(gè)原因是t-NMF-L1是一種半在線的方法,其每次使用上一個(gè)時(shí)間片的主題-詞矩陣作為當(dāng)前分解的初始化矩陣.OHNMF獲得了第2高的主題平滑度,時(shí)間參數(shù)β和主題相關(guān)度的閾值將會(huì)影響到主題平滑度.額外實(shí)驗(yàn)表明本文方法設(shè)置更大的β和更小的閾值都可獲得更加平滑的主題.

2.6 運(yùn)行時(shí)間

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

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

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

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

從實(shí)驗(yàn)結(jié)果中可以看出ODL和OHNMF花費(fèi)了最少的運(yùn)行時(shí)間.從圖2中可以看出,隨著文檔數(shù)n的增長(zhǎng)運(yùn)行時(shí)間的變化,Hie-NMF-L1和JPP的時(shí)間增長(zhǎng)的最快,OHNMF與ODL增長(zhǎng)最慢.從圖3中可以看出,隨著主題數(shù)k的增長(zhǎng)運(yùn)行時(shí)間的變化,t-NMF-L1增長(zhǎng)的最快,OHNMF最慢,其他3種方法趨勢(shì)差不多,這與本文前面分析相符.從圖4中可以看出,隨著數(shù)據(jù)維度m的增長(zhǎng)運(yùn)行時(shí)間的變化,Hie-NMF-L1和JPP的時(shí)間增長(zhǎng)的最快,OHNMF增長(zhǎng)的最慢.綜上所述,OHNMF在時(shí)間效率上是所有對(duì)比方法中最優(yōu)的,在數(shù)據(jù)規(guī)模增長(zhǎng)時(shí)的可擴(kuò)展性是最強(qiáng)的.

3 結(jié) 語(yǔ)

對(duì)文本流中的潛在主題進(jìn)行檢測(cè)和跟蹤是當(dāng)前數(shù)據(jù)挖掘領(lǐng)域的一個(gè)熱點(diǎn).本文提出了一種層次化的在線稀疏非負(fù)矩陣分解方法且將本文方法與其他當(dāng)前方法在Nist TDT2數(shù)據(jù)集上進(jìn)行比較,實(shí)驗(yàn)證明本文提出的方法在更短的運(yùn)行時(shí)間內(nèi)取得了更好的結(jié)果.未來(lái)后續(xù)工作主要有以下幾個(gè)方向,1)目前方法對(duì)于周期性出現(xiàn)的話題沒(méi)有較好地?cái)M合2)本文方法能夠捕捉到發(fā)現(xiàn)的主題之間的結(jié)構(gòu)關(guān)系,可進(jìn)一步根據(jù)這些結(jié)構(gòu)關(guān)系去生成更加可理解的主題層次.

[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] 景麗萍,朱巖,于劍.層次非負(fù)矩陣分解及在文本聚類中的應(yīng)用[J].計(jì)算機(jī)科學(xué)與探索,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.

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

涂鼎，(1987—)，男，博士，從事非結(jié)構(gòu)化數(shù)據(jù)管理、數(shù)據(jù)挖掘等研究.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

浙江大學(xué)學(xué)報(bào)(工學(xué)版)網(wǎng)址： www.journals.zju.edu.cn/eng