0%

ML-朴素贝叶斯算法

贝叶斯定理

w是由待测数据的所有属性组成的向量。p(c|x)表示,在数据为x时,属于c类的概率。
$$
p(c|w)=\frac{p(w|c)p(c)}{p(w)}
$$

如果数据的目标变量最后有两个结果,则需要分别计算p(c1|x)p(c2|x)取最大的值为分类的结果
$$
p(c_{1}|w)=\frac{p(w|c_{1})p(c_{1})}{p(w)}、
p(c_{2}|w)=\frac{p(w|c_{2})p(c_{2})}{p(w)}
$$

算法的目的就在于找到使p最大的 $c_{i}$。由于只需要比较两个概率的大小,则分母p(w)可以不用算,并不影响结果。那 $p(w|c_{0})p(c_{0})$又如何计算呢?一条数据w其实包含很多属性w=w1,w2,w3,...,wn.以 $p(w|c_{0})p(c_{0})$为例:

p(c0) 表示分类结果为c0的概率:

$$
p(c_{0})=\frac{数据集中属于c_{0}类别的数据条数}{数据集的总数}
$$

而 $p(w|c_{0})$ == $p(w_{1},w_{2},w_{3},…,w_{n}|c_{0})$。朴素贝叶斯分类假设所有属性之间是独立的,互不影响。那么就满足如下关系:
$$
p(w_{1},w_{2},w_{3},…,w_{n}|c_{0}) = p(w_{1}|c{0})p(w_{2}|c{0})p(w_{3}|c{0})…p(w_{n}|c{0})
$$
$$
p(w_{1}|c{0})=\frac{在c_{0}类别的数据中单词w_{1}出现的次数}{属于c_{0}类别的单词总数}
$$

至此,已经计算出了足够数据来计算出$p(w|c_{1})p(c_{1})$,用这些概率可以给新的数据分类。如果此时有数据 w=w1,w3,w5,那需要分别算出两个概率:
$$
p(c_{0}|w_{1},w_{3},w_{5})=>p(w_{1}|c{0})p(w_{3}|c{0})p(w_{5}|c{0})p(c_{0})
$$
$$
p(c_{1}|w_{1},w_{3},w_{5})=>p(w_{1}|c{1})p(w_{3}|c{0})p(w_{5}|c{1})p(c_{1})
$$
比较大小,找到最大的概率,最大概率的 $c_{i}$就是分类的结果

算法实现

收集数据

1、从文本文件中读取数据,并分割成每个单词,放到一个list中。每个文件一个list,最后是一个二维的list:

[[‘my’, ‘dog’, ‘has’, ‘flea’, ‘problems’, ‘help’, ‘please’],
[‘maybe’, ‘not’, ‘take’, ‘him’, ‘to’, ‘dog’, ‘park’, ‘stupid’]]

1
2
3
4
5
6
7
8
9
10
11
12
13
def loadDataSet():
"""
创建数据集
:return: 文档列表 docList, 所属类别classVec
"""
docList = [['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 docList, classVec

2、遍历上例的二维表,找到所有出现的单词,使用set()去重。这个集合就作为数据集的属性.上例的词汇表为:

[‘steak’, ‘dog’, ‘problems’, ‘so’, ‘buying’, ‘my’, ‘how’, ‘licks’, ‘dalmation’, ‘take’, ‘food’, ‘maybe’, ‘stop’, ‘posting’, ‘him’, ‘garbage’, ‘has’, ‘stupid’, ‘park’, ‘ate’, ‘mr’, ‘not’, ‘love’, ‘help’, ‘worthless’, ‘flea’, ‘please’, ‘quit’, ‘to’, ‘is’, ‘I’, ‘cute’]

1
2
3
4
5
6
7
8
def createVocabList(docList):
"""构造词汇表,统计所有文本中的所有单词
:return list 去重的词汇表
"""
vocalSet = set([])
for line in docList:
vocalSet = vocalSet | set(line) # 集合求并集操作
return list(vocalSet)

3、将每个文件的单词列表转换为向量。遍历文件中的每个单词,如果出现在词汇表中则为1,否则为0

[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1]

1
2
3
4
5
6
7
def setOfWords2Vec(vocabList, inputSet):
"""将输入数据转换为向量.存在这个单词记为1,不存在则记为0"""
returnVec = [0] * len(vocabList)
for word in inputSet:
if word in vocabList:
returnVec[vocabList.index(word)] = 1
return returnVec

训练算法

训练算法就是计算一系列概率的过程。要预测一个文本,需要计算以下概率:

  • $p(c_{0})$ 和 $p(c_{1})$
  • $p(w_{i}|c_{0})$ 和 $p(w_{i}|c_{1})$

下面的代码计算出了这些概率,其中p0是一个列表,其中记录了每一个 $p(w_{i}|c_{0})$的值。p1同理。pc1表示 $p(c_{1})$,$p(c_{0})$可以用 1-pc1 得到

p0: [[0.04166667 0.04166667 0.04166667 0.04166667 …]]
p1: [[0. 0.10526316 0. 0. …]]
pc: 0.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def trainNB0(trainMatrix, trainCategory):
"""分类器训练函数"""
numberOfAttr = len(trainMatrix[0])
numbrOfDoc = len(trainMatrix)
p0 = np.zeros((1, numberOfAttr)) # p(wi|c0)
p1 = np.zeros((1, numberOfAttr)) # p(wi|c1)
p0Total = 0.0
p1Total = 0.0
pc1 = float(sum(trainCategory)) / numbrOfDoc # p(c1)

for i in range(numbrOfDoc):
if trainCategory[i] == 0:
p0 += trainMatrix[i] # 统计先验概率c0下,每个单词出现的次数
p0Total += sum(trainMatrix[i])
else:
p1 += trainMatrix[i] # 统计先验概率c1下,每个单词出现的次数
p1Total += sum(trainMatrix[i])

p0 = p0 / p0Total # 用c0下每个单词出现的次数,分别除以c0下的总数==> p(wi|c0)
p1 = p1 / p1Total # p(wi|c1)

return p0, p1, pc1

分类

根据之前的理论。如果数据有三个单词 w=w1,w3,w5,那需要分别算出两个概率:
$$
p(c_{0}|w_{1},w_{3},w_{5})=>p(w_{1}|c{0})p(w_{3}|c{0})p(w_{5}|c{0})p(c_{0})
$$
$$
p(c_{1}|w_{1},w_{3},w_{5})=>p(w_{1}|c{1})p(w_{3}|c{0})p(w_{5}|c{1})p(c_{1})
$$

优化代码

1、书上说,对于 $p(w_{1}|c{0})p(w_{2}|c{0})p(w_{3}|c{0})$如果其中任何一个概率为0,则总概率为零,所以把所有单词出现的次数初始化为1。(其实不改也行,但是代码中inputData * p0已经过滤出了所有非零元素)

2、 概率都是很小的数,如果直接以小数运算会带来很大的误差。书上采用了对数替代直接的小数运算。本来的概率是这样算的
$$
p(w_{1}|c{0})p(w_{3}|c{0})p(w_{5}|c{0})p(c_{0}) == \frac{count(w_{1}|c_{0})}{count(c{0})}\frac{count(w_{3}|c_{0})}{count(c{0})}\frac{count(w_{5}|c_{0})}{count(c{0})}p(c_{0})
$$
现在使用对数,In(fx)并不会影响f(x)的单调性,所以计算的结果可以直接比较大小,不会影响分类结果。计算方式如下:
$$
In(p(w_{1}|c{0})p(w_{3}|c{0})p(w_{5}|c{0})p(c_{0})) == In(\frac{count(w_{1}|c_{0})}{count(c{0})})+In(\frac{count(w_{3}|c_{0})}{count(c{0})})+In(\frac{count(w_{5}|c_{0})}{count(c{0})}) + In(p(c_{0}))
$$

优化后的训练代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def trainNB1(trainMatrix, trainCategory):
"""分类器训练函数"""
numberOfAttr = len(trainMatrix[0])
numbrOfDoc = len(trainMatrix)
p0 = np.ones((1, numberOfAttr)) # p(wi|c0)
p1 = np.ones((1, numberOfAttr)) # p(wi|c1)
p0Total = 2.0 # 不唯一
p1Total = 2.0
pc1 = float(sum(trainCategory)) / numbrOfDoc # p(c1)

for i in range(numbrOfDoc):
if trainCategory[i] == 0:
p0 += trainMatrix[i]
p0Total += sum(trainMatrix[i])
else:
p1 += trainMatrix[i]
p1Total += sum(trainMatrix[i])

p0 = np.log(p0 / p0Total)
p1 = np.log(p1 / p1Total)

return p0, p1, pc1

分类的代码如下:

1
2
3
4
5
6
7
8
def classifyNB(inputData, p0, p1, pc1):
"""使用计算得到的概率分类"""
prob0 = np.sum(inputData * p0) + np.log(1-pc1)
prob1 = np.sum(inputData * p1) + np.log(pc1)
if prob0 > prob1:
return 0
else:
return 1

测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def testNB():
"""测试函数"""
docList, classVec = loadDataSet()
vocabList = createVocabList(docList)

trainMat = [] # 由0/1组成的数据集 : [[0,1,0,0,1,....],[0,0,0,0,0,1,...]]
for doc in docList:
trainMat.append(setOfWords2Vec(vocabList, doc))
p0, p1, pc1 = trainNB0(trainMat, classVec)

testData = ['love', 'my', 'dalmation']
thisDoc = setOfWords2Vec(vocabList, testData)
print("分类结果是:", classifyNB(thisDoc, p0, p1, pc1))

testData = ['stupid', 'garbage']
thisDoc = setOfWords2Vec(vocabList, testData)
print("分类结果是:", classifyNB(thisDoc, p0, p1, pc1))

词袋模型

上面的代码中,文件中出现的单词,记为1,否则为0。这种方式叫词集模型(set-of-words model)。得到的是如下的向量:

[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1]

但是同一个单词在文档中可能多次出现,在向量中记录单词出现的次数的方式叫做词袋模型(bag-of-words model)。得到的向量可能是这样的:

[0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 7, 0, 0, 2]

要实现词袋模型只需要改动很少量的代码:

1
2
3
4
5
6
7
def bagOfWords2Vec(vocabList, inputSet):
"""[词袋模型]将输入数据转换为向量.存在这个单词记为1,不存在则记为0"""
returnVec = [0] * len(vocabList)
for word in inputSet:
if word in vocabList:
returnVec[vocabList.index(word)] += 1
return returnVec

案例:过滤垃圾邮件

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def textParse(bigString):
"""将字符串返回成单词列表
1. 以空白字符作为分隔符
2. 排除长度小于2的单词,他可能没有实际意义
3. 所有单词转换为小写
"""
import re
listOfWords = re.split(r'\W*', bigString)
return [word.lower() for word in listOfWords if len(word) > 2]


def spamTest():
"""测试算法。使用交叉验证"""
docList, classList, fullText = [], [], []
# 1. 解析文本文件。一个文件解析成一个list,所有文件保存为一个二维list
for i in range(1, 26):
spam = open("dataset/email/spam/%d.txt" % i)
wordList = textParse(spam.read())
docList.append(wordList)
classList.append(1)

ham = open("dataset/email/ham/%d.txt" % i)
wordList = textParse(ham.read())
docList.append(wordList)
classList.append(0)

# 2.格式化
vocabList = createVocabList(docList) # 创建词汇表

# 3. 随机挑选10个测试数据(可能没有10个)
trainSet = list(range(50)) # 记录了所有用于训练的数据集的下标
testSet = [] # 记录了所有用于测试的数据集的下标
for i in range(10):
randIndex = int(random.uniform(0, len(trainSet)))
testSet.append(trainSet[randIndex])
del trainSet[randIndex]

# 4. 训练
trainMatrix, trainCategory = [], []
for i in range(len(trainSet)):
trainMatrix.append(bagOfWords2Vec(vocabList, docList[trainSet[i]]))
trainCategory.append(classList[trainSet[i]])
p0, p1, pc1 = trainNB1(trainMatrix, trainCategory)

# 5. 测试
testMatrix, testCategory, error = [], [], 0
for i in range(len(testSet)):
line = bagOfWords2Vec(vocabList, docList[testSet[i]])
result = classifyNB(line, p0, p1, pc1)
if result != classList[testSet[i]]:
error += 1
print("错误率为:", (float(error)/len(testSet)))