前言

概率论是许多机器学习算法的基础,理解并使用概率论就显得十分重要。本文给出一个使用概率论分类的方法 - 朴树贝叶斯,并写出一个最简单的贝叶斯分类器, 完成这个分类器后可以对概率分类器有一个更好的理解。

Bayes

Source: WikiPedia
In probability theory and statistics, Bayes’ theorem (alternatively Bayes’ law or Bayes’ rule) describes the probability of an event, based on prior knowledge of conditions that might be related to the event. For example, if cancer is related to age, then, using Bayes’ theorem, a person’s age can be used to more accurately assess the probability that they have cancer, compared to the assessment of the probability of cancer made without knowledge of the person’s age.

贝叶斯引入先验知识和逻辑推理来处理不确定命题。

概率分类器原理

分类问题

分类问题可以看做构造分类器。

已知集合$I= \{ y_1,y_2,…,y_n \}$、$ C= \{ y_1,y_2,…,y_n \} $,映射规则$y=f(x)$, 使得$\forall x_i\in I$有且仅有一个$y_j\in C$使得$y_j=f(x_i)$成立。(不考虑模糊数学里的模糊集情况)

其中,$C$为类别集合,每一个元素是一个类别,而$I$为项集合,每一个元素是一个待分类项,$f$为分类器。

概率分类

简单来说,使用概率分类就是,计算每一个待分类项属于某一项的概率,最后使用最大概率作为此项的类别。

贝叶斯分类器

贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。
如果已知$ P(B|A) $, 求$P(A|B)$, 那么贝叶斯准则告诉我们可以通过以下方式计算:
$$p(A|B) = \frac{p(B|A)p(A)}{p(B)}$$

贝叶斯定理之所以很有用,就是生活中经常遇到,很容易甚至直接得出$ P(B|A) $的概率,但是$P(A|B)$的概率就非常困难,并且我们也关心这个概率,那么就可以方便的使用贝叶斯定理。

朴素贝叶斯

朴素贝叶斯分类器通常有两种实现方式:一是基于贝努力模型,二是基于多项式模型实现。有两个假设:假设一是特征之间相互独立,假设二是每个特征权重相等。

理论上,朴素贝叶斯是一个条件概率模型:
设$A=\{a_1,a_2,…,a_n\}$为待分类项, 其中a为A项的独立特征,有类别集合$C=\{c_1,c_2,…,c_n\}$, 分别计算$P(c_1|A),P(c_2|A),…,P(c_n|A)$的概率, 若$P(c_k|A)=max\{P(c_1|A),P(c_2|A),…,P(c_n|A)\}$, 则说$A \in k$类.
然后,统计各个特征在各个类别下的概率,即:
$$P(a_1|c_1),P(a_2|c_1),…P(a_n|c_1) ;\\
P(a_1|c_2),P(a_2|c_2),…P(a_n|c_2) ; \\
P(a_1|c_3),P(a_2|c_3),…P(a_n|c_3) .$$

根据贝叶斯定理有
$$P(c_i|A) = \frac{P(A|c_i)p(c_i)}{P(A)}$$

因为分母对于所有类别为常数,又根据假设一,所以有:
$$P(A|c_i)p(c_i)=P(a_1|c_i),P(a_2|c_i),…P(a_n|c_i)P(c_i)$$

$$=\prod_{j=1}^{n}P(a_j|c_i)P(c_i)$$

编写一个简单的朴树贝叶斯分类器

这个例子来自于《Mechina Learning in Action》 源码可以在这里获取:https://github.com/pbharrin/machinelearninginaction/blob/master/Ch04/bayes.py.

准备数据

  1. 我们先准备好一些数据,主要这次使用的斑点犬爱好者的留言板, 并且已经标注出是侮辱性(1)还是非侮辱性的语句(0)。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def loadDataSet():
    postingList=[['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 is abusive, 0 not
    return postingList,classVec
  2. 统计所有出现的词,构建一个字典Set

    1
    2
    3
    4
    5
    def createVocabList(dataSet):
    vocabSet = set([]) #create empty set
    for document in dataSet:
    vocabSet = vocabSet | set(document) #union of the two sets
    return list(vocabSet)
  3. 根据构建好的字典,生成向量。将生成一个与字典长度一样的所有元素为0的向量,将句子中出现的单词的位置标注为1,表示为出现。

    1
    2
    3
    4
    5
    6
    7
    def setOfWords2Vec(vocabList, inputSet):
    returnVec = [0]*len(vocabList)
    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

训练算法

根据字典长度生成同样长度的元素为1的初始化向量,遍历每一条评论的所有词,如果某词出现就在向量对应就+1,统计完所有词后除以词条评论的总次数,获得词频概率。
训练算法后获得三个返回值,包括非侮辱性词出现的概率向量、侮辱性词出现的概率向量。

特别需要注意的:

  1. 计算多个概率的乘积时,如果出现某个类别为0,那么结果也为0。为了避免这种影响,将生成1的初始向量,并将分母改成2(出现和不出现都是0.5)。
  2. 由于概率都是0以下数,因子非常小,导致乘积结果也非常小,导致程序下溢出或者得不到正确答案,采用对乘积取自然对数的方法避免。($f(x)$与$ln(f(x))$图像相似,$x$取值范围是$[0,0.5]$)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def trainNB0(trainMatrix,trainCategory):
numTrainDocs = len(trainMatrix)
numWords = len(trainMatrix[0])
pAbusive = sum(trainCategory)/float(numTrainDocs)
p0Num = ones(numWords); p1Num = ones(numWords) #change to ones()
p0Denom = 2.0; p1Denom = 2.0 #change to 2.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 = log(p1Num/p1Denom) #change to log()
p0Vect = log(p0Num/p0Denom) #change to log()
return p0Vect,p1Vect,pAbusive

测试算法

先构建分类器。根据各个特征互相独立的假设,将待验证项的各个特征向量化与训练好的概率向量点乘,在将其结果乘以这个类别的概率获得最终的概率,比较每个类比概率的大小,概率最大的类别即使待验证项类别。

1
2
3
4
5
6
7
def classifyNB(vec2Classify, p0Vec, p1Vec, pClass1):
p1 = sum(vec2Classify * p1Vec) + log(pClass1) #element-wise mult
p0 = sum(vec2Classify * p0Vec) + log(1.0 - pClass1)
if p1 > p0:
return 1
else:
return 0

然后测试分类器

1
2
3
4
5
6
7
8
9
10
11
12
13
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)

至此,整个简单的朴素贝叶斯分类器就编写完成了。

总结

在遇到文档分类的需要的时候,通常都会使用朴素贝叶斯分类器来处理相关内容。我们须假设词与词之间是没有关系(当然,我们知道这是不准确的),然后根据出现词频概率来训练算法,通常是行之有效的方法。但是,这个方法需要人工提前去标注类别,所以在训练数据的时候,可以使用28原则,将8份的数据进行训练,然后测试2份的数据进行准确度判断。