詹增榮,程 丹

(1.廣州番禺職業(yè)技術(shù)學(xué)院，中國 廣州 511483；2.廣州體育職業(yè)技術(shù)學(xué)院，中國 廣州 510650)

?

基于LDA與距離度量學(xué)習(xí)的文本分類研究

詹增榮1*,程 丹2

(1.廣州番禺職業(yè)技術(shù)學(xué)院，中國 廣州 511483；2.廣州體育職業(yè)技術(shù)學(xué)院，中國 廣州 510650)

提出了一種基于隱含狄利克雷分布(LDA)與距離度量學(xué)習(xí)(DML)的文本分類方法，該方法利用LDA為文本建立主題模型，借助Gibbs抽樣算法計算模型參數(shù)，挖掘隱藏在文本內(nèi)主題與詞的關(guān)系，得到文本的主題概率分布.以此主題分布作為文本的特征，利用DML方法為不同類別的文本學(xué)習(xí)馬氏距離矩陣，從而較好的表達(dá)了文本之間的相似性.最后在學(xué)習(xí)到的文本間距離上，利用常用的KNN及 SVM分類器進(jìn)行文本分類.在經(jīng)典的3個數(shù)據(jù)集中的實驗結(jié)果表明，該方法提高了文本分類的準(zhǔn)確率，并且在不同的隱含主題數(shù)目參數(shù)下能體現(xiàn)較好的穩(wěn)定性.

文本分類；距離度量學(xué)習(xí)；隱含狄利克雷分布；主題模型

隨著互聯(lián)網(wǎng)的高速發(fā)展，文本數(shù)據(jù)作為最主要的信息載體之一以指數(shù)級的速度不斷增長.因此，如何有效地從海量文本數(shù)據(jù)中挖掘出有用的信息成為當(dāng)前的迫切需求.文本自動分類技術(shù)作為自然語言處理的關(guān)鍵技術(shù)近年來廣泛受到關(guān)注并得到了快速的發(fā)展，已成為當(dāng)前研究的熱點.文本自動分類的過程中主要的技術(shù)包括了文本的預(yù)處理、特征的提取、文本的表示、分類器的設(shè)計，以及分類效果的評估等.

在文本分類研究中，向量空間模型(Vector Space Model，VSM)[1]是數(shù)據(jù)挖掘領(lǐng)域經(jīng)典的分析模型之一.VSM利用統(tǒng)計詞在文本和文本集中出現(xiàn)的頻率來表征詞對文本的重要性，最終將文本表示成一個向量，并通過余弦等不同的距離度量方式來計算文本之間的相似度.然而，由于自然語言的復(fù)雜性，類似文本語義等復(fù)雜問題并不能在VSM中得到建模，而且利用VSM表示文本得到的數(shù)據(jù)空間是極度高維且稀疏的.近年來，以隱含狄利克雷分布(Latent Dirichlet Allocation,LDA)[2]為代表的主題模型成為研究的熱點.基于LDA主題模型進(jìn)行建模能很好地考慮文本語義的相似性問題，因而被廣泛應(yīng)用到各個文本分類算法中，如Bao[3]、姚全珠[4]、李文波[5]等都使用LDA模型來對文本進(jìn)行分類.

樣本間的距離度量是模式識別領(lǐng)域研究的核心問題之一，它對分類、聚類等模式分析任務(wù)非常重要，如K近鄰、支持向量機(jī)等分類算法的準(zhǔn)確率就非常依賴于距離的定義.在文本分類中，為文本的特征向量選擇適合的距離度量方法將直接影響到最終分類的效果.為此，許多學(xué)者分別提出了不同類型距離度量學(xué)習(xí)(Distance Metric Learning，DML)方法，即從給定訓(xùn)練集的相似或不相似的樣本中學(xué)習(xí)一個距離度量來提高分類或聚類等任務(wù)的準(zhǔn)確率.Davis[6]等給出了一種基于信息理論的方法去學(xué)習(xí)一個馬氏距離，Weinberger[7]等闡述了就提高KNN分類器的準(zhǔn)確率中的大間距框架的距離學(xué)習(xí)問題，Kulis[8]等給出了距離學(xué)習(xí)的綜述.多數(shù)的DML研究都是著重在尋找一個線性矩陣來最優(yōu)化全局?jǐn)?shù)據(jù)間的可分離性和緊湊性，但是如果不同類別的數(shù)據(jù)呈現(xiàn)出不同的分布，尋找一個適合全局?jǐn)?shù)據(jù)的距離度量線性矩陣往往不太現(xiàn)實.一個可行的方法是針對不同的局部數(shù)據(jù)來學(xué)習(xí)不同的線性矩陣，從而滿足不同局部數(shù)據(jù)的最佳距離度量矩陣.

基于以上考慮，本文提出基于LDA和距離度量學(xué)習(xí)的文本分類方法.該方法首先利用LDA模型對文本集進(jìn)行建模，即利用文本的統(tǒng)計特性將文本語料映射到各個主題空間，挖掘隱藏主題與詞的分布，從而得到文本的主題分布.然后，以此分布為文本特征，針對不同類別的文本通過距離度量學(xué)習(xí)得到適合該類別文本與其他文本最佳距離度量矩陣.最后，根據(jù)得到的不同類別文本的距離度量矩陣計算文本數(shù)據(jù)與該類別文本間的距離，再放到常見的KNN[9]或SVM[10]分類器中實現(xiàn)文本的分類.

1 相關(guān)理論

1.1 LDA模型

LDA模型[2]是由Blei提出等人在2003年提出的一種對離散數(shù)據(jù)集建模的主題概率模型.LDA模型相對于傳統(tǒng)的LSI[11]和PLSI[12]等模型不僅具有更加清晰的層次結(jié)構(gòu)而且解決了隨著訓(xùn)練文本數(shù)目增加主題個數(shù)不斷增加導(dǎo)致的過渡擬合問題，從而更加適合于大規(guī)模語料庫分析.

LDA是一種非監(jiān)督機(jī)器學(xué)習(xí)技術(shù)，它的基本思想是文本由多個潛在的主題所構(gòu)成，而每個潛在的主題又由文本中若干個特定詞匯構(gòu)成.它將文本、主題、詞的結(jié)構(gòu)構(gòu)成三層貝葉斯概率模型，即文本中的主題服從Dirichlet分布，且任一主題中出現(xiàn)的詞服從多項式分布.如圖1所示，LDA模型具有非常清晰的層次結(jié)構(gòu).

給定一個文本集合D={d1,d2,…,dN}和隱含主題數(shù)K,LDA模型將按照圖2所示的有向概率圖來生成文本，其具體的過程如下：

圖1 LDA隱主題模型拓?fù)浣Y(jié)構(gòu)圖Fig.1 LDA topological structure graph

圖2 LDA隱主題模型有向概率圖Fig.2 LDA directed probability graph

1)對每個主題k∈{1,2,…,K},根據(jù)多項式分布φ～multinomial(β)得到該主題中詞多項式分布向量φk.

2)對文本集D中的文檔di,根據(jù)主題分布概率向量θ～Dir(α)，取樣生成文檔di的主題分布θi.

3)對文檔di的每個詞wij,j∈{1,2,…,Ni},Ni為文檔di中特征詞的數(shù)目：

a)根據(jù)多項式分布z～multinomial(θi)中取樣生成文檔di第j個詞所屬的主題zij.

b)設(shè)主題zij=k,根據(jù)主題的詞概率分布w～multinomial(φk)生成相應(yīng)的詞wij.

重復(fù)2和3過程直到文本集中所有的文本及文本的詞都生成完成后，最終得到每個文檔的主題概率分布和每個主題中詞的概率分布.因此，文檔di中的第j詞的概率為:

從而得到文本中每個詞的生成概率為P(wij,di)=P(di)·P(wij|di),式中P(di)為已知，結(jié)合先驗概率分布的參數(shù)α,β得到文檔di的概率密度為：

(1)

1.2 GP采樣

LDA對參數(shù)的估計比較常用的方法包括了變分推算方法和Gibbs抽樣方法.其中Gibbs抽樣算法屬于馬爾科夫鏈-蒙特卡羅(Markov Chain-Monte Carlo，MCMC)的一種特例，它通過構(gòu)造收斂于目標(biāo)概率分布的馬爾科夫鏈，并從鏈中抽樣出接近于該概率分布的樣本.由于Gibbs抽樣算法簡單且容易實現(xiàn)，對于聯(lián)合概率分布維度較高的情況非常適用，因此成為主題模型最常用的參數(shù)估計算法.

在式(1)中,需要估計的定參數(shù)有兩個，一個是在參數(shù)α下產(chǎn)生的文檔中主題的分布θ；第二是在確定主題后，由參數(shù)β產(chǎn)生的主題中詞的分布φ.利用Gibbs抽樣算法可以得到：

1.3 距離度量學(xué)習(xí)

歐式距離與馬氏距離作為最常用的樣本間距離度量方法，目前已經(jīng)被廣泛應(yīng)用到不同的分類算法中.兩個樣本xi和xj在Rd的歐式平方距離定義為：

d2(xi,xj)=‖xi-xj‖2=〈xi-xj,xj-xj〉,

而兩個樣本xi和xj在Rd中的馬氏平方距離

其中w是一個d×d的半正定參數(shù)矩陣.可以看出當(dāng)w為單位矩陣時，馬氏距離就是歐式平方距離.絕大多數(shù)距離度量學(xué)習(xí)是去學(xué)習(xí)w這個半正定矩陣來作為馬氏距離的參數(shù)，例如信息論度量學(xué)習(xí)[6]將距離度量問題轉(zhuǎn)化為Bregman最優(yōu)化問題，通過在線性條件限制下最小化LogDet散度來求得最優(yōu)化的w.在距離度量學(xué)習(xí)中，最優(yōu)化問題可以被描述成為在給定限制集合下的凸方程問題.既給定相似集合S={(i,j)|C(xi)=C(xj)}和不相似集合D={(i,j)|C(xi)≠C(xj)} 其中C(xi)表示xi的類別標(biāo)簽，距離學(xué)習(xí)問題可以被定義為：

(2)

如在KNN分類算法中，給定分類的樣本集x={xi|i=1,2,…,n}和樣本對應(yīng)的標(biāo)簽{yi|i=1,2,…,n}.對于xi的類別，KNN分類器根據(jù)xi的最近k個領(lǐng)域樣本集合中所屬的不同類別標(biāo)簽的數(shù)量比例來決定預(yù)測樣本的類別標(biāo)簽.因此，KNN分類器中xi的目標(biāo)鄰域樣本離xi越近，分類的準(zhǔn)確率就越高,即xi與其他樣本點的距離可以用以下限制式子來表達(dá).

最優(yōu)化式(2)中的目標(biāo)函數(shù)變成尋找W使得xi到它同類別的其他樣本的距離最小，且盡量減少違反(2)式中第二個限制.從而可以將(2)中優(yōu)化的目標(biāo)轉(zhuǎn)換為

(3)

式中前部分主要代表了樣本點到它領(lǐng)域的距離之和，而后半部分為對于那些違反了(2)式第二限制的樣本點的懲罰，γ來懲罰系數(shù).

在ITML[6]中兩個矩陣之間的布雷格曼散度的定義如下：

Dφ(X,Y)=φ(X)-φ(Y)-tr((φ(Y))T(X-Y)),

從而使得在距離度量學(xué)習(xí)中的優(yōu)化問題可以被描述為去尋找一個正定矩陣W使得它W0與間的散度距離在滿足一定的約束下最近.即在給定相似集合S和不相似集合D時，優(yōu)化問題可以表示為：

其中c(i,j)為第(i,j)個限制，ξ為包含松弛變量的向量，ξ0為包含判斷相似或不相似闕值的向量.

2 基于LDA與距離度量學(xué)習(xí)的文本分類

基于LDA與距離度量學(xué)習(xí)的文本分類算法主要是利用了LDA主題模型對文本進(jìn)行建模并使用Gibbs抽樣方法間接計算模型的參數(shù)，在確定了主題數(shù)目K等參數(shù)后，得到文本集中所有文本上的主題概率分布.以文本的主題概率分布為特征向量，文本已有的類別標(biāo)簽，并利用距離度量學(xué)習(xí)算法學(xué)習(xí)每個類別內(nèi)樣本與測試樣本的最優(yōu)距離，最后將得到的樣本間的最優(yōu)距離放入到KNN或SVM等分類器中進(jìn)行分類得到每個文本的類別.分類具體過程主要包括了文本的預(yù)處理、LDA建模、距離度量學(xué)習(xí)、文本分類等，算法的流程框架圖如圖3所示.

圖3 算法的流程圖Fig.3 Flowchart of the algorithm

2.1 文本預(yù)處理

針對實驗語料庫進(jìn)行清洗、去停用詞、提取詞干，并過濾冗余的信息，建立初步的文檔向量空間模型.

2.2 LDA建模

利用LDA算法對文本集合中的文本進(jìn)行主題建模，建模過程利用Gibbs抽樣方法來進(jìn)行參數(shù)估計,并確定了主題數(shù)目K和參數(shù)α,β.通過計算得到主題分布向量θ，并最終得到文本-隱主題分布矩陣.

2.3 距離度量學(xué)習(xí)

尋找一個馬氏距離矩陣來達(dá)到最優(yōu)化全局?jǐn)?shù)據(jù)間的可分離性和緊湊性是距離度量學(xué)習(xí)研究目的，但是在數(shù)據(jù)呈現(xiàn)出不同的分布的情況下，很難得到一個適合全局?jǐn)?shù)據(jù)的距離度量矩陣.因此，本節(jié)提出為不同的類別樣本數(shù)據(jù)學(xué)習(xí)一個適合該類別的馬氏距離矩陣w，用于表達(dá)該類別內(nèi)數(shù)據(jù)樣本與其他數(shù)據(jù)樣本的距離度量.

其中相似集合S和不相似集合D的定義為：當(dāng)學(xué)習(xí)某一類別p的馬氏距離矩陣時，S中的元素為該類別所有元素的二元組合，D中的為該類別的元素與其他類別元素的二元組合.

2.4 文本分類

根據(jù)LDA建模獲得的所有文本的主題概率分布矩陣，結(jié)合樣本類別信息利用距離度量學(xué)習(xí)算法計算出樣本之間的距離，然后放到常見的KNN或SVM分類器中進(jìn)行分類得到相應(yīng)的測試樣本的類別.

3 實驗設(shè)計與結(jié)果分析

3.1 實驗環(huán)境

實驗在CPU為Intel Core 8核、內(nèi)存為16G、操作系統(tǒng)為Windows 7的PC機(jī)上進(jìn)行.主要算法采用了Matlab來實現(xiàn)，LDA算法利用文[13]中提供的Matlab Toolbox來實現(xiàn)，距離度量學(xué)習(xí)算法及KNN分類器算法是在ITML[6]中的算法的基礎(chǔ)上改進(jìn)得到.SVM分類器選取了臺灣大學(xué)林智仁教授開發(fā)設(shè)計的LIBSVM[14]作為分類器的訓(xùn)練環(huán)境實現(xiàn).

3.2 實驗數(shù)據(jù)

實驗選擇了3個經(jīng)典的數(shù)據(jù)集Reuters21578，20Newsgroups和TDT2作為實驗的數(shù)據(jù)，數(shù)據(jù)來源及預(yù)處理都來自于文[15].Reuters21578是路透社1987年中新聞專線的文檔集合.它包含了21 578個樣本，分成135個類別.為了實驗方便剔除了屬于多個類別的樣本，并從中選取了最大的9個類別集合共7 258個數(shù)據(jù)作為實驗數(shù)據(jù).20Newsgroups文檔集合包含了18 846個文檔，平均分布為20個類別，為了減少實驗有效性，選取了全部類別作為實驗數(shù)據(jù).TDT2(NIST Topic Detection and Tracking)文檔集包含了來自6個不同新聞源的文檔集合，總共有11 201個文檔數(shù)據(jù)，并被分成96個語義類別.為了簡化實驗結(jié)果，剔除了屬于多個類別的文檔數(shù)據(jù)，最后只保留了9 394個文檔.所有的數(shù)據(jù)集合都按照文[15]的方法做了預(yù)處理，包括剔除無用詞語、應(yīng)用波特詞干算法等.最后都按照按照0.7的比例劃分訓(xùn)練集和測試集.

3.3 評估方法

為了較好地描述模型對文本分類的效果，實驗從分類的準(zhǔn)確率(Accuracy)、精確率(Precision)、召回率(Recall)、F測量來評估測試的結(jié)果，其中F測量是一種結(jié)合精確率和召回率的平衡指標(biāo).對于分類問題可以用表1所示的混合矩陣來表示分類結(jié)果的情況.根據(jù)表中的描述，實驗中各個評估方法的定義如下(其中一般取值為1)：

表1 分類評估混合矩陣

3.4 實驗結(jié)果分析

在經(jīng)典的3個數(shù)據(jù)集進(jìn)行預(yù)處理后分別采用3種算法進(jìn)行實驗，包括傳統(tǒng)的KNN分類；LDA建模后進(jìn)行KNN分類(LDA-KNN)；LDA建模后利用距度量離學(xué)習(xí)算法計算樣本間距離后再進(jìn)行KNN分類(LDA-DML-KNN).實驗得到結(jié)果如表2所示(其中LDA的主題數(shù)取值為100)，從表2中可以看出，基于LDA主題模型與KNN相結(jié)合算法(LDA-KNN)相對于傳統(tǒng)的KNN算法具有較高的準(zhǔn)確率，在Reuters和TDT數(shù)據(jù)集上的多項指標(biāo)都有超過15%的提高.而融合距離度量學(xué)習(xí)的分類算法(LDA-DML-KNN)比LDA-KNN算法在準(zhǔn)確率等指標(biāo)上具有5%左右的提升.

表2 經(jīng)典數(shù)據(jù)集上的實驗結(jié)果

鑒于主題數(shù)(T)的大小會影響實驗的效果，實驗針對不同的主題數(shù)目在3個數(shù)據(jù)集上分別使用KNN和SVM兩個分類器進(jìn)行了測試，測試結(jié)果如圖4所示,其中KNN的領(lǐng)域數(shù)目k=10,SVM采用了高斯核函數(shù)(其中參數(shù)σ=1/4)，且為了訓(xùn)練樣本間不同類別的樣本距離取樣本到相互間距離的中值.在3個實驗集合實驗結(jié)果中，當(dāng)主題數(shù)取得T=100時已經(jīng)具有較好的效果.其次，結(jié)果表明融合距離度量學(xué)習(xí)的分類算法不僅取得較高的準(zhǔn)確率且更加穩(wěn)定.此外，在實驗中SVM分類器比KNN分類具有更好的分類效果，特別是在20Newsgroups數(shù)據(jù)集上.

圖4 不同主題數(shù)在KNN和SVM上分類的實驗結(jié)果Fig.4 Experimental results for classification with different topic number in KNN and SVM

4 總結(jié)

本文將LDA主題模型和距離度量學(xué)習(xí)應(yīng)用到文本分類中，不僅將文本深層次的語義知識嵌入到模型中，并且學(xué)習(xí)了不同文本深層次語義之間的距離度量，從而提高了文本分類的準(zhǔn)確率.此外，由于LDA主題模型所建立的文本主題空間的維度要遠(yuǎn)遠(yuǎn)小于文本的向量空間模型，大大提高了計算了速度.在文本分類常用的3個實驗數(shù)據(jù)集進(jìn)行的實驗結(jié)果表明，該方法可以明顯提高文本分類效果，模型可以為數(shù)據(jù)挖掘、自然語言處理等學(xué)科的研究和實現(xiàn)提供借鑒與參考.

[1] SALTON G,WONG A,YANG C S.A vector space model for automatic indexing [J].Commun ACM,1975,18(11):613-620.

[2] BLEI D M,NG A Y,JORDAN M I.Latent Dirichlet allocation [J].Machine Learning Res,2003,29(3):993-1022.

[3] BAO Y,COLLIER N,DATTA A.A partially supervised cross-collection topic model for cross-domain text classification; proceedings of the 22nd ACM international conference on information & knowledge management[C].F.ACM,2013.

[4] 姚全珠,宋志理,彭 程.基于LDA模型的文本分類研究 [J].計算機(jī)工程與應(yīng)用,2011,13(1):150-153.

[5] 李文波,孫 樂,張大鯤.基于Labeled-LDA模型的文本分類新算法 [J].計算機(jī)學(xué)報,2008,31(4):620-627.

[6] DAVIS J V,KULIS B,JAIN P,etal.Information-theoretic metric learning[C]//Proceedings of the 24th international conference on Machine learning,F.ACM,2007.

[7] WEINBERGER K Q,SAUL L K.Distance metric learning for large margin nearest neighbor classification [J].Machine Learning Res,2009,10(2):207-244.

[8] KULIS B.Metric learning: A survey [J].Found Trends Machine Learning,2012,5(4):287-364.

[9] COVER T M,HART P E.Nearest neighbor pattern classification [J].Inf Theory,IEEE Trans,1967,13(1):21-27.

[10] BURGES C J C.A tutorial on support vector machines for pattern recognition [J].Data Mining Knowledge Discovery,1998,2(2):121-167.

[11] DUMAIS S T.Latent semantic indexing (LSI): TREC-3 report [J].Nist Special Publication SP,1995,9(2):219.

[12] THOMAS H.Probabilistic latent semantic indexing[C]//Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval,Berkeley,California,USA,F.ACM,1999.

[13] GRIFFITHS T L,STEYVERS M.Finding scientific topics [J].Proc Nat Acad Sci,2004,101(suppl 1):5228-5235.

[14] CHANG C C,LIN C J.LIBSVM: a library for support vector machines [J].ACM Trans Intell Syst Technol (TIST),2011,2(3):27.

[15] ZHANG D,WANG J,CAI D,etal.Self-taught hashing for fast similarity search[C]//Proceedings of the 33rd international ACM SIGIR conference on Research and development in information retrieval,F.ACM,2010.

(編輯 CXM)

Research on Text Classification Based on LDA and Distance Metric Learning

ZHANZeng-rong1*,CHENGDan2

(1.Guangzhou Panyu Polytechnic,Guangzhou 511483,China； 2.Guangzhou Polytechnic of Sport,Guangzhou 510650,China)

A text classification method based on Latent Dirichlet Allocation (LDA)and distance metric learning (DML)were presented.The method models text data with LDA,which generate the topic distribution of different text through detecting the hidden relationship between different topics and words inside the text data,and parameters of the model are estimated with Gibbs sampling algorithm.The generated topic distribution is used as the features of the text data,and the DML method is used to learning the Mahalanobis distance metric for different classes so that the similarity between text data are well presented.Classifiers like KNN or SVM are used to classify text data based on the learning distances.Experimental results showed that this method can improve the text classification accuracy and is robust in setting different topic number.

text classification; distance metric learning; latent Dirichlet allocation; topic model

10.7612/j.issn.1000-2537.2016.05.012

2016-04-03

廣州教育科學(xué)規(guī)劃資助項目(2013A179，1201533765)；廣州市屬高?？蒲杏媱澷Y助項目(2012B154)；廣東省自然科學(xué)基金資助項目(2015A030313807)；廣東省高等學(xué)校優(yōu)秀青年教師培養(yǎng)計劃資助項目(YQ2015207)

*通訊作者,E-mail：zhanzr@gzpyp.edu.cn

TP391.41

A

1000-2537(2016)05-0070-07