基于统计学的方法

已经知道，分类分析是根据数据值及其他约束条件，将未知类别的数据样本划分到某个类别中。对于分类问题，除了前面介绍的确定性分类问题（即其输入样本唯一对应着一个类别）外，还有另一类分类问题是可能出现类别的重叠现象的分类，即来自不同类别的样本从外观特征上具有极大的相似性，此时，只能说某一样本属于某一类别的概率是多大，也就是说，预测给定样本属于一个特定类的概率，对于这类分类问题可以采用基于统计学的贝叶斯分类方法。

本小节主要介绍两种常用的贝叶斯分类算法的基本原理：朴素贝叶斯（naïve Bayes Classifier）和贝叶斯网络（Bayes network）。贝叶斯分类以贝叶斯定理为基础，下面先回顾相关的基本概念及贝叶斯定理。

1）基本概念

（1）先验概率：是指根据历史的资料或主观判断所确定的各事件发生的概率，这一类概率没能经过实验证实，属于检验前的概率。先验概率一般分为两类：一是客观先验概率，是指利用过去的历史资料计算得到的概率；二是主观先验概率，是指在无历史资料或历史资料不全的时候，只能凭借入们的主观经验来判断取得的概率。

（2）后验概率：是指利用贝叶斯公式，结合调查等方式获取了新的附加信息，对先验概率进行修正后得到的更符合实际的概率。

（3）联合概率：是指两个任意事件的乘积的概率，或称之为交事件的概率。

（4）全概率公式：如果影响事件A的所有因素B1， B2，…，B，满足Bi ∩ Bj=（i≠j），且P（UBi） = 1，P（Bi） ＞ 0， i = 1， 2，…， n，则必有：

（5）贝叶斯定理（公式）（后验概率公式）：设先验概率为P（Bi），调查所获的新附加信息为P（Aj | Bi ），其中i = 1， 2，…， n， j = 1， 2，…， m。则贝叶斯公式计算的后验概率为：

上面的概念和公式应用于分类分析时，可以设X是类标号未知的数据样本，H为某种假设，如数据样本X属于某特定的类C。对于分类问题需要确定给定观测数据样本X，假定H成立的概率，即后验概率P（H| X）。

根据贝叶斯定理，可以根据X的先验概率P（X），H的先验概率P（H）和条件H下X的后验概率P（X| H）计算条件X下H的后验概率P（| X）：

2）朴素贝叶斯分类

朴素贝叶斯分类假定一个属性值对给定类的影响独立于其他属性的值。借助贝叶斯定理，朴素贝叶斯分类的基本思想是：

（1）设样本有n个属性（A1 ， A2 ， … ， An ），每个样本可看作是n维空间的一个点x =（x1， x2， …， xn）。

（2）假定有m个不同的类别，C1 ， C2 ， … ， Cm 。 X是一个未知类别的样本。朴素贝叶斯分类算法预测X的类别为后验概率最大的那个类别，即算法将未知类别的样本X归属到类别Ci，当且仅当

P（Ci | X） ＞ P（Cj | X），对于所有的j成立（1≤j≤m， j≠i）即P（Ci | X）最大。

根据贝叶斯定理得知：

P（Ci | X） = P（X | Ci）P（Ci）/P（X）

（3）显然P（X）对于所有类为常数，因此只需P（X|Ci）P（Ci）取最大即可。如果类的先验概率未知，那么通常假定这些类是等概率的，即P（C1） = P（C2） =…=P（Cm），据此只需对P（X|Ci）最大化；否则，最大化P（X|Ci）P（Ci）。

类的先验概率P（Ci）一般可通过P（Ci） = si/s估算，其中si为训练样本中属于类别Ci的样本个数，s为全部训练样本的样本个数。

（4）对于具有许多属性的数据集，计算P（X|Ci）的开销可能很大，为降低P（X|Ci）的开销，做类条件独立的朴素假定，假设各类别相互独立，即各属性的取值相互独立，属性间不存在依赖关系，从而有

P（X | Ci） = P（x1 | Ci）P（x2 | Ci）…P（xn | Ci）

可由训练样本估算P（x1 | Ci），P（x2 | Ci）， …，P（xn|Ci）的值，其中：

①如果Ak是分类属性，则P（xk | Ci） = sik / si（ sik是在属性Ak上具有值xk的类Ci的训练样本数，si是Ci中的训练样本数）。

②如果Ak是连续值属性，则通常假设该属性服从高斯分布。因此，

其中，给定类Ci的训练样本属性Ak的值，g（xk，μci，σci）是属性Ak的高斯密度函数，而μci，σci分别为平均值和标准差。

（5）对未知样本X分类，对每个类Ci，计算P（X|Ci）P（Ci）。样本X被指派到类Ci，当且仅当：

P（X | Ci）P（Ci） ＞ P（X | Ci）P（Ci） （1 ≤ j ≤m，j ≠i）

即X被指派到其P（X|Ci）P（Ci）最大的类Ci。

例5.3：如表5-1中的训练样本数据集，用朴素贝叶斯分类模型预测下面一个新的未知样本的类标号（适合运动，不适合运动）。

（天气=晴朗，温度=凉，湿度=高，风况=强）

表5-1　打网球的天气条件训练数据表

先计算每个类的先验概率P（Ci）：(www.xing528.com)

P（打网球=适合）=9/14 =0.64

P（打网球=不适合）=5/14=0.36

然后估计出条件概率，例如对于风况=强，有：

P（风况=强|打网球=适合）=3/9 =0.33

P（风况=强|打网球=不适合）=3/5 =0.60

同理得出所有条件概率，此处略。

使用以上概率，得到：

P（适合）P（晴朗|适合）P（凉|适合）P（高|适合）P（强|适合）=v1

P（不适合）P（晴朗|不适合）P（凉|不适合）P（高|不适合）P（强|不适合）=v2如果v1＜v2，那么朴素贝叶斯分类器将此样本赋以目标值“打网球=不适合”。

3）贝叶斯网络

朴素贝叶斯分类在分类性能上与决策树和神经网络都是可比的，但朴素贝叶斯分类方法假定属性A1， A2， …， An的值在给定目标值v下是条件独立的，这一假定显著地减少了目标函数学习的计算复杂度。当此条件成立时，朴素贝叶斯分类方法可得到最优贝叶斯分类。然而，在许多情形下，变量之间的依赖可能存在，条件独立假定明显过于严格。

（1）贝叶斯网络模型。贝叶斯网络描述的是一组变量所遵从的概率分布，它通过一组条件概率来指定一组条件独立性假定。朴素贝叶斯方法假定所有变量在给定目标变量值时为条件独立的。与此不同，贝叶斯网络中允许在变量的子集上定义类条件独立性。因此，贝叶斯网络提供了一种折中的方法，它比朴素贝叶斯分类方法中条件独立性的全局假定的限制更少，又比在所有变量中计算条件依赖更可行。

定义5.6（贝叶斯网络）：给定一个随机变量集X=｛X1，X2， …，X n｝，其中Xi是一个m维向量。贝叶斯网络由两部分定义：

第一部分有向无环图。网络中每个节点对应于随机变量集x中的一个随机变量Xi，变量可以是离散的或连续值。每条弧代表一个概率依赖。如果一条弧由节点（变量）Xi到结点（变量）Xj，则xi是Xj的双亲或直接前驱，而Xj是xi的后继。每个变量在给定其直接前驱时条件独立于其非后继。在有向图中的Xi所有双亲（或直接前驱）变量用集合Parents（Xi）表示，图5-3中，节点“平时成绩”和节点“家庭鼓励”就是节点“是否希望上大学”的双亲节点。

第二部分每个变量（节点）有一个条件概率表（CPT， conditional probability table），描述了该变量在给定其直接前驱时的概率分布，即此节点相对于双亲节点的所有可能的条件概率。对网络变量的元组＜X1 ， …， Xnn＞赋以所希望的值（x1 ，… ，xn）的联合概率，由下面的公式计算：

其中，Parents（Xi）表示网络中Xi的直接前驱集合。P（xi| Parent（ Xi））的值等于与结点Xi关联的条件概率表中的值。

贝叶斯网络又称贝叶斯信念网络（Bayesian belief network），在很多情况下，变量之间的直接依赖关系表示的是变量之间的因果关系，因此，有时贝叶斯网络也被称为贝叶斯因果网络（causal network）。

贝叶斯网络表示一组变量的联合概率分布，它将联合概率分布分解保存在有向无环图中，并同时表示了变量之间的条件依赖和条件独立关系。贝叶斯网络内节点可选作输出节点，代表类标号属性。可以有多个输出节点。分类过程不返回单个类标号，而是返回类标号属性的概率分布，即预测每个类的概率。

下面用一个简单的例子来描述贝叶斯网络模型。

例5.4：在对某学校的学生进行调查后，对学生的学习情况进行评估，现有以下几个变量因素：家庭鼓励S（yes，no），平时成绩G（good，bad），家庭经济E（rich， poor），是否希望上大学C（yes，no）。得到如图5-3所示的贝叶斯网络，表示了在以上各个变量上的联合概率分布。

图5-3b的CPT表示：P（C=yes | S=yes，G=good） =0.9， P（C=no | S=yes，G=good） =0.1，P（C=no | S=no，G=good） =0.8等。

（2）贝叶斯网络的推理。一旦构造了贝叶斯网络（包括网络结构以及网络节点上的各个参数），则需要基于该模型计算所需要的其他的概率。贝叶斯网络本身是一种分解存储联合概率分布的方法，于是可以利用式5-3得到联合概率，进而利用式5-4求出各种不同的边缘分布（marginal distribution），再利用条件概率公式以及贝叶斯公式，可以得到任何条件概率。

图5-3　贝叶斯网络模型

如上例中，可以通过已知的“家庭鼓励”、“平时成绩”、“家庭经济”来推断该学生“是否希望上大学”，即C的值。

但这种推理是NP难问题，基于这个问题已经有很多为降低时间复杂度而牺牲精度的近似推理等各种推理方法，这里不做详细介绍。

（3）贝叶斯网络的学习。贝叶斯网络的学习是找出一个能够最真实地反映现有数据集中各个数据变量之间的依赖关系的贝叶斯网络模型。

已经知道，贝叶斯网络包括模型结构和模型参数两个部分，贝叶斯网络的学习同样也主要分为学习参数和学习网络结构两个部分。由于在学习网络时，可能会遇到以下情况：网络结构预先给定或是由数据导出；网络变量是可见的或隐藏在所有或某些训练样本中。因此，贝叶斯网络的学习过程需要解决两个主要问题，一个是结构问题，一个是CPT（条件概率表）问题，包括下面几个情况：

①已知贝叶斯网络结构，学习CPT：

a.如果网络结构已知，并且变量是可见的，贝叶斯信念网络的学习过程由计算条件概率表中的项组成。

b.如果网络结构已知，而某些变量具有空缺值或具有不完全数据时，可以使用梯度下降方法训练贝叶斯网络。 目标是学习条件概率表项的值。

②贝叶斯网络未知时，必须学习它的结构和CPT。学习网络结构，实际上是从所有可能的网络结构候选空间中，挑选出一个好的结构，或者是挑选出多个好的结构，然后再基于这个（或这些）好的结构进行推理或预测。前者称为模型选择（model selection），最终学习得到一个好的网络结构；后者称为选择模型平均（selective model averaging），最终可能学习得到多个较好的网络结构，再利用这些结构共同参与预测。

学习贝叶斯网络，基本有两大类方法，一类是基于得分（score-based）的网络结构搜索方法，这类方法是基于一个对网络的得分函数，在可选网络空间里进行搜索的过程，得分准则可以是最小描述长度（MDL），在所有候选网络结构中选择得分最高的网络结构；一类是基于约束（constraint-based）的网络构造方法，这类方法一般是通过对变量进行条件独立性测试，然后依据得到的条件独立性来构造变量之间的边连接。