机器学习(03)朴素贝叶斯构建敏感词过滤系统

贝叶斯理论入门

贝叶斯?

贝叶斯概率以18世纪的一位神学家托马斯·贝叶斯(Thomas Bayes)的名字命名。贝叶斯概率引入先验知识和逻辑推理来处理不确定命题。另一种概率解释称为频数概率(frequency probability),它只从数据本身获得结论,并不考虑逻辑推理及先验知识。

朴素贝叶斯中的朴素一词的含义是指:整个形式化过程,我们只做最原始、最简单的假设。(如果你不理解这句话的含义,不要担心,后面我们会详细讲解的)。

条件概率与贝叶斯准则

如果你对$p(x,y|c_1)$符号很熟悉,那么请跳过本段

条件概率定义:

事件A在另外一个事件B已经发生条件下的发生概率。条件概率表示为P(A|B),读作“在B条件下A的概率”。

举个栗子:

假设现在有一个装了7块石头的罐子,其中3块是灰色的,4块是黑色的,如果从罐子里随即取出一块石头,那么是灰色石头的可能性是多少?很显然,答案是3/7。

那么如果把这些石头分别放到两个桶中,A桶中为2块灰色2块黑色,B桶中为1块灰色2块黑色,那么取出灰色石头的概率又该如何计算呢?

要计算$P(gray)$或者$P(black)$,事先得知道石头所在桶的信息会不会改变结果。你有可能已经想到计算从B桶中取到灰色石头的概率的方法,这就是所谓的条件概率(conditional probability)

假定计算的是从B桶取到灰色石头的概率,这个概率可以记作$P(gray|bucketB)$,我们称之为“在已知石头出自B桶的条件下,取出灰色石头的概率”。不难得到,$P(gray|bucketA)$值为2/4,$P(gray|bucketB)$的值为1/3。

记从B桶中取出灰色石头的概率为:$P(gray and bucketB)$,石头出自B桶的概率为$P(pucketB)$,那么条件概率计算公式如下:

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

贝叶斯准则

另一种有效计算条件概率的方法称为贝叶斯准则。贝叶斯准则告诉我们如何交换条件概率中的条件与结果,即如果已知$p(x|c)$,要求$p(c|x)$,那么可以使用下面的计算方法:

$$
p(c|x) = \dfrac{p(x|c)p(c)}{p(x)}
$$

基本原理

假设有一个数据集,它由两类数据组成,数据分布如下图所示:

朴素贝叶斯图例

其中不同形状代表不同的数据类型。

我们现在用$p1(x,y)$表示数据点$(x,y)$属于类别1(图中圆点表示的类型)的概率,用$p2(x,y)$表示数据点$(x,y)$属于类别2(图中三角形表示的类型)的概率。

那么对于一个新的数据点$(x,y)$,我们可以通过以下规则来判断它所属于的类型:

  • 如果$p1(x,y) > p2(x,y)$,那么类型为1
  • 如果$p1(x,y) < p2(x,y)$,那么类型为2

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

机器学习的一个重要应用就是文档的自动分类。对例如用户留言,邮件内容等任意类型的文本进行分类,我们可以观察文档中出现的词,并把每个词的出现或者不出现作为一个特征,这样得到的特征数目就会跟词汇表中的词目一样多。

两个假设前提

我们使用的朴素贝叶斯进行文档分类时,需要建立在两个假设前提之上的,虽然这两个假设前提有一些瑕疵,但实际情况证明,贝叶斯工作的效果很好。

假设词汇表中有1000个单词。要得到好的概率分布,就需要足够的数据样本,假定样本数为$N$。由统计学可知,如果每个特征需要$N$个样本,那么对于10个特征将需要$N^{10}$个样本,对于包含1000个特征的词汇表,将需要$N^{1000}$个样本。可以看到,所需要的样本书会随着特征数目的增大而迅速增长。

假设1:特征之间相互独立,那么样本数就可以从$N^{1000}$减少到$1000N$了。

假设2:每个特征同等重要

注释:特征之间相互独立指的是统计意义上的独立,即一个特征的出现的可能性不受其他特征所影响。 举个例子来说明:比如单词A出现在B后面的概率和出现在C后面的概率相同。很明显这种情况很不靠谱,这也正是朴素贝叶斯朴素一词的含义。

实现效果

接下来我们要用python代码来实现一个侮辱性词汇过滤系统,要用到我们刚才学习的朴素贝叶斯的知识。也许你会问,构建一个侮辱性词汇集合的数据库,遇到了侮辱性词汇,就认定这个文本为侮辱性文本,不就可以很好的解决这个问题了吗?何必要用贝叶斯呢?

首先不否认这也是一种实现思路,但我们要做的过滤系统的最终效果将是由人工去判断样本数据是否为侮辱性的文本,然后剩下的就可以交给机器,机器会自动识别出侮辱性词汇,以及判断待测试数据是侮辱性文本的可能性和非侮辱性文本的可能性,取概率较大的作为判定结果来标识出侮辱性的文本。

数据的处理

想要从一个文本中获取特征,首先需要拆分文本。这里的特征来自于文本的词条(token),我们可以把词条理解为单个单词。我们将出现在所有的文本中的词条做一个不重复的集合,然后对每一条文本进行标识,如果对应文本中对应位置的词条没有出现记为0,出现记为1。这样我们可以得到一系列用来标识文本片段特征的由0和1组成的列表,这个列表我们称为词条向量

代码实现

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

构建数据源:首先创建数据源,获取所有文本词条集合以及对应类型集合,这里省略分词部分逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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']
]
# 1代表侮辱性文字,0代表正常言论
# 这些数据将由人工标注,用于训练程序以便自动检测侮辱性留言
classVec = [0, 1, 0, 1, 0, 1]
return postingList,classVec

词条字典构建:将所有词条集合传入,得到一个所有不重复词条的集合字典

1
2
3
4
5
6
def createVocabList(dataSet):
vocabSet = set([])
for document in dataSet:
# '|'操作符可以取两个列表的并集,set()方法可以去除重复项
vocabSet = vocabSet | set(document)
return list(vocabSet)

构建词条向量:传入词条字典,和待测试的对应文本词条集合,得到词条向量

1
2
3
4
5
6
7
8
9
10
11
def setOfWords2Vec(vocabList, inputSet):
# 初始化词条向量
# [0]*len(vocabList) 可以获得一个和vocabList等长的,全部由0组成的集合
returnVec = [0]*len(vocabList)
for word in inputSet:
if word in vocabList:
# 如果词条集合中的词条出现在了词条字典中,则将词条向量中的词条对应位置的元素记为1
returnVec[vocabList.index(word)] = 1
else:
print "the word: %s is not in my Vocabulary!" % word
return returnVec

执行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
postingList,classVec = loadDataSet()
print("------postings------")
for posting in postingList:
print(posting)
print("------classVec------")
print(classVec)
vocabList = createVocabList(postingList)
print("------vocabList------")
print(vocabList)
print("------words2Vec------")
for posting in postingList:
print(setOfWords2Vec(vocabList,posting))

输出结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
------postings------
['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]
------vocabList------
['cute', 'love', 'help', 'garbage', 'quit', 'I', 'problems', 'is', 'park', 'stop', 'flea', 'dalmation', 'licks', 'food', 'not', 'him', 'buying', 'posting', 'has', 'worthless', 'ate', 'to', 'maybe', 'please', 'dog', 'how', 'stupid', 'so', 'take', 'mr', 'steak', 'my']
------words2Vec------
[0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0]
[1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1]
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]

这样我们就得到了这六组待测试数据的词条向量。

训练算法:通过词条向量计算是侮辱性评论的概率

问题分析

前面介绍了如何将一组单词转换为一组数字,接下来看看如何使用这些数字计算概率。

现在我们已经知道了一个词是否出现在一篇文档中,也知道该文档所属的类别。根据前面提到的贝叶斯准则,我们将其中的$x$替换为$\textbf{w}$。注意:这里的粗体的$\textbf{w}$代表一个向量,即它是由多个值组成。

$$
p(c_i|\textbf{w}) = \dfrac{p(\textbf{w}|c_i)p(c_i)}{p(\textbf{w})}
$$

我们将使用上述公式,对每个类计算该值,然后比较着两个概率值的大小(这个例子中就是分别计算是侮辱性言论和不是侮辱性言论的概率,比较两种情况的概率大小)

如何计算呢?

step1:计算$p(c_{i})$

首先可以通过类别i(侮辱性言论或者非侮辱性言论)中文档数除以总的文档数来计算$p(ci)$(对应类别的文档占总文档数的比例)

step2:计算$p(\textbf{w}|c_i)$

这里就要用到朴素贝叶斯的假设了。假设$\textbf{w}$展开为一个个独立特征,那么可以将上述概率写作$p(w_0,w_1,w_2..w_n|c_i)$。这里假设所有词都互相独立,该假设也称作条件独立假设,它意味着可以使用$p(w_0|c_i)p(w_1|c_i)p(w_2|c_i)..p(w_n|c_i)$来计算上述概率,这就极大的简化了计算的过程。

代码实现:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# trainMatrix:多个词条向量组成的集合矩阵
# trainCategory:分类标签集合
def trainNBO(trainMatrix, trainCategory):
# 记录词条向量个数
numTrainDocs = len(trainMatrix)
# 单个词条向量的长度,即词条字典的长度
numWords = len(trainMatrix[0])
# 引入numpy后,sum函数可以计算一个集合的所有元素的总和
# pAbusive 是所有词条向量中 是侮辱性言论的概率: 3/6 = 0.5
pAbusive = sum(trainCategory) / float(numTrainDocs)
# 初始化 侮辱性/非侮辱性 言论中 词条分布总和向量
# 引入numpy后,zeros(numWords)方法用来得到一个和numWords等长的0矩阵
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

运行代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
postingList, classVec = loadDataSet()
vocabList = createVocabList(postingList)
for posting in postingList:
word2Vec = setOfWords2Vec(vocabList, posting)
trainMat.append(word2Vec)
p0V,p1V,pAb = trainNBO(trainMat,classVec)
print("------p0V------")
print(p0V)
print("------p1V------")
print(p1V)
print("------pAb------")
print(pAb)

运行结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
------p0V------
[ 0.04166667 0.04166667 0.04166667 0. 0. 0.04166667
0.04166667 0.04166667 0. 0.04166667 0.04166667 0.04166667
0.04166667 0. 0. 0.08333333 0. 0.
0.04166667 0. 0.04166667 0.04166667 0. 0.04166667
0.04166667 0.04166667 0. 0.04166667 0. 0.04166667
0.04166667 0.125 ]
------p1V------
[ 0. 0. 0. 0.05263158 0.05263158 0. 0.
0. 0.05263158 0.05263158 0. 0. 0.
0.05263158 0.05263158 0.05263158 0.05263158 0.05263158 0.
0.10526316 0. 0.05263158 0.05263158 0. 0.10526316
0. 0.15789474 0. 0.05263158 0. 0. 0. ]
------pAb------
0.5

p0V是所有词汇出现在非侮辱性言论中的概率向量。

p1V是所有词汇出现在侮辱性言论中的概率向量。

从中可以看出,p1V中,概率最大的是倒数第六个0.15789474,然后查询词条字典,发现这个词是‘stupid’,这意味着‘stupid’这个单词是最能表征类型1的词条,事实也确实如此。同时我们也能发现最能表征类别0的词条是‘him’。

从结果中我们同样也能看到,在p0V中为0的词条,在p1V中不为0,相反的,在p1V中为0的词条,在p0V中也不为0。其实这并不是绝对的,这是巧合所致,如果我们的测试样本数量足够大,就可以看出这个现象了。

代码优化

代码实现了贝叶斯分类器,并不是完事大吉了,有些地方我们需要根据实际情况来优化我们的代码。

注意点1:

利用贝叶斯分类器对文档进行分类时,要计算多个概率的乘积,以获得文档属于某个类别的概率,即计算$p(w_0|1)p(w_1|1)p(w_2|1)$。如果其中一个概率为0,那么最后的成积也为0。为降低这种影响,可以将所有词的出现数初始化为1,并将分母初始化为2(分子分母各加1)

将trainNBO()的14到18这几行代码进行修改:

1
2
3
4
5
6
7
# 初始化 侮辱性/非侮辱性 言论中 词条分布总和向量
# 引入numpy后,zeros(numWords)方法用来得到一个和numWords等长的单位矩阵
p0Num = ones(numWords)
p1Num = ones(numWords)
# 初始化 侮辱性/非侮辱性 言论中 词条总个数
p0Denom = 2.0
p1Denom = 2.0

注意点2:

另一个问题是下溢出,这是由于太多很小的数相乘造成的。当计算$p(w_0|c_i)p(w_1|c_i)p(w_2|c_i)…p(w_N|c_i)$时,由于大部分因子都非常小,所以非常容易出现下溢出(可以尝试用python计算多个很小的数字相乘,最后的结果会变为0)

一种解决办法是对乘积取自然对数。在代数中有$ln(a*b)=ln(a)+ln(b)$,于是通过求对数可以将乘法转化为加法,从而避免下溢出或者浮点数舍入导致的错误。同时,采用自然对数进行处理不会有任何损失。

修改trainNBO()中的代码,在return之前添加如下代码:

1
2
3
4
5
6
# 分别对每个元素取对数
for i in range(len(p1Vect)):
p1Vect[i]=log(p1Vect[i])
for i in range(len(p0Vect)):
p0Vect[i]=log(p0Vect[i])

只差一步,构建朴素贝叶斯分类函数

现在已经准备好了构建完整的分类器了。

1
2
3
4
5
6
7
8
9
10
11
# vec2Classify:待测试数据的词条向量
# pClass1:所有词条向量中是侮辱性词条向量的概率
def classifyNB(vec2Classify, p0Vec, p1Vec, pClass1):
# sum(vec2Classify * p1Vec)当前词条向量中,每个词条可能是侮辱性词条的概率之积p(w:c1)
# pClass1 : p(c1)
p1 = sum(vec2Classify * p1Vec) + log(pClass1)
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
14
15
16
17
18
19
20
postingList, classVec = loadDataSet()
vocabList = createVocabList(postingList)
trainMat = []
for posting in postingList:
word2Vec = setOfWords2Vec(vocabList, posting)
trainMat.append(word2Vec)
p0V,p1V,pAb = trainNBO(trainMat,classVec)
# 测试数据1
testEntry = ['love','my','dalmation']
thisDoc = array(setOfWords2Vec(vocabList,testEntry))
print testEntry,'classified as: ',classifyNB(thisDoc,p0V,p1V,pAb)
# 测试数据2
testEntry = ['stupid','garbage']
thisDoc = array(setOfWords2Vec(vocabList,testEntry))
print testEntry,'classified as: ',classifyNB(thisDoc,p0V,p1V,pAb)

运行结果:

1
2
['love', 'my', 'dalmation'] classified as: 0
['stupid', 'garbage'] classified as: 1

总结

至此,完成了朴素贝叶斯识别侮辱性言论的系统。对于分类而言,有的时候使用概率要比使用硬规则更为有效。可以看出,朴素贝叶斯提供了一种利用已知值来估计未知概率的有效方法

虽然建立在特征独立性假设特征同等重要假设之上,但是,贝叶斯分类器依然是一种很有效的分类器。

坚持原创技术分享,您的支持将鼓励我继续创作!