, ,

(1.華東師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系,上海 200241; 2.上海長江計(jì)算機(jī)有限公司,上海 200241)

0 概述

近年來,互聯(lián)網(wǎng)新聞報(bào)道平臺(如LexisNexis、Google新聞和GDELT)已經(jīng)成為用戶觀察新聞話題變遷趨勢的重要來源。然而,這種新聞?wù)Z料庫面臨著信息冗余的問題,特別是針對同一事件的內(nèi)容的重復(fù)報(bào)道和新聞之間的互相轉(zhuǎn)載報(bào)道,造成了讀者對互聯(lián)網(wǎng)新聞事件的閱讀困難。關(guān)注話題變遷對人們理解和分析社會事件發(fā)展趨勢有著積極的意義。話題變遷是指一個(gè)話題隨著時(shí)間變化的過程,一般包含話題提出、話題發(fā)展、話題減少和話題消失等4個(gè)階段[1]。在話題變遷過程中,話題的內(nèi)容通常隨時(shí)間的變化而改變,即時(shí)序文檔中包括相似話題和異同話題。因此,識別異同話題及其發(fā)生時(shí)刻是一個(gè)挑戰(zhàn)性的任務(wù)。

與本文研究相關(guān)的是話題發(fā)現(xiàn)和演變(Topic Discovery and Evolution,TDE)任務(wù)。之前關(guān)于TDE的研究工作大多是采用了聚類算法,例如k-means、層級聚類和DBSCAN[2]等。然而,這些方法的準(zhǔn)確率較低。近年來,為提高話題發(fā)現(xiàn)的準(zhǔn)確性,LDA(Latent Dirichlet Allocation)模型和改進(jìn)的LDA模型被引入到TDE任務(wù)中[3]。這些方法主要利用LDA去構(gòu)建動態(tài)話題模型[4]或者判別式話題模型[3],或?qū)DA與時(shí)間上下文特征相結(jié)合[4]。其他基于LDA改進(jìn)的話題模型,例如Link-LDA[5]、關(guān)系話題模型[5]和LTECS模型[6],是在LDA模型中添加地理信息或者上下文背景信息等特征元素來提高話題發(fā)現(xiàn)的準(zhǔn)確率。因?yàn)榫垲惖馁|(zhì)量會隨著特征矩陣的維度的增加而減小[7],所以上述方法具有以下問題:1)LDAs相關(guān)方法不適合從時(shí)序文檔中發(fā)現(xiàn)異同話題,其原因是隨著時(shí)間發(fā)展,舊話題消失和新的話題出現(xiàn);不同的時(shí)間范圍內(nèi)話題的數(shù)量也是不同的,上述原因?qū)υ掝}發(fā)現(xiàn)的效果影響很大。2)因?yàn)長DAs的時(shí)間復(fù)雜度與話題數(shù)和詞袋中詞語數(shù)的乘積呈線性關(guān)系,所以LDAs方法在用于大規(guī)模文檔的話題提取任務(wù)時(shí)具有較高的時(shí)間復(fù)雜度。

近年來,非負(fù)矩陣分解(Nonnegtive Matrix Factorization,NMF)及其擴(kuò)展算法被引入TDE任務(wù)[6,8-9]。NMF是一種非監(jiān)督機(jī)器學(xué)習(xí)算法,能夠自動挖掘大規(guī)模文檔集中的話題[10]。與概率話題模型(例如LDA、PLSI)相比,NMF將原始數(shù)據(jù)矩陣分解為2個(gè)子矩陣,并通過平行學(xué)習(xí)得到各子矩陣的解。因此,比其他概率模型具有更好的可擴(kuò)展性。文獻(xiàn)[5]提出了基于NMF的正則化的共享空間遷移的方法,對2個(gè)相關(guān)的文檔集進(jìn)行聯(lián)合建模。設(shè)置嚴(yán)格的共享空間,相比于其他方法,該方法的靈活性較差。文獻(xiàn)[11]提出了具有偏移向量的基因數(shù)據(jù)集的NMF方法。該方法的思想是提出共同的基因調(diào)節(jié)模式,每個(gè)數(shù)據(jù)集中穩(wěn)定的表達(dá)層被偏移向量吸收。文獻(xiàn)[6]提出一種利用大型語料庫中包含的文本信息和社會情景信息來構(gòu)建非負(fù)矩陣分解的模型。文獻(xiàn)[12]提出了通過規(guī)范化組稀疏方法來發(fā)現(xiàn)多個(gè)文檔集中的相似話題和異同話題的方法。在其隨后工作中設(shè)計(jì)了一種基于聯(lián)合NMF的話題建模方法(JNMF),可以發(fā)現(xiàn)多個(gè)文檔集中包含的共同和不同的話題[9]。該方法在聯(lián)合非負(fù)矩陣分解的目標(biāo)函數(shù)中引入了2個(gè)懲罰函數(shù)來判斷最相似的話題和最不同的話題。然而,以上研究大多集中在從大規(guī)模語料庫中檢測潛在的話題,這些方法缺乏從時(shí)序文檔集中識別話題和跟蹤分析話題隨時(shí)間變遷的能力。

為從時(shí)序文檔語料庫中發(fā)現(xiàn)異同話題,并跟蹤和分析所探測的異同話題隨著時(shí)間的發(fā)展的變遷趨勢,本文提出一種基于聯(lián)合非負(fù)矩陣分解的時(shí)序異同話題發(fā)現(xiàn)方法(Discriminative Topics Discovering Using Joint NMF Algorithm,ToD)。ToD方法包括3個(gè)主要部分:特征選擇,聯(lián)合NMF模型和優(yōu)質(zhì)話題選擇。ToD采用改進(jìn)的聯(lián)合非負(fù)矩陣分解方法來發(fā)現(xiàn)多個(gè)文檔集中的話題集合,并在話題集合中發(fā)現(xiàn)不同文檔集之間相似和不同的話題。

1 符號定義

本文所采用的方法是檢測來自2個(gè)不同時(shí)間下的文檔集Dt和Dt+1中的所有潛在話題,然后同時(shí)從Dt和Dt+1中發(fā)現(xiàn)相似話題和異同話題。也就是說,給定大規(guī)模的文檔語料庫,ToD方法首先識別異同話題集(包含c個(gè)相同的話題和d個(gè)不同的話題),然后追蹤同一個(gè)話題中的話題詞隨時(shí)間演變的趨勢。異同話題發(fā)現(xiàn)的關(guān)鍵問題之一是確定相似話題Vc和異同話題Vd在所有話題Vk中的比例。為了解決上述問題,本文設(shè)計(jì)了一種可以同時(shí)分解2個(gè)文檔集Dt和Dt+1的方法,并且引入2個(gè)懲罰函數(shù)R1和R2去平衡Vc和Vd所占的比例。

為了便于后續(xù)的表述和理解,本文統(tǒng)一使用不帶下標(biāo)的字母來表示各自集合中的任意元素。

2 時(shí)序異同話題發(fā)現(xiàn)算法

ToD方法的主要流程是:在文檔預(yù)處理之后,首先從文檔中提取特征矩陣。然后利用聯(lián)合NMF模型發(fā)現(xiàn)不同子集中的相似話題和異同話題。最后根據(jù)話題發(fā)現(xiàn)的結(jié)果,從中提取優(yōu)質(zhì)話題。

為方便敘述,考慮2個(gè)文檔集合的情況。假設(shè)存在時(shí)序文檔集合D,將D按照時(shí)間劃分為2個(gè)子集合:D1和D2。例如,實(shí)驗(yàn)數(shù)據(jù)集(LTN2011)中包含了1997年—2011年之間的拉丁美洲非法移民的新聞報(bào)道,根據(jù)年代將數(shù)據(jù)集劃分為2個(gè)子集:第1個(gè)子集D1包含從1997年—2004年的所有新聞,而另一個(gè)子集D2包含了2005年—2011年的所有新聞。

在為文檔子集D1和D2構(gòu)造了2個(gè)特征矩陣X1和X2之后,本文使用改進(jìn)的聯(lián)合非負(fù)矩陣分解算法,分別對這2個(gè)特征矩陣進(jìn)行分解,從而得到相似話題和一同話題。

2.1 改進(jìn)的聯(lián)合非負(fù)矩陣分解算法

2.1.1 非負(fù)矩陣分解算法

X≈W×HT

(1)

由于NMF是NP問題,一般采取迭代計(jì)算2個(gè)矩陣W和H的方法來求得2個(gè)矩陣的解。代表的求解方法是采取梯度投影法來計(jì)算矩陣W和矩陣H。雖然梯度投影法不能收斂到全局最優(yōu),但是相比其他的迭代算法,有著良好的優(yōu)化性能[13]。梯度投影法通過計(jì)算矩陣X與矩陣W和H的乘積的歐幾里得距離來測量近似度,目標(biāo)方程定義為,

(2)

在矩陣分解的過程中,矩陣中的每個(gè)元素只有非負(fù)值。矩陣X中的列向量可以解釋為矩陣W中所有列向量和矩陣H的分量的線性加權(quán)和。因此,W的列向量也稱為基向量,W也被視為基矩陣,而權(quán)重系數(shù)對應(yīng)于作為系數(shù)矩陣H中的列向量的元素。這種基于基向量組合的表示形式具有視覺語義上的可解釋性,它反映了零件構(gòu)成整體的概念。此外,基于簡單迭代的NMF方法具有收斂速度快,非負(fù)矩陣存儲空間小和語義解釋性強(qiáng)的優(yōu)點(diǎn),因此,它適用于處理大規(guī)模文本的話題發(fā)現(xiàn)。但是,NMF的工作在處理具有時(shí)間屬性的多個(gè)文檔集的問題上關(guān)注較少。例如,標(biāo)準(zhǔn)NMF方法,它只能從單個(gè)文檔集中發(fā)現(xiàn)話題,但是無法同時(shí)處理多個(gè)文檔集。因此,標(biāo)準(zhǔn)NMF不能處理多個(gè)文檔中的話題同時(shí)發(fā)現(xiàn)的問題。

本文提出一種改進(jìn)的聯(lián)合非負(fù)矩陣分解算法(NJNMF),通過使用聯(lián)合NMF算法與懲罰函數(shù),可以從多個(gè)數(shù)據(jù)集中提取異同話題。

2.1.2 改進(jìn)聯(lián)合非負(fù)矩陣分解算法描述

在對文檔集中的文檔進(jìn)行預(yù)處理和特征選擇之后,得到2個(gè)特征矩陣X1和X2。本文利用NJNMF算法同時(shí)分解2個(gè)矩陣X1和X2,公式如下:

(3)

圖1 NJNMF算法分解過程示意圖

在聯(lián)合矩陣分解中,本文引入2個(gè)懲罰函數(shù)R1(W1,c,W2,c)和R2(W1,d,W2,d)到聯(lián)合矩陣分解過程中,這2個(gè)懲罰函數(shù)分別代表不同文檔集中話題的相似性和差異性。通過這2個(gè)懲罰函數(shù),就可以控制矩陣分解后的基矩陣Wi的結(jié)果,目標(biāo)函數(shù)為:

ω1R1(W1,c,W2,c)+ω2R2(W1,d,W2,d)

(4)

圖1顯示了改進(jìn)的聯(lián)合NMF算法的迭代過程。首先,從2個(gè)文檔集D1和D2之間獲取相似話題和異同話題Vc和Vd,即話題Vk=Vc+Vd是從基矩陣Wi中發(fā)現(xiàn)的,基矩陣Wi中的第i列向量也就是話題V中的第i個(gè)話題,記為Si,且有k=c+d。其次,基于基矩陣Wi的結(jié)構(gòu),每個(gè)Si都是由m個(gè)話題詞組成。然后,將第i個(gè)話題中的在第j個(gè)話題詞記為TiWj,這意味著TiWj代表著其話題類別中的特定話題詞語。因此,最終可以從2個(gè)文檔集中得到所有相似和不同的話題以及每個(gè)話題所包含的話題詞。

2.1.3 懲罰函數(shù)

為了得到方程的最優(yōu)解,首先定義2個(gè)懲罰函數(shù)R1和R2,公式如下:

(5)

根據(jù)式(5),在矩陣分解的過程中,文中利用最小化基矩陣W1和W2元素之間的平方差來聚類相似的話題。在式(5)中,W1,d×W2,d中的第(i,j)個(gè)元素表示矩陣W1和W2的內(nèi)積的值,即W1中第i個(gè)話題向量和W2中第j個(gè)話題向量的乘積。因此,式(5)中的SFt就表示矩陣W1,d和W2,d之間的所有列向量的內(nèi)積。其中R2(W1,d,W2,d)中的部分元素的數(shù)值將變?yōu)榱?這樣就可以讓每一個(gè)話題詞只能對應(yīng)于一個(gè)話題類別。通過迭代計(jì)算,可以在2個(gè)數(shù)據(jù)集之間找到更多的異同話題。然后利用式(5)來計(jì)算式(4),得到最終的目標(biāo)函數(shù):

ω1NFt(W1,c-W2,c)+ω2SFt(W1,d×W2,d)

(6)

2.2 優(yōu)化算法

為了在文檔集D1和D2之間得到最優(yōu)的k值來發(fā)現(xiàn)相似和異同話題,本文選擇了塊坐標(biāo)下降法[13]來求解式(6)。該迭代算法具有3個(gè)部分:1)最小化懲罰函數(shù)R1(W1,c,W2,c)來計(jì)算2個(gè)矩陣W1,c和W2,c的值,它們表示2個(gè)數(shù)據(jù)集D1和D2的相似話題。2)最小化懲罰函數(shù)R2(W1,d,W2,d)來計(jì)算2個(gè)矩陣W1,d和W2,d的值,這2個(gè)矩陣代表的是文檔集D1和D2之間的異同話題。3)為參數(shù)ω1和ω2選擇適當(dāng)?shù)闹狄云胶?個(gè)懲罰函數(shù)R1(W1,c,W2,c)和R2(W1,d,W2,d)的權(quán)重比例。該迭代算法的主要思想是:坐標(biāo)下降法并不是尋求整個(gè)變量的梯度,而是沿著變量的每個(gè)維度單變量的進(jìn)行循環(huán)地優(yōu)化。如果函數(shù)在當(dāng)前迭代中未優(yōu)化,則表明已達(dá)到其駐點(diǎn)。因此,該算法可以保證每個(gè)極值點(diǎn)就是一個(gè)駐點(diǎn)。

大多數(shù)近似算法分別計(jì)算矩陣W和H。本文將矩陣Wi和Hi的乘積作為基組,利用式(7)計(jì)算Wi×Hi的值:

(7)

ToD算法的目標(biāo)是通過迭代更新Wi×Hi中的向量的值,直到獲得最優(yōu)解。為了在迭代過程中得到式(6)中的參數(shù)值,本文定義以下迭代規(guī)則,公式如下:

(8)

算法1改進(jìn)的聯(lián)合NMF算法

3.end for

4.repeat

5.Update Wi,Hiusing Eq.(8)

6.ComputeR1(W1,c,W2,c)using Eq.(5);

7.ComputeR2(W1,d,W2,d)using Eq.(5);

8.repeat

12.until Update Hiusing Eq.(7);

13.until Stop criteria threshold;

14.End

在算法1中,n1和n2代表的是文檔集D1和D2中包含的文檔的數(shù)目,矩陣X1和矩陣X2分別是文檔集D1和D2所構(gòu)建的特征矩陣,參數(shù)ω1和ω2是用于控制懲罰函數(shù)的權(quán)重,n1和n2分別表示2個(gè)文檔集中的文檔數(shù)目,m代表的是D1和D2中的詞袋中所有的詞語的數(shù)目。

2.3 算法分析

標(biāo)準(zhǔn)NMF算法采用的是基于迭代計(jì)算的優(yōu)化方法[14],算法的時(shí)間開銷主要用于矩陣之間的相乘計(jì)算,其時(shí)間復(fù)雜度取決于待處理的語料庫的大小,達(dá)到穩(wěn)定點(diǎn)時(shí)平均的迭代的次數(shù),時(shí)間復(fù)雜度為O(tmnk),其中,m為詞袋中詞語的數(shù)量,n為文檔數(shù)量,k為話題數(shù)量,t是平均迭代次數(shù)。

2.4 優(yōu)質(zhì)話題選擇

為了確定所獲得的話題是否為優(yōu)質(zhì)話題,本文通過測量話題熵(TE)來提取優(yōu)質(zhì)話題:

(9)

其中,p(θ|S)表示話題詞θ出現(xiàn)在話題S下的概率。當(dāng)話題熵的值越大時(shí),話題S越可能是噪聲話題。使用式(9)計(jì)算每個(gè)話題的話題熵,預(yù)先設(shè)定一個(gè)話題熵閾值g,所有小于閾值g的話題熵所對應(yīng)的話題S被視為優(yōu)質(zhì)話題。

3 實(shí)驗(yàn)與結(jié)果分析

為了評估本文提出的方法,本文進(jìn)行了2組實(shí)驗(yàn):第1組實(shí)驗(yàn)來評估ToD話題發(fā)現(xiàn)的效果;第2組實(shí)驗(yàn)使用拉丁美洲非法移民數(shù)據(jù)(LTN2011)來發(fā)現(xiàn)隨著時(shí)間變化,人們所關(guān)注的相似話題和異同話題的變遷趨勢。所有實(shí)驗(yàn)均在具有2.7 GHz CPU和32 GB主存儲器的戴爾服務(wù)器上進(jìn)行。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文使用2個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),分別是20Newsgroups[9]和LTN2011。

20Newsgroups:20Newsgroups數(shù)據(jù)集是由20個(gè)新聞組,大約20 000個(gè)新聞文檔構(gòu)成的,所占硬盤空間近62 MB。該數(shù)據(jù)集最初由Ken Lang收集,是新聞事件的文檔集合。近年來,20Newsgroups已經(jīng)越來越受到話題發(fā)現(xiàn)文本聚類實(shí)驗(yàn)的歡迎。 20個(gè)新聞組的統(tǒng)計(jì)信息如圖2所示。

圖2 20 Newsgroups數(shù)據(jù)集的統(tǒng)計(jì)信息

LTN2011:從LexisNexis中收集并構(gòu)建了LTN2011數(shù)據(jù)集。LexisNexis是世界上最大的新聞媒體之一,其中包含美國主要新聞媒體的新聞報(bào)道(如紐約時(shí)報(bào)和華盛頓時(shí)報(bào))。利用查詢詞“illegal”“ immigrant”作為關(guān)鍵詞來搜索LexisNexis,這樣就得到了從1997年—2011年間關(guān)于非法移民問題的所有新聞報(bào)道數(shù)據(jù)。 LTN2011數(shù)據(jù)集有13 039篇文章,大小為40 MB。是按照平均每年有大約900份的數(shù)目收集的新聞報(bào)道,以確保新聞數(shù)據(jù)的平衡性。圖3顯示了該數(shù)據(jù)集的統(tǒng)計(jì)信息。

圖3 LTN2011數(shù)據(jù)集的統(tǒng)計(jì)信息

3.2 評估指標(biāo)

本文使用2個(gè)常用的度量指標(biāo)來評估話題發(fā)現(xiàn)的結(jié)果,分別是準(zhǔn)確度(AC)和歸一化互信息(NMI)[15]。假定文本樣本分別用樣本提供的標(biāo)簽來表示,即αi、γi、si,公式如下:

(10)

其中,n是樣本文本的數(shù)量,在函數(shù)δ(x,y)中,當(dāng)x等于y時(shí),函數(shù)δ(x,y)的值為1;否則函數(shù)為0。排序映射函數(shù)map(γi)的作用,是將樣本γi的每個(gè)標(biāo)簽都映射到等效的標(biāo)簽上。

本文還使用NMI方法來評估話題提取的效果。NMI方法優(yōu)于純度(purity)和熵(entropy)的方法,它可以消除由聚類結(jié)果簇個(gè)數(shù)的不同,對評價(jià)聚類結(jié)果產(chǎn)生的影響。NMI的值越接近1,表明聚類結(jié)果越好。NMI的公式如下:

(11)

其中,C表示樣本聚類的實(shí)際結(jié)果,C′表示由該算法獲得的聚類結(jié)果,H(C)和H(C′)分別表示C和C′的熵,由式(11)可知,NMI(C,C′)值的變化范圍在0～1之間。當(dāng)C和C′完全相同時(shí),NMI(C,C′)等于1;當(dāng)C和C′相互獨(dú)立時(shí),NMI(C,C′)等于0。

3.3 實(shí)驗(yàn)設(shè)計(jì)與分析

實(shí)驗(yàn)設(shè)計(jì)與分析過程如下:

1)20Newsgroups實(shí)驗(yàn)結(jié)果分析。本文比較了ToD與其他6個(gè)話題發(fā)現(xiàn)算法在20Newsgroups數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果,分別是LDA[16]、NMF[8]、GNMF[17]、CNMF[17]、LLRNMF[18]和JNMF[9]。后5種方法的實(shí)驗(yàn)結(jié)果源自文獻(xiàn)[9,19]。所有方法的準(zhǔn)確度和NMI的實(shí)驗(yàn)結(jié)果如圖4所示,其中,整個(gè)矩形是指算法在該指標(biāo)上的最大值,矩形下部的實(shí)心部分是指算法的最小得分,而矩形上部的陰影部分是算法在該指標(biāo)上的最大得分和最小得分之間的差。

圖4在20Newsgroups數(shù)據(jù)集上7種算法的準(zhǔn)確度和歸一化互信息值

圖4顯示ToD算法在準(zhǔn)確度和NMI上均勝過其他6種方法。其中,標(biāo)準(zhǔn)NMF算法的準(zhǔn)確度最低。從圖4中可以看到,ToD方法的準(zhǔn)確度和NMI值(80%和0.5)均優(yōu)于JNMF方法(60%和0.4)[9]。進(jìn)一步調(diào)查表明:JNMF方法的目標(biāo)是發(fā)現(xiàn)2個(gè)單獨(dú)文檔集之間的共同和不同話題,而ToD方法通過將時(shí)間參數(shù)t引入到NFt和SFt中,以改進(jìn)矩陣迭代計(jì)算期間的懲罰函數(shù)的值。這樣就可以比較在不同時(shí)間戳下的多個(gè)文檔集之間的相似話題矩陣和異同話題矩陣。因此,ToD可以發(fā)現(xiàn)并跟蹤多個(gè)文檔集之間的時(shí)序異同話題。由于同樣的原因,JNMF對多個(gè)文檔集中的話題的連續(xù)性考慮較少,這降低了話題提取的準(zhǔn)確性。

本文進(jìn)一步比較和分析了不同k值下的實(shí)驗(yàn)結(jié)果,如圖5所示,從左到右分為LDA、NMF、GNMF、CNMF、LLRNMF和ToD算法的NMI指標(biāo)。圖5顯示了在所有方法的NMI指標(biāo)中,ToD的方法優(yōu)于其他方法,當(dāng)增加話題數(shù)k時(shí),其他5個(gè)算法的NMI值明顯減小,而ToD算法在不同k值的情況下依然保持著穩(wěn)定的值。標(biāo)準(zhǔn)NMF獲得最低的NMI得分,是因?yàn)樵摲椒ㄝ^少的使用了文檔集中的標(biāo)簽信息,從而導(dǎo)致聚類效果較差。 CNMF是一種半監(jiān)督算法,它使用樣本數(shù)據(jù)的類別信息作為輸入約束。通過將類似的樣本數(shù)據(jù)從高維度投影到低維度,保持樣本信息的一致性,所以具有比NMF更好的聚類效果。但是CNMF忽略樣本數(shù)據(jù)結(jié)構(gòu)的信息[20-21],LLRNMF不僅使用樣本數(shù)據(jù)信息的結(jié)構(gòu),還使用樣本數(shù)據(jù)中的識別信息,所以它具有比GNMF更好的結(jié)果。

圖5 20Newsgroups數(shù)據(jù)集上6種算法的NMI評估結(jié)果

2)LTN2011實(shí)驗(yàn)數(shù)據(jù)分析。本文使用ToD算法來處理LTN2011數(shù)據(jù)集,并將1997年—2011年期間關(guān)于拉丁美洲非法移民的話題變遷趨勢可視化。

(1)數(shù)據(jù)準(zhǔn)備。本文使用以下步驟處理原始新聞數(shù)據(jù):首先從文本中移除屬性的標(biāo)簽,例如報(bào)道字?jǐn)?shù)、作者、出版商等,只保留新聞標(biāo)題及其新聞?wù)牟糠?。然后對?biāo)題和內(nèi)容進(jìn)行了以下預(yù)處理,使用了POS過濾、停止詞過濾、位置標(biāo)記和詞干預(yù)處理等。其次根據(jù)它們的出版日期,將LTN2011文檔集分為兩部分,分別是1997年—2004年和2005年—2011年。從2個(gè)文檔集中提取特征可以得到2個(gè)輸入矩陣X1和X2。最后在2個(gè)矩陣X1和X2上使用ToD方法來獲得1997年—2004年和2005年—2011年之間相似話題和異同話題的結(jié)果,并在優(yōu)質(zhì)話題選擇之后分析話題變遷趨勢。

(2)參數(shù)選擇。為了在不同k值下,得到話題發(fā)現(xiàn)的最佳結(jié)果,本文通過設(shè)置不同的控制參數(shù)ω1和ω2來尋找合適的參數(shù)值。在LTN2011數(shù)據(jù)集上顯示不同參數(shù)的實(shí)驗(yàn)結(jié)果如圖6所示?？梢钥闯?ToD算法在k=10時(shí)獲得最好的聚類效果。而且當(dāng)k值從1變到10時(shí),ToD算法的NMI保持穩(wěn)定。

圖6ToD算法在LTN2011數(shù)據(jù)集上的準(zhǔn)確度和歸一化互信息評估結(jié)果

3.4 案例分析

本文分析了1997年—2004年和2005年—2011年2個(gè)時(shí)間范圍每年的拉丁美洲威脅事件的話題演變。通過使用ToD算法,本文從LTN2011文檔集中提取相似和異同話題及其話題詞。下文通過使用詞云和折線趨勢圖的方式來顯示所有發(fā)現(xiàn)的話題內(nèi)容及話題的變遷趨勢。圖7展示出了4個(gè)相似話題的每年的變遷趨勢示例。每個(gè)折線圖部分都表示與拉丁美洲移民事件相關(guān)的相似話題的變遷。詞云中的話題詞的大小表示公眾對該話題詞語的關(guān)注程度。根據(jù)圖7可以得知拉丁美洲非法移民原有話題的變遷趨勢和新興話題的出現(xiàn)情況,可以看出,移民相關(guān)話題分布的峰值在2005年—2006年。話題的峰值主要來源于限制性移民法的頒布。在2004年—2006年期間,國會通過了更嚴(yán)格的移民法。

圖7 相似話題的變遷趨勢示意圖

3.4.1 非法移民話題分析

圖7(a)和圖7(d)從2個(gè)角度展示了非法移民的最相關(guān)話題詞:公民合法性和就業(yè)合法性。這2個(gè)話題詞在非法移民問題的關(guān)注中的有著一致性的變遷趨勢。圖7(a)表明,公眾通常關(guān)心移民問題的合法性,他們使用了諸如“Legally(合法)”“illegally(非法)”“deadline(最后期限)”“deport(驅(qū)逐)”等話題詞來描述移民問題,“l(fā)egitimacy(合法性)”話題的討論在2004年達(dá)到頂峰。圖7(d)中的話題詞為“l(fā)icense(許可證)”“industry(工業(yè))”“l(fā)aborer(勞動者)”“housing(住房)”“employment(勞動傷害敘事)”等,表明政府在移民的合法化方面做了大量工作,并幫助新移民居住在美國。圖7(c)和圖7(b)中出現(xiàn)了一些新興的話題。圖7(c)顯示了一個(gè)新的相關(guān)話題即移民的方式,從“immigrats(移民)”“l(fā)anding(登陸)”“vessel(船舶)”和“coast(海岸)”等詞語中可以看到,人們經(jīng)常使用交通相關(guān)的術(shù)語,例如,“ship(船)”“carry(攜帶)”“island(島)”“port(港口)”“navy(海軍)”“rescue(救援)”,而其中“smuggling(走私)”的關(guān)注度更多,這也意味著公眾雖然關(guān)注移民的方式,但是認(rèn)為無論何種移民方式,這樣的移民都是非法的。圖7(b)揭示了“illegal immigration and human trafficking(非法移民和人口販運(yùn))”的相關(guān)話題。注意到從1997年到2004年,關(guān)注的焦點(diǎn)一直在諸如“smuggle(走私)”、“truck(卡車)” “charge(費(fèi)用)”“passport(護(hù)照)”“death(死亡)”“cargo(貨物)”等。雖然在隨后的幾年(從2004年—2011年),這個(gè)話題有更高的關(guān)注,但此類話題的變遷趨勢與這一時(shí)期的人口販運(yùn)整體趨勢一致,且在2001年達(dá)到峰值,然后從2001年到2004年呈減少的趨勢。

3.4.2 異同話題的變遷趨勢分析

ToD算法還可以分析不同文檔集之間異同話題的變遷趨勢。如圖8所示,可以看到有3種不同字體的話題詞:1)刑事定罪的相關(guān)話題詞(斜體單詞);2)聯(lián)邦政府移民法規(guī)的相關(guān)話題詞(普通字體單詞);3)移民經(jīng)濟(jì)問題的相關(guān)話題詞(加粗字體單詞)。圖8(a)表明,新聞媒體不斷著重于移民問題消極方面的報(bào)道,即判定拉丁美洲移民問題為刑事犯罪,例如“illegal(非法)”和“crime(犯罪)”等(見圖8(a)中的斜體單詞)。移民犯罪化的主要后果是監(jiān)獄人數(shù)和驅(qū)逐出境人數(shù)的增加,體現(xiàn)在話題詞“deportation(驅(qū)逐出境)”“jail(牢獄)”“prison(監(jiān)獄)”等(見圖8(b)中的斜體字體)。普通字體字體反映了聯(lián)邦政府關(guān)于移民問題的立場,例如“official(官方)”“l(fā)aw(法律)”“enforcement(執(zhí)行)”等。圖8(b)顯示了公眾對移民問題在經(jīng)濟(jì)方面的關(guān)注,由諸如“employer(雇主)”“worker(工人)”“economic(經(jīng)濟(jì))”“worker(工作)”(見圖8(b)中的加粗字體)等話題詞表示。

圖8 LTN204文檔集中2個(gè)不同話題的變遷趨勢示意圖

4 結(jié)束語

本文針對大規(guī)模時(shí)序文檔集中異同話題發(fā)現(xiàn)問題,提出一種改進(jìn)的聯(lián)合NMF算法(ToD)。該算法可以從時(shí)序性文檔集中同時(shí)發(fā)現(xiàn)相似和異同話題;然后通過計(jì)算所有話題的話題熵,以提取優(yōu)質(zhì)話題;接著將這些優(yōu)質(zhì)話題可視化,以展示LTN2011的話題變遷的趨勢;最后對2個(gè)真實(shí)的文檔集的進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果證明,ToD算法的AC與NMI優(yōu)于其他6種話題發(fā)現(xiàn)算法。下一步將繼續(xù)優(yōu)化ToD算法的效率,使其可以支持大規(guī)模文檔語料庫的實(shí)時(shí)TDE分析的任務(wù)。此外,計(jì)劃建立一個(gè)具有可視化功能的TDE系統(tǒng)來展示時(shí)序文檔集之間的相似話題和異同話題的變遷趨勢。

[1] 楚克明,李 芳.基于LDA模型的新聞話題的演化[J].計(jì)算機(jī)應(yīng)用與軟件,2011,28(4):4-7.

[2] ESTER M,KRIEGEL H P,SANDER J,et al.A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]//Proceedings of KDD’96.Berlin,Germany:Springer,1996:226-231.

[3] JIANG Y,LI X,MENG W.Discword:Learning Discriminative Topics[C]//Proceedings of IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technologies.Washington D.C.,USA:IEEE Press,2014:63-70.

[4] ZHANG H,KIM G,XING E P.Dynamic Topic Modeling for Monitoring Market Competition from Online Text and Image Data[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2015:1425-1434.

[5] LIU Y,NICULESCU M A,GRYC W.Topic-link Lda:Joint Models of Topic and Author Community[C]//Proceedings of the 26th Annual International Conference on Machine Learning.New York,USA:ACM Press,2009:665-672.

[6] KALYANAM J,MANNTRACH A,SAEZ T D,et al.Leveraging Social Context for Modeling Topic Evolution[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2015:517-526.

[7] 王 鑫,李 璐,王曉芳.基于 Nystr?m 譜聚類的詞典學(xué)習(xí)[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(6):112-117.

[8] LEE D D,SEUNG H S.Algorithms for Non-negative Matrix Factorization[C]//Proceedings of Advances in Neural Information Processing Systems.[S.1.]:MIT Press,2001:556-562.

[9] KIM H,CHOO J,KIM J,et al.Simultaneous Discovery of Common and Discriminative Topics via Joint Nonnegative Matrix Factorization[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2015:567-576.

[10] LI Q,CHEN B,MA S,et al.Contrastive Ttopic Evolution Discovery via Nonnegative Matrix Factorization[C]//Proceedings of IEEE International Conference on Communications.Washington D.C.,USA:IEEE Press,2016:1-6.

[11] BADEA L.Extracting Gene Expression Profiles Common to Colon and Pancreatic Adenocarcinoma Uing Simultaneous Nonnegative Matrix Factorization[J].Biocomputing,2008,290(13):279-290.

[12] KIM J,MONTEIRO R,PARK H.Group Sparsity in Nonnegative Matrix Factorization[C]//Proceedings of SDM’12.[S.1.]:SIAM Press,2012:851-862.

[13] KIM J,HE Y,PARK H.Algorithms for Nonnegative Matrix and Tensor Factorizations:A Unified View Based on Block Coordinate Descent Framework[J].Journal of Global Optimization,2014,58(2):285-319.

[14] 李 謙.非負(fù)矩陣分解及其在高維數(shù)據(jù)應(yīng)用中的研究[D].北京:北京交通大學(xué),2014.

[15] ESTEVEZ P A,TESMER M,PEREZ C A,et al.Normalized Mutual Information Feature Selection[J].IEEE Transactions on Neural Networks,2009,20(2):189-201.

[16] BLEI D M,NG A Y,JORDAN M I.Latent Dirichlet Allocation[J].Journal of Machine Learning Research,2003,3(1):993-1022.

[17] LIU H,WU Z,CAI D,et al.Constrained Nonnegative Matrix Factorization for Image Representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(7):1299-1311.

[18] WANG Q,CAO Z,XU J.Group Matrix Factorization for Scalable Topic Modeling[C]//Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval.New York,USA:ACM Press,2012:375-384.

[19] 舒振球,趙春霞.基于局部學(xué)習(xí)的受限非負(fù)矩陣分解算法[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,43(7):82-86.

[20] 杜世強(qiáng),石玉清,王維蘭,等.基于圖正則化的半監(jiān)督非負(fù)矩陣分解[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(36):194-200.

[21] 藍(lán) 龍.半監(jiān)督非負(fù)矩陣分解算法及其在文本聚類中的應(yīng)用[D].長沙:國防科學(xué)技術(shù)大學(xué),2012.