朴素贝叶斯算法

超、凢脫俗 2022-03-15 14:14 363阅读 0赞

### 理论： ###

P(X|Y) = P(X,Y)/P(Y)

P(X,Y) = P(X|Y)P(Y)  
P(X,Y) = P(Y|X)P(X)

### 由此推导出朴素贝叶斯公式：   P(X|Y) = P(Y|X)P(X)/P(Y) ###

由此推导：

p(yi|X) = P(yi)p(X|yi)/P(X)

Y = 表示类别集合\{军事0、财经1、体育2\}  
yi = 表示第i个类别  
X = 一篇文章  
xi = 文章中的某一个词.

X=\{x1,x2,x3...\}  
分析：

1.P(yi)是先验概率，可以提前算出来的概率，举例

假设有100篇文章(训练集)，其中50篇是军事，30篇是财经，20篇体育  
P(y=军事) = 50/100  
P(y=财经) = 30/100  
P(y=体育) =20/100

2.P(X) = 常数，所以接下来计算，公式缩减为

### p(yi|X) = P(yi)p(X|yi) ###

p(X|yi)=p(xj)p(yi)=p(x=词一|y=类别1)p(x=词2|y=类别1)...

举例：

X=\{军舰、大炮、航母\}, y=军事

p(X|y=军事)=p(x=军舰|y=军事)\*p(x=大炮|y=军事)\*p(x=航母|y=军事)

而p(xj|yi) 的统计2种方法：

第一种：  
        分子：军事类文章中包含“谷歌”这词的文章个数  
        分母：军事类文章个数  
        P(x=谷歌|y=军事) = 分子 / 分母  
第二种（实践代码）：  
        分子：军事类文章中包含“谷歌”这个词的个数  
        分母：军事类文章中所有词的个数  
        P(x=谷歌|y=军事) = 分子 / 分母

举例：\{军事0、财经1、体育2\}  
p(y=0|X)  = 90%  
p(y=1|X)  = 1%  
p(y=2|X)  = 9%

### 实践：朴素贝叶斯 ###

### 第一步：格式转换，生成训练集和测试集   python DataConvert.py data/ nb\_data ###

1.数据：3607篇文章，各种类别，文件名有标识，分词已经分好的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4Mjg2MDI3_size_16_color_FFFFFF_t_70][]

![20190303133824903.png][]

直接用词做计算不方便，于是把每一个词变成一个数字，数字和词一一对应，如下：

![20190303133956871.png][]

第一条命令做数据转换，分为（80%）训练集和（20%）测试集，输出：

![20190303134039804.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4Mjg2MDI3_size_16_color_FFFFFF_t_70 1][]

实现代码  DataConvert.py：

import sys  
import os  
import random

WordList = \[\]  
WordIDDic = \{\}  
TrainingPercent = 0.8

inpath = sys.argv\[1\]  
OutFileName = sys.argv\[2\]  
trainOutFile = file(OutFileName+".train", "w")  
testOutFile = file(OutFileName+".test", "w")

def ConvertData():  
    i = 0  
    tag = 0  
    for filename in os.listdir(inpath):  
        if filename.find("business") != -1:  
            tag = 1  
        elif filename.find("auto") != -1:  
            tag = 2  
        elif filename.find("sport") != -1:  
            tag = 3  
        i += 1  
        rd = random.random()  
        outfile = testOutFile  
        if rd < TrainingPercent:  
            outfile = trainOutFile

if i % 100 == 0:  
            print i,"files processed!\\r",

infile = file(inpath+'/'+filename, 'r')  
        outfile.write(str(tag)+" ")  
        content = infile.read().strip()  
        content = content.decode("utf-8", 'ignore')  
        words = content.replace('\\n', ' ').split(' ')  
        for word in words:  
            if len(word.strip()) < 1:  
                continue  
            if word not in WordIDDic:  
                WordList.append(word)  
                WordIDDic\[word\] = len(WordList)  
            outfile.write(str(WordIDDic\[word\])+" ")  
        outfile.write("\#"+filename+"\\n")  
        infile.close()

print i, "files loaded!"  
    print len(WordList), "unique words found!"

ConvertData()  
trainOutFile.close()  
testOutFile.close()

![20190303134715438.png][]

做词做编号处理方法：

![20190303135219828.png][]

### 第二步：利用训练集，得到模型   python NB.py 1 nb\_data.train model ###

（1是训练，nb\_data.train训练数据，model是模型文件）

![20190303140500644.png][]

代码理解：第一步加载数据，第二步，生成模型参数，第三步，把参数保存

![20190303140906508.png][]

代码理解：

P(x=谷歌|y=军事)这种信息用这个代码（classFeaDic）维护。（每个类别出现的某个词的次数）

P(x=谷歌|y=军事)    =  ClassFeaDic——》（最大似然）——》ClassFeaProb

ClassFreq:用来做先验概率

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4Mjg2MDI3_size_16_color_FFFFFF_t_70 2][]

代码理解：

ClassFeatDic:计数

得到一个model（模型），模型里都是参数（p(yi),p(X|yi)）

实现代码：

NB.py:

#coding=utf8
    #Usage:
    #Training: NB.py 1 TrainingDataFile ModelFile
    #Testing: NB.py 0 TestDataFile ModelFile OutFile
    
    import sys
    import os
    import math
    
    
    DefaultFreq = 0.1
    TrainingDataFile = "nb_data.train"
    ModelFile = "nb_data.model"
    TestDataFile = "nb_data.test"
    TestOutFile = "nb_data.out"
    ClassFeaDic = {}
    ClassFreq = {}
    WordDic = {}
    ClassFeaProb = {}
    ClassDefaultProb = {}
    ClassProb = {}
    
    def Dedup(items):
        tempDic = {}
        for item in items:
            if item not in tempDic:
                tempDic[item] = True
        return tempDic.keys()
    
    def LoadData():
        i =0
        infile = file(TrainingDataFile, 'r')
        sline = infile.readline().strip()
        while len(sline) > 0:
            pos = sline.find("#")
            if pos > 0:
                sline = sline[:pos].strip()
            words = sline.split(' ')
            if len(words) < 1:
                print "Format error!"
                break
            # 类别号，分类标签:每条样本的第一列
            classid = int(words[0])
            if classid not in ClassFeaDic:
                # 记录每个类中的每个token的计数
                ClassFeaDic[classid] = {}
                # 记录每个token在各自类中的概率
                ClassFeaProb[classid] = {}
                # 记录每个类的文章个数
                ClassFreq[classid]  = 0
            ClassFreq[classid] += 1
            # 记录每篇文章的正文文本特征
            words = words[1:]
            #remove duplicate words, binary distribution
            #words = Dedup(words)
            for word in words:
                if len(word) < 1:
                    continue
                wid = int(word)
                if wid not in WordDic:
                    WordDic[wid] = 1
                if wid not in ClassFeaDic[classid]:
                    ClassFeaDic[classid][wid] = 1
                else:
                    ClassFeaDic[classid][wid] += 1
            i += 1
            sline = infile.readline().strip()
        infile.close()
        print i, "instances loaded!"
        print len(ClassFreq), "classes!", len(WordDic), "words!"
    
    
    def ComputeModel():
        sum = 0.0
        for freq in ClassFreq.values():
            sum += freq
        for classid in ClassFreq.keys():
            # p(yi)：先验概率：每个类的文章个数/总文章数
            ClassProb[classid] = (float)(ClassFreq[classid])/(float)(sum)
        # p(xj|yi)
        # 遍历每个类，针对每一个类，重构ClassFeaProb为概率值
        for classid in ClassFeaDic.keys():
            #Multinomial Distribution
            sum = 0.0
            for wid in ClassFeaDic[classid].keys():
                sum += ClassFeaDic[classid][wid]
            #newsum = (float)(sum+len(WordDic)*DefaultFreq)
            newsum = (float)(sum + 1)
            #Binary Distribution
            #newsum = (float)(ClassFreq[classid]+2*DefaultFreq)
            for wid in ClassFeaDic[classid].keys():
                ClassFeaProb[classid][wid] = (float)(ClassFeaDic[classid][wid]+DefaultFreq)/newsum
            ClassDefaultProb[classid] = (float)(DefaultFreq) / newsum
        return
    
    
    def SaveModel():
        outfile = file(ModelFile, 'w')
        for classid in ClassFreq.keys():
            outfile.write(str(classid))
            outfile.write(' ')
            outfile.write(str(ClassProb[classid]))
            outfile.write(' ')
            outfile.write(str(ClassDefaultProb[classid]))
            outfile.write(' ' )
        outfile.write('\n')
        for classid in ClassFeaDic.keys():
            for wid in ClassFeaDic[classid].keys():
                outfile.write(str(wid)+' '+str(ClassFeaProb[classid][wid]))
                outfile.write(' ')
            outfile.write('\n')
        outfile.close()
    
    
    def LoadModel():
        global WordDic
        WordDic = {}
        global ClassFeaProb
        ClassFeaProb = {}
        global ClassDefaultProb
        ClassDefaultProb = {}
        global ClassProb
        ClassProb = {}
        infile = file(ModelFile, 'r')
        sline = infile.readline().strip()
        items = sline.split(' ')
        if len(items) < 6:
            print "Model format error!"
            return
        i = 0
        while i < len(items):
            classid = int(items[i])
            ClassFeaProb[classid] = {}
            i += 1
            if i >= len(items):
                print "Model format error!"
                return
            ClassProb[classid] = float(items[i])
            i += 1
            if i >= len(items):
                print "Model format error!"
                return
            ClassDefaultProb[classid] = float(items[i])
            i += 1
        for classid in ClassProb.keys():
            sline = infile.readline().strip()
            items = sline.split(' ')
            i = 0
            while i < len(items):
                wid  = int(items[i])
                if wid not in WordDic:
                    WordDic[wid] = 1
                i += 1
                if i >= len(items):
                    print "Model format error!"
                    return
                ClassFeaProb[classid][wid] = float(items[i])
                i += 1
        infile.close()
        print len(ClassProb), "classes!", len(WordDic), "words!"
    
    def Predict():
        global WordDic
        global ClassFeaProb
        global ClassDefaultProb
        global ClassProb
    
        TrueLabelList = []
        PredLabelList = []
        i =0
        infile = file(TestDataFile, 'r')
        outfile = file(TestOutFile, 'w')
        sline = infile.readline().strip()
        # 存储最后的结果：针对每一类的概率值
        # p(yi|X) = p(yj)p(X|yi)
        # p(X|yi) = p(x0|yi)*...*p(xn|yi)
        scoreDic = {}
        iline = 0
        while len(sline) > 0:
            iline += 1
            if iline % 10 == 0:
                print iline," lines finished!\r",
            pos = sline.find("#")
            if pos > 0:
                sline = sline[:pos].strip()
            words = sline.split(' ')
            if len(words) < 1:
                print "Format error!"
                break
            classid = int(words[0])
            # 真实标签
            TrueLabelList.append(classid)
            words = words[1:]
            #remove duplicate words, binary distribution
            #words = Dedup(words)
            for classid in ClassProb.keys():
                scoreDic[classid] = math.log(ClassProb[classid])
            for word in words:
                if len(word) < 1:
                    continue
                wid = int(word)
                if wid not in WordDic:
                    #print "OOV word:",wid
                    continue
                for classid in ClassProb.keys():
                    if wid not in ClassFeaProb[classid]:
                        scoreDic[classid] += math.log(ClassDefaultProb[classid])
                    else:
                        scoreDic[classid] += math.log(ClassFeaProb[classid][wid])
            #binary distribution
            #wid = 1
            #while wid < len(WordDic)+1:
            #   if str(wid) in words:
            #       wid += 1
            #       continue
            #   for classid in ClassProb.keys():
            #       if wid not in ClassFeaProb[classid]:
            #           scoreDic[classid] += math.log(1-ClassDefaultProb[classid])
            #       else:
            #           scoreDic[classid] += math.log(1-ClassFeaProb[classid][wid])
            #   wid += 1
            i += 1
            maxProb = max(scoreDic.values())
            for classid in scoreDic.keys():
                if scoreDic[classid] == maxProb:
                    # 预测标签
                    PredLabelList.append(classid)
            sline = infile.readline().strip()
        infile.close()
        outfile.close()
        print len(PredLabelList),len(TrueLabelList)
        return TrueLabelList,PredLabelList
    
    def Evaluate(TrueList, PredList):
        accuracy = 0
        i = 0
        while i < len(TrueList):
            if TrueList[i] == PredList[i]:
                accuracy += 1
            i += 1
        # 准确率
        accuracy = (float)(accuracy)/(float)(len(TrueList))
        print "Accuracy:",accuracy
    
    def CalPreRec(TrueList,PredList,classid):
        correctNum = 0
        allNum = 0
        predNum = 0
        i = 0
        while i < len(TrueList):
            if TrueList[i] == classid:
                allNum += 1
                if PredList[i] == TrueList[i]:
                    correctNum += 1
            if PredList[i] == classid:
                predNum += 1
            i += 1
        return (float)(correctNum)/(float)(predNum),(float)(correctNum)/(float)(allNum)
    
    #main framework
    if len(sys.argv) < 4:
        print "Usage incorrect!"
    elif sys.argv[1] == '1':
        print "start training:"
        TrainingDataFile = sys.argv[2]
        ModelFile = sys.argv[3]
        LoadData()
        ComputeModel()
        SaveModel()
    elif sys.argv[1] == '0':
        print "start testing:"
        TestDataFile = sys.argv[2]
        ModelFile = sys.argv[3]
        TestOutFile = sys.argv[4]
    
        LoadModel()
        TList,PList = Predict()
        i = 0
        outfile = file(TestOutFile, 'w')
        while i < len(TList):
            outfile.write(str(TList[i]))
            outfile.write(' ')
            outfile.write(str(PList[i]))
            outfile.write('\n')
            i += 1
        outfile.close()
        Evaluate(TList,PList)
        for classid in ClassProb.keys():
            pre,rec = CalPreRec(TList, PList,classid)
            print "Precision and recall for Class",classid,":",pre,rec
    else:
        print "Usage incorrect!"

第三步：模型的产生：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4Mjg2MDI3_size_16_color_FFFFFF_t_70 3][]

代码：如何将最大似然变成概率：ClassFeaDic——》（最大似然）——》ClassFeaProb

代码理解：第一个sum为总文章数，第二个sum为某个类的所有词的总数,ClassFeaDic\[classid\]\[wid\]为某个类某个词的数目，所以ClassFeaProb为某个类出现某个词的概率

### 第三步：利用测试机，评估模型效果   python NB.py 0 nb\_data.test model out ###

预估结果：

![20190303150308545.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4Mjg2MDI3_size_16_color_FFFFFF_t_70]: /images/20220315/ac96236904f448a79d8b611131d3157b.png
[20190303133824903.png]: /images/20220315/197fae0f80a14c04b80d83a8f4c74e54.png
[20190303133956871.png]: /images/20220315/a2d71b27c0634b70a5b7de632404d170.png
[20190303134039804.png]: /images/20220315/70d67d00b4b84338878a124acd5699fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4Mjg2MDI3_size_16_color_FFFFFF_t_70 1]: /images/20220315/c756099994824cf397579664464e3493.png
[20190303134715438.png]: /images/20220315/303aa78a972d410098b0ba640682cc3b.png
[20190303135219828.png]: /images/20220315/33b13d485e544735a43aa336fc6458f1.png
[20190303140500644.png]: /images/20220315/322d995ab4234c91b39303c6eeca0e37.png
[20190303140906508.png]: /images/20220315/ef027728232a45898344596053db2a84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4Mjg2MDI3_size_16_color_FFFFFF_t_70 2]: /images/20220315/07a2cc3141cc412c843fed3f07ade5bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4Mjg2MDI3_size_16_color_FFFFFF_t_70 3]: /images/20220315/093b172dc27b46b89c855592ca3e803b.png
[20190303150308545.png]: /images/20220315/873b8b49a2164056a629342ac2220fef.png