關于描述CRP模型中的聚類算法的論文
本文是由上傳的：基于CRP模型的聚類算法。
【摘要】 關于聚類問題現(xiàn)在已經有很多方法可以實現(xiàn)，但大多數(shù)基于有限混合模型的聚類方法需要預先估計聚類的個數(shù)，因而聚類的準確性和泛化性會受到一定影響。本文則提出了一種基于無線混合模型――中國餐館模型（CRP）的聚類方法，CRP模型是Dirichlet過程的一種表示方法，基于Dirichlet無線混合模型找出其后驗分布，利用Gibbs采樣MCMC方法估計出模型中各個參數(shù)以及潛在的聚類個數(shù)，并在MATLAB環(huán)境下進行一個小實驗來驗證聚類的效果。
【關鍵詞】 聚類 CRP模型 Dirichlet過程 MCMC采樣
一、引言
聚類顧名思義就是把事物按照特定的性質或者相似性進行區(qū)分和分類，在這一過程中不指導，屬于無監(jiān)督分類。作為一種重要的數(shù)據(jù)分析方法，聚類分析問題在很久以前就已經為人們所研究，并且已經取得了一定成果，目前的算法已經能對一般簡單的聚類問題做出很好的聚類結果。但隨著大數(shù)據(jù)時代的到來，實際應用中的數(shù)據(jù)越來月復雜，如基因表達數(shù)據(jù)，交通流數(shù)據(jù)，web文檔等，有一些數(shù)據(jù)還存在著極大的不確定性，有的數(shù)據(jù)可以達到幾百維甚至上千維，受“維度效應”的影響，很多在低維空間能得到很好結果的聚類算法在高維空間中并不是十分理想。
關于高維數(shù)據(jù)的聚類近幾年一些基于有限混合模型的方法取得了很有效的成果。但是這些算法需要提前估計聚類個數(shù)的前提下，根據(jù)樣本的屬性進行分析分類。本文采用了一種基于Dirichlet無線混合模型的方法，利用CRP模型和Gibbs采樣方法，在分析過程中找出潛在的聚類個數(shù)，實現(xiàn)對數(shù)據(jù)的聚類。
二、CRP模型
2.1 關于CRP
CRP模型是Dirichlet過程的一種表示方法，它是關于M個顧客到一家中國餐館如何就坐問題的一個離散隨機過程。具體描述如下：有一家中國餐館，假設有無限個桌子，并且每張桌子上可以容納無限個顧客，每一個顧客到來時可以隨意選擇一個餐桌，也可以自己新開一個餐桌。在CRP過程中，我們把每一位到來的顧客都當作最后一位來看待，有如下分配過程：第一位顧客到來，一定會開一個桌子自己坐下，第二個顧客到來時，以一定概率坐在第一個人開的桌子上，一定概率新開一張桌子，第三個顧客到來時，有一定概率坐在第一、二個人開的桌子上，也可以開第三張桌子……以此類推，具體定義的概率如下：
其中α是狄利克雷的先驗參數(shù)； c 是第m 個顧客選擇的餐桌上已有的顧客人數(shù)。顧客選擇餐桌時不僅與顧客對餐桌的個人情感有關，還與該桌上在座的顧客關系有關，如果是朋友或是認識的人就算有更好的選擇顧客也可能選擇與朋友坐一桌。而在CRP模型中并未考慮到顧客的情感色彩因素。
2.2 Gibbs Samping
關于Dirichlet混合模型的Gibbs Sampling實際上就是根據(jù)先驗求后驗的過程，雖然中心思想一樣，但具體實現(xiàn)方法有很多種[1]，這里根據(jù)CRP的情況，選擇其中一種算法，在下一節(jié)詳細講解。
2.3 參數(shù)估計
假設有一個整體的數(shù)據(jù)集D={xi}in=1，它的兩個參數(shù)為z=（z1，…，zn），zn∈{1，…，K}，φ=（φ1…，φK）
其中Z為隱變量，表示樣本聚類的標簽，Zi=k代表當前第i個類有k個成員，而φ則是該模型的每一類的成員參數(shù)，根據(jù)貝葉斯理論，可以得出p（φ，z|D）∝p0（φ）p0（z）p（D|φ，z），因此，參數(shù)φ后驗分布可以通過計算其先驗分布及似然函數(shù)來實現(xiàn)，在此基礎上計算出φ的后驗分布，并通過Gibbs采樣的方法更新參數(shù)φ。
其中nk代表當前坐在第k個桌子上的其他人的總數(shù)。
2.4 使用Gibbs采樣的算法
假設待處理的數(shù)據(jù)是高斯隨機分布的，首先隨機初始化參數(shù)z，φ。
對于每一個zi才用如下采樣方法：
選擇已有桌子（第K個）的概率：
新開一個桌子（第K+1）的概率：
而對于參數(shù)φ，采用如下方式（每當?shù)趉個桌子上加了人，這個類的參數(shù)φk就要更新）：
三、實驗與結果
本文以matlab為平臺，對二維空間上一些隨機分布的點進行模擬聚類測試。正如上一節(jié)所說，這里對測試數(shù)據(jù)采用高斯隨機來生成，為了簡化處理，生成了300個各項同向高斯分布的.點，具體代碼如下：
這樣就默認把這300個點分成了潛在的3個類，我們最后要求出的結果應該就是K=3。實驗結果發(fā)現(xiàn)，真正的結果與Dirichlet過程CRP模型的集中度參數(shù)α有很大關系。α很大的時候會不準確，我在這里讓α隨機選取，并重復了100次，最后一次的結果是k=4：
而根據(jù)α的不同取值，100次的聚類結果在3-6之間，其中還是以3居多：
由此可知，對于Dirichlet先驗參數(shù)α的選擇會直接影響到最終的聚類效果。而Dirichlet過程作為一個無線混合模型，隨著數(shù)據(jù)的增多，模型的個數(shù)是呈現(xiàn)log 增加的，即模型的個數(shù)的增長是比數(shù)據(jù)的增長要緩慢得多的。同時也可以說明Dirichlet過程是有一個馬太效應在里面的，即“越富裕的人越來越富裕”，每個桌子已有的人越多，那么下一次被選中的概率越大，因為與在桌子上的個數(shù)成正比的，因而這種無線混合模型對于發(fā)現(xiàn)潛在的聚類個數(shù)會有很好的效果。
四、總結
基于CRP模型的聚類方法不同于先前的有限混合模型，無需預先估計聚類的個數(shù)，而是在分析過程中自動確定。聚類的結果與α有關，所以選取合適的集中度參數(shù)很重要。關于CRP模型現(xiàn)在的研究還不是很廣泛，也有一些在主題模型中的應用，比如基于CRP模型的詞匯分類，實現(xiàn)主題模型等。相信在不遠的將來，這種利用無線混合模型的聚類方法會有更多的開拓空間。
參 考 文 獻
[4] 易瑩瑩. 基于Dirichlet過程的非參數(shù)貝葉斯方法研究綜述[J]. 統(tǒng)計與決策. 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
【描述CRP模型中的聚類算法的論文】相關文章：
針對非均勻數(shù)據(jù)集自適應聚類算法的研究論文04-14
《算法與描述》教學反思07-07
課程表的空間模型及排課算法分析的教育論文07-03
碰撞檢測中的KDOPS算法論文06-15
計量模型論文04-11
最短路徑算法在線路搶修中的應用論文02-20
有計量模型的論文04-11