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

精选 0 1045

小小草 2020年8月23日 08:38 发表

摘要：在上一篇算法中，逻辑回归作为一种二分类的分类器，一般的回归模型也是是判别模型，也就根据特征值来求结果概率。形式化表示为 p(y|x;θ)p(y|x;θ)，在参数 θθ 确定的情况下，

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

贝叶斯定理

定理推导

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

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

p (A | B) = \frac{p (A ⋂ B)}{p (B)}

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

p (B | A) = \frac{p (B ⋂ A)}{p (A)}

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

p (A | B) p (B) = p (A ⋂ 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 | x 1) = \frac{30}{10 + 30} \times \frac{1}{2}$ ，即抽到x1的概率是 $\frac{1}{2}$ ，再在x1中抽到普通饼干的概率是 $\frac{30}{10 + 30} = \frac{3}{4}$ ，同理可得 $P (y | x 2) = \frac{20}{20 + 20} \times \frac{1}{2}$ 。而问题中挑到挑到的普通饼干来自一号碗，已知挑到普通饼干，那么这个普通饼干来自一号碗的概率为：

P (x 1 | y) = \frac{P (y | x 1) P (x 1)}{P (y)}

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

计算为：

\begin{aligned} P (x 1 | y) & = \frac{P (y | x 1) P (x 1)}{P (y)} \\ = \frac{P (y | x 1) P (x 1)}{P (y | x 1) P (x 1) + P (y | x 2) P (x 2)} \\ = \frac{0.75 \times 0.5}{0.75 \times 0.5 + 0.5 \times 0.5} \\ = 0.6 \end{aligned}

朴素贝叶斯

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

电子邮件仅仅是一段文本，就像是一个词列表，因此利用词来构建特征向量 $\vec{x}$ 。首先遍历词典，并且得到一个词典中词的列表，假设词典中此的列表如下所示：

词
word_1
word_2
word_3
...
word_n

假设邮件中存在字典中的词，那么特征向量 $\vec{x}$ 就就记为1，不存在就记为0。例如邮件中假设存在词 $[w o r d_{1}, w o r d_{2}, . . ., w o r d_{n}]$ ，则该邮件的特征向量 $\vec{x}$ 表示为：

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

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

算法推导

在朴素贝叶斯算法中，我们会对 $p (x | y)$ 做一个假设，假设给定 $y$ 的时候，其中 $x \in {0, 1}^{50000}$ ， $x_{i}$ 是条件独立的，根据链式法则可以得到：

\begin{aligned} 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_{5} 0000 | 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{aligned}

为了拟合出模型的参数，符号假设为，其中 $y = 1$ 是垃圾邮件， $y = 0$ 是正常邮件：

ϕ_{i | y = 1} = p (x_{i} = 1 | y = 1) ϕ_{i | y = 0} = p (x_{i} = 1 | y = 0) ϕ_{y} = p (y = 1)

假设存在 $m$ 个样本，那么 $y = 1$ 和 $y = 0$ 的组合起来的似然估计表示为：

L (ϕ_{y}, ϕ_{i | y = 0}, ϕ_{i | y = 1}) = \prod_{i = 1}^{m} p (x^{(i)} | y^{(i)})

假设训练样本为 $m$ 封邮件， $x_{j} = 1$ 表示包含关键词 $j$ ， $x_{j} = 0$ 表示不包含关键词 $j$ ，则垃圾邮件 $y = 1$ 里面包含的单词 $j$ 的极大似然估计为：

ϕ_{j | y = 1} = \frac{\sum_{i = 1}^{m} l {x_{j}^{(i)} ⋂ y^{(i)} = 1}}{\sum_{i = 1}^{m} l {y^{(i)} = 1}}

上述公式中，分子的含义是从 1到 $m$ 遍历垃圾邮件内容，对于标签 $x_{j} = 1$ 的邮件计算其中词语 $j$ 出现的邮件数目之和。换句话说就是，遍历所有垃圾邮件，统计这些垃圾邮件中包含词语 $j$ 的邮件数目。分母是对 $i$ 从1到 $m$ 求和，最后得到垃圾邮件的总数，即分母就是垃圾邮件的数目。

同理，正常邮件 $y = 0$ 里面包含的单词 $j$ 的极大似然估计为：

ϕ_{j | y = 0} = \frac{\sum_{i = 1}^{m} l {x_{j}^{(i)} = 1 ⋂ y^{(i)} = 0}}{\sum_{i = 1}^{m} l {y^{(i)} = 0}}

垃圾邮件 $y = 1$ 的极大似然估计为：

ϕ_{j | y = 1} = \frac{\sum_{i = 1}^{m} l {x_{j}^{(i)} = 1 ⋂ y^{(i)} = 1}}{\sum_{i = 1}^{m} l {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{aligned} 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{aligned}

上式中分母是由 全概率 计算出词 $p (x)$ 的概率，即假设 $w o r d_{3}$ 在垃圾邮件中没有出现，那么可以得到：

\begin{aligned} 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{aligned}

这就意味着如果 $w o r d_{3}$ 在垃圾邮件中没有出现，那么概率为0，这样子很明显是不合理的，无论在数学上会导致无法继续计算，还是从概率的角度来说直接排除 $w o r d_{3}$ 的可能性，其实最好的是 $w o r d_{3}$ 没出现，但是还是会有概率，只是概率很低很低。举个例子来说，如果某个人投篮球，连续5次都是没投中，那么是不是投中的概率为0了，没投中的概率是1了？

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

拉普拉斯平滑(Laplace smoothing)

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

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

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

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

那么同理可以知道， $m$ 封邮件中， $x_{j} = 1$ 表示包含关键词 $j$ ， $x_{j} = 0$ 表示不包含关键词 $j$ ，则垃圾邮件 $y = 1$ 里面包含的单词 $j$ 的极大似然估计为：

ϕ_{j | y = 1} = \frac{\sum_{i = 1}^{m} l {x_{j}^{(i)} ⋂ y^{(i)} = 1} + 1}{\sum_{i = 1}^{m} l {y^{(i) = 1}} + 2}

正常邮件 $y = 0$ 里面包含的单词 $j$ 的极大似然估计为：

ϕ_{j | y = 0} = \frac{\sum_{i = 1}^{m} l {x_{j}^{(i)} = 1 ⋂ y^{(i)} = 0} + 1}{\sum_{i = 1}^{m} l {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)：

a r g m a x_{y} p (y | x) = a r g m a x_{y} \frac{p (x | y) p (y)}{p (x)} a r g m a x_{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%：

点赞 0 收藏(0)