先介绍了朴素贝叶斯思想理论，然后用朴素贝叶斯代码实现垃圾邮件分类

条件概率

基础知识

条件概率

在\(B\)发生的情况下\(A\)的概率$ $

​ \(P(A|B) = \frac{P(AB)}{P(B)}\)

​ \(P(c_i|x)=\frac{P(c_ix)}{P(x)}\)。\(c_i\)是类别，\(x\)是一个向量。\(x\)属于类别\(c_i\)的概率。

贝叶斯准则

交换条件概率中的条件与结果，得到想要的值。

\(P(A|B) = \frac{P(AB)}{P(B)}\), \(P(B|A) = \frac{P(AB)}{P(A)}\) \(\to\) \(P(B|A)=\frac{P(A|B)P(B)}{P(A)}\)

所以可以得到\(\color{red}{P(c_i|x)}=\frac{P(x|c_i)P(c_i)}{P(x)}\)

条件概率分类

贝叶斯决策理论

计算两个概率\(x\)属于类别1和类别2的概率\(p_1(x)\)和\(p_2(x)\)。

  • 如果\(p_1(x) > p_2(x)\)，则\(x\)属于类别1
  • 如果\(p_2(x) > p_1(x)\)，则\(x\)属于类别2

贝叶斯准则

\(x\)属于类别\(c_i\)的概率是\(\color{red}{P(c_i|x)}\)。

  • 如果\(P(c_1|x) > P(c_2|x)\)，则\(x\)属于\(c_1\)
  • 如果\(P(c_2|x) > P(c_1|x)\)，则\(x\)属于\(c_2\)

朴素贝叶斯文档分类

简介

机器学习的一个重要应用就是文档的自动分类。我们可以观察文档中出现的词，并把每个词出现与否或者出现次数作为一个特征。朴素贝叶斯就是用于文档分类的常用算法，当然它可以用于任意场景的分类。

向量\(\color{red}{\vec{w}}={(w_1,w_2,...,w_n)}\)代表一篇文章。其中\(w_i=0,1\)，代表词汇表中第\(i\)个词汇出现与否。词汇表是指一个总体的全局词汇表。文章\(\vec{w}\)属于第\(i\)类的概率\(\color{red}{P(c_i|\vec{w})}=\frac{P(\vec{w}|c_i)P(c_i)}{P(\vec{w})}\)。

朴素贝叶斯分类器的两个假设：

  • 特征之间相互独立
  • 每个特征同等重要

尽管这有瑕疵，但是朴素贝叶斯的实际效果却很好了。

朴素贝叶斯分类器的两种实现：

  • 伯努利模型：只考虑出现或者不出现
  • 多项式模型：考虑词在文档中的出现次数

文档分类中的独立：每个单词出现的可能性和其他单词没有关系。独立的好处在下面概率计算中会体现出来。

概率计算

对每一个文章的各个分类概率计算，其实只需要计算上式的分母就行了。

对于\(P(c_i)=\frac{c_i数量}{总数量}\)，即\(c_i\)类文章的数量除以所有类别的文章的总数量。

对于\(P(\vec{w}|c_i)\)，要稍微复杂一些。由于各个特征（单词出现否）独立，则有如下推导公式：

\[P(\vec{w}|c_i)=P(w_1,w_2,...,w_n|c_i)=P(w_1|c_i)P(w_2|c_i)\cdots P(w_n|c_i)\]

其中\(\color{red}{P(w_i|c_i)}\)代表第\(i\)个单词在\(c_i\)类别文章的总词汇里出现的概率。

实际操作的一个小技巧，由于概率都很小多个小值做乘法会导致下溢出，所以决定对概率取对数做加法，最后再比较对数的大小。

\[\ln(P(\vec{w}|c_i))=\ln(P(w_1|c_i))+\ln(P(w_2|c_i))+\dots+\ln(P(w_n|c_i))\]

如上，可以求得每个单词在各个类别文章里出现的概率。用\(\color{red}{\vec{wp_0}}\)、\(\color{red}{\vec{wp_1}}\)来分别表示所有单词在类别0、类别1中总词汇中的概率。当然，在程序中实际上这个概率是取对数了的。

当要求一篇新的文章\(\color{red}{\vec{w}}={(0,1,0,0,\dots)}\)，此时为出现或者不出现，当然也可以统计出现次数，属于哪个类别的时候，要先求出\(\color{red}{P(w|c_0)}\)和\(\color{red}{P(w|c_1)}\)，然后根据贝叶斯准则选择概率大的分类为结果。

\[P(w|c_0)=\vec{w}\cdot\vec{wp_0}, P(w|c_1)=\vec{w}\cdot\vec{wp_1}\]

程序实现

朴素贝叶斯的实例应有很多，这里主要是介绍垃圾邮件分类。数据集中的邮件有两种：垃圾邮件和正常邮件。每个类型都有25个样本，一共是50个样本。我们对数据集进行划分为训练集和测试集。训练集用来训练获得\(\vec{wp_0}\)、\(\vec{wp_1}\)和\(p(c_1)\)。然后用测试集去进行朴素贝叶斯分类，计算错误率，查看效果。

加载数据

数据是存放在两个文件夹中的，以txt格式的形式存储。取出来后要进行单词切割。然后得到邮件列表email_list和它对应的分类列表class_list。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def parse_str(big_str):
    ''' 解析文本为单词列表
    Args:
        big_str: 长文本
    Returns:
        单词列表
    '''
    # 以任何非单词字符切割
    word_list = re.split(r'\W*', big_str)
    # 只保留长度大于3的单词，并且全部转化为小写
    return [word.lower() for word in word_list if len(word) > 2]


def load_dataset(spam_dir, ham_dir):
    ''' 从文件夹中加载文件
    Args:
        spam_dir: 垃圾邮件文件夹
        ham_dir: 正常邮件文件夹
    Returns:
        email_list: 邮件列表
        class_list: 分类好的列表
    '''
    email_list = []
    class_list = []
    txt_num = 25    # 每个文件夹有25个文件
    for i in range(1, txt_num + 1):
        for j in range(2):
            file_dir = spam_dir if j == 1 else ham_dir
            f = open(('{}/{}.txt').format(file_dir, i))
            f_str = f.read()
            f.close()
            words = parse_str(f_str)
            email_list.append(words)    # 邮件列表
            class_list.append(j)        # 分类标签，1垃圾邮件，0非垃圾邮件
    return email_list, class_list

划分数据集

由于前面email_list包含所有的邮件，下标是从0-49，所以我们划分数据集只需要获得对应的索引集合就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def get_train_test_indices(data_num):
    ''' 划分训练集和测试集
    Args:
        data_num: 数据集的数量
    Returns:
        train_indices: 训练集的索引列表
        test_indices: 测试集的索引列表
    '''
    train_indices = range(data_num)
    test_ratio = 0.3        # 测试数据的比例
    test_num = int(data_num * test_ratio)
    test_indices = random.sample(train_indices, test_num)	# 随机抽样选择
    for i in test_indices:
        train_indices.remove(i)
    return train_indices, test_indices

获得训练矩阵

获得训练数据之后，要把训练数据转化为训练矩阵。

获得所有的词汇

1
2
3
4
5
6
7
8
9
10
11
def get_vocab_list(post_list):
    ''' 从数据集中获取所有的不重复的词汇列表
    Args:
        post_list: 多个文章的列表，一篇文章：由单词组成的list
    Returns:
        vocab_list: 单词列表
    '''
    vocab_set = set([])
    for post in post_list:
        vocab_set = vocab_set | set(post)
    return list(vocab_set)

获得一篇文章的文档向量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def get_doc_vec(doc, vocab_list, is_bag = False):
    ''' 获得一篇doc的文档向量
    词集模型：每个词出现为1，不出现为0。每个词出现1次
    词袋模型：每个词出现次数，可以多次出现。
    Args:
        vocab_list: 总的词汇表
        doc: 一篇文档，由word组成的list
        is_bag: 是否是词袋模型，默认为Fasle
    Returns:
        doc_vec: 文档向量，1出现，0未出现
    '''
    doc_vec = [0] * len(vocab_list)
    for word in doc:
        if word in vocab_list:
            idx = vocab_list.index(word)
            if is_bag == False:         # 词集模型
                doc_vec[idx] = 1
            else:
                doc_vec[idx] += 1       # 词袋模型
        else:
            print '词汇表中没有 %s ' % word
    return doc_vec

获得训练矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def go_bayes_email():
    ''' 贝叶斯垃圾邮件过滤主程序
    Returns:
        error_rate: 错误率
    '''
    # 源数据
    email_list, class_list = load_dataset('email/spam', 'email/ham')
    # 总的词汇表
    vocab_list = bys.get_vocab_list(email_list)
    # 训练数据，测试数据的索引列表
    data_num = len(email_list)
    train_indices, test_indices = get_train_test_indices(data_num)
    # 训练数据的矩阵和分类列表
    train_mat = []
    train_class = []
    for i in train_indices:
        vec = bys.get_doc_vec(email_list[i], vocab_list)
        train_mat.append(vec)
        train_class.append(class_list[i])
    # 后续还有训练数据和测试数据，在下文给出

贝叶斯算法

贝叶斯训练算法

通过训练数据去计算上文提到的\(\vec{wp_0}\)、\(\vec{wp_1}\)和\(p(c_1)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def train_nb0(train_mat, class_list):
    ''' 朴素贝叶斯训练算法，二分类问题
    Args:
        train_mat: 训练矩阵，文档向量组成的矩阵
        class_list: 每一篇文档对应的分类结果
    Returns:
        p0_vec: c0中各个word占c0总词汇的概率
        p1_vec: c1中各个word占c1总词汇的概率
        p1: 文章是c1的概率
    '''
    # 文档数目，单词数目
    doc_num = len(train_mat)
    word_num = len(train_mat[0])
    # 两个类别的总单词数量
    c0_word_count = 2.0
    c1_word_count = 2.0
    # 向量累加
    c0_vec_sum = np.ones(word_num)
    c1_vec_sum = np.ones(word_num)
    for i in range(doc_num):
        if class_list[i] == 0:
            c0_word_count += sum(train_mat[i])
            c0_vec_sum += train_mat[i]
        else:
            c1_word_count += sum(train_mat[i])
            c1_vec_sum += train_mat[i]
    c1_num = sum(class_list)
    p1 = c1_num / float(doc_num)
    p0_vec = c0_vec_sum / c0_word_count
    p1_vec = c1_vec_sum / c1_word_count
    # 由于后面做乘法会下溢出，所以取对数做加法
    for i in range(word_num):
        p0_vec[i] = math.log(p0_vec[i])
        p1_vec[i] = math.log(p1_vec[i])
    return p0_vec, p1_vec, p1

贝叶斯分类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def classify_nb(w_vec, p0_vec, p1_vec, p1):
    ''' 使用朴素贝叶斯分类
    Args:
        w_vec: 要测试的向量
        p0_vec: c0中所有词汇占c0的总词汇的概率
        p1_vec: c1中所有词汇占c1的总词汇的概率
        p1: 文章为类型1的概率，即P(c1)
    '''
    # P(w|c0)*P(c0) = P(w1|c0)*...*P(wn|c0)*P(c0)
    # 由于下溢出，所以上文取了对数，来做加法
    w_p0 = sum(w_vec * p0_vec) + math.log(1 - p1)
    w_p1 = sum(w_vec * p1_vec) + math.log(p1)
    if w_p0 > w_p1:
        return 0
    return 1

训练数据

1
p0_vec, p1_vec, p1 = bys.train_nb0(train_mat, train_class)

测试数据

一次执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def go_bayes_email():
	# 此处省略上文的部分内容
    # 训练数据
    p0_vec, p1_vec, p1 = bys.train_nb0(train_mat, train_class)
    
    # 测试数据
    error_count = 0
    for i in test_indices:
        vec = bys.get_doc_vec(email_list[i], vocab_list)
        res = bys.classify_nb(vec, p0_vec, p1_vec, p1)
        if res != class_list[i]:
            error_count += 1
    error_rate = error_count / float(data_num)
    print 'error=%d, rate=%s, test=%d, all=%d' % (error_count, error_rate, len(test_indices),
                    data_num)
    return error_rate

多次执行，取平均值

1
2
3
4
5
6
7
def test_bayes_email():
    ''' 执行多次go_bayes_email，计算平均错误率 '''
    times = 100
    error_rate_sum = 0.0
    for i in range(10):
        error_rate_sum += go_bayes_email()
    print 'average_rate = %s' % (error_rate_sum / 10)

源代码