在上一篇算法中, 逻辑回归作为一种二分类的分类器, 一般的回归模型也是是判别模型, 也就根据特征值来求结果概率. 形式化表示为 \(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}\times\frac{1}{2}\), 即抽到 x1 的概率是 \(\frac{1}{2}\) , 再在 x1 中抽到普通饼干的概率是 \(\frac{30}{10+30}=\frac{3}{4}\) , 同理可得 \(P(y|x2)=\frac{20}{20+20}\times\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\) . 首先遍历词典, 并且得到一个词典中词的列表, 假设词典中此的列表如下所示:
词 |
---|
word_1 |
word_2 |
word_3 |
... |
word_n |
假设邮件中存在字典中的词, 那么特征向量 \(\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\) 没出现, 但是还是会有概率, 只是概率很低很低. 举个例子来说, 如果某个人投篮球, 连续 5 次都是没投中, 那么是不是投中的概率为 0 了, 没投中的概率是 1 了?
为了修正这个方法, 这里最好是在分子分母加上一个极小数, 防止数学上的无效计算和实际中的绝对不可能发生.
拉普拉斯平滑 (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\) 只有两种可能, 我们这里也假设事先存在一封垃圾邮件和一封正常邮件, 所以分子只需要 + 1, 分母只需要 + 2.
总结
总的来说, 朴素贝叶斯训练阶段为, 给定一组已知的训练样本 \((\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%:
数据和代码下载请关注公众号 [ TTyb ] , 后台回复 [ 机器学习 ] 即可获取:
来源: https://www.cnblogs.com/TTyb/p/10989082.html