[科普中国]-贝叶斯分类算法

分类朴素贝叶斯算法

设每个数据样本用一个n维特征向量来描述n个属性的值，即：X={x1，x2，…，xn}，假定有m个类，分别用C1, C2,…，Cm表示。给定一个未知的数据样本X（即没有类标号），若朴素贝叶斯分类法将未知的样本X分配给类Ci，则一定是

P(Ci|X)>P(Cj|X) 1≤j≤m，j≠i

根据贝叶斯定理

由于P(X)对于所有类为常数，最大化后验概率P(Ci|X)可转化为最大化先验概率P(X|Ci)P(Ci)。如果训练数据集有许多属性和元组，计算P(X|Ci)的开销可能非常大，为此，通常假设各属性的取值互相独立，这样

先验概率P(x1|Ci)，P(x2|Ci)，…，P(xn|Ci)可以从训练数据集求得。

根据此方法，对一个未知类别的样本X，可以先分别计算出X属于每一个类别Ci的概率P(X|Ci)P(Ci)，然后选择其中概率最大的类别作为其类别。

朴素贝叶斯算法成立的前提是各属性之间互相独立。当数据集满足这种独立性假设时,分类的准确度较高，否则可能较低。另外，该算法没有分类规则输出。1

TAN算法（树增强型朴素贝叶斯算法）TAN算法通过发现属性对之间的依赖关系来降低NB中任意属性之间独立的假设。它是在NB网络结构的基础上增加属性对之间的关联(边)来实现的。

实现方法是：用结点表示属性，用有向边表示属性之间的依赖关系，把类别属性作为根结点，其余所有属性都作为它的子节点。通常，用虚线代表NB所需的边，用实线代表新增的边。属性Ai与Aj之间的边意味着属性Ai对类别变量C的影响还取决于属性Aj的取值。

这些增加的边需满足下列条件：类别变量没有双亲结点，每个属性有一个类别变量双亲结点和最多另外一个属性作为其双亲结点。

找到这组关联边之后，就可以计算一组随机变量的联合概率分布如下：

其中ΠAi代表的是Ai的双亲结点。由于在TAN算法中考虑了n个属性中(n-1)个两两属性之间的关联性，该算法对属性之间独立性的假设有了一定程度的降低，但是属性之间可能存

在更多其它的关联性仍没有考虑，因此其适用范围仍然受到限制。

分类算法关联规则挖掘是数据挖掘研究的一个重要的、高度活跃的领域。近年来，数据挖掘技术己将关联规则挖掘用于分类问题，取得了很好的效果。

ARCSARCS(Association Rule Clustering System)基于2聚类挖掘关联规则，然后使用规则进行分类。将关联规则画在2-D栅格上，算法扫描栅格，搜索规则的矩形聚类。实践发现，当数据中存在孤立点时，ARCS比C4.5稍微精确一点。ARCS的准确性与离散化程度有关。从可伸缩性来说，不论数据库多大，ARCS需要的存储容量为常数。

CBACBA(classification based on association)是基于关联规则发现方法的分类算法。该算法分两个步骤构造分类器。第一步：发现所有形如xi1∧x => Ci 的关联规则，即右部为类别属性值的类别关联规则(classification association rules，CAR)。第二步：从已发现的CAR中选择高优先度的规则来覆盖训练集，也就是说，如果有多条关联规则的左部相同，而右部为不同的类，则选择具有最高置信度的规则作为可能规则。文献[4]对该过程进行了较深入的研究，使得算法在此步骤不需要对训练数据集进行过多的扫描。

CBA算法的优点是其分类准确度较高，在许多数据集上比C4.5更精确。此外，上述两步都具有线性可伸缩性。

CBACBA(Classification Based on Association)是关联分类。此算法把分类规则挖掘和关联规则挖掘整合到一起。与CART和C4.5只产生部分规则不同的是,CBA产生所有的类关联规则CARs(Class Association Rules)，然后选择最好的规则去覆盖训练集。另外，在此算法的框架中，数据库可以驻留在磁盘中

CAEP使用项集支持度挖掘HV露模式(Emerging Pattern), 而EP用于构造分类。CAEP找出满足给定支持度和增长率阈值的EP。已经发现，在许多数据集上，CAEP比C4.5和基于关联的分类更精确。一种替代的、基于跳跃的HV露模式JEP(Jnmping Emerging Pattern)是一种特殊类型的EP，项集的支持度由在一个数据集中的0陡峭地增长到另一个数据集中的非0。在一此大的多维数据库中，JEP性能优于CAEP, 但在一些小型数据库中，CAEP比JEP优，这二种分类法被认为是互补的。

ADTADT(Association Decision Trec)分二步实现以精确度驱动为基础的过度适合规则的剪枝。第一步，运用置信度规则建立分类器。主要是采用某种置信度的单调性建立基于置信度的剪枝策略。第二步，为实现精确性，用关联规则建立一种平衡于DT(Dccision Tree)归纳的精确度驱动剪枝。这样的结果就是ADT(Association Based Decision Trec)。它联合了大量的关联规则和DT归纳精确性驱动剪枝技术。

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

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

基本步骤主要有以下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) 超过预定阈值时，就可以判断邮件为垃圾邮件。