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

(1.東北大學信息科學與工程學院,遼寧沈陽110819;2.醫(yī)學影像計算教育部重點實驗室(東北大學),遼寧沈陽110819)

1 引言

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

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

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

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

2.1 LDA模型

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

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

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

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

2.2 語義空間分析

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

圖1 語義空間α分布圖實例

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

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

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

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

圖2 凸點與凹點

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

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

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

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

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

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

圖3 圖1中α分布的凸點與凹點

圖4 不同IS值的α分布

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

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

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

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

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

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

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

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

(1)對γ矩陣預處理：γ矩陣行為文檔代號(docID),列為語義代號(SN),每個語義均對應有α向量中的一個αk,通過對α向量的升序排列來對γ矩陣相應的列進行交換;

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

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

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

圖56號、18～20號文檔在γ矩陣中一行的值

圖6300～303號文檔在γ矩陣中一行的值

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

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

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

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

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

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

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

4.2 基于“類別與語義互作用”機制的聚類結果修正

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

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

圖7 文檔類別與語義互作用實例

5 實驗

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

實驗采用宏平均MacroP作為聚類質量的度量準則,計算方法如下。

5.1 對γ矩陣不同預處理方法的聚類實驗

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

圖8 不同預處理方法聚類的MacroP對比實驗結果

結果表明,大于1者歸1方法具有更好的聚類結果。由于聚類過程中文本的相似性度量采用歐式距離,而歐氏距離要求對象的各個分量貢獻同等。如果某個語義對應的值過大,足以掩蓋其他語義時,直接應用歐氏距離將導致對象間區(qū)分度較差。為體現(xiàn)各語義在文檔中的作用,需進行平滑處理,而大于1者歸1方法將對語義包含者進行平滑處理,在應用歐氏距離時表現(xiàn)出了更好的質量?；谕瑯釉?0、1歸一化效果也比較好。

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

5.2 基于“類別與語義互作用”機制的聚類結果修正實驗

在初始聚類基礎上,應用MutualAction of Semantic-Cluster算法修正聚類結果,其結果與圖8中smooth to one的初始聚類的結果對比如圖9所示。

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

圖9 修正前后的聚類結果對比

6 結語

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

本文目前的工作尚顯粗糙,一些問題尚需深入研究,因此今后進一步的工作包括：(1)低頻、中頻、高頻語義區(qū)的精確劃分算法;(2)各區(qū)語義內容、特別是高頻語義區(qū)作用的深入剖析;(3)基于LDA的文檔表示、聚類及其他相關算法的進一步優(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]薛定宇,陳陽泉.高等應用數學問題的MATLAB求解[M].第一版,北京清華大學學研大廈A座：清華大學出版社,2004.10.