机器学习3——朴素贝叶斯

摘要：贝叶斯是基于概率论的分类方法，通过概率的方式来描述对象划分到某个分类的可能性。对象有多个属性假设各个属性之间是相互独立的，求解在出现的条件下各个类别出现的概率，选择最大的作为的分类，通过这种方法构造的分类算法称为朴素贝叶斯。

贝叶斯是基于概率论的分类方法，通过概率的方式来描述对象划分到某个分类的可能性。对象X有多个属性$$X={a_{1}, a_{2}, a_{3}, ... , a_{n}}$$假设各个属性之间是相互独立的，求解在X出现的条件下各个类别 $$C_{i}$$出现的概率，选择最大的 $$P(C_{i}|X) $$作为X的分类，通过这种方法构造的分类算法称为朴素贝叶斯。

假设为Ω实验E的样本空间，B为E的一组事件，满足
$$B_{i}B_{j}=B_{i}cap B_{j}=phi, i,j=1,2,3,...,n $$
$$B_{1}cup B_{2} cup ... cup B_{n}=Omega$$
则称B为样本空间Ω的一个划分。假设A为E的一个事件，由全概率公式得:
$$P(A)=P(A|B_{1})P(B_{1})+P(A|B_{2})P(B_{2})+...+P(A|B_{n})P(B_{n})=sum_{i=1}^{n}P(A|B_{i})P(B_{i})$$
证明：
$$A=AOmega=Acap(B_{1}cup B_{2} cup ... cup B_{n})=AB_{1}cup AB_{2}cup...cup AB_{n}$$
$$P(ab)=P(a)P(b|a)=P(b)P(a|b),P(a)>0,P(b)>0$$
$$=>P(A)=P(B_{1})P(A|B_{1})+P(B_{2})P(A|B_{2})+...+P(B_{n})P(A|B_{n})$$

P(A|B)表示在事件B发生的前提下，事件A发生的概率，公式表示为：
$$P(A|B)=frac{P(AB)}{P(B)}$$

P(B|A)是根据A参数值判断对象属于类别B的概率，称为后验概率。P(B)是直接判断某个样本属于类别B的概率，称为先验概率。P(A|B)是在类别B中观测到A的概率，P(A)是在数据集中观测到A的概率，则有：
$$P(B|A)=frac{P(A|B)P(B)}{P(A)}$$
公式的证明很简单，参考条件概率公式。于是有:
$$=>P(B_{i}|A) = frac{P(A|B_{i})P(B_{i})}{P(A)} = frac{P(A|B_{i})P(B_{i})}{sum_{i=1}^{n}P(B_{i})P(A|B_{i})}$$
对于朴素贝叶斯，对象的各个特征值相互独立，则有：
$$=>P(A|B_{i}) = P(a_{1}|B_{i})P(a_{2}|B_{i})...P(a_{n}|B_{i})=prod_{k=1}^{n}P(a_{k}|B_{i})$$
$$=>P(B_{i}|A) = frac{prod_{k=1}^{n}P(a_{k}|B_{i})P(B_{i})}{sum_{i=1}^{n}P(B_{i})prod_{k=1}^{n}P(a_{k}|B_{i})}$$

设X={a1, a2, a3, ..., an}为一个待分类项，每个a为X的一个特征属性，特征属性彼此独立

设C={c1, c2, c3, ..., cn}为样本类别集合

计算P(c1|X)P(c2|X)P(c3|X)...P(cn|X)

计算P(ck|X) = max{P(c1|X), P(c2|X), P(c3|X), ..., P(cn|X)}，则X属于类别ck

数据集：

age | income | student | credit_rating | buy_computer
-----------------------------------------------------
<=30   high      no          fail            no
<=30   high      no          good            no
31-40  high      no          fail            yes
>40   medium     no          fail            yes
>40    low       yes         fail            yes
>40    low       yes         good            no
31-40  low       yes         good            yes
<=30  medium     no          fail            no
<=30   low       yes         fail            yes
>40   medium     yes         fail            yes
<=30  medium     yes         good            yes
31-40 medium     no          good            yes
31-40  high      yes         fail            yes
>40   medium     no          good            no

待分类样本：
<=30  medium     yes         fail            ?

样本特征属性：a1=age、a2=income、a3=student、a4=credit_rating

类别属性：buy_computer={"c1": "yes", "c2": "no"}

计算每个类的先验概率：
$$P(c_{1})=9/14，P(c_{2})=5/14$$
计算每个属性对于每个类别的条件概率:
P(age = "<=30" | buy_computer = "yes") = 2/9
P(income = "medium" | buy_computer = "yes") = 4/9
P(student= "yes" | buy_computer = "yes") = 6/9
P(credit_rating = "fail" | buy_computer = "yes") = 6/9

P(age = "<=30" | buy_computer = "no") = 3/5
P(income = "medium" | buy_computer = "no") = 2/5
P(student= "yes" | buy_computer = "no") = 1/5
P(credit_rating = "fail" | buy_computer = "no") = 2/5

计算条件概率P(X|Ci)：
P(X|buy_computer="yes") = 2/9 × 4/9 × 6/9 × 6/9 = 0.044
P(X|buy_computer="no") = 3/5 × 2/5 × 1/5 × 2/5 = 0.019

计算每个类的P(X|Ci)P(Ci)：
P(X|buy_computer="yes")P(buy_computer="yes") = 0.044 × 9/14 = 0.028
P(X|buy_computer="no")P(buy_computer="no") = 0.019 × 5/14 = 0.007

判定分类：
max(P(buy_computer="yes"|X), P(buy_computer="no"|X))=max{P(X|buy_computer="yes")P(buy_computer="yes"), P(X|buy_computer="no")P(buy_computer="no")} = 0.028
分类结果为buy_computer="yes"

要从文本中获取特征，需要先拆分文本。这里的特征是来自文本的词条（token），一个词条是字符的任意组合。将每个文本片段表示为一个词条向量，其中值为1表示词条出现在文档中，0表示词条未出现。

准备数据：将文本片段切分成一系列词条集合，每个文本片段人工标记为：贬义文字和正常文字。

postList = [["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表示正常文字

构建词向量：

def createVocabList(dataSet):
    vocabSet = set([])
    for document in dataSet:
        vocabSet = vocabSet | set(document)  # 两个集合的并集
    return list(vocabSet)
    
def Words2Vec(vocabList, inputSet):
    returnVec = [0]*len(vocabList)
    for word in inputSet:
        if word in vocabList:
            returnVec[vocabList.index(word)] = 1
    return returnVec

createVocabList函数将所有文本片段的词条组成一个不含重复元素的集合。作为一个无序的集合，set不记录元素位置或者插入点，所以每次的返回结果都不一样。
测试：

vocabList = createVocabList(postList)
print(vocabList)
print(words2Vec(vocabList, postList[0]))

=> ["take", "flea", "stop", "my", "mr", "food", "how", "worthless", "love", "not", "I",
 "help", "steak", "buying", "stupid", "has", "is", "licks", "dalmation", "dog", "him", 
"so", "ate", "garbage", "quit", "cute", "posting", "problems", "to", "maybe", "park", "please"]
=> [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]

根据词向量计算概率：
流程如下：

计算每个类别中的文档数目
对每个训练文档片段：
    对每个类别：
        如果词条出现在文档中 → 增加该词条的计数
        增加所有词条的计数
    对每个类别：
        对每个词条：
            将该词条的数目除以总词条数目得到条件概率
    返回每个类别的条件概率

# 朴素贝叶斯分类器训练函数
def trainNB(trainMatrix, trainClass):  
    numTrainDocs = len(trainMatrix)  # 训练文档的个数
    numWords = len(trainMatrix[0])  # 每个文档的词条个数
    pNagtive = sum(trainClass) / float(numTrainDocs)
    p0Num = zeros(numWords)
    p1Num = zeros(numWords)
    p0Denom = 0.0
    p1Denom = 0.0
    for i in range(numTrainDocs):
        if trainClass[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, pNagtive 

测试：

vocabList = createVocabList(postList)
trainMat = []
for postinDoc in postList:
    trainMat.append(Words2Vec(vocabList, postinDoc))
p0V, p1V, pNa = trainNB(trainMat, classVec)

=> pNa = 0.5
=> p1V = [0.05263158 0.         0.05263158 0.         0.         0.05263158
          0.         0.10526316 0.         0.05263158 0.         0.
          0.         0.05263158 0.15789474 0.         0.         0.
          0.         0.10526316 0.05263158 0.         0.         0.05263158
          0.05263158 0.         0.05263158 0.         0.05263158 0.05263158
          0.05263158 0.        ]
=> p0V = [0.         0.04166667 0.04166667 0.125      0.04166667 0.
          0.04166667 0.         0.04166667 0.         0.04166667 0.04166667
          0.04166667 0.         0.         0.04166667 0.04166667 0.04166667
          0.04166667 0.04166667 0.08333333 0.04166667 0.04166667 0.
          0.         0.04166667 0.         0.04166667 0.04166667 0.
          0.         0.04166667]

文档属于贬义类的概率 pNa = 0.5，计算正确；词汇表的第一个词是 take，take 在类别1出现1次，在类别0出现0次，对应的条件概率 0.05263158 > 0，计算正确；p1V中最大的概率值是 p1V[14] = 0.15789474，对应的词汇为vocabList[14] = "stupid"，这意味着"stupid"是最能表征类别1的词条。

构建分类函数
在计算P(w|c)时，如果其中一个概率为0，则最后的乘积也为0。为降低这种影响，所有词的出现次数初始化为1，并将分母初始化为2，即修改trainNB函数代码：

p0Num = ones(numWords)
p1Num = ones(numWords)
p0Denom = 2.0
p1Denom = 2.0

同时，为了避免多个小数想成结果太小，造成下溢，对p1Vect和p0Vect取对数

p1Vect = log(p1Num / p1Denom)  # 正常文档条件概率
p0Vect = log(p0Num / p0Denom)  # 贬义文档条件概率

构造分类函数：

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

算法逻辑简单，易于实现；

分类过程时空开销少；

算法稳定；

特征属性是非连续的，如果是连续的需要特殊处理；

特征属性是相互独立，现实中很难满足，对于互相联系的特征需要特殊处理；

这个编辑器的行内公式$xxx$无效啊，4个$可成功嵌入独立一行的公式，参考latex公式编写

python集合（set）类型的操作

十大经典算法朴素贝叶斯

机器学习实战第4章