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