一種基于LDA的潛在語義區(qū)劃分及Web文檔聚類算法

劉振鹿,王大玲,2,馮 時(shí),張一飛,2,方東昊

(1.東北大學(xué)信息科學(xué)與工程學(xué)院,遼寧沈陽110819;2.醫(yī)學(xué)影像計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室(東北大學(xué)),遼寧沈陽110819)

1 引言

向量空間模型[1](VSM)將文檔視為n個(gè)索引項(xiàng)(t1,t2,…,tn)構(gòu)成的向量,為每個(gè)索引項(xiàng)ti賦予權(quán)值wi(1≤i≤n),采用向量d=(w1,w2,…,wn)表示文檔d。傳統(tǒng)的表示方法將ti視為出現(xiàn)在文檔中的一些術(shù)語,采用術(shù)語的絕對(duì)詞頻或相對(duì)詞頻(如TFIDF)為wi賦值,這樣的權(quán)值忽略了術(shù)語之間的相互關(guān)系,而且以這樣的模型表達(dá)的文檔通常具有很高的維數(shù),從而使文檔聚類過程因“維災(zāi)”而導(dǎo)致相似性度量失去意義[2]?；诖?在文本聚類研究中,一些學(xué)者探索將索引項(xiàng)ti由可見的術(shù)語轉(zhuǎn)換成潛在的語義,因而將wi由術(shù)語的權(quán)值轉(zhuǎn)換為語義的權(quán)值,彌補(bǔ)了以詞為特征的缺陷,而且很大程度上降低聚類的維數(shù),節(jié)省聚類的時(shí)間。目前研究工作中表達(dá)文檔潛在語義的方法主要包括 LSA[3]、PLSA[4]和 LDA[5-7]。文獻(xiàn)[6]、[7]等研究在比較、分析LSA、PLSA、LDA的基礎(chǔ)上證明了LDA在采用潛在語義表達(dá)文檔方面具有更大的優(yōu)勢。

基于上述研究,本文根據(jù)LDA模型的特點(diǎn),深入分析文檔的潛在語義空間,獲得能夠表現(xiàn)文本特征的最佳語義區(qū)間,將其應(yīng)用于Web游離文檔的檢測和Web文檔聚類,采用文檔類別與語義互作用機(jī)制對(duì)聚類結(jié)果進(jìn)行修正,以獲得更好的聚類結(jié)果。

本文其余部分組織結(jié)構(gòu)如下：第2節(jié)基于LDA模型進(jìn)行文檔語義分布的分析,第3節(jié)基于語義分布的分析結(jié)果進(jìn)行游離文檔的檢測,第4節(jié)基于語義分析結(jié)果進(jìn)行Web文檔聚類以及基于文檔類別與語義互作用機(jī)制的聚類結(jié)果修正,第5節(jié)通過實(shí)驗(yàn)證明本文算法的優(yōu)勢,最后第6節(jié)是結(jié)論及進(jìn)一步的工作。

2 基于LDA的文檔語義空間分析

2.1 LDA模型

LDA模型是由Blei等提出的三級(jí)層次結(jié)構(gòu)的貝葉斯模型[5]。在應(yīng)用于文檔分析時(shí),表現(xiàn)為文檔d、潛在語義z、術(shù)語t之間的關(guān)系。文檔集合D 由M個(gè)文檔單元構(gòu)成,D={d1,d2,…,dM},di(i=1,2,…,M)由N個(gè)術(shù)語序列構(gòu)成,即di={t1,t2,…,tN},在潛在語義zn條件下生成術(shù)語tn(n=1,2,…,N)的概率為 P(tn|zn,β)?；诖?概率模型表示為：

對(duì)文檔建模,實(shí)際上就是估計(jì)α和β兩個(gè)參數(shù)。文獻(xiàn)[5]采用variational inference方法簡化了模型,選擇一個(gè)變分分布Q函數(shù)逼近P,即P(H|D)≈Q(H),Q選擇為：

其中γ和φ為Q的參數(shù)。文獻(xiàn)[5]假設(shè)θ和z相互獨(dú)立 ,并丟掉 t,求最優(yōu)解滿足 Q(θ,z|γ,φ)和P(θ,z|t,α,β)之間的 KL 散度最小 ,計(jì)算出 γ和 φ迭代公式：

據(jù)此進(jìn)行EM迭代,E步計(jì)算每篇文檔的參數(shù)γ和φ,M步最大化Variational Inference中的下界,求出此時(shí)的α和β,直到α和β收斂。

2.2 語義空間分析

為表示語義空間分析過程,這里采用中國科學(xué)院計(jì)算所譚松波等收集并建立的中文文本分類語料庫 TanCorpV1.0[8]中的3類(電腦網(wǎng)絡(luò),汽車快訊,醫(yī)藥)858個(gè)文檔,初始語義數(shù)量IS設(shè)置為100,采用 LDA迭代結(jié)果α向量中αk(1≤k≤100),按值的升序排列后的結(jié)果如圖1所示(橫坐標(biāo)SN表示語義編號(hào))。

圖1 語義空間α分布圖實(shí)例

直觀地看,如果將α分布曲線擬合成直線,根據(jù)直線的斜率,α曲線可近似分為A、B、C共3個(gè)區(qū)域。A區(qū)域中,α較小,表明在文檔集中包含此區(qū)域中SN對(duì)應(yīng)語義的文檔較少;C區(qū)域中,α較大,則文檔集包含此區(qū)域中SN對(duì)應(yīng)語義的文檔較多;B區(qū)域本身對(duì)應(yīng)的語義最多,而文檔集中包含該區(qū)域中SN對(duì)應(yīng)語義的文檔較A區(qū)域大較C區(qū)域小。基于此,將A、B、C區(qū)分別定義為低頻語義區(qū)、中頻語義區(qū)和高頻語義區(qū)。

對(duì)于低頻語義區(qū),包含對(duì)應(yīng)語義的文檔較少,因此,低頻語義區(qū)的語義對(duì)于表達(dá)文檔特征的貢獻(xiàn)較少。從文檔聚類的意義上,中、高頻語義區(qū)的語義對(duì)于表達(dá)不同類別文檔特征的貢獻(xiàn)更大。

為求得3個(gè)區(qū)域的分割點(diǎn),本文首先給出兩個(gè)定義。

定義1(凸點(diǎn))：繪制 α曲線的輔助曲線α=f(SN),該曲線在兩點(diǎn)(α1,SN1)與(α2,SN2)之間表現(xiàn)為一凸弧,則對(duì)于連接(α1,SN1)與(α2,S N2)的直線 α=aS N+b,?(α1*,SN1*)使(α1*,SN1*)∈α曲線且(α1*,SN1*)與α=aS N+b距離最大,則稱(α1*,SN1*)為凸點(diǎn)(Convex vertex),如圖 2(a)。

圖2 凸點(diǎn)與凹點(diǎn)

定義2(凹點(diǎn))：繪制 α曲線的輔助曲線α=f(SN),該曲線在兩點(diǎn)(α3,SN3)與(α4,SN4)之間表現(xiàn)為一凹弧,則對(duì)于連接(α3,SN3)與(α4,SN4)的直線 α=aSN+b,?(α2*,SN2*)使(α2*,SN2*)∈ α曲線且(α2*,SN2*)與 α=aSN+b距離最大,則稱(α2*,SN2*)為凹點(diǎn)(Concave vertex),如圖 2(b)。

根據(jù)定義可見,這里的輔助曲線α=f(SN)僅僅是為了獲得(α1,SN1)與(α2,SN2)以及(α3,SN3)與(α4,SN4),即凸弧和凹弧的兩個(gè)端點(diǎn),當(dāng)各自端點(diǎn)確定后,凸點(diǎn)和凹點(diǎn)求解過程與α=f(SN)無關(guān),而且凸點(diǎn)和凹點(diǎn)一般也不一定等于凸弧和凹弧的駐點(diǎn)。

分析α分布圖,低頻語義和中頻語義區(qū)的分界近似為凸點(diǎn),而中頻語義和高頻語義的分界則近似為凹點(diǎn),因此若將α分布圖擬合成曲線,在凸點(diǎn)和凹點(diǎn)之間必存在一個(gè)“拐點(diǎn)”,使α分布圖的起點(diǎn)與該拐點(diǎn)構(gòu)成定義1中的(α1,SN1)與(α2,SN2),而該拐點(diǎn)與α分布圖的終點(diǎn)構(gòu)成定義2中的(α3,SN3)與(α4,SN4)。

為獲得α=f(S N),將α分布圖擬合成曲線α=f(SN)=a3SN3+a2SN2+a1SN+a0,求拐點(diǎn) ,然后分別在α分布圖起點(diǎn)—拐點(diǎn)、拐點(diǎn)—終點(diǎn)中求出凸點(diǎn)和凹點(diǎn)。對(duì)圖1中α分布圖所求的拐點(diǎn)、凸點(diǎn)和凹點(diǎn)如圖3所示?；诖?求α分布圖中低頻、中頻、高頻語義區(qū)的算法 Algorithm α-Analysis包括：1)求擬合曲線及拐點(diǎn);2)求凸點(diǎn)和凹點(diǎn);3)劃分A 、B、C 區(qū) 。

劃分低、中、高頻語義區(qū)對(duì)于文檔集特征提取和聚類具有重要作用。此外,語義數(shù)量IS的設(shè)置對(duì)于α分布曲線分布及其中低、中、高頻語義區(qū)的變化也是有影響的,即IS不同時(shí),α分布圖亦不同。圖4為 IS 分別為 10、20、40、60、80、100 時(shí),α分布曲線分布。

3 基于LDA語義區(qū)間分析的游離點(diǎn)檢測

圖3 圖1中α分布的凸點(diǎn)與凹點(diǎn)

圖4 不同IS值的α分布

由2.2節(jié)分析可知,分布在低頻語義區(qū)的語義被較少的文檔包含。對(duì)于文檔集D,假設(shè)其中的文檔分屬 C1、C2、…、Cn個(gè)類,若選擇足夠的 IS,則其 α分布圖能夠劃分出低頻、中頻、高頻語義區(qū)。直覺上,如果一個(gè)文檔d不屬于C1～Cn的任何一類,則其包含的語義應(yīng)該處于低頻語義區(qū)。因此,本文應(yīng)用這一啟發(fā)式規(guī)則進(jìn)行游離文檔的檢測。

為此,這里給出游離文檔的定義和性質(zhì)。

定義3(游離文檔與非游離文檔)：設(shè)文檔集D中的文檔分屬于C1、C2、…、Cn個(gè)類,若文檔 d不屬于C1～Cn的任何一類,則將d定義為游離文檔,否則將其定義為非游離文檔。

基于前面的分析,游離文檔與非游離文檔具有如下性質(zhì)：

性質(zhì)1：基于 LDA模型表示并采用EM算法迭代后,非游離文檔的潛在語義在α分布圖中能夠分布在低、中、高頻語義區(qū)或中、高頻語義區(qū);

性質(zhì)2：基于 LDA模型表示并采用EM算法迭代后,游離文檔的潛在語義在α分布圖中僅分布在低頻語義區(qū)。

為說明上述性質(zhì),本文在上面的電腦網(wǎng)絡(luò)、汽車快訊、醫(yī)藥三方面858個(gè)文檔的文檔集D中加入一個(gè)體育類的文檔d,根據(jù)定義3,d為游離文檔。

前述公式(3)給出了α與γ的關(guān)系,本文通過對(duì)γ矩陣的展示來分析游離文檔。過程如下：

(1)對(duì)γ矩陣預(yù)處理：γ矩陣行為文檔代號(hào)(docID),列為語義代號(hào)(SN),每個(gè)語義均對(duì)應(yīng)有α向量中的一個(gè)αk,通過對(duì)α向量的升序排列來對(duì)γ矩陣相應(yīng)的列進(jìn)行交換;

(2)應(yīng)用 2.2節(jié) Algorithm α-Analysis算法檢測低、中、高頻語義區(qū),然后逐行掃描文檔,判斷其分布在各語義區(qū)的值選出游離文檔。

以IS=60為例,游離文檔(docID=19)與一些非游離文檔(docID=6、18、20)的對(duì)比如圖5所示。19號(hào)文檔包含的語義只出現(xiàn)在低頻語義區(qū),不包含中、高頻語義區(qū)的語義,而其他非游離文檔,包含了中、高頻語義區(qū)的語義。

為了進(jìn)一步驗(yàn)證游離點(diǎn)檢測算法的有效性,本文在原有文檔集電腦網(wǎng)絡(luò)、汽車快訊、醫(yī)藥三方面858個(gè)文檔的基礎(chǔ)之上加入了3個(gè)不同類別的游離文檔：300號(hào)文檔為體育類,301號(hào)文檔為城建類,302號(hào)文檔為電影類,303號(hào)為非游離文檔(汽車快訊)。這些文檔的對(duì)比如圖6所示。從圖中可見303號(hào)非游離文檔和300,301,302號(hào)游離文檔明顯的差別,從而也證明了本文的游離點(diǎn)檢測算法對(duì)于多游離點(diǎn)文檔集同樣適用。

圖56號(hào)、18～20號(hào)文檔在γ矩陣中一行的值

圖6300～303號(hào)文檔在γ矩陣中一行的值

因此,通過對(duì)語義區(qū)的劃分以及對(duì)文檔在不同語義區(qū)分布的分析,可以檢測游離文檔。而游離文檔的檢測,對(duì)于文檔聚類具有預(yù)處理的作用,特別是對(duì)于如K-Means這類基于劃分的聚類方法(即要求預(yù)先給定聚類數(shù)目),可以提高聚類的準(zhǔn)確性。

4 基于文檔類別與語義的互作用機(jī)制的聚類

基于LDA模型表達(dá)文本,提取中、高頻語義區(qū)的語義作為文本特征,根據(jù)這些特征進(jìn)行初始文本聚類。然后通過統(tǒng)計(jì)每個(gè)語義在各類文檔中的比例獲得語義的類,通過統(tǒng)計(jì)每篇文檔在各類的比例修正文檔所屬的類,以此“文檔類別與語義互作用”機(jī)制修正聚類結(jié)果。

4.1 基于K-Means的文本初始聚類

根據(jù)公式(3)對(duì)γ矩陣進(jìn)行分析,部分中、高頻語義區(qū)γ矩陣的值如表1所示。

表1 中、高頻語義區(qū) γ矩陣局部圖

可見,γ矩陣中的值相差很多,由于不能滿足歐式距離“貢獻(xiàn)等同”的要求,直接聚類質(zhì)量較差。本文在聚類時(shí)采用如下方法進(jìn)行處理：(1)不作任何處理;(2)行歸一化處理(對(duì)同一行的元素進(jìn)行極大-極小歸一化處理);(3)0、1歸一化處理(即如果值大于等于1則賦值為1,否則賦值為0);(4)大于1者歸1處理(即如果值大于1則賦值為1,否則保留原值)。在此基礎(chǔ)上,以處理后的γ矩陣值為文檔特征,應(yīng)用K-Means算法進(jìn)行文檔聚類。

4.2 基于“類別與語義互作用”機(jī)制的聚類結(jié)果修正

若4.1節(jié)中對(duì)γ矩陣的預(yù)處理采用方法(3)或者(4),則γ矩陣每一行中1的數(shù)目即一篇文檔所包含的語義數(shù)目,每一列中1的數(shù)目即包含該列對(duì)應(yīng)語義的文檔數(shù)目?；诖?本文通過對(duì)錯(cuò)誤聚類的文本進(jìn)一步糾正,從而得到更好的聚類結(jié)果。具體地,在初始聚類的基礎(chǔ)上,采用“類別與語義互作用”機(jī)制做進(jìn)一步的調(diào)整：一方面,通過對(duì)γ矩陣各列中1數(shù)目的統(tǒng)計(jì),獲得各語義在各類文檔中所占比例,就某一列而言,所占比例最大的文檔類別即為該語義的類別;另一方面,通過對(duì)γ矩陣各行中1數(shù)目的統(tǒng)計(jì),獲得各“類”語義在該文檔中所占的比例,最大者為該文檔的類別。重復(fù)這一過程,直到穩(wěn)定。其算法MutualAction of Semantic-Cluster如下：

算法中,2～5行是根據(jù)初始聚類結(jié)果對(duì)語義“分類”,此過程結(jié)束后,各語義便有了對(duì)應(yīng)的“類”;6～9行是根據(jù)語義分類結(jié)果對(duì)文檔聚類結(jié)果進(jìn)行修正,由于這種修正可能會(huì)影響語義“分類”結(jié)果,所以上述2～9行一般還需重復(fù)執(zhí)行,直到穩(wěn)定。圖7給出了一個(gè)γ矩陣的初始聚類和調(diào)整過程及結(jié)果。

圖7 文檔類別與語義互作用實(shí)例

5 實(shí)驗(yàn)

本文分別在2個(gè)數(shù)據(jù)集上實(shí)驗(yàn),數(shù)據(jù)集同樣采用中國科學(xué)院計(jì)算所譚松波等的中文文本分類語料庫-TanCorpV1.0,數(shù)據(jù)集1選擇電腦網(wǎng)絡(luò)、汽車快訊、醫(yī)藥3個(gè)類別共858個(gè)文檔;數(shù)據(jù)集2選擇電腦病毒、電腦軟件、電腦網(wǎng)絡(luò)3個(gè)類別共1200個(gè)文檔。前者3類文檔語義差別較大,后者3類文檔語義相似,均為電腦類別。采用Matlab軟件工具[9]實(shí)現(xiàn)相關(guān)算法。

實(shí)驗(yàn)采用宏平均MacroP作為聚類質(zhì)量的度量準(zhǔn)則,計(jì)算方法如下。

5.1 對(duì)γ矩陣不同預(yù)處理方法的聚類實(shí)驗(yàn)

如前所述,在聚類之前,對(duì)γ矩陣的值采用了不同的預(yù)處理方法,這里將不作任何處理、行歸一化方法、0-1歸一化方法、大于1者歸1方法進(jìn)行對(duì)比,同時(shí),將傳統(tǒng)向量空間模型采用的“以術(shù)語為特征”(word as feature)的方法也進(jìn)行對(duì)比。這里采用KMeans算法、每類隨機(jī)選擇初始中心點(diǎn)進(jìn)行聚類,圖8是進(jìn)行100次上述實(shí)驗(yàn)的聚類結(jié)果的MacroP平均值。(圖8中將上述4種方法分別表示為no smooth、unitary 、0-1 smooth、smooth to one)。

圖8 不同預(yù)處理方法聚類的MacroP對(duì)比實(shí)驗(yàn)結(jié)果

結(jié)果表明,大于1者歸1方法具有更好的聚類結(jié)果。由于聚類過程中文本的相似性度量采用歐式距離,而歐氏距離要求對(duì)象的各個(gè)分量貢獻(xiàn)同等。如果某個(gè)語義對(duì)應(yīng)的值過大,足以掩蓋其他語義時(shí),直接應(yīng)用歐氏距離將導(dǎo)致對(duì)象間區(qū)分度較差。為體現(xiàn)各語義在文檔中的作用,需進(jìn)行平滑處理,而大于1者歸1方法將對(duì)語義包含者進(jìn)行平滑處理,在應(yīng)用歐氏距離時(shí)表現(xiàn)出了更好的質(zhì)量。基于同樣原因,0、1歸一化效果也比較好。

另一方面,從圖8也可看出IS的選擇對(duì)聚類結(jié)果的影響,前者IS在30附近、后者IS在50附近時(shí)聚類結(jié)果是最好的。

5.2 基于“類別與語義互作用”機(jī)制的聚類結(jié)果修正實(shí)驗(yàn)

在初始聚類基礎(chǔ)上,應(yīng)用MutualAction of Semantic-Cluster算法修正聚類結(jié)果,其結(jié)果與圖8中smooth to one的初始聚類的結(jié)果對(duì)比如圖9所示。

圖9(a)中,當(dāng)IS為50到110時(shí),MacroP經(jīng)糾正后有大幅提升(最高11%),圖9(b)則無明顯變化,說明基于“類別與語義互作用”機(jī)制對(duì)于類別差異不大的文檔集的聚類修正效果不明顯。

圖9 修正前后的聚類結(jié)果對(duì)比

6 結(jié)語

本文在應(yīng)用LDA模型表示文檔的基礎(chǔ)上,對(duì)潛在語義的分布進(jìn)行了深入分析,通過對(duì)不同頻度語義區(qū)的劃分以及對(duì)文檔在不同語義區(qū)分布的分析,得到表現(xiàn)文檔的主要語義特征,并據(jù)此檢測游離文檔和進(jìn)行文檔聚類。

本文目前的工作尚顯粗糙,一些問題尚需深入研究,因此今后進(jìn)一步的工作包括：(1)低頻、中頻、高頻語義區(qū)的精確劃分算法;(2)各區(qū)語義內(nèi)容、特別是高頻語義區(qū)作用的深入剖析;(3)基于LDA的文檔表示、聚類及其他相關(guān)算法的進(jìn)一步優(yōu)化。

[1]Salton G,Wong A,Yang C.A vector space model for automatic indexing[J]//Communications of the ACM,1975,18(11)：613-620.

[2]Hinneburg A,Aggarwal C,Keim D.What Is the Nearest Neighbor in High Dimensional Spaces[C]//Proceedingofthe 26th VLDB Conference,2000：506-515.

[3]Dumais S,Furnas G.,Landauer T,Scott D,et al.U-sing Latent Semantic Analysis to Improve Access to Textual Information[C]//Proceedings of Computer Human Interaction,1988：281-285.

[4]Hofmann T.Probabilistic Latent Semantic Indexing[C]//Proceedings of the 22th Annual International SIGIR Conference on Research and Development in Information Retrieval,1999：50-57.

[5]Blei D,Ng A,Jordan M.Latent Dirichlet allocation[J].Journal of Machine Learning Research,2003,3(5)：993-1022.

[6]Phan X,Nguyen L,Horiguchi S.Learning to classify short and sparse text&web with hidden topics from large-scale data collections[C]//Proceedings of 2008 WWW Conference,2008：91-100.

[7]Titov I,McDonald.Modeling online reviews with multi-grain topic models[C]//Proceedings of 2008 WWW Conference,2008：111-120.

[8]譚松波,王月粉.中文文本分類語料庫.TanCorpV1.0。www.Searchforum.org.cn/tansongbo/corpus.htm

[9]薛定宇,陳陽泉.高等應(yīng)用數(shù)學(xué)問題的MATLAB求解[M].第一版,北京清華大學(xué)學(xué)研大廈A座：清華大學(xué)出版社,2004.10.