基于CRP模型的聚類算法

白云鵬

【摘要】 關(guān)于聚類問題現(xiàn)在已經(jīng)有很多方法可以實(shí)現(xiàn)，但大多數(shù)基于有限混合模型的聚類方法需要預(yù)先估計(jì)聚類的個(gè)數(shù)，因而聚類的準(zhǔn)確性和泛化性會(huì)受到一定影響。本文則提出了一種基于無線混合模型——中國(guó)餐館模型（CRP）的聚類方法，CRP模型是Dirichlet過程的一種表示方法，基于Dirichlet無線混合模型找出其后驗(yàn)分布，利用Gibbs采樣MCMC方法估計(jì)出模型中各個(gè)參數(shù)以及潛在的聚類個(gè)數(shù)，并在MATLAB環(huán)境下進(jìn)行一個(gè)小實(shí)驗(yàn)來驗(yàn)證聚類的效果。

【關(guān)鍵詞】 聚類 CRP模型 Dirichlet過程 MCMC采樣

一、引言

聚類顧名思義就是把事物按照特定的性質(zhì)或者相似性進(jìn)行區(qū)分和分類，在這一過程中不指導(dǎo)，屬于無監(jiān)督分類。作為一種重要的數(shù)據(jù)分析方法，聚類分析問題在很久以前就已經(jīng)為人們所研究，并且已經(jīng)取得了一定成果，目前的算法已經(jīng)能對(duì)一般簡(jiǎn)單的聚類問題做出很好的聚類結(jié)果。但隨著大數(shù)據(jù)時(shí)代的到來，實(shí)際應(yīng)用中的數(shù)據(jù)越來月復(fù)雜，如基因表達(dá)數(shù)據(jù)，交通流數(shù)據(jù)，web文檔等，有一些數(shù)據(jù)還存在著極大的不確定性，有的數(shù)據(jù)可以達(dá)到幾百維甚至上千維，受“維度效應(yīng)”的影響，很多在低維空間能得到很好結(jié)果的聚類算法在高維空間中并不是十分理想。

關(guān)于高維數(shù)據(jù)的聚類近幾年一些基于有限混合模型的方法取得了很有效的成果。但是這些算法需要提前估計(jì)聚類個(gè)數(shù)的前提下，根據(jù)樣本的屬性進(jìn)行分析分類。本文采用了一種基于Dirichlet無線混合模型的方法，利用CRP模型和Gibbs采樣方法，在分析過程中找出潛在的聚類個(gè)數(shù)，實(shí)現(xiàn)對(duì)數(shù)據(jù)的聚類。

二、CRP模型

2.1 關(guān)于CRP

CRP模型是Dirichlet過程的一種表示方法，它是關(guān)于M個(gè)顧客到一家中國(guó)餐館如何就坐問題的一個(gè)離散隨機(jī)過程。具體描述如下：有一家中國(guó)餐館，假設(shè)有無限個(gè)桌子，并且每張桌子上可以容納無限個(gè)顧客，每一個(gè)顧客到來時(shí)可以隨意選擇一個(gè)餐桌，也可以自己新開一個(gè)餐桌。在CRP過程中，我們把每一位到來的顧客都當(dāng)作最后一位來看待，有如下分配過程：第一位顧客到來，一定會(huì)開一個(gè)桌子自己坐下，第二個(gè)顧客到來時(shí)，以一定概率坐在第一個(gè)人開的桌子上，一定概率新開一張桌子，第三個(gè)顧客到來時(shí)，有一定概率坐在第一、二個(gè)人開的桌子上，也可以開第三張桌子……以此類推，具體定義的概率如下：

其中α是狄利克雷的先驗(yàn)參數(shù)； c 是第m 個(gè)顧客選擇的餐桌上已有的顧客人數(shù)。顧客選擇餐桌時(shí)不僅與顧客對(duì)餐桌的個(gè)人情感有關(guān)，還與該桌上在座的顧客關(guān)系有關(guān)，如果是朋友或是認(rèn)識(shí)的人就算有更好的選擇顧客也可能選擇與朋友坐一桌。而在CRP模型中并未考慮到顧客的情感色彩因素。

2.2 Gibbs Samping

Gibbs Sampling是一種馬爾可夫蒙特卡羅方法（MCMC），這種方法廣泛應(yīng)用于離散隨機(jī)過程的采樣處理，它的中心思想就是由一個(gè)具有2個(gè)或更多變量的聯(lián)合概率分布P（x1，x2，…，xn），生成一個(gè)樣本序列{y1，y2，…，ym}，用于逼近這一個(gè)聯(lián)合分布，或計(jì)算一個(gè)積分（例如期望）。

關(guān)于Dirichlet混合模型的Gibbs Sampling實(shí)際上就是根據(jù)先驗(yàn)求后驗(yàn)的過程，雖然中心思想一樣，但具體實(shí)現(xiàn)方法有很多種[1]，這里根據(jù)CRP的情況，選擇其中一種算法，在下一節(jié)詳細(xì)講解。

2.3 參數(shù)估計(jì)

假設(shè)有一個(gè)整體的數(shù)據(jù)集D={xi}in=1，它的兩個(gè)參數(shù)為z=（z1，…，zn），zn∈{1，…，K}，φ=（φ1…，φK）

其中Z為隱變量，表示樣本聚類的標(biāo)簽，Zi=k代表當(dāng)前第i個(gè)類有k個(gè)成員，而φ則是該模型的每一類的成員參數(shù)，根據(jù)貝葉斯理論，可以得出p（φ，z|D）∝p0（φ）p0（z）p（D|φ，z），因此，參數(shù)φ后驗(yàn)分布可以通過計(jì)算其先驗(yàn)分布及似然函數(shù)來實(shí)現(xiàn)，在此基礎(chǔ)上計(jì)算出φ的后驗(yàn)分布，并通過Gibbs采樣的方法更新參數(shù)φ。

其中nk代表當(dāng)前坐在第k個(gè)桌子上的其他人的總數(shù)。

2.4 使用Gibbs采樣的算法

假設(shè)待處理的數(shù)據(jù)是高斯隨機(jī)分布的，首先隨機(jī)初始化參數(shù)z，φ。

對(duì)于每一個(gè)zi才用如下采樣方法：

選擇已有桌子（第K個(gè)）的概率：

新開一個(gè)桌子（第K+1）的概率：

而對(duì)于參數(shù)φ，采用如下方式（每當(dāng)?shù)趉個(gè)桌子上加了人，這個(gè)類的參數(shù)φk就要更新）：

三、實(shí)驗(yàn)與結(jié)果

本文以matlab為平臺(tái)，對(duì)二維空間上一些隨機(jī)分布的點(diǎn)進(jìn)行模擬聚類測(cè)試。正如上一節(jié)所說，這里對(duì)測(cè)試數(shù)據(jù)采用高斯隨機(jī)來生成，為了簡(jiǎn)化處理，生成了300個(gè)各項(xiàng)同向高斯分布的點(diǎn)，具體代碼如下：

這樣就默認(rèn)把這300個(gè)點(diǎn)分成了潛在的3個(gè)類，我們最后要求出的結(jié)果應(yīng)該就是K=3。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，真正的結(jié)果與Dirichlet過程CRP模型的集中度參數(shù)α有很大關(guān)系。α很大的時(shí)候會(huì)不準(zhǔn)確，我在這里讓?duì)岭S機(jī)選取，并重復(fù)了100次，最后一次的結(jié)果是k=4：

而根據(jù)α的不同取值，100次的聚類結(jié)果在3-6之間，其中還是以3居多：

由此可知，對(duì)于Dirichlet先驗(yàn)參數(shù)α的選擇會(huì)直接影響到最終的聚類效果。而Dirichlet過程作為一個(gè)無線混合模型，隨著數(shù)據(jù)的增多，模型的個(gè)數(shù)是呈現(xiàn)log 增加的，即模型的個(gè)數(shù)的增長(zhǎng)是比數(shù)據(jù)的增長(zhǎng)要緩慢得多的。同時(shí)也可以說明Dirichlet過程是有一個(gè)馬太效應(yīng)在里面的，即“越富裕的人越來越富?！?，每個(gè)桌子已有的人越多，那么下一次被選中的概率越大，因?yàn)榕c在桌子上的個(gè)數(shù)成正比的，因而這種無線混合模型對(duì)于發(fā)現(xiàn)潛在的聚類個(gè)數(shù)會(huì)有很好的效果。

四、總結(jié)

基于CRP模型的聚類方法不同于先前的有限混合模型，無需預(yù)先估計(jì)聚類的個(gè)數(shù)，而是在分析過程中自動(dòng)確定。聚類的結(jié)果與α有關(guān)，所以選取合適的集中度參數(shù)很重要。關(guān)于CRP模型現(xiàn)在的研究還不是很廣泛，也有一些在主題模型中的應(yīng)用，比如基于CRP模型的詞匯分類，實(shí)現(xiàn)主題模型等。相信在不遠(yuǎn)的將來，這種利用無線混合模型的聚類方法會(huì)有更多的開拓空間。

參 考 文 獻(xiàn)

[1] 張林，劉輝. Dirichlet過程混合模型的聚類算法[J]. 中國(guó)礦業(yè)大學(xué)學(xué)報(bào). 2012（01）

[2] 張小平，周雪忠，黃厚寬，馮奇，陳世波. 基于詞相似性與CRP的主題模型[J]. 模式識(shí)別與人工智能. 2010（01）[3] 羅輝停. 基于CRP模型的評(píng)論熱點(diǎn)挖掘研究修正版[J]. 技術(shù)與創(chuàng)新管理. 2012（02）

[4] 易瑩瑩. 基于Dirichlet過程的非參數(shù)貝葉斯方法研究綜述[J]. 統(tǒng)計(jì)與決策. 2012（04）

[5] Pruteanu-Malinici I，Ren L，Paisley J，Wang E，Carin L.Hierarchical Bayesian modeling of topics in time-stamped documents. IEEE Transactions on Pattern Analysis and Ma-chine Intelligence . 2010

[6] H. Ishwaran，M. Zarepour.Markov Chain Monte Carlo in approximate Dirichlet and beta two-parameter process hierarchical models. Biometrika . 2000

[7] R Thibaux，M I Jordan.Hierarchical beta processes and the indian buffet process. Proceedings of International Conference on Artificial Intelligence and Statistics . 2007