朴素贝叶斯分类算法
wangxiaohua 2016-09-09
之前有次考试考的是手工计算朴素贝叶斯的分类。当时没答对，后来搞明白了，不久又忘得差不多了。所以写个例子在这儿记一下。
先推导一下贝叶斯公式：
假定我们观察到两个事件都发生了，记做P(A∙B)，那么我们既可以认为先发生了事件A，在此基础上又发生了事件B，也可以认为先发生了事件B，在此基础上又发生了事件A。所以这两个事件发生的概率，可以记做P(A∙B)=P(A|B)*P(B) 和 P(B∙A)=P(B|A)*P(A)，其中P(A|B)、P(B|A)是条件概率，意思是在B事件的条件下又发生A的概率及在A事件的条件下又发生B的概率，那么显然P(A∙B)= P(B∙A)，所以这两个公式合并就成了P(A|B)*P(B)=P(B|A)*P(A)，再变形一下即得到P(A|B)=P(B|A)*P(A)/P(B)或者P(B|A)= P(A|B)*P(B)/P(A)。防止公式看花眼，只拿其中一个举例。
P(B|A)=P(A|B)*P(B)/P(A)，观察等式两边，先不管P(A)和P(B)，一边是P(B|A)，一边是P(A|B)，意味着如果我们知道了P(A)和P(B)，那么就可以对两个条件概率进行互算。这正是朴素贝叶斯算法的理论基础——根据已有数据的概率预测新数据的概率，举个例子见表格：
观测项 | 类别(假定只有两类) |
| |
已有数据1 | 000 | C1 | 已知P(观测项|类别)——可以算出各类别条件下某观测项的概率 |
已有数据2 | 001 | C1 | |
已有数据3 | 010 | C1 | |
已有数据4 | 011 | C2 | |
已有数据5 | 100 | C1 | |
已有数据6 | 101 | C1 | |
已有数据7 | 110 | C2 | |
… … | … … | … … |
|
新数据 | 111 | ？ | 计算P(类别|观测项)——某观测项条件下各类别的概率，并选取最大概率那个类别作为“预测”结果 |
那再回到公式，P(A)和P(B)是否可知呢？当然是可知的，因为我们已有数据的数量是有限的，在这个数量中求某一观测项的概率或者某一类别的概率就是个简单的除法。而且并不需要计算P(A)，我们只是要比较哪个类别的概率更大，分母相同，只计算分子，看哪个大就可以了。
以上表的7条已知数据为例：P(C1)=5/7；P(C2)=2/7；
P(000|C1)=1/5、P(001|C1)=1/5、P(010|C1)=1/5、P(011|C2)=1/2、P(100|C1)=1/5、P(101|C1)=1/5、P(110|C2)=1/2，这些都可以算出来。理想情况下我们要分别计算P(C1|111)和P(C2|111)的概率并比较二者大小。P(C1|111)= P(111|C1)*P(C1)/P(111)；P(C2|111)= P(111|C2)*P(C2)/P(111)，分母相同不去管，只计算并比较P(111|C1)*P(C1)和P(111|C2)*P(C2)。P(C1)、P(C2)有了，然而P(111|C1)和P(111|C2)都没有，等于0。说明这是一条从没出现过的“纯”新数据。这种情况其实是很常见的，但是0乘以任何数都是0，0和0怎么比较大小呢。所以应对这种情况，常用一种叫做Laplace平滑的方法，就是假设已知数据里每个类别下至少有一条这样的数据。看起来有些粗暴，但当数据量较大时几乎是不影响结果的正确性的。这样一来，P(C1|111)=P(111|C1)*P(C1)=1/6*5/7=0.12、P(C2|111)=P(111|C2)*P(C2)=1/3*2/7=0.09，0.12>0.09，以此推断111属于C1类。事实上我在设计上面的数据时改了好几次，因为数据量实在太小，即便+1也会对结果造成影响。这个完全的新数据111被预测为C1类，那么从逻辑上是否讲的通呢？只能说有一点儿，毕竟通过观察我们发现大部分（5/7）的数据都是C1类，那么来一条没有任何“迹象”的新数据我们也只能往可能性最大的类别里分。
在实际应用中，我们的观测项往往并非一项，也就是说，表格多半是这样的：
观测项1 | 观测项2 | 观测项3 | 类别 |
| |
已有数据1 | 000 | ○ | M | C1 | 已知P(观测项|类别)——可以算出各类别条件下某观测项的概率 |
已有数据2 | 001 | □ | A | C1 | |
已有数据3 | 010 | ○ | A | C1 | |
已有数据4 | 011 | ○ | M | C2 | |
已有数据5 | 100 | ○ | A | C1 | |
已有数据6 | 101 | ○ | A | C1 | |
已有数据7 | 110 | □ | M | C2 | |
… … | … … |
|
| … … |
|
新数据 | 111 | ○ | A | ？ | 计算P(类别|观测项)——某观测项条件下各类别的概率，并选取最大概率那个类别作为“预测”结果 |
计算P(C1|111∙○∙A)和P(C2|111∙○∙A)需要用到P(111∙○∙A|C1)和P(111∙○∙A|C2)，此时应用朴素贝叶斯算法，我们需要一个先决条件——各观测项相互独立、没有关联关系。因为如果相互独立，就可以把概率公式拆分成这样：P(111∙○∙A|C1)=P(111|C1)*P(○|C1)*P(A|C1)，这样算起来会更容易，而且更少出现等于0的情况。
P(C1|111∙○∙A)= P(111∙○∙A|C1)*P(C1)= P(111|C1)*P(○|C1)*P(A|C1)*P(C1)=1/6*4/5*4/5*5/7=0.076
P(C2|111∙○∙A)= P(111∙○∙A|C2)*P(C2)= P(111|C2)*P(○|C2)*P(A|C2)*P(C2)=1/3*1/2*1/3*2/7=0.016
C1类比C2类概率大多了，自然预测为C1类。肉眼观察也能有这样感觉：虽然111没有在观测项1里出现过，但大部分○和大部分A都属于C1类，那么这条新数据属于C1类的可能性也很大。这就是三个观测项相互独立并共同作用于结果的情况。
实际类别是什么呢？那就没人知道了。其实我在设计第一个表格的时候预想的规则是这样的：只有连着两个1以上的数字是C2类，否则就是C1类。可见算法是很难猜测规则的，尤其训练数据量少的时候。我们只能在已有数据上多尝试几种算法，多试验一些参数，评估正确率最高的算法，再应用到未来的数据上去。
