k2贝叶斯算法

‘壹’ 如何利用贪心法构建贝叶斯网络代码

基于matlab的贝叶斯网络工具箱BNT是kevin p.murphy基于matlab语言开发的关于贝叶斯网络学习的开源软件包，提供了许多贝叶斯网络学习的底层基础函数库，支持多种类型的节点（概率分布）、精确推理和近似推理、参数学习及结构学习、静态模型和动态模型。
贝叶斯网络表示：BNT中使用矩阵方式表示贝叶斯网络，即若节点i到j有一条弧，则对应矩阵中（i，j）值为1，否则为0。
结构学习算法函数：BNT中提供了较为丰富的结构学习函数，都有：
1. 学习树扩展贝叶斯网络结构的TANC算法learn_struct_tan().
2. 数据完整条件下学习一般贝叶斯网络结构的K2算法learn_struct_k2()、贪婪搜索GS（greedy search）算法learn_struct_gs()和爬山HC（hill climbing）算法learn_struct_hc()等。
3. 缺失数据条件下学习一般贝叶斯网络结构的最大期望EM（expectation maximization）算法learn_struct_EM（）和马尔科夫链蒙特卡罗MCMC（Markov Chain Monte Carlo）learn_struct_mcmc()算法等。
参数学习算法函数：BNT中也提供了丰富的参数学习函数，都有：
1． 完整数据时，学习参数的方法主要有两种：最大似然估计learn_params()和贝叶斯方法bayes_update_params();
2． 数据缺失时，如果已知网络拓扑结构，用EM算法来计算参数，倘若未知网络拓扑结构，使用结构最大期望SEM（structure EM）算法learn_struct_SEM()。
推理机制及推理引擎：为了提高运算速度，使各种推理算法能够有效应用，BNT工具箱采用了引擎机制，不同的引擎根据不同的算法来完成模型转换、细化和求解。这个推理过程如下：

BNT中提供了多种推理引擎，都有：
1． 联合树推理引擎jtree_inf_engine();
2． 全局联合树推理引擎global_joint_inf_engine();
3． 信念传播推理引擎 belprop_inf_engine();
4． 变量消元推理引擎 var_elim_inf_engine().

‘贰’ 朴素贝叶斯（Naive Bayes）算法

朴素贝叶斯算法属于分类算法。发源于古典数学理论，对缺失数据不太敏感，有稳定的分类效率，模型所需估计的参数很少，算法比较简单。

朴素贝叶斯算法 ， 贝叶斯 是说明这个算法和贝叶斯定理有联系，而 朴素 是因为处理实际的需要，做了一个简化—— 假设每个特征之间是独立的 （如果研究的对象互相之间的影响很强，计算概率时考虑的问题非常复杂，做了独立假设，就可以分解后进行研究），这是这个算法模型与贝叶斯定理的区别。

将 x 作为特征，y 作为类别，那公式左边的 P（yi|x）就是说在知道特征 x 的情况下，计算这个特征属于 yi 类的可能性大小。通过比较找出这个可能性的值最大的属于哪一类，就将特征 x 归为这一类。

第3步的计算就是整个关键所在，计算依据是上面的贝叶斯公式。

对于每一个类的概率计算，公式右边的分母的 P(x)都是相同的，所以可以不计算（我们只是对最终结果进行比较，不影响）。

P（yi）也称为先验概率，是 x 属于 yi 类的一个概率，这个是通过历史信息得到的（在程序实现的时候，历史信息或者说先验信息就是我们的训练数据集），我们通过对训练样本数据进行统计，分别算出 x 属于 y1,y2,...,yn 类的概率是多少,这个是比较容易得到的。

所以，主要是求 P（x|yi）= P(a1,a2,...,am|yi)

这个时候对于贝叶斯模型的 朴素 的独立性假设就发挥作用了(综合的计算变成了独立计算后的综合，简化模型，极大地减少了计算的复杂程度)：

P(a1,a2,...,am|yi) = P(a1|yi)P(a2|yi)...P(am|yi)

所以计算想要得到的东西如下：

一个程序简例

‘叁’ 贝叶斯规则

全概率公式 ：设试验E的样本空间为S，A为E的事件，B1,B2,...,Bn为S的一个划分，并且P(Bi)>0(i=1,2,..,n) 那么：
P(A)=P(A|B1)P(B1)+P(A|B2)PB2)+...+P(A|Bn)P(Bn)

全概率公式证明依据：P(A)=P(AS)=P(AB1)+P(AB2)...+P(ABn)=P(A|B1)P(B1)+P(A|B2)P(B2)+....P(A|Bn)P(Bn)
S是样本空间，B1,B2,...,Bn是S的划分

贝叶斯公式 ：设试验E的样本空间为S，A为E的事件，B1,B2,..,Bn为S的一个划分，且P(A)>0,P(Bi)>0(i=1,2,3,...,n)那么：

贝叶斯公式分子证明依据（条件概率公式）：P(Bi|A)=P(BiA)/P(A) P(BiA)=P(A|Bi)P(Bi)
贝叶斯公式分母证明依据（全概率公式）

贝叶斯规则以Thomas Bayes主教命名。
用来估计统计量的某种性质。
贝叶斯是用概率反映知识状态的确定性程度，数据集可以直接观测到，所以他不是随机的。

贝叶斯推断与其他统计学推断方法截然不同。它建立在主观判断的基础上，也就是说，你可以不需要客观证据，先估计一个值，然后根据实际结果不断修正。贝叶斯推断需要大量逗亏的计算。

http://www.ruanyifeng.com/blog/2011/08/bayesian_inference_part_one.html

他是一种条件概率条件概率。 比如：在B发生时，A发生的可能性。
公式为：

公式中，事件Bi的概率为P(Bi)，事件Bi已发生条件下事件A的概率为P(A│Bi)，事件A发生条件下事件Bi的概率为P(Bi│A)。
用来计算简单条件下发生的复杂事件。

正如以上所说：在B发生时，A发生的可能性。 P(A|B)
通过韦恩图可以看到：

B发生时，A发生的概率：P(A|B)=P(A∩B)/P(B)
可以得到条件概率的推导过程如下：

等式合并：

最终得到：

P(类山察神别|特征) = P(特征|类别)P(类别)/P(特征)

根据以往经验和分析得到的概率。 往往作为 由因求果 问题中的 因 出现的概率。 又称： 古典概率

（在观测数据之前，我们将已知的知识表示成 先验概率分布 但是一般而言我们会选择一个相当宽泛的先验（高熵），反映在观测到的任何数据前，参数的高度不确定性）
（通常，先验概率开始是相对均匀的分布或高熵的高斯分布，观测数据通常会使后验的熵下降）

在上述贝叶斯公式中，我们把P(A)称为 先验概率 。没祥 （B事件发生之前，对A事件概率的一个判断）
把P（A|B)称为 后验概率 。(事件B发生之后，对事件A概率的重新评估）
P(B|A)/P(B)称为：可能性函数。 这是一个调整因子，使得预估概率更接近真实概率。

在一个通信系统中，在收到某个消息之后，接收端所了解到的该消息发送的概率称为后验概率。
他是在给出相关证据或者数据后得到的条件概率。
他指的是在得到结果的信息重新修正的概率。计算后验概率必须以先验概率为基础。

后验概率 = 先验概率 * 调整因子

上述调整因子又叫 似然函数
他是关于统计模型参数的函数。
假定一个关于参数y，具有离散型概率分布P的随机变量X，则在给定X的输出x时，关于参数y的似然函数是：L(y|x)等于给定参数y后变量X的概率：
L(y|x) = P(X=x|y) = Py(x)

概率：用于已知一些参数的情况下，预测接下来的观测所得到的结果。
似然：用于在已知某些观测所得到的结果时，对有关食物的性质的参数进行估计。
似然函数可以理解为条件概率的逆反。

材料：
1：先验概率：利用现有材料计算的。
2：后验概率：利用先验概率+补充材料计算的。
计算：
1：先验概率：古典概率。
2：后验概率：使用贝叶斯公式，使用样本资料计算逻辑概率，还要使用概率分布，数理统计。

将复杂事件概率求解 转化为： 不同情况下发生的简单事件概率的和。
用来计算复杂事件的概率。

定义：假设{Bn:n=1,2,3,...}是一个概率空间的有限或者无限的分割（既Bn为一完备事件组），且每个集合Bn是一个可测集合，则对任意时间A有全概率公式：

通过条件概率的推导可以看到:P(A∩B) = P(A|B)P(B) = P(B|A)P(A)
带入上述公式。

全概率公式，将对一复杂事件A的概率求解问题转换为在不同情况下或者不同原因Bn下发生的简单概率的求和问题。

现在我们有样本空间S，事件A，A‘和B。
韦恩图：

从上图给出：
P(B) = P(B∩A) + P(B∩A')
将条件概率推导中的公式有：
P(B∩A) = P(B|A)P(A)
将上述公式合并：
P(B) = P(B|A)P(A) + P(B|A')P(A')

解释：如果A和A'构成样本空间，那么事件B的概率就是A和A’的概率分别乘以B对这两个事件的条件概率之和。
公式另一写法：

朴素贝叶斯算法是假设各个特征之间相互独立。

假设一种特定的癌症，发病率为人口的1%。
如果得了这种癌症，检查结果90%可能是呈阳性。
但是你并没有患癌症，检查结果还是呈阳性。所以，假设 如果你没有患上这种特定癌症，有90%可能性是呈阴性的。 这通常叫做 特异性 。

问题：没有任何症状的情况下，你进行了检查，检查结果呈阳性， 那么你认为患上这种特定癌症的可能性是多少？
之前的癌症概率是 1%，敏感型和特殊性是 90%，癌症测试结果呈阳性的人患病的概率有多大？
是： 百分之八又1/3

假定A事件表示得病，P(A)=0.001,这是 先验概率 。（没有做实验之前，我们预计的发病率）
假定B事件表示阳性，那么计算P=(A|B)，这是 后验概率 。（做了试验后，对发病率的估计）
P(A|B)=P(A)P(B|A)/P(B)
用全概率公式，改写分母：
P(A|B)=P(A)P(B|A)/(P(B|A)P(A)+P(B|A反)P(A反))

假设：现在我们有两个人A和B，两人写邮件都会用到love，deal，life这三个单词。
A使用三个单词的频率为：love=0.1,deal=0.8,life=0.1。
B使用三个单词的频率为：love=0.5，deal=0.2,life=0.3。
现在我们有很多封email，假设这封email作者是A或者B是等概率的，
现在有一封email，只包括life和deal两个词，那么这封邮件的作者是A或者B的概率。

计算先验概率
P(emailA) = P(lifeA)P(dealA)P(A) = 0.1* 0.8 * 0.5 = 0.04
P(emailB) = P(lifeB)P(dealB)P(B) = 0.3 * 0.2 * 0.5 = 0.03

当观察到life和deal两个词的条件下，作者是A或者B的概率
计算后验概率
P(emailA|"life,deal") = P(emailA) * f(x)(似然函数) = 0.04 * (1/(0.04+ 0.03)) = 0.57
P(emailB|"life,deal") = P(emialB) * f(x) = 0.03 * (1/(0.04+ 0.03)) = 0.43

全概率：
P(emailA|"life,deal") + P(emailB|"life,deal") = 1

‘肆’ 贝叶斯的学习算法

DATA MINING? 如果是和k-means那个配套用的话，可以使用Bayesian 算法先进行分类，初始所有样本属于一个大类，然后随机的把这个大类切割成2个小类并且计算差派闹错误率，切N次，选错误虚罩率最低的一次切割。然后把2个里面较大的错误率的那个类继续切割，如此反复，直到，切成羡念N个clusters。其中错误率应该有个threshold。

‘伍’ 贝叶斯网络算法Java实现

public static void main(String[] args){
int n=10;//定义n
int[] π={};//定义存放π的数组
for(int i=0;i++;i<n){
π[i]=Ф;
int Pold=g(i,π[i]);//调用g方法
boolean OkToProceed=true;//定义布尔值
while(OkToProceed &&Math.abs(π[i])<u){
//写不下去了。。。好多都不知道是什么方法
}

}
}

‘陆’ 贝叶斯分类器的基本思想是什么

朴素贝叶斯分类器是一种应用基于独立假设的贝叶斯定理的简单概率分类器，之所以成为朴素，应该是Naive的直译，意思为简单，朴素，天真。

1、贝叶斯方法

贝叶斯方法是以贝叶斯原理为基础，使用概率统计的知识对样本数据集进行分类。由于其有着坚实的数学基础，贝叶斯分类算法的误判率是很低的。

贝叶斯方法的特点是结合先验概率和后验概率，即避免了只使用先验概率的主观偏见，也避免了单独使用样本信息的过拟合现象。贝叶斯分类算法在数据集较大的情况下表现出较高的准确率，同时算法本身也比较简单。

2、朴素贝叶斯算和羡禅法

朴素贝叶斯唤尘算法（Naive Bayesian algorithm) 是应用最为广泛的分类算法之一。

朴素贝叶斯派做方法是在贝叶斯算法的基础上进行了相应的简化，即假定给定目标值时属性之间相互条件独立。也就是说没有哪个属性变量对于决策结果来说占有着较大的比重，也没有哪个属性变量对于决策结果占有着较小的比重。

虽然这个简化方式在一定程度上降低了贝叶斯分类算法的分类效果，但是在实际的应用场景中，极大地简化了贝叶斯方法的复杂性。

(6)k2贝叶斯算法扩展阅读

研究意义

人们根据不确定性信息作出推理和决策需要对各种结论的概率作出估计，这类推理称为概率推理。概率推理既是概率学和逻辑学的研究对象，也是心理学的研究对象，但研究的角度是不同的。概率学和逻辑学研究的是客观概率推算的公式或规则。

而心理学研究人们主观概率估计的认知加工过程规律。贝叶斯推理的问题是条件概率推理问题，这一领域的探讨对揭示人们对概率信息的认知加工过程与规律、指导人们进行有效的学习和判断决策都具有十分重要的理论意义和实践意义。

‘柒’ 贝叶斯分类算法和朴素贝叶斯算法的区别

为了测试评估贝叶斯分类器的性能,用不同数据集进行对比实验是必不可少的. 现有的贝叶斯网络实验软件包都是针对特定目的设计的,不能满足不同研究的需要. 介绍了用Matlab在BNT软件包基础上建构的贝叶斯分类器实验平台MBNC,阐述了MBNC的系统结构和主要功能,以及在MBNC上建立的朴素贝叶斯分类器NBC,基于互信息和条件互信息测度的树扩展的贝叶斯分类器TANC,基于K2算法和GS算法的贝叶斯网络分类器BNC. 用来自UCI的标准数据集对MBNC进行测试,实验结果表明基于MBNC所建构的贝叶斯分类器的性能优于国外同类工作的结果,编程量大大小于使用同类的实验软件包,所建立的MBNC实验平台工作正确、有效、稳定. 在MBNC上已经进行贝叶斯分类器的优化和改进实验,以及处理缺失数据等研究工作.

‘捌’ 贝叶斯算法是什么

贝叶斯算法是统计学的一种分类方法，它是一类利用概率统计知识进行分类的算法。在许多场合，朴素贝叶斯（Naïve Bayes，NB)分类算法可以与决策树和神经网络分类算法相媲美，该算法能运用到大型数据库中，而且方法简单、分类准确率高、速度快。

由于贝叶斯定理假设一个属性值对给定类的影响独立于其它属性的值，而此假设在实际情况中经常是不成立的，因此其分类准确率可能会下降。为此，就衍生出许多降低独立性假设的贝叶斯分类算法，如TAN(tree augmented Bayes network)算法。

贝叶斯算法的主要步骤：

1、收集大量的垃圾邮件和非垃圾邮件，建立垃圾邮件集和非垃圾邮件集。

2、提取邮件主题和邮件体中的独立字符串，例如ABC32，￥234等作为TOKEN串并统计提取出的TOKEN串出现的次数即字频。按照上述的方法分别处理垃圾邮件集和非垃圾邮件集中的所有邮件。

3、每一个邮件集对应一个哈希表，hashtable_good对应非垃圾邮件集而hashtable_bad对应垃圾邮件集。表中存储TOKEN串到字频的映射关系。

‘玖’ 贝叶斯分类算法的基本步骤

主要有以下7个步骤：
1. 收集大量的垃圾邮件和非垃圾邮件，建立垃圾邮件集和非垃圾邮件集。
2. 提取邮件主题和邮件体中的独立字符串，例如 ABC32，￥234等作为TOKEN串并统计提取出的TOKEN串出现的次数即字频。按照上述的方法分别处理垃圾邮件集和非垃圾邮件集中的所有邮件。
3. 每一个邮件集对应一个哈希表，hashtable_good对应非垃圾邮件集而hashtable_bad对应垃圾邮件集。表中存储TOKEN串到字频的映射关系。
4. 计算每个哈希表中TOKEN串出现的概率P=（某TOKEN串的字频）/（对应哈希表的长度）。
5. 综合考虑hashtable_good和hashtable_bad，推断出当新来的邮件中出现某个TOKEN串时，该新邮件为垃圾邮件的概率。数学表达式为：
A 事件 ---- 邮件为垃圾邮件；
t1,t2 …….tn 代表 TOKEN 串
则 P （ A|ti ）表示在邮件中出现 TOKEN 串 ti 时，该邮件为垃圾邮件的概率。
设
P1 （ ti ） = （ ti 在 hashtable_good 中的值）
P2 （ ti ） = （ ti 在 hashtable_ bad 中的值）
则 P （ A|ti ） =P2 （ ti ） /[ （ P1 （ ti ） +P2 （ ti ） ] ；
6. 建立新的哈希表hashtable_probability存储TOKEN串ti到P（A|ti）的映射
7. 至此，垃圾邮件集和非垃圾邮件集的学习过程结束。根据建立的哈希表 hashtable_probability可以估计一封新到的邮件为垃圾邮件的可能性。
当新到一封邮件时，按照步骤2，生成TOKEN串。查询hashtable_probability得到该TOKEN 串的键值。
假设由该邮件共得到N个TOKEN 串，t1,t2…….tn,hashtable_probability中对应的值为 P1 ， P2 ， ……PN ， P(A|t1 ,t2, t3……tn) 表示在邮件中同时出现多个TOKEN串t1,t2……tn时，该邮件为垃圾邮件的概率。
由复合概率公式可得
P(A|t1 ,t2, t3……tn)=（P1*P2*……PN）/[P1*P2*……PN+（1-P1）*（1-P2）*……（1-PN）]
当 P(A|t1 ,t2, t3……tn) 超过预定阈值时，就可以判断邮件为垃圾邮件。