理論與實踐： 一種基于狄利克雷過程混合模型的文本聚類算法
相關(guān)鏈接： 中國安全網(wǎng) 中國質(zhì)量網(wǎng) 中國論文網(wǎng) 中國資訊網(wǎng)
作者：張毅
隨著互聯(lián)網(wǎng)的普及，論壇、微博、微信等新媒體已經(jīng)成為人們獲取和發(fā)布信息的重要渠道，而網(wǎng)絡(luò)中的這些文本數(shù)據(jù)，由于文本數(shù)目和內(nèi)容的不確定性，給網(wǎng)絡(luò)輿情聚類分析工作帶來了很大的挑戰(zhàn)。非參數(shù)貝葉斯模型為我們提供了一種很好的解決方法，它是一種定義在無限維參數(shù)空間上的貝葉斯模型，由于參數(shù)的維數(shù)可以根據(jù)數(shù)據(jù)集的大小自適應調(diào)整，因此不需要事先確定聚類數(shù)目。本文中介紹的狄利克雷過程( Dirichlet process，DP)就是一種非常流行的非參數(shù)貝葉斯模型，近年來廣泛應用在貝葉斯模型驗證、密度估計和基于混合模型的聚類等領(lǐng)域。
由于狄利克雷過程混合模型( Dirichlet process mixturemodel，DPMM)的提出，使得狄利克雷過程的應用得到了長足的發(fā)展。Andreas等人將DPMM用于自然語言處理中的基于語義的動詞聚類上面，利用成對約束這一特性，指導DPMM將動詞聚到指定的類別中。Fox等人利用DPMM的聚類性質(zhì)，結(jié)合數(shù)據(jù)中的關(guān)聯(lián)特性，在目標跟蹤上面實現(xiàn)了目標數(shù)量的確定。Zhang等人將DPMM過程混合模型應用在多元有監(jiān)督學習的回歸問題上，通過MCMC采樣，得到了良好的統(tǒng)計學和計算效果。
基于以上工作，本文提出了基于DPMM的文本聚類模型，該模型使用狄利克雷過程中的中國餐館過程( Chineserestaurant process，CRP)構(gòu)造方式，結(jié)合多項式分布與狄利克雷分布共軛的特性，實現(xiàn)了基于中國餐館過程的狄利克雷過程混合模型，然后利用吉布斯采樣算法對模型近似求解。實驗發(fā)現(xiàn)，該模型能夠有效解決自動確定聚類數(shù)目這一問題，而且在聚類過程中可以利用類簇中聚類一詞語的多項式分布來計算每個詞語在相應類簇下出現(xiàn)的概率，然后利用每個類簇下面概率排名比較高的詞語去表示這個類簇。在本文提出的文本聚類模型中，每個類簇可以當做一個主題，可以在聚類的同時去發(fā)現(xiàn)數(shù)據(jù)集中的主題數(shù)目和主題內(nèi)容。
1狄利克雷過程及其構(gòu)造方式
1.1狄利克雷過程的定義
狄利克雷過程是一種基于非參數(shù)貝葉斯模型的隨機過程，它是由Ferguson于1973年提出。狄利克雷過程的定義如下。
假設(shè)Go是測度空間上的隨機概率分布，參數(shù)ao是一個正實數(shù)。對于測度空間@的任意有限劃分A1…，Ar，如果存在如下的關(guān)系：
那么G服從由基分布Go和集中參數(shù)ao組成的狄利克雷過程，即G:DP(ao，Go)。對于測度空間O中的任意子集Ak，我們可以得到：
因為狄利克雷分布和多項式分布具有共軛的特性，所以如果G:DP(ao，Go)并且觀測值θ1…，θn：G服從多項式分布，則狄利克雷過程對測度空間@有限劃分后的后驗分布也服從狄利克雷過程，即：
由于G是測度空間0上的概率分布，觀測值θi同樣是在測度空間@中取值，所以這里的nk=≠#{i:θi∈Ak}，表示觀測值θi屬于Ak的數(shù)目。由公式(3)可以看出，任意狄利克雷過程的先驗分布的后驗分布依然服從狄利克雷過程，即
其中δ（θ=θi)是狄拉克函數(shù)，當且僅當θ=θi時函數(shù)值等于1，其他情況都等于O。
1.2 CRP的構(gòu)造
按照上面對狄利克雷過程的定義，無法實現(xiàn)對狄利克雷過程的采樣，在實際應用中往往采用其他構(gòu)造方式，包括截棍構(gòu)造方式( Stick-breaking construction)、Polya罐子模型( Polya urn scheme)構(gòu)造方式以及中國餐館過程(CRP)構(gòu)造方式，本文將采用CRP來對狄利克雷過程進行構(gòu)造：CRP利用了一個隱喻：假設(shè)有一個餐館，可以容納無數(shù)張桌子，每張桌子（相當于聚類組）分配參數(shù)p1…，pk:Go，pk表示第k張桌子的參數(shù)，我們分配桌子給每一個顧客（相當于數(shù)據(jù)點）Zl，…,zn：crp (ao)，指示變量Zi表示分配給第i位顧客的桌子。每位新到的顧客可以坐在已有頤客的桌子或者新開一張桌子。具體算法的流程如下：
1)初始化一個空的餐館；
2)第一個人進入餐館，選擇一張桌子坐下，然后點菜，其他坐在這張桌子上的人共享該道菜；
3)第二個人進入餐館，以概率可
選擇一張新的桌子，然后點菜，或者以概率
選擇和第一個人共享同一張桌子（相當于進入相同的組）；
4)第n+l個人進入餐館，以p(zn+1=k|Z1:n)=
的概率坐到第k張桌子，或者以a|…0的概率新開一張桌子，nk表示第k張桌子的顧客數(shù)目。
圖1給出了CRP的構(gòu)造過程。
由上面的描述可知，越多的顧客坐某一張桌子，那么下一個顧客選擇這張桌子的概率越大，說明CRP具有很好的聚類性質(zhì)。其次，參數(shù)ao的值越大，那么顧客選擇新桌子的概率也就越大，這說明ao能夠控制聚類數(shù)目的大小。
2狄利克雷過程混合模型( DPMM)與基于狄利克雷過程混合模型的文本聚類算法( DCA-DPMM)
2.1狄利克雷過程混合模型
從上面的描述中可以看出，狄利克雷過程具有良好的聚類性質(zhì)。但是狄利克雷過程只能實現(xiàn)具有相同值的數(shù)據(jù)聚類，無法進行數(shù)據(jù)之間相似性很大但值不同的聚類。針對這個問題，研究者在狄利克雷過程的基礎(chǔ)上，提出了狄利克雷過程混合模型。不同于有限混合模型，狄利克雷過程混合模型可以看作是具有無限分布分量的無限混合模型，是具有狄利克雷過程先驗假設(shè)的有限混合模型的極限形式。這使得在對數(shù)據(jù)進行建模時，聚類的數(shù)
目可以動態(tài)調(diào)整。狄利克雷過程混合模型的定義可以表述為以下形式：
觀測值θi服從參數(shù)為F(θi）的分布，參數(shù)θi服從概率測度G，而G則可以通過狄利克雷過程構(gòu)造。θi既可以是單個參數(shù)，也可以是多個參數(shù)構(gòu)成的向量，如果兩個觀測值xi和xi服從混合分布中的同一個分布，那么它們的分布變量相同，即θi=θio狄利克雷過程混合模型可以用如圖2所示的圖模型表示。
2.2 DCA-DPMM聚類算法
本文采用CRP構(gòu)造的狄利克雷過程混合模型進行文本聚類，該模型需要分別對文本集中的聚類以及每個聚類中的詞語進行建模�；贑RP的狄利克雷過程混合模型定義如下：
每個聚類（主題）z被表示成一個在詞典上的多項式分布0：。每個文檔xi對應聚類（主題）都有一個特定的多項式分布。一個文檔的生成過程如下：
1)采樣p：Dir(ao)；
2)對于文檔xi，本文采取以下方法：
(1)采樣一個類別標簽ZI：Mult(PI,)；
(2)生成文檔XI中的每一個詞Xi:0z。
文檔的生成過程采用概率圖模型表示，如圖3所示。
該模型使用多項式分布作為生成分布，使用狄利克雷分布作為它的先驗分布。e表示活躍的聚類數(shù)目，n表示文本數(shù)目。
在DCA-DPMM聚類算法中，每個文本分配給一個聚類，即每個文本屬于一個話題．同一類簇中的聽有文本都屬于同一個話題，那么第二個話題中第i個詞語出現(xiàn)的概率θzj為：
關(guān)于狄利克雷過程混合模型中隱變量的推斷問題，本文使用了坍塌的吉布斯采樣算法，它是蒙特卡羅采樣算法的一種變形，具有簡單高效的特點。由于觀測數(shù)據(jù)之間能夠相互交換，可以把觀測數(shù)據(jù)xi當作最后一個觀測值。指示變量zi的后驗分布為：
其中Z-I表示第i個觀測數(shù)據(jù)xI外其他所有觀測數(shù)據(jù)的指示變量。上面的推導過程利用了貝葉斯規(guī)則，公式(12)右邊的第一項是先驗，可以用狄利克雷過程中的CRP來表示：
公式( 12)右側(cè)的第二項是似然函數(shù)，如果指示因子zIi值k在已有的類別當中，那么：
如果指示變量是新的聚類，那么：
結(jié)合上面吉布斯采樣的公式，可以得出基于DPMM文本聚類算法( DCA-DPMM)的流程如下：
3實驗結(jié)果與分析
為了對本文提出的聚類算法的有效性進行評估，本文使用復旦大學標準語料庫進行聚類分析。常用的聚類有效性評估方法主要有外部評價法和內(nèi)部評價法，外部評估方法主要是比較聚類算法對數(shù)據(jù)集的分類結(jié)果和已知分類的相似程度，本文使用聚類純度( Purity)以及F-score作為外部評估聚類算法的指標，內(nèi)部評估方法主要通過判斷類間的疏離程度和類內(nèi)的緊密程度來評估一個聚類算法的有效性，文本使用輪廓系數(shù)( silhouette coefficient)怍為內(nèi)部評估聚類算法的有效性的指標。
3.1評估指標
1)聚類純度
為了計算純度，本文算出每個類別i中被正確分配的文本數(shù)，然后將各個類別的文本數(shù)累加，再除以文本總數(shù)，即可得到聚類純度，計算公式如下：
其中Ni表示文本數(shù)目，K表示聚類數(shù)目，Ci表示類別k中最具代表性的類別的文本數(shù)目。
2) F-measure指標
F-measure綜合了文本檢索中的查準率(precision)和查全率( r-ecall)這兩種評價指標，對于一個聚類i和一個事實類別j的查準率和查全率的定義如下：
其中N1表示在聚類i中屬于事實類別i的數(shù)目，N2為聚類i中所有文本的數(shù)目，N3為事實類別j中所有文本的數(shù)目。文本采用的F-measure是查準率和查全率的調(diào)和平均值，也被稱為F1值，F(xiàn)1值的定義如下：
- 輪廓系數(shù)
假設(shè)把具有n個文本的數(shù)據(jù)集X劃分成k個聚類C1，C2…,，Ck，對于類簇中的每一個文本x∈X，a(x)表示數(shù)據(jù)點x和x所在類簇其他數(shù)據(jù)點之間的平均距離，b(x)表示數(shù)據(jù)點x和所有x不屬于的類簇之間的最小平均距離。假設(shè)x∈Ci（1≤i≤k），那么a(x)和b(x)分別表示為：
數(shù)據(jù)點z的輪廓系數(shù)的定義如下：
x的輪廓系數(shù)取值區(qū)間是[-1,1]，越靠近+1，說明類間距越大，類內(nèi)緊密程度越好，聚類的質(zhì)量越好。本文計算所有數(shù)據(jù)點的平均輪廓系數(shù)。
3.2實驗結(jié)果與分析
本文采用的實驗數(shù)據(jù)集是復旦大學中文語料庫，本文將其分為三個子數(shù)據(jù)集，每個子數(shù)據(jù)集有10個類別，表1展示了實驗數(shù)據(jù)集。如表1所示，預處理時只保留文檔中的動詞和名詞，在使用K-means聚類算法時，手動設(shè)定K-means的聚類數(shù)目為10，用TF-IDF對文本向量化，在使用DCA-DPMM聚類算法時，分別設(shè)置ao=l.0，β=1.0和K=50。表2展示了DCA-DPMM聚類算法和K-means聚類算法在對數(shù)據(jù)集進行聚類后的純度對比，從表2中可以看出，無論在哪個測試數(shù)據(jù)集上，本文提出的算法在純度上都要略好于經(jīng)典的K-means算法，兩種聚類算法在數(shù)據(jù)集1上的純度略差，原因是在數(shù)據(jù)集1上部分類簇的相似度很大，如文學、歷史、藝術(shù)這三個類簇，文本的特征向量相似度很高，在聚類時沒有將它們很好地劃分開。表3展示了DCA-DPMM聚類算法和K-means聚類算法在對數(shù)據(jù)集進行聚類后的F1值對比，F(xiàn)．值是查全率和查準率的加權(quán)調(diào)和平均，F(xiàn)1值越高說明聚類算法越有效，從表3中可以看出，本文提出的文本聚類算法F1值要好于K-means聚類算法。
在使用輪廓系數(shù)評估DCA-DPMM聚類算法的有效性時，本文首先用DCA-DPMM聚類算法對數(shù)據(jù)集聚類，得到聚類數(shù)目K后，設(shè)定K-means的聚類數(shù)目為K1為了驗證DCA-DPMM聚類算法的聚類數(shù)目的有效性，K-means的聚類數(shù)目在K值的__KF浮動，分別計算出輪廓系數(shù)。在數(shù)據(jù)集1上的實驗結(jié)果如圖4所示。
從圖4中可以看出，DCA-DPMM聚類算法在數(shù)據(jù)集1上確定的聚類數(shù)目為7，此時的輪廓系數(shù)為- 0.17；而當K-means聚類算法的聚類數(shù)目為7時，輪廓系數(shù)為- 0.19，在聚類數(shù)目相同時，本文提出的文本聚類算法在類內(nèi)的緊密程度和類間的疏離程度要略優(yōu)于K-means聚類算法。為了驗證本文提出的文本聚類算法的有效性，設(shè)定K-means聚類算法的聚類數(shù)目在7上下浮動，從圖4中可以看到，K-means算法的聚類質(zhì)量都略差于聚類數(shù)目為7的情況，
這說明本文提出的文本聚類算法能夠有效確定聚類數(shù)目，在數(shù)據(jù)集2上得到的輪廓系數(shù)與在數(shù)據(jù)集l的結(jié)果相似，如圖5所示。
在DCA-DPMM聚類算法中，同一個類簇下面的詞語能夠表示成主題一單詞多項式分布，通過公式( 12)可以計算出同一主題下詞語出現(xiàn)的概率，表4列舉了數(shù)據(jù)集1中部分話題的高頻（按出現(xiàn)概率排名）詞語。從表4中可以看出，通過若干個高頻詞語即可表示出話題內(nèi)容。
4結(jié)束語
本文基于狄利克雷過程混合模型實現(xiàn)了對文本的主題聚類，狄利克雷過程是一種非參數(shù)貝葉斯框架，它的構(gòu)造方式CRP具有良好的聚類性質(zhì)。利用這一性質(zhì)，本文構(gòu)造了基于中國餐館過程的狄利克雷過程混合模型，并利用吉布斯采樣算法來近似求解該模型。實驗結(jié)果表明該聚類算法不僅可以動態(tài)確定聚類數(shù)目，而且在聚類的有效性上優(yōu)于經(jīng)典的K-means聚類算法。
本文中控制聚類數(shù)目的先驗參數(shù)ao只是選擇了經(jīng)驗值，但是它的大小會影響到混合分量的數(shù)目，可以給先驗參數(shù)ao分配一個先驗伽馬分布，然后在吉布斯采樣過程后驗推斷ao。在DCA-DPMM聚類算法中，每個文檔只屬于一個主題，但在話題模型中，如Latent Dirichlet Allcation( LDA)中，每個文檔服從關(guān)于話題的多項式分布。下一步研究可以讓隨機過程G服從一個先驗狄利克雷過程分布，這樣便可以實現(xiàn)多文檔之間的主題共享。
5摘要：
隨著互聯(lián)網(wǎng)的普及，論壇、微博、微信等新媒體已經(jīng)成為人們獲取和發(fā)布信息的重要渠道，而網(wǎng)絡(luò)中的這些文本數(shù)據(jù)，由于文本數(shù)目和內(nèi)容的不確定性，給網(wǎng)絡(luò)輿情聚類分析工作帶來了很大的挑戰(zhàn)。在文本聚類分析中，選擇合適的聚類數(shù)目一直是一個難點。文章提出了一種基于狄利克雷過程混合模型的文本聚類算法，該算法基于非參數(shù)貝葉斯框架，可以將有限混合模型擴展成無限混合分量的混合模型，使用狄利克雷過程中的中國餐館過程構(gòu)造方式，實現(xiàn)了基于中國餐館過程的狄利克雷混合模型，然后采用吉布斯采樣算法近似求解模型，能夠在不斷的迭代過程中確定文本的聚類數(shù)目。實驗結(jié)果表明，文章提出的聚類算法，和經(jīng)典的K-means聚類算法相比，不僅能更好的動態(tài)確定文本主題聚類數(shù)目，而且該算法的聚類質(zhì)量（純度、F-score和輪廓系數(shù)）明顯好于K-means聚類算法。
上一篇:理論與實踐： CASoRT系統(tǒng)中基于聚集特性的在線流行度預測方法
下一篇:理論與實踐： 智能家居433 MHz射頻通信協(xié)議棧設(shè)計與網(wǎng)關(guān)實現(xiàn)
