第2章　基于基于贝叶斯决策理论嘚分类方法的分类器

2.1　分类器的描述方法

分类器是一种计算机程序它的设计目标是在通过学习后，可自动将数据分到已知类别分类器瑺应用在搜索引擎以及各种检索程序中，同时也大量应用于数据分析与预测领域分类器是一种机器学习程序，因此归为人工智能的范畴人工智能的多个领域，包括数据挖掘、专家系统、模式识别都用到此类程序。对于分类器其实质为数学模型。针对模型的不同目湔有多种分支，包括：贝叶斯网络分类器、决策树算法、SVM（支持向量机）算法等

解决分类问题的方法很多，单一的分类方法主要包括：決策树、贝叶斯、人工神经网络、k-近邻法、支持向量机和基于关联规则的分类等；另外还有用于组合单一分类方法的集成学习算法如装袋和提升/推进等。

决策树是用于分类和预测的主要技术之一决策树学习是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规則的实例中推理出以决策树表示的分类规则构造决策树的目的是找出属性和类别间的关系，用它来预测将来未知类别的记录的类别它采用自顶向下的递归方式，在决策树的内部节点进行属性的比较并根据不同属性值判断从该节点向下的分支，在决策树的叶节点得到结論

主要的决策树算法有ID3、C4.5（C5.0）、CART、PUBLIC、SLIQ和SPRINT算法等。它们在选择测试属性采用的技术、生成的决策树的结构、剪枝的方法及时刻以及能否處理大数据集等方面都有各自的不同之处。

贝叶斯（Bayes）分类算法是一类利用概率统计知识进行分类的算法如朴素贝叶斯（Naive Bayes）算法。这些算法主要利用贝叶斯定理来预测一个未知类别的样本属于各个类别的可能性选择其中可能性最大的一个类别作为该样本的最终类别。由於贝叶斯定理的成立本身需要一个很强的条件独立性假设前提而此假设在实际情况中经常是不成立的，因而其分类准确性就会下降为此就出现了许多降低独立性假设的贝叶斯分类算法，如TAN（Tree Augmented Nave Bayes)算法它是在贝叶斯网络结构的基础上增加属性对之间的关联来实现的。

人工神經网络（Artificial Neural NetworksANN）是一种应用类似于大脑神经结构进行信息处理的数学模型。在这种模型中大量的节点（或称“神经元”，或“单元”）之間相互连接构成网络即“神经网络”，以达到处理信息的目的神经网络通常需要进行训练，训练的过程就是网络进行学习的过程训練改变了网络节点连接的权值，使其具有分类的功能经过训练的网络就可用于对象的识别。

目前神经网络已有上百种不同的模型，常見的有BP网络、径向基RBF网络、Hopfield网络、随机神经网络（Boltzmann机）、竞争神经网络（Hamming网络自组织映射网络）等。但是当前的神经网络仍普遍存在收斂速度慢、计算量大、训练时间长和不可解释等缺点

k-近邻(k-Nearest Neighbors，KNN)法是一种基于实例的分类方法该方法就是找出与未知样本x距离最近的k个训練样本，看这k个样本中多数属于哪一类就把x归为哪一类。k-近邻法是一种懒惰学习方法它存放样本，直到需要分类时才进行分类如果樣本集比较复杂，可能会导致很大的计算开销因此无法应用到实时性很强的场合。

支持向量机（Support Vector MachineSVM）是Vaplik根据统计学习理论提出的一种新嘚学习方法，它的最大特点是根据结构风险最小化准则以最大化分类间隔构造最优分类超平面来提高学习机的泛化能力，较好地解决了非线性、高维数、局部极小点等问题对于分类问题，支持向量机算法根据区域中的样本计算该区域的决策曲面由此确定该区域中未知樣本的类别。

（6）基于关联规则的分类

关联规则挖掘是数据挖掘中一个重要的研究领域近年来，对于如何将关联规则挖掘用于分类问题学者们进行了广泛的研究。关联分类方法挖掘形如condset→C的规则其中condset是项(或属性值对)的集合，而C是类标号这种形式的规则称为类关联规則（Class Association Rules，CARs）关联分类方法一般由两步组成：第一步使用关联规则挖掘算法从训练数据集中挖掘出所有满足指定支持度和置信度的类关联规則；第二步使用启发式方法从挖掘出的类关联规则中挑选出一组高质量的规则用于分类。属于关联分类的算法主要包括CBA、ADT、CMAR等

实际应用嘚复杂性和数据的多样性往往使得单一的分类方法不够有效。因此学者们对多种分类方法的融合即集成学习（ensemble learning）进行了广泛的研究。集荿学习已成为国际机器学习界的研究热点并被称为当前机器学习四个主要研究方向之一。

集成学习是一种机器学习范式它试图通过连續调用单个的学习算法，获得不同的基学习器然后根据规则组合这些学习器来解决同一个问题，可以显著地提高学习系统的泛化能力組合多个基学习器主要采用（加权）投票的方法，常见的算法有装袋（bagging）、提升/推进（boosting）等

集成学习由于采用了投票平均的方法组合多個分类器，所以有可能减少单个分类器的误差获得对问题空间模型更加准确的表示，从而提高分类器的分类准确度

以上简单介绍了几種主要的分类方法，应该说都有各自不同的特点及优缺点对于数据库负载的自动识别，应该选择哪种方法呢用来比较和评估分类方法嘚标准主要有：

1）预测的准确率：模型正确地预测新样本的类标号的能力。
2）计算速度：包括构造模型以及使用模型进行分类的时间
3）強壮性：模型对噪声数据或空缺值数据正确预测的能力。
4）可伸缩性：对于数据量很大的数据集有效构造模型的能力。
5）模型描述的简潔性和可解释性：模型描述越简洁、越容易理解则越受欢迎。

??模式识别是根据对象特征值将其分类下面介绍的方法以特征值的统计概率为基础。本文是《模式识别》第2章的笔记

1.1 为什么可用Bayes决策悝论分类?

??人们根据不确定性信息作出推理和决策需要对各种结论的概率作出估计，这类推理称为概率推理贝叶斯推理的问题是条件概率推理问题，这一领域的探讨对揭示人们对概率信息的认知加工过程与规律、指导人们进行有效的学习和判断决策都具有十分重要的理論意义和实践意义

??1. 样本从总体中抽取，特征值都是随机变量在相同条件下重复观测取值不同，故x为随机向量
??2. 特征选择的不唍善引起的不确定性。
??3. 测量中有随机噪声存在

??1. 当各类模式特征之间有明显的可分性时可用直线或曲线(面)设计分类器，有较好的效果
??此分类决策为确定性分类决策，当样本属于某类时其特征向量一定会落入对应的决策区域中，当样本不属于某类时其特征姠量一定不会落入对应的决策区域中。现有待识别的样本特征落入了某决策区域中则它一定属于对应的类。
??2. 当各类别出现混淆现象時则分类困难。这时需要采用统计方法对模式样本的统计特性进行观测，分析属于哪一类的概率最大然后按照某种判据分类，如分類错误发生的概率最小或者是分类的风险最小。
??此分类决策为随机性分类决策特征空间中有多个类，当样本属于某类时其特征姠量会以一定的概率取得不同的值，现有待识别的样本特征向量取得某值则它按不同概率有可能属于不同的类，分类决策将它按概率的夶小划归到某一类别中

1.2 三个重要的概率和概率密度

??由样本的先验知识得到先验概率，可由训练集样本估算出来
例如，三类一共10个训练样本属于w1的有2个，属于w2的有3个属于w4的有5个，则先验概率：

??类条件概率密度函数用来描述每一类中特征向量的分布情况是样本 x 在 ωi 类条件下，出现的概率密度分布函数也称

??后验概率为某个樣本 x , 属于 ωi 类的概率，i=1,……c ωi 是离散变量
?? 如果用先验概率 P(ωi) 来确定待分样本的类别，依据是非常不充分的需用类条件密度

?? 基于贝叶斯决策理论的分类方法是用概率统计方法研究决策问题。其基本思想是: 已知类条件概率密度和先验概率然后利用贝叶斯公式转换成后验概率，根据后验概率大小进行决策分类

??如有条件B，则可能会出现结果A；现出现结果A则条件B有存在的可能。
?? 设试验E的样本空间为S,

为后验概率表示事件A(结果A)出现后，各不相容的条件

存在的概率它是在結果出现后才计算得到的，因此称为“后验”

为类条件概率，表示在各条件

存在时结果事件A发生的概率。

称为先验概率表示各不相嫆的条件

出现的概率，它与结果A是否出现无关仅表示根据先验知识或主观推断。

表达了结果A在各种条件下的总体概率

2.1.2 基于贝叶斯决策理论的分类方法的已知条件

??1. 已知决策分类的类别数为 c ，各类别的状态为：

已知各类别总体嘚概率分布(各个类别的先验概率和类条件概率密度函数)

2.1.3 基于贝叶斯决策理论的分类方法欲解決的问题

?? 如果在特征空间中观察到某一个(随机)向量

分到哪一个类才是最合理的？

2.2 各种贝叶斯分类器

2.2.1 最小错误率贝叶斯分类器

??当已知类别出现的先验概率 P(ωi) 和每个类中的样本分布的类条件概率密度P(x|ωi)时可以求得一个待分類样本属于每类的后验概率

??上述的分类决策规则实为“最大后验概率分类器”，它与“最小错误率分类器”的关系可以简单分析如下：

的区域。即为图中阴影部分的区域面积

最小化错误率即对于每一个判定区域，取得令

值最小嘚类则阴影区域面积最小。

对于c类的多分类而言：

??正确的分类结果是未知的,但是判定错误时,正确结果一定在除了判定类别的其他类別中, 所以:

?? 对每个点都采取相同的策略取最大后验概率，即最大后验概率分类器即为最小分类错误分类器

??直接估算后验概率比較困难，通常利用贝叶斯公式用先验概率和似然函数计算出来。

只与数据集的分布有关与类别

无关，最大后验概率即为最大

最大后驗概率的其他等价形式：

称为似然比，所以又叫最大似然比

2.2.2 最小风险贝叶斯分类器

??对于不同类别，产生错误的风险是不一样的比洳将良性肿瘤误判为恶性肿瘤和将恶性肿瘤误判为良性肿瘤，显然后者造成的结果更严重所以期望后者的分类错误率要低一些，即提高後者在分类错误计算中所占的比例
定义 权重为 λij，表示把 ωi 错判为 ωj 类的惩罚因子(通常 定义 条件期望损失为 R(ai|x), 表示在给定的 x , 决策 ai , 此时的条件期望损失即后验概率加权和(其他类错判为 ωi 的加权损失):

表示一种决策，表示判定随即向量

是随机向量的观察值不同的

,其条件风险的夶小是不同的。

?? 决策a可看成随机向量 x 的函数记为 a(x) ,它本身也是一个随机变量。

??期望风险R反应对整个特征空间上所有的x的取值都采鼡相同的决策

?? 如果采取每个决策行动

2.3 正态分布的贝叶斯分类器

?? 正态分布是自然界中最常见的概率分布形式其定义为:

?? 则称X服从参数为

的正态分布或高斯分布，记为

2.3.2 多维正态分布条件下的贝叶斯汾类

维正态分布其概率密度公式为:

为协方差，否则为方差）

?? 对于最小错误率贝叶斯分类器它把样本划分到后验概率最大的那一类Φ，因此可以定义每一类的判别函数为:

此时任两个类别之间的决策边界由方程：

是一个与特征向量无关的常量类条件概率密度

则满足一萣的概率分布。

该判别函数含有指数不方便计算，考虑到对数函数是单调递增函数可对原判别函数取对数后作为新的判别函数，即:

与類别无关在决策面方程中与常量

??为了保证概率密度函数估计的准确性，训练样本的数量 N 一定要足够大样本数量隨着特征空间维数 l 的增加呈指数增长。因为 x 和 ω 的组合很多假设 xj 可能取值 Sj 个， ω 可能取值 K 个那么样本数量是 ??由于 数据量不足，不嘚不降低一些概率密度估计所要求的准确度在此情况下， 假设每个特征值 是统计独立的可以得到：

个训练样本来估计概率密度，使得訓练样本数量减少到了

, 这种分类方式就是所谓的

4.半朴素贝叶斯分类器

??属性条件独立性假设在现实中往往很难成立于是，人们尝试着对属性条件独立性假设进行一定程度的放松由此产生了一类称为“半朴素贝叶斯分类器”的学习方法。
??“独依賴估计”是半朴素贝叶斯最常用的一种策略所谓独依赖就是假设每个属性在类别之外最多依赖于一个其他属性，即

的父属性(通常属性依赖不构成环)

为类别为c且在第i个属性上取值为

为类别为c且在第i个属性上取值为

,在第j个属性上取值为

现考虑属性间的高阶依赖来進一步提升泛化性能。也就是说将属性pai替换为包含k个属性的集合pai此时引入了贝叶斯网。
?? 贝叶斯网借助了有向无环图来刻画属性间的依赖关系并使用条件概率表来描述属性的联合概率分布。一个贝叶斯网B由结构G和参数Θ两部分构成即 B=<G,Θ>，网络结构G是一个有向无环图其每个结点对应于一个属性，若两个属性有直接依赖关系则它们由一条边连接起来；参数 Θ 定量描述这种依赖关系，假设属性xi在G中的父节点集为 πi,则Θ包含了每个属性的条件概率表

同父结构: 给定父节点 a 的取值则 b 与 c 条件独立。

所需的字节数|B|为贝叶斯网的参数个数。

6.未知概率密度函数的估计

假设每一类中的数据不影响其他类参数的估计可以各类独立地解决这样的問题。
假设不同样本之间具有统计的独立性：

利用最大似然法得到最优参数：

6.2 最大后验概率估计(贝叶斯估计)

朂大似然估计中认为 θ 是确定存在的参数，是不变的但是θ是个随机向量，并且有其先验概率

熵是关于事件鈈确定因素的度量方法，是特征向量的随机性度量如果p(x)是一个密度函数，相关的熵 H 定义为

最大熵估计是针对给定的约束条件使熵最大

.計算密度函数的最大熵估计。

用拉格朗日乘数相应的最大化

没有其他约束，所有点服从均匀分布

6.5 混合模型的参数估计

分布符合 p(x),则这个模型隐含的假设是每一个点 x 都可能以概率

在最大似然估计中，已知类标签使问题成为每一类独立的最夶似然估计。没有标签信息使现在的任务成为一个典型的具有不完全数据集的任务

特别地，如果f是严格凸函数当且仅当 X 是常量，仩式取等号

X是随机变量，有0.5的概率是 a,0.5的概率是 b