垃圾邮件过滤--朴素贝叶斯 (Python)

目录

• 内容概况
• 认识朴素贝叶斯
• 邮件过滤系统

---

内容概况

现实生活中，我们会在各类网站使用自己的电子邮箱注册，避免不了网站会时不时的给我们发送一些垃圾邮件。我们的目的是手写一个识别系统，将收到的邮件进行分类。

在这一方面，我们不得不提朴素贝叶斯，在处理文本分类，垃圾邮件过滤中的效率极高。2002年，Paul Graham提出使用"贝叶斯推断"过滤垃圾邮件。他说，这样做的效果，好得不可思议。1000封垃圾邮件可以过滤掉995封，且没有一个误判。

认识朴素贝叶斯

朴素贝叶斯 (naive Bayes) 法是基于贝叶斯定理与特征条件独立假设的分类的方法。对于给定的训练数据集，首先基于特征条件独立假设学习输入/输出的联合概率分布；然后基于此模型，对于给定的输入x，利用贝叶斯定理求出后验概率最大的输出y。

基本方法

贝叶斯定理是关于随机事件A和B的条件概率（或边缘概率）的一则定理。以邮件过滤为例：

其中:

• Pr(S|W) 为邮件为垃圾邮件(spam)的概率，在已知词汇W的条件下。
• Pr(S) 为垃圾邮件的概率
• Pr(W|S) 为垃圾邮件中，词汇W的概率

---

假定每一封邮件用一个向量来表示 x=(x1, x2, x3,..., xn), 其中 x1, x2,..., xn 为特征 X1, X2,...,Xn 的取值。在这里我们用0和1来表示，Xi=1表示Xi词汇出现在当前邮件中，Xi=0表示当前邮件中不存在Xi词汇。

先验概率分布

条件概率分布

![][02]
之所以称为“朴素”，是因为对条件概率分布做了独立性假设，尽管这样的假设在真实世界中是不太可行的，例如delicious接在taste 后面的概率会大于smell后面的概率，但是运用朴素贝叶斯计算时，将会把他们的看成相互独立的。尽管这样，朴素贝叶斯在预测方面的准确率依旧非常的高。

因此，条件概率分布可以写成如下形式：
![][03]

朴素贝叶斯法分类时，对于给定的输入x，通过学习到的模型计算后验概率分布P(Y=y|X=x)，将后验概率最大的类作为x的类输出，后验概率计算根据贝叶斯定理进行：
![][04]

注意到，在上式中分母对于spam, ham都是相同的，所以：
![][05]

邮件过滤系统

对于如下这样一个社区留言板文本：

posting_list = [
    ['my', 'dog', 'has', 'flea', 'problem', 'help', 'please'],
    ['maybe', 'not', 'take', 'him', 'to', 'dog', 'park', 'stupid'],
    ['my', 'dalmation', 'is', 'so', 'cute', 'I', 'love', 'him'],
    ['stop', 'posting', 'stupid', 'worthless', 'garbage'],
    ['mr', 'licks', 'ate', 'ny', 'steak', 'how', 'to', 'stop', 'him'],
    ['quit', 'buying', 'worthless', 'dog', 'food', 'stupid']
    ]
labels = [0, 1, 0, 1, 0, 1]

其中，我们对进行负面和正面分类，0代表正类，1代表负类。

首先得根据上述文本建立一个词汇表，即把重复的词汇剔除。代码如下：

def create_vocabulary_list(dataset):
    # dataset 包含了多条留言的文本，每一条留言为一个列表
    vocabset = set([])
    for document in dataset:
        vocabset = vocabset | set(document)
    return list(vocabset)

接下便是计算词汇表中每个单词分别在负类和正类条件下的概率，以及负类的概率：

P(y=1)=0.5, P(y=1)= 1-P(y=1)=0.5

其中负类的先验概率是0.5，等于负类的数量除以留言的总数量。正类的概率为1减去负类的概率。

计算每个单词分别在负类和正类条件下的概率，首先得把留言转化为向量如下所示：

词汇表: ['help', 'to', 'stupid', 'problem', 'garbage', 'love', 'licks', 'dog', 'stop', 'so', 'ny', 'take', 'is', 'food', 'worthless', 'park', 'flea', 'steak', 'has', 'dalmation', 'how', 'posting', 'please', 'my', 'maybe', 'buying', 'quit', 'ate', 'cute', 'mr', 'not', 'I', 'him']
对于文本：['my', 'dog', 'has', 'flea', 'problem', 'help', 'please']
转化为向量：[0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0]

转化为向量的代码如下：

def wordsToVector(vocabset, inputset):
    # vocabset 是词汇表， inputset 为要转化为向量的文本
    vector = [0]*len(vocabset)
    for word in inputset:
        if word in vocabset:
            vector[vocabset.index(word)] = 1
        else:
            print("The word: {} is not in my Vocabulary.".format(word))
    return vector

转化为向量之后，计算每个词汇分别在负类和正类的概率代码如下：

def traing_bayes(trainset, trainCategory):
    """sovle the conditional probility"""
    # trainCategory 是标记为负类和正类的向量
    num_train = len(trainset)
    # 获取训练集的数量，其中训练集是由文本向量组成
    num_vocab = len(trainset[0])
    # 由于训练集中的每个元素都是文本向量，即包含了整个词汇表

    pAbusive = sum(trainCategory) / num_train
    # 计算负类的概率，负类的数量除以训练集的数目
    
    pnorm_vector = np.ones(num_vocab)
    # 每个词汇出现在正类中的概率组成的向量
    pabu_vector = np.ones(num_vocab)
    # 每个词汇出现在负类中的概率组成的向量
    
    pnorm_denom = 2.0
    # 正类中词汇的数目
    pabu_denom = 2.0
    # 负类中词汇的数目

    for i in range(num_train):
        if trainCategory[i] == 1:
            pabu_vector += trainset[i]
            pabu_denom += sum(trainset[i])
        else:
            pnorm_vector += trainset[i]
            pnorm_denom += sum(trainset[i])

    pnorm_vector = np.log(pnorm_vector / pnorm_denom)
    pabu_vector = np.log(pabu_vector / pabu_denom)

    return pnorm_vector, pabu_vector, pAbusive

进行分类的代码如下：

def classify(testVector, pnorm_vector, pabu_vector, pabusive):
    # 先将测试文本转化为向量
    pnorm = sum(testVector*pnorm_vector) + np.log(1 - pabusive)
    # 计算测试文本为正类的概率
    pabu = sum(testVector*pabu_vector) + np.log(pabusive)
    # 计算测试文本为负类的概率
    if pabu > pnorm:
        return 1
    else:
        return 0

测试代码如下：

def test_bayes():
    posts_list, classes_list = load_data_set()
    vocab_list = create_vocab_list(posts_list)

    trainset = []
    for post in posts_list:
        trainset.append(wordsToVector(vocab_list, post))
    pnorm_vector, pabu_vector, pAbusive = traing_bayes(trainset, classes_list)

    testEntry = ['love', 'my', 'dalmation']
    testVector = np.array(wordsToVector(vocab_list, testEntry))

    print(testEntry, "classified as: {}".format(classify(testVector, pnorm_vector, pabu_vector, pAbusive)))

    testEntry = ['stupid', 'garbage']
    testVector = np.array(wordsToVector(vocab_list, testEntry))

    print(testEntry, "classified as: {}".format(classify(testVector, pnorm_vector, pabu_vector, pAbusive)))

结果如下：
['love', 'my', 'dalmation'] classified as: 0
['stupid', 'garbage'] classified as: 1

[02]:http://latex.codecogs.com/png.latex?$$P(X=x|Y=y)=P(X^{(1)}=x{(1)},...,X^{(n)}=x{(n)}|Y=y),y\in{spam,ham}$$
[03]:http://latex.codecogs.com/png.latex?$$P(X=x|Y=y)=\prod_{j=1}^nP(X{(j)}=x^{(j)}|Y=y)$$
[04]:http://latex.codecogs.com/png.latex?$$P(spam|x)=\frac{P(x|spam)\cdot{P(spam)}}{P(x|spam)\cdot{P(spam)+P(x|ham)\cdot{P(ham)}}}$$
[05]:http://latex.codecogs.com/png.latex?$$f(x)=\mathop{\arg\min}\limits_{y\in{ham,spam}}P(Y=y)\prod_{j=1}^nP(X{(j)}=x^{(j)}|Y=y)$$