数据挖掘算法之贝叶斯网络

贝叶斯网络

序

上上周末写完上篇朴素贝叶斯分类后，连着上了七天班，而且有四天都是晚上九点下班，一直没有多少时间学习贝叶斯网络,所以更新慢了点，利用清明节两天假期，花了大概七八个小时，写了这篇博客，下面讲的例子有一个是上一篇朴素贝叶斯讲过的，还有其他的都是出自贝叶斯网络引论中。我会以通俗易懂的方式写出来，不会讲得很复杂，会介绍贝叶斯网络的绝大部分知识点，看完会让你对于贝叶斯网络有个大概的了解。但是对于比较深层次的东西，我先不打算写。比如训练贝叶斯网络，因为涉及到比较加深入的数学知识，我自己暂时也不是理解得很透彻，所以先不写。

这几天利用闲暇时间，看了一部电视剧，stb超级教师，这部电视剧虽然没有什么明星，但是个人觉得还是挺好看的，比较有营养，算是一部喜剧和励志片。故事情节大概就是一个家庭贫困的孩子，在高中没有读完就去黑市打黑拳，十多年后，这个男主角和几个兄弟在黑道上打出了一片天，但是男主角后悔当初没读书，对于打打杀杀的日子感到腻了，就去一家高中当了一个班主任，但是这个班是全校的垃圾班，班上的班主任已经换了16个，有的还被学生整得去了精神病院。虽然刚开始也遭到了同学们的暗算，但是在他不懈的坚持下，感化了所有学生。因为男主角以前没受过什么正规教育，没有教师资格证，被一些老师排挤，要求他离校，最终在男主角不断的坚持和同学们的帮助下，考上了教师资格证。

里面有几句男主角说的话：共勉

成长就是让你一个人，踉踉跄跄的受伤，跌跌撞撞的坚强

你们生下来不是为了考试成绩而活，那证明不了什么，真正重要的，是你们要好好的活着,为自己找到一个真正的答案。

不管是什么样的人，只要肯用心，肯努力，都可以达到自己的目标

引子

前面讲了朴素贝叶斯，朴素贝叶斯有个前提，就是每个随机变量（特征属性）都是相互独立的。 但是在现实生活中，我们遇到的情况不是所有随机变量都相互独立，他们之间相互关联、相互影响。 上一篇我们讲过一个通过朴素贝叶斯来检测真假账号的例子。 账号真假的判断根据三个特征属性来判断：

       F1: 日志数量/注册天数 

　　　　 F2: 好友数量/注册天数  　　　　 F3: 是否使用真实头像（真实头像为1，非真实头像为0） 通过计算这个式子：P(F1|C)P(F2|C)P(F3|C)P(C) 来判断一个账号的真假。但是我们的前提是假设这三个特征相互独立。 现在发现三个特征属性具有如图所示的关联关系

1、真实账号比非真实账号平均具有更大的日志密度、各大的好友密度以及更多的使用真实头像 2、日志密度与好友密度、日志密度与是否使用真实头像在账号真实性给定的条件下是独立的 3、使用真实头像的用户比使用非真实头像的用户平均有更大的好友密度 由于特征属性间存在依赖关系，使得朴素贝叶斯分类不能解决这种问题了，看下面这种解决办法： 上图是一个有向无环图，其中每个节点代表一个随机变量，而弧则表示两个随机变量之间的联系，代表父节点影响子节点 不过上面这个图，只是定性地给出了随机变量（特征属性）之间的关系，如果要定量，还需要一些数据，这些数据就是每个节点对其直接前驱节点的条件概率，而没有前驱节点的节点则使用先验概率表示。而这些数据可以通过训练获得，如下，是通过训练获得的在已知账号为真或假地情况下，使用真实头像的概率分布

 纵向表头表示条件变量，横向表头表示随机变量。上表为真实账号和非真实账号的概率，而下表为头像真实性对于账号真实性的概率。这两张表分别为“账号是否真实”和“头像是否真实”的条件概率表。有了这些数据，不但能顺向推断，还能通过贝叶斯定理进行逆向推断。例如，现随机抽取一个账户，已知其头像为假，求其账号也为假的概率：

      也就是说，在仅知道头像为假的情况下，有大约35.7%的概率此账户也为假。

上面的计算式子中分母P(H=0)用到了全概率公式进行变形

看看百度百科上面全概率公式的定义

若事件B1，B2，…构成一个完备事件组且都有正概率，则对任意一个事件A，有如下公式成立：

P(A)=P(AB1)+P(AB2)+...+P(ABn)=P(A|B1)P(B1) + P(A|B2)P(B2) + ... + P(A|Bn)P(Bn).

此公式即为全概率公式。

特别地，对于任意两随机事件A和B，有如下成立：

如果给出所有节点的条件概率表（可以通过样本训练得到）。和各节点之间的关系，就可以算出每个节点发生的概率。上述方法就是使用了贝叶斯网络。

不确定性推理与联合概率分布

使用概率方法进行不确定性推理就是： 1、把问题用一组随机变量X={X1，X2，...,Xn}来刻画； 2、把关于问题的知识表示为一个联合概率分布P(X); 3、按照概率论原则进行推理计算。 下面看一个例子 Alarm问题：Peari教授家住在洛杉矶，那里地震(E)和盗窃(B)时有发生，教授的家里装有警铃(A)，地震和盗窃都可能触发警铃，听到警铃后，两个邻居Mary(M)和Join(J)可能都会打电话给他，一天，Peari教授接到Mary的电话，说听到他家警铃响，Pearl教授想知道他家遭盗窃的概率是多大？ 按照上面的步骤：

把问题用一组随机变量X={X1，X2，...,Xn}来刻画；

这个问题包含5个随机变量：盗窃(B)、地震(E)、警铃响(A）、接到John的电话(J)和接到Mary(M)的电话; 所有变量的取值均是y或n。这里各变量间的关系存在不确定性：盗窃和地震以一定的概率随机发生；它们发生后，并不一定会触发警铃；而警铃响后，Mary和John可能会因为某些原因，如在听摇滚音乐和听力问题，而没有听到警铃；有时候，两人也会将其他声音误听为警铃声。假设Pearl教授对这5个变量的联合概率分布P(B,E,A,J,M)的评估如表2.1所示，要计算的是接到Mary的电话(M=y)后，Pearl教授对家里招盗(B=y)的信度，即计算(B=y|M=y).

从联合概率分布P(B,E,A,J,M)出发，先计算边缘分布

直接使用联合分布计算进行不确定性推理的困难很明显，就是它的复杂度很高。例如上面有5个二值随机变量，整个联合分布包含的独立参数有：1+2+4+8+16=31.一般地，n个二值变量的联合概率分布包含(2的n次方-1)个独立参数，所以，联合分布的复杂度相对于变量的个数成指数增长。当变量很多时，存储和计算都十分困难。 那么，有什么办法解决了，肯定有。就是降低联合分布的复杂度。接着看下面的内容。

条件独立与联合分布的分解

上面讲的Alarm问题的五个随机变量都是不确定的，进而增大了计算的复杂度。但是，利用变量间的条件独立可以将联合分布分解成多个复杂度较低的概率分布，达到降低模型表达式的复杂度。 原先我们可以把联合概率分布P(B,E,A,J,M)表示为 P(B,E,A,J,M)=P(B)P(E|B)P(A|B,E)P(J|B,E,A)P(M|B,E,A,J)

这个式子上面讲过有31个独立参数，计算比较复杂。

但是我们可以根据背景知识知道：

地震应该与盗窃无关。于是假设E与B相互独立。即P(E|B)=P(E).把P(E|B)分解成了P(E).

John和Mary是否打电话直接取决于他们是否听到警铃。可以假设给定A时，J与B和E,以及M与J、B和E都相互独立，即P(J|B,E,A)=P(J|A)和P(M|B,E,A,J)=P(M|A)

将这些独立假设代入以前的联合分布公司，得到：

P(B,E,A,J,M)=P(B)P(E)P(A|B,E)P(J|A)P(M|A) 得到的新公式分解成了若干个复杂度较低的概率分布的乘积。仅包含 1+1+4+2+2=10个独立参数。 将上面的变量间的关系用一个有向无环图表示出来。变量之间的依赖关系通过边和边的箭头来表示。B->A则表示A依赖于B,再通过样本训练得到每个图节点（随机变量）的概率分布。得到下图：

贝叶斯网络的构造 

分为两步：确定网络拓扑和确定网络参数

确定网络拓扑

1 、选定一组刻画问题的随机变量{X1,X2,...Xn}; 2 、选择一个变量顺序a={X1,X2,...Xn}; 3、 从一个空图出发，按照顺序a逐个将变量加入网络图中 4、在加入变量Xi时，网络图中的变量包括X1，X2,...,X(i-1); 4.1、利用问题背景知识，在这些变量中选择一个尽可能小的子集C(Xi),使得假设给定这个子集C(Xi) ，Xi与网络图中的其他变量条件都独立合理。   4.2、从子集C(Xi)中的每一个节点添加一条指向Xi的有向边   如果你看不很明白的话，看下面这个例子，还是上面的Alarm问题的例子   该问题涉及五个随机变量，假设用序列a1={B,E,A,M,J}来构造一个贝叶斯网络结构，过程如下：

  1、首先把B加入空图，得到图a   2、接着加入E：假设B和E相互独立，C(E)=空集，因此无需加边，结果如图b   3、然后加入A:我们假设A同时依赖B和E,所以C(A)={B,E}，于是分别从B和E画一条到A的边，得到图c   4、加入M:假设给定A,M与B、E条件独立，所以C(M)={A}，于是画一条到M的边，得到图d   5、最后加入J:假设给定A,J与B、E和M相互条件独立，所以C(J)={A},画一条从A到J的边，得到图e

不同的序列，会得到不同的网络结构图：通常我们通过因果关系来决定变量顺序

  比如上面的E(地震)和B(盗窃)是A(警铃响)的直接原因。于是有E->A，B->A这两条边，A(警铃响)是Mary和john打电话的直接原因，于是有A->M,和A-J。通过因果关系，就能构造网络图。

确定网络参数

贝叶斯网络参数就是各变量的概率分布，一般是通过训练样本统计获得。 不过有时也可以从问题的特性直接得到，看一个例子 种马农场：考虑一个种马农场中的公马、母马和它们生育的后代之间的基因遗传关系。假设基因a是一个隐性致病基因，对应的显性基因是A,当没有任何信息时，任意一匹马关于该疾病的基因型可能是以下三者之一。 aa(患病) 、aA(携带者)  、AA(正常)。根据基因遗传学，可以直接确定任意一匹马的基因型Gc与它的父母的基因型Gp和Gm之间的概率关系P(Gc|Gp,Gm).当公马是aa时，如果母马也是aa，则后代只可能是aa,所以其分布是(1,0,0); 如果母马是aA，则后代不可能是AA,如果母马是AA，则后代一定是aA。 各情况的分布如下表

贝叶斯网络的三种结构形式

考虑两个变量a和b通过3个变量c间接相连的这一基本情况，可以分为3个子形式：顺连、分连、汇连

顺连

    有：P(a,b,c)=P(a)*P(c|a)*P(b|c)。

    化简后可得：

    即：在c已知的情况下，对a了解不会影响c的信度，进而也不会影响b的信度，a、b之间的信息通道是被阻塞、被阻断的(blocked)，a、b是相互独立的。但是在c未知的情况下，对a的了解对影响关于c的信度，进而影响关于b的信度

在Alarm网络图中,存在一个从盗窃(B)到警铃响(A)再到Mary打电话(M)的顺连结构：B->A->M.   若不知道A的状态，接到Mary的电话，会增加对警铃响了的信度，从而增加对发生了盗窃的信度。反之，若被告知发生了盗窃，则也会增加对警铃响了的信度，从而增加对Mary打电话的信度。 另一方面，如果早上出门前特地关闭了警铃，则知道发生了盗窃不会影响警铃响了的信度，所以不会增加对Mary打了电话的信度。同理，知道Mary打了电话，也不会增加对发生了盗窃的信度，因为警铃已被关闭，所以会认为Mary可能是听摇滚音乐太多而产生了幻听。 所以在未知A时，B和M相互关联，而在已知A时，B和M相互条件独立。

分连

    有P(a,b,c)=P(c)*P(a|c)*P(b|c)，则：P(a,b|c)=P(a,b,c)/P(c)，然后将P(a,b,c)=P(c)*P(a|c)*P(b|c)带入上式，得到：P(a,b|c)=P(a|c)*P(b|c)。 在c未知的情况下，信息可以在a、b之间传递，他们是关联的，在c已知的情况下，信息不能在a、b之间传递，他们是被阻塞的，是阻断的，a、b是相互独立的

在Alarm网络图中 ,警铃响(A)后Mary(M)和john(J)都可能打电话，即有分连结构：M<--A-->J

若接到Mary电话，则对警铃响了的信度会增加，从而也会进一步期望John的电话。所以，未知A时，M和J相互关联。但是如果事先知道警铃已被关掉，就不会出现这样的推理。即已知A后，M和J条件独立。

汇连

    所以有：P(a,b,c) = P(a)*P(b)*P(c|a,b)成立，化简后可得：

  汇连和前面两种情况完全相反，在c已知的情况下，a、b是相互关联的。  在c未知的情况下，a、b被阻断(blocked)，是独立的。（举个不恰当的例子，你爸妈和你，在你还没出生前，他们是相互独立的，在你出生后，他们就通过你联系起来了，不再是相互独立的了） 在Alarm网络图中,盗窃(B)和地震(E)都会触响警铃(A),从而会有汇连结构：E-->A<--B。 在A未知时，B和E相互独立，得知发生了地震不会改变对发送了盗窃的信度。 但是如果知道警铃响，若得知发生了地震，警铃响就有了合理的解释，从而对发生了盗窃的信度会降低，反过来，若得知发生了盗窃，警铃响也有了合理的解释，从而对发送了地震的信度也会降低，所以在A已知的情况下，B和E相互关联，在A未知的情况下，B和E相互独立。和前面两种情况相反。 好了，今天就写到这里了，天已经黑了，还没吃饭。下一篇会写数据挖掘的决策树算法包括ID3和C4.5

参考资料：贝叶斯网络引论

  数据挖掘理论与概念

   数学之美

 http://www.cnblogs.com/leoo2sk/archive/2010/09/18/bayes-network.html http://blog.csdn.net/zdy0_2004/article/details/41096141