關於描述CRP模型中的聚類演算法的論文

　　本文是由上傳的：基於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

　　關於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模型的詞彙分類，實現主題模型等。相信在不遠的將來，這種利用無線混合模型的聚類方法會有更多的開拓空間。

　　參考文獻

　　[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