基于CRP模型的聚類算法

白云鵬

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

【關鍵詞】 聚類 CRP模型 Dirichlet過程 MCMC采樣

一、引言

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

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

二、CRP模型

2.1 關于CRP

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

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

2.2 Gibbs Samping

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

關于Dirichlet混合模型的Gibbs Sampling實際上就是根據先驗求后驗的過程，雖然中心思想一樣，但具體實現方法有很多種[1]，這里根據CRP的情況，選擇其中一種算法，在下一節詳細講解。

2.3 參數估計

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

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

其中nk代表當前坐在第k個桌子上的其他人的總數。

2.4 使用Gibbs采樣的算法

假設待處理的數據是高斯隨機分布的，首先隨機初始化參數z，φ。

對于每一個zi才用如下采樣方法：

選擇已有桌子（第K個）的概率：

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

而對于參數φ，采用如下方式（每當第k個桌子上加了人，這個類的參數φk就要更新）：

三、實驗與結果

本文以matlab為平臺，對二維空間上一些隨機分布的點進行模擬聚類測試。正如上一節所說，這里對測試數據采用高斯隨機來生成，為了簡化處理，生成了300個各項同向高斯分布的點，具體代碼如下：

這樣就默認把這300個點分成了潛在的3個類，我們最后要求出的結果應該就是K=3。實驗結果發現，真正的結果與Dirichlet過程CRP模型的集中度參數α有很大關系。α很大的時候會不準確，我在這里讓α隨機選取，并重復了100次，最后一次的結果是k=4：

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

由此可知，對于Dirichlet先驗參數α的選擇會直接影響到最終的聚類效果。而Dirichlet過程作為一個無線混合模型，隨著數據的增多，模型的個數是呈現log 增加的，即模型的個數的增長是比數據的增長要緩慢得多的。同時也可以說明Dirichlet過程是有一個馬太效應在里面的，即“越富裕的人越來越富裕”，每個桌子已有的人越多，那么下一次被選中的概率越大，因為與在桌子上的個數成正比的，因而這種無線混合模型對于發現潛在的聚類個數會有很好的效果。

四、總結

基于CRP模型的聚類方法不同于先前的有限混合模型，無需預先估計聚類的個數，而是在分析過程中自動確定。聚類的結果與α有關，所以選取合適的集中度參數很重要。關于CRP模型現在的研究還不是很廣泛，也有一些在主題模型中的應用，比如基于CRP模型的詞匯分類，實現主題模型等。相信在不遠的將來，這種利用無線混合模型的聚類方法會有更多的開拓空間。

參 考 文 獻

[1] 張林，劉輝. Dirichlet過程混合模型的聚類算法[J]. 中國礦業大學學報. 2012（01）

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

[4] 易瑩瑩. 基于Dirichlet過程的非參數貝葉斯方法研究綜述[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