貝葉斯聚類算法

貝葉斯方法的基本思想是：假定對所研究的對象在抽樣前已有一定的認識，常用先驗分布來描述這種認識，然後基於抽取的樣本再對先驗認識作修正，得到後驗分布，而各種統計推斷都基於後驗分布進行。一般都將bayes用於分類，在此介紹貝葉斯方法在層次聚類上的使用。 　　套用方法是，每一步中都選擇兩個類別合併為一個類別，選擇的依據是使合併後分類方案的後驗機率P(C|D)最大，即每一步進行局部最佳化的目標函式為P(C|D),其中D是個體的集合D = d1,d2,...,dn，分類方案C表示類別的集合，是對D的一個劃分：C = c1,c2,...,cm，ci是D的子集，ci∩cj= ∅，對任意i，j都成立。 　　在初始階段，每個個體被看作一個獨立的類別，即ci=di,1≤i≤n，此時的分類方案為C_0。假設現在已經完成第k步，其分類方案是C_k，我們需要為k+1步選擇最優的聚類方案C_k+1的關鍵是選擇合適的兩個類別cx,cy進行合併。

貝葉斯方法的基本思想是：假定對所研究的對象在抽樣前已有一定的認識，常用先驗分布來描述這種認識，然後基於抽取的樣本再對先驗認識作修正，得到後驗分布，而各種統計推斷都基於後驗分布進行。一般都將bayes用於分類，在此介紹貝葉斯方法在層次聚類上的使用。
套用方法是，每一步中都選擇兩個類別合併為一個類別，選擇的依據是使合併後分類方案的後驗機率P(C|D)最大，即每一步進行局部最佳化的目標函式為P(C|D),其中D是個體的集合D = {d1,d2,...,dn}，分類方案C表示類別的集合，是對D的一個劃分：C = {c1,c2,...,cm}，ci是D的子集，ci∩cj= ∅，對任意i，j都成立。
在初始階段，每個個體被看作一個獨立的類別，即ci={di},1≤i≤n，此時的分類方案為C_0。假設現在已經完成第k步，其分類方案是C_k，我們需要為k+1步選擇最優的聚類方案C_k+1的關鍵是選擇合適的兩個類別cx,cy進行合併。
其中
P(C_k|D) = ∏∏P(c|d), 對c∈C, d∈c
= ∏∏[P(d|c)*P(c)/P(d)],
...
= PC(C)∏SC(c)/P(D)
其中 PC(C)=∏P(c)^|c|, 對c∈C,
SC(c)=∏P(d|c), 對d∈c
C_k和C_k+1之間顯然有C_k+1 = C_k-{cx,cy}+{cx∪cy}，於是：
P(C_k+1|D)/P(C_k|D)
= [PC(C_k+1)/PC(C_k)]*[SC(cx∪cy)/SC(cx)/SC(cy)]
( 1‑2 )
由於對k+1步而言，P(C_k|D)是已知常數，我們無須直接計算P(C_k+1|D)，就可以找到最佳的cx, cy。上式中第一項採用近似估計值PC(C_k+1)/PC(C_k)] ~ A^(-1), A>1是一個常數。
至此我們只要選擇最大化P(C_k+1|D)/P(C_k|D)的兩個類別，在第k+1步將其合併為一個類即可，綜合上的討論，我們可以給出形式化的算法如下（見圖）

algorithm