自己动手写贝叶斯分类器给图书分类
一杯啤酒一段代码.jpg
背景与目的##
首先，这是一个机器学习初学者兼非数学科班出身的非典型工程师的自学记录。所以本文不会特别理论，也不会太深入地讲解公式，但是会非常有目的性，针对一个特别现实的问题，从头开始分享解决方案，包括某些优化方案。
另外，我不是“理论搬运工”。我开发的产品海鸟电波（我的其它文章也有介绍到，或者可以百度一下）的后台图书分类也用到了这个分类器。
从问题开始##
我们要解决的问题，是对图书进行二元分类。分类的依据是图书的tag。这些tag可能来自专家，或者编辑，或者用户。例如“外国文学”，“侦探”，“计算机”，“python”都属于tag。
出于我们的小小实验项目的需求，简化问题，我们现在要把图书分为“人文”或者“非人文”两类。所以，正如上文所说，这是一个对图书进行的二元分类问题。
例如，《计算机科学导论》，它的标签有“计算机”“科学”“经典”“导论”，它属于“非人文”。《麦田里的守望者》，它的标签有“小说”“文学”“美国”，它属于“人文”。我们的分类器有能力根据一本书的标签，自动地将其归类为“人文”或者“非人文”。试试看，蛮有意思的！
为了解决这个问题，我们给出若干个前提：
- 任何一本书只可能归类为“人文”或“非人文”中的一类
- 1本书有1个或以上的tag
- 所有书都没有“人文”和“非人文” 的tag（什么？你不相信？看看亚马逊京东就知道了）
- 你需要很少的概率知识，比如什么是概率？条件概率又是什么？
使用python和numpy##
我们将使用python作为这个实验项目的编程语言。
numpy是一个python的科学计算库，需要你自行安装。因为我们的程序涉及一些简单的矩阵运算，用numpy可以大大简化编程工作量。
基本原理##
贝叶斯分类器的工作原理###
还是需要了解一定的理论知识的，别担心，这部分很快就过去。我会直接结合要解决的问题来讲解。
基本上，用贝叶斯分类是要解决一个这样的问题：已知一本书有这些tag：tag1,tag2,tag3......它属于“人文”分类的概率是多少？属于“非人文”分类的概率呢？
假设p1表示在这种情况下，它属于“人文”的概率，p2表示这种情况下，它属于“非人文”的概率。
如果p1>p2，那么这本书就属于“人文”，反过来就是“非人文”。我们不考虑p1=p2的情况。
很简单，不是么？
所以，问题就变成了，如何通过tag1,tag2,tag3...来计算p1和p2？毕竟，只要知道了这两个值，我们的最终问题就解决了。
条件概率###
其实，这是一个条件概率的问题。所谓条件概率，就是求：在已知b发生的情况下，a发生的概率。我们写做：p(a|b)。
结合我们的实际问题，那就是在tag1,tag2,tag3...已经发生的情况下（也就是这本书的tag就是tag1,tag2,tag3...），这本书属于“人文”和“非人文”的概率。我们写做：
p(cate1|tag1,tag2,tag3...) 意思是在tag1,tag2,tag3...发生的情况下，这本书属于cate1的概率（cate1＝“人文”）
p(cate2|tag1,tag2,tag3...) 意思是在tag1,tag2,tag3...发生的情况下，这本书属于cate2的概率（cate2=“非人文”）
这里的p(cate1|tag1,tag2,tag3...)其实就是上面说的p1,我们这里用更为专业的方法来写。
条件概率怎么求呢？这就是贝叶斯公式：
p(a|b) = p(b|a) * p(a) / p(b)
这个意思就是：想要求p(a|b)，而你又知道p(b|a)，p(a)和p(b)的值，那你就可以通过p(b|a)*p(a)/p(b)来求得p(a|b)。
换成我们要解决的实际问题，等于：
p(cate1|tag1,tag2,tag3...) = p(tag1,tag2,tag3...|cate1) * p(cate1) / p(tag1,tag2,tag3...)
翻译为人话，那就是你想求p(cate1|tag1,tag2,tag3...)，而你现在知道：
- p(tag1,tag2,tag3...|cate1)的值，也就是你知道在一本书已经被分类为“人文”的情况下，tag1,tag2,tag3...一起出现的概率
- p(cate1)，也就是所有被标记为“人文”分类的书，（在训练集中）在所有书（“人文”和“非人文”）中出现的概率
- p(tag1,tag2,tag3...)，也就是tag1,tag2,tag3...（在训练集）所有tag中出现的概率
也就是说，我们只要挨个求出上述3项，我们就可以求出p(cate1|tag1,tag2,tag3...)了。同样，p(cate2|tag1,tag2,tag3...)也可以求出。
这里有个值得注意的技巧，上述3项中，其实第3项不需要我们计算。因为我们的目的是比较p(cate1|tag1,tag2,tag3...)与p(cate2|tag1,tag2,tag3...)的大小，不是为了得到实际的值，由于上述公式里的分母p(tag1,tag2,tag3...)是一样的，所以，我们只需要比较分子的大小就可以了。也就是比较：
p(tag1,tag2,tag3...|cate1) * p(cate1)，
与p(tag1,tag2,tag3...|cate2) * p(cate2)的大小
这样可以省去我们一些计算。
朴素贝叶斯###
那么，如何计算p(tag1,tag2,tag3...|cate1)呢？这里要用到朴素贝叶斯的概念，就是说，我们认为，在一本书中的标签里，每个标签都是相互独立的，与对方是否出现没有关系。也就是说“计算机”和“经典”出现的概率互不相关，不会因为“计算机”出现了就导致“经典”出现的概率高。
既然是相互独立，那么，p(tag1,tag2,tag3...|cate1)就等于：
p(tag1|cate1) x p(tag2|cate1) x p(tag3|cate1) x ...
p(tag1,tag2,tag3...|cate2)就等于：
p(tag1|cate2) x p(tag2|cate2) x p(tag3|cate2) x ...
也就是说，我们可以计算每一个tag，分别在“人文”和“非人文”书籍的所有tag中出现的概率，然后将它们乘起来，就得到我们想要的。
举例分析###
我们现在有一本书《计算机科学导论》，它的标签是“计算机”“科学”“理论”“经典”“导论”，我们想知道在这几个标签出现的情况下，《计算机科学导论》分别属于“人文”和“非人文”的概率。
那么，我们已经有了什么呢？幸运的是，我们目前手头有10本书，已知其中6本是“人文”，4本是“非人文”。这10本书，经过排重，一共有70个不同的标签，“计算机”，“科学”，“理论”，“导论”也在其中。
基于此，我们可以得出，p(cate1)=6/10=0.6，p(cate2)=1-0.6=0.4。也就是说“人文”书在所有书中的概率是0.6，“非人文”是0.4。
接下来就是p(tag1,tag2,tag3...|cate1)和p(tag1,tag2,tag3...|cate2)了。也就是，我们要算出，在“人文”类里的所有书中，“计算机”“科学”“理论”“经典”“导论”这几个tag在“人文”书的所有tag里出现的概率。同样，我们还要算出，在“非人文”类里的所有书中，上述这几个tag在所有“非人文”书中的所有tag里出现的概率。计算的方法，就是将每个tag在“人文”和“非人文”中出现的概率，相乘，然后再分别乘以0.6和0.4。
然后比较一下大小就可以了。也就是比较p(cate1) x p(tag1,tag2,tag3...|cate1)与p(cate2) x p(tag1,tag2,tag3...|cate2)的大小。
开始动手##
1.准备训练集###
几乎所有的机器学习都需要训练集。贝叶斯分类也一样。事实上，我们上面所说的我们##已知##的数据，就是训练集。上面例子中举出的那10本书，以及这10本书所有排重后的tag，就是我们的训练集；而0.6和0.4这两个概率，还有p1(tag1,tag2,tag3...|cate1)和p2(tag1,tag2,tag3...|cate2)，就是我们基于训练集的数据计算出来的，机器学习管这叫“训练”。
基于我们的问题，我们需要准备100本书，人为地分为“人文”和“非人文”两类，并且收集将这些书的所有tag。这些书如何获得？你可以爬取亚马逊或者豆瓣上的书籍资源。
2.形成tag集###
将上述所说的tag，用python里的列表来保存，我们令其为dicts.dicts里的每一个元素是一个tag，例如：
dicts = ['科学','理论','c++']这样的形式。
3.计算训练集中“人文”和“非人文”的概率###
非常简单，如我们的例子所说，假设这训练集中的这100本书，有60本是“人文”，那么p(cate1)=60/100=0.6。p(cate2)=1-p(cate1)=0.4。这里我们用变量:
pcate1 = 0.6
pcate2 = 0.4
4.计算tag集中每个tag在训练集“人文”书籍中的tag出现的概率###
首先，我们基于训练集构造一个列表，这个列表里的每一项又是一个列表，这个列表里的每一项，不是1就是0。1表示这个词典中这个位置的tag是这本书的一个tag。
举例：假设我们的dicts是这样的：
['计算机','小说','心理','科学','编程','行为','导论','经典','游记','美国']
我们有这样一个列表：tag_vector_cate1
[
[0,1,0,0,0,0,0,1,0,1],
[0,0,1,0,0,1,0,0,0,1],
..............
]
这个列表对应的是“人文”类。
每一行代表训练集中“人文”类的一本书。第一行对应的书是《麦田里的守望者》，它的标签是“小说”，“经典”，“美国”。第二行对应的书是《可预测的非理性》，它的标签是“心理”，“行为”，“美国”。注意，我们是用整个tag集dicts来表示一本书的tag。所以，第一行第1列(我们从0开始计数)的1，表示《每天里的守望者》有一个'小说'的tag(对应dicts里的第1列)；第一行第2列的0，表示《麦田里的守望者》这本书没有'心理'这个tag(对应dicts里的第2列)。同理，我们看到第一行和第二行的第9列都是1，说明《麦田里的守望者》和《可预测的非理性》都有'美国'这个tag。
有了这样的数据，我们就很好计算了。现在以计算p(tag1|cate1)为例。对于tag1，我们计算出在训练集里“人文”的所有书中，tag1出现了多少次。例如：在训练集里，“人文”有60本，其中40本书都有“经典”这个tag，那么我们就令num_of_tag1=40。按照这个方法，我们求出每个tag出现了多少次，比如：num_of_tag2=32,num_of_tage=18......
然后，我们求出在“人文”类里，所有书的tag标签总数（注意这里是不排重的）。例如“人文”类有2本书，第一本书的标签是“散文”“经典”“外国”，第二本是“经典”“小说”。那么，所有书的tag标签总数就是3+2=5。现在，我们求出训练集里所有100本的tag标签总数。假设总数是700。我们令total_cate1=700。
于是，tag1在“人文”类里出现的概率：p(tag1|cate1) = num_of_tag1 / total_cate1 = 40/700 = 0.057。同理，我们得出p(tag2|cate1)，p(tag3|cate1)...
利用numpy，我们可以很方便地用几句代码来实现这个过程。
from numpy import *
num_tags_cate1 = ones(len(dicts)) #(1)
total_cate1 = 2.0 #(2)
for item in tag_vector_cate1: num_tags_cate1 += item #(3) total_cate1 += sum(item) #(4) p_tags_cate1 = num_tags_cate1 / total_cate1 #(5)
这里做一下说明。
(1)代码，表示生成一个numpy数组。ones()是numpy的函数，返回一个填充了数值1的numpy数组，参数是这个数组的长度。例如：temp=ones(3)，表示生成了一个numpy数组[1,1,1]并返回给了temp。所以，(1)代码就是以训练集的tag集dicts的长度为参数，生成一个和dicts等长的填充了1的numpy数组，返回给num_tags_cate1。为什么要和dicts登长？还记得吧，我们是以整个字典集来表示一本书的。我们要计算的就是这个dicts里的每一个tag的概率，并放到一个数组里。num_tags_cate1就是这个数组。至于这个数组为什么要填充1，稍后会说明。
(2)total_cate1 = 2.0。total_cate1是分母，分母不能是0，所以我们要令其初始值不为0。为什么是2.0？稍后会说明。
(3)num_tags_cate1 += item。item显然是一个python的列表，就是我们刚才说的[0,1,0,0,0,0,0,1,1]。当你用一个numpy数组加上一个python的list时，numpy会帮你做对应项目的计算，相当于重载了＋。例如，a是一个numpy数组：[1,2,3,5,0]，b是一个python的list：[0,0,3,2,1]。a + b = [1,2,6,7,1]，结果是一个numpy数组。在这个例子里，相当于“小说”，“经典”，“美国”这3个标签的数量分别增加了1。
(4)把每本书出现的所有tag的数量相加。sum(item)也是numpy的函数，作用是将item里的每一项相加。例如：sum([2,5,-1])，其结果2+5+(-1)=6。假如item是这样的一个list：[0,1,0,0,0,0,0,1,1]，对应的是《麦田里的守望者》，它的标签分别是“小说”“经典”“美国”，相当于标签总数增加了3。
(5)很明显，我们用num_tags_cate1去除以total_cate1，这也是numpy重载了“/”运算符，例如[2,4,6]/2，相当于每一项分别除以2，最后得到一个numpy数组，也就是[1,2,3]。在这个例子里，就相当于我们分别用tag1,tag2,tag3...出现的次数去除以标签的总数量，并得到一个numpy数组p_tags_cate1。这个数组里的每一项是一个概率值，代表其对应的tag在cate1（“人文”）类别里出现的概率。
同样，我们可以计算出p_tags_cate2。也就是每个tag在cate2（“非人文”）里出现的概率。
5.现在我们有什么###
来到这里，我们已经有了几乎所有的东西。回忆一下贝叶斯分类的公式：
p(cate1|tag1,tag2,tag3...) = p(tag1,tag2,tag3...|cate1) x p(cate1) / p(tag1,tag2,tag3...)
我们前面讨论过，分子可以忽略，不计算，也就是不需要理会分母p(tag1,tag2,tag3...)。
进一步地，按照朴素贝叶斯理论，分子等于：
p(tag1,tag2,tag3...|cate1) x p(cate1) = p(tag1|cate1) x p(tag2|cate1) x p(tag3|cate1) x ... x p(cate1)
p(cate1)就是等于上面所说的pcate1。
p(tag1|cate1)，p(tag2|cate1)......就是我们上面得出的numpy数组p_tags_cate1里的每一项。我们只需要把它们相乘起来，就得到p(tag1|cate1) x p(tag2|cate1) x ...... !
来到这里，我们要解释一下，为什么上文的代码用1来填充num_tags_cate1。如果我们用0来填充，当某个tag一直为0时（虽然理论上不可能出现），整个分子相乘的结果为0，这样最后的值就变为0了，影响了结果。所以，为了避免这种情况，我们认为每个tag至少要出现1次，所以我们用ones来填充。这样，最坏情况下，num_tags_cate1=[1,1,1,.....]。
而total_cate1=2.0，就是对应当num_tags_cate1=[1,1,1,...]时，那么我们认为每个tag出现的概率是0.5（1/2.0），这是一个可以调节的参数，但是要记住不要令total_cate1=1.0。如果这样，那么每个tag出现的概率变成1了，大有问题。
6.利用训练得出的数据给新书进行分类###
终于完成了贝叶斯分类器，现在我们看看如何给新书分类。
所谓给新书分类，就是当已经完成了训练集的训练后（还记得吧？那100本手工分类的书就是训练集），这时候，我们要对第101本书进行分类。这本书不是训练集里的书，是新书。我们基于前面计算出来的公式里的几个元素，来对它进行分类。
同样的，我们抽取新书的标签，并用python里的list来保存，记作：tagvects，它的形式如：[1,0,0,1,0,0,1....]。
接着，我们让p_tags_cate1里的每个项乘以对应的tagvects里的项：
results_tags_cate1 = p_tags_cate1 * tagvects
再令num_tags_cate1里的每一项相乘：
temp1 = 1.0
for item in results_tags_cate1: if item != 0: temp1 = temp1 * item
同样的方法，计算出temp2：
results_tags_cate2 = p_tags_cate2 * tagvects
temp2 = 1.0
for item in results_tags_cate2: if item != 0: temp2 = temp2 * item
最后，这样：
p_cate1_tags = temp1 * pcate1
p_cate2_tags = temp2 x pcate2
if p_cate1_tags > p_cate2_tags: print '人文' else: print '非人文'
显然，我们通过比较p_cate1_tags与p_cate2_tags的大小，就可以为新书进行分类了，哪边的值大，就分到哪边。
优化trick##
由于上面的公式，是多个概率相乘，当你的tag集dicts的长度非常大时（也就是你的书的标签特别多时），这是个很可怕的做法，由于每一项都是小数，这么多小数相乘，将可能出现溢出，或者数太小导致计算结果为0。这时候，需要一个trick，来做一下优化，避免这种情况。
我们取数学上非常流行的做法，取对数ln，来改善我们的算法。在python里，取对数的函数是log()。
可以在几个地方取对数。这里推荐这样的做法，把要计算的式子变成：
ln(p(tag1|cate1) * p(tag2|cate1) *....* p(cate1)))
展开来，就变成：
ln(p(tag1|cate1)) + ln(p(tag2|cate1)) + ... + ln(pcate1)
回忆一下，p(tag1|cate1),p(tag2|cate1)...是我们上面算出的p_tags_cate1的每一项（p_tags_cate1是numpy数组，其中每一项表示对应的tag在“人文”分类中出现的概率）。在我们上面的计算中：
p_tags_cate1 = num_tags_cate1 / total_cate1
现在我们对其取对数，于是，改代码改为：
p_tags_cate1 = log(num_tags_cate1 / total_cate1)
注意，这里的log，是对numpy的数组中的每一项求log，结果还是一个数组。
于是，p_tags_cate1就成为了取对数后的数组。
然后求ln(pcate1)，把pcate1变为：
pcate1 = log(pcate1)
所以，上面最后分类的代码就改为：
results_tags_cate1 = p_tags_cate1 * tagvects
temp1 = 1.0
for item in results_tags_cate1: if item != 0: temp1 = temp1 + item
同样的方法，计算出temp2：
results_tags_cate2 = p_tags_cate2 * tagvects
temp2 = 1.0
for item in results_tags_cate2: if item != 0: temp2 = temp2 + item
然后就可以分类了：
p_cate1_tags = temp1 + pcate1
p_cate2_tags = temp2 + pcate2
if p_cate1_tags > p_cate2_tags: print '人文' else: print '非人文'
总结##
很高兴你终于来到了这里。本文力求简洁，尽量降低学习成本。但是肯定存在第一次阅读还觉得有些不太理解的可能，这是正常的，凡事总有个过程，尤其是机器学习这个领域，需要你反复咀嚼和思考以及实践。攥写本文的过程中，我也在反复加深对贝叶斯分类的理解，但是表达出来，还是有不太清晰的地方。如果你有不解或者建议，欢迎与我多讨论。
通过本文，我们明白了：
- 什么是朴素贝叶斯
- 为了施行朴素贝叶斯分类，应该如何准备训练集，其中tag集是非常重要的
- 在训练数据的基础上，得到每个tag在“人文”和“非人文”中的出现概率
- 利用这些出现概率，为新的文章进行分类
- 巧妙利用对数和一些初始值（例如ones()）来为算法做一些优化
凡尔赛宫.jpg
最后，给自己的一个小创作做一下宣传，海鸟电波是一个语音评论书籍的平台，目前以微信公众号h5页面的形式来提供服务，在这里你可以自由评论书籍、倾听真人语音的点评，分享自己的见解等。另外，我也在简书上发表了一篇文章海鸟电波的第一天描述我开发海鸟电波的缘由。
本文由电流首发于简书。转载请注明出处。欢迎来到原文处进行交流。
谢谢你的阅读。
文章开头的配图摄于某个酒吧，在酒吧里编程是一种特别的体验。图片归本人所有。
文章结尾的配图摄于凡尔赛宫外，选此图的意义是希望科技与人文艺术优美结合。图片归本人所有。
