朴素贝叶斯

基本概念

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

优点：在数据较少的情况下仍然有效，可以处理多类别问题。

缺点：对于输入数据的准备方式较为敏感。

适用数据类型：标称型数据。

关于朴素贝叶斯法的进一步介绍，可以参考这两篇博文：朴素贝叶斯分类器的应用和算法杂货铺——分类算法之朴素贝叶斯分类(Naive Bayesian classification)。

学习与分类算法

下面给出朴素贝叶斯法的学习与分类算法。

输入：训练数据集
$T=\left \{ (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N}) \right \}$
其中
$x_{i}=\left(x_{i}^{(1)},x_{i}^{(2)},...,x_{i}^{(n)}\right)^{T}$
$x_{i}^{(j)}$
是第i个样本的第j个特征

$x_{i}^{(j)}\epsilon \left \{ x_{j1},x_{j2},...,x_{jS_{j}} \right \}$
$a_{jl}$ 是第j个特征可能取得第l个值，j=1,2,…,n，l=1,2,…
$S_{j}$

$y_{i}\epsilon \left \{ c_{1},c_{2},...,c_{k}\right \}$
实例x；

输出：实例x的分类。

（1）计算先验概率及条件概率

$P\left ( Y=c_{k} \right )=\frac{\sum_{i=1}^{N}I(y_{i}=c_{k})}{N},k=1,2,...,K$

$P\left ( X^{j}=a_{jl}|Y=c_{k} \right )=\frac{\sum_{i=1}^{N}I(x_{i}^{(j)}=a_{jl},y_{i}=c_{k})}{\sum_{i=1}^{N}I(y_{i}=c_{k})}$

$j=1,2,...,n;l=1,2,...,S_{j};k=1,2,...,K$

（2）对于给定的实例
$x=(x^{(1)},x^{(2)},...,x^{(n)})^{T}$
计算

$P(Y=c_{k})\prod_{j=1}^{n}P(X^{(j)}=x^{j}|Y=c_{k}),k=1,2,...,K$

（3）确定实例x的类

$y=argmaxP(Y=c_{k})\prod_{j=1}^{n}P(X^{(j)}=x^{(j)}|Y=c_{k})$

贝叶斯估计

上述用的是极大似然估计，如果概率值为0的话，就会影响到结果，贝叶斯估计就是用来解决这个问题的，简单的说就是在分子和分母上加上常数，避免为0的情况。条件概率的贝叶斯估计是：

$P_{\lambda }(X^{(j)}=a_{jl}|Y=c_{k})=\frac{\sum_{i=1}^{N}I(x_{i}^{(j)}=a_{jl},y_{i}=c_{k})+\lambda }{\sum_{i=1}^{N}I(y_{i}=c_{k})+S_{j}\lambda }$

其中的$\lambda$=0时，就是极大似然估计。$\lambda$=1时，称为拉普拉斯平滑（Laplace smoothing）。

同样先验概率的贝叶斯估计是：

$P_{\lambda }(Y=c_{k})=\frac{\sum_{i=1}^{N}I(y_{i}=c_{k})+\lambda }{N+K\lambda }$

Python实现

初始化

# 创建实验样本
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代表侮辱性文字，0代表正常言论
    return postingList, classVec

# 创建一个包含在所有文档中出现的不重复词的列表
def createVocabList(dataSet):
    vocabSet = set([])
    for document in dataSet:
        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

训练算法

def trainNB0(trainMatrix, trainCategory):
    numTrainDocs = len(trainMatrix)
    numWords = len(trainMatrix[0])
    pAbusive = sum(trainCategory)/float(numTrainDocs)
    p0Num = np.ones(numWords); p1Num = np.ones(numWords)
    p0Denom = 2.0; p1Denom = 2.0
    for i in xrange(numTrainDocs):
        if trainCategory[i] == 1:
            p1Num += trainMatrix[i]
            p1Denom += sum(trainMatrix[i])
        else:
            p0Num += trainMatrix[i]
            p0Denom += sum(trainMatrix[i])
    p1Vect = np.log(p1Num/p1Denom)     # log防止下溢出
    p0Vect = np.log(p0Num/p0Denom)     
    return p0Vect, p1Vect, pAbusive

测试算法

def classifyNB(vec2Classify, p0Vec, p1Vec, pClass1):
    p1 = sum(vec2Classify * p1Vec) + np.log(pClass1)
    p0 = sum(vec2Classify * p0Vec) + np.log(1.0 - 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 =  trainNB0(np.array(trainMat), np.array(listClasses))
    testEntry = ['love', 'my', 'dalmation']
    thisDoc = np.array(setOfWords2Vec(myVocabList, testEntry))
    print testEntry, 'classified as: ', classifyNB(thisDoc, p0V, p1V, pAb)
    testEntry = ['stupid', 'garbage']
    thisDoc = np.array(setOfWords2Vec(myVocabList, testEntry))
    print testEntry, 'classified as: ', classifyNB(thisDoc, p0V, p1V, pAb)

参考文献

[1][机器学习实战]

[2][统计学习方法]