首页 > 代码库 > 初识分类算法(3)-----朴素贝叶斯算法
初识分类算法(3)-----朴素贝叶斯算法
1. 例子引入：如上篇的play or not 例子。
未知分类的样本：D:<A=sunny, B=cool, C=high ,D=strong>, 是 or 否？
我们要判断该样本的分类，即比较该样本属于是的概率大还是否的概率大 P(是/否|A=sunny, B=cool, C=high ,D=strong)
P(是|A=sunny, B=cool, C=high ,D=strong)=P(是，(A=sunny, B=cool, C=high ,D=strong))/P(A=sunny, B=cool, C=high,D=strong)
分母不变，转化为比较分子，P(是，(A=sunny, B=cool, C=high ,D=strong))=P(A=sunny, B=cool, C=high ,D=strong|是)*P(是)
=P(A=sunny|是)*P(B=cool|是)*P(C=high|是)*P(D=strong|是)*P(是)
P(是)=9/14 P(否)=5/14 
P(A=sunny|是)=2/5 P(A=sunny|否)=3/5
类似算出P(B=cool|是)，P(B=cool|否)，P(C=high|是)，P(C=high|否)，P(D=strong|是)，P(D=strong|否)。
那么该未知分类的样本属于是/否的概率分别是：
是： P(是)*P(A=sunny|是)*P(B=cool|是)*P(C=high|是)*P(D=strong|是)=？1
否：P(否)*P(A=sunny|否)*P(B=cool|否)*P(C=high|否)*P(D=strong|否)=？2
？1>?2,则该未知分类的样本输出是。
2. 朴素贝叶斯分类的原理与流程
朴素贝叶斯分类是一种十分简单的分类算法，叫它朴素贝叶斯分类是因为这种方法的思想真的很朴素，朴素贝叶斯 的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。通俗来说，就好比这么个 道理，你在街上看到一个黑人，我问你你猜这哥们哪里来的，你十有八九猜非洲。为什么呢？因为黑人中非洲人的比率最高，当然人家也可能是美洲人或亚洲人，但 在没有其它可用信息下，我们会选择条件概率最大的类别，这就是朴素贝叶斯的思想基础。
朴素贝叶斯分类的正式定义如下：
1、设为一个待分类项，而每个a为x的一个特征属性。
2、有类别集合。
3、计算。
4、如果，则
。
那么现在的关键就是如何计算第3步中的各个条件概率。我们可以这么做：
1、找到一个已知分类的待分类项集合，这个集合叫做训练样本集。
2、统计得到在各类别下各个特征属性的条件概率估计。即。
3、如果各个特征属性是条件独立的，则根据贝叶斯定理有如下推导：
因为分母对于所有类别为常数，因为我们只要将分子最大化皆可。又因为各特征属性是条件独立的，所以有：
根据上述分析，朴素贝叶斯分类的流程可以由下图表示（暂时不考虑验证）：
可以看到，整个朴素贝叶斯分类分为三个阶段：
第一阶段——准备工作阶段，这个阶段的任务是为朴素贝叶斯分类做必要的准备，主要工作是根据具体情况确定特征属性，并对每个特征属性进行适当划分，然后由 人工对一部分待分类项进行分类，形成训练样本集合。这一阶段的输入是所有待分类数据，输出是特征属性和训练样本。这一阶段是整个朴素贝叶斯分类中唯一需要 人工完成的阶段，其质量对整个过程将有重要影响，分类器的质量很大程度上由特征属性、特征属性划分及训练样本质量决定。
第二阶段——分类器训练阶段，这个阶段的任务就是生成分类器，主要工作是计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估 计，并将结果记录。其输入是特征属性和训练样本，输出是分类器。这一阶段是机械性阶段，根据前面讨论的公式可以由程序自动计算完成。
第三阶段——应用阶段。这个阶段的任务是使用分类器对待分类项进行分类，其输入是分类器和待分类项，输出是待分类项与类别的映射关系。这一阶段也是机械性阶段，由程序完成。
3.估计类别下特征属性划分的条件概率及Laplace校准
这一节讨论P(a|y)的估计。
由上文看出，计算各个划分的条件概率P(a|y)是朴素贝叶斯分类的关键性步骤，当特征属性为离散值时，只要很方便的统计训练样本中各个划分在每个类别中出现的频率即可用来估计P(a|y)，下面重点讨论特征属性是连续值的情况。
当特征属性为连续值时，通常假定其值服从高斯分布（也称正态分布）。即：
而
因此只要计算出训练样本中各个类别中此特征项划分的各均值和标准差，代入上述公式即可得到需要的估计值。均值与标准差的计算在此不再赘述。
另一个需要讨论的问题就是当P(a|y)=0怎么办，当某个类别下某个特征项划分没有出现时，就是产生这种现象，这会令分类器质量大大降低。为了解决这个 问题，我们引入Laplace校准，它的思想非常简单，就是对没类别下所有划分的计数加1，这样如果训练样本集数量充分大时，并不会对结果产生影响，并且 解决了上述频率为0的尴尬局面。
4. 朴素贝叶斯的实例应用， 并用python实现
4.1 从文本文档中构建自己的词列表
1 #-*-coding:utf-8-*-‘ 2 mysent=‘A man is not old until regrets take the place of dreams. (J. Barrymore)‘ 3 print mysent.split() 4 import re 5 regEX=re.compile(‘\\W*‘) # 使用正则表示式来切分句子，其中分隔符是除单词,数字外的任意字符串。 6 listoftokens=regEX.split(mysent) 7 print listoftokens 8 print [tok for tok in listoftokens if len(tok)>0] #去掉空字符串 9 print [tok.lower() for tok in listoftokens if len(tok)>0] #将字符串全部转为小写10 11 ####函数12 def textParse(bigString): #input is big string, #output is word list13 import re14 listOfTokens = re.split(r‘\W*‘, bigString)15 return [tok.lower() for tok in listOfTokens if len(tok) > 2]
先看一个简单的例子。
训练集是从聊天室里摘取的6句话，每句话都有一个标签0或者1，表示是否是辱骂信息（abusive or not abusive）。当然可以把每个消息看成是一个文档，只不过文档单词比这个多，但是一样的道理。
1 def loadDataSet(): 2 postingList=[[‘my‘, ‘dog‘, ‘has‘, ‘flea‘, ‘problems‘, ‘help‘, ‘please‘], 3 [‘maybe‘, ‘not‘, ‘take‘, ‘him‘, ‘to‘, ‘dog‘, ‘park‘, ‘stupid‘], 4 [‘my‘, ‘dalmation‘, ‘is‘, ‘so‘, ‘cute‘, ‘I‘, ‘love‘, ‘him‘], 5 [‘stop‘, ‘posting‘, ‘stupid‘, ‘worthless‘, ‘garbage‘], 6 [‘mr‘, ‘licks‘, ‘ate‘, ‘my‘, ‘steak‘, ‘how‘, ‘to‘, ‘stop‘, ‘him‘], 7 [‘quit‘, ‘buying‘, ‘worthless‘, ‘dog‘, ‘food‘, ‘stupid‘]] 8 classVec = [0,1,0,1,0,1] #1 is abusive, 0 not 9 return postingList,classVec10 listoposts,listclasses=loadDataSet()
4.3 现在有6个文档的词列表，并且有它们对应的分类，将词表合并。该函数返回一个由唯一单词组成的词汇表
1 def createVocabList(dataSet):2 vocabSet = set([]) #create empty set3 for document in dataSet:4 vocabSet = vocabSet | set(document) #union of the two sets5 return list(vocabSet)6 myvocablist=createVocabList(listoposts)
print len(myvocablist) #32
4.4 这个函数功能：输入词汇表和消息，通过逐个索引词汇表，然后看消息中的是否有对应的字在词汇表中，如果有就标记1，没有就标记0，这样就把每条消息都转成了和词汇表一样长度的有0和1组成的特征向量
1 def setOfWords2Vec(vocabList, inputSet): 2 returnVec = [0]*len(vocabList) 3 for word in inputSet: 4 if word in vocabList: 5 returnVec[vocabList.index(word)] = 1 6 else: print "the word: %s is not in my Vocabulary!" % word 7 return returnVec 8 #a1=setOfWords2Vec(myvocablist, listoposts[0]) 9 #print len(a1) #3210 #a6=setOfWords2Vec(myvocablist, listoposts[5])11 trainmat=[]12 for i in listoposts:13 trainmat.append(setOfWords2Vec(myvocablist, i))
4.5 首先计算P(class=1)，然后分别求出训练样本中，每一类：对每个元素除以该类别的总数，返回两个向量。P(a(i)|class=1),P(a(i)|class=0)
1 def trainNB0(trainMatrix,trainCategory): 2 numTrainDocs = len(trainMatrix) 3 print numTrainDocs 4 numWords = len(trainMatrix[0]) 5 print numWords 6 pAbusive = sum(trainCategory)/float(numTrainDocs) 7 print sum(trainCategory) 8 p0Num = ones(numWords); p1Num = ones(numWords) #change to ones() 9 p0Denom = 2.0; p1Denom = 2.0 #change to 2.010 for i in range(numTrainDocs):11 if trainCategory[i] == 1:12 p1Num += trainMatrix[i]13 p1Denom += sum(trainMatrix[i]) 14 else:15 p0Num += trainMatrix[i]16 p0Denom += sum(trainMatrix[i])17 p1Vect = log(p1Num/p1Denom) #change to log()18 p0Vect = log(p0Num/p0Denom) #change to log()19 return p0Vect,p1Vect,pAbusive20 p0v,p1v,pab=trainNB0(trainmat,listclasses)
上面的代码中输入的是特征向量组成的矩阵，和一个由标签组成的向量，其中pAbusive是类别概率P(ci)，因为只有两类，计算一类后，另外一类可以 直接用1-p得出。接下来初始化计算p(wi|c1)和p(wi|c0)的分子和分母，这里惟一让人好奇的就是为什么分母p0Denom和p1Denom 都初始化为2？这是因为在实际应用中，我们计算出了（公式三）右半部分的概率后，也就是p(wi|ci)后，注意wi表示消息中的一个字，接下来就是判断 整条消息属于某个类别的概率，就要计算p(w0|1)p(w1|1)p(w2|1)的形式，这样如果某个wi为0，这样整个概率都为0，或者都很小连乘后会更小，甚至round off 0。这样就会影响判断，因此把他们转到对 数空间中来做运算，对数在机器学习里经常用到，在保持单调的情况下避免因数值运算带来的歧义问题，而且对数可以把乘法转到加法运算，加速了运算。因此上面 的代码中把所 有的出现次数初始化为1，然后把分母初始为2，接着都是累加，在对数空间中从0还是1开始累加，最后比较大小不会受影响的。
4.6 对未知的分类样本testEntry = [‘love‘, ‘my‘, ‘dalmation‘] 和 testEntry = [‘stupid‘, ‘garbage‘] 进行测试
并且classifyNB函数：计算了
1 def classifyNB(vec2Classify, p0Vec, p1Vec, pClass1): 2 p1 = sum(vec2Classify * p1Vec) + log(pClass1) #element-wise mult 3 p0 = sum(vec2Classify * p0Vec) + log(1.0 - pClass1) 4 if p1 > p0: 5 return 1 6 else: 7 return 0 8 9 listOPosts,listClasses = loadDataSet()10 myVocabList = createVocabList(listOPosts)11 #print len(myVocabList)12 trainMat=[]13 for postinDoc in listOPosts:14 trainMat.append(setOfWords2Vec(myVocabList, postinDoc))15 p0V,p1V,pAb = trainNB0(array(trainMat),array(listClasses))16 testEntry = [‘love‘, ‘my‘, ‘dalmation‘]17 thisDoc = array(setOfWords2Vec(myVocabList, testEntry))18 print testEntry,‘classified as: ‘,classifyNB(thisDoc,p0V,p1V,pAb)19 testEntry = [‘stupid‘, ‘garbage‘]20 thisDoc = array(setOfWords2Vec(myVocabList, testEntry))21 print testEntry,‘classified as: ‘,classifyNB(thisDoc,p0V,p1V,pAb)
5. 朴素贝叶斯法属于生成方法，关键在于找到输入输出的联合分布，或者说确定联合分布的参数也就确定了联合分布。在特征条件独立的假设下，对每一个特征通过频率求解其条件概率分布，这些条件概率分布最终用于求解后验概率。根据后验概率来判断，选择P(Ci|X)最大的作为X的类别Ci,另外朴素贝叶斯只所以被称为朴素的原因是，它假设了特征之间都是独立的。可是，现实中往往特征之间不会是相互独立的，改进的做法：贝叶斯网络。
初识分类算法(3)-----朴素贝叶斯算法