一種基于Pitman-Yor過程模型的不平衡文本數(shù)據(jù)集聚類算法

鐘文良 黃瑞章

(貴州大學計算機科學與技術(shù)學院 貴陽 550025)

一種基于Pitman-Yor過程模型的不平衡文本數(shù)據(jù)集聚類算法

鐘文良 黃瑞章

(貴州大學計算機科學與技術(shù)學院 貴陽 550025)

在現(xiàn)實生活中,文本數(shù)據(jù)集的結(jié)構(gòu)常常體現(xiàn)不平衡性,不同類別的文本數(shù)量存在較大差異,既包含極大的多樣本類,也包含極小的多少樣本類。傳統(tǒng)的文本聚類方法,對于極大類存在分配偏見,使得極大類更容易吸引新的文本數(shù)據(jù)的加入。因此,如何找到這種不平衡文本數(shù)據(jù)集的文本結(jié)構(gòu),是文本聚類分析的一個需要被切實解決的難點問題。針對這一問題,論文創(chuàng)新地提出了一個基于Pitman-Yor過程模型的文本聚類算法,命名為參數(shù)自適應(yīng)PYP(Discount Adaptation Pitman-Yor process,DAPYP)模型。該模型在文本聚類的過程中,依據(jù)各樣本類別的文本數(shù)量,自動調(diào)整PYP(Pitman-Yor Process)的折扣參數(shù)。實現(xiàn)了從不平衡數(shù)據(jù)集中識別出極小類和極大類。通過在人工數(shù)據(jù)集和真實文本數(shù)據(jù)集上進行的實驗,表明該文提出的模型可以有效地解決真實文本數(shù)據(jù)集聚類分析中的數(shù)據(jù)不平衡問題。

文本聚類; 不平衡數(shù)據(jù)集; Pitman-Yor過程

Class Number TP312

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展,在線文本的數(shù)量日益增加,與此同時,在Web文本挖掘的領(lǐng)域中,如何自動從大規(guī)模的文本語料庫中挖掘出主題結(jié)構(gòu)變得愈發(fā)重要。在實際生活中,獲得的數(shù)據(jù)集的分布結(jié)構(gòu)通常是很復(fù)雜的。首先,真實文本數(shù)據(jù)集往往是非常復(fù)雜的,類別分布極度不平衡。即在一個真實的文本數(shù)據(jù)集中,往往會出現(xiàn)絕大多數(shù)的文本屬于一個類(多樣本類),而其他的類別(少樣本類)相對于多樣本類只具有少量的文本。這個問題在新聞數(shù)據(jù)集的主題結(jié)構(gòu)分析中尤為明顯,數(shù)據(jù)集中的各個主題分布是極度不平衡。在新聞數(shù)據(jù)集中,新聞熱點通常是新發(fā)生的少樣本類數(shù)據(jù),這些含有少量的數(shù)據(jù)類別有很大可能是即將爆發(fā)的新聞事態(tài)趨勢,有可能在一段時間內(nèi)引起人們的極大關(guān)注。因此,如何及時有效地檢測與識別出這些少樣本類是本文主要關(guān)注的問題。在實際應(yīng)用中,此問題的有效解決將能極大地促進輿情分析、趨勢走向、醫(yī)療診斷和欺詐檢測等問題的解決。截至目前,在處理不平衡數(shù)據(jù)集的問題研究中,較為主流的方法是分類算法,其主要的研究途徑是更改數(shù)據(jù)集的樣本分布或者算法層面的修改。

早期的分類算法是通過隨機過采樣技術(shù),使得非平衡數(shù)據(jù)集獲得數(shù)據(jù)分布均勻的狀態(tài)。該方法最主要的做法是對少樣本類進行隨機采樣,采樣的文本數(shù)為多樣本類與其他少樣本類之間的數(shù)量差值,這種方式很容易理解與實現(xiàn),但容易出現(xiàn)分類中的過擬合現(xiàn)象[1～3]。隨后也有其他很多研究者對過采樣技術(shù)不斷改進[4～6]。另一種方式是通過對多樣本類中數(shù)據(jù)集進行欠采樣,對多樣本類進行削減后,得到一個分布均勻的文本訓練數(shù)據(jù)集[7～9]。另一種途徑以獲取分布性質(zhì)更好的數(shù)據(jù)集為目的,但是在出現(xiàn)極度不平衡現(xiàn)象時分類精度依然很低。在改良原始數(shù)據(jù)集分布不平衡的方法之后,研究人員開始考慮從算法層面入手,例如,核學習方法、主動學習方法、代價敏感算法等方法成為解決數(shù)據(jù)集不平衡問題的新途徑并取得了顯著的效果[10]。

然而不管怎么樣,在分類算法之外,對于非平衡數(shù)據(jù)集進行的聚類研究相對較少,要準確地從中識別出分布結(jié)構(gòu)更加困難,主要的解決途徑還是集中在更改數(shù)據(jù)集的樣本分布上。傳統(tǒng)的文本聚類方法是根據(jù)經(jīng)驗設(shè)定類別的個數(shù),在數(shù)據(jù)分布平衡的數(shù)據(jù)集上可以有效地聚類分析[11～12],而少樣本類中的文本則被當成噪音數(shù)據(jù)進行處理。近些年,出現(xiàn)了很多基于傳統(tǒng)聚類的改進算法,都是考慮從數(shù)據(jù)層面上處理,比如對不平衡數(shù)據(jù)集進行欠采樣處理[13],或者是過采樣處理[14],但是這些方法仍然需要假定類別的個數(shù)。除此之外,基于非參貝葉斯模型[15]的文本聚類算法,比如狄利克雷過程混合模型(Mixtures of Dirichlet Processes,DPM)[16～17],作為一種可以從數(shù)據(jù)集中自動學習類別個數(shù)的自主學習方法得到了廣泛的應(yīng)用[18～19]。盡管這樣,當面臨不平衡數(shù)據(jù)集時,該方法的識別結(jié)果并不理想。原因在于基于狄利克雷過程(Dirichlet Process,DP)的模型中,DP自身存在“富人越富”的性質(zhì),即新的文本更傾向于分配到多樣本類中。在現(xiàn)實生活中,多樣本類別通常是過去或者已經(jīng)發(fā)生的事件熱點,而在更多的情況下,少樣本類卻預(yù)示著未來的發(fā)展動向和關(guān)注點。

本文提出了一種基于Pitman-Yor過程(Pitman-Yor Process,PYP)模型的新穎文本聚類算法,命名為折扣參數(shù)自適應(yīng)的DAPYP模型(discount adaptation Pitman-Yor process model,DAPYP),該模型可以從極度不平衡的數(shù)據(jù)集中自動學習類別個數(shù),同時把少樣本類高效地識別出來。PYP模型作為一種DP模型的廣義形式,已廣泛應(yīng)用于統(tǒng)計與概率領(lǐng)域中[20～22]。PYP模型最重要的是利用一個固定的折扣參數(shù)來控制新類別的產(chǎn)生,即不會因為已有生成的類別數(shù)量的增加而降低新類別產(chǎn)生的可能性。這種方法可以很好捕捉冪律分布的尾部區(qū)域。但是基本的PYP模型在面對極度不平衡數(shù)據(jù)集(比如只含有兩個類別的極度不平衡數(shù)據(jù)集)時,折扣參數(shù)也很難識別出少樣本類別中的文本。因此,“富人越富”的問題也同樣暴露出來。本文可以依據(jù)每個類別的分布情況和類別大小,自動調(diào)整折扣參數(shù)的值,在分配多樣本類別的文本時,動態(tài)懲罰對少樣本類產(chǎn)生影響的多樣本類。采取這種方式能夠很好地避免在不平衡數(shù)據(jù)下可能發(fā)生的“富人越富”問題。

在DAPYP的參數(shù)推斷中,本文利用廣義的Polya罐子模型(Polya urn model)機制與Gibbs采樣算法進行模型參數(shù)的求解。同時,本文在人工數(shù)據(jù)集和真實數(shù)據(jù)集都做了大量的實驗。實驗結(jié)果表明,本文提出的方法在解決不平衡文本數(shù)據(jù)集聚類分析上具有魯棒性和有效性。

2 PYP模型及其基本原理

2.1 PYP模型

Pitman-Yor過程[23]作為DP的擴展,可以直接從數(shù)據(jù)集中自動學習類別個數(shù),而無需事先設(shè)定數(shù)據(jù)的聚類的個數(shù)。此外,PYP模型含有一個固定值的折扣參數(shù),用于控制產(chǎn)生新類別的數(shù)量。但是PYP在產(chǎn)生的類別個數(shù)不多,且已產(chǎn)生的類別的文本又有數(shù)量多的優(yōu)勢時,“富人越富”的問題將會發(fā)生,導(dǎo)致新類產(chǎn)生的可能性逐漸降低。

本節(jié)將介紹PYP模型在文本聚類問題上的應(yīng)用。做如下定義來描述PYP模型,即含有n個文本的語料庫D;每個文本x均來自于分布參數(shù)為π的K個混合分布,此處的K值從語料庫數(shù)據(jù)中自動學習獲得,π由PYP模型中G決定。則語料庫D的PYP模型生成過程如下

πi|d,θ,G0～PYP(d,θ,G0),

xi|πi～F(xi|πi),i=1,…,n

(1)

三個參數(shù)分別是:折扣參數(shù)d,且d∈[0,1);強度參數(shù)θ,且θ>-d;基分布G0。F(xi|πi)為給定分布參數(shù)πi下生成xi的分布函數(shù)。當d=0時,此時的參數(shù)θ退化成為DP模型的參數(shù)α,PYP模型退化為一個含參數(shù)θG0的DP模型。圖1所示為PYP模型的生成圖模型。

圖1 PYP的圖模型表示

綜上所述,文本語料庫的生成過程可以描述如下。x1,x2,…xn表示語料庫中的全部n個文本,z1,z2,…zn為文本分配的類別標記。K為當前已從基分布G0中采樣的分布個數(shù)。分配到每個類別的文本數(shù)為Ck。則任意一個文本xi+1(1≤i

(2)

δk是Kronecher delta函數(shù),是描述文本分布到類別k的集中趨勢函數(shù)。在語料庫中的所有文本都獨立同分布于G,在采樣的過程中,每個文本都假定是從G的邊緣分布中計算其生成概率。式(3)能夠清晰地說明PYP模型生成所有文本的過程中可能會發(fā)生“富人越富”的問題。這導(dǎo)致在文本的采樣過程中,當越多的文本從同一個分布生成時,新的文本將以更大的機會分配到這個分布中。這種缺陷很大地影響了那些少樣本類別的生成,導(dǎo)致在處理不平衡數(shù)據(jù)集時出現(xiàn)了少樣本類別識別率不理想。

2.2 PYP模型的基本原理

本節(jié)將通過中國餐館過程(Chinese Restaurant Process,CRP)[24～25]描述整個文本語料庫的生成過程,CRP也經(jīng)常用于解釋DP模型。

為了更好解釋PYP模型的生成過程,本文也采用CRP來描述生成過程。zi表示第i位顧客,則PYP模型的中國餐館過程為

(3)

Zi表示除了第i位以外的其他所有顧客,Ck表示第k張桌子已入座的顧客人數(shù),zi=k表示入座在第k張桌子上。與CRP類似,PYP模型中的顧客也是無順序的,且每張桌子上的顧客都服從相同的分布。

(4)

Γ為伽馬函數(shù)。在這個生成過程中,把每個被標記的文本看作顧客分配到餐館中的一張桌子中,π(Z)=π1,…,πK表示所有的文本都被對應(yīng)的桌子標記。當一名顧客入座到一張無人的桌子上時,則被服從基分布G0的桌子標記,該標記也將應(yīng)用到隨后入座的其他顧客。如圖2所示。正如模型所定義的,文本中的詞項w均來自一個含有V詞匯的字典,每個類別中的所有詞項都服從同一個多項分布。則一個文本可表示為一個v維的向量D={w1,w2,…,w3},wv為一個文本中詞項v出現(xiàn)的頻率,進一步,語料庫D={x1,x2,…,x3}表示含有n個文本。則生成圖2中所示結(jié)果的概率為

P(D)=θ/θ×P0(s)·(d+θ)/(1+b)·P0(p)

×(1-d)/(2+θ)×P(s)·(2+2·d)/(3+θ)

·P0(e)…×(5-d)/(8+b)×P(s)

根據(jù)以上生成過程,在極度不平衡的數(shù)據(jù)集中,新文本隨著多樣本類別的文本量增加,分配到一個新類的可能性將會越來越低,最終導(dǎo)致“富人越富”的問題將明顯地出現(xiàn)。

圖2 用一個標記的中國餐館過程表示的PYP,對應(yīng)每位入座到不同的桌子的顧客,被標記成Z=1;2;1;3;1;1;2;1

3 DAPYP模型

3.1 DAPYP模型描述

DAPYP模型通過對折扣參數(shù)的自動調(diào)整來處理不平衡數(shù)據(jù)集的聚類分析問題,與固定折扣參數(shù)(強度參數(shù))PYP模型不同。在本文提出的方法中,引入一個不平衡率(Imbalance Ratio,IR),衡量多樣本類與少樣本類的之間的文本數(shù)不平衡比值。則計算機如下:

(5)

此處的#A表示多樣本個數(shù),同理#B為少樣本個數(shù)。表示IR的選擇判定如下:

1) 當IR>1時,多樣本類將與少樣本類的樣本數(shù)比值大于兩類之間的多項分布比值(樣本最合理的分配去向)。這將導(dǎo)致少樣本類的樣本因多樣本類的樣本數(shù)量大的優(yōu)勢而偏向多樣本類。

2) 當IR≤1時,多樣本類將與少樣本類的樣本數(shù)比值小于兩類之間的多項分布比值。這種情形下,不發(fā)生“富人越富”的問題,則DAPYP模型以PYP模型進行聚類。新文本也將以平等的優(yōu)勢分配到新類別中。

接下來,本文正式地接觸結(jié)合折扣參數(shù)和選擇判定參數(shù),給出懲罰機制,定義如下:

(6)

Ck為類別K的文本數(shù),d為自適應(yīng)的折扣參數(shù)。

3.2 DAPYP模型描述

階段1 計算文本的最優(yōu)分布概率,即分別計算分配到多樣本類別和少樣本類別的多項分布概率,并得到兩個分布概率的比值作為發(fā)生不平衡的臨界值,即為分布選擇最優(yōu)判定參數(shù)IR0。則IR0計算如下

(7)

此處的P(A)表示分配到多樣本類類別的多項分布概率,同理P(B)表示分配到少樣本類別的多項分布的概率。

1) 隨機采樣一個文本xi,基于以下條件概率就算多項分布概率:

(8)

和

p(xi|zi=k+1,D-i,d)=f(xj|π)dπ

(9)

D-i為除了文本xi(i≠j)之外的其他所有文本。

2) 根據(jù)前一步計算得出的文本分布概率,然后計算出多樣本類別與少樣本類別的樣本個數(shù)比值IR,并與IR0進行比較。計算IR/IR0的比值。

階段2 根據(jù)階段1中得出的結(jié)果,若IR/IR0>1,那么文本將以式(10)分配到多樣本類別中,如下式:

(10)

dt表示在時刻t文本分配到不同類別的折扣參數(shù)值,也即是懲罰力度。則分配到少樣本類別的條件概率為

(11)

否則以式(12)計算生成一個新類別的概率:

(12)

dt是一個隨著類別個數(shù)K逐漸增大而減小的函數(shù)。需要說明的是,模型的推斷主要集中在描述數(shù)據(jù)集的結(jié)構(gòu)分布的潛在變量z,其他的相關(guān)變量將會在計算過程中被積分。同樣,相應(yīng)的其他參數(shù)都會在實驗中給出相應(yīng)的初始值。

4 實驗結(jié)果與分析

本節(jié)將在人工數(shù)據(jù)集和真實的文本數(shù)據(jù)集上進行大量的驗證試驗,以檢驗本文提出的模型。首先給出如何獲得兩種類型的不平衡數(shù)據(jù)集,進而在性能上對比DPM(Dirichlet Process Mixture,DPM)[27]和DAPYP。

4.1 評價準側(cè)

在評價非參數(shù)文本聚類算法上,一般采用歸一化互信息(Normalized Mutual Information,NMI)來評價試驗結(jié)果[28]。本文提出的DAPYP模型同樣利用NMI衡量試驗的結(jié)果。作為衡量試驗結(jié)果與人工標記的文本之間的信息共享度量,NMI是一種有效的度量準則。下面給出NMI的定義:

(13)

r為文本數(shù)量,ri為類別i的文本個數(shù);與此類似,rj為類別j的文本個數(shù);rij表示文本同時屬于類別i和j的文本個數(shù)。當NMI趨近1時,說明聚類結(jié)果與人工標記越匹配;當NMI趨向于0時,說明聚類結(jié)果很差,即文本的隨機性很強。

4.2 人工數(shù)據(jù)集

4.2.1 人工數(shù)據(jù)集實驗設(shè)置

在驗證真實數(shù)據(jù)集之前,本文利用創(chuàng)建的人工數(shù)據(jù)集來說明DPM和DAPYP在處理不平衡數(shù)據(jù)集上的問題,同時驗證本文提出的模型。這種方法利用一個人工數(shù)據(jù)集生成器,人工設(shè)置不同類別的文本下的數(shù)據(jù)模擬。在人工數(shù)據(jù)集部分,實驗包括數(shù)據(jù)的屬性集和文本的特征集。在實際生活中,文本的主題分布符合多項分布的,且屬于同一個類別中的文本具有相似的特征分布,而不同類別之間的文本有很明顯的差異。所以本文使用的人工數(shù)據(jù)集生成器也是基于多個多項分布的隨機數(shù)發(fā)生器。盡管如此,仍然有些文本含有其他類別的部分特征值,因此在聚類過程中類別分布不是很明確,這也是導(dǎo)致在處理高度不平衡的文本數(shù)據(jù)集時,DPM、PYP等模型頻繁出現(xiàn)的“富人越富”問題。與此同時,真實的文本數(shù)據(jù)集,更是本身含有大量的噪音和數(shù)據(jù)集的稀疏性問題,對非參聚類模型的聚類結(jié)果造成很大干擾。根據(jù)以上描述,本文的人工數(shù)據(jù)集生成器需要對數(shù)據(jù)集大小、類別個數(shù)和文本特征集進行設(shè)置。通過生成器產(chǎn)生文本量為3010的數(shù)據(jù)集,其中每個文本的維度為10。全部數(shù)據(jù)的生成采用兩個混合的多項分布,每個分布生成一個類別的所有數(shù)據(jù)。從第一個多項分布中產(chǎn)生了3000個文本,另一個只產(chǎn)生10個文本。則本文的不平衡數(shù)據(jù)集為

i=1,2,…,3010;j=1,2;i=1+3000(j-1)

π1和π2分別是兩個多項分布的參數(shù),這兩個參數(shù)的值由狄利克雷分布獲得。在整個人工數(shù)據(jù)集的實驗過程中,每個模型下進行多次實驗,獲得其平均值,且每次實驗中模型迭代的次數(shù)設(shè)定在5000次。

4.2.2 實驗結(jié)果與分析

在人工數(shù)據(jù)集上,本文提出的模型可以有效地識別在不同程度下的不平衡數(shù)據(jù)集的少樣本類識別及樣本主題結(jié)構(gòu)。本文實驗中,設(shè)置了多樣本類別與少樣本類別樣本量之間的不平衡度IR值為0、10∶50、10∶100、10∶200、10∶500、10∶1000、10∶1500、10∶2000、10∶2500和10∶3000等10組不同的實驗組。

圖3 由Gibbs采樣算法的人工數(shù)據(jù)集類別個數(shù)軌跡圖

如圖3所示,描述了在IR為3000∶10的實驗過程中收斂情況,由圖可得,在迭代次數(shù)達到150次以后,類別個數(shù)開始趨于穩(wěn)定,實驗也進行收斂。同時也可以看到,DAPYP模型相比于DPM模型,能以更快的速度趨于收斂。此外,如圖4和圖5,展示了IR為1000∶10和IR為3000∶10下的10次Gibbs采樣后,少樣本類中識別出的樣本個數(shù),在圖4中,(c)(d)表示DAPYPM(DAPYP Model,DAPYPM)可以完全地識別出來。在(a)、(b)中,DPM在識別出少樣本類的過程中,卻有四個文本被分配到多樣本類別中。正如圖5所示,在IR值增大時,DPM則無法從多文本中識別出少樣本類別中文本。但DAPYPM仍然可以準確地識別出少樣本類的文本。綜上所述,實驗表明DAPYPM處理IR不同的不平衡的文本數(shù)據(jù)集上,對少樣本類的識別能力明顯優(yōu)于DPM模型。

圖4 由Gibbs算法采樣的人工數(shù)據(jù)IR為1000∶10的文本標記估計

圖5 由Gibbs算法采樣的人工數(shù)據(jù)IR為3000∶10的文本標記估計

因此,在人工數(shù)據(jù)集上,本文提出的模型可以有效地識別出少樣本類。

4.3 真實數(shù)據(jù)集

4.3.1 真實數(shù)據(jù)集實驗設(shè)置

為了驗證本文提出的方法在現(xiàn)實世界真實數(shù)據(jù)集上的效果,采用了UCI[29]機器學習倉庫網(wǎng)站中的開源數(shù)據(jù)集Reuter_50_50 Data Set。這個數(shù)據(jù)集中包含訓練集和測試集兩個部分,在本實驗中,為了能夠測試更大不平衡度情形下的效果,將兩個部分的數(shù)據(jù)集,共得到了50個主題類別,每個主題類別下有100個實例文本。所以,本實驗從中選取了三個主題類別的數(shù)據(jù)集,共300個數(shù)據(jù)文本。如表1描述,選取其中3個主題類別的文本數(shù)據(jù)集。

表1 真實的文本數(shù)據(jù)集描述(D:文本個數(shù),W:詞項個數(shù))

基于上述的三個主題數(shù)據(jù)集,把其中一個類別作為少樣本類,另一個作為多樣本類,此外第三個類別與多樣本類別中的樣本個數(shù)保持相同,作為對照。在實際實驗中,把其中一個類別的文本數(shù)量逐漸調(diào)整為100、50、10,得到了三個IR等級,最終得到三組不同IR的數(shù)據(jù)集。表2描述了不同IR值下的數(shù)據(jù)集情況。

4.3.2 實驗結(jié)果與分析

本小節(jié)描述的是在不同的IR設(shè)置條件下,DPM和DAPYP模型的實驗結(jié)果。在參數(shù)設(shè)置中,alpha和alphaWords都是設(shè)置為1.0。DPM和DAPYP在不同的IR下的NMI實驗結(jié)果如圖6所示。

表2 不同IR下不平衡數(shù)據(jù)集

圖6 DPM和DAPYP的NMI軌跡圖

下面采用NMI來評估DPM和DAPYPM在不同IR下的實驗結(jié)果。

從圖6的實驗結(jié)果分析得出,IR在不同的值下,DAPYP模型可以有效地從不平衡數(shù)據(jù)集中識別出小樣本類。首先在IR為1∶1∶1時,DPM的聚類結(jié)果表現(xiàn)良好,NMI可達到0.77,但DAPYP有出色的聚類效果,NMI有0.98。當在IR為2∶1∶2的情況下,由于在真實數(shù)據(jù)集中,受少量的噪音數(shù)據(jù)影響,容易導(dǎo)致有些文本被單獨分成新的類別,因此,在DPM中,如IR不是很極端的情況下,也有較好的聚類效果。但在IR的值達到為10∶1∶10時,對于少樣本類的識別,DPM的識別率就很低,只有0.36左右,而DAPYP還保持0.63的聚類效果。綜上,本文提出的方法可以處理不平衡文本數(shù)據(jù)集的聚類分析問題,也可以很好地自動學習出數(shù)據(jù)集中的類別個數(shù)。

5 結(jié)語

本文提出了一種處理不平衡的文本數(shù)據(jù)集聚類算法,DAPYP模型。該模型在基于PYP模型上,不僅能從不平衡數(shù)據(jù)集下自動學習類別個數(shù),還能有效地識別出少樣本類的樣本。此外,詳細闡述了如何在實際應(yīng)用中,實現(xiàn)PYP模型中的折扣參數(shù)(強度參數(shù))的自適應(yīng)調(diào)整參數(shù)值。也更進一步比較了在不平衡文本數(shù)據(jù)集的情況下,現(xiàn)有的非參數(shù)文本聚類方法(DPM、PYP等)。實驗結(jié)果表明,本文提出的模型在不平衡的文本數(shù)據(jù)上可以有效地識別出少樣本類。

在未來的研究中,將致力于在大規(guī)模的極端不平衡數(shù)據(jù)集上處理的模型的收斂速度以及在動態(tài)的不平衡文本數(shù)據(jù)上的聚類研究。具體來說,預(yù)計將在兩個方面提高本文的模型性能:第一,提出更合理的模型,找出更好的懲罰機制,用于處理不平衡數(shù)據(jù)中多類別的聚類分析;第二,研究可適用于動態(tài)不平衡數(shù)據(jù)集上的聚類算法。

[1] Japkowicz N. Concept-Learning in the Presence of Between-Class and Within-Class Imbalances[C]//Biennial Conference of the Canadian Society on Computational Studies of Intelligence: Advances in Artificial Intelligence. Springer-Verlag,2001:67-77.

[2] Holte R, Acker L, Porter B. Concept Learning and the Problem of Small Disjuncts[C]//Eleventh International Joint Conference on Artificial Intelligence,1995:813-818.

[3] Mease D, Wyner A J, Buja A. Boosted Classification Trees and Class Probability/Quantile Estimation[J]. Journal of Machine Learning Research,2007,8(3):409-439.

[4] Han H, Wang W Y, Mao B H. Borderline-SMOTE: A New Over-Sampling Method in Imbalanced Data Sets Learning[C]//Advances in Intelligent Computing. Springer Berlin Heidelberg,2005:878-887.

[5] He H, Bai Y, Garcia E A, et al. ADASYN: Adaptive synthetic sampling approach for imbalanced learning[C]//Neural Networks, 2008. IJCNN 2008. (IEEE World Congress on Computational Intelligence). IEEE International Joint Conference on. IEEE,2008:1322-1328.

[6] Lou X J, Sun Y X, Liu H T. Clustering boundary over-sampling classification method for imbalanced data sets[J]. Journal of Zhejiang University(Engineering Science),2013,37(2):135-43.

[7] Drummond C, Holte R C. C4.5, Class Imbalance, and Cost Sensitivity: Why Under-Sampling beats OverSampling[J]. Proc of the Icml Workshop on Learning from Imbalanced Datasets Ⅱ,2003:1-8.

[8] Fithian W, Hastie T. Local Case-control Sampling: Efficient Subsampling in Imbalanced Data Sets[J]. Annals of Statistics,2013,60(5):187-190.

[9] Kubat M. Addressing the Curse of Imbalanced Training Sets: One-Sided Sampling[C]//International Conference on Machine Learning,1997.

[10] 張晶,馮林.針對動態(tài)非平衡數(shù)據(jù)集魯棒的在線極端學習機[J].計算機研究與發(fā)展,2015(7):1487-1498. ZHANG Jing, FENG Lin. An Algorithm of Robust Online Extreme Learning Machine for Dynamic Imbalanced Datasets[J]. Journal of Computer Research and Development,2015(7):1487-1498.

[11] Hartigan J A, Wong M A. A K-means clustering algorithm[J]. Applied Statistics,1979,28(1):100-108.

[12] Estivill-Castro V. Why so many clustering algorithms: a position paper[J]. Acm Sigkdd Explorations Newsletter,2002,4(1):65-75.

[13] Kumar N S, Rao K N, Govardhan A, et al. Undersampled (K)-means approach for handling imbalanced distributed data[J]. Progress in Artificial Intelligence,2014,3(1):29-38.

[14] Kumar C N S, Rao K N, Govardhan A, et al. Subset K-means approach for handling imbalanced-distributed data[C]//Emerging ICT for Bridging the Future-Proceedings of the 49th Annual Convention of the Computer Society of India CSI Volume 2. Springer International Publishing,2015:497-508.

[15] Richardson S, Green P J. On Bayesian analysis of mixtures with an unkown number of components[J]. Journal of the Royal Statistical Society,1997.

[16] Frigyik B A, Kapila A, Gupta M R. Introduction to the Dirichlet distribution and related processes[J]. Spokesman Review,2010,59(4):731-758.

[17] Antoniak C E. Mixtures of Dirichlet Processes with Applications to Bayesian Nonparametric Problems[J]. Annals of Statistics,1974,2(6):1152-1174.

[18] Ferguson T S. A Bayesian Analysis of Some Nonparametric Problems[J]. Annals of Statistics,2015,1(2):209-230.

[19] Müller B P, Quintana F A. Nonparametric Bayesian analysis[C]//Statistical Science,2010.

[20] Pitman J, Yor M. The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator[J]. Annals of Probability,1995,25(2):855-900.

[21] Teh Y W, Jordan M I, Beal M J, et al. Hierarchical Dirichlet Processes[J]. Journal of the American Statistical Association,2006,101(476):1566-1581.

[22] Teh Y W. A hierarchical Bayesian language model based on Pitman-Yor processes[J]. Coling/acl,2010:985-992.

[23] Pitman J, Yor M. The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator[J]. Annals of Probability,2010,25(2):855-900.

[24] Buntine W, Hutter M. A Bayesian View of the Poisson-Dirichlet Process[J]. Cornell University Library, 2010, arxiv: 1007.0296.

[25] Chen C, Du L, Buntine W. Sampling Table Configurations for the Hierarchical Poisson-Dirichlet Process[C]//Machine Learning and Knowledge Discovery in Databases. Springer Berlin Heidelberg,2011:296-311.

[26] Ishwaran H, James L F. Gibbs Sampling Methods for Stick-Breaking Priors[J]. Journal of the American Statistical Association,2001,96(453):161-173.

[27] Antoniak C E. Mixtures of Dirichlet Processes with Applications to Bayesian Nonparametric Problems[J]. Annals of Statistics,1974,2(6):1152-1174.

[28] Huang R, Yu G, Wang Z, et al. Dirichlet Process Mixture Model for Text Clustering with Feature Partition[J]. IEEE Transactions on Knowledge & Data Engineering,2012,99(8):1748-1759.

[29] J. Houvardas, E. Stamatatos, a N-gram Feature Selection for Authorship Identification[C]//Proc. of the 12th Int. Conf. on Artificial Intelligence: Methodology, Systems, Applications,2006,4183:77-86.

A Text Clustering Approach with Pitman-Yor Process Model for Imbalanced Datasets

ZHONG Wenliang HUANG Ruizhang

(College of Computer Science and Technology, Guizhou University, Guiyang 550025)

One essential practical problem of text clustering is that real text datasets are usually highly imbalanced. Although existing knowledge discovery and data engineering techniques have shown some successes in many real-world applications, the problem of clustering from imbalanced datasets is a relatively new challenge that has attracted growing interest from both academic and industry. However, one of the most critical problems is that extremely small clusters, as well as large clusters, are need to be discovered simultaneously from imbalanced datasets. In this paper, a novel model, namely DAPYP (discount adaptation Pitman-Yor process) model is proposed, to address the issue. The DAPYP is designed based on the PYP (Pitman-Yor process) which produces power-law distribution and more closely resembles the problem of imbalanced clustering. Rather than a fixed discount parameter employed by PYP, the discount parameter automatically is adjusted according to cluster sizes to relax its “rich get richer” property. The proposed model is able to deal with the imbalanced datasets, and learn the number of clusters during clustering. The performance of proposed approach is explored on both synthetic datasets and real text datasets. Experiments illustrate that our proposed DAPYP model is effective to solve the imbalanced problem of text datasets.

text clustering, imbalanced datasets, Pitman-Yor process

2016年8月4日,

2016年9月17日

國家自然科學基金(編號:61462011;61202089);高等學校博士學科專項科研基金(編號:20125201120006);貴州大學引進人才科研項目(編號:2011015);貴州大學研究生創(chuàng)新基金(編號:研理工2016052)資助。作者簡介:鐘文良,男,碩士,研究方向:文本挖掘。黃瑞章,女,副教授,碩士生導(dǎo)師,研究方向:文本挖掘、網(wǎng)絡(luò)挖掘、機器學習和知識學習等。

TP312

10.3969/j.issn.1672-9722.2017.02.021