基于聯(lián)合非負(fù)矩陣分解的話題變遷檢測方法

, ,

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

0 概述

近年來,互聯(lián)網(wǎng)新聞報道平臺(如LexisNexis、Google新聞和GDELT)已經(jīng)成為用戶觀察新聞話題變遷趨勢的重要來源。然而,這種新聞?wù)Z料庫面臨著信息冗余的問題,特別是針對同一事件的內(nèi)容的重復(fù)報道和新聞之間的互相轉(zhuǎn)載報道,造成了讀者對互聯(lián)網(wǎng)新聞事件的閱讀困難。關(guān)注話題變遷對人們理解和分析社會事件發(fā)展趨勢有著積極的意義。話題變遷是指一個話題隨著時間變化的過程,一般包含話題提出、話題發(fā)展、話題減少和話題消失等4個階段[1]。在話題變遷過程中,話題的內(nèi)容通常隨時間的變化而改變,即時序文檔中包括相似話題和異同話題。因此,識別異同話題及其發(fā)生時刻是一個挑戰(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與時間上下文特征相結(jié)合[4]。其他基于LDA改進(jìn)的話題模型,例如Link-LDA[5]、關(guān)系話題模型[5]和LTECS模型[6],是在LDA模型中添加地理信息或者上下文背景信息等特征元素來提高話題發(fā)現(xiàn)的準(zhǔn)確率。因為聚類的質(zhì)量會隨著特征矩陣的維度的增加而減小[7],所以上述方法具有以下問題:1)LDAs相關(guān)方法不適合從時序文檔中發(fā)現(xiàn)異同話題,其原因是隨著時間發(fā)展,舊話題消失和新的話題出現(xiàn);不同的時間范圍內(nèi)話題的數(shù)量也是不同的,上述原因?qū)υ掝}發(fā)現(xiàn)的效果影響很大。2)因為LDAs的時間復(fù)雜度與話題數(shù)和詞袋中詞語數(shù)的乘積呈線性關(guān)系,所以LDAs方法在用于大規(guī)模文檔的話題提取任務(wù)時具有較高的時間復(fù)雜度。

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

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

1 符號定義

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

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

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

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

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

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

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

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

X≈W×HT

(1)

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

(2)

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

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

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

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

(3)

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

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

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

(4)

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

2.1.3 懲罰函數(shù)

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

(5)

根據(jù)式(5),在矩陣分解的過程中,文中利用最小化基矩陣W1和W2元素之間的平方差來聚類相似的話題。在式(5)中,W1,d×W2,d中的第(i,j)個元素表示矩陣W1和W2的內(nèi)積的值,即W1中第i個話題向量和W2中第j個話題向量的乘積。因此,式(5)中的SFt就表示矩陣W1,d和W2,d之間的所有列向量的內(nèi)積。其中R2(W1,d,W2,d)中的部分元素的數(shù)值將變?yōu)榱?這樣就可以讓每一個話題詞只能對應(yīng)于一個話題類別。通過迭代計算,可以在2個數(shù)據(jù)集之間找到更多的異同話題。然后利用式(5)來計算式(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個部分:1)最小化懲罰函數(shù)R1(W1,c,W2,c)來計算2個矩陣W1,c和W2,c的值,它們表示2個數(shù)據(jù)集D1和D2的相似話題。2)最小化懲罰函數(shù)R2(W1,d,W2,d)來計算2個矩陣W1,d和W2,d的值,這2個矩陣代表的是文檔集D1和D2之間的異同話題。3)為參數(shù)ω1和ω2選擇適當(dāng)?shù)闹狄云胶?個懲罰函數(shù)R1(W1,c,W2,c)和R2(W1,d,W2,d)的權(quán)重比例。該迭代算法的主要思想是:坐標(biāo)下降法并不是尋求整個變量的梯度,而是沿著變量的每個維度單變量的進(jìn)行循環(huán)地優(yōu)化。如果函數(shù)在當(dāng)前迭代中未優(yōu)化,則表明已達(dá)到其駐點。因此,該算法可以保證每個極值點就是一個駐點。

大多數(shù)近似算法分別計算矩陣W和H。本文將矩陣Wi和Hi的乘積作為基組,利用式(7)計算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個文檔集中的文檔數(shù)目,m代表的是D1和D2中的詞袋中所有的詞語的數(shù)目。

2.3 算法分析

標(biāo)準(zhǔn)NMF算法采用的是基于迭代計算的優(yōu)化方法[14],算法的時間開銷主要用于矩陣之間的相乘計算,其時間復(fù)雜度取決于待處理的語料庫的大小,達(dá)到穩(wěn)定點時平均的迭代的次數(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)話題熵的值越大時,話題S越可能是噪聲話題。使用式(9)計算每個話題的話題熵,預(yù)先設(shè)定一個話題熵閾值g,所有小于閾值g的話題熵所對應(yīng)的話題S被視為優(yōu)質(zhì)話題。

3 實驗與結(jié)果分析

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

3.1 實驗數(shù)據(jù)集

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

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

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

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

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

3.2 評估指標(biāo)

本文使用2個常用的度量指標(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ù)δ(x,y)的值為1;否則函數(shù)為0。排序映射函數(shù)map(γi)的作用,是將樣本γi的每個標(biāo)簽都映射到等效的標(biāo)簽上。

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

(11)

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

3.3 實驗設(shè)計與分析

實驗設(shè)計與分析過程如下:

1)20Newsgroups實驗結(jié)果分析。本文比較了ToD與其他6個話題發(fā)現(xiàn)算法在20Newsgroups數(shù)據(jù)集上的實驗結(jié)果,分別是LDA[16]、NMF[8]、GNMF[17]、CNMF[17]、LLRNMF[18]和JNMF[9]。后5種方法的實驗結(jié)果源自文獻(xiàn)[9,19]。所有方法的準(zhǔn)確度和NMI的實驗結(jié)果如圖4所示,其中,整個矩形是指算法在該指標(biāo)上的最大值,矩形下部的實心部分是指算法的最小得分,而矩形上部的陰影部分是算法在該指標(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個單獨文檔集之間的共同和不同話題,而ToD方法通過將時間參數(shù)t引入到NFt和SFt中,以改進(jìn)矩陣迭代計算期間的懲罰函數(shù)的值。這樣就可以比較在不同時間戳下的多個文檔集之間的相似話題矩陣和異同話題矩陣。因此,ToD可以發(fā)現(xiàn)并跟蹤多個文檔集之間的時序異同話題。由于同樣的原因,JNMF對多個文檔集中的話題的連續(xù)性考慮較少,這降低了話題提取的準(zhǔn)確性。

本文進(jìn)一步比較和分析了不同k值下的實驗結(jié)果,如圖5所示,從左到右分為LDA、NMF、GNMF、CNMF、LLRNMF和ToD算法的NMI指標(biāo)。圖5顯示了在所有方法的NMI指標(biāo)中,ToD的方法優(yōu)于其他方法,當(dāng)增加話題數(shù)k時,其他5個算法的NMI值明顯減小,而ToD算法在不同k值的情況下依然保持著穩(wěn)定的值。標(biāo)準(zhǔn)NMF獲得最低的NMI得分,是因為該方法較少的使用了文檔集中的標(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ù)據(jù)分析。本文使用ToD算法來處理LTN2011數(shù)據(jù)集,并將1997年—2011年期間關(guān)于拉丁美洲非法移民的話題變遷趨勢可視化。

(1)數(shù)據(jù)準(zhǔn)備。本文使用以下步驟處理原始新聞數(shù)據(jù):首先從文本中移除屬性的標(biā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個文檔集中提取特征可以得到2個輸入矩陣X1和X2。最后在2個矩陣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ù)的實驗結(jié)果如圖6所示。可以看出,ToD算法在k=10時獲得最好的聚類效果。而且當(dāng)k值從1變到10時,ToD算法的NMI保持穩(wěn)定。

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

3.4 案例分析

本文分析了1997年—2004年和2005年—2011年2個時間范圍每年的拉丁美洲威脅事件的話題演變。通過使用ToD算法,本文從LTN2011文檔集中提取相似和異同話題及其話題詞。下文通過使用詞云和折線趨勢圖的方式來顯示所有發(fā)現(xiàn)的話題內(nèi)容及話題的變遷趨勢。圖7展示出了4個相似話題的每年的變遷趨勢示例。每個折線圖部分都表示與拉丁美洲移民事件相關(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個角度展示了非法移民的最相關(guān)話題詞:公民合法性和就業(yè)合法性。這2個話題詞在非法移民問題的關(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)顯示了一個新的相關(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(非法移民和人口販運)”的相關(guān)話題。注意到從1997年到2004年,關(guān)注的焦點一直在諸如“smuggle(走私)”、“truck(卡車)” “charge(費用)”“passport(護(hù)照)”“death(死亡)”“cargo(貨物)”等。雖然在隨后的幾年(從2004年—2011年),這個話題有更高的關(guā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)表明,新聞媒體不斷著重于移民問題消極方面的報道,即判定拉丁美洲移民問題為刑事犯罪,例如“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個不同話題的變遷趨勢示意圖

4 結(jié)束語

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

[1] 楚克明,李 芳.基于LDA模型的新聞話題的演化[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].計算機工程與應(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é)報(自然科學(xué)版),2015,43(7):82-86.

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

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