【机器学习】算法原理详细推导与实现(三):朴素贝叶斯

【机器学习】算法原理详细推导与实现(三):朴素贝叶斯

【机器学习】算法原理详细推导与实现(三):朴素贝叶斯

在上一篇算法中，逻辑回归作为一种二分类的分类器，一般的回归模型也是是判别模型，也就根据特征值来求结果概率。形式化表示为 \(p(y|x;\theta)\)，在参数 \(\theta\) 确定的情况下，求解条件概率 \(p(y|x)\) 。通俗的解释为：在给定特定特征后预测结果出现的概率。逻辑回归的 \(y\) 是离散型，取值为 \(\{0,1\}\) 。这里将要介绍另一个分类算法 朴素贝叶斯，用以解决 \(x\)

贝叶斯定理

定理推导

朴素贝叶斯是基于贝叶斯原理得到的。假设A和B为两个不相互独立的事件：

由上图可以看出，在事件B已经发生的情况下，事件A发生的概率为事件A和事件B的交集除以事件B：

\[p(A|B)=\frac{p(A\bigcap B)}{p(B)} \]

同理，在事件A已经发生的情况下，事件B发生的概率为事件A和事件B的交集除以事件A：

\[p(B|A)=\frac{p(B\bigcap A)}{p(A)} \]

结合这两个方程式，我们可以得到：

\[p(A|B)p(B)=p(A\bigcap B)=p(B|A)p(A) \]

转换后贝叶斯定理的公式定义为：

\[P(A|B) = \frac{P(B|A)P(A)}{P(B)} \]

总的来说，贝叶斯定理可以总结为：

贝叶斯定理是将先验概率做一次更新，得到后验概率朴素贝叶斯是输入先验概率，找到后验概率，最后找到最大后验概率，作为最终的分类结果，以及分类概率

实际问题

假设我们有两个装满了饼干的碗，第一个碗里有10个巧克力饼干和30个普通饼干，第二个碗里两种饼干都有20个。我们随机挑一个碗，再在碗里随机挑饼干。那么我们挑到的普通饼干来自一号碗的概率有多少？

解决方案

我们用 x1 代表一号碗，x2 代表二号碗。在x1中取到普通饼干的概率是 \(P(y|x1)=\frac{30}{10+30}\)，抽到x1的概率是 \(P(x1)=\frac{1}{2}\) ，再在x1中抽到普通饼干的概率是 \(\frac{30}{10+30}=\frac{3}{4}\) 。同理可得 \(P(y|x2)=\frac{20}{20+20}\) ，抽到x2的概率是 \(P(x2)=\frac{1}{2}\)。而问题中挑到挑到的普通饼干来自一号碗，已知挑到普通饼干，那么这个普通饼干来自一号碗的概率为：

\[P(x1|y) = \frac{P(y|x1)P(x1)}{P(y)} \]

根据 全概率公式 可知，其中拿到普通饼干的概率为： \(P(y)=P(y|x1)P(x1)+ P(y|x2)P(x2)\)

计算为：

\[\begin{split} P(x1|y)&=\frac{P(y|x1)P(x1)}{P(y)} \\ &=\frac{P(y|x1)P(x1)}{P(y|x1)P(x1)+ P(y|x2)P(x2)} \\ &= \frac{0.75\times0.5}{0.75\times0.5+0.5\times0.5} \\ &=0.6 \end{split} \]

朴素贝叶斯

例如如果想实现一个垃圾邮件分类器，用邮件作为输入，确定邮件是否为垃圾邮件作为输出，即 \(y\in \{0,1\}\)，1表示是垃圾邮件0表示不是垃圾邮件，那么问题来了：给你一封邮件，怎么将邮件转化为特征向量 \(\vec x\)。

电子邮件仅仅是一段文本，就像是一个词列表，因此利用词来构建特征向量 \(\vec x\)

假设邮件中存在字典中的词，那么特征向量 \(\vec x\) 就就记为1，不存在就记为0。例如邮件中假设存在词 \([word_1,word_2,...,word_n]\) ，则该邮件的特征向量 \(\vec x\)

\[x= \begin{bmatrix} 1 \\ 1 \\ 0 \\ ... \\ 1 \end{bmatrix} \]

则 $x\in {0,1}^n $ ，假设词典的长度为50000，那么 \(x\) 就可能有 \(2^{50000}\) 种向量。如果需要简历多项式用回归模型进行建模分类，那么可能需要 \(2^{50000-1}\) 个参数 \(\theta\)，很明显看出需要的参数太多了，如果使用梯度下降那么收敛将会非常慢，因此利用朴素贝叶斯算法是一个很好的选择。

算法推导

在朴素贝叶斯算法中，我们会对 \(p(x|y)\) 做一个假设，假设给定 \(y\) 的时候，其中\(x \in \{0,1\}^{50000}\)， \(x_i\)

\[\begin{split} p(x_1,x_2,...,x_{50000}|y)&=p(x_1|y)p(x_1|y,x_1)p(x_2|y,x_1,x_2)...p(x_{50000}|y,x_1,x_2,...,x_{49999}) \\ &=p(x_1|y)p(x_2|y)...p(x_{50000}|y) \\ &=\prod_{i=1}^n p(x_i|y) \end{split} \]

为了拟合出模型的参数，符号假设为，其中 \(y=1\) 是垃圾邮件， \(y=0\)

\[\phi_{i|y=1}=p(x_i=1|y=1) \\ \phi_{i|y=0}=p(x_i=1|y=0) \\ \phi_y=p(y=1) \]

假设存在 \(m\) 个样本，那么 \(y=1\) 和 \(y=0\)

\[L(\phi_y,\phi_{i|y=0},\phi_{i|y=1})=\prod_{i=1}^m p(x^{(i)}|y^{(i)}) \]

假设训练样本为 \(m\) 封邮件，\(x_j=1\)表示包含关键词 \(j\)，\(x_j=0\)表示不包含关键词 \(j\)，则垃圾邮件 \(y=1\) 里面包含的单词 \(j\)

\[\phi_{j|y=1}=\frac{\sum_{i=1}^ml\{x_j^{(i)}\bigcap y^{(i)}=1\}}{\sum_{i=1}^ml\{y^{(i)}=1\}} \]

上述公式中，分子的含义是从 1到 \(m\) 遍历垃圾邮件内容，对于标签\(x_j=1\)的邮件计算其中词语 \(j\) 出现的邮件数目之和。换句话说就是，遍历所有垃圾邮件，统计这些垃圾邮件中包含词语 \(j\) 的邮件数目。分母是对 \(i\) 从1到 \(m\)

同理，正常邮件 \(y=0\) 里面包含的单词 \(j\)

\[\phi_{j|y=0}=\frac{\sum_{i=1}^ml\{x_j^{(i)}=1\bigcap y^{(i)}=0\}}{\sum_{i=1}^ml\{y^{(i)}=0\}} \]

垃圾邮件 \(y=1\)

\[\phi_{j|y=1}=\frac{\sum_{i=1}^ml\{x_j^{(i)}=1\bigcap y^{(i)}=1\}}{\sum_{i=1}^ml\{y^{(i)}=1\}} \]

假设 \(m\) 封邮件里面的词向量 \(\vec x\) 和标识 \(y\)

\[(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...,(x^{(m)},y^{(m)}) \]

所以当垃圾邮件分类器开始训练时，假设训练垃圾邮件中包含某些词 \(x\) 的概率 \(p(y=1|x)\)

\[\begin{split} p(y=1|x)&=\frac{p(x|y=1)p(y=1)}{p(x)} \\ &=\frac{(\prod_{i=1}^n p(x_i|y=1))p(y=1)}{(\prod_{i=1}^n p(x_i|y=1))p(y=1)+(\prod_{i=0}^n p(x_i|y=0))p(y=0)} \end{split} \]

上式中分母是由 全概率 计算出词 \(p(x)\) 的概率，即假设 \(word_3\)

\[\begin{split} p(y=1|x)&=\frac{p(x|y=1)p(y=1)}{p(x)} \\ &=\frac{(\prod_{i=1}^{50000} p(x_3|y=1))p(y=1)}{(\prod_{i=1}^{50000} p(x_3|y=1))p(y=1)+(\prod_{i=0}^n p(x_i|y=0))p(y=0)} \\ &=\frac{0}{0+0} \end{split} \]

这就意味着如果 \(word_3\) 在垃圾邮件中没有出现，那么概率为0，这样子很明显是不合理的，无论在数学上会导致无法继续计算，还是从概率的角度来说直接排除 \(word_3\) 的可能性，其实最好的是 \(word_3\)

为了修正这个方法，这里最好是在分子分母加上一个极小数，防止数学上的无效计算和实际中的绝对不可能发生。

拉普拉斯平滑(Laplace smoothing)

继续上面投篮球的例子，假设没投中的概率记为 \(p(y=0)\) ，投中的概率记为 \(p(y=1)\)

\[\begin{split} p(y=0)&=\frac{没投中的次数}{投篮球的总次数} \\ &=\frac{没投中的次数}{投中的次数+没投中的次数} \\ &=\frac{0}{5+0} \end{split} \]

如果给每一项都平滑一个极小数1，代表投中篮球和没投中篮球在事先都已经发生过一次了，那么上述式子变成：

\[\begin{split} p(y=0)&=\frac{0+1}{(5+1)+(0+1)} \\ &=\frac{1}{7} \end{split} \]

那么同理可以知道， \(m\) 封邮件中，\(x_j=1\)表示包含关键词 \(j\)，\(x_j=0\)表示不包含关键词 \(j\)，则垃圾邮件 \(y=1\) 里面包含的单词 \(j\)

\[\phi_{j|y=1}=\frac{\sum_{i=1}^ml\{x_j^{(i)}\bigcap y^{(i)}=1\}+1}{\sum_{i=1}^ml\{y^{(i)=1}\}+2} \]

正常邮件 \(y=0\) 里面包含的单词 \(j\)

\[\phi_{j|y=0}=\frac{\sum_{i=1}^ml\{x_j^{(i)}=1\bigcap y^{(i)}=0\}+1}{\sum_{i=1}^ml\{y^{(i)}=0\}+2} \]

因为 \(y\)

总结

总的来说，朴素贝叶斯训练阶段为，给定一组已知的训练样本 \((\vec{x_1},y_1),(\vec{x_2},y_2),...,(\vec{x_n},y_n)\)，可以得到垃圾邮件中，每一个单词出现的概率：

\[p(x|y)=(\prod_{i=1}^{n}p(x_i|y_i) \]

而在 预测阶段 ，给定一封邮件的单词向量 \(\vec x\)，求这个邮件是否是垃圾邮件，那么问题就转化为：已知单词\(\vec x\)已经发生，求解是否垃圾邮件p(y|x)：

\[argmax_yp(y|x)=argmax_y \frac{p(x|y)p(y)}{p(x)}argmax_y p(x|y)p(y) \]

上述中，\(x\) 的取值只能是 \(x \in \{0,1 \}\)，\(n\)的长度应该等于词典中词的数目。

实例

朴素贝叶斯是一个非常优秀的文本分类器，现在大部分垃圾邮件过滤的底层也是基于贝叶斯思想。作者收集了 ​​25​​​ 封垃圾邮件， ​​25​​​ 封正常邮件，取 ​​40​​​ 封邮件做训练，​​10​​ 封邮件做测试。

加载数据：

# 打开数据集，获取邮件内容，# spam为垃圾邮件，ham为正常邮件def loadData(): # 选取一部分邮件作为测试集 testIndex = random.sample(range(1, 25), 5) dict_word_temp = [] testList = [] trainList = [] testLabel = [] trainLabel = [] for i in range(1, 26): wordListSpam = textParse(open('./email/spam/%d.txt' % i, 'r').read()) wordListHam = textParse(open('./email/ham/%d.txt' % i, 'r').read()) dict_word_temp = dict_word_temp + wordListSpam + wordListHam if i in testIndex: testList.append(wordListSpam) # 用1表示垃圾邮件 testLabel.append(1) testList.append(wordListHam) # 用0表示正常邮件 testLabel.append(0) else: trainList.append(wordListSpam) # 用1表示垃圾邮件 trainLabel.append(1) trainList.append(wordListHam) # 用0表示正常邮件 trainLabel.append(0) # 去重得到词字典 dict_word = list(set(dict_word_temp)) trainData = tranWordVec(dict_word, trainList) testData = tranWordVec(dict_word, testList) return trainData, trainLabel, testData, testLabel

训练函数为：

# 训练函数def train(trainData, trainLabel): trainMatrix = np.array(trainData) # 计算训练的文档数目 trainNum = len(trainMatrix) # 计算每篇文档的词条数 wordNum = len(trainMatrix[0]) # 文档属于垃圾邮件类的概率 ori_auc = sum(trainLabel) / float(trainNum) # 拉普拉斯平滑 # 分子+1 HamNum = np.ones(wordNum) SpamNum = np.ones(wordNum) # 分母+2 HamDenom = 2.0 SpamDenom = 2.0 for i in range(trainNum): # 统计属于垃圾邮件的条件概率所需的数据，即P(x0|y=1),P(x1|y=1),P(x2|y=1)··· if trainLabel[i] == 1: SpamNum += trainMatrix[i] SpamDenom += sum(trainMatrix[i]) else: # 统计属于正常邮件的条件概率所需的数据，即P(x0|y=0),P(x1|y=0),P(x2|y=0)··· HamNum += trainMatrix[i] HamDenom += sum(trainMatrix[i]) # 取对数，防止下溢出 SpamVec = np.log(SpamNum / SpamDenom) HamVec = np.log(HamNum / HamDenom) # 返回属于正常邮件类的条件概率数组，属于垃圾邮件类的条件概率数组，文档属于垃圾邮件类的概率 return HamVec, SpamVec, ori_auc

预测函数：

# 预测函数def predict(testDataVec, HamVec, SpamVec, ori_auc): predictToSpam = sum(testDataVec * SpamVec) + np.log(ori_auc) predictToHam = sum(testDataVec * HamVec) + np.log(1.0 - ori_auc) if predictToSpam > predictToHam: return 1 else: return 0

预测错误一个，错误率 ​​10%​​​ ，正确率 ​​90%​​：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。