基于非參數(shù)貝葉斯的聚類分析

楊穎穎

（滁州職業(yè)技術學院基礎部，安徽滁州239000）

基于非參數(shù)貝葉斯的聚類分析

楊穎穎

（滁州職業(yè)技術學院基礎部，安徽滁州239000）

將Dirichlet過程作為無窮高斯混合模型中權重參數(shù)的先驗分布，利用貝葉斯定理得到參數(shù)的估計，并由Gibbs抽樣算法得出聚類的個數(shù)和判斷觀測值的指示因子，利用統(tǒng)計模擬說明了算法的有效性，與傳統(tǒng)方法相比，該方法誤判率更低。

Dirichlet過程；Gibbs抽樣；聚類分析

聚類分析是一種重要的無監(jiān)督分類方法和數(shù)據(jù)挖掘工具，在數(shù)據(jù)處理領域起到了重要的作用。非參數(shù)貝葉斯聚類可以使用基于特定模型的指標代替?zhèn)鹘y(tǒng)的簡單的距離指標來實現(xiàn)聚類過程，并可以在聚類的過程中引入貝葉斯假設檢驗。基于有限高斯混合模型的貝葉斯聚類是非參數(shù)聚類方法中較常用的一種方法[1]，有限高斯混合模型雖然在多維尺度聚類問題中獲得了廣泛應用和發(fā)展，但是它本身需要事先指定聚類的個數(shù)[2]，因此會影響聚類分析的準確性[3]。為了解決這個問題，采用基于無窮高斯混合模型的非參數(shù)貝葉斯模型進行聚類分析。首先選取Dirichlet過程作為參數(shù)分布的先驗分布，聚類個數(shù)可由模型和數(shù)據(jù)計算得出[4]，因而可以解決有限混合模型中聚類個數(shù)不確定的難題。

1 無窮高斯混合模型

無窮高斯混合模型的基本形式：

Ferguson[5]證明，任意密度函數(shù)f（x）在L1范數(shù)下均收斂于（1）式。下面對于（1）式中（i=1，2，…）采取Dirichlet過程的先驗分布。

首先給出Dirichlet過程的定義。假設G是可測空間Ω上的隨機概率分布，參數(shù)α是正實數(shù)，空間Ω上的概率分布G如果滿足以下條件：對可測空間Ω的任意有限分割A1，…，Ak均存在：

[G（A1），…，G（Ak）]~Dir[αG0（A1），…，αG0（Ak）]，則G服從由基分布G0和超參數(shù)α組成的Dirichlet過程，記為G~DP（α，G0）。

Dirichlet過程應用起來方便靈活，它允許模型參數(shù)的實際先驗分布G隨機偏離基分布G0，并且Dirichlet過程是一種共軛先驗分布，其后驗分布還是Dirichlet過程。Dirichlet過程的常用構(gòu)造方法很多[5-6]，現(xiàn)引用其中的Polya罐子模型[7]構(gòu)造方法。

若一個罐子一共裝了a個球，顏色為k的球最初個數(shù)為ak。現(xiàn)在每隔一段時間隨機從罐子中抽取一個球然后把球放回去，同時再放回一個與取出的顏色相同的球。設第i次從罐子中取出的球顏色為k的概率為P（Xi=k），則

通過不斷重復從給定X1，…，Xn-1條件下抽取Xn的過程來構(gòu)造X1，…，Xn-1的分布，即

易知上述序列是無窮可交換序列。根據(jù)de Finetti定理，構(gòu)造的Dirichlet過程確實存在。因此，以Dirichlet過程為先驗分布的無窮高斯混合模型為

其中G0（μ，Σ）=N（μ；m，B）·W（Σ-1；r，R），這里N表示多元正態(tài)分布，W表示威沙特分布。

2 抽樣算法

下面利用貝葉斯定理和Gibbs抽樣算法給出該模型的抽樣算法。方便起見，先給出一些記號。

令Z(t)表示第t次循環(huán)時觀測數(shù)據(jù)的指示因子，K(t)表示對應的聚類個數(shù)，x-i表示（x1，…，xi-1，xi+1，…，xn）T。若第i個觀測值的指示因子為zi=k，由貝葉斯定理，得

若第i個觀測數(shù)據(jù)的指示因子為zi=k′（一個新類），則有

該模型的Gibbs抽樣算法描述如下。

步驟1：給定初值α(0)，Z(0)，令t=1；

步驟2：將n個觀測值重新進行隨機排序，并把第i個觀測值的新序號記為τi，i=1,…，n；

步驟3：令α(t)=α(t-1)，Z(t)=Z(t-1)，對每一個數(shù)據(jù)i∈{τ1，…，τn}，計算fk（xi）=p（xi│zi=k，X-i，λ）以及fk′（xi）=p（xi│zi=k′，X-i，λ）；

步驟4：對zi按照下面分布進行抽樣：

當zi=k′時，K(t)=K(t)+1；

步驟5：檢查各個類內(nèi)包含的觀測值的個數(shù)，若某一類內(nèi)的觀測數(shù)據(jù)個數(shù)為0，則將該類刪去，且令K(t)=K(t)-1；

步驟6：令t=t+1，重復步驟2至步驟6直至收斂為止。

該方法與文獻[8]的聚類算法類似，但是兩者觀測值所基于的底層模型不一樣。文獻[8]考慮的是具有某種分布的模型，該分布的形式是未指定的，而這里討論的是無限高斯混合模型。由于任意密度函數(shù)f（x）在L1范數(shù)下均收斂于（1）式。因此基于無限高斯混合模型所利用的信息會更多一些，特別是當指定的分布形式與實際分布有偏差時，則基于無限高斯混合模型會更準確一些。

3 統(tǒng)計模擬

為了說明以上方法的優(yōu)良性，下面進行統(tǒng)計模擬來說明該聚類方法的有效性。首先按照下面概率密度隨機生成100個服從高斯混合分布的二維數(shù)據(jù)，總體的概率密度函數(shù)為

其中1=1/4，2=1/2，3=1/4，

因此，可以看出這個數(shù)據(jù)的真實類別共3類。利用上述基于無限高斯混合模型的非參數(shù)貝葉斯Gibbs抽樣算法對該模擬數(shù)據(jù)集進行聚類，且令初始參數(shù)α=2，得出聚類的個數(shù)為3，與傳統(tǒng)的系統(tǒng)聚類法相比，本方法誤判率為17%，不需預先指定類別數(shù)，而傳統(tǒng)的系統(tǒng)聚類法誤判率為31%，需預先指定類別數(shù)。說明非參數(shù)貝葉斯聚類的誤判率更低、更有效，并且能夠有效估計出聚類類別個數(shù)。

[1]MCLACHLANG J,BASFORDK E.MixtureModels:Inference andApp lications to Clustering[M].New York：Marcel Dekker Inc，1988：34-86.

[2]胡慶輝,丁立新,陸玉靖,等.一種快速、魯棒的有限高斯混合模型聚類算法[J].計算機科學，2013，40（8）：191-195.

[3]張林，劉輝.Dirichlet過程混合模型的聚類算法[J].中國礦業(yè)大學學報，2012，41（1）：159-163.

[4]徐謙，周俊生，陳家俊.Dirichlet過程及其在自然語言處理中的應用[J].中文信息學報，2009，23（5）：25-32.

[5]SETHURAMAN R C,TIWARI J.Convergence of Dirichlet measures and the interpretation of their parameter[J].Statistical Decision Theoryand Related Topics，1982，3（2）：305-315.

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

[7]SUDDERTH E B.GraphicalModels for VisualObject Recognition and Tracking[D].Massachusetts:Massachusetts Institute of Technology，2006.

[8]張媛媛.一種基于非參數(shù)貝葉斯模型的聚類算法[J].寧波大學學報（理學版），2013，26（4）：24-28.

Clustering Analysis Based on the Nonparametric Bayes

YANG Ying-Ying
(Foundation Department Chuzhou Vocational and Technical College，Chuzhou，Anhui239000，China)

Dirichlet process is supposed as the prior distribution of the weights parameters based on infinite Gaussian mixturemodel.Bayes theorem is used to deduce the estimators of parameters.The Gibbs sampling algorithm isapplied to obtain the clustering number and the judge indicator factor of the observation data.Finally,we conduct simulation to show that our algorithm can effectively cluster data and our algorithm have lower error rate than the traditional clusteringmethods.

Dirichlet process；Gibbs sampling；clustering analysis

O212.8

A

1007-4260(2016)04-0027-03

時間：2017-1-3 17:19

http://www.cnki.net/kcms/detail/34.1150.N.20170103.1719.008.html

2016-06-04

2015年安徽省教育廳高校自然科學研究項目（KJ2015A345，KJ2015A372），2016年滁州職業(yè)技術學院院級規(guī)劃立項課題（YJZ-2016-01）和2014年安徽省教育廳高校教學研究項目（2014jyxm515）。

楊穎穎，女，安徽濉溪人，碩士，滁州職業(yè)技術學院基礎部講師，研究方向為高職院?！陡叩葦?shù)學》課程教學、數(shù)學文化。

E-mail:yyy20080413@163.com

10.13757/j.cnki.cn34-1150/n.2016.04.008