上一篇: 数据挖掘:理论与算法笔记2-数据预处理
下一篇: 数据挖掘:理论与算法笔记4-神经网络

3 从贝叶斯到决策树: 意料之外，情理之中

3.1 贝叶斯奇幻之旅

分类

鱼的种类就是一种分类问题，比如我以前经常抓到的flathead是catfish家族的，他们家的鱼都是有胡子的，在catfish家族中根据颜色，体型，条纹和鱼鳍等特征还可以进一步细分，flathead就是头部特别扁平，身体颜色带点棕黄，手感滑腻。

分类是所有的动物和人类能够生存下来的一种本能，原始人看见兔子和鹿就会识别出来这是可以捕猎的对象，而看到狮子或者老虎就知道要赶紧逃命了。分类属于监督学习，必须对样本数据打标签进行训练，学习过程中有input和output，input是特征向量，output可以是boolean value(binary classification), 也可以是integer(multiclass)，手写数字图像的识别就是一个典型的多分类问题，可参考前文手工打造神经网络: 透视分析。以后我们再讨论非监督学习，即对没有标签的样本数据进行处理，如聚类。

贝叶斯定理

$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$

P(A): A发生的先验概率
P(B): B发生的先验概率
P(B|A): 当A发生时B发生的概率
P(A|B): 当B发生时A发生的概率

Case 1

患癌症 $\omega_1$ 的概率是0.8%, 健康 $\omega_2$ 的概率是99.2%，体检报告的结果有阳性和阴性。
患癌症后体检结果为阳性的概率为98%，为阴性的概率为2%
健康的体检结果为阳性的概率为3%，为阴性的概率为97%

那么如果一个人体的癌症体检结果为阳性，他实际患上癌症的概率有多少呢? 下面可以套用贝叶斯公式来计算一下:

$P(\omega_1|+) \propto P(+|\omega_1)P(\omega_1)=0.98*0.08=0.0078$
$P(\omega_2|+) \propto P(+|\omega_2)P(\omega_2)=0.03*0.992=0.0298$
$P(\omega_1|+) = \frac{0.0078}{0.0078+0.0298}=0.21$

所以检查结果为阳性时患癌症概率正比于0.0078，而健康概率正比于0.0298，健康的概率远高于患癌症概率。当检查结果为阳性时实际患癌症的概率是21%，大部分情况都是假阳性结果。虽然患癌症后检验结果为阳性的概率高达98%但也不必过于恐慌，因为健康的先验概率比患癌症的先验概率高的多。

Case 2

头疼的概率是1/10, 患流感的概率是1/40，患流感后头疼的概率是1/2, 那么如果出现头疼患流感的概率是多少呢?

套用贝叶斯公式计算:

$P(F|H)=\frac{P(H|F)P(F)}{P(H)}=\frac{1/2*1/40}{1/10}=\frac{1}{8}$

下图红色与蓝色重叠部分的面积占红色的二分之一，但只占蓝色部分的八分之一。

3.2 朴素是一种美德

接下来看看如何用贝叶斯真正的去做分类。
贝叶斯分类器强调的是后验概率，当观察到对象的一组特征 $[\alpha_1, \alpha_1,...\alpha_n]$ 之后，要判断对象属于哪个分类， $\omega_{MAP}$ 是分类的集合, 集合中哪一个分类的后验概率大则对象归属于哪个分类。

假设所有的特征都是条件独立的，我们可以把联合概率转化为概率的乘积，其实Naive Bayes这个名称中Naive指的就是这个条件独立的假设前提。

MAP：Maximum A Posterior

独立事件

如果事件A的发生对事件B的发生不产生任何影响，反之亦然，则这两个事件是独立的。比如扔硬币的结果和周几扔硬币是独立的事件，但不是所有的场景都这么明显，人的性别和是否左撇子看似独立事件，实际上不区分性别的话只有10%的人是左利手，但12%的男性是左利手。所以这两个事件不是独立的，性别为男会增加左撇子的概率。

两个事件A和B, 如果 $P(A|B)=P(A)$ 且 $P(B|A)=P(B)$ 则事件A和B是独立的，此时 $P(A \cap B) = P(A)P(B)$

$P(A \cap B|C)=P(A|C)P(B|C)$
因为 $P(A|B)= \frac{P(A \cap B)}{P(B)}$
所以 $P(A|B,C)= \frac{P(A \cap B|C)}{P(B|C)} = \frac{P(A|C)P(B|C)}{P(B|C)}=P(A|C)$

条件独立

对于条件独立来说，多了一个条件事件G, 事件A发生的概率仅依赖于G发生的概率，与B无关。

下面结合一个例子来说明什么是条件独立，假设我们有蓝色和红色两个箱子，蓝色箱子里有一个黑球和一个白球，红色箱子里有两个黑球，我要随机选择一个箱子随机挑出一个球，然后再从另一个箱子里随机挑出一个球，有以下几个事件:
A - 从第一个随机选择的箱子里随机挑出的球是黑球
B - 从第二个箱子里挑出的球是黑球
C - 第一个随机选择的箱子是蓝色的

A事件和B事件的概率同为0.75

如果A成立，则C发生的概率是三分之一，因为当A发生的时候其实已经改变了C的概率
$P(C|A)= \frac{P(A|C)P(C)}{P(A)}= \frac{0.5*0.5}{0.75}= \frac{1}{3}$

看似B的发生概率依赖于A的发生概率
$P(B|A)= \frac{1}{3}*0.5 + \frac{2}{3}*1.0= \frac{5}{6} \neq P(B)$

其实不是A影响B, 而是B的发生概率依赖于条件概率C
$P(B|A, C)=P(B|C)=0.5$

看到这里也许很多人已经会联想起那个反直觉的著名案例 - Monty Hall Problem

Monty Hall 是美国一个电视游戏节目的主持人，你是参赛者。你面对三扇门(A,B,C)，其中一扇门的后面是汽车，另外两扇门后面是山羊，你的目标是赢得汽车。你随机选择一扇门(假设你选择了A)，这时主持人打开了C，C后面是一只山羊，并给你一次重新选择的机会。现在汽车只可能在A和B中，你该不该换门，汽车在A和B后面的概率各是多少？

正确的做法是换门以增加中奖概率，可是很多人理解不了为什么，下面就用贝叶斯公式来验证下:
通过贝叶斯公式推导主持人选择打开C门时汽车在A门后的概率
$P(CarA|C) = \frac{P(C|CarA)*P(CarA)}{P(C)}$

现在需要找出当我们挑选A门后主持人选择C门的概率
$P(C) = P(C|CarA)*P(CarA)+P(C|CarB)*P(CarB)+P(C|CarC)*P(CarC)$

下面来拆解分析一下
P(C|CarA): 如果汽车在A门后面，主持人只能在B和C门中选择，所以选择C门的概率是0.5
P(C|CarB): 如果汽车在B门后面，那么主持人只能选择打开C门，这个唯一的选择概率是1
P(C|CarC): 最后，如果汽车在C门后面，主持人不可能直接打开C门给出答案，这个概率是0

代入上面的公式得出
$P(C) = 0.5*P(CarA)+P(CarB)$

因为CarA, CarB, CarC的概率都是三分之一，所以P(C)等于0.5

所以 $P(CarA|C) = \frac{P(C|CarA)*P(CarA)}{P(C)}=\frac{0.5*\frac{1}{3}}{0.5}=\frac{1}{3}$

此时再看主持人打开C门时汽车在B门后的概率
$P(CarB|C) = \frac{P(C|CarB)*P(CarB)}{P(C)}=\frac{1*\frac{1}{3}}{0.5}=\frac{2}{3}$

所以当你选择了A门，而主持人打开C门里面有一只山羊的时候，应该毫不犹豫的选择换到B门，这样中奖的概率会高一倍呢。

分类示例

下面结合实例看看如何用朴素贝叶斯来做分类

下表中的input是各种天气情况，output是是否打网球的标识

有了这些训练集之后来判断一个新的天气组合场景下是否会打网球的概率
Given：
<Outlook=sunny, Temperature=cool, Humidity=high, Wind=Strong>
Predict:
PlayTennis(Yes or no)

Bayes Solution:
P(PlayTennis=yes)=9/14
P(PlayTennis=no)=5/14
P(Wind=strong|PlayTennis=yes)=3/9
P(Wind=strong|PlayTennis=no)=3/5
...

在这种天气情况下打网球的概率是0.0053/(0.0053+0.0206)=0.205

拉普拉斯平滑

朴素贝叶斯分类器也可以应用在推荐系统如文本分类上，公式为
$P(V_k|\omega=\omega_i)=\frac{n_k+1}{n+| Vocabulary |}$
这个公式用到了拉普拉斯平滑(Lplace smoothing)，分子加了一个1，分母加了一个种类的个数。因为朴素贝叶斯分类是概率的乘积，如果某个特征项没有出现过，比如有个新的单词不在训练集里，这个特征项的概率为0会导致整体的乘积也为0，为了解决这个零概率的问题，法国数学家拉普拉斯最早提出用加1的方法估计没有出现过的现象的概率。

3.3 数据, 规则与树

决策树是一个自上而下的树状结构，模仿人类思考模式一层层做出决策。

比如销售要给潜在客户打电话，记录下来客户的一系列特征已经打电话营销是否成功的标识。特征属性包括居住地区，住房类型，收入高低，以前是否曾经购买过。

上表只是一个很小的数据集，如果记录有上百万条一定看得人蒙圈，但是我们可以通过决策树模型清晰的揭示其中的规律。下面的决策树首先按照区域划分，第一层告诉我们住在农村的人一定会买，住在城市和郊区的人不太确定购买可能性，所以往下再次划分，层层递推，最后得到非常理想的纯结果的叶节点，可以提取出明确的规则，但实际上通常到最后也不可能划分的这么纯粹。

这棵树能提取出来的规则如:
(District=Rural) -> (Outcome = Responded)
(District=Urban) and (Previous Customer=Yes) -> (Outcome=Nothing)

对于同样的数据集来说决策树并非唯一，有很多组合的可能，下面这棵树的层级更少，但是也能很好的区分出用户是否会购买。

如果特征属性很多，那么决策树的组合数量也会非常庞大，选择的基本原则是遵循奥卡姆剃刀原理，用尽可能简单的模型来描述规律。

3.4 植树造林学问大

所有的决策树算法中，Iterative Dischotomizer 3算的上是鼻祖了，虽然特殊属性很多，但是其中有些区分效果特别好的关键因子，基本思路是把这些强大的属性放在前面。

熵(Entropy)

熵是用来衡量系统的不确定性，或者说一个变量取值的不确定性。
假如变量可以取C种值，每个取值有一个概率p, 从而我们有一个预期结果的熵函数:
$Entropy(S)=-\sum^C_{i=1} p_ilog(p_i)$

前面电话营销案例的样本空间S=[9/14(responses), 5/14(no responses)], 这个结果有多不确定呢，可以用上面的公式来算一下:
$Entropy(S)=-\frac{9}{14}log_2\frac{9}{14} - \frac{5}{14}log_2\frac{5}{14}=0.940$

这里熵值最大为1，表示不确定性最高，比如扔硬币，上面的0.940也是相当的不确定了。

当我们放一个属性进来的时候，原始数据集就被切分了，可以针对每个子集再取计算它的熵。
假设 $S_v$ 是属A取值为v时集合S的子集，加入属性后的信息增益公式为:
$Gain(S,A)=Entropy(S)-\sum_{v \in A}\frac{|S_v|}{|S|}Entropy(S_v)$
这里计算的当知道某个属性A的取值后能把原始的不确定性降低多少，取值当然是越大越好。

现在看看用District来划分数据集效果如何：
$Gain(S, District)=Entropy(S)-\frac{5}{14}Entropy(S_{District=Suburban})$
$-\frac{5}{14} Entropy(S_{District=Urban})- \frac{4}{14}Entropy(S_{District=Rural})$
$=0.940- \frac{5}{14} * 0.971- \frac{5}{14} * 0.971- \frac{4}{14} * 0=0.247$