朴素贝叶斯算法

条件：在观测结果$$yi$$已知的条件下，各个变量间相互独立即$$P(X^{(1)}=x^{(1)},X^{(2)}=x^{(2)}|Y=y_i)=P(X^{(1)}=x^{(1)}|Y=y_i)P(X^{(2)}=x^{(2)}|Y=y_i)$$ 输入:训练数据$$T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}$$,其中$$x_i=(x_i^{(1)},x_i^{(2)},\ldots,x_i^{(n)})$$,$$x_i^{(j)}$$是第i个样本的第j个特征，$$x_i^{(j)}\in{a{j1},a{j2},\ldots,a{jSj}}$$,$$a{jl}$$是第j个特征可能取的第l个值，$$j=1,2,\ldots,n,l=1,2\ldots,S_j,y_i\in{c_1,c_2,\ldots,c_K}$$;实例x。 输出:实例x的分类

• 计算先验概率和条件概率 $$ P(Y=ck)=\frac{\sum{i=1}^NI(yi=c_k)}{N}\quad,k=1,2,\ldots,K\ P(X^{(j)}=a{jl}|Y=ck)=\frac{\sum{i=1}^NI(xi^{(j)}=a{jl},yi=c_k)}{\sum{i=1}^NI(y_i=c_k)}\ j=1,2,\ldots,n;l=1,2,\ldots,S_j;k=1,2,\ldots,K $$
• 对于给定的实例$$x=(x^{(1)},x^{(2)},\ldots,x^{(n)})^T$$计算 $$ P(Y=ck)\prod{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k),\quad k=1,2,\ldots,K $$
• 确定实例x的类 $$ y = argmax{c_k}P(Y=c_k)\prod{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k) $$

贝叶斯估计

为了避免极大似然估计中

$$ P(X^{(j)}=a{jl}|Y=c_k)=\frac{\sum{i=1}^NI(xi^{(j)}=a{jl},yi=c_k)}{\sum{i=1}^NI(y_i=c_k)}\ j=1,2,\ldots,n;l=1,2,\ldots,S_j;k=1,2,\ldots,K

$$ 为0，设定条件概率的贝叶斯估计为

$$ P(X^{(j)}=a{jl}|Y=c_k)=\frac{\sum{i=1}^NI(xi^{(j)}=a{jl},yi=c_k)+\lambda}{\sum{i=1}^NI(y_i=c_k)+S_j\lambda}

$$ 这里的$$\lambda\geq0$$,等价于在随机变量取各个取值的频数上赋予一个正数$$\lambda>0$$,当$$\lambda=0$$时就是级大师然估计。常取$$\lambda=1$$,这是称为拉普拉斯平滑。显然，对任意$$l=1,2,\cdots,S_j,k=1,2,\cdots,K$$有

$$ P{\lambda}(X^{(j)}=a{jl}|Y=ck)>0\ \sum{l=1}^{S_j}P(X^{(j)}|Y=c_k)=1

$$, 先验概率的贝叶斯估计是

$$ P{\lambda}(Y=c_k)=\frac{\sum{i=1}^NI(y_i=c_k)+\lambda}{N+K\lambda} $$