贝叶斯算法PPT

数据挖掘分类之主讲人：软件学院卢卫刚贝叶斯网络目录贝叶斯网络2贝叶斯分类1总结4贝叶斯网络的应用及实例3致谢51.1分类的基本概念1.2贝叶斯分类概述1.贝叶斯分类1.1分类的基本概念近几十年来，Internet互联网的普及使得人们获得和存储数据的能力得到逐步的提高，数据规模不断壮大。面对“数据丰富而知识匮乏”的挑战，数据挖掘技术应运而生。数据挖掘是一门多学科的交叉领域，涉及统计学，机器学习、神经网络、模式识别、知识库系统、信息检索、高性能计算和可视化等学科。而数据挖掘中的分类技术是一项非常重要的技术。Q1什么是分类超市中的物品分类生活中的垃圾分类Q1什么是分类生活信息的分类由此可见，分类是跟我们的生活息息相关的东西，分类让生活更加有条理，更加精彩.Q1什么是分类分类就是把一些新的数据项映射到给定类别的中的某一个类别，比如说当我们发表一篇文章的时候，就可以自动的把这篇文章划分到某一个文章类别。分类也称为有监督学习(supervisedlearning),与之相对于的是无监督学习(unsupervisedlearning),比如聚类。分类与聚类的最大区别在于，分类数据中的一部分的类别是已知的，而聚类数据的类别未知。Q2分类问题名称胎生会飞水中生活有腿类别Human是否否是哺乳动物python否否否否非哺乳动物salmon否否是否非哺乳动物whale是否是否哺乳动物frog否否有时是非哺乳动物komodo否否否是非哺乳动物bat是是否是哺乳动物pigeon否是否是非哺乳动物cat是否否是哺乳动物leopard_shark是否是否非哺乳动物turtle否否有时是非哺乳动物penguin否否有时是非哺乳动物porcupine是否否是哺乳动物eel否否是否非哺乳动物salamander否否有时是非哺乳动物gila_monster否否否是非哺乳动物platypus否否否是哺乳动物owl否是否是非哺乳动物dolphin是否是否哺乳动物eagle否是否是非哺乳动物胎生会飞水中生活有腿类别是否是否？Q2分类问题税号去年退税婚姻状况可征税收入逃税1是单身125k否2否婚姻中100k否3否单身70k否4是婚姻中120k否5否离婚95k是6否婚姻中60k否7是离婚220k否8否单身85k是9否婚姻中75k否10否单身90k是(,,120K)X对于去年退税否　婚姻状况＝婚姻中　可征税收入Q2分类的流程动物种类体型翅膀数量脚的只数是否产蛋是否有毛类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类动物A大02是无？动物B中22否是？•根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息，我们能否对新发现的物种，比如动物A，动物B进行分类？动物种类体型翅膀数量脚的只数是否产蛋是否有毛类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类•步骤一：将样本转化为等维的数据特征（特征提取）。–所有样本必须具有相同数量的特征–兼顾特征的全面性和独立性Q2分类的流程动物种类体型翅膀数量脚的只数是否产蛋是否有毛类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类•步骤二：选择与类别相关的特征（特征选择）。–比如，绿色代表与类别非常相关，黑色代表部分相关，灰色代表完全无关Q2分类的流程•步骤三：建立分类模型或分类器（分类）。–分类器通常可以看作一个函数，它把特征映射到类的空间上iiniiiyxxxxf),......,,,(321Q2分类的流程Q3分类的方法对数据挖掘中心的可信技术分类算法的内容及其研究现状进行综述。认为分类算法大体可以分为传统分类算法和基于软件计算的分类法两类，主要包括相似函数，关联规则分类算法，K近邻分类算法，决策树分类算法，贝叶斯分类算法和基于模糊逻辑，遗传算法，粗糙集和神经网络的分类算法。分类的算法有很多种，他们都有各自的优缺点和应用范围，本次我就贝叶斯分类算法展开我的演讲。1.2贝叶斯分类概述贝叶斯分类基于贝叶斯定理，贝叶斯定理是由18世纪概率论和决策论的早起研究者ThomasBayes发明的，故用其名字命名为贝叶斯定理。分类算法的比较研究发现，一种称为朴素贝叶斯分类法的简单贝叶斯分类法可以与决策树和经过挑选的神经网络分类器相媲美。用于大型数据库，贝叶斯分类法也已表现出高准确率和高速度。目前研究较多的贝叶斯分类器主要有四种，分别是：NaiveBayes、TAN、BAN和GBN。ThomasBayes贝叶斯定理贝叶斯定理（Bayes'theorem）是概率论中的一个结果，它跟随机变量的条件概率以及边缘概率分布有关。在有些关于概率的解说中，贝叶斯定理能够告知我们如何利用新证据修改已有的看法。通常，事件A在事件B（发生）的条件下的概率，与事件B在事件A的条件下的概率是不一样的；然而，这两者是有确定的关系，贝叶斯定理就是这种关系的陈述。贝叶斯公式提供了从先验概率P(A)、P(B)和P(B|A)计算后验概率P(A|B)的方法：P(A|B)=P(B|A)*P(A)/P(B)，P(A|B)随着P(A)和P(B|A)的增长而增长，随着P(B)的增长而减少，即如果B独立于A时被观察到的可能性越大，那么B对A的支持度越小。贝叶斯公式贝叶斯法则机器学习的任务：在给定训练数据D时，确定假设空间H中的最佳假设。最佳假设：一种方法是把它定义为在给定数据D以及H中不同假设的先验概率的有关知识下的最可能假设。贝叶斯理论提供了一种计算假设概率的方法，基于假设的先验概率、给定假设下观察到不同数据的概率以及观察到的数据本身。贝叶斯分类的原理贝叶斯分类器的分类原理是通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。也就是说，贝叶斯分类器是最小错误率意义上的优化。根据贝叶斯定理：•由于P(X)对于所有类为常数，只需要P(X|H)*P(H)最大即可。)()()|()()()|(XPHPHXPXPXHPXHP朴素贝叶斯朴素贝叶斯分类是一种十分简单的分类算法，叫它朴素贝叶斯分类是因为这种方法的思想真的很朴素，朴素贝叶斯的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。通俗来说，就好比这么个道理，你在街上看到一个黑人，我问你你猜这哥们哪里来的，你十有八九猜非洲。为什么呢？因为黑人中非洲人的比率最高，当然人家也可能是美洲人或亚洲人，但在没有其它可用信息下，我们会选择条件概率最大的类别，这就是朴素贝叶斯的思想基础。概率最大第一阶段——准备工作阶段，这个阶段的任务是为朴素贝叶斯分类做必要的准备，主要工作是根据具体情况确定特征属性，并对每个特征属性进行适当划分，然后由人工对一部分待分类项进行分类，形成训练样本集合。这一阶段的输入是所有待分类数据，输出是特征属性和训练样本。这一阶段是整个朴素贝叶斯分类中唯一需要人工完成的阶段，其质量对整个过程将有重要影响，分类器的质量很大程度上由特征属性、特征属性划分及训练样本质量决定。第二阶段——分类器训练阶段，这个阶段的任务就是生成分类器，主要工作是计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计，并将结果记录。其输入是特征属性和训练样本，输出是分类器。这一阶段是机械性阶段，根据前面讨论的公式可以由程序自动计算完成。第三阶段——应用阶段。这个阶段的任务是使用分类器对待分类项进行分类，其输入是分类器和待分类项，输出是待分类项与类别的映射关系。这一阶段也是机械性阶段，由程序完成。朴素贝叶斯分类实例检测SNS社区中不真实账号下面讨论一个使用朴素贝叶斯分类解决实际问题的例子。这个问题是这样的，对于SNS社区来说，不真实账号（使用虚假身份或用户的小号）是一个普遍存在的问题，作为SNS社区的运营商，希望可以检测出这些不真实账号，从而在一些运营分析报告中避免这些账号的干扰，亦可以加强对SNS社区的了解与监管。如果通过纯人工检测，需要耗费大量的人力，效率也十分低下，如能引入自动检测机制，必将大大提升工作效率。这个问题说白了，就是要将社区中所有账号在真实账号和不真实账号两个类别上进行分类。下面我们一步一步实现这个过程。首先设C=0表示真实账号，C=1表示不真实账号。1、确定特征属性及划分这一步要找出可以帮助我们区分真实账号与不真实账号的特征属性，在实际应用中，特征属性的数量是很多的，划分也会比较细致，但这里为了简单起见，我们用少量的特征属性以及较粗的划分，并对数据做了修改。我们选择三个特征属性：a1：日志数量/注册天数a2：好友数量/注册天数a3：是否使用真实头像在SNS社区中这三项都是可以直接从数据库里得到或计算出来的。下面给出划分：a1：{a=0.05,0.05a0.2,a=0.2}a2：{a=0.1,0.1a0.8,a=0.8}a3：{a=0（不是）,a=1（是）}2、获取训练样本这里使用运维人员曾经人工检测过的1万个账号作为训练样本。3、计算训练样本中每个类别的频率用训练样本中真实账号和不真实账号数量分别除以一万，得到：P(C=0)=8900/10000=0.89P(C=1)=1100/10000=0.114、计算每个类别条件下各个特征属性划分的频率P(a1=0.05|C=0)=0.3P(a1=0.05|C=1)=0.8P(0.05a10.2|C=0)=0.5P(0.05a10.2|C=1)=0.1P(a10.2|C=0)=0.2P(a10.2|C=1)=0.1P(a2=0.1|C=0)=0.1P(a2=0.1|C=1)=0.7P(0.1a20.8|C=0)=0.7P(0.1a20.8|C=1)=0.2P(a20.8|C=0)=0.2P(a20.8|C=0)=0.1P(a3=0|C=0)=0.2P(a3=1|C=0)=0.8P(a3=0|C=1)=0.9P(a3=1|C=1)=0.15、使用分类器进行鉴别下面我们使用上面训练得到的分类器鉴别一个账号，属性如下a1:日志数量与注册天数的比率为0.1a2:好友数与注册天数的比率为0.2a3:不使用真实头像(a=0)P(C=0)P(x|C=0)=P(C=0)P(0.05a10.2|C=0)P(0.1a20.8|C=0)P(a3=0|C=0)=0.89*0.5*0.7*0.2=0.0623P(C=1)P(x|C=1)=P(C=1)P(0.05a10.2|C=1)P(0.1a20.8|C=1)P(a3=0|C=1)=0.11*0.1*0.2*0.9=0.00198可以看到，虽然这个用户没有使用真实头像，但是通过分类器的鉴别，更倾向于将此账号归入真实账号类别。朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。但是朴素贝叶斯分类有一个限制条件，就是特征属性必须有条件独立或基本独立（实际上在现实应用中几乎不可能做到完全独立）。当这个条件成立时，朴素贝叶斯分类法的准确率是最高的，但不幸的是，现实中各个特征属性间往往并不条件独立，而是具有较强的相关性，这样就限制了朴素贝叶斯分类的能力。于是诞生了一种更高级、应用范围更广的——贝叶斯网络。2.1贝叶斯网络结构概述2.2贝叶斯网络学习2.贝叶斯网络2.3贝叶斯网络推理计算在上一篇文章中我们讨论了朴素贝叶斯分类。这一篇文章中，我们接着上一篇文章的例子，讨论贝叶斯分类中更高级、应用范围更广的一种算法——贝叶斯网络（又称贝叶斯信念网络或信念网络）。复杂的网络2.1贝叶斯网络概述上一篇文章我们使用朴素贝叶斯分类实现了SNS社区中不真实账号的检测。在那个解决方案中，我做了如下假设：i、真实账号比非真实账号平