朴素贝叶斯算法及其代码实现

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

条件概率

基础知识

条件概率

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

$P (A | B) = \frac{P (A B)}{P (B)}$

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

贝叶斯准则

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

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

所以可以得到 $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}$ 的概率是 $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}$

朴素贝叶斯文档分类

简介

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

向量 $\vec{w} = (w_{1}, w_{2}, . . ., w_{n})$ 代表一篇文章。其中 $w_{i} = 0, 1$ ，代表词汇表中第 $i$ 个词汇出现与否。词汇表是指一个总体的全局词汇表。文章 $\vec{w}$ 属于第 $i$ 类的概率 $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}) \dots P (w_{n} | c_{i})

其中 $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}))

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

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

P (w | c_{0}) = \vec{w} \cdot \vec{w p_{0}}, P (w | c_{1}) = \vec{w} \cdot \vec{w p_{1}}

程序实现

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

加载数据

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

python

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，所以我们划分数据集只需要获得对应的索引集合就可以了。

python

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

获得训练矩阵

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

获得所有的词汇

python

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)

获得一篇文章的文档向量

python

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

获得训练矩阵

python

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{w p_{0}}$ 、 $\vec{w p_{1}}$ 和 $p (c_{1})$ 。

python

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

贝叶斯分类

python

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

训练数据

python

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

测试数据

一次执行

python

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

多次执行，取平均值

python

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)

源代码

朴素贝叶斯算法及其代码实现

条件概率 ​

基础知识 ​

条件概率分类 ​

朴素贝叶斯文档分类 ​

程序实现 ​

加载数据 ​

划分数据集 ​

获得训练矩阵 ​

贝叶斯算法 ​

测试数据 ​

条件概率

基础知识

条件概率分类

朴素贝叶斯文档分类

程序实现

加载数据

划分数据集

获得训练矩阵

贝叶斯算法

测试数据