贝叶斯聚类算法
贝叶斯聚类算法
贝叶斯方法的基本思想是：假定对所研究的对象在抽样前已有一定的认识，常用先验分布来描述这种认识，然后基于抽取的样本再对先验认识作修正，得到后验分布，而各种统计推断都基于后验分布进行。一般都将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)]
( 12 )
由于对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步将其合并为一个类即可，综合上的讨论，我们可以给出形式化的算法如下（见图）