屠雄剛 陳 軍 楊 璐 嚴(yán)建峰

（1.浙江工業(yè)職業(yè)技術(shù)學(xué)院設(shè)計(jì)與藝術(shù)學(xué)院 紹興 312000 2.蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 蘇州 215006 3.蘇州大學(xué)江蘇省計(jì)算機(jī)信息處理技術(shù)重點(diǎn)實(shí)驗(yàn)室 蘇州 215006）

1 引言

潛在狄利克雷分配（Latent Dirichlet Allocation,LDA）[1]是識別大規(guī)模文本集或語料庫中潛在主題信息的概率主題模型，它能夠?qū)卧~空間中的文檔變換到主題空間，得到文檔在低維空間中的表達(dá)。LDA 假定每篇文檔是主題的一個(gè)概率組合，而主題是單詞表中單詞的多項(xiàng)分布。文檔-主題分布可以看作是文檔在主題空間的表示，能夠被用來分類以及檢索，而主題在單詞的分布能被用來表示主題的意義。然而這樣的LDA 模型不能直接控制推理參數(shù)的后驗(yàn)稀疏度。

在文本模型中語義空間的稀疏表示具有實(shí)際的應(yīng)用價(jià)值，通常每篇文檔或每個(gè)單詞只有幾個(gè)突出的主題意義，而不是在每個(gè)主題上都有非0 的值。單詞的主題分布越稀疏就能越清晰的反映出單詞的主題意義，在模型參數(shù)估計(jì)和推理的過程中增加稀疏限定可以提高模型的精度。稀疏主題編碼（Sparse Topical Coding，STC）[2]是發(fā)現(xiàn)大規(guī)模文本集隱藏表示的非概率主題模型，與概率主題模型不同，STC松弛了混合比例和最大似然函數(shù)的標(biāo)準(zhǔn)化限定，使用稀疏規(guī)則化的方法直接控制推斷表示的稀疏性，無縫地結(jié)合凸誤差函數(shù)到監(jiān)督學(xué)習(xí)中，有效地學(xué)習(xí)半監(jiān)督結(jié)構(gòu)化的條件下降算法。稀疏編碼的潛在狄利克雷分配（SCLDA）[3]是一個(gè)加入稀疏限定的基于連續(xù)特征的主題模型，假定連續(xù)單詞的概率分布是拉普拉斯分布，該分布的參數(shù)依賴于主題，使用期望最大化（Expectation Maximization,EM）算法估計(jì)模型參數(shù)，該模型在計(jì)算機(jī)視覺問題中取得了不錯(cuò)的效果。稀疏隱藏語義分析（Sparse Latent Semantic Analysis,SLSA）[4]在L1范數(shù)約束的條件下產(chǎn)生了一個(gè)稀疏投影矩陣。與傳統(tǒng)的LSA 相比，SLSA 緊緊選擇每個(gè)主題的少數(shù)幾個(gè)單詞，提高了主題-單詞分布的可解釋性，在內(nèi)存和效率上也有相應(yīng)改進(jìn)。變分貝葉斯（Variational Bayes，VB）[1]、塌陷吉布斯采樣法（Collapsed Gibbs Sampling，GS）[5]以及消息傳遞算法（Belief Propagation，BP）[6]是LDA 的三種近似推理算法。BP 算法把計(jì)算全局積分的過程分散到各個(gè)節(jié)點(diǎn)的信息傳遞，而各個(gè)節(jié)點(diǎn)和鄰近節(jié)點(diǎn)交互信息，它在效率和準(zhǔn)確率上都明顯優(yōu)于VB 和GS 算法。本文的研究是在消息傳遞算法的基礎(chǔ)上進(jìn)行的。

LDA 模型的先驗(yàn)參數(shù)可以在一定程度上控制文檔-主題分布和主題-單詞分布的稀疏度，然而因概率主題模型的標(biāo)準(zhǔn)化操作而很難獲得稀疏的主題表示。稀疏非負(fù)矩陣分解[7]提供了一個(gè)在原來算法基礎(chǔ)上獲得向量稀疏表示的基本框架。本文在前人研究的基礎(chǔ)上，提出了稀疏限定的消息傳遞算法（sparseBP），用基于L1范數(shù)和L2范數(shù)的方法度量向量的稀疏度，在算法的迭代過程中投影單詞在主題上的概率分布到稀疏空間，從而得到特定稀疏度的單詞在主題上的分布。本文也探索了sparseBP 的聚類性能，并把sparseBP 看作是一種降維算法，把文檔在主題上的分布作為libsvm 分類器的輸入探索文本分類準(zhǔn)確率。

2 消息傳遞算法

消息傳遞（Belief propagation,BP）最初被機(jī)器學(xué)習(xí)專家用于樹狀結(jié)構(gòu)的統(tǒng)計(jì)推斷，后來這種算法忽略掉它本來對樹狀結(jié)構(gòu)的要求而應(yīng)用與帶環(huán)的模型。文獻(xiàn)[1]在馬爾科夫隨機(jī)場的框架下證明了在主題模型意義下LDA 是一種特殊的因子圖，并提出用消息傳遞算法近似求解LDA 模型。本文中用到的符號見表1。

表1 符號標(biāo)簽Tab.1 Symbol labels

圖1 基于因子圖的消息傳遞Fig.1 Message passing based on factor graph

這里 -w 表示除了單詞w 以外的所有單詞，-d表示除了文檔d 以外的所有文檔。信息更新式（1）取決于除了當(dāng)前信息μw,d以外的所有其他鄰接信息μ-(w,d)。文檔-主題分布θ 和主題-單詞分布φ 的計(jì)算公式為

信息更新過程將通過迭代公式（1），直到信息收斂于一個(gè)固定的點(diǎn)。算法的執(zhí)行過程如圖2 所示，算法的迭代過程分為兩個(gè)步驟，第一步更新每個(gè)單詞的主題分布μw,d,第二步用更新的消息μw,d估計(jì)參數(shù)dθ 和wφ 。

圖2 消息傳遞算法Fig.2 Message passing algorithm

3 稀疏消息傳遞算法

本節(jié)首先描述稀疏度的概念，然后介紹如何把稀疏度結(jié)合進(jìn)LDA 模型的消息傳遞中，最后介紹算法具體執(zhí)行過程。

3.1 稀疏度

向量稀疏度的度量可以用向量中0 元素的數(shù)目與向量維度的比值來計(jì)算。對于大部分元素取值接近與0 而只有幾個(gè)有意義的非0 值的向量會有一個(gè)較低的稀疏度，然而在實(shí)際應(yīng)用中，這樣的向量被認(rèn)為有一個(gè)較高的稀疏度。本文使用基于L1_norm和L2_norm的稀疏度度量方式[7]

其中K 表示μ 的維度，當(dāng)向量μ 只有一個(gè)非0的元素時(shí)稀疏度為1，當(dāng)向量μ 的所有元素都相等時(shí)稀疏度為0。

3.2 稀疏限定的消息傳遞

消息傳遞算法可以看作是對語料庫中的單詞分配標(biāo)簽的過程，通常每個(gè)單詞的主題集合只有小部分是活躍的。在消息傳遞算法的迭代過程中對于單詞-文檔矩陣中的非0 元素都需要通過公式1 來得到單詞的主題分布，這個(gè)分布往往是很稀疏的。稀疏度隨著迭代次數(shù)的增加而不斷增加。像“l(fā)earning，paper，algorithm”這樣的常用詞往往有一個(gè)較低的稀疏度，而像“network neural genetic”這樣的關(guān)鍵詞有較高的稀疏度。主題模型中主題數(shù)目K 通常是啟發(fā)性的設(shè)置或者是通過非參數(shù)的貝葉斯模型學(xué)習(xí)得到，當(dāng)K 初始設(shè)置的數(shù)目比較大時(shí)，常用詞和關(guān)鍵詞的主題分布的稀疏度可能有更大的差距。本文中我們固定主題在單詞分布上的稀疏度，每次迭代得到μw,d后把它投影到與它距離最近的稀疏空間中去，而向量的稀疏度可以自由設(shè)定，通常越稀疏的向量越能清晰的反應(yīng)單詞的主題分布。然后整合出LDA 模型的兩個(gè)輸出文檔-主題分布和主題-單詞分布。這種增加稀疏度限定的消息傳遞算法稱為稀疏消息傳遞算法（sparseBP），算法的具體執(zhí)行過程如圖3 所示。

圖3 稀疏消息傳遞算法Fig.3 Sparse message transfer algorithm

投影向量到稀疏度為S 的空間的具體操作如算法3 所示，該算法首先投影給定的向量到L1的空間中，然后投影到與之最接近的由L1和L2聯(lián)合限定的空間中。如果投影結(jié)果完全是非負(fù)的，就退出循環(huán)，而如果有負(fù)值，把負(fù)值設(shè)置為0，然后在額外限定的條件下去尋找一個(gè)新的點(diǎn)。原則上，算法的迭代次數(shù)和向量的維度是相等的，因?yàn)樗惴ǖ囊淮蔚^程或者是收斂，或者是增加一個(gè)值為0 的元素。而事實(shí)上，算法可以收斂的更快。

3.3 復(fù)雜度分析

消息傳遞算法需要存儲單詞的主題概率分布，在存儲和計(jì)算方面都要乘以主題數(shù)目K 的倍數(shù)，消息傳遞算法的時(shí)間復(fù)雜度 O (KDWdT)，sparseBP 在BP 算法的基礎(chǔ)上增加了投影操作，sparseBP 的時(shí)間復(fù)雜度為 O (K2DWdT)。sparseBP 在投影的過程中增加了幾個(gè)維度為K 的向量，然而它的空間復(fù)雜度與消息傳遞算法相同，均為 O (K * NNZ)，其中D 是輸入文檔-單詞共現(xiàn)矩陣的列數(shù)，Wd是共現(xiàn)矩陣每一列中非零單元 xw,d≠ 0的個(gè)數(shù)，T 是算法的迭代次數(shù)，NNZ 為單詞-文檔共現(xiàn)矩陣中非0 元素的總數(shù)目。

圖4 投影向量到稀疏度為s 的空間的算法Fig.4 projection vector to the sparse degree s of space algorithm

4 實(shí)驗(yàn)分析

本文的實(shí)驗(yàn)在Matlab C/C++MEX 平臺上進(jìn)行，這個(gè)平臺在文獻(xiàn)[8]中已經(jīng)被使用。先驗(yàn)參數(shù)初始化設(shè)置為 α=2/K， β=0.01，這里K 是主題的數(shù)目，對于所有的算法分別做300 次迭代并運(yùn)行5 次計(jì)算其均值。每篇文檔中單詞的概率分布μw,d的稀疏度S 在0.7～0.9 之間變化時(shí)，效果基本一致，這里固定S 為0.8。本文采用標(biāo)準(zhǔn)化互信息來評估文檔聚類的準(zhǔn)確率，并使用常用的聚類方法BP，GS，非負(fù)矩陣分解（Non-negative Matrix Factorization,NMF）[9]，譜聚類（Spectral Clustering,SC）[10]來進(jìn)行對比。此外，使用消息傳遞算法對文檔-單詞共現(xiàn)矩陣進(jìn)行降維，并借助于libsvm 測量文本的分類準(zhǔn)確率，使用BP，GS 和NMF 來和sparseBP 進(jìn)行對比。在評價(jià)sparseBP 在文檔聚類和分類中相比其它算法提高的百分比時(shí)本文采用的計(jì)算公式為：

4.1 數(shù)據(jù)集選擇

本文在英文語料上進(jìn)行測試，采用CORA[11]和TEUTERS[12]兩個(gè)通用的文本數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)所用文本數(shù)據(jù)如表1 所示，這里D 是文檔的總數(shù)目，W 是單詞表的大小，N 是文檔中單詞的總數(shù)目，Ave( d) 是文檔的平均長度，classes 是文檔集中文檔的類別數(shù)目。文檔去除了停用詞以及單詞的后綴，采用1-Gram 的表示法，使用單詞在文檔中出現(xiàn)的次數(shù)作為文檔的特征。

表2 數(shù)據(jù)集Tab.2 Data sets

4.2 文檔聚類分析

稀疏消息傳遞算法可以用來做文本聚類，算法得到文檔在主題的分布 θd(k)是文檔在主題上的概率分布，在模型的訓(xùn)練過程中不使用數(shù)據(jù)真實(shí)的類別標(biāo)簽，得到 θd(k)后選出每篇文檔最可能的主題，并使用標(biāo)準(zhǔn)化互信息評估算法的聚類準(zhǔn)確率。

4.2.1 聚類評價(jià)標(biāo)準(zhǔn)

標(biāo)準(zhǔn)化互信息（Normalized Mutual Information,NMI）[13]是一種被廣泛應(yīng)用的外部聚類評價(jià)標(biāo)準(zhǔn)，通過比較數(shù)據(jù)集的聚類結(jié)果和該數(shù)據(jù)集的真實(shí)劃分的相似程度來實(shí)現(xiàn)，而在聚類過程中不使用文檔的類別標(biāo)簽。NMI 可以在預(yù)測類別和真實(shí)類別不同時(shí)利用互信息進(jìn)行評測，NMI 的計(jì)算公式為：

式中，hn 是類別為h 的文檔的總數(shù)目，ln 是類別為l的文檔的總數(shù)目，nh,l是同時(shí)為類別h 和l 的文檔的總數(shù)目，n 是數(shù)據(jù)集中文檔的總數(shù)目，h 是真實(shí)的類別標(biāo)簽，l 是用聚類算法得到的預(yù)測類別標(biāo)簽。NMI 是介于0～1之間的值，當(dāng)聚類標(biāo)簽和外部真實(shí)標(biāo)簽完全一致時(shí)NMI 值為1，而當(dāng)隨機(jī)劃分時(shí)NMI值為0，NMI 值越大表示有越好的聚類準(zhǔn)確率。

4.2.2 聚類實(shí)驗(yàn)結(jié)果

圖5 和圖6 分別表示了當(dāng)主題數(shù)目K={50,75,100,125,150}時(shí)5 種算法在CORA 和TEUTERS 數(shù)據(jù)集上的NMI。從圖中可以看出，在兩個(gè)數(shù)據(jù)集上sparseBP 的NMI 都是最好的，勝過了其它的文本聚類方法，例如，在CORA 數(shù)據(jù)集上，當(dāng)主題數(shù)目為100 時(shí)，sparseBP 勝過其它四種方法分別為3.67%，9.68%，32.21%和60.18%。結(jié)果表明稀疏消息傳遞算法提高了文檔聚類的準(zhǔn)確率。

圖5 CORA 數(shù)據(jù)集上的NMI 比較Fig.5 NMI comparison on CORA data sets

圖6 TEUTERS 數(shù)據(jù)集上的NMI 比較Fig.6 NMI comparison on TEUTERS data sets

4.3 文檔分類分析

首先使用sparseBP 把語料庫中的文檔-單詞矩陣投影到隱藏主題空間當(dāng)中得到文擋-主題分布，然后以4：1 的比例隨機(jī)劃分低維的文檔特征數(shù)據(jù)為訓(xùn)練集和測試集，最后根據(jù)已知文檔的類別標(biāo)簽使用libsvm 分類器去分類文檔。在使用libsvm 分類時(shí)，采用網(wǎng)格搜索法學(xué)習(xí)參數(shù)C 和G。

4.3.1 分類評價(jià)標(biāo)準(zhǔn)

準(zhǔn)確率（Accuracy）是評價(jià)文本分類結(jié)果優(yōu)劣的一種常用評價(jià)標(biāo)準(zhǔn)，其計(jì)算公式為：

Accuracy 是介于0%～100%之間的值，越高的類別準(zhǔn)確率暗示基于主題的低維特征具有越好的區(qū)分能力，即在降維的過程中提取到了高質(zhì)量的文檔特征。

4.3.2 分類實(shí)驗(yàn)結(jié)果

圖7 和圖8 分別顯示了當(dāng)主題數(shù)目K={50,75,100,125,150}時(shí)5 種算法在CORA 和TEUTERS 數(shù)據(jù)集上的Accuracy。從圖中可以看出sparseBP 總是有最好的分類準(zhǔn)確率，例如，在CORA 數(shù)據(jù)集上，當(dāng)主題數(shù)目為100 時(shí)，sparseBP 勝過BP，GS 和NMF分別為3.81%，8.21%和14.03%。在RETURE 數(shù)據(jù)集上，當(dāng)主題數(shù)目為100 時(shí)，sparseBP 勝過BP，GS 和NMF 分別為1.83%，1.73%和0.18%。譜聚類不能獲得文檔-主題這樣的分布，于是這里沒有相關(guān)對比結(jié)果。

圖7 CORA 數(shù)據(jù)集上的Accuracy 比較Fig.7 Accuracy comparison on CORA data sets

圖8 TEUTERS 數(shù)據(jù)集上的Accuracy 比較Fig.8 Accuracy comparison on TEUTERS data sets

5 結(jié)束語

本文提出了把稀疏限定加入到消息傳遞算法中，在迭代的過程中將向量投影到稀疏空間中去，同時(shí)也探索該方法對文本聚類以及分類準(zhǔn)確率的影響。豐富的實(shí)驗(yàn)結(jié)果表明本文提出的加入基于 L1范數(shù)和L2 范數(shù)的稀疏消息傳遞算法提高了文本的聚類以及分類準(zhǔn)確率。進(jìn)一步的研究工作將主要圍算法在其它方面的應(yīng)用以及時(shí)間效率的因素開展，以便使算法適應(yīng)于更多的應(yīng)用并提高算法的執(zhí)行效率。

[1]David M.Blei,Andrew Ng and Michael Jordan,Latent Dirichlet Allocation[C].Neural Information Processing Systems,2001:601-608.

[2]Jun Zhu and Eric P.Xing.Sparse Topical Coding[C].Uncertainty in Artificial Intelligence,2011:267-286.

[3]Wenjun Zhu,Liqing Zhang and Qianwei Bian.A hierarchical latent topic model based on sparse coding[J].Neuro Computing,2012,76(1):28-35.

[4]Xi Chen,Yanjun Qi,Bing Bai,Qihang Lin and Jaime G.Carbonell.Sparse latent semantic analysis[C].SIAM International Conference on Data Mining,2011:474-485.

[5]Gregor Heinrich.Parameter Estimation for Text Analysis[R]. Fraunhofer IGD,2004.

[6]Jia Zeng,William K.Cheung,Jiming Liu,Learning topic models by belief Propagation[J],IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,33(5):1121-1134.

[7]Patrik O.Hoyer.Non-negative Matrix Factorization with Sparseness Constraints[J].Journal of Machine Learning Research,2004,5(1):1457-1469.

[8]Jia Zeng.A topic modeling toolbox using belief propagation[J],Journal of Machine Learning Research,2012,13(1) 2233-2236.

[9]Daniel D.Lee and H.Sebastian Seung.Algorithms for non-negative matrix factorization[C],Neural Information Processing Systems,2002:556-562.

[10]Ulrike Luxburg.A Tutorial on Spectral Clustering[J].Journal Statistics and Computing,2007,17(4):395-416.

[11]Andrew McCallum,Kamal Nigam,Jason Rennie and Kristie Seymore.Automating the construction of internet portals with machine learning[J].Information Retrieval,2000,3(2):127-163.

[12]Deng Cai,Xiaofei He,Jiawei Han.Document clustering using locality preserving indexing[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(12):1624-1637

[13]Shi Zhong and Joydeep Ghosh.Generative modelbased document clustering:a comparative study[J].Knowledge and Information Systems,2005,8(3):374-384.