贝叶斯算法及其相关

introduce贝叶斯网络BN(BayesianNetworks)源于概率统计学,作为机器学习的重要方法倍受瞩目,在数据挖掘中被广泛研究应用。朴素贝叶斯NB(Na!veBayes)分类方法（p.s.其缩写都是nb，可见此算法确实很牛逼）具有坚实的理论基础,和其它分类方法相比,表现出了高速度和高效率,被广泛地应用于模式识别、自然语言处理、机器人导航、规划、机器学习以及利用贝叶斯网络技术构建和分析软件系统。贝叶斯其人贝叶斯ThomasBayes，英国数学家.1702年出生于伦敦，做过神甫。1742年成为英国皇家学会会员。1763年4月7日逝世。贝叶斯在数学方面主要研究概率论。他首先将归纳推理法用于概率论基础理论，并创立了贝叶斯统计理论，对于统计决策函数、统计推断、统计的估算等做出了贡献.1763年发表了这方面的论著，对于现代概率论和数理统计都有很重要的作用。贝叶斯的另一著作《机会的学说概论》发表于1758年。贝叶斯所采用的许多术语被沿用至今。贝叶斯的两大贡献概率论中的贝叶斯公式统计学中的贝叶斯决策理论贝叶斯公式又称逆概公式。在全概公式后出现，不是第一也是前三重要的概率公式。设D1，D2，……，Dn为样本空间S的一个划分，如果以P(Di)表示Di发生的概率，且P(Di)>0(i=1，2，…，n)。对于任一事件x，P(x)>0，则有：就形式上而言，该公式可写作一简单的形式，p(Di|x)=p(Di,x)/p(x)非常简洁明了，但是十分犀利如何犀利，下一页见分晓一个例子有一个经典的概率问题，在三个箱子a，b，c里有一个里面有礼物，甲选择了a箱子以后，工作人员从剩余的两个中打开一个没有礼物的箱子c，这时甲被要求再做一次选择。他可以选择：（1）改变以前的想法，选择箱子b（2）坚持以前的想法，选择第一次选择的箱子a他到底应该做出怎样的选择呢？目标:比较p(a非空|选a，工作人员打开c)和p(b非空|选a，工作人员打开c)贝叶斯决策理论什么是统计决策？设x的分布函数是F(x,c),c是未知参数，c∈C，C叫做参数空间。X=(x1,x2,…,xn)是X的样本。又设A是某项实际工作中可能采取的各种行动所组成的非空集合，A叫做行动空间。L(c,a)是定义在C*A上的非负函数，它表示参数是c时采取行动a（a∈A）引起的损失。称样本空间到行动空间A的映射g(x1,…xn)为决策函数，简称决策。目的是找一个决策g，使得L的平均值最小。一个例子检查某设备零件零件可能状态：c1(好),c2(坏)可能采取的行动：a1(保留),a2(更换),a3(修理).损失函数为样本：X取值为0或1.在工作时用手摸零件，温度正常时则记1，发烫则记0.X的概率函数为La1a2a3c10105c21216p01c10.30.7c20.60.4贝叶斯决策理论经典方法中把参数c看做是客观常数，通过样本的研究对c给出估计值或者判断c属于某个给定的范围贝叶斯学派的基本观点，认为在关于c的任何统计推断问题中，除了使用样本X提供的信息外，还必须对c提供一个先验分布，它是进行推断时不可缺少的要素。说得准确些，应该把c看做随机变量，他服从某个概率分布（叫做先验分布），总体X的分布实际上是c给定时x的分布。根据分布密度f和c的先验分布，可以算出在样本x下c的条件分布密度，p(c|x)，因为这个分布是在抽样后得到的，故成为后验分布贝叶斯方法的关键在于得出后验分布后，他所做的推断就只基于后验分布，而与样本无关了，无论是做最大似然估计，还是最小二乘估计。朴素贝叶斯分类算法假设A1,A2,⋯,An是数据集的n个属性,假定有m个类,C={C1,C2,⋯,Cm},给定一个具体的例子X,其属性值为(x1,x2,⋯,xn),这里xi就是属性Ai的取值,该例子属于某一个类Ci的后验概率是P(X|Ci),c(X)表示分类所得的类标签。贝叶斯分类器进行如下工作:朴素贝叶斯分类假设类条件独立,即属性之间不存在依赖关系。这样有:于是,朴素贝叶斯的分类算法公式为:其中P(Ci)被称为先验概率,有时认为P(C1)=P(C2)=⋯=P(Cn),也可以通过公式P(Ci)=si/s计算,其中si是类Ci中的训练样本数,而s是训练样本总数。概率P(xk|Ci)可以由训练样本估值,即P(xk|Ci)=sik/si,其中sik是在属性Ak中具有值xk的类Ci的训练样本数,而si是Ci中的训练样本数。上周论文中的NBC算法贝叶斯过滤算法利用概率函数构建哈希表，当其判定函数超过阙值时，判定为垃圾邮件。foxmail等都用此算法判定是否为垃圾邮件，当然是改进后的。一个例子：垃圾邮件例如：一封含有“法轮功”字样的垃圾邮件A和一封含有“法律”字样的非垃圾邮件B根据邮件A生成hashtable_bad，该哈希表中的记录为法：1次轮：1次功：1次计算得在本表中：法出现的概率为0。3轮出现的概率为0。3功出现的概率为0。3根据邮件B生成hashtable_good，该哈希表中的记录为：法：1

律：1

计算得在本表中：法出现的概率为0。5

律出现的概率为0。5综合考虑两个哈希表，共有四个TOKEN串：法轮功律当邮件中出现“法”时，该邮件为垃圾邮件的概率为：

P=0。3/（0。3+0。5）=0。375

出现“轮”时：

P=0。3/（0。3+0）=1

出现“功“时：

P=0。3/（0。3+0）=1

出现“律”时

P=0/（0+0。5）=0；由此可得第三个哈希表：hashtable_probability其数据为：法：0。375

轮：1

功：1

律：0当新到一封含有“功律”的邮件时，我们可得到两个TOKEN串，功律查询哈希表hashtable_probability可得

P（垃圾邮件|功）=1P（垃圾邮件|律）=0

此时该邮件为垃圾邮件的可能性为：

P=（0*1）/[0*1+（1-0）*（1-1）]=0

由此可推出该邮件为非垃圾邮件优点与缺点优点：高速度，高效率，占用内存少缺点：基于独立性假设，当假设成立时与其他分类算法相比,朴素贝叶斯分类