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

鐘文良 黃瑞章

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

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

鐘文良 黃瑞章

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

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

文本聚類; 不平衡數據集; Pitman-Yor過程

Class Number TP312

1 引言

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

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

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

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

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

2 PYP模型及其基本原理

2.1 PYP模型

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

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

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

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

(1)

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

圖1 PYP的圖模型表示

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

(2)

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

2.2 PYP模型的基本原理

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

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

(3)

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

(4)

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

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)

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

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

3 DAPYP模型

3.1 DAPYP模型描述

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

(5)

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

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

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

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

(6)

Ck為類別K的文本數,d為自適應的折扣參數。

3.2 DAPYP模型描述

階段1 計算文本的最優分布概率,即分別計算分配到多樣本類別和少樣本類別的多項分布概率,并得到兩個分布概率的比值作為發生不平衡的臨界值,即為分布選擇最優判定參數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) 根據前一步計算得出的文本分布概率,然后計算出多樣本類別與少樣本類別的樣本個數比值IR,并與IR0進行比較。計算IR/IR0的比值。

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

(10)

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

(11)

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

(12)

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

4 實驗結果與分析

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

4.1 評價準側

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

(13)

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

4.2 人工數據集

4.2.1 人工數據集實驗設置

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

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

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

4.2.2 實驗結果與分析

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

圖3 由Gibbs采樣算法的人工數據集類別個數軌跡圖

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

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

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

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

4.3 真實數據集

4.3.1 真實數據集實驗設置

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

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

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

4.3.2 實驗結果與分析

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

表2 不同IR下不平衡數據集

圖6 DPM和DAPYP的NMI軌跡圖

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

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

5 結語

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

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

[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] 張晶,馮林.針對動態非平衡數據集魯棒的在線極端學習機[J].計算機研究與發展,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);貴州大學研究生創新基金(編號:研理工2016052)資助。作者簡介:鐘文良,男,碩士,研究方向:文本挖掘。黃瑞章,女,副教授,碩士生導師,研究方向:文本挖掘、網絡挖掘、機器學習和知識學習等。

TP312

10.3969/j.issn.1672-9722.2017.02.021