第7章--分类与预测--数据挖掘：概念与技术-教学1课件.ppt

《第7章--分类与预测--数据挖掘：概念与技术-教学1课件.ppt》由会员分享，可在线阅读，更多相关《第7章--分类与预测--数据挖掘：概念与技术-教学1课件.ppt（116页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第7章 分类与预测1 分类的任务是通过分析由已知类别数据对象组成的训练数据集，建立描述并区分数据对象类别的分类函数或分类模型（也常常称作分类器）。分类的目的是利用分类模型预测未知类别数据对象的所属类别。2 分类和聚类是两个容易混淆的概念，事实上它们具有显著区别。在分类中，为了建立分类模型而分析的数据对象的类别是已知的，然而，在聚类时处理的所有数据对象的类别都是未知的。因此，分类是有指导的，而聚类是无指导的。3 数据分类与数值预测都是预测问题，都是首先通过分析训练数据集建立模型，然后利用模型预测数据对象。但是，在数据挖掘中，如果预测目标是数据对象在类别属性（离散属性）上的取值（类别），则称为分类

2、；如果预测目标是数据对象在预测属性（连续属性）上的取值或取值区间，则称为预测。例如，对100名男女进行体检，测量了身高和体重，但是事后发现，a和b 两人忘了填写性别，c 和d 两人漏了记录体重。现在根据其他96人的情况，推断a和b 两人的性别是分类，而估计c 和d 两人的体重是预测。4 1.学习阶段（1）建立分类模型：通过分类算法分析训练数据集建立分类模型。训练数据集S 中的元组或记录称为训练样本，每个训练样本由m+1个属性描述，其中有且仅有一个属性称为类别属性，表示训练样本所属的类别。属性集合可用矢量X=（A1,Am,C）表示，其中Ai（1im）对应描述属性，可以具有不同的值域，当一个属性的

3、值域为连续域时，该属性称为连续属性（Numerical Attribute），否则称为离散属性（Discrete Attribute）；C 表示类别属性，C=（c1,c2,ck），即训练数据集有k个不同的类别。6 分类算法有决策树分类算法、神经网络分类算法、贝叶斯分类算法、k-最近邻分类算法、遗传分类算法、粗糙集分类算法、模糊集分类算法等。分类算法可以根据下列标准进行比较和评估。1）准确率。涉及分类模型正确地预测新样本所属类别的能力。2）速度。涉及建立和使用分类模型的计算开销。3）强壮性。涉及给定噪声数据或具有空缺值的数据，分类模型正确地预测的能力。4）可伸缩性。涉及给定大量数据，有效地建立分

4、类模型的能力。5）可解释性。涉及分类模型提供的理解和洞察的层次。分类模型有分类规则、判定树等。7（2）评估分类模型的准确率：利用测试数据集评估分类模型的准确率。测试数据集中的元组或记录称为测试样本。分类模型正确分类的测试样本数占总测试样本数的百分比称为该分类模型的准确率。如果分类模型的准确率可以接受，就可以利用该分类模型对新样本进行分类。否则，需要重新建立分类模型。8 2.分类阶段 分类阶段就是利用分类模型对未知类别的新样本进行分类。数值预测过程：与数据分类过程相似。首先通过分析由预测属性取值已知的数据对象组成的训练数据集，建立描述数据对象特征与预测属性之间的相关关系的预测模型，然后利用预测模

5、型对预测属性取值未知的数据对象进行预测。数值预测技术主要采用回归统计技术，例如，一元线性回归、多元线性回归、非线性回归等。107.2 决策树分类 决策树：一棵决策树由一个根节点，一组内部节点和一组叶节点组成。每个内部节点（包括根节点）表示在一个属性上的测试，每个分枝表示一个测试输出，每个叶节点表示一个类，有时不同的叶节点可以表示相同的类。7.2.1 决策树11 建立一棵决策树，需要解决的问题主要有：1）如何选择测试属性？测试属性的选择顺序影响决策树的结构甚至决策树的准确率，一般使用信息增益度量来选择测试属性。2）如何停止划分样本？从根节点测试属性开始，每个内部节点测试属性都把样本空间划分为若干

6、个（子）区域，一般当某个（子）区域的样本同类时，就停止划分样本，有时也通过阈值提前停止划分样本。13 可能出现如下情况，需要停止建立决策（子）树的递归过程。1）某节点对应的训练数据（子）集为空。此时，该节点作为叶节点并用父节点中占多数的样本类别标识。2）某节点没有对应的（剩余）描述属性。此时，该节点作为叶节点并用该节点中占多数的样本类别标识。15 算法：决策树分类算法Generate_decision_tree（S,A）输入：训练数据集S，描述属性集合A 输出：决策树 步骤：（1）创建对应S 的节点Node;（2）if S 中的样本属于同一类别c then 以c 标识Node 并将Node 作

7、为叶节点返回;（3）if A 为空 then 以S 中占多数的样本类别c 标识Node 并将Node 作为叶节点返回;决策树ID3 算法162.信息增益 在决策树分类算法中使用信息增益度量来选择测试属性。从信息论角度看，通过描述属性可以减少类别属性的不确定性。假设有蕃茄、茄子、黄瓜三种蔬菜，现在对某蔬菜分类。在不给任何描述时，该蔬菜可能是蕃茄、茄子、黄瓜三种之一，不确定性大。在给出该蔬菜是“长的”形状描述时，该蔬菜可能是茄子、黄瓜两种之一，不确定性减小。在给出该蔬菜是“紫的”颜色描述时，该蔬菜只可能是茄子了，不确定性为零。18 离散型随机变量X 的无条件熵定义为 式中，p(xi)为X=xi的概

8、率；u 为X 的可能取值个数。根据H(X)的极值性，当 时，即当不确定性最大时，H(X)最大。根据H(X)的确定性，当 时，即当不确定性为零时，H(X)=0。所以，H(X)反映X 的不确定性。19 给定离散型随机变量Y，离散型随机变量X 的条件熵定义为 式中，p(xiyj)为X=xi,Y=yj的联合概率；p(xi/yj)为已知Y=yj时，X=xi的条件概率；u、v分别为X、Y 的可能取值个数。可以证明，H(X/Y)H(X)。所以，通过Y 可以减少X的不确定性。20 假设训练数据集是关系数据表r1,r2,rn，其中描述属性为A1,A2,Am、类别属性为C，类别属性C的无条件熵定义为 式中，u 为

9、C 的可能取值个数，即类别个数，类别记为c1,c2,cu；si为属于类别ci的记录集合，|si|即为属于类别ci的记录总数。21 给定描述属性Ak（1km），类别属性C 的条件熵定义为 式中，v 为Ak的可能取值个数，取值记为a1,a2,av；sj为Ak=aj的记录集合，|sj|即为Ak=aj的记录数目；sij为Ak=aj且属于类别ci的记录集合，|sij|即为Ak=aj且属于类别ci的记录数目。22 采用类别属性的无条件熵与条件熵的差（信息增益）来度量描述属性减少类别属性不确定性的程度。给定描述属性Ak（1km），类别属性C 的信息增益定义为：G(C,Ak)=E(C)-E(C,Ak)可以看出

10、，G(C,Ak)反映Ak减少C 不确定性的程度，G(C,Ak)越大，Ak对减少C 不确定性的贡献越大。24 例如，假设蔬菜数据表如表7.1所示，“颜色”、“形状”是描述属性，“蔬菜”是类别属性，分别求给定“颜色”、“形状”属性时，“蔬菜”属性的信息增益。表7.1 蔬菜数据表 颜色 形状 蔬菜红 圆 蕃茄紫 长 茄子绿 长 黄瓜结论属性条件属性25解：颜色 形状 蔬菜红 圆 蕃茄紫 长 茄子绿 长 黄瓜共有3个记录，蕃茄、茄子和黄瓜各计一个记录。26颜色 形状 蔬菜红 圆 蕃茄紫 长 茄子绿 长 黄瓜按形状分类，再按蔬菜分类，圆形状只有一种蔬菜，而长形状有两种蔬菜。28则有：G(蔬菜，颜色)1.

11、5850-0=1.5850G(蔬菜，形状)1.5850-0.6667=0.9183说明颜色对蔬菜分类的不确定性小，而形状对蔬菜分类的不确定性大。信息熵反映不确定的程度，为1时表示最大不确定性，为0时表示最小不确定性。信息增益G(C,A)=E(C)-E(C,A)反映属性A 减少C不确定性的程度，G(C,A)越大，属性A 对减少C 不确定性的贡献越大。29 例如，假设顾客数据表如下表所示，“购买计算机”属性是类别属性，其余属性是描述属性，建立决策树。年龄 收入 学生 信誉 购买计算机30 高 否 中 是30 高 否 优 否31.40 高 否 中 是41 中 否 中 是41 低 是 中 是41 低

12、是 优 否31.40 低 是 优 是30 中 否 中 否30 低 是 中 是41 中 是 中 是30 中 是 优 是31.40 中 否 优 是31.40 高 是 中 是41 中 否 优 否31解：考虑根节点：G(购买计算机，年龄)=0.246G(购买计算机，收入)=0.029G(购买计算机，学生)=0.151G(购买计算机，信誉)=0.048 所以根节点的测试属性为“年龄”32 考虑分枝“年龄=30”节点G(购买计算机，收入)=0.571G(购买计算机，学生)=0.971G(购买计算机，信誉)=0.02 所以分枝“年龄=30”节点的测试属性为“学生”。年龄 收入 学生 信誉 购买计算机30 高

13、 否 中 是30 高 否 优 否30 中 否 中 否30 低 是 中 是30 中 是 优 是33 考虑分枝“年龄=3140”节点 因为所有记录属于同一类别 是，所以分枝“年龄=3140”节点为叶节点。年龄 收入 学生 信誉 购买计算机31.40 高 否 中 是31.40 低 是 优 是31.40 中 否 优 是31.40 高 是 中 是34 考虑分枝“年龄=41”节点 G(购买计算机，收入)=0.02 G(购买计算机，学生)=0.02 G(购买计算机，信誉)=0.971 所以分枝“年龄=41”节点的测试属性为“信誉”年龄 收入 学生 信誉 购买计算机41 中 否 中 是41 低 是 中 是41

14、 低 是 优 否41 中 是 中 是41 中 否 优 否35 考虑分枝“学生=否”节点 因为所有记录属于同一类别 否，所以分枝“学生=否”节点为叶节点。年龄 收入 学生 信誉 购买计算机41 中 否 中 是41 中 否 优 否36 考虑分枝“学生=是”节点 因为所有记录属于同一类别 是 所以分枝“学生=是”节点为叶节点。考虑分枝“信誉=优”节点 因为所有记录属于同一类别 否 所以分枝“信誉=否”节点为叶节点。考虑分枝“信誉=中”节点 因为所有记录属于同一类别 是 所以分枝“信誉=是”节点为叶节点。建立的决策树如下图所示。37一棵决策树 购买计算机年龄？是3031.4041否 是 否 是否是 优

15、 中学生？信誉？387.2.3 提取分类规则建立了决策树之后，可以对从根节点到叶节点的每条路径创建一条IF-THEN 分类规则，即沿着路径，每个内部属性-值对（内部节点-分枝对）形成规则前件（IF部分）的一个合取项，叶节点形成规则后件（THEN 部分）。例如，沿着从根节点到叶节点的每条路径，上图的决策树可以转换成以下IF-THEN 分类规则：IF 年龄=30 AND 学生=否 THEN 购买计算机=否IF 年龄=30 AND 学生=是 THEN 购买计算机=是IF 年龄=3140 THEN 购买计算机=是IF 年龄=41 AND 信誉=优 THEN 购买计算机=否IF 年龄=41 AND 信誉

16、=中 THEN 购买计算机=是397.2.4 对新样本分类 假如现在来了一位新顾客，他是一名教师，年龄为45岁，收入较低但信誉很好。商场需要判断该顾客是否会购买计算机？即将该顾客划分到“购买计算机”类呢？还是将他划分到“不购买计算机”类？很显然，利用上面的分类规则，可以判定该顾客不会购买计算机。407.2.5 C4.5 算法Quinlan 建议将E(C,Ak)改为：GRatio=E(C,Ak)/SplitE(C,Ak)，其中：SplitE(C,Ak)=I(|T1|/|T|,|T2|/|T|,|Tn|/|T|)，而T1,T2,Tn 表示以C 的取值分割T 所产生的T 的子集。I 的定义若给定的概

17、率分布P=(p1,p2,pn)，则由该分布传递的信息量称为P 的熵，即：I(P)=-(p1*log2p1+p2*log2p2+pn*log2pn)原描述属性Ak（1km），类别属性C 的条件熵定义为：41 前馈神经网络是分层网络模型，具有一个输入层和一个输出层，输入层和输出层之间有一个或多个隐藏层。每个层具有若干单元，前一层单元与后一层单元之间通过有向加权边相连。7.3.1 前馈神经网络7.3 前馈神经网络分类42 输入层单元的数目与训练样本的描述属性数目对应，通常一个连续属性对应一个输入层单元，一个p值离散属性对应p个输入层单元；输出层单元的数目与训练样本的类别数目对应，当类别数目为2时，输

18、出层可以只有一个单元；目前，隐藏层的层数及隐藏层的单元数尚无理论指导，一般通过实验选取。在输入层，各单元的输出可以等于输入，也可以按一定比例调节，使其值落在1和+1 之间。43 在隐藏层、输出层，每个单元的输入都是前一层各单元输出的加权和，输出是输入的某种函数，称为激活函数。隐藏层、输出层任意单元j 的输入为 式中，wij是单元j 与前一层单元i 之间的连接权值；Oi是单元i 的输出；为改变单元j 活性的偏置，一般在区间 1，1 上取值。44 单元j 的输出为Oj=f(netj)如果f 采用S 型激活函数，即 则 45计算隐藏层、输出层任意单元j 的输出的过程46例如，定义蔬菜分类的前馈神经网

19、络结构。表7.1 蔬菜数据表 颜色 形状 蔬菜红 圆 蕃茄紫 长 茄子绿 长 黄瓜47两层前馈神经网络结构 因为离散属性“颜色”有三个取值、“形状”有两个取值，分别采用3位、2位编码，所以输入层有5个单元。因为类别属性“蔬菜”有三个取值，采用3位编码，所以输出层有3个单元。如果只用一个具有4个单元的隐藏层并且采用全连接，则两层前馈神经网络结构如下图所示。487.3.2 学习前馈神经网络 确定了网络结构（网络层数，各层单元数）之后，应该确定各单元的偏置及单元之间的连接权值。学习过程就是调整这组权值和偏置，使每个训练样本在输出层单元上获得期望输出。学习目的就是找出一组权值和偏置，这组权值和偏置能使

20、所有训练样本在输出层单元上获得期望输出。49 误差后向传播的基本思想是：首先赋予每条有向加权边初始权值、每个隐藏层与输出层单元初始偏置；然后迭代地处理每个训练样本；输入它的描述属性值，计算输出层单元的实际输出；比较实际输出与期望输出（类别属性值），将它们之间的误差从输出层经每个隐藏层到输入层“后向传播”；根据误差修改每条有向加权边的权值及每个隐藏层与输出层单元的偏置，使实际输出与期望输出之间的误差最小。50 对于某个训练样本，实际输出与期望输出的误差Error 定义为 式中，c 为输出层的单元数目；Tk为输出层单元k的期望输出；Ok为输出层单元k的实际输出。希望Error 越小越好！51 首先

21、考虑输出层单元k与前一层单元j 之间的权值wjk的修改量wjk、单元k的偏置 的修改量。式中，l 为避免陷入局部最优解的学习率，一般在区间0,1 上取值。这里采用的是梯度下降法。52 求解上式可以得到权值、偏置的修改量为 式中，Oj为单元j 的输出；Errk是误差Error 对单元k的输入netk的负偏导数，即 53 类似地，隐藏层单元j 与前一层单元i 之间的权值wij 的修改量wij、单元j 的偏置j 的修改量j 为 式中，l 为学习率；Oi为单元i 的输出；Oj为单元j 的输出；Errk为与单元j 相连的后一层单元k的误差；wjk为单元j 与单元k相连的有向加权边的权值。54 权值、偏置

22、的修改公式为 权值、偏置的更新有两种策略：1）处理一个训练样本更新一次，称为实例更新，一般采用这种策略。2）累积权值、偏置，当处理所有训练样本后再一次更新，称为周期更新。55 一般，在训练前馈神经网络时，误差后向传播算法经过若干周期以后，可以使误差Error 小于设定阈值，此时认为网络收敛，结束迭代过程。此外，也可以定义如下结束条件：1）前一周期所有的权值变化都很小，小于某个设定阈值；2）前一周期预测的准确率很大，大于某个设定阈值；3）周期数大于某个设定阈值。56 算法：误差后向传播算法 输入：训练数据集S，前馈神经网络NT，学习率l 输出：经过训练的前馈神经网络NT 步骤：（1）在区间-1,

23、1 上随机初始化NT 中每条有向加权边的权值、每个隐藏层与输出层单元的偏置（2）while 结束条件不满足（2.1）for S 中每个训练样本s57（2.1.1）for 隐藏层与输出层中每个单元j/从第一个隐藏层开始向前传播输入（2.1.2）for 输出层中每个单元k Errk=Ok(1-Ok)(Tk-Ok)58（2.1.3）for 隐藏层中每个单元j/从最后一个隐藏层开始向后传播误差（2.1.4）for NT 中每条有向加权边的权值wij wij=wij+lErrjOi（2.1.5）for 隐藏层与输出层中每个单元的偏置j j=j+lErrj59 误差后向传播算法要求输入层单元的输入是连续值

24、，并对连续值进行规格化以便提高训练的效率与质量。如果训练样本的描述属性是离散属性，则需要对其编码，编码方法有两种：1）p值离散属性：可以采用p位编码。假设p值离散属性的可能取值为a1,a2,ap，当某训练样本的该属性值为a1时，则编码为1,0,0；当某训练样本的该属性值为a2时，则编码为0,1,0；依次类推。2）二值离散属性：除采用2位编码外还可以采用1位编码。当编码为1时表示一个属性值；当编码为0时表示另一个属性值。60 例如，假设训练样本s 的描述属性值与类别属性值分别为1,0,1 与1，前馈神经网络NT 如下图所示，NT 中每条有向加权边的权值、每个隐藏层与输出层单元的偏置如表7.3所示

25、，学习率为0.9。写出输入s 训练NT 的过程。一个前馈神经网络NT61NT 中边的权值、单元的偏置 x1 x2 x3 w14 w15 w24 w25 w34 w35 w46 w56 4 5 6 1 0 1 0.2 0.3 0.4 0.1 0.5 0.2 0.3 0.2 0.4 0.2 0.1 wij和j是随机产生的，l 0.962隐藏层与输出层中单元的输入、输出 单元j 输入netj 输出Oj 4 0.2*1+0.4*0+(0.5)*1+(0.4)=0.7 1/(1+e(0.7)=0.332 5(0.3)*1+0.1*0+(0.2)*1+0.2=0.1 1/(1+e 0.1)=0.525 6

26、(0.3)*0.332+(0.2)*0.525+0.1=0.105 1/(1+e(0.105)=0.474 63隐藏层与输出层中单元的Err 单元j Errj 6 0.474*(1 0.474)*(1 0.474)=0.13115 0.525*(1 0.525)*(0.1311*(0.2)=0.00654 0.332*(1 0.332)*(0.1311*(0.3)=0.0087Errk=Ok(1-Ok)(Tk-Ok)64NT 中边的新权重、单元的新偏置 w46 0.3+0.9*0.1311*0.332=0.261 w56 0.2+0.9*0.1311*0.525=0.138 w14 0.2+0

27、.9*(0.0087)*1=0.192w15 0.3+0.9*(0.0065)*1=0.306w24 0.4+0.9*(0.0087)*0=0.4w25 0.1+0.9*(0.0065)*0=0.1w34 0.5+0.9*(0.0087)*1=0.508 w35 0.2+0.9*(0.0065)*1=0.1946 0.1+0.9*0.1311=0.2185 0.2+0.9*(0.0065)=0.194 4 0.4+0.9*(0.0087)=0.408 wij=wij+lErrjOi j=j+lErrj这里只有一个训练样本，只示例了学习过程中的一次迭代过程。在实际应用中，训练样本多，迭代次数多，

28、这样得到的结果好。激活函数的选取很重要：l 收敛l 收敛速度657.3.3 神经网络分类 学习结束后，神经网络得到一组固定的权值及偏置。新样本到来后，将其描述属性值送入输入层各单元，从输入层到输出层正向传播，计算输出层各单元的值O1,O2,On，令r=max(O1,O2,On)，则第r个输出层单元所代表的类别就是该样本所属的类别。例如，在上例中，只有一个输出层单元，表示只有两个类别（A 类、B 类）。神经网络学习结束后，表7.6中的各权值和偏置都固定。将一个新样本X=（x1,x2,x3）送入输入层后可以计算出O6，若O61，则表示X 应属于A 类；若O60，则表示X 应属于B 类；若O60.5

29、，则拒绝分类。667.4 贝叶斯分类 1.贝叶斯公式 式中，p(x)、p(y)为随机变量X=x、Y=y 的概率；p(x|y)为已知Y=y 时，X=x 的条件概率；p(y|x)为已知X=x 时，Y=y 的条件概率。7.4.1 贝叶斯分类概述67 根据贝叶斯公式，可以得到贝叶斯分类公式：式中，p(a1,am)为m 个描述属性A1=a1,Am=am的联合概率；p(c)为类别属性C=c 的概率，也称为类别c 的先验概率；p(a1,am|c)为已知C=c 时，A1=a1,Am=am的条件概率，也称为类条件概率；p(c|a1,am)为已知A1=a1,Am=am时，C=c 的条件概率，也称为类别c 的后验概

30、率。68 贝叶斯分类的分类阶段就是给定新样本的描述属性值a1,am，根据上述公式，计算各个类别的后验概率，后验概率最大的类别就是新样本的类别属性值，即新样本的类别为：综合上述两式，得到新样本的类别为：贝叶斯分类的学习阶段就是根据训练样本，计算各个类别的先验概率、各个类条件概率。69 例如，训练样本如下表：年龄 收入 学生 信誉 购买计算机30 高 否 中 是30 高 否 优 否31.40 高 否 中 是41 中 否 中 是41 低 是 中 是41 低 是 优 否31.40 低 是 优 是30 中 否 中 否30 低 是 中 是41 中 是 中 是30 中 是 优 是31.40 中 否 优 是3

31、1.40 高 是 中 是41 中 否 优 否70新样本为（31 40,中,否,优），应用贝叶斯分类对新样本进行分类。因为p(是)9/14，p(否)5/14；p(31 40,中,否,优)|是)1/9；p(31 40,中,否,优)|否)0；p(31 40,中,否,优)|是)p(是)1/99/14 1/14；p(31 40,中,否,优)|否)p(否)05/14 0；结论：新样本的类别为 是。71 2.贝叶斯网 如果随机变量（或不相交的随机变量集合）X、Y 和Z满足P(X,Y|Z)=P(X|Z)P(Y|Z)，则称X 和Y 在已知Z 时条件独立，记为X Y|Z。式中，P(X|Z)、P(Y|Z)分别为已知

32、Z 时X、Y 的条件概率分布，P(X,Y|Z)为已知Z 时X、Y 的联合条件概率分布。一个贝叶斯网（Bayesian Network,BN）由一个有向无环图G 和一组参数 组成，记为BN(G,)。其中，有向无环图G 中的节点表示随机变量，有向边表示随机变量之间的直接依赖关系；参数 为节点X 在已知父节点(X)时的条件概率分布P(|(X)，如果节点X 没有父节点，即(X)，则P(X|(X)P(X)。72 在贝叶斯网中，如果已知节点X 的父节点(X)，则X 和它的所有非后代节点nd(X)-(X)条件独立，即X nd(X)-(X)|(X)，称为局部马尔可夫性。根据局部马尔可夫性，贝叶斯网节点X1,.

33、,Xm 的联合概率分布可以分解为条件概率分布的乘积，即 73 例如，在如下图所示的贝叶斯网中，X 和Y 在已知Z 时条件独立，即X Y|Z，并且P(X,Y,Z)=P(Z)P(X|Z)P(Y|Z)。贝叶斯网示例ZX Y如，P(X=0,Y=0,Z=0)=P(Z=0)P(X=0|Z=0)P(Y=0|Z=0)=0.5*0.7*0.2=0.07。74 贝叶斯网可以用于计算贝叶斯分类中的类条件概率。然而，通过分析训练数据集，构造贝叶斯网是一个NP-complete 问题。为了简化计算，一般应用条件独立假设，限定贝叶斯网结构。不同的条件独立假设形成了不同的贝叶斯分类。朴素贝叶斯分类 树增强朴素贝叶斯分类 7

34、57.4.2 朴素贝叶斯分类 朴素贝叶斯分类（Nave Bayesian Classifier）将类别属性C 和描述属性A1,.,Am放在不同的地位，C 的取值决定了A1,.,Am的取值，C 和A1,.,Am有直接依赖关系，也就是说，在贝叶斯网中，节点C 和节点A1,.,Am有有向边相连，C 是A1,.,Am的父节点。为了简化计算，朴素贝叶斯分类假设A1,.,Am在已知C 时条件独立，也就是说，在贝叶斯网中，节点A1,.,Am之间没有有向边相连。因此，朴素贝叶斯分类限定贝叶斯网结构为：(C)，(Ai)C，如下图所示。76朴素贝叶斯分类的贝叶斯网结构 CA1Am77 在朴素贝叶斯分类中，类条件概

35、率可以通过下式估计 综合公式，得到新样本a1,am的类别为：78 例如，训练样本如下：年龄 收入 学生 信誉 购买计算机30 高 否 中 是30 高 否 优 否31.40 高 否 中 是41 中 否 中 是41 低 是 中 是41 低 是 优 否31.40 低 是 优 是30 中 否 中 否30 低 是 中 是41 中 是 中 是30 中 是 优 是31.40 中 否 优 是31.40 高 是 中 是41 中 否 优 否79 新样本为（31 40,中,否,优），应用朴素贝叶斯分类对新样本进行分类。贝叶斯网结构购买计算机年龄 收入 学生 信誉结论：是或否：p(是)p(31 40|是)p(中|是)

36、p(否|是)p(优|是)p(否)p(31 40|否)p(中|否)p(否|否)p(优|否)哪个值大？所有属性独立80因为p(是)9/14，p(31 40|是)4/9；p(中|是)4/9；p(否|是)3/9；p(优|是)3/9；p(是)p(31 40|是)p(中|是)p(否|是)p(优|是)9/144/94/93/93/9 8/567；p(否)5/14；p(31 40|否)0；p(中|否)2/5；p(否|否)4/5；p(优|否)3/5；p(否)p(31 40|否)p(中|否)p(否|否)p(优|否)5/1402/54/53/5 0；所以新样本的类别是 是。新样本为（31 40,中,否,优），81

37、算法：朴素贝叶斯分类参数学习算法 输入：训练数据集S 输出：各个类别的先验概率p(c)，各个类条件概率p(a1,am|c)步骤：（1）for S 中每个训练样本s(as1,asm,cs)（1.1）增加类别cs 的计数cs.count（1.2）for 每个描述属性值asi 增加类别cs 中描述属性值asi的计数cs.asi.count82（2）for 每个类别c（2.1）（2.2）for 每个描述属性Ai（2.2.1）for 每个描述属性值ai（2.3）for 每个a1,am83 算法：朴素贝叶斯分类算法 输入：各个类别的先验概率p(c)，各个类条件概率p(a1,am|c)，新样本r(ar1,a

38、rm)输出：新样本的类别cr 步骤：求所属的最大类别值84 树增强朴素贝叶斯分类（Tree Augmented Nave Bayesian Classifier,TAN）在朴素贝叶斯分类的基础上，允许各个描述属性之间形成树型结构，从而削弱了各个描述属性在给定类别属性时条件独立假设，增强了朴素贝叶斯分类，因此，称为树增强朴素贝叶斯分类。也就是说，在贝叶斯网中，节点C 和节点A1,.,Am有有向边相连，C 是A1,.,Am的父节点，此外，A1,.,Am之间有有向边相连并形成树，根节点的父节点只有C，其它节点的父节点除了C 之外还有一个节点。7.4.3 树增强朴素贝叶斯分类85 例如，一个包括5个描

39、述属性A1,.,A5和1个类别属性C 的树增强朴素贝叶斯分类的贝叶斯网结构如下图所示。树增强朴素贝叶斯分类的贝叶斯网结构CA1A2A4A5A386 在树增强朴素贝叶斯分类中，如果通过分析训练数据集，得到了各个描述属性之间的树型结构，就可以估计类条件概率，从而可以得到新样本的类别。例如，在如上图所示的树增强朴素贝叶斯分类中，类条件概率可以通过下式估计：新样本a1,a5的类别可以通过下式得到：CA1A2A4A5A387 树增强朴素贝叶斯分类树型结构构造方法的基本思想是：首先，计算在给定类别属性C 时，描述属性A1,.,Am之间的依赖强度，共得到 个依赖强度；然后，根据从强到弱的原则选择m-1个依赖

40、强度，添加相应描述属性之间的无向边，并使各个描述属性之间形成无向树；最后，选择根节点，为无向边添加方向形成有向树。其中，可以利用条件互信息描述在给定类别属性C 时，描述属性A1,.,Am之间的依赖强度。88 在给定离散随机变量Z 时，离散随机变量X 和Y 之间的条件互信息定义为 式中，p(x,y,z)为X=x,Y=y,Z=z 的联合概率；p(x,y|z)为已知Z=z 时，X=x,Y=y 的联合条件概率；p(x|z)为已知Z=z 时，X=x 的条件概率；p(y|z)为已知Z=z 时，Y=y 的条件概率。可以证明，X 和Y 在给定Z 时条件独立当且仅当I(X;Y|Z)=0。89 类似地，可以定义在

41、给定类别属性C 时，描述属性Ai 和Aj之间的条件互信息I(Ai;Aj|C)式中，p(ai,aj,c)为Ai=ai,Aj=aj,C=c 的联合概率；p(ai,aj|c)为已知C=c 时，Ai=ai,Aj=aj的联合条件概率；p(ai|c)为已知C=c 时，Ai=ai的条件概率；p(aj|c)为已知C=c 时，Aj=aj的条件概率。90 算法：树增强朴素贝叶斯分类结构学习算法 输入：训练数据集S 输出：树增强朴素贝叶斯分类的贝叶斯网结构TAN 步骤：（1）扫描S，通过式（7.22）计算在给定类别属性C时，描述属性A1,.,Am之间的条件互信息（2）构造一个无向完全图，以描述属性为节点，以条件互信

42、息为边的权重（3）构造上述无向完全图的最大生成树（4）在上述最大生成树中选择一个节点为根节点，为无向边添加方向形成有向树（5）在上述有向树中添加节点C 和C 到各个A1,.,Am的有向边，得到TAN91 例如，训练样本如下表所示L年龄 收入 学生 信誉 购买计算机30 高 否 中 是30 高 否 优 否31.40 高 否 中 是41 中 否 中 是41 低 是 中 是41 低 是 优 否31.40 低 是 优 是30 中 否 中 否30 低 是 中 是41 中 是 中 是30 中 是 优 是31.40 中 否 优 是31.40 高 是 中 是41 中 否 优 否92 新样本为（31 40，中，

43、否，优），应用树增强朴素贝叶斯分类对新样本进行分类。因为I(年龄；收入|购买计算机)0.4196 I(年龄；学生|购买计算机)0.2228 I(年龄；信誉|购买计算机)0.3118 I(收入；学生|购买计算机)0.4196 I(收入；信誉|购买计算机)0.1689 I(学生；信誉|购买计算机)0.0611 所以树增强朴素贝叶斯分类的贝叶斯网结构如下图所示。93贝叶斯网结构购买计算机信誉 年龄 收入 学生94 因为p(是)9/14；p(31 40|是)4/9；p(中|是，31 40)1/4；p(否|是，中)2/4；p(优|是，31 40)2/4；p(是)p(31 40|是)p(中|是，31 40

44、)p(否|是，中)p(优|是，31 40)9/144/91/42/42/4 1/56；p(否)5/14；p(31 40|否)0；p(中|否，31 40)0；p(否|否，中)1；p(优|否，31 40)0；p(否)p(31 40|否)p(中|否，31 40)p(否|否，中)p(优|否，31 40)5/140010 0；所以新样本的类别是 是。957.5 回归分析 事物之间的因果关系涉及两个或两个以上的变量，只要其中一个变量变动了，另一个变量也会跟着变动。表示原因的变量称为自变量，用X 表示，它是固定的（试验时预先确定的），没有随机误差。表示结果的变量称为依变量，用Y 表示。Y 随X 的变化而变化

45、，有随机误差。如果两个变量间的关系属于因果关系，一般用回归来研究。一元回归：依变量Y 在一个自变量X 上的回归称为一元回归；多元回归：依变量Y 在多个自变量X1,X2,Xn上的回归称为多元回归。967.5.1 一元回归分析 1.建立一元线性回归方程 如果两个变量在散点图上呈线性关系，就可用一元线性回归方程来描述。其一般形式为 Y=a+bX 式中，X 是自变量；Y 是依变量；a、b是一元线性回归方程的系数。97 a、b的估计值应是使误差平方和Q(a,b)取最小值的、。式中，n 是训练样本数目，(x1,y1),(xn,yn)是训练样本。98 为了使Q(a,b)取最小值，分别取Q 关于a、b的偏导数

46、，并令它们等于零：99 求解上述方程组，得到唯一的一组解、：其中，100 算法：一元线性回归分析算法 输入：训练数据集S 输出：一元线性回归方程的系数估计、步骤：（1）初始化Sx、Sy、Sxy、Sxx为零（2）for S 中的每个训练样本(x,y)（2.1）Sx=Sx+x/计算（2.2）Sy=Sy+y/计算（2.3）Sxy=Sxy+xy/计算（2.4）Sxx=Sxx+x2/计算 101（3）（4）2.假设检验：检验两个变量之间的线性关系假设是否可以接受。如果变量X 与Y 之间的线性关系假设符合实际，则一元线性回归方程的系数b不应为零。因此，检验假设H0：b=0，H1：b0。如果拒绝假设H0：b

47、=0，则认为变量X 与Y 之间的线性关系假设符合实际。102 t 检验是一种比较常用的假设检验方法。t 检验采用以下检验统计量 t(n-2)式中，为 的标准差。103 当H0为真时，b=0，t(n-2)。所以，H0的拒绝域为 t/2(n-2)式中，为显著性水平。给定显著性水平，如果|t|t/2(n-2)，则拒绝假设H0：b=0，认为回归效果显著，变量X 与Y 之间的线性关系假设符合实际。104 3.预测：经过假设检验，如果变量X 与Y 之间的线性关系假设符合实际，则可用一元线性回归方程进行预测。对于任意x，将其代入方程即可预测出与之对应的y。105年薪数据表工作年数Year 3 8 9 13

48、3 6 11 21 1 16年薪Salary(￥1000)30 57 64 72 36 43 59 90 20 83年薪数据的散点图 例如，假设年薪数据如下表所示，大学毕业以后的“工作年数Year”属性是描述属性，“年薪Salary”属性是预测属性，建立回归方程预测具有10年工作经验的大学毕业生的年薪。106 从年薪数据的散点图可以推测，属性Year 与预测属性Salary 之间大致具有线性相关关系，因此回归方程的形式为Salary(Year)=a+bYear 因为 所以 即：Salary 关于Year 的一元线性回归方程为Salary=23.6+3.5Year 107 采用t 检验法得到：在

49、给定的显著性水平=0.05下，假设H0:b=0 的拒绝域为-,-2.3060 与+2.3060,+，而检验统计量t=10.6724 2.3060。所以，拒绝假设H0:b=0，认为回归效果显著，属性Year 与预测属性Salary 之间的线性关系假设符合实际，可以利用Salary=23.6+3.5Year 预测。具有10年工作经验的大学毕业生的年薪Salary=23.6+3.510=58.6。1087.5.2 多元回归分析 多元回归是指依变量Y 与多个自变量X1,Xp有关。多元线性回归方程是一元线性回归方程的推广，其一般形式为Y=a+b1X1+bpXp 式中，X1,Xp是自变量；Y 是依变量；a

50、,b1,bp是多元（p元）线性回归方程的系数。109 a,b1,bp的估计值应是使误差平方和Q(a,b1,bp)取最小值的：式中，n 是训练样本数目，(xi1,xip,yi)（1in）是训练样本。110 为了使Q(a,b1,bp)取最小值，分别取Q 关于a,b1,bp的偏导数，并令它们等于零：求解上述方程组，即可得到。111品种 比叶重（X1）气孔密度（X2）叶绿素含量（X3）光合速率（Y）V1 1.9993 11.4 4.0575 11.7161V2 V3 例如，某植物有16个品种，它们的比叶重（X1，g/dm2）、气孔密度（X2，个/视野）、叶绿素含量（X3，mg/dm2）和光合速率（Y，