Machine Learning in Action Chapter 4

《机器学习实战》第四章朴素贝叶斯源码学习笔记及源码。

基于贝叶斯决策理论的分类方法

朴素贝叶斯特点：

• 优点：在数据较少的情况下仍然有效，可以处理多类别问题。
• 缺点：对于输入数据的准备方式较为敏感。
• 适用数据类型： 标称型数据。

贝叶斯：

此处使用的概率解释属于贝叶斯概率理论的范畴，该理论非常流行且效果良好。贝叶斯概率以18世纪的一位神学家Thomas Bayes的名字命名。贝叶斯概率引入先验知识和逻辑推理来处理不确定命题。另一种概率解释称为频数概率（frequency probability），它只从数据本身获得结论，并不考虑逻辑推理及先验知识。

贝叶斯理论简述

假设一个数据集由两类数据组成。用p1(x,y)表示数据点(x,y)属于类别1的概率，用p2(x,y)表示数据点(x,y)属于类别2的概率，可以用以下规则判断它的类别：

• 如果p1(x,y) > p2(x,y)，那么类别为1.
• 如果p2(x,y) > p1(x,y)，那么类别为2.

条件概率

条件概率的计算公式：

P(gray|bucketB) = P(gray and bucketB)/P(bucketB)

另一种计算条件概率的方法——贝叶斯准则，告诉我们如何交换条件概率中的条件与结果，即如果已知P(x|c)，要求P(c|x)，那么可以使用下面的计算方法：
$$ p(c|x)=\frac{p(x|c)p(c)}{p(x)} $$

使用条件概率来分类

应用贝叶斯准则得到公式：
$$ p(c_i)|x,y)=\frac{p(x,y|c_i)p(c_i)}{p(x,y)} $$

可以定义贝叶斯分类准则为：

• 如果$P(c_1|x,y)>P(c_2|x,y)$，那么属于类别$c_1$。
• 如果$P(c_1|x,y)<P(c_2|x,y)$，那么属于类别$c_2$。

使用朴素贝叶斯进行文档分类

朴素贝叶斯的一般过程：

1. 收集数据：可以使用任何方法。例子中使用rss源。
2. 准备数据：需要数值型或布尔型数据。
3. 分析数据：有大量特征时，绘制特征作用不大，此时使用直方图效果更好。
4. 训练方法：计算不同的独立特征的条件概率。
5. 测试算法：计算错误率。
6. 使用算法：一个常见的朴素贝叶斯应用是文档分类。可以在任意分类场景中使用朴素贝叶斯分类器，不一定非要是文本。

由统计学知，如果每个特征需要N个样本，那么对于10个特征将需要$N^{10}$个样本，对于包含1000个特征的词汇表将需要$N^{1000}$个样本。如果特征之间相互独立，即一个特征或则单词出现的可能性与它和其他单词相邻没有关系，那么样本数就可以从$N^{1000}$减少到$1000*N$。

使用Python进行文本分类

准备数据：从文本中构建词向量

词表到向量的转换函数，bayes.py:

#-*-coding:utf-8-*-

def loadDataSet():
    """
    创建一些实验样本。
    """
    postingList = [['my','dog','has','flea',\
            'problems','help','pleas'],
            ['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 代表正常言论
    return postingList, classVec

def createVocabList(dataSet):
    """
    创建一个包含在所有文档中出现的不重复词的列表。
    """
    vocabSet = set([])
    for document in dataSet:
        vocabSet = vocabSet | set(document)
    return list(vocabSet)

def setOfWords2Vec(vocabList,inputSet):
    """
    输入参数为词汇表及某个文档，输出的是文档向量，向量的每一
    元素为1或0,分别表示词汇表中的单词在输入文档中是否出现。
    """
    returnVec = [0]*len(vocabList) # 创建一个其中所有元素都为0的向量
    for word in inputSet:
        if word in vocabList:
            returnVec[vocabList.index(word)] = 1
        else:
            print "the word: %s is not in my Vocabulary!"%word
    return returnVec

训练算法：从词向量构建概率

$$ p(c_i|w)=\frac{p(w|c_i)p(c_i)}{p(w)} $$

使用上述公式，对每个类计算该值，然后比较两个概率值大小。

函数伪代码：

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

朴素贝叶斯分类器训练函数

def trainNB0(trainMatrix,trainCategory):
    """
    输入参数为文档矩阵以及由每篇文档类别标签所构成的向量。
    """
    # 获取文档数量
    numTrainDocs = len(trainMatrix)
    # 获取词数量
    numWords = len(trainMatrix[0])
    # 计算侮辱性文档概率
    pAbusive = sum(trainCategory)/float(numTrainDocs)
    # 初始化概率
    p0Num = zeros(numWords)
    p1Num = zeros(numWords)
    p0Denom = 0.0
    p1Denom = 0.0
    for i in range(numTrainDocs):
        if trainCategory[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,pAbusive

测试算法：根据现实情况修改分类器

def classifyNB(vec2Classify,p0Vec,p1Vec,pClass1):
    """
    vec2Classify: 要分类的向量
    p0Vec,p1Vec,pClass1：使用函数trainNB0计算的3个概率
    """
    p1 = sum(vec2Classify*p1Vec)+log(pClass1)
    p0 = sum(vec2Classify*p0Vec)+log(1.0-pClass1)
    if p1 > p0:
        return 1
    else:
        return 0

def testingNB():
    listOPosts,listClasses = loadDataSet()
    myVocabList = createVocabList(listOPosts)
    trainMat = []
    for postinDoc in listOPosts:
        trainMat.append(setOfWords2Vec(myVocabList,postinDoc))
    p0V,p1V,pAb = trainNB0(array(trainMat),array(listClasses))
    testEntry = ['love','my','dalmation']
    thisDoc = array(setOfWords2Vec(myVocabList,testEntry))
    print testEntry,'classified as: ',classifyNB(thisDoc,p0V,p1V,pAb)
    testEntry = ['stupid','garbage']
    thisDoc = array(setOfWords2Vec(myVocabList,testEntry))
    print testEntry,'classified as: ',classifyNB(thisDoc,p0V,p1V,pAb)

测试代码：

>>>import bayes
...
>>>bayes.testingNB()
...

准备数据：文档词袋模型

将每个词的出现与否作为一个特征，这可以被描述为词集模型(set-of-words model)。如果一个词在文档中出现不只一次，这可能意味着包含该词是否出现在文档中所不能表达的某种信息，这种方法称为词袋模型(bag-of-words model)。

朴素贝叶斯词袋模型：

def bagOfWrods2VecMN(vocabList,inputSet):
    returnVec = [0]*len(vocabList)
    for word in inputSet:
        if word in vocabList:
            returnVec[vocabList.index(word)] += 1
        return returnVec

示例：使用朴素贝叶斯过滤垃圾邮件

• 收集数据：提供文本文件。
• 准备数据：将文本文件解析成词条向量。
• 分析数据：检查词条确保解析的正确性。
• 训练算法：使用之前建立的trainNB0函数。
• 测试算法：使用classifyNB()，并且构建一个新的测试函数来计算文档集的错误率。
• 使用算法：构建一个完整的程序对一组文档进行分类，将错分的文档输出到屏幕上。

准备数据：切分文本

>>>mySent='This book is the best book on Python or M.L. I have ever laid eyes upon.'
>>>import re
>>>regEx=re.compile('\\W*')
>>>listOfTokens=regEx.split(mySent)
>>>[tok.lower() for tok in listOfTokens if len(tok)>0]
...
>>>emailText=open('email/ham/6.txt').read()
>>>listOfTokens=regEx.split(emailText)

测试算法：使用朴素贝叶斯进行交叉验证

文件解析及完整的垃圾邮件测试函数：

def textParse(bigString):
    """
    接受一个大字符串并将其解析为字符串列表。
    """
    import re
    listOfTokens = re.split(r'\w*',bigString)
    return [tok.lower() for tok in listOfTokens if len(tok)>2]

def spamTest():
    """
    对贝叶斯垃圾邮件分类器进行自动化处理。
    """
    import random
    docList = []; classList = []; fullText = []
    for i in range(1,26):
        wordList = textParse(open('chapter_4/email/spam/%d.txt' % i).read())
        docList.append(wordList)
        fullText.extend(wordList)
        classList.append(1)
        wordList = textParse(open('chapter_4/email/ham/%d.txt' % i).read())
        docList.append(wordList)
        fullText.extend(wordList)
        classList.append(0)
    vocabList = createVocabList(docList)
    trainingSet = range(50); testSet = []
    for i in range(10):
        randIndex = int(random.uniform(0,len(trainingSet)))
        testSet.append(trainingSet[randIndex])
        del(trainingSet[randIndex])
    
    trainMat = []; trainClasses = []
    for docIndex in trainingSet:
        trainMat.append(setOfWords2Vec(vocabList,docList[docIndex]))
        trainClasses.append(classList[docIndex])
    
    p0V,p1V,pSpam = trainNB0(array(trainMat),array(trainClasses))
    errorCount = 0
    for docIndex in testSet:
        wordVector = setOfWords2Vec(vocabList, docList[docIndex])
        if classifyNB(array(wordVector),p0V,p1V,pSpam) != classList[docIndex]:
            errorCount += 1
    print 'the error rate is: ',float(errorCount)/len(testSet)

示例：使用朴素贝叶斯分类器从个人广告中获取区域倾向

使用朴素贝叶斯来发现地域相关的用词

• 收集数据：从RSS源收集内容，此处需要对RSS源构建一个接口。
• 准备数据：将文本文件解析成词条向量。
• 分析数据：检查词条确保解析的正确性。
• 训练算法：使用我们之前建立的trainNB0函数。
• 测试算法：观察错误率，确保分类器可用。可以修改切分程序，以降低错误率，提高分类结果。
• 使用算法：构建一个完整的程序，封装所有内容。给定两个RSS源，该程序会现实最常用的公共词。

收集数据：导入RSS源

可以在http://code.google.com/p/feedparser/下载安装feedparser，然而ubuntu下最简单的安装方式是：

pip install feedparser

RSS源分类器及高频词去除函数。去除高频词可大大降低错误率，这些高频词称为停用词表(stop word list)。一个停用词表的资源网站http://www.rands.nl/stopwords，里面有中文停用词列表，^^。

def calcMostFreq(vocabList,fullText):
    """
    遍历词汇表中的每个词并统计它在文本中出现的次数，
    然后根据出现次数从高到底对词典进行排序，最后返回
    排序最高的30个单词。
    """
    import operator
    freqDict = {}
    for token in vocabList:
        freqDict[token] = fullText.count(token)
    sortedFreq = sorted(freqDict.iteritems(),key=operator.itemgetter(1),\
            reverse=True)
    return sortedFreq[:30]

def localWords(feed1,feed0):
    import feedparser
    docList = []; classList = []; fullText = []
    minLen = min(len(feed1['entries']),len(feed0['entries']))
    for i in range(minLen):
        # 每次访问一条RSS源
        wordList = textParse(feed1['entries'][i]['summary'])
        docList.append(wordList)
        fullText.extend(wordList)
        classList.append(1)
        wordList = textParse(feed0['entries'][i]['summary'])
        docList.append(wordList)
        fullText.extend(wordList)
        classList.append(0)
    vocabList = createVocabList(docList)
    # 去掉出现次数最高的那些词
    top30Words = calcMostFreq(vocabList,fullText)
    for pairW in top30Words:
        if pairW[0] in vocabList:
            vocabList.remove(pairW[0])
    trainingSet = range(2*minLen)
    testSet = []
    for i in range(20):
        randIndex = int(random.uniform(0,len(trainingSet)))
        testSet.append(trainingSet[randIndex])
        del(trainingSet[randIndex])
    trainMat = []; trainClasses = []
    for docIndex in trainingSet:
        trainMat.append(bagOfWords2VecMN(vocabList,docList[docIndex]))
        trainClasses.append(classList[docIndex])
    p0V,p1V,pSpam = trainNB0(array(trainMat),array(trainClasses))
    errorCount = 0
    for docIndex in testSet:
        wordVector = bagOfWords2VecMN(vocabList,docList[docIndex])
        if classifyNB(array(wordVector),p0V,p1V,pSpam)!=classList[docIndex]:
            errorCount += 1
    print 'the error rate is: ',float(errorCount)/len(testSet)
    return vocabList,p0V,p1V

分析数据：显示地域相关的用词

最具表征性的词汇显示函数

def getTopWords(ny,sf):
    import operator
    vocabList,p0V,p1V = localWords(ny,sf)
    topNY = []; topSF = []
    for i in range(len(p0V)):
        if p0V[i] > -6.0:
            topSF.append((vocabList[i],p0V[i]))
        if p1V[i] > -6.0:
            topNY.append((vocabList[i],p1V[i]))
    sortedSF = sorted(topSF,key=lambda pair:pair[1],reverse=True)
    print "SF**SF**SF**SF**SF**SF**SF**SF**SF**SF**SF**SF**SF**SF**"
    for item in sortedSF:
        print item[0]
    sortedNY = sorted(topNY,key=lambda pair:pair[1],reverse=True)
    print "NY**NY**NY**NY**NY**NY**NY**NY**NY**NY**NY**NY**NY**NY**"
    for item in sortedNY:
        print item[0]

小结

贝叶斯概率及贝叶斯概率准则提供了一种利用已知值估计未知概率的有效方法。可以通过特征之间的条件独立性假设，降低对数据量的需求。当然这个假设过于简单，这就是称为朴素贝叶斯的原因。

可通过对概率取对数解决下溢出问题。词袋模型在解决文档分类问题上比词集模型有所提高。移除停用词也是一个改进。