数据仓库与数据挖掘原理及应用（第二版）_教学课件_ppt 作者 王丽珍 周丽华 陈红梅 第8章

在线教务辅导网： 教材其余课件及动画素材请查阅在线教务辅导网 QQ:349134187 或者直接输入下面地址： 1 第八章 分类与预测 2 第八章 目录 8.1 分类过程 8.2 决策树分类 8.3 前馈神经网络分类 8.4 贝叶斯分类 8.5 回归分析 8.6 本章小结 3 引言（1） 分类的任务是通过分析由已知类别数据对 象组成的训练数据集，建立描述并区分数 据对象类别的分类函数或分类模型（也常 常称作分类器）。 分类的目的是利用分类模型预测未知类别 数据对象的所属类别。 4 引言（2） 分类和聚类是两个容易混淆的概念，事实 上它们具有显著区别。在分类中，为了建 立分类模型而分析的数据对象的类别是已 知的，然而，在聚类时处理的所有数据对 象的类别都是未知的。因此，分类是有指 导的，而聚类是无指导的。 5 引言（3） 数据分类与数值预测都是预测问题，都是 首先通过分析训练数据集建立模型，然后 利用模型预测数据对象。但是，在数据挖 掘中，如果预测目标是数据对象在类别属 性（离散属性）上的取值（类别），则称 为分类；如果预测目标是数据对象在预测 属性（连续属性）上的取值或取值区间， 则称为预测。 例如，对100名男女进行体检，测量了身高 和体重，但是事后发现，a和b两人忘了填 写性别，c和d两人漏了记录体重。现在根 据其他96人的情况，推断a和b两人的性别 是分类，而估计c和d两人的体重是预测。 6 8.1 分类过程（1） 分类过程分为两个阶段：学习阶段与分类 阶段，如图8.1所示，图中左边是学习阶段 ，右边是分类阶段。 图8.1 分类过程 7 8.1 分类过程（2） 1. 学习阶段 （1）建立分类模型：通过分类算法分析训练数据 集建立分类模型。 训练数据集S中的元组或记录称为训练样本，每个训练样 本由m+1个属性描述，其中有且仅有一个属性称为类别 属性，表示训练样本所属的类别。属性集合可用矢量X= （A1, , Am, C）表示，其中Ai（1im）对应描述属性 ，可以具有不同的值域，当一个属性的值域为连续域时 ，该属性称为连续属性（Numerical Attribute），否则称 为离散属性（Discrete Attribute）；C表示类别属性，C= （c1, c2, , ck），即训练数据集有k个不同的类别。 8 8.1 分类过程（3） 分类算法有决策树分类算法、神经网络分类算法 、贝叶斯分类算法、k-最近邻分类算法、遗传分类 算法、粗糙集分类算法、模糊集分类算法等。分 类算法可以根据下列标准进行比较和评估。 1）准确率。涉及分类模型正确地预测新样本所属类别的 能力。 2）速度。涉及建立和使用分类模型的计算开销。 3）强壮性。涉及给定噪声数据或具有空缺值的数据，分 类模型正确地预测的能力。 4）可伸缩性。涉及给定大量数据，有效地建立分类模型 的能力。 5）可解释性。涉及分类模型提供的理解和洞察的层次。 分类模型有分类规则、判定树等。 9 8.1 分类过程（4） （2）评估分类模型的准确率：利用测试数据 集评估分类模型的准确率。 测试数据集中的元组或记录称为测试样本。 分类模型正确分类的测试样本数占总测试样本数 的百分比称为该分类模型的准确率。如果分类模 型的准确率可以接受，就可以利用该分类模型对 新样本进行分类。否则，需要重新建立分类模型 。 10 8.1 分类过程（5） 评估分类模型准确率的方法有保持（holdout）、k- 折交叉确认等。 保持方法将已知类别的样本随机地划分为训练数据集与 测试数据集两个集合，一般，训练数据集占2/3，测试数 据集占1/3。分类模型的建立在训练数据集上进行，分类 模型准确率的评估在测试数据集上进行。 k-折交叉确认方法将已知类别的样本随机地划分为大小大 致相等的k个子集S1, , Sk，并进行k次训练与测试。第i次 ，子集Si作为测试数据集，分类模型准确率的评估在其上 进行，其余子集的并集作为训练数据集，分类模型的建 立在其上进行。进行k次训练得到k个分类模型，当利用 分类模型对测试样本或者新样本进行分类时，可以综合 考虑k个分类模型的分类结果，将出现次数最多的分类结 果作为最终的分类结果。 11 8.1 分类过程（6） 2. 分类阶段 分类阶段就是利用分类模型对未知类别的新样本进行分 类。 数值预测过程： 与数据分类过程相似。首先通过分析由预测属性取值已 知的数据对象组成的训练数据集，建立描述数据对象特 征与预测属性之间的相关关系的预测模型，然后利用预 测模型对预测属性取值未知的数据对象进行预测。 数值预测技术主要采用回归统计技术，例如，一元线性 回归、多元线性回归、非线性回归等。 12 8.2 决策树分类 8.2.1 决策树（1） 决策树：一棵决策树由一个根节点，一组 内部节点和一组叶节点组成。每个内部节 点（包括根节点）表示在一个属性上的测 试，每个分枝表示一个测试输出，每个叶 节点表示一个类，有时不同的叶节点可以 表示相同的类。 13 8.2.1 决策树（2） 图8.2 判断顾客是否购买计算机的决策树 14 8.2.1 决策树（3） 建立一棵决策树，需要解决的问题主要有 ： 1）如何选择测试属性？ 测试属性的选择顺序影响决策树的结构甚至决策树的 准确率，一般使用信息增益度量来选择测试属性。 2）如何停止划分样本？ 从根节点测试属性开始，每个内部节点测试属性都把 样本空间划分为若干个（子）区域，一般当某个（子 ）区域的样本同类时，就停止划分样本，有时也通过 阈值提前停止划分样本。 15 8.2.2 建立决策树（1） 1. 算法思想及描述 首先，在整个训练数据集S、所有描述属性A1, A2, , Am 上递归地建立决策树。即将S作为根节点；如果S中的样 本属于同一类别，则将S作为叶节点并用其中的类别标识 ，决策树建立完成（递归出口）； 否则在S上计算当给定Ak（1km）时类别属性C的信息增 益G(C, Ak)，选择信息增益最大的Ai作为根节点的测试属 性；如果Ai的取值个数为v（取值记为a1, a2, , av），则 Ai将S划分为v个子集S1, S2, , Sv（Sj（1jv）为S中Ai=aj 的样本集合），同时根节点产生v个分枝与之对应。其次 ，分别在训练数据子集S1, S2, , Sv、剩余描述属性A1, , Ai-1, Ai+1, , Am上采用相同方法递归地建立决策树子树（ 递归）。 16 8.2.2 建立决策树（2） 可能出现如下情况，需要停止建立决策（ 子）树的递归过程。 1）某节点对应的训练数据（子）集为空。此时 ，该节点作为叶节点并用父节点中占多数的样 本类别标识。 2）某节点没有对应的（剩余）描述属性。此时 ，该节点作为叶节点并用该节点中占多数的样 本类别标识。 17 8.2.2 建立决策树（3） 算法：决策树分类算法Generate_decision_tree （S, A） 输入：训练数据集S，描述属性集合A 输出：决策树 步骤： （1）创建对应S的节点Node （2）if S中的样本属于同一类别c then 以c标识Node并将Node作为叶节点返回 （3）if A为空 then 以S中占多数的样本类别c标识Node并将Node作为叶节点 返回 18 8.2.2 建立决策树（4） （4）从A中选择对S而言信息增益最大的描 述属性Ai作为Node的测试属性 （5）for Ai的每个可能取值aj（1jv ）/设 Ai的可能取值为a1, a2, , av （5.1）产生S的一个子集Sj /Sj（1jv）为 S中Ai=aj的样本集合 （5.2）if Sj为空 then 创建对应Sj的节点Nj，以S中占多数的样本类别c标识Nj ，并将Nj作为叶节点形成Node的一个分枝 （5.3）else 由Generate_decision_tree（Sj, A-Ai ）创建子树形成Node的一个分枝 19 8.2.2 建立决策树（5） 2. 信息增益：在决策树分类算法中使用信 息增益度量来选择测试属性。 从信息论角度看，通过描述属性可以减少 类别属性的不确定性。 假设有蕃茄、茄子、黄瓜三种蔬菜，现在对某 蔬菜分类。在不给任何描述时，该蔬菜可能是 蕃茄、茄子、黄瓜三种之一，不确定性大。在 给出该蔬菜是“长的”形状描述时，该蔬菜可能 是茄子、黄瓜两种之一，不确定性减小。在给 出该蔬菜是“紫的”颜色描述时，该蔬菜只可能 是茄子了，不确定性为零。 20 8.2.2 建立决策树（6） 离散型随机变量X的无条件熵定义为 式中，p(xi)为X= xi的概率；u为X的可能取 值个数。 根据H(X)的极值性，当 时，即 当不确定性最大时，H(X)最大。根据H(X) 的确定性，当 时，即当不确定性 为零时，H(X)=0。所以，H(X)反映X的不确 定性。 21 8.2.2 建立决策树（7） 给定离散型随机变量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的不确定性。 22 8.2.2 建立决策树（8） 假设训练数据集是关系数据表r1, r2, , rn， 其中描述属性为A1, A2, , Am、类别属性为 C，类别属性C的无条件熵定义为 式中，u为C的可能取值个数，即类别个数 ，类别记为c1, c2, , cu；si为属于类别ci的 记录集合，|si|即为属于类别ci的记录总数。 23 8.2.2 建立决策树（9） 给定描述属性Ak（1km），类别属性C的 条件熵定义为 式中，v为Ak的可能取值个数，取值记为a1, a2, , av；sj为Ak=aj的记录集合，|sj|即为 Ak=aj的记录数目；sij为Ak=aj且属于类别ci的 记录集合，|sij|即为Ak=aj且属于类别ci的记 录数目。 24 8.2.2 建立决策树（10） 不同描述属性减少类别属性不确定性的程 度不同，即不同描述属性对减少类别属性 不确定性的贡献不同。 例如，假设有蕃茄、茄子、黄瓜三种蔬菜，现 在对某蔬菜分类，形状描述与颜色描述的贡献 是不同的。在给出该蔬菜的颜色描述时，如果 颜色是红的，则该蔬菜是蕃茄；如果颜色是紫 的，则该蔬菜是茄子；如果颜色是绿的，则该 蔬菜是黄瓜，不确定性减少为0。而在给出该蔬 菜的形状描述时，如果形状是圆的，则该蔬菜 是蕃茄；如果形状是长的，则该蔬菜可能是茄 子，也可能是黄瓜，不确定性还是存在。 25 8.2.2 建立决策树（11） 采用类别属性的无条件熵与条件熵的差（ 信息增益）来度量描述属性减少类别属性 不确定性的程度。 给定描述属性Ak（1km），类别属性C的 信息增益定义为 G(C, Ak)=E(C)-E(C, Ak) 可以看出，G(C, Ak)反映Ak减少C不确定性 的程度，G(C, Ak)越大，Ak对减少C不确定 性的贡献越大。 26 8.2.2 建立决策树（12） 例8.1 假设蔬菜数据表如表8.1所示，“颜色”、“形 状”是描述属性，“蔬菜”是类别属性，分别求给定“ 颜色”、“形状”属性时，“蔬菜”属性的信息增益。 表8.1 蔬菜数据表 颜色形状蔬菜 红圆蕃茄 紫长茄子 绿长黄瓜 27 8.2.2 建立决策树（13） G(蔬菜，颜色)1.5850-0=1.5850 G(蔬菜，形状)1.5850-0.6667=0.9183 28 8.2.2 建立决策树（14） 例8.2 建立例8.1的决策树。 因为G(蔬菜，颜色)G(蔬菜，形状)，所以选择“颜色”属 性作为根节点的测试属性，得到的决策树如图8.3所示。 图8.3 例8.1的决策树 29 8.2.2 建立决策树（15） 例8.3 假设顾客数据表如表8.2所示，“购买计算机” 属性是类别属性，其余属性是描述属性，建立决 策树。 考虑根节点： G(购买计算机，年龄)=0.246 G(购买计算机，收入)=0.029 G(购买计算机，学生)=0.151 G(购买计算机，信誉)=0.048 所以根节点的测试属性为“年龄” 考虑分枝“年龄=30”节点 G(购买计算机，收入)=0.571 G(购买计算机，学生)=0.971 G(购买计算机，信誉)=0.02 所以分枝“年龄=30”节点的测试属性为“学生” 30 8.2.2 建立决策树（16） 考虑分枝“年龄=3140”节点 因为所有记录属于同一类别是，所以分枝“年 龄=3140”节点为叶节点。 考虑分枝“年龄=41”节点 G(购买计算机，收入)=0.02 G(购买计算机，学生)=0.02 G(购买计算机，信誉)=0.971 所以分枝“年龄=41”节点的测试属性为“信誉” 考虑分枝“学生=否”节点 因为所有记录属于同一类别否，所以分枝“学 生=否”节点为叶节点。 31 8.2.2 建立决策树（17） 考虑分枝“学生=是”节点 因为所有记录属于同一类别是所以分枝“学生= 是”节点为叶节点。 考虑分枝“信誉=优”节点 因为所有记录属于同一类别否所以分枝“信誉= 否”节点为叶节点。 考虑分枝“信誉=中”节点 因为所有记录属于同一类别是所以分枝“信誉= 是”节点为叶节点。 建立的决策树如图8.4所示。 32 8.2.2 建立决策树（18） 图8.4 例8.3的决策树 33 8.2.2 建立决策树（19） 在数据挖掘中应用决策树分类算法递归地 建立决策树时，需要考虑如下问题： 1）从信息增益的计算可以知道，决策树分类算 法要求描述属性是离散属性。如果描述属性是 连续属性，则需要离散化。可以采用基于概念 层次树的离散化技术、基于熵的离散化技术等 将连续属性离散化。 34 8.2.2 建立决策树（20） 2）由于决策树是在分析训练数据集的基础上建立 的，决策树倾向于过分适合训练数据集。如果训 练数据集含有噪声，那么可能决策树的某些分枝 反映的是噪声而不是总体，应该剪去这些不可靠 的分枝，以便提高决策树的分类准确率。有两种 剪枝策略： 先剪枝策略：在建立决策树的过程中，通过某度量标 准判断每个内部节点是否需要进一步划分，如果进一步 划分将导致建立不可靠的分枝，则停止划分，从而达到 剪枝。此时，该内部节点变成叶节点并用其中占多数的 记录类别标识。 后剪枝策略：首先，建立完整的决策树；然后，通过 某度量标准判断哪些内部节点分枝是不可靠的，将这些 内部节点变成叶节点并用其中占多数的记录类别标识， 从而达到剪枝。 35 8.2.3 提取分类规则 建立了决策树之后，可以对从根节点到叶节点的 每条路径创建一条IF-THEN分类规则，即沿着路径 ，每个内部属性-值对（内部节点-分枝对）形成规 则前件（IF部分）的一个合取项，叶节点形成规则 后件（THEN部分）。 例8.4 沿着从根节点到叶节点的每条路径，图8.4 的决策树可以转换成以下IF-THEN分类规则： IF 年龄=30 AND 学生=否 THEN 购买计算机=否 IF 年龄=30 AND 学生=是 THEN 购买计算机=是 IF 年龄=3140 THEN 购买计算机=是 IF 年龄=41 AND 信誉=优 THEN 购买计算机=否 IF 年龄=41 AND 信誉=中 THEN 购买计算机=是 36 8.2.4 对新样本分类 假如现在来了一位新顾客，他是一名教师 ，年龄为45岁，收入较低但信誉很好。商 场需要判断该顾客是否会购买计算机？即 将该顾客划分到“购买计算机”类呢？还是 将他划分到“不购买计算机”类？很显然， 利用上面的分类规则，可以判定该顾客不 会购买计算机。 37 8.3 前馈神经网络分类 8.3.1 前馈神经网络（1） 前馈神经网络是分层网络模型，具有一个输 入层和一个输出层，输入层和输出层之间有 一个或多个隐藏层。每个层具有若干单元， 前一层单元与后一层单元之间通过有向加权 边相连。 图8.5 两层前馈神经网络结构 38 8.3.1 前馈神经网络（2） 输入层单元的数目与训练样本的描述属性 数目对应，通常一个连续属性对应一个输 入层单元，一个p值离散属性对应p个输入 层单元； 输出层单元的数目与训练样本的类别数目 对应，当类别数目为2时，输出层可以只有 一个单元； 目前，隐藏层的层数及隐藏层的单元数尚 无理论指导，一般通过实验选取。 39 8.3.1 前馈神经网络（3） 在输入层，各单元的输出可以等于输入，也可以 按一定比例调节，使其值落在1和+1之间。 在隐藏层、输出层，每个单元的输入都是前一层 各单元输出的加权和，输出是输入的某种函数， 称为激活函数。 隐藏层、输出层任意单元j的输入为 式中，wij是单元j与前一层单元i之间的连接权值；Oi是单 元i的输出； 为改变单元j活性的偏置，一般在区间1 ，1上取值。 40 8.3.1 前馈神经网络（4） 单元j的输出为 Oj=f(netj) 如果f采用S型激活函数，即 则 41 8.3.1 前馈神经网络（5） 图8.6 计算隐藏层、输出层任意单元j的输出的过程 42 8.3.1 前馈神经网络（6） 例8.5 定义例8.1的前馈神经网络结构。 因为离散属性“颜色”有三个取值、“形状”有两 个取值，分别采用3位、2位编码，所以输入层 有5个单元。 因为类别属性“蔬菜”有三个取值，采用3位编码 ，所以输出层有3个单元。 如果只用一个具有4个单元的隐藏层并且采用全 连接，则两层前馈神经网络结构如图8.7所示。 43 8.3.1 前馈神经网络（7） 图8.7 例8.5的两层前馈神经网络结构 44 8.3.2 学习前馈神经网络（1） 确定了网络结构（网络层数，各层单元数 ）之后，应该确定各单元的偏置及单元之 间的连接权值。 学习过程就是调整这组权值和偏置，使每 个训练样本在输出层单元上获得期望输出 。 学习目的就是找出一组权值和偏置，这组 权值和偏置能使所有训练样本在输出层单 元上获得期望输出。 45 8.3.2 学习前馈神经网络（2） 误差后向传播的基本思想是： 首先赋予每条有向加权边初始权值、每个隐藏 层与输出层单元初始偏置； 然后迭代地处理每个训练样本； 输入它的描述属性值，计算输出层单元的实际输出； 比较实际输出与期望输出（类别属性值），将它们之 间的误差从输出层经每个隐藏层到输入层“后向传播” ； 根据误差修改每条有向加权边的权值及每个隐藏层与 输出层单元的偏置，使实际输出与期望输出之间的误 差最小。 46 8.3.2 学习前馈神经网络（3） 对于某个训练样本，实际输出与期望输出 的误差Error定义为 式中，c为输出层的单元数目；Tk为输出层 单元k的期望输出；Ok为输出层单元k的实 际输出。 47 8.3.2 学习前馈神经网络（4） 首先考虑输出层单元k与前一层单元j之间的 权值wjk的修改量wjk、单元k的偏置 的修 改量 。 式中，l为避免陷入局部最优解的学习率， 一般在区间0, 1上取值。 48 8.3.2 学习前馈神经网络（5） 求解上式可以得到权值、偏置的修改量为 式中，Oj为单元j的输出；Errk是误差Error 对单元k的输入netk的负偏导数，即 49 8.3.2 学习前馈神经网络（6） 类似地，隐藏层单元j与前一层单元i之间的 权值wij的修改量wij、单元j的偏置j的修 改量j为 式中，l为学习率；Oi为单元i的输出；Oj为 单元j的输出；Errk为与单元j相连的后一层 单元k的误差；wjk为单元j与单元k相连的有 向加权边的权值。 50 8.3.2 学习前馈神经网络（7） 权值、偏置的修改公式为 权值、偏置的更新有两种策略： 1）处理一个训练样本更新一次，称为实例更新 ，一般采用这种策略。 2）累积权值、偏置，当处理所有训练样本后再 一次更新，称为周期更新。 51 8.3.2 学习前馈神经网络（8） 一般，在训练前馈神经网络时，误差后向 传播算法经过若干周期以后，可以使误差 Error小于设定阈值，此时认为网络收敛， 结束迭代过程。此外，也可以定义如下结 束条件： 1）前一周期所有的权值变化都很小，小于某个 设定阈值； 2）前一周期预测的准确率很大，大于某个设定 阈值； 3）周期数大于某个设定阈值。 52 8.3.2 学习前馈神经网络（9） 算法：误差后向传播算法 输入：训练数据集S，前馈神经网络NT，学 习率l 输出：经过训练的前馈神经网络NT 步骤： （1）在区间-1, 1上随机初始化NT中每条 有向加权边的权值、每个隐藏层与输出层 单元的偏置 （2）while 结束条件不满足 （2.1）for S中每个训练样本s 53 8.3.2 学习前馈神经网络（10） （2.1.1）for 隐藏层与输出层中每个单元j /从 第一个隐藏层开始向前传播输入 （2.1.2）for 输出层中每个单元k Errk=Ok(1- Ok)( Tk - Ok) 54 8.3.2 学习前馈神经网络（11） （2.1.3）for 隐藏层中每个单元j /从最后 一个隐藏层开始向后传播误差 （2.1.4）for NT中每条有向加权边的权值wij wij= wij+lErrjOi （2.1.5）for 隐藏层与输出层中每个单元的偏置 j j=j+lErrj 55 8.3.2 学习前馈神经网络（12） 误差后向传播算法要求输入层单元的输入 是连续值，并对连续值进行规格化以便提 高训练的效率与质量。如果训练样本的描 述属性是离散属性，则需要对其编码，编 码方法有两种： 1）p值离散属性：可以采用p位编码。假设p值 离散属性的可能取值为a1, a2,ap，当某训练 样本的该属性值为a1时，则编码为1,0,0；当 某训练样本的该属性值为a2时，则编码为 0,1,0；依次类推。 2）二值离散属性：除采用2位编码外还可以采 用1位编码。当编码为1时表示一个属性值；当 编码为0时表示另一个属性值。 56 8.3.2 学习前馈神经网络（13） 例8.6 假设训练样本s的描述属性值与类别 属性值分别为1, 0, 1与1，前馈神经网络 NT如图8.8所示，NT中每条有向加权边的权 值、每个隐藏层与输出层单元的偏置如表 8.3所示，学习率为0.9。写出输入s训练NT 的过程。 57 8.3.2 学习前馈神经网络（13） 图8.8 前馈神经网络NT 58 8.3.2 学习前馈神经网络（14） 表8.3 NT中边的权值 、单元的偏置 x1 x2 x3 w14 w15 w24 w25 w34 w35 w46 w56 4 5 6 1010.2 0.3 0.4 0.1 0.5 0.2 0.3 0.2 0.4 0.2 0.1 59 8.3.2 学习前馈神经网络（15） 表8.4 隐藏层与输出层中单元的输入、输出 单元j 输入netj 输出Oj 40.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+e01)=0.525 6(0.3) *0.332+(0.2)*0.525+0.1=0.105 1/(1+e(0.105)=0.474 60 8.3.2 学习前馈神经网络（16） 表8.5 隐藏层与输出层中单元的Err 单元j Errj 60.474*(10.474)*(10.474)=0.1311 50.525*(10.525)*(0.1311*(0.2)=0.0065 40.332*(10.332)*(0.1311*(0.3)=0.0087 61 8.3.2 学习前馈神经网络（17） 表8.6 NT中边的新权重、单元的新偏置 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.9*(0.0087)*1=0.192 w15 0.3+0.9*(0.0065)*1=0.306 w24 0.4+0.9*(0.0087)*0=0.4 w25 0.1+0.9*(0.0065)*0=0.1 w34 0.5+0.9*(0.0087)*1=0.508 w35 0.2+0.9*(0.0065)*1=0.194 6 0.1+0.9*0.1311=0.218 5 0.2+0.9*(0.0065)=0.194 4 0.4+0.9*(0.0087)=0.408 62 8.3.3 神经网络分类 学习结束后，神经网络得到一组固定的权值及偏 置。新样本到来后，将其描述属性值送入输入层 各单元，从输入层到输出层正向传播，计算输出 层各单元的值O1, O2, , On，令r=max(O1, O2, , On)，则第r个输出层单元所代表的类别就是该 样本所属的类别。 例如，在例8.6中，只有一个输出层单元，表示只 有两个类别（A类、B类）。神经网络学习结束后 ，表8.6中的各权值和偏置都固定。将一个新样本 X=（x1, x2, x3）送入输入层后可以计算出O6，若 O61，则表示X应属于A类；若O60，则表示X应 属于B类；若O60.5，则拒绝分类。 63 8.4 贝叶斯分类 8.4.1 贝叶斯分类概述（1） 1. 贝叶斯公式 式中，p(x)、p(y)为随机变量X=x、Y=y的概 率；p(x|y)为已知Y=y时，X=x的条件概率； p(y|x)为已知X=x时，Y=y的条件概率。 64 8.4.1 贝叶斯分类概述（2） 根据贝叶斯公式，可以得到贝叶斯分类公 式： 式中，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的后验概率。 65 8.4.1 贝叶斯分类概述（3） 贝叶斯分类的分类阶段就是给定新样本的 描述属性值a1,am，根据上述公式，计算 各个类别的后验概率，后验概率最大的类 别就是新样本的类别属性值，即新样本的 类别为： 综合上述两式，得到新样本的类别为： 贝叶斯分类的学习阶段就是根据训练样本 ，计算各个类别的先验概率、各个类条件 概率。 66 8.4.1 贝叶斯分类概述（4） 例8.7 训练样本如例8.3中的表8.2所示，新 样本为（3140，中，否，优），应用 贝叶斯分类对新样本进行分类。 因为p(是)9/14； p(否)5/14； p(3140，中，否，优)| 是)1/9； p(3140，中，否，优)| 否)0； p(3140，中，否，优)| 是)p(是) 1/99/141/14； p(3140，中，否，优)| 否)p(否) 05/140； 所以新样本的类别是是。 67 8.4.1 贝叶斯分类概述（5） 2. 贝叶斯网 如果随机变量（或不相交的随机变量集合）X、 Y和Z满足P(X,Y|Z)=P(X|Z)P(Y|Z)，则称X和Y在 已知Z时条件独立，记为XY|Z。式中，P(X|Z) 、P(Y|Z)分别为已知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)。 68 8.4.1 贝叶斯分类概述（6） 在贝叶斯网中，如果已知节点X的父节点 (X)，则X和它的所有非后代节点nd(X)- (X)条件独立，即Xnd(X)-(X)|(X)，称 为局部马尔可夫性。 根据局部马尔可夫性，贝叶斯网节点X1, ., Xm的联合概率分布可以分解为条件概 率分布的乘积，即 69 8.4.1 贝叶斯分类概述（7） 例如，在如图8.9所示的贝叶斯网中，X和Y 在已知Z时条件独立，即XY|Z，并且 P(X,Y,Z)=P(Z)P(X|Z)P(Y|Z)。 图8.9 贝叶斯网示例 70 8.4.1 贝叶斯分类概述（8） 贝叶斯网可以用于计算贝叶斯分类中的类 条件概率。然而，通过分析训练数据集， 构造贝叶斯网是一个NP-complete问题。为 了简化计算，一般应用条件独立假设，限 定贝叶斯网结构。不同的条件独立假设形 成了不同的贝叶斯分类。 朴素贝叶斯分类 树增强朴素贝叶斯分类 71 8.4.2 朴素贝叶斯分类（1） 朴素贝叶斯分类（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，如图8.10所示。 72 8.4.2 朴素贝叶斯分类（2） 图8.10 朴素贝叶斯分类的贝叶斯网结构 73 8.4.2 朴素贝叶斯分类（3） 在朴素贝叶斯分类中，类条件概率可以通 过下式估计 综合公式，得到新样本a1,am的类别为： 74 8.4.2 朴素贝叶斯分类（4） 例8.8 训练样本如例8.3中的表8.2所示，新 样本为（3140，中，否，优），应 用朴素贝叶斯分类对新样本进行分类。 图8.11 例8.8的贝叶斯网结构 75 8.4.2 朴素贝叶斯分类（5） 因为p(是)9/14； p(3140|是)4/9； p(中|是)4/9； p(否|是)3/9； p(优|是)3/9； p(是)p(3140|是)p(中|是)p(否|是)p(优|是) 9/144/94/93/93/98/567； p(否)5/14； p(3140|否)0； p(中|否)2/5； p(否|否)4/5； p(优|否)3/5； p(否)p(3140|否)p(中|否)p(否|否)p(优|否) 5/1402/54/53/50； 所以新样本的类别是是。 76 8.4.2 朴素贝叶斯分类（6） 算法：朴素贝叶斯分类参数学习算法 输入：训练数据集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.count 77 8.4.2 朴素贝叶斯分类（7） （2）for 每个类别c （2.1） （2.2）for 每个描述属性Ai （2.2.1）for 每个描述属性值ai （2.3）for 每个a1, , am 78 8.4.2 朴素贝叶斯分类（8） 算法：朴素贝叶斯分类算法 输入：各个类别的先验概率p(c)，各个类条 件概率p(a1, , am|c)，新样本r( ar1, , arm ) 输出：新样本的类别cr 步骤： （1） 79 8.4.3 树增强朴素贝叶斯分类 （1） 树增强朴素贝叶斯分类（Tree Augmented Nave Bayesian Classifier, TAN）在朴素贝 叶斯分类的基础上，允许各个描述属性之 间形成树型结构，从而削弱了各个描述属 性在给定类别属性时条件独立假设，增强 了朴素贝叶斯分类，因此，称为树增强朴 素贝叶斯分类。也就是说，在贝叶斯网中 ，节点C和节点A1, ., Am有有向边相连，C 是A1, ., Am的父节点，此外，A1, ., Am之间 有有向边相连并形成树，根节点的父节点 只有C，其它节点的父节点除了C之外还有 一个节点。 80 8.4.3 树增强朴素贝叶斯分类（2） 例如，一个包括5个描述属性A1, ., A5和1个 类别属性C的树增强朴素贝叶斯分类的贝叶 斯网结构如图8.12所示。 图8.12 树增强朴素贝叶斯分类的贝叶斯网结构 81 8.4.3 树增强朴素贝叶斯分类（3） 在树增强朴素贝叶斯分类中，如果通过分 析训练数据集，得到了各个描述属性之间 的树型结构，就可以估计类条件概率，从 而可以得到新样本的类别。 例如，在如图8.12所示的树增强朴素贝叶斯分 类中，类条件概率可以通过下式估计： 新样本a1, , a5的类别可以通过下式得到： 82 8.4.3 树增强朴素贝叶斯分类（4） 树增强朴素贝叶斯分类树型结构构造方法 的基本思想是： 首先，计算在给定类别属性C时，描述属性A1, ., Am之间的依赖强度，共得到 个依赖强度 ； 然后，根据从强到弱的原则选择m-1个依赖强度 ，添加相应描述属性之间的无向边，并使各个 描述属性之间形成无向树； 最后，选择根节点，为无向边添加方向形成有 向树。 其中，可以利用条件互信息描述在给定类别属 性C时，描述属性A1, ., Am之间的依赖强度。 83 8.4.3 树增强朴素贝叶斯分类（5） 在给定离散随机变量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。 84 8.4.3 树增强朴素贝叶斯分类（6） 类似地，可以定义在给定类别属性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的条件概率。 85 8.4.3 树增强朴素贝叶斯分类（7） 算法：树增强朴素贝叶斯分类结构学习算法 输入：训练数据集S 输出：树增强朴素贝叶斯分类的贝叶斯网结构TAN 步骤： （1）扫描S，通过式（8.22）计算在给定类别属性 C时，描述属性A1, ., Am之间的条件互信息 （2）构造一个无向完全图，以描述属性为节点， 以条件互信息为边的权重 （3）构造上述无向完全图的最大生成树 （4）在上述最大生成树中选择一个节点为根节点 ，为无向边添加方向形成有向树 （5）在上述有向树中添加节点C和C到各个A1, ., Am的有向边，得到TAN 86 8.4.3 树增强朴素贝叶斯分类（8） 例8.9 训练样本如例8.3中的表8.2所示，新 样本为（3140，中，否，优），应用 树增强朴素贝叶斯分类对新样本进行分类 。 因为I(年龄；收入|购买计算机)0.4196 I(年龄；学生 | 购买计算机)0.2228 I(年龄；信誉 | 购买计算机)0.3118 I(收入；学生 | 购买计算机)0.4196 I(收入；信誉 | 购买计算机)0.1689 I(学生；信誉 | 购买计算机)0.0611 所以树增强朴素贝叶斯分类的贝叶斯网结构如 图8.13所示。 87 8.4.3 树增强朴素贝叶斯分类（9） 图8.13 例8.9的贝叶斯网结构 88 8.4.3 树增强朴素贝叶斯分类（10） 因为p(是)9/14； p(3140 | 是)4/9； p(中 | 是，3140)1/4； p(否 | 是，中)2/4； p(优 | 是，3140)2/4； p(是)p(3140 | 是)p(中 | 是，3140)p(否 | 是，中 )p(优 | 是，3140)9/144/91/42/42/41/56； p(否)5/14； p(3140 | 否)0； p(中 | 否，3140)0； p(否 | 否，中)1； p(优 | 否，3140)0； p(否)p(3140 | 否)p(中 | 否，3140)p(否 | 否，中 )p(优 | 否，3140)5/1400100； 所以新样本的类别是是。 89 8.5 回归分析 事物之间的因果关系涉及两个或两个以上的变量 ，只要其中一个变量变动了，另一个变量也会跟 着变动。 表示原因的变量称为自变量，用X表示，它是固定的（试 验时预先确定的），没有随机误差。 表示结果的变量称为依变量，用Y表示。Y随X的变化而变 化，有随机误差。 如果两个变量间的关系属于因果关系，一般用回 归来研究。 一元回归：依变量Y在一个自变量X上的回归称为一元回 归； 多元回归：依变量Y在多个自变量X1, X2, , Xn上的回归 称为多元回归。 90 8.5.1 一元回归分析（1） 1. 建立一元线性回归方程 如果两个变量在散点图上呈线性关系，就可用 一元线性回归方程来描述。其一般形式为 Y=a+bX 式中，X是自变量；Y是依变量；a、b是一元线 性回归方程的系数。 91 8.5.1 一元回归分析（2） a、b的估计值应是使误差平方和Q(a, b)取 最小值的 、 。 式中，n是训练样本数目，(x1, y1), , (xn, yn)是训练样本。 92 8.5.1 一元回归分析（3） 为了使Q(a, b)取最小值，分别取Q关于a、b 的偏导数，并令它们等于零： 93 8.5.1 一元回归分析（4） 求解上述方程组，得到唯一的一组解 、 ： 其中， ， 。 94 8.5.1 一元回归分析（5） 算法：一元线性回归分析算法 输入：训练数据集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 /计算 95 8.5.1 一元回归分析（6） （3） （4） 2. 假设检验：检验两个变量之间的线性关 系假设是否可以接受。 如果变量X与Y之间的线性关系假设符合实 际，则一元线性回归方程的系数b不应为零 。因此，检验假设 H0：b=0， H1：b0。 如果拒绝假设H0：b=0，则认为变量X与Y之 间的线性关系假设符合实际。 96 8.5.1 一元回归分析（7） t检验是一种比较常用的假设检验方法。t检 验采用以下检验统计量 t(n-2) 式中， 为 的标准差。 97 8.5.1 一元回归分析（8） 当H0为真时，b=0， t(n-2)。所以， H0的拒绝域为 t/2(n-2) 式中，为显著性水平。 给定显著性水平，如果|t|t/2(n-2)，则拒 绝假设H0：b=0，认为回归效果显著，变量 X与Y之间的线性关系假设符合实际。 98 8.5.1 一元回归分析（9） 3. 预测：经过假设检验，如果变量X与Y之 间的线性关系假设符合实际，则可用一元 线性回归方程进行预测。对于任意x，将其 代入方程即可预测出与之对应的y。 例8.10 假设年薪数据如表8.7所示，大学毕业以 后的“工作年数Year”属性是描述属性，“年薪 Salary”属性是预测属性，建立回归方程预测具 有10年工作经验的大学毕