管理学ch02y11数据挖掘理论与应用课件

第2章分类方法

数据分类（dataclassfication）是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。这种类别通常由分类规则组成，可以用来对未来的数据进行分类和预测。

分类的结果是构造一个分类函数或分类模型（分类器），该模型能把数据库中的数据项映射到某一个给定类别。

例：顾客是否会购买笔记本电脑的分类模型

婚姻年龄收入否是否否是单身已婚<30>=30低中高分类目的分析影响数据归类的因素

预测数据所属的类别(classlabel)

分类应用信用额度核准(creditapproval)例如：根据预测的信用等级决定核卡额度目标营销(targetmarketing)例如：找出会购买笔记型计算机的顾客属性医疗诊断(medicaldiagnosis)例如：依病人的症状判断是否患某种疾病．．．

在进行分类或预测挖掘之前，必须首先准备好分类的数据。一般需要对数据进行预处理，以帮助提高分类或预测的准确性、效率和可扩展性。分类所需的数据前期处理

分类的步骤1、建立模型:

利用现有数据找出分类模型

分类规则形式决策树形式或数学公式形式。模型的表示方式有为建立模型而被分析的数据样本形成训练数据集训练数据分类算法IF年龄=30-40且收入=高则信用评估=良好分类规则图3.1数据分类过程中的第一步：学习建模学习建模是建立一个描述已知数据集类别或概念的模型。该模型是在对数据属性进行分析的基础上而构造的。–每个数据属于一个预定义的类，即每个数据有一个类标号，确定它所属的类别。–为建立模型所使用的数据形成训练数据集。其中的单个数据称作训练样本。由于提供了每个训练样本的类标号，该步也称作有指导的学习。

2、评估模型

对模型分类准确率进行估计，如果一个学习所获模型的准确率经测试被认为是可以接受的，那么就可以使用这一模型对未来数据行或对象（其类别未知）进行分类。第二阶段测试样本评估准确性

数据训练样本(trainingsamples)测试样本(testingsamples):第一阶段利用训练样本来建立模型

有多种方法可以用来评估分类的准确率。保持(holdout)方法是一种简单的估计方法。它利用一组带有类别的样本进行分类测试（测试样本随机获得且与训练样本相互独立）。1.对每个测试样本，将已知的类标号和该样本的学习模型类预测比较2.模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比3.测试集要独立于训练样本集，否则会出现“过分适应数据”的情况3、模型使用

找出数据分类的原因利用所获得的模型预测新数据的类型

分类规则测试数据新数据王鹿，30-40，高信用评估如何？良好图3.2数据分类过程中的第二、三步

在图2.1中利用训练数据集学习并获得分类规则知识（模型）；在图2.2中则利用学习获得的分类规则（模型），对已知测试数据进行模型准确率的评估，以及对未知（类别）的新顾客（类别）进行分类预测。分类程序举例分类程序举例步骤1：建立模型训练样本分类模型年龄收入是<30>=30低中高婚姻否否否是单身已婚姓名年龄婚姻收入购买笔记本电脑王大铭<30单身高否陈倩茹<30单身中否张明雄>=30已婚高是田信程>=30单身低是何伟业>=30已婚高是林玮婷>=30已婚低否步骤2：评估模型姓名年龄婚姻收入购买笔记本电脑黄欣怡>=30单身中是胡大明<30单身中否刘志强<30单身低否邓乔贤>=30已婚高否分类模型年龄收入是<30>=30低中高婚姻否否否是单身已婚胡大明否邓乔贤是×测试样本步骤3：使用模型

假设有一位新会员陈建成前来注册，其基本数据为35岁，单身，低收入。依分类模型所预测的结果为“是”，也就是此会员有可能会购买笔记本计算机。该在线购物商店可对此会员进行一连串笔记本计算机的广告营销活动，例如寄送广告，以促使顾客下单购买笔记型计算机

。可以根据以下几条标准对各种分类方法进行比较：

预测准确率，它描述（学习所获）模型能够正确预测未知对象类别或（类别）数值的能力。

速度，它描述在构造和使用模型时的计算效率。

强壮性，它描述在数据带有噪声和有数据遗失情况下，（学习所获）模型仍能进行正确预测的能力。

可扩展性，考虑分类法在数据样本规模扩大时是否仍能在可容忍的时间内求得挖掘的结果

易理解性，它描述学习所获模型表示的可理解程度。分类算法的评估

分类模型的构造方法机器学习方法：决策树法，知识表示是决策树规则归纳，知识表示是产生式规则统计方法：知识表示是判别函数和原型事例贝叶斯法非参数法(近邻学习或基于事例的学习)神经网络方法：BP算法,模型表示是前向反馈神经网络模型粗糙集(roughset)，知识表示是产生式规则

2.1.1决策树基本概念

决策树被广泛的用作决策工具。所谓决策树就是一个类似流程图的树型结构，其中树的每个内部结点代表对一个属性（取值）的测试，其分支就代表测试的每个结果；而树的每个叶结点就代表一个类别。树的最高层结点就是根结点。根据表2-1示例数据集构造决策树如下：2.1决策树

该决策树描述了一个购买电脑的分类模型，利用它可以对一个学生是否会在本商场购买电脑进行分类预测。决策树的中间结点通常用矩形表示；而叶子结点常用椭圆表示。图2.3决策树示意描述

为了对未知数据对象进行分类识别，可以根据决策树的结构对数据集中的属性值进行测试，从决策树的根结点到叶结点的一条路径就形成了对相应对象的类别预测。决策树可以很容易转换为分类规则。决策树归纳方法是目前许多基于规则进行归纳数据挖掘商用系统的基础。在这个例子中，样本向量为：（age,income，student,credit_rating;buys_computers）被决策数据的格式为:（age,income，student,credit_rating）输入新的被决策的记录，可以预测该记录隶属于哪个类。

决策树的特点是非常直观，基于理解，符合人类的思维的特点。而且，决策树很容易转化成决策规则。

构造决策树是采用自上而下的递归构造方法。以多叉树为例，如果一个训练数据集中的数据有几种属性值，则按照属性的各种取值把这个训练数据集再划分为对应的几个子集（分支），然后再依次递归处理各个子集。反之，则作为叶结点。

决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为(a=b)的逻辑判断，其中a是属性，b是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（ID3）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记。2.1.2决策树的构造过程

建树（TreeBuilding）：这是一个递归的过程，最终将得到一棵树。开始，数据都在根节点递归的进行数据分片（选择哪一个属性进行划分？）显然，不同的属性选取顺序将生成不同的决策树。因此，适当地选取属性将生成一棵简单的决策树。（什么时候停止划分？）停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割假设没有样本满足测试属性的值，那么创建一个叶结点，并将其标记为当前结点所含样本集中占统治地位的类别。定义一个停止树进一步生长的条件。剪枝（TreePruning）：去掉一些可能是噪音或者异常的数据。在一个决策树刚刚建立起来的时候，它其中的许多分支都是根据训练样本集合中的异常数据（由于噪声等原因）构造出来的。树枝修剪就是处理这种问题。其实质：消除训练集中的异常和噪声。树枝修剪方法通常利用统计方法删去最不可靠的分支（树枝），以提高今后分类识别的速度和分类识别新数据的能力。通常采用两种方法进行树枝的修剪：事前修剪方法。在建树的过程中，当满足一定条件，例如InformationGain或者某些有效统计量达到某个预先设定的阈值时，结点不再继续分裂，内部结点成为一个叶结点。叶结点取子集中频率最大的类作为自己的标识，或者可能仅仅存储这些实例的概率分布函数。

但确定这样一个合理的阈值常常也比较困难。阈值过大会导致决策树过于简单化，而阈值过小时又会导致多余树枝无法修剪。事后修剪方法：该方法从一个“充分生长”树中，修剪掉多余的树枝（分支）。与建树时的训练集独立的测试数据进入决策树并到达叶结点时，训练数据的classlabel与叶结点的classlabel不同，这时称为发生了分类错误。当树建好之后，对每个内部结点，算法通过每个枝条的出错率进行加权平均，计算如果不剪枝该结点的错误率。如果裁减能够降低错误率，那么该结点的所有分支节点就被剪掉，而该结点成为一片叶。出错率用与训练集数据独立的测试数据校验。最终形成一棵错误率尽可能小的决策树。事前修剪可以与事后修剪相结合，从而构成一个混合的修剪方法。事后修剪比事前修剪需要更多的计算时间，从而可以获得一个更可靠的决策树。1.属性选择度量信息增益——Informationgain

（ID3）增益比率——Gainratio（C4.5）基尼指数——Giniindex

(SLIQ，SPRINT)

…………

在决策树归纳方法中，通常使用信息增益方法来帮助确定生成每个结点时所应采用的合适属性。这样就可以选择具有最高信息增益的属性作为当前结点的测试属性，以便使对之后所划分获得的训练样本子集进行分类所需要信息最小，也就是说，利用该属性进行当前（结点所含）样本集合划分，将会使得所产生的各样本子集中的“不同类别混合程度”降为最低。因此采用这样一种信息论方法将帮助有效减少对象分类所需要的次数，从而确保所产生的决策树是简单的（但不必是最简单的）。信息增益度度量

InformationGain指标的原理来自于信息论。

熵是事件不确定程度的度量，不确定程度越大，熵就越大。把它搞清楚所需要的信息量也就越大。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。所以，信息熵也可以说是系统有序化程度的一个度量。

在decisiontree中，用来定义一个节点的同构型。同构型高者包含较少信息，因此entropy比较小。若一节点包含n种预测值，且每一种预测值在该节点中的出现频率为pi

，则该节点的entropy为

S是s个数据样本的集合。类别属性具有m个不同值,定义m个不同类Ci（i=1,2,…,m）

。si是类Ci中的样本数。pi是任意样本属于Ci的概率，并用si/s估计。

S集合的信息熵：

其中，

(1)设属性A具有v个不同值｛a1，a2，…，av｝。则可用属性A将S划分为v个子集｛S1，S2，…，Sv｝；其中Sj包含S中在A上具有值aj的样本。如果选择A作为测试属性，则这些子集对应于由包含集合S的结点生长出来的分枝。设sij是子集Sj中类Ci的样本数，则按照A划分成子集的熵为：

(2)属性A(集合s)s1s2…sj

信息增益（InformationGain），表示系统由于分类获得的信息量。由系统熵的减少值定量描述。用属性A分类后的信息增益为：而对于一个给定子集Sj，它的信息熵为：其中是sj中的样本属于类ci的概率。(3)(4)

熵是一个衡量系统混乱程度的统计量。熵越大，表示系统越混乱。分类的目的是提取系统信息，使系统向更加有序、有规则组织的方向发展。所以自然而然的，最佳的分裂方案是使熵减少量最大的分裂方案。熵减少量就是InformationGain，所以，最佳分裂就是使Gain(A)最大的分裂方案。

决策树归纳算法计算每个属性的信息增益，具有最高信息增益的属性选择作为给定训练数据集合S的测试属性。创建一个结点，并以该属性为标记，对属性的每一个值创建分枝，并据此划分样本。公式再复习(切记！)：例：决策树的归纳描述。表2-1所示为一个商场顾客数据库（训练样本集合）。表3-1一个商场顾客数据库（训练样本集合）

样本集合的分类属性为：“buys-computer”，该属性有两个不同取值，即{yes，no}，因此就有两个不同的类别（m=2）。设C1对应yes类别，C2对应no类别。C1类别包含9个样本，C2类别包含5个样本。为了计算每个属性的信息增益，首先利用公式（1）计算出对一个给定样本进行分类所需要的信息，具体计算过程如下：

接着需要计算每个属性的（信息）熵。假设先从属性“age”开始，根据属性“age”每个取值在yes类别和no类别中的分布，就可以计算出每个分布所对应的信息。

然后利用公式（2）就可以计算出若根据属性“age”对样本集合进行划分，所获得对一个数据对象进行分类而需要的信息熵为：

由此获得利用属性“age”对样本集合进行划分所获得的信息增益为：

类似可以获得Gain(income)=0.029，以及Gain(student)=0.151，Gain（credit_rating）=0.048。显然选择属性“age”所获得的信息增益最大，因此被作为测试属性用于产生当前分支结点。这个新产生的结点被标记为“age”；同时根据属性“age”的三个不同取值，产生三个不同的分支，当前的样本集合被划分为三个子集，如下图

所示。

图

选择属性“age”产生相应分支的示意描述

其中落入age=30−40子集的样本类别均为yes类别，因此在这个分支末端产生一个叶结点并标记为yes类别。根据如表3-1所示的训练样本集合，最终产生一个如下图所示的决策树。分类规则挖掘的ID3算法

由Quinlan在80年代中期提出的ID3算法是分类规则挖掘算法中最有影响的算法。ID3即决策树归纳（InductionofDecisionTree）。早期的ID算法只能就两类数据进行挖掘（如正类和反类）；经过改进后，现在ID算法可以挖掘多类数据。待挖掘的数据必须是不矛盾的、一致的，也就是说，对具有相同属性的数据，其对应的类必须是唯一的。在ID3算法挖掘后，分类规则由决策树来表示。在ID3算法中，所选的测试属性是从根到当前节点的路径上尚未被考虑的具有最高信息增益的属性。也就是说，生成最少分支决策树的那个属性。ID3算法的优点1.算法的基础理论清晰，算法较简单，2.不存在无解的危险3.利用全部训练数据的统计性质进行决策。ID3算法的缺点1.只能处理分类属性，不能处理数值属性。一个改进的方法是将数值属性划分为若干个区间，形成新的分类属性，但是区间端点的选取是一个问题2.属性间的相关性强调不够3.对训练样本的质量的依赖性很强。Gini系数从另一个方面刻画了信息纯度。对样本集D：其中pj是类别j在样本集中出现的概率。对于任一属性A，将数据集划分为多个子集，若D被划分为D1、D2、…、Dk，则此次划分的GINI系数为

其中，s是D中样本的个数，si为Di中的样本个数。Gini系数

划分前后的差为在上例中数据集的Gini系数为：若用age来划分：

属性age优于属性student，两者计算结果相似。实际上，直接比较所有候选属性的GINI系数，拥有最小GINI系数的属性成为最终测试属性。信息增益率

用信息增益法和Gini系数选择属性时，偏向于选择具有很多取值的属性，因为多个分支能降低信息熵。决策树分支过多会降低决策树的适用性。

为解决此问题，在CART算法中进行了限制，即决策结点只能有两个划分，因此CART算法只能生成二叉树。对候选属性集中的每一个属性，CART算法计算该属性上每种可能划分的GINI系数，找到GINI系数最小的划分作为该属性上的最佳划分，然后比较所有候选属性上最佳划分的GINI系数，拥有最小划分GINI系数的属性成为最终测试属性。

在C4.5用信息增益率来选择属性，信息增益率在信息增益中引入了该节点的分支信息，为分支过多的情况做出了惩罚。分支越多，split-info越大，增益率越小。以上例的age属性为例：

C4.5算法即是ID3算法的后继，也成为以后诸多算法的基础。在应用于单机的决策树算法中，c4.5算法不仅分类准确率高而且速度快。C4.5算法在ID3的基础上加进了对连续属性、属性值空缺情况的处理，对树剪枝也有较为成熟的方法。

C4.5算法与ID3算法的不同点：1.属性选择采用增益率（Gain-ratio）

2.对数值属性值的处理，将数值属性划分为区间3.对未知属性值的处理，用常用值代替或者是用平均值4.是用k次迭代交叉验证评估模型的优劣度5.根据生成的决策树产生一个if-then规则集合交叉纠错方法(Crossvalidation)：数据集被分成k个没有交叉数据的子集，所有子集的大小大致相同。生成器训练和测试共k次；每一次，生成器使用去除一个子集的剩余数据作为训练集，然后在被去除的子集上进行测试。把所有得到的错误率的平均值作为评估错误率。K次交叉验证

决策树归纳算法被广泛应用到许多进行分类识别的应用领域。这类算法无需相关领域知识。归纳的学习与分类识别的操作处理速度都相当快。而对某些数据集合来讲，决策树归纳算法相应的分类准确率是相当高的。决策树中分类规则的获取

决策树所表示的分类知识可以被抽取出来并可用IF-THEN分类规则形式加以表示。从决策树的根结点到任一个叶结点所形成的一条路径就构成了一条分类规则。沿着决策树的一条路径所形成的属性-值偶对就构成了分类规则条件部分（IF部分）中的一个合取项，叶结点所标记的类别就构成了规则的结论内容（THEN部分）。IF-THEN分类规则表达方式易于被人理解，且当决策树较大时，IF-THEN规则表示形式的优势就更加突出。〖例〗对于buys_computer的决策树可提取以下分类规则：IFage＝‘<=30’ANDstudent＝‘no’THENbuys_computer＝‘no’

IFage＝‘<=30’ANDstudent＝‘yes’THENbuys_computer＝‘yes’IFage＝‘30…40’THENbuys_computer＝‘yes’IFage＝‘>40’ANDcredit_rating＝‘excellent’

THENbuys_computer＝‘no’IFage＝‘>40’ANDcredit_rating＝‘fair’

THENbuys_computer＝‘yes’

2.1.

3.决策树方法的扩展

为了进一步提高决策树的性能，很多研究者提出了各种决策树的扩展。主要的扩展方法有：1.多元划分传统的决策树在树的每个结点使用一个属性进行划分，为进一步提高效率，可以在每个结点用几个属性的线性组合进行划分。然而找到最优的线性组合非常困难。采用多元属性划分的决策树的性能要好于传统的决策树，计算复杂程度则远高于一元决策树。超大数据集传统的决策树算法需要所有数据集均在内存中，对于超大规模的数据集来说这是不实际的。在数据集超出内存时，传统的算法往往会引起频繁的内外存交换，训练时间急剧增大，解决超大数据集问题的一个方法是采样。另外一方面可对传统决策树方法进行改进，如SLIQ算法。

SLIQ算法首先把训练样本集划分成若干子集，使每一个子样本集都能放入内存，然后对每个子样本集分别构造一棵决策树，再把这些决策树综合，得到最终决策树。SLIQ算法可以处理大规模的训练样本集，具有较好的伸缩性。与传统决策树算法相比，减少了运行时间。成本矩阵在实际数据中，往往存在一些类别不均衡的数据集，如信用欺诈数据，其中正常数据个数远远大于异常数据个数，然而，找出其中的异常数据对用户来说更为重要。即将正常数据分类为异常数据的重要性要小于将异常数据分类为正常数据的重要性。使用成本矩阵可指定将一个类错误划分到另一个类的成本，对于支持成本矩阵的决策树算法，可以给异常数据分类为正常数据指定更大的误分类成本值，强迫决策树算法更关注异常数据，从而在异常数据类上的性能得到提升，满足应用的需要。决策树可通过对寻找最优划分点的计算方法进行扩展而支持成本矩阵。2.1.

4.决策树方法的评价

与其他分类算法相比，决策树有如下优点：

（1）速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。例如，沿着结点Age->CreditRating->no走下来就能得到一条谓词：

ifthereisaperson(age>40)and(creditratingisexcellent) thenhewillnotbuyacomputer.（2）准确性高：挖掘出的分类规则准确性高，便于理解。一般决策树的劣势：（1）缺乏伸缩性：由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。一个例子：在Irvine机器学习知识库中，最大可以允许的数据集仅仅为700KB，2000条记录。而现代的数据仓库动辄存储几个G-Bytes的海量数据。用以前的方法是显然不行的。（2）为了处理大数据集或连续量的种种改进算法（离散化、取样）不仅增加了分类算法的额外开销，而且降低了分类的准确性。对企业的应用价值极适合用于建立容易了解的model。使用者可对其结果进行人工确认。使用者可依个人的专业知识对decisiontree进行修改。较容易根据model的结果研究各种策略，因此通常会有不错的投资报酬率(ROI)。容易与既有的系统(relationaldatabases)整合操作上不太需要使用者的介入，自动性高。所需的资料前置处理与资料清洗动作极少。其他datamining的技术常要使用者介入来处理missingdata与避免overfitting的情況。1.请用决策树方法，根据下面所给的14个例子，构造相应关于天气状况的决策树。天气温度湿度风况运动晴8585无不适合晴8090有不适合多云8378无适合有雨7096无适合有雨6880无适合有雨6570有不适合多云6465有适合晴7295无不适合晴6970无适合有雨7580无适合晴7570有适合多云7290有适合多云8175无适合有雨7180有不适合使用信息增益进行属性选择类C1运动＝“适合”，类C2对运动＝“不适合”I(s1,s2)=I(9,5)=0.940计算属性天气的熵:决策树天气?湿度?风况?<=75>75无有天晴有雨适合不适合不适合适合适合多云2.2贝叶斯分类

贝叶斯分类器是一个统计分类器。它基于以下假定：待考察的变量遵循某种概率分布，且可以根据这些概率及已观察到的数据进行推理，以做出最优决策。贝叶斯分类器可以发现变量间的潜在关系，预测类成员变量的可能性，即利用统计学中的贝叶斯定理，来预测类成员的概率，即给定一个样本，计算该样本属于一个特定的类的概率。对分类方法进行比较的有关研究结果表明：简单贝叶斯分类器（称为基本贝叶斯分类器）在分类性能上与决策树和神经网络都是可比的。在处理大规模数据库时，贝叶斯分类器已表现出较高的分类准确性和运算性能。

贝叶斯分类方法的主要特点：能充分利用领域知识和其他先验信息，能够显示的计算假设概率，分类结果是两样知识和数据样本信息的综合体现。利用有向图的表示方式，用弧表示变量之间的依赖关系，用概率分布表示依赖关系的强弱。表示方法非常直观，有利于对领域知识的理解。一般情况下，所有属性参加分类，并在分类中潜在的起作用。能进行增量式学习，数据样本都可以增量的提高或降低某种假设的估计概率，并且能够方便的处理不完整数据。贝叶斯分类一般处理的是离散型的对象。2.2.1贝叶斯定理和极大后验假设

设D为一个数据样本，H为某个假设，P(H)表示在没有训练数据时假设H成立的先验概率，P(D)表示观察到的训练数据D的先验概率，P(D|H)表示假设H成立下观察到数据D的概率。贝叶斯分类关心的是给定训练数据D即数据样本D属于一个特定的类别时假设H成立的概率P(H|D)。P(H|D)被称为假设H的后验概率，它反映了观察到数据D后H成立的置信度。先验概率P(H)是独立于数据D的，相反，后验概率P(H|D)反映了训练数据对H的影响。

例如：假设数据样本是水果，描述水果的属性有颜色和形状。假设D为红色和圆状，H为D是一个苹果的假设，因此P(H|D)就表示在已知D是红色和圆状时，确定D为一个苹果的H假设成立的概率；相反P(H)为事前概率，在上述例子中，P(H)就表示任意一个数据对象，它是一个苹果的概率。无论它是何种颜色和形状。与P(H)相比，P(H|D)是建立更多信息基础之上的；而前者则与D无关。

类似的，P(D|H)是建立在H基础之上的D成立概率，也就是说：若已知D是一个苹果那它是红色和圆状的概率可表示为P(D|H)。

由于P(D)、P(H)和P(D|H)的概率值可以由给定的数据计算得到，贝叶斯定理则描述了如何根据P(D)、P(H)和P(D|H)计算获得的P(H|D)，有关的具体公式定义描述如下：(1)

后验概率P(H|D)随着先验概率P(H)和概率P(D|H)的增长而增加，随着概率P(D)的增加而减少。如果D独立于H时被观察到的可能性越大，那么D对H的支持就越小。

贝叶斯分类器在假设空间中寻找给定数据D时可能性最大的假设，具有最大可能性的假设称为极大后验假设。确定极大后验假设的方法是用贝叶斯公式计算每个候选假设的后验概率。因为P(D)是不依赖h的常量，所以计算时去掉P(D)。

在没有任何背景知识的情况下，可假定假设空间中每个假设有相同的先验概率(即对任意的Hi和Hj，P(Hi)=P(Hj))，此时可进一步简化，只考虑用P(D|H)来寻找最大可能假设。P(D|H)常被称作给定H时数据D的似然度，而使P(D|H)最大的假设称为极大似然假设(maximumlikelihood，ML)假设，即hML=argmaxP(D|h)2.2.2贝叶斯网络和贝叶斯分类器贝叶斯网络是一种基于概率推理的有向图。通过可视化网络模型表达问题领域中变量的依赖关系和关联关系。适用于不确定性知识的表达和推理。它可以将具体问题中复杂的变量关系展现在一个网络结构中。以简洁的图形形式表示变量之间内在的联系，运用概率参数描述变量之间的关联强度，将繁琐的联合概率通过局部条件概率表达出来。

一个贝叶斯网络包含两部分内容：

（1）一部分就是有向无环图（DirectedAcyclicGraphae，DAG）。称为贝叶斯网络结构。由若干个结点和连接这些结点的有向边组成。其中的每一个结点代表一个随机变量；每一条有向边代表结点之间的依赖或因果关系。边上的箭头代表因果关系影响的方向性（由父节点指向子结点）。若一条有向边从结点Y到结点Z，那么Y就是Z的一个父结点，Z就是Y的一个子结点。贝叶斯网络结构表达了如下条件独立性假设：一个结点在给定其父节点集的情况下条件独立于其非子孙结点。

下图所示就是一个简单的贝叶斯网络。它表示一个人患肺癌与他家庭的肺癌史有关；也与该人是否吸烟有关。图中的弧同时也表示在给定父结点

FamilyHistory和Smoker情况下，变量LungCancer条件独立于Emphysema。这也就意味着若知道FamilyHistory和Smoker的值，变量Emphysema就不会提供任何有关LungCancer的附加信息。（2）第二个部分就是反映变量之间关联性的局部条件概率分布集合，叫条件概率表（conditionalprobabilitytable简称CPT），概率值表示子节点与其父节点之间的关系强度或置信度，没有父节点的结点的概率为先验概率。对于一个变量Z，CPT定义了一个条件分布P(Z|Parents(Z))，其中Parents(Z)是Z的双亲。如下表所示就是LungCancer的一个CPT表。它描述了对于其父结点每一种组合，LungCancer取每个值的条件概率。例如表的左上角和右下角入口分别表示：有关LungCancer的条件概率列表

用贝叶斯网络进行分类，就是给定训练数据，求新数据对象的最可能的类别。对于给定的一个未知数据对象Z={z1,z2,…,zn}，分类就是预测Z的类变量C的取值。通过先验概率和贝叶斯公式计算类变量的后验概率分布：Z={z1,z2,…,zn}的联合概率可以通过以下公式计算获得：其中P(Zi|Parents(Zi))的值对应于Zi的CPT中的表目。一般情况下，贝叶斯分类器就是应用极大后验假设原理，将数据对象分配给最大的类别。

2.2.3几种常见的贝叶斯分类器模型朴素贝叶斯分类器是贝叶斯分类器中最简单有效而且在实际使用中很成功的一个分类器。朴素贝叶斯分类器假设每一个属性的取值对给定类的影响都独立于其他属性的取值，即给定类变量的条件下各属性变量之间条件独立。这一假设也被称为：类别条件独立，可以帮助有效减少在构造贝叶斯分类器时所需要进行的计算量。1.朴素贝叶斯分类器（NaïveBayes,NB）在朴素贝叶斯分类器的网络结构中，类变量没有父结点，每一个变量均以类变量作为其唯一的父节点，由于结构简单，有时将其与贝叶斯网络分类器相区别，因此称之为朴素的贝叶斯分类器。

朴素贝叶斯分类器的进行分类操作处理的步骤说明如下：（1）每个数据样本均是由一个n维特征向量，X={a1,a2,…an}来描述其n个属性(A1,A2,…An)的具体取值；（2）假设共有m个不同类别，c1,c2,…cm

。给定一个未知类别的数据样本X，分类器将预测X属于事后概率最大的那个类别。也就是说，朴素贝叶斯分类器将未知类别的样本归属到类别cj

，当且仅当：也就是

最大。根据公式（1）可得：(2)（3）由于

对于所有的类别均是相同的，因此只需要取最大即可。由于各类别的事前概率是未知的，类别的事前概率一般可以通过P(cj)=sj/s公式进行估算，其中sj为类别cj中的训练样本个数，s为整个训练样本总数。（3）（4）根据所给定包含多个属性的数据集，直接计算

的运算量是非常大的。为降低计算的开销，基本贝叶斯分类器通常都假设各类别是相互独立的，即各属性的取值是相互独立的即在属性间不存在依赖关系。这样，就会有：

可以根据训练数据样本估算值：若ai是分类属性，就有

这里sij

为训练样本中类别为cj且属性i取ai值的样本数，sj是训练样本中类别为cj

的样本数；若ai是连续值属性，那么一是对其离散化，然后按照离散值处理；另一种是假设属性具有高斯分布用相应的公式计算。属性Ak的高斯密度函数平均值和标准差换言之，X被指派到其最大的类cj。（5）为预测一个未知样本x={a1,a2,…an}的类别，可对每个类别cj

估算相应的。样本x归属类别Cj

，当且仅当：例4：利用贝叶斯分类方法预测一个数据对象类别。利用如表-1所示数据作为训练样本集和贝叶斯分类器来帮助预测未知（类别）数据样本类别。训练数据集包含age、income、student和credit-rating这四个属性，其类别属性为buys-computer。它有两个不同取值：{yes,no}。设C1

对应类别buys-computer=“yes”；C2对应类别buys-computer=“no”

；我们希望分类的未知样本为：为了获得P(X|Ci)P(Ci)其中i=1,2；P(Ci)为每个类别的事前概率，所进行的具体计算结果描述如下：计算P(X|Ci)其中i=1,2，因为：利用以上所获得的计算结果，可以得到：

因此需要首先进行以下运算最后朴素贝叶斯分类器得出结论：对于数据对象x的

buys-computer=“yes”打网球实例:估计P(xi|C)P(p)=9/14P(n)=5/14yesnoyesnoyesnoyesnooutlooksunny2/93/5Temperaturehot2/92/5humidityhigh3/94/5windytrue3/93/5overcast4/90/5mild4/92/5normal6/91/5false6/92/5rainy3/92/5cool3/91/5天气数据统计X=<rain,hot,high,false>P(X|p)·P(p)=

P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p)=3/9·2/9·3/9·6/9·9/14=0.010582P(X|n)·P(n)=

P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n)=2/5·2/5·4/5·2/5·5/14=0.018286样本X通过类n

(don’tplay)来分类分类X

从理论上讲与其它分类器相比，贝叶斯分类器具有最小的错误率。但实际上由于其所依据的类别独立性假设和缺乏某些数据的准确概率分布，从而使得贝叶斯分类器预测准确率受到影响。但各种研究结果表明：与决策树和神经网络分类器相比，贝叶斯分类器在某些情况下具有更好的分类效果。它适合用在预测未知样本的类别，而不适合用来找出数据分类的原因

。

朴素贝叶斯分类器存在的问题是需要满足较强的属性条件独立性的假设，而这个假设在很多实际问题中并不成立。近年来，许多学者都在改进朴素贝叶斯分类器性能方面做了许多工作，主要包括两个方面：一是引入属性选择方法，二是放松条件独立性假设，这两种方法都得到了较好的效果。树扩展的朴素贝叶斯分类器(TAN)NirFriedman等人提出了基于树扩展的朴素贝叶斯分类器。它允许属性变量之间形成树形结构。即对于分类器中每个变量结点可以有两个父节点，一个是分类结点C，另一个可以是其他属性结点，这样在一定程度上降低了朴素贝叶斯分类器中只允许每个变量结点有一个父节点的限制。其结构如图(b)所示。(b)

相对于朴素贝叶斯模型，TAN考虑了属性之间的依赖关系，因此其提高了朴素贝叶斯的分类精度，但是由于只允许一个属性只能有一个父节点属性，因此，其复杂度并不大，因而可以从较小的训练数据中有效估计其各项概率。Friedman基于Chow和Liu学习树结构贝叶斯网络反腐的基础上，提出了一种建立TAN分类器的算法。（1）计算任意两个属性Ai，Aj关于类的条件相互信息(conditionalmutualinformation)：其中xi,xj,c分别表示属性Ai，Aj，C的取值。（2）建立一个无向完全图。其中，结点是属性结点集{A1,A2,…,An}。将两个变量的条件互信息作为依附于相应结点之间边上的权重。（3）建立一颗最大权重生成树。（4）选择一个属性结点作为生成树的根节点，设置每条边的方向，使得所有边的方向都由跟结点向外指，将无向树转变成一颗有向树。（5）加入类结点C，并插入类结点指向各属性结点的有向边。

TAN分类器具有朴素贝叶斯分类器的简单性和健壮性等优点，性能优于朴素贝叶斯分类器。但是由于TAN结构中一个属性至多只能依赖于一个属性节点，因此并不能很好地反映属性之间的复杂的依赖关系，而相对复杂的结构虽然可以更好地反映在属性之间的依赖关系，但由于需要估计的项太多，对于有限的训练数据，性能并不能得到保证3.BAN分类器BAN（bayesiannetworkAugementedNaïveBayes)分类器是另一种增强的朴素贝叶斯分类器。它改进了朴素贝叶斯分类器的条件独立假设，并取消了TAN分类器中属性变量之间必须符合树状结构的要求，它假定属性变量之间存在贝叶斯网络关系而不是树状关系，从而能够表达属性变量间的各种依赖关系。X3CX1X2Xn…

在BAN分类器中，除了类结点外，其余属性结点组成一个贝叶斯网络，其结构是任意的。因此，构建一个BAN费力气的结构需要两个过程：首先用贝叶斯学习方法建立属性变量之间的一个贝叶斯网络，然后再加入类结点及由类结点指向各个属性结点的有向边，使得类结点作为各个属性结点的父节点。对于BAN分类器的参数学习同样可以使用数据集中的观察频率估计。4.贝叶斯多网分类器

贝叶斯多网分类器（BayesianMuti-netClassifier)分类器TAN或BAN分类器的一个扩展。TAN或BAN分类器认为对不同的类别，各个属性变量之间的关系是不变的，即对于不同的类别具有相同的网络结构。而贝叶斯多网分类器则认为对类变量的不同取值，各属性变量之间的关系可能是不一样的。

贝叶斯多网分类器对应于一组贝叶斯网络，类结点的每一个可能的取值都对应一个贝叶斯网络，即将数据集合按照不同的类别分组，对不同的类别在朴素贝叶斯分类器的基础上增添不同的有向边，形成不同的结构。对每一个类别ci都建立一个关于属性变量的贝叶斯网络，称为ci的局部网。局部网的集合及C的先验概率P(C)就称为贝叶斯多网分类器。X3C1X1X2Xn…X3CmX1X2Xn……贝叶斯多网分类器网络结构5.GBN分类器GBN（GeneralBayesianNetwork)分类器是一种无约束的贝叶斯网络分类器。与前面几类分类器的区别是，在前面几类分类器中均将类变量作为一个特殊的结点，类结点在网络结构中是各个属性的父节点，而GBN分类器把类结点作为一个普通结点。X3C1X1X2Xn….GBN分类器网络结构

学习贝叶斯网络的问题描述为：给定U中一组实例构成训练数据集合D={u1,

…,un},找到一个与数据集匹配最好的网络结构B。这样学习贝叶斯网络的问题转化为一个优化问题。处理这个问题的方法是在可能的网络结构构成的空间中进行启发式搜索：每一步中通过添加、翻转或删除一条有向边的操作不断改进网络结构，并确定一个合理的评分函数来评价网络结构对训练数据的匹配程度以指导搜索，直到找到一个评分最高的贝叶斯网络结构。

介绍一种建立贝叶斯网络的评分函数：最小描述长度（MinnmalDescriptionLength,MDL)评分函数。MDL评分是渐近正确的，学习所获

得的贝叶斯网络表达的分布，随样本数目的增加，得分最高的网络将逼近

训练样本的概率分布。用MDL（B|D）表示给定训练数据集D时贝叶斯网络B的MDL评分函数。其中，|B|表示网络参数的个数，是网络每一个参数使用的比特数；第一项表示网络结构B的描述长度，即表示网络需要的比特数；第二项是给定训练数据集D时贝叶斯网络B的对数似然函数，它表示基于概率分布PB描述D所需要的比特数：对数似然的统计意义是对数似然越高，B对数据集D中的概率分布的拟合就越好。使用以上方法可以从训练数据集合得到一个表示变量A1，…,An,C的联合概率分布P(