前言
朴素贝叶斯方法通过构造数据生成分布来预测未知数据的类型，属于生成模型。这里之所以称为“朴素”，是因为我们假设数据特征之间具有互相独立的假设。
在这篇博客里，我们将介绍朴素贝叶斯方法，并对其进行推导，最后给出python3的实现代码。
1. 朴素贝叶斯方法
记数据集为 T={(x1,y1),(x2,y2),...,(xN,yN)}T=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}T={(x1,y1),(x2,y2),...,(xN,yN)}，其中，xi∈Rnx_i\in\mathbb{R}^nxi∈Rn，yi∈{c1,c2,...,ck}y_i\in\{c_1, c_2, ..., c_k\}yi∈{c1,c2,...,ck}。
我们假设数据按照分布 P(X,Y)P(X, Y)P(X,Y) 独立同分布生成。这是容易理解的，类似于做 NNN 次抛硬币实验，我们假设单次抛硬币的分布为P(X)P(X)P(X)，实验结果同样是独立同分布的。
朴素贝叶斯方法可以简述如下：
输入：数据集 T={(x1,y1),(x2,y2),...,(xN,yN)}T=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}T={(x1,y1),(x2,y2),...,(xN,yN)}；新数据 xN+1x_{N+1}xN+1输出：新数据 xN+1x_{N+1}xN+1 的标记 yN+1y_{N+1}yN+1，其中，yN+1=arg maxc∈{c1,c2,...,ck}P(Y=c∣X=xN+1)y_{N+1}=\argmax\limits_{c\in\{c_1, c_2, ..., c_k\}}P(Y=c|X=x_{N+1})yN+1=c∈{c1,c2,...,ck}argmaxP(Y=c∣X=xN+1)
上面的 yN+1y_{N+1}yN+1 输出表达式可以这样理解：在给定数据 xN+1x_{N+1}xN+1 的情况下，每一种标记都有可能，我们选择概率最大的标记作为 xN+1x_{N+1}xN+1 的标记。
这样的决策遍布于生活之中。 比如，一个人35岁单身，我们有两种猜测，这个人过于优秀，或者这个人没有吸引力。我们选择概率最大的那个，也就是 P(过于优秀∣35岁单身)<P(没有吸引力∣35岁单身)P(过于优秀|35岁单身)<P(没有吸引力|35岁单身)P(过于优秀∣35岁单身)<P(没有吸引力∣35岁单身)。所以，我们基本做出结论，35岁单身是因为自身不够有吸引力~
我们可以接着对上面的输出表达式分析一下，看看我们需要什么：
yN+1=arg maxc∈{c1,c2,...,ck}P(Y=c∣X=xN+1)=arg maxc∈{c1,c2,...,ck}P(Y=c,X=xN+1)P(X=xN+1)=arg maxc∈{c1,c2,...,ck}P(Y=c,X=xN+1)∑c∈{c1,c2,...,ck}P(X=xN+1∣Y=c)P(Y=c)=arg maxc∈{c1,c2,...,ck}P(Y=c,X=xN+1)=arg maxc∈{c1,c2,...,ck}P(X=xN+1∣Y=c)P(Y=c)=arg maxc∈{c1,c2,...,ck}P(Y=c)Πi=1nP(X(i)=xN+1(i)∣Y=c)\begin{array}{lll} y_{N+1}&=&\argmax\limits_{c\in\{c_1, c_2, ..., c_k\}}P(Y=c|X=x_{N+1})\\ &=&\argmax\limits_{c\in\{c_1, c_2, ..., c_k\}}\frac{P(Y=c, X=x_{N+1})}{P(X=x_{N+1})}\\ &=&\argmax\limits_{c\in\{c_1, c_2, ..., c_k\}}\frac{P(Y=c, X=x_{N+1})}{\sum_{c\in\{c_1, c_2, ..., c_k\}}P(X=x_{N+1}|Y=c)P(Y=c)}\\ &=&\argmax\limits_{c\in\{c_1, c_2, ..., c_k\}}P(Y=c, X=x_{N+1})\\ &=&\argmax\limits_{c\in\{c_1, c_2, ..., c_k\}}P(X=x_{N+1}|Y=c)P(Y=c)\\ &=&\argmax\limits_{c\in\{c_1, c_2, ..., c_k\}}P(Y=c)\Pi_{i=1}^nP(X^{(i)}=x_{N+1}^{(i)}|Y=c) \end{array} yN+1======c∈{c1,c2,...,ck}argmaxP(Y=c∣X=xN+1)c∈{c1,c2,...,ck}argmaxP(X=xN+1)P(Y=c,X=xN+1)c∈{c1,c2,...,ck}argmax∑c∈{c1,c2,...,ck}P(X=xN+1∣Y=c)P(Y=c)P(Y=c,X=xN+1)c∈{c1,c2,...,ck}argmaxP(Y=c,X=xN+1)c∈{c1,c2,...,ck}argmaxP(X=xN+1∣Y=c)P(Y=c)c∈{c1,c2,...,ck}argmaxP(Y=c)Πi=1nP(X(i)=xN+1(i)∣Y=c)
说明：
第二个和第三个等号是从贝叶斯公式直接得到；第三个等号并不需要，只是一般都会写出来，可以直接忽略第四个等号可以从第二个等号直接得到，这是由于第二个等号的分母部分与变量 ccc 无关，所以不影响决策第五个等号同样可以由贝叶斯公式得到第六个等号则由特征之前互相独立假设得到
从上面公式可以知道，为了得到 yN+1y_{N+1}yN+1，我们需要知道
先验概率 P(Y=c)P(Y=c)P(Y=c)条件概率 P(X(i)=xN+1(i)∣Y=c)P(X^{(i)}=x_{N+1}^{(i)}|Y=c)P(X(i)=xN+1(i)∣Y=c)
下面，我们将用极大似然估计得到上述两个概率。
1.1 先验概率 P(Y=c)P(Y=c)P(Y=c)
记 njn_jnj 为 cjc_jcj 在数据集 {y1,y2,...,yN}\{y_1, y_2, ..., y_N\}{y1,y2,...,yN} 中出现的次数。设 pj=P(Y=cj)p_j=P(Y=c_j)pj=P(Y=cj)，则似然函数
L(pj)=log(pjnj⋅(1−pj)N−nj)=nj⋅logpj+(N−nj)⋅log(1−pj)\begin{array}{lll} L(p_j)&=&log(p_j^{n_{j}}\cdot (1-p_j)^{N-n_j})\\ &=& n_j\cdot logp_j+(N-n_j)\cdot log(1-p_j) \end{array} L(pj)==log(pjnj⋅(1−pj)N−nj)nj⋅logpj+(N−nj)⋅log(1−pj)
对似然函数 L(pj)L(p_j)L(pj) 求导，有
∂L(pj)∂pj=njpj−N−nj1−pj\frac{\partial L(p_j)}{\partial p_j}=\frac{n_j}{p_j}-\frac{N-n_j}{1-p_j} ∂pj∂L(pj)=pjnj−1−pjN−nj
令 ∂L(pj)∂pj=0\frac{\partial L(p_j)}{\partial p_j}=0∂pj∂L(pj)=0，有
pj=njN=∑i=1NI(yi=cj)N\begin{array}{lll} p_j&=&\frac{n_j}{N}\\ &=&\frac{\sum_{i=1}^N I(y_i=c_j)}{N} \end{array} pj==NnjN∑i=1NI(yi=cj)
因此，我们有 P(Y=c)=∑i=1NI(yi=c)NP(Y=c)=\frac{\sum_{i=1}^N I(y_i=c)}{N}P(Y=c)=N∑i=1NI(yi=c)
1.2 条件概率 P(X(i)=xN+1(i)∣Y=c)P(X^{(i)}=x_{N+1}^{(i)}|Y=c)P(X(i)=xN+1(i)∣Y=c)
记数据 xxx 的第i维数值 x(i)x^{(i)}x(i) 有 sis_isi 个不同取值 {x(i1),x(i2),...,x(isi)}\{x^{(i1)}, x^{(i2)}, ..., x^{(is_i)}\}{x(i1),x(i2),...,x(isi)}。取数据集 TTT 的子集 Tk={(x,y)∈T∣y=ck}T_k=\{(x, y)\in T|y=c_k\}Tk={(x,y)∈T∣y=ck}，设 njn_jnj 为 x(ij)x^{(ij)}x(ij) 在数据集 {x(i)∣(x,y)∈Tk}\{x^{(i)}|(x, y)\in T_k\}{x(i)∣(x,y)∈Tk} 中出现的次数。
进一步的，设 pj=P(X(i)=x(ij)∣Y=ck)p_j=P(X^{(i)}=x^{(ij)}|Y=c_k)pj=P(X(i)=x(ij)∣Y=ck)。与先验概率的极大似然估计一样，我们可以得到
pj=nj∣{x(i)∣(x,y)∈Tk}∣=∑l=1NI(xl(i)=x(ij),yl=ck)∑i=1NI(yi=ck)\begin{array}{lll} p_j&=&\frac{n_j}{|\{x^{(i)}|(x, y)\in T_k\}|}\\ &=&\frac{\sum_{l=1}^NI(x_l^{(i)}=x^{(ij)}, y_l=c_k)}{\sum_{i=1}^NI(y_i=c_k)} \end{array} pj==∣{x(i)∣(x,y)∈Tk}∣nj∑i=1NI(yi=ck)∑l=1NI(xl(i)=x(ij),yl=ck)
所以，我们有 P(X(i)=x(ij)∣Y=ck)=∑l=1NI(xl(i)=x(ij),yl=ck)∑i=1NI(yi=ck)P(X^{(i)}=x^{(ij)}|Y=c_k)=\frac{\sum_{l=1}^NI(x_l^{(i)}=x^{(ij)}, y_l=c_k)}{\sum_{i=1}^NI(y_i=c_k)}P(X(i)=x(ij)∣Y=ck)=∑i=1NI(yi=ck)∑l=1NI(xl(i)=x(ij),yl=ck)
也即意味着 P(X(i)=xN+1(i)∣Y=c)=∑l=1NI(xl(i)=xN+1(i),yl=c)∑i=1NI(yi=c)P(X^{(i)}=x_{N+1}^{(i)}|Y=c)=\frac{\sum_{l=1}^NI(x_l^{(i)}=x_{N+1}^{(i)}, y_l=c)}{\sum_{i=1}^NI(y_i=c)}P(X(i)=xN+1(i)∣Y=c)=∑i=1NI(yi=c)∑l=1NI(xl(i)=xN+1(i),yl=c)
1.3 朴素贝叶斯算法
将先验概率和条件概率代入 yN+1y_{N+1}yN+1 表达式中，得到
yN+1=arg maxc∈{c1,c2,...,ck}∑i=1NI(yi=c)N⋅Πi=1n∑l=1NI(xl(i)=xN+1(i),yl=c)∑l=1NI(yl=c)y_{N+1}=\argmax\limits_{c\in\{c_1, c_2, ..., c_k\}}\frac{\sum_{i=1}^N I(y_i=c)}{N}\cdot \Pi_{i=1}^n\frac{\sum_{l=1}^NI(x_l^{(i)}=x_{N+1}^{(i)}, y_l=c)}{\sum_{l=1}^NI(y_l=c)}yN+1=c∈{c1,c2,...,ck}argmaxN∑i=1NI(yi=c)⋅Πi=1n∑l=1NI(yl=c)∑l=1NI(xl(i)=xN+1(i),yl=c)
综合上面讨论，我们有如下的朴素贝叶斯算法（见《统计学习方法》第二版 p62）。
输入：数据集 T={(x1,y1),(x2,y2),...,(xN,yN)}T=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}T={(x1,y1),(x2,y2),...,(xN,yN)}，其中，xi=(xi(1),xi(2),...,xi(n))x_i=(x_i^{(1)}, x_i^{(2)}, ..., x_i^{(n)})xi=(xi(1),xi(2),...,xi(n))，xi(j)x_i^{(j)}xi(j)是xix_ixi的第jjj个特征， xi(j)∈{aj1,aj2,...,ajSj}x_i^{(j)}\in\{a_{j1}, a_{j2}, ..., a_{jS_j}\}xi(j)∈{aj1,aj2,...,ajSj}，yi∈{c1,c2,...,cK}y_i\in\{c_1, c_2, ..., c_K\}yi∈{c1,c2,...,cK}；实例 xxx输出：实例 xxx 的分类 yyy
(1) 先验概率及条件概率
P(Y=ck)=∑i=1NI(yi=ck)NP(Y=c_k)=\frac{\sum_{i=1}^NI(y_i=c_k)}{N}P(Y=ck)=N∑i=1NI(yi=ck)
P(X(j)=ajl∣Y=ck)=∑i=1NI(xi(j)=ajl,yi=ck)∑i=1NI(yi=ck)P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^NI(x_i^{(j)}=a_{jl}, y_i=c_k)}{\sum_{i=1}^NI(y_i=c_k)}P(X(j)=ajl∣Y=ck)=∑i=1NI(yi=ck)∑i=1NI(xi(j)=ajl,yi=ck)
(2) 对于给定的 x=(x(1),x(2),...,x(n))x=(x^{(1)}, x^{(2)}, ..., x^{(n)})x=(x(1),x(2),...,x(n))，计算
P(Y=ck)Πj=1nP(X(j)=x(j)∣Y=ck)P(Y=c_k)\Pi_{j=1}^{n} P(X^{(j)}=x^{(j)}|Y=c_k)P(Y=ck)Πj=1nP(X(j)=x(j)∣Y=ck)
(3) 确定实例 xxx 的类
y=arg maxckP(Y=ck)Πj=1nP(X(j)=x(j)∣Y=ck)y=\argmax_{c_k}P(Y=c_k)\Pi_{j=1}^{n} P(X^{(j)}=x^{(j)}|Y=c_k)y=ckargmaxP(Y=ck)Πj=1nP(X(j)=x(j)∣Y=ck)
2. 后验概率最大化与期望损失最小化
我们证明，期望损失最小化实际上与后验概率最大化等价。
设损失函数为0-1损失函数，即，
L(Y,f(X))={1ifY≠f(X)0ifY=f(X)L(Y, f(X))=\left\{ \begin{array}{lll} 1 &if& Y\neq f(X)\\ 0 &if& Y= f(X) \end{array}\right. L(Y,f(X))={10ififY=f(X)Y=f(X)
则期望损失函数为
Rexp(f)=EX×Y[L(Y,f(X))]=EX[∑k=1KL(ck,f(X))P(Y=ck∣X)]\begin{array}{lll} R_{exp}(f)&=&E_{X\times Y}[L(Y,f(X))]\\ &=&E_X[\sum_{k=1}^KL(c_k,f(X))P(Y=c_k|X)] \end{array} Rexp(f)==EX×Y[L(Y,f(X))]EX[∑k=1KL(ck,f(X))P(Y=ck∣X)]
我们希望选择一个 fff，使得 Rexp(f)R_{exp}(f)Rexp(f) 最小，也就是
f(⋅)=arg minfRexp(f)=arg minfEX[∑k=1KL(ck,f(X))P(Y=ck∣X)]=arg minfEX[R(X,f(X))]=arg minf∑x∈Range(X)R(x,f(x))P(X=x)\begin{array}{lll} f(\cdot) &=& \argmin_{f} R_{exp}(f)\\ &=& \argmin_{f} E_X[\sum_{k=1}^KL(c_k,f(X))P(Y=c_k|X)]\\ &=& \argmin_{f} E_X[R(X, f(X))]\\ &=& \argmin_{f} \sum_{x\in Range(X)} R(x, f(x))P(X=x) \end{array} f(⋅)====fargminRexp(f)fargminEX[∑k=1KL(ck,f(X))P(Y=ck∣X)]fargminEX[R(X,f(X))]fargmin∑x∈Range(X)R(x,f(x))P(X=x)
其中， R(X,f(X))=∑k=1KL(ck,f(X))P(Y=ck∣X)]R(X, f(X))=\sum_{k=1}^KL(c_k,f(X))P(Y=c_k|X)]R(X,f(X))=∑k=1KL(ck,f(X))P(Y=ck∣X)]。
显然，上式中 ∑x∈Range(X)R(x,f(x))P(X=x)\sum_{x\in Range(X)} R(x, f(x))P(X=x)∑x∈Range(X)R(x,f(x))P(X=x) 是函数 R(x,f(x)),x∈Range(X)R(x, f(x)), x\in Range(X)R(x,f(x)),x∈Range(X) 的一个线性组合。我们只需要让R(x,f(x))R(x, f(x))R(x,f(x))最小，就能确保它关于 xxx 的线性组合最小。
所以，接下来的问题就是，如何在给定 xxx 的情况下，求得 R(x,f(x))R(x, f(x))R(x,f(x)) 的最小值。其实观察这个式子，可以知道，只有 f(x)f(x)f(x) 这个数值（注意，不是函数）是未知的，所以我们可以选择 y=f(x)y=f(x)y=f(x)，使得 R(x,y)R(x, y)R(x,y) 最小。对于每一个 xxx，我们都求出这样的 yyy，这样，我们将这样的 xxx 和 yyy 的映射，记做函数 fff，也就是， f(x)=yf(x)=yf(x)=y。
对于给定 xxx，我们有
f(x)=arg miny∈Range(Y)∑k=1KL(ck,y)P(Y=ck∣X=x)=arg miny∈Range(Y)P(Y≠y∣X=x)=arg miny∈Range(Y)(1−P(Y=y∣X=x))=arg maxy∈Range(Y)P(Y=y∣X=x)=arg maxck∈Range(Y)P(Y=ck∣X=x)\begin{array}{lll} f(x)&=&\argmin_{y\in Range(Y)}\sum_{k=1}^KL(c_k,y)P(Y=c_k|X=x)\\ &=&\argmin_{y\in Range(Y)}P(Y\neq y|X=x)\\ &=&\argmin_{y\in Range(Y)} \left(1-P(Y= y|X=x) \right)\\ &=&\argmax_{y\in Range(Y)} P(Y= y|X=x) \\ &=& \argmax_{c_k\in Range(Y)} P(Y= c_k|X=x) \\ \end{array} f(x)=====y∈Range(Y)argmin∑k=1KL(ck,y)P(Y=ck∣X=x)y∈Range(Y)argminP(Y=y∣X=x)y∈Range(Y)argmin(1−P(Y=y∣X=x))y∈Range(Y)argmaxP(Y=y∣X=x)ck∈Range(Y)argmaxP(Y=ck∣X=x)
证毕。
在下一篇博客中，我们将介绍python3实现。
