MachineLearning-NaiveBayesClassifiers

发表于 | 分类于

Machine Learning-NaiveBayesClassifiers

标签： MachineLearning 人工智能 贝叶斯

算法概述

  概率论是许多机器学习算法基础，朴素贝叶斯分类器(NaiveBayesClassifiers)是一个比较简单的概率分类器。之所以称其为“朴素”，是因为此分类器在形式化的过程中只做了最原始的最简单的假设。其优势是在数据较少的情况下仍然有效，可以处理多类别的问题；但是其对于输入数据的准备方式较为敏感；其适用的数据类型为标称型数据。

算法准备

  在学习朴素贝叶斯分类之前，我们需要先回顾一些数学基础的概念。

贝叶斯决策论

  贝叶斯决策论(BayesianDecisionTheory)是概率框架下实施决策的基本方法，对于分类任务来说，在所有相关概率都已知的理想情况下，贝叶斯决策论如何基于这些概率和误判损失来选择最优的类别标记。贝叶斯判定准则可以概括为：最小化总体风险。对于贝叶斯分类器，具体来说，其目标是最小化分类错误率。
  不难看出，欲使用贝叶斯判定准则来最小化决策风险，首先要获得后验概率，然而在现实任务中，这通常难以直接获得。从这个角度来说机器学习所要实现的是基于有限的训练样本集尽可能准确地估计出后验概率。大体来说，主要有两种决策：通过直接建模来对目标概率建模，得到“判别式模型”；也可以先对联合分布建模，然后再利用贝叶斯定理间接获得条件概率，这样得到的是“生成式模型”。决策树，BP神经网络，支持向量机等，都可以归入判别式模型的范畴。对于生成模型来说必然考虑基于贝叶斯定理的:
           Markdown
  其中 P(c)是先验概率；P(x|c)则是样本x相对于类标记c的类条件概率，或称“似然”；P(x)是用于归一化的“证据”因子。其中P(c)表达样本空间中各类样本所占的比例，根据大数定理得，当训练集包含充足的独立同分布样本时，P(c)可通过各类样本出现的频率直接进行估计。但是对于P(x|c)来说，由于它涉及关于$x$所有属性的联合概率，直接根据样本出现的概率来估计将会遇到严重的困难，因为“未被观察到”与“出现概率为零”通常是不同的。

条件概率

  条件概率是指事件c，在已知事件x发生的前提下发生的概率。而贝叶斯决策是一种有效计算条件概率的方法，另一种有效的方法则较为简单，可直接用如下公式计算：
              Markdown

使用条件概率分类

  使用条件概率进行分类的基本思路在已知所有发生事件的前提下，比较不同分类发生的条件概率，选择条件概率值最大的分类方式作为其分类标签。具体的，应用贝叶斯准则得到：
          Markdown
  使用这些定义，可以定义贝叶斯分类准则为：
   如果P(c_1|x,y)>P(C_2|x,y) 那么属于c_1
   如果P(c_2|x,y)>P(C_1|x,y) 那么属于c_2

算法思路

  不难发现，基于贝叶斯公式来估计后验概率P(c|x)的主要困难在于：类条件概率P(x|c)是所有属性上的联合概率，难以从有限的训练样本直接估计得到，为避免此障碍，朴素贝叶斯分类器采用了“属性条件独立性假设”：对于已知类型，假设所有属性相互独立。基于条件独立性假设有：
   Markdown
  其中d为属性数目，x_i为x在第i个属性上的取值。对于所有类别来说P(x)相同，因此基于上式的贝叶斯判别准则有：
        Markdown
  此为贝叶斯分类器的表达式。实现的时候，计算出各属性的P(c_i)值进行比较。选择出最大的值，其对应的分类标签即为朴素贝叶斯分类器的结果
  需要注意的是，在实际计算的过程中，为了避免其他属性携带的信息被训练集中未出现的属性值抹去，在估计概率值时通常要进行“平滑”，常用“拉普拉斯修正”，具体来说，另N表示训练集D中可能出现的类别数，N_i表示第i个属性可能的取值数，则将P(c)和P(x_i|c)分别修正为：
               Markdown
  拉普拉斯修正避免了因为训练集样本不充分而导致概率估计为零的问题，并且在训练集变大时，修正过程所引起的先验影响也会逐渐变得可忽略，使得估值逐渐趋向实际概率值。

算法实现

  朴素贝叶斯分类器通常有两种实现方式：一种是基于伯努利模型实现，一种是基于多项式模型实现。在此处的实现采用前一种实现方式。该实现方式中并不考虑词在文档中出现的次数，只考虑出不出现，因此在这个意义上相当于假设词是等权重的，即在此基础上做出朴素贝叶斯分类器的第二个假设，每个特征同等重要。其实现的一般过程为：
    （1）收集数据：方法不限
    （2）准备数据：数值型或者布尔型
    （3）分析数据：特征分析
    （4）训练算法：计算不同的独立同分布特征的条件概率
    （5）测试算法：计算错误率
  本文实现是在参考《Machine Learing in Action》实现的基础上实现的。
  本文实现朴素贝叶斯分类器是基于文本分类实现的，将文本看做单词向量或者词条向量，考虑所有文档中所有单词，再决定将哪些词纳入词汇表或者说要的词汇集合，然后将每一篇文档转换为词汇表上的向量。向量中”1”代表文档中有该词，“0”代表无该词；之后训练算法，即从词向量中计算每个类别的条件概率；然后利用条件概率计算每个两个标签的概率，取概率较大的标签作为结果。
  核心函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def trainNBO(trainMatrix,trainCategory):
    numTrainDocs = len(trainMatrix)
    numWords = len(trainMatrix[0])
    pAbusive = sum(trainCategory)/float(numTrainDocs)
    #p0Num = zeros(numWords)
    #p1Num = zeros(numWords)
    p0Num = ones(numWords)
    p1Num = ones(numWords)
    #p0Denom = 0.0; p1Denom = 0.0
    p0Denom = 2.0; p1Denom = 2.0
    for i in range(numTrainDocs):
        if trainCategory[i] == 1:
            p1Num += trainMatrix[i]
            p1Denom += sum(trainMatrix[i])
        else:
            p0Num += trainMatrix[i]
            p0Denom += sum(trainMatrix[i])
    p1Vect = p1Num/p1Denom
    p0Vect = p0Num/p0Denom
    return p0Vect,p1Vect,pAbusive

  此函数为朴素贝叶斯分类器的训练函数。输入“trainMatrix”为文档矩阵,“trainCategory”为每篇文档类别标签构成的向量。此函数是利用样本对贝叶斯分类器进行训练，返回的结果为每个类别的条件概率，包括两个概率向量和一个概率值，两个概率向量分别属于两个标签。此函数完成拉普拉斯修正，标注代码为未进行拉普拉斯修正。

1
2
3
4
5
6
7
def classifyNB(vec2Classify,p0Vec,p1Vec,pClass1):
    p1 = sum(vec2Classify*p1Vec) + log(pClass1)
    p0 = sum(vec2Classify*p0Vec) + log(1-pClass1)
    if p1 > p0:
        return 1
    else:
        return 0

  此函数为朴素贝叶斯的分类函数，即在得到每个类别的条件概率之后，利用各条件概率计算两个标签的概率，之后再进行比较选择值较大的标签作为结果。函数的输入为要分类的向量“vec2Classify”,以及三个训练好的概率参数“p0Vec,p1Vec,pClass1”。
  利用朴素贝叶斯分类器进行文本分类的完整代码如下：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
from numpy import *

def loadDataSet():
    postingList=[['my', 'dog', 'has', 'flea', 'problems', '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', 'my', 'steak', 'how', 'to', 'stop', 'him'],
                 ['quit', 'buying', 'worthless', 'dog', 'food', 'stupid']]
    classVec = [0,1,0,1,0,1]    #1 is abusive, 0 not
    return postingList,classVec

def createVocabList(database):
    vocabSet = set([])
    for document in database:
        vocabSet = vocabSet | set(document)
    return list(vocabSet)

def setOfWords2Vec(vocabList, inputSet):
    returnVec = [0]*len(vocabList)
    for word in inputSet:
        if word in vocabList:
            returnVec[vocabList.index(word)] = 1
        else: print "the word:%s is not in my Vocabulary!" %word
    return returnVec

# train def of NaiveBayesClassifiers
def trainNBO(trainMatrix,trainCategory):
    numTrainDocs = len(trainMatrix)
    numWords = len(trainMatrix[0])
    pAbusive = sum(trainCategory)/float(numTrainDocs)
    #p0Num = zeros(numWords)
    #p1Num = zeros(numWords)
    p0Num = ones(numWords)
    p1Num = ones(numWords)
    #p0Denom = 0.0; p1Denom = 0.0
    p0Denom = 2.0; p1Denom = 2.0
    for i in range(numTrainDocs):
        if trainCategory[i] == 1:
            p1Num += trainMatrix[i]
            p1Denom += sum(trainMatrix[i])
        else:
            p0Num += trainMatrix[i]
            p0Denom += sum(trainMatrix[i])
    p1Vect = p1Num/p1Denom
    p0Vect = p0Num/p0Denom
    return p0Vect,p1Vect,pAbusive

def classifyNB(vec2Classify,p0Vec,p1Vec,pClass1):
    p1 = sum(vec2Classify*p1Vec) + log(pClass1)
    p0 = sum(vec2Classify*p0Vec) + log(1-pClass1)
    if p1 > p0:
        return 1
    else:
        return 0

def testingNB():
    listOPosts,listClasses = loadDataSet()
    myVocabList = createVocabList(listOPosts)
    trainMat = []
    for postinDoc in listOPosts:
        trainMat.append(setOfWords2Vec(myVocabList,postinDoc))
    p0V,p1V,pAb = trainNBO(array(trainMat),array(listClasses))
    testEntry = ['love','my','dalmation']
    thisDoc = array(setOfWords2Vec(myVocabList,testEntry))
    print thisDoc
    print testEntry,'classified as: ',classifyNB(thisDoc,p0V,p1V,pAb)
    testEntry = ['stupid','garbage']
    thisDoc = array(setOfWords2Vec(myVocabList,testEntry))
    print thisDoc
    print testEntry,'classified as: ',classifyNB(thisDoc,p0V,p1V,pAb)

  测试代码如下：

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
from numpy import *
import matplotlib
import matplotlib.pyplot as plt
import NaiveBayes

# test Of first and secong def in NaiveBayes
'''
listOPosts,listClasses = NaiveBayes.loadDataSet()
myVocabList = NaiveBayes.createVocabList(listOPosts)
print myVocabList
'''
# test of setOfWords2Vec
'''
testOfSW2V=NaiveBayes.setOfWords2Vec(myVocabList,listOPosts[0])
print testOfSW2V
'''

# test of trainNB0
'''
reload(NaiveBayes)
listOPosts,listClasses = NaiveBayes.loadDataSet()
myVocabList = NaiveBayes.createVocabList(listOPosts)
trainMat = []
for postinDoc in listOPosts:
    trainMat.append(NaiveBayes.setOfWords2Vec(myVocabList,postinDoc))
p0V,p1V,pAb = NaiveBayes.trainNBO(trainMat,listClasses)
print pAb
print p0V
print p1V
'''

# test of NaiveBayes.py
reload(NaiveBayes)
NaiveBayes.testingNB()

  测试结果如下：

1
2
3
4
5
$  python run.py
[0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
['love', 'my', 'dalmation'] classified as:  0
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]
['stupid', 'garbage'] classified as:  1

  可知第一个测试样本结果为“0”，第二个测试样本结果为“1”.

算法应用

  在实现任务中，朴素贝叶斯分类器有多种使用方法。例如若对预测速度要求较高，则对给定训练集，可将朴素贝叶斯分类器涉及的所有概率估计值事先计算好储存起来，这样在进行预测时，只需要查表即可进行判别；若任务数据更替频繁，则可采用“懒惰学习”方式，先不进行任何训练，待收到预测请求时再根据当前数据集进行概率估值；若数据不断增加，则可以在现有的基础上，仅对新增样本的属性值所涉及的概率估值进行计数修正即可实现增量学习。
  可以利用朴素贝叶斯分类器进行垃圾邮件过滤，个人广告获取区域倾向等应用，在《Machine Learing in Action》中有一个简单的例子可以参考。

算法小结

  对于分类而言，使用概率有时候比使用硬规则更加有效。贝叶斯概率即贝叶斯准则提供了一种利用已知值来进行估计未知概率的有效方法，可以通过特征值之间的条件独立性假设降低对数据量的要求，尽管条件性假设并不正确，但是朴素贝叶斯仍然是一种有效的分类器。

算法延伸

  朴素贝叶斯分类器的延伸算法有半朴素贝叶斯分类器，贝叶斯网络等，详见西瓜书。