朴素贝叶斯分类

原理

　　贝叶斯最基本的思想就是条件概率公式+条件独立假设+贝叶斯估计。

　　因为条件假设是一个较强的假设，因此称作朴素贝叶斯法。

　　它的思想有点类似于奥卡姆剃刀原理，举个例子，当前眼前走过一个黑人的时候，为你他是那里人，你第一眼想到的是他是个非洲人。因为非洲人普遍皮肤黑。

　　贝叶斯分类思想与此类似，当问你某个数据实例属于某个类别时候，会先去求各个类别下出现该数据实例的概率是多少，那个类别下概率越大，就分为哪个类别。

　　条件概率公式：

P(xy) = P(y|x)*P(x) = P(x|y)*P(y)...............(1)

=> P(y|x) = P(x|y)*P(y) / P(x).................(2)

　　　　条件概率P(y|x)就是我们朴素贝叶斯模型要求解的给定特征向量x下，预测x的类别y。

　　　　那么公式(2)右边的概率怎么求呢？贝叶斯做了个很朴素的假设——条件独立性假设

　　条件独立性假设：

　　当随机变量x是相互独立的随机变量组成的时候，P(x) = P(x1)*...*P(xn)

　　因此公式(2)中的P(x|y)等价于：

P(x|y) = P(x1|y)*...*P(xn|y).......................(3)

　　由公式(2)和公式(3)得到:

P(y|x) = P(x1|y)*...*P(xn|y)*P(y) / P(x).......(4)

　　这里x就是我们的训练集中的特征向量，y是我们要预测的分类类别。

　　期望风险最小化

　　对于给定特征向量x，它的类别为Yc，

　Yc = max i { P(yi|x) } .............................(5)

　　即求解最大条件概率P(yi|x)的yi作为分类类别。

　　根据公式(4)，公式(5)可以转化为：

Yc = max i { P(x1|yi)*...*P(xn|yi)*P(yi) / P(x) }........(6)

　　由于等式右边的分母P(x)对于每个yi都有且一样，所以只用计算

Yc = max i { P(x1|yi)*...*P(xn|yi)*P(yi) }..................(7)

　　其中：

　　　　　　P(yi)是每个类别的概率

　　　　　　条件概率P(xj|yi)是每个类别yi下，特征分量xj的条件概率

　　所以贝叶斯分类模型的训练只要计算好以下两个概率：

各个类别yi的概率P(yi)
各个类型yi下每个特征xj取各个值的概率P(xj|yi)

　　贝叶斯估计：

　　对于上面结论中所说的概率我们怎么计算呢？

　　一般对于概率的计算我们用估计法，计算的概率也叫先验概率。

　　最常见的估计法就是：极大似然估计，就是用频率去估计概率

　　但是存在一个问题，当频率为0的时候概率也为0，这意味着训练集中特征分量xj某一取值没有出现，我们就武断的认为他的概率为0，后面都不会出现了，这显然不是我们想要的，所以需要平滑。

　　并且，当某个特征分量频率为0的时候，整个条件概率P(xj|yi)累乘也等于0，这也不是我们想要的。当然这个问题可以在解决下溢出问题时候对条件概率P(xj|yi)取对数而解决。

　　贝叶斯估计就是在频率计算的时候，分子加上一个常数入，分母则加上|xj|入。其中|xj|是特征分量xj可能取值的个数，分子加上常数是为了平滑，分母加上常数是为了xj取各个值的概率和依然为1

　　当常数入等于0的时候，就是极大似然估计。

　　当常数入等于1的时候，就是著名的拉普拉斯平滑。

Python实现

　　在Python中可以用嵌套字典这样表示模型训练要求的概率P(xi=val|Yi)：

　　其中yi是各个类别，fi是当前类别yi下每一个特征，val是当前特征fi下的取值，pi是fi取值为pi的频率。有点绕口。。。

　　可以按照上面的数据结构，依次按yi、fi划分数据集，其实就是按行在按列切分数据集，然后求fi取各个值的概率。

　　上图中收入是预测的类别变量，后面三个是特征变量，对应求解过程就是，先按类别变量收入排序(划分数据)，然后求收入yi=高(低)的时候，特征变量fi=能力(学历、性别)时候，取值val=高(中、低)的概率。概率用频率来估计。

#coding=uft-8
import os, sys
from math import *
import time

#load dataSet
def loadData(filePath):
    dataSet = []
    with open(filePath) as fin:
        for line in fin:
            label_feats = line.strip().split('	')
            #print label_feats
            dataSet.append(label_feats)
    labelList = [i[0] for i in dataSet]
    uniqLabel = list(set(labelList))
    featuresNum = len(dataSet[0][1:])
    features = []
    for i in range(featuresNum):
        features.append('f'+str(i+1))
    #print uniqLabel
    #print features
    return dataSet,uniqLabel,features

def calcPOfLabels(dataSet, labels):
    pOfLabels = []
    total = len(dataSet)
    labelList = [example[0] for example in dataSet]
    labelsKinds = len(labels)
    for i in range(labelsKinds):
        pOfLabels.append(labelList.count(labels[i]))
        #pOfLabels[i] /= float(total)    #laplacian correction
        pOfLabels[i] = (pOfLabels[i] + 1) / (float(total) + labelsKinds)
        print pOfLabels[i]
    return pOfLabels

def getYi_Fi_ConditionP(subColumn, colIndex):
    yi_fi = {}
    uniqCol = set(subColumn)
    total  = len(subColumn)
    for val in uniqCol:
        pinlv = 0
        for d in subColumn:
            if(d == val):
                pinlv += 1
        #yi_fi[val] = float(pinlv) / total    #'192':p
        if(colIndex != 10):
            yi_fi[val] = (float(pinlv) + 1)/ (total + 256)    #laplacian correction
        else:
            yi_fi[val] = (float(pinlv) + 1)/ (total + 15672)    #laplacian correction
    return yi_fi

def getYi_Fs_ConditionP(subSet, features):
    yi_fs = {}
    for f in features:
        col = features.index(f) + 1            #subSet first col is label 
        subColumn = [d[col] for d in subSet]        #split subSet with feature
        yi_fs[f] = getYi_Fi_ConditionP(subColumn, col)    #fi:{'192':0.2, '202':0.4}
    return yi_fs

def getYs_Fs_ConditionP(dataSet, labels, features):
    conditionP = {}
    for yi in labels:
        subSet = []    #split dataSet with yi
        for d in dataSet:
            if(d[0] == yi):
                subSet.append(d)
        conditionP[yi] = getYi_Fs_ConditionP(subSet, features)    #yi:{'f1':{}, 'f2':{}}，依次构建字典
    return conditionP

if(len(sys.argv) < 2):
    print 'Usage xxx.py trainDataFile'
    sys.exit()
t1 = time.time()
dataSet, labels, features = loadData(sys.argv[1])
pOfLabels = calcPOfLabels(dataSet, labels)
ys_fs_conditionP = getYs_Fs_ConditionP(dataSet, labels, features)
print pOfLabels
print ys_fs_conditionP
t2 = time.time()
print t2 - t1

　　得到P(xi|Yi)就可以求解当前数据实例条件下各个类别的条件概率，以此来预测分类。

　　ps:

　　1、代码实现过程中要注意拉普拉斯平滑。因为按照yi划分数据集后，可能某个特征的取值val不在当前类别的划分中；

　　　虽然不在，但是我们不能不去求P(xi=val|Yi)的概率啊(测试集中可能会出现)，而且也不能直接让P(xi=val|Yi)=0，需要用拉普拉斯平滑。

　　　即让每个取值val都+1，那么分母也要加N，N是val的取值个数，这样可以保证概率和还是为1

　　　上面的代码val取值不存在我就没有计算它的概率，我是在预测的时候计算了拉普拉斯平滑后的概率。

　　2、写了决策树和贝叶斯分类模型，感觉都是对数据集划分，然后用频率估计概率。重要的是怎么构建求解结果的数据结构。

　　参考文献：李航《统计学习方法》

　　　　　　　周志华《机器学习》

　　　　　　　王斌《机器学习实战》