【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.朴素贝叶斯分类器
基于贝叶斯公式：
\[P(c\mid \mathbf x)=\frac{P(c)P(\mathbf x \mid c)}{P(\mathbf x)} \tag{1}\]来估计后验概率$P(c \mid \mathbf x)$的主要困难在于：类条件概率$P(\mathbf x \mid c)$是所有属性上的联合概率，难以从有限的训练样本直接估计而得。为避开这个障碍，朴素贝叶斯分类器（naive Bayes classifier）采用了“属性条件独立性假设”（attribute conditional independence assumption）：对已知类别，假设所有属性相互独立。换言之，假设每个属性独立地对分类结果发生影响。
基于有限训练样本直接估计联合概率，在计算上将会遭遇组合爆炸问题，在数据上将会遭遇样本稀疏问题；属性数越多，问题越严重。
基于属性条件独立性假设，式(1)可重写为：
\[P(c\mid \mathbf x)=\frac{P(c)P(\mathbf x \mid c)}{P(\mathbf x)} = \frac{P(c)}{P(\mathbf x)} \prod ^d_{i=1} P(x_i \mid c) \tag{2}\]其中$d$为属性数目，$x_i$为$\mathbf x$在第$i$个属性上的取值。
由于对所有类别来说$P(\mathbf x)$相同，基于贝叶斯判定准则有：
\[h_{nb}(\mathbf x)=\mathop{\arg\max}_{c \in \mathcal{Y}} P(c) \prod ^d_{i=1} P(x_i \mid c) \tag{3}\]这就是朴素贝叶斯分类器的表达式。
显然，朴素贝叶斯分类器的训练过程就是基于训练集$D$来估计类先验概率$P(c)$，并为每个属性估计条件概率$P(x_i \mid c)$。
令$D_c$表示训练集$D$中第$c$类样本组成的集合，若有充足的独立同分布样本，则可容易地估计出类先验概率：
\[P(c)=\frac{\lvert D_c \rvert}{\lvert D \rvert} \tag{4}\]对离散属性而言，令$D_{c,x_i}$表示$D_c$中在第$i$个属性上取值为$x_i$的样本组成的集合，则条件概率$P(x_i \mid c)$可估计为：
\[P(x_i \mid c)=\frac{\lvert D_{c,x_i} \rvert}{\lvert D_c \rvert} \tag{5}\]对连续属性可考虑概率密度函数，假定$p(x_i \mid c) \sim \mathcal{N}(\mu_{c,i} , \sigma ^2_{c,i})$，其中$\mu_{c,i}$和$\sigma ^2_{c,i}$分别是第$c$类样本在第$i$个属性上取值的均值和方差，则有：
\[p(x_i \mid c)=\frac{1}{\sqrt{2\pi} \sigma_{c,i} } exp \left(- \frac{(x_i-\mu_{c,i})^2}{2\sigma^2_{c,i}} \right) \tag{6}\]下面我们用以下西瓜数据集训练一个朴素贝叶斯分类器：
对测试例“测试1”进行分类：
首先估计类先验概率$P(c)$，显然有：
\[P(好瓜=是)=\frac{8}{17} \approx 0.471\] \[P(好瓜=否)=\frac{9}{17} \approx 0.529\]然后，为每个属性估计条件概率$P(x_i \mid c)$：
\[P_{青绿 \mid 是}=P(色泽=青绿 \mid 好瓜=是)=\frac{3}{8}=0.375\] \[P_{青绿 \mid 否}=P(色泽=青绿 \mid 好瓜=否)=\frac{3}{9} \approx 0.333\] \[P_{蜷缩 \mid 是}=P(根蒂=蜷缩 \mid 好瓜=是)=\frac{5}{8} = 0.625\] \[P_{蜷缩 \mid 否}=P(根蒂=蜷缩 \mid 好瓜=否)=\frac{3}{9} \approx 0.333\] \[P_{浊响 \mid 是}=P(敲声=浊响 \mid 好瓜=是)=\frac{6}{8} = 0.750\] \[P_{浊响 \mid 否}=P(敲声=浊响 \mid 好瓜=否)=\frac{4}{9} \approx 0.444\] \[P_{清晰\mid 是}=P(纹理=清晰 \mid 好瓜=是)=\frac{7}{8} = 0.875\] \[P_{清晰\mid 否}=P(纹理=清晰 \mid 好瓜=否)=\frac{2}{9} \approx 0.222\] \[P_{凹陷\mid 是}=P(脐部=凹陷 \mid 好瓜=是)=\frac{6}{8} = 0.750\] \[P_{凹陷\mid 否}=P(脐部=凹陷 \mid 好瓜=否)=\frac{2}{9} \approx 0.222\] \[P_{硬滑\mid 是}=P(触感=硬滑 \mid 好瓜=是)=\frac{6}{8} = 0.750\] \[P_{硬滑\mid 否}=P(触感=硬滑 \mid 好瓜=否)=\frac{6}{9} \approx 0.667\] \[P_{密度:0.697 \mid 是}=p(密度=0.697 \mid 好瓜=是)=\frac{1}{\sqrt{2\pi} \cdot 0.129} exp \left( -\frac{(0.697-0.574)^2}{2\cdot 0.129^2} \right) \approx 1.959\] \[P_{密度:0.697 \mid 否}=p(密度=0.697 \mid 好瓜=否)=\frac{1}{\sqrt{2\pi} \cdot 0.195} exp \left( -\frac{(0.697-0.496)^2}{2\cdot 0.195^2} \right) \approx 1.203\] \[P_{含糖:0.460 \mid 是}=p(含糖率=0.460 \mid 好瓜=是)=\frac{1}{\sqrt{2\pi} \cdot 0.101} exp \left( -\frac{(0.460-0.279)^2}{2\cdot 0.101^2} \right) \approx 0.788\] \[P_{含糖:0.460 \mid 否}=p(含糖率=0.460 \mid 好瓜=否)=\frac{1}{\sqrt{2\pi} \cdot 0.108} exp \left( -\frac{(0.460-0.154)^2}{2\cdot 0.108^2} \right) \approx 0.066\]注意，当样本数目足够多时才能进行有意义的概率估计。这里的西瓜数据集只是一个简单的演示。
于是，有：
\[P(好瓜=是) \times P_{青绿 \mid 是} \times P_{蜷缩 \mid 是} \times P_{浊响 \mid 是} \times P_{清晰 \mid 是} \times P_{凹陷 \mid 是} \times P_{硬滑 \mid 是} \times p_{密度:0.697\mid 是} \times p_{含糖:0.460\mid 是} \approx 0.038\] \[P(好瓜=否) \times P_{青绿 \mid 否} \times P_{蜷缩 \mid 否} \times P_{浊响 \mid 否} \times P_{清晰 \mid 否} \times P_{凹陷 \mid 否} \times P_{硬滑 \mid 否} \times p_{密度:0.697\mid 否} \times p_{含糖:0.460\mid 否} \approx 6.80 \times 10^{-5}\]实践中常通过取对数的方式来将“连乘”转化为“连加”以避免数值下溢。
由于$0.038>6.80 \times 10^{-5}$，因此，朴素贝叶斯分类器将测试样本“测1”判别为“好瓜”。
需注意，若某个属性值在训练集中没有与某个类同时出现过，则直接基于式(5)进行概率估计，再根据式(3)进行判别将出现问题。例如，在使用西瓜数据集训练朴素贝叶斯分类器时，对一个“敲声=清脆”的测试例，有：
\[P_{清脆\mid 是}=P(敲声=清脆\mid 好瓜=是)=\frac{0}{8}=0\]由于式(3)的连乘式计算出的概率值为零，因此，无论该样本的其他属性是什么，哪怕在其他属性上明显像好瓜，分类的结果都将是“好瓜=否”，这显然不太合理。
为了避免其他属性携带的信息被训练集中未出现的属性值“抹去”，在估计概率值时通常要进行“平滑”（smoothing），常用“拉普拉斯修正”（Laplacian correction）。具体来说，令$N$表示训练集$D$中可能的类别数，$N_i$表示第$i$个属性可能的取值数，则式(4)和(5)分别修正为：
\[\hat {P} (c)=\frac{\lvert D_c \rvert +1}{\lvert D \rvert +N} \tag{7}\] \[\hat {P} (x_i \mid c)=\frac{\lvert D_{c,x_i} \rvert +1}{\lvert D_c \rvert +N_i} \tag{8}\]例如，在本文的例子中，类先验概率可估计为：
\[\hat {P} (好瓜=是)=\frac{8+1}{17+2} \approx 0.474, \hat {P} (好瓜=否) =\frac{9+1}{17+2} \approx 0.526\]类似地，$P_{青绿 \mid 是}$和$P_{青绿 \mid 否}$可估计为：
\[\hat {P}_{青绿 \mid 是}=\hat {P} (色泽=青绿 \mid 好瓜=是)=\frac{3+1}{8+3} \approx 0.364\] \[\hat {P}_{青绿 \mid 否}=\hat {P} (色泽=青绿 \mid 好瓜=否)=\frac{3+1}{9+3} \approx 0.333\]同时，上文提到的概率$P_{清脆\mid 是}$可估计为：
\[\hat {P}_{清脆\mid 是}=\hat {P} (敲声=清脆 \mid 好瓜=是)=\frac{0+1}{8+3} \approx 0.091\]显然，拉普拉斯修正避免了因训练集样本不充分而导致概率估值为零的问题，并且在训练集变大时，修正过程所引入的先验（prior）的影响也会逐渐变得可忽略，使得估值逐渐趋向于实际概率值。
在现实任务中朴素贝叶斯分类器有多种使用方式。例如，若任务对预测速度要求较高，则对给定训练集，可将朴素贝叶斯分类器涉及的所有概率估值事先计算好存储起来，这样在进行预测时只需“查表”即可进行判别；若任务数据更替频繁，则可采用“懒惰学习”（lazy learning）方式，先不进行任何训练，待收到预测请求时再根据当前数据集进行概率估值；若数据不断增加，则可在现有估值基础上，仅对新增样本的属性值所涉及的概率估值进行计数修正即可实现增量学习。
