《统计学习方法》学习笔记（3）-- 朴素贝叶斯

1. 贝叶斯定理

　　英国数学家托马斯·贝叶斯（Thomas Bayes）在1763年发表的一篇论文中，首先提出了这个定理。

　　A，B表示在一个样本空间中的两个事件，在事件B发生的情况下，事件A发生的概率用P(A|B)表示，它等于事件A，B同时发生的概率除以事件B发生的概率。

　　因为：P(AB) = P(A|B) P(B) P(BA) = P(B|A) P(A)，所以：P(A|B) P(B) = P(B|A) P(A)，即

假设样本空间是A与A’的和（A’是A的补集），则P(B) = P(B∩A) + P(B∩A’)，代入贝叶斯定理即得全概率公式：P(B) = P(B|A)P(A) + P(B|A’)P(A’)，所以

2. 朴素贝叶斯方法

　　朴素贝叶斯方法是基于贝叶斯定理与特征条件独立假设的分类方法，之所以被称为朴素的（naive）是因为这种方法假设特征条件独立。对于给定的数据训练集，首先基于特征条件独立假设学习输入/输出的联合概率分布；然后基于此模型，对给定的输入x，求出后验概率最大的输出y。

　　训练数据集：

　　先验概率分布P(Y = c_k) k=1, 2, …, K 的条件概率分布

　　后验概率根据贝叶斯定理进行：

　　由于朴素贝叶斯方法对条件概率分布做了条件独立性的假设，所以有

　　这就是朴素贝叶斯分类法的基本公式。由于上式中分母对所有c_k都是相同的，于是贝叶斯分类器可表示为：

当某个特征项x^(j)没有出现划分时，会出现P(X^(j)= x^(j)|Y=c_k)=0的情况，这会影响后验概率的计算结果，解决这一问题的方式是采用贝叶斯估计：

S_j为x^(j)的取值个数，常取λ=1，这时称为拉普拉斯平滑。同样，先验概率的贝叶斯估计是：

　　　　　　 N为样本数量，K为c_k的取值个数。

3. 代码

#《统计学习方法》，例4.1，4.2代码
from numpy import *

def trainNB(dataList, labelList):
    dimension = len(dataList[0])
    dataSet = []                        
    for i in range(dimension):
        dataSetIdim = set([])
        for example in dataList:
            dataSetIdim = dataSetIdim | set([example[i]])
        dataSetIdim = list(dataSetIdim)
        dataSet.append(dataSetIdim)
    print(dataSet)

    p1Num = []; p0Num = []
    i=0
    for i in range(dimension):
        p0NumIdim = zeros(len(dataSet[i]))
        p1NumIdim = zeros(len(dataSet[i]))
        j=0
        for j in range(len(dataList)):
            flagList = zeros(len(dataSet[i]))
            flagList[dataSet[i].index(dataList[j][i])] = 1
            if labelList[j] == 1:
                p1NumIdim = p1NumIdim + flagList
            else:
                p0NumIdim = p0NumIdim + flagList
        p1NumIdim = list(p1NumIdim); p0NumIdim = list(p0NumIdim)
        p1Num.append(p1NumIdim)
        p0Num.append(p0NumIdim)
    print(p1Num, p0Num)
    return dataSet, p1Num, p0Num

def testingNB(testData, dataSet, p1Num, p0Num, num1, num0):
    p1 = num1/(num1+num0)
    p0 = num0/(num1+num0)
    for i in range(len(testData)):
        p1 = p1*(p1Num[i][dataSet[i].index(testData[i])]/num1)
        p0 = p0*(p0Num[i][dataSet[i].index(testData[i])]/num0)
    print("naive bayes: P(1)=",p1," P(0)=",p0)
    if(p1 > p0):
        str = "classefied as 1"
    else:
        str = "classified as 0"
    print(str)

def testingNBwithLS(testData, dataSet, p1Num, p0Num, num1, num0):  #with laplace smoothing
    p1 = (num1+1)/(num1+num0+2)
    p0 = (num0+1)/(num1+num0+2)
    for i in range(len(testData)):
        p1 = p1*((p1Num[i][dataSet[i].index(testData[i])]+1)/(num1+len(dataSet[i])))
        p0 = p0*((p0Num[i][dataSet[i].index(testData[i])]+1)/(num0+len(dataSet[i])))
    print("naive bayes with Laplace smoothing: P(1)=",p1," P(0)=",p0)
    if(p1 > p0):
        str = "classefied as 1"
    else:
        str = "classified as 0"
    print(str)
    
def test(testData=[2,'S']):
    dataList = [[1, 'S'],
                [1, 'M'],
                [1, 'M'],
                [1, 'S'],
                [1, 'S'],
                [2, 'S'],
                [2, 'M'],
                [2, 'M'],
                [2, 'L'],
                [2, 'L'],
                [3, 'L'],
                [3, 'M'],
                [3, 'M'],
                [3, 'L'],
                [3, 'L']]
    labelList = [0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0]
    
    dataSet, p1Num, p0Num = trainNB(dataList, labelList)
    num1 = labelList.count(1)
    num0 = labelList.count(0)
    testingNB(testData, dataSet, p1Num, p0Num, num1, num0)
    testingNBwithLS(testData, dataSet, p1Num, p0Num, num1, num0)

　　代码输出：

　　>>> import bayes
　　>>> bayes.test()
　　[[1, 2, 3], ['S', 'M', 'L']]
　　[[2.0, 3.0, 4.0], [1.0, 4.0, 4.0]] [[3.0, 2.0, 1.0], [3.0, 2.0, 1.0]]
　　naive bayes: P(1)= 0.0222222222222 P(0)= 0.0666666666667
　　classified as 0
　　naive bayes with Laplace smoothing: P(1)= 0.0326797385621 P(0)= 0.0610021786492
　　classified as 0

4. 扩展阅读：

贝叶斯推断及其互联网应用. http://www.ruanyifeng.com/blog/2011/08/bayesian_inference_part_one.html

数学之美番外篇：平凡而又神奇的贝叶斯方法. http://mindhacks.cn/2008/09/21/the-magical-bayesian-method/

分类算法之朴素贝叶斯分类. http://www.cnblogs.com/leoo2sk/archive/2010/09/17/1829190.html