贝叶斯分类算法

《贝叶斯分类算法》由会员分享，可在线阅读，更多相关《贝叶斯分类算法（5页珍藏版）》请在装配图网上搜索。

1、贝叶斯分类算法贝叶斯分类算法是统计学的一种分类方法，它是一类利用概率统计知识进行分类的算法。在 许多场合，朴素贝叶斯(NaTve Bayes, NB)分类算法可以与决策树和神经网络分类算法相媲 美，该算法能运用到大型数据库中，而且方法简单、分类准确率高、速度快。由于贝叶斯定理假设一个属性值对给定类的影响独立于其它属性的值，而此假设在实际情况 中经常是不成立的，因此其分类准确率可能会下降。为此，就衍生出许多降低独立性假设的 贝叶斯分类算法，如 TAN(tree augmented Bayes network)算法。目录1分类2分类算法3 基本步骤折叠编辑本段分类(1) 朴素贝叶斯算法设每个数据样

2、本用一个n维特征向量来描述n个属性的值，即:X=xl, x2,，xn，假定 有m个类，分别用C1, C2,，Cm表示。给定一个未知的数据样本X(即没有类标号)，若朴 素贝叶斯分类法将未知的样本X分配给类Ci,则一定是P(CilX)P(CjlX) 1WjWm, jMi根据贝叶斯定理由于P(X)对于所有类为常数，最大化后验概率P(Ci|X)可转化为最大化先验概率 P(XICi)P(Ci)。如果训练数据集有许多属性和元组，计算P(XICi)的开销可能非常大，为此， 通常假设各属性的取值互相独立，这样先验概率P(x1|Ci), P(x2ICi),，P(xn|Ci)可以从训练数据集求得。根据此方法，对一

3、个未知类别的样本X,可以先分别计算出X属于每一个类别Ci的概率 P(XICi)P(Ci),然后选择其中概率最大的类别作为其类别。朴素贝叶斯算法成立的前提是各属性之间互相独立。当数据集满足这种独立性假设时,分类 的准确度较高，否则可能较低。另外，该算法没有分类规则输出。TAN算法(树增强型朴素贝叶斯算法)TAN 算法通过发现属性对之间的依赖关系来降低 NB 中任意属性之间独立的假设。它是在 NB 网络结构的基础上增加属性对之间的关联(边)来实现的。实现方法是:用结点表示属性，用有向边表示属性之间的依赖关系，把类别属性作为根结点， 其余所有属性都作为它的子节点。通常，用虚线代表NB所需的边，用实线

4、代表新增的边。 属性Ai与Aj之间的边意味着属性Ai对类别变量C的影响还取决于属性Aj的取值。这些增加的边需满足下列条件:类别变量没有双亲结点，每个属性有一个类别变量双亲结点 和最多另外一个属性作为其双亲结点。找到这组关联边之后，就可以计算一组随机变量的联合概率分布如下:其中nAi代表的是Ai的双亲结点。由于在TAN算法中考虑了 n个属性中(n-1)个两两属性 之间的关联性，该算法对属性之间独立性的假设有了一定程度的降低，但是属性之间可能存在更多其它的关联性仍没有考虑，因此其适用范围仍然受到限制。折叠编辑本段分类算法 关联规则挖掘是数据挖掘研究的一个重要的、高度活跃的领域。近年来，数据挖掘技术

5、己将 关联规则挖掘用于分类问题，取得了很好的效果。折叠 ARCSARCS(Association Rule Clustering System)基于聚类挖掘关联规则，然后使用规则进行分类。 将关联规则画在 2-D 栅格上，算法扫描栅格，搜索规则的矩形聚类。实践发现，当数据中 存在孤立点时，ARCS比C4.5稍微精确一点。ARCS的准确性与离散化程度有关。从可伸 缩性来说，不论数据库多大， ARCS 需要的存储容量为常数。折叠CBACBA(classification based on associatio n)是基于关联规则发现方法的分类算法。该算法分两个 步骤构造分类器。第一步:发现所有形如

6、xi1Ax = Ci的关联规则，即右部为类别属性值的 类别关联规贝9(classification association rules，CAR)。第二步从已发现的CAR中选择高优先 度的规则来覆盖训练集，也就是说，如果有多条关联规则的左部相同，而右部为不同的类， 则选择具有最高置信度的规则作为可能规则。文献4对该过程进行了较深入的研究，使得 算法在此步骤不需要对训练数据集进行过多的扫描。CBA算法的优点是其分类准确度较高，在许多数据集上比C4.5更精确。此外，上述两步都 具有线性可伸缩性。折叠 CBACBA(Classification Based on Association)是关联分类。此

7、算法把分类规则挖掘和关联规则挖 掘整合到一起。与CART和C4.5只产生部分规则不同的是,CBA产生所有的类关联规则 CARs(Class Association Rules),然后选择最好的规则去覆盖训练集。另外，在此算法的框架 中，数据库可以驻留在磁盘中CAEP使用项集支持度挖掘HV露模式(Emerging Pattern),而EP用于构造分类。CAEP找出 满足给定支持度和增长率阈值的EP。已经发现，在许多数据集上，CAEP比C4.5和基于关 联的分类更精确。一种替代的、基于跳跃的HV露模式JEP(Jnmping Emerging Pattern)是一 种特殊类型的EP,项集的支持度由在

8、一个数据集中的0陡峭地增长到另一个数据集中的非 0。在一此大的多维数据库中，JEP性能优于CAEP,但在一些小型数据库中，CAEP比JEP 优，这二种分类法被认为是互补的。折叠 ADTADT(Association Decision Tree)分二步实现以精确度驱动为基础的过度适合规则的剪枝。第 一步，运用置信度规则建立分类器。主要是采用某种置信度的单调性建立基于置信度的剪枝 策略。第二步，为实现精确性，用关联规则建立一种平衡于DT(Dccision Tree)归纳的精确度 驱动剪枝。这样的结果就是ADT(Association Based Decision Trec)。它联合了大量的关联规

9、则和DT归纳精确性驱动剪枝技术。折叠 CMAR基于多维关联规则的分类算法 CMAR(Classification Based on Multiple Class-Association Rules) 是利用FP-Growth算法挖掘关联规则，建立类关联分布树FP-树。采用CR-树(Classification Rulc Trcc)结构有效地存储关联规则。基于置信度、相关性和数据库覆盖来剪枝。分类的具 体执行采用加权厂来分析。与CBA和C 4.5相比，CMAR性能优异且伸缩性较好。但CMAR 优先生成的是长规则，对数据库的覆盖效果较差;利用加权x统计量进行分类，会造成x统 计量的失真，致使分类值

10、的准确程度降低。折叠 CPARCPAR(Classification Based on Predictive Association Rules)整 合了关联规则分类和传统的基于 规则分类的优点。为避免过度适合，在规则生成时采用贪心算法，这比产生所有候选项集的 效率高;采用一种动态方法避免在规则生成时的重复计算;采用顶期精确性评价规则，并在预 测时应用最优的规则，避免产生冗余的规则。另外，MSR(Minimnm Set Rule)针对基于关联 规则分类算法中产生的关联规则集可能太大的问题，在分类中运用最小关联规则集。在此算 法中，CARS并不是通过置信度首先排序，因为高置信度规则对噪声是很敏感

11、的。采用早期 剪枝力方法可减少关联规则的数量，并保证在最小集中没有不相关的规则。实验证实， MSR 比C45和CBA的错误率要低得多。折叠编辑本段基本步骤主要有以下7 个步骤:1. 收集大量的垃圾邮件和非垃圾邮件，建立垃圾邮件集和非垃圾邮件集。2. 提取邮件主题和邮件体中的独立字符串，例如ABC32,234等作为TOKEN串并统计 提取出的TOKEN串出现的次数即字频。按照上述的方法分别处理垃圾邮件集和非垃圾邮件 集中的所有邮件。3.每一个邮件集对应一个哈希表,hashtable_good对应非垃圾邮件集而hashtable_bad对应垃圾邮件集。表中存储TOKEN串到字频的映射关系。4. 计

12、算每个哈希表中TOKEN串出现的概率P=(某TOKEN串的字频)/(对应哈希表的长度)。5. 综合考虑hashtable_good和hashtable_bad,推断出当新来的邮件中出现某个TOKEN串时， 该新邮件为垃圾邮件的概率。数学表达式为:A 事件 邮件为垃圾邮件;tl,t2 .tn 代表 TOKEN 串则 P ( A|ti )表示在邮件中出现 TOKEN 串 ti 时，该邮件为垃圾邮件的概率。设Pl ( ti ) = ( ti 在 hashtable_good 中的值)P2 ( ti ) = ( ti 在 hashtable_ bad 中的值)则 P ( A|ti ) =P2 ( ti

13、 ) / ( Pl ( ti ) +P2 ( ti ) ;6. 建立新的哈希表hashtable_probability存储TOKEN串ti到P(Alti)的映射7. 至此， 垃圾邮件集和非垃圾邮件集的学习过程结束。 根据建立的哈希表 hashtable_probability 可以估计一封新到的邮件为垃圾邮件的可能性。当新到一封邮件时，按照步骤2,生成TOKEN串。查询hashtable_probability得到该TOKEN 串的键值。假设由该邮件共得到N个TOKEN串，t1,t2.tn,hashtable_probability中对应的值为P1， P2， PN， P(A|t1 ,t2, t3tn)表示在邮件中同时出现多个TOKEN串t1,t2tn 时，该邮件为垃圾邮件的概率。由复合概率公式可得P(A|tl ,t2, t3tn)=(Pl*P2*PN)/P1*P2*PN+(1-P1)*(1-P2)*(1-PN)