第八章：分类与预测-《数据挖掘与知识发现》-教学课件.ppt

1、第八章：分类与预测n8.1 简介n8.2 决策树n8.3 贝叶斯分类n8.4 基于遗传算法分类n8.5 分类法的评估n8.6 预测n本章小结2003-11-11第八章：分类与预测n8.1 简介n8.2 决策树n8.3 贝叶斯分类n8.4 基于遗传算法分类n8.5 分类法的评估n8.6 预测n本章小结2003-11-12分类n分类的目的是提出一个分类函数或分类模型（即分类器），通过分类器将数据对象映射到某一个给定的类别中。n数据分类可以分为两步进行。n第一步建立模型，用于描述给定的数据集合。通过分析由属性描述的数据集合来建立反映数据集合特性的模型。这一步也称作有监督的学习，导出模型是基于训练数据

2、集的，训练数据集是已知类标记的数据对象。n第二步使用模型对数据对象进行分类。首先应该评估模型的分类准确度，如果模型准确度可以接受，就可以用它来对未知类标记的对象进行分类。2003-11-13决策树学习简介n决策树（Decision Tree）学习是以样本为基础的归纳学习方法。n决策树的表现形式是类似于流程图的树结构，在决策树的内部节点进行属性值测试，并根据属性值判断由该节点引出的分支，在决策树的叶节点得到结论。内部节点是属性或属性的集合，叶节点代表样本所属的类或类分布。n经由训练样本集产生一棵决策树后，为了对未知样本集分类，需要在决策树上测试未知样本的属性值。测试路径由根节点到某个叶节点，叶节

3、点代表的类就是该样本所属的类。2003-11-16决策树实例n关于PlayTennis的决策树如图所示：High Overcast Normal Strong Weak Sunny Rain Outlook Wind Humidity No Yes Yes No Yes 2003-11-17决策树学习的算法 n决策树学习的基本算法是贪心算法，采用自顶向下的递归方式构造决策树。nHunt等人于1966年提出的概念学习系统CLS是最早的决策树算法，以后的许多决策树算法都是对CLS算法的改进或由CLS衍生而来。nQuinlan于1979年提出了著名的ID3方法。以ID3为蓝本的C4.5是一个能处理连

4、续属性的算法。n其他决策树方法还有ID3的增量版本ID4和ID5等。n强调在数据挖掘中有伸缩性的决策树算法有SLIQ、SPRINT、RainForest算法等。2003-11-18ID3算法 n算法 Decision_Tree（samples,attribute_list）n输入 由离散值属性描述的训练样本集samples；候选属性集合atrribute_list。n输出 一棵决策树。n方法 n(1)创建节点N；n(2)if samples 都在同一类C中 then n(3)返回N作为叶节点，以类C标记；n(4)if attribute_list为空 then 2003-11-19ID3算法（

5、续）n(5)返回N作为叶节点，以samples中最普遍的类标记；/多数表决 n(6)选择attribute_list中具有最高信息增益的属性test_attribute；n(7)以test_attribute标记节点N；n(8)for each test_attribute的已知值v /划分samples n(9)由节点N分出一个对应test_attribute=v的分支；n(10)令Sv为samples中test_attribute=v的样本集合；/一个划分块 n(11)if Sv为空 then n(12)加上一个叶节点，以samples中最普遍的类标记；n(13)else 加入一个由Dec

6、ision_Tree(Sv,attribute_listtest_attribute)返回的节点。2003-11-110信息熵nID3算法采用基于信息熵定义的信息增益度量来选择内节点的测试属性。熵（Entropy）刻画了任意样本集的纯度。n设S是n个数据样本的集合，将样本集划分为c个不同的类Ci(i=1,2,c)，每个类Ci含有的样本数目为ni，则S划分为c个类的信息熵或期望信息为：其中，pi为S中的样本属于第i类Ci的概率，即pini/n。ciiippSE12log2003-11-111n熵值反映了对样本集合S分类的不确定性，也是对样本分类的期望信息。熵值越小，划分的纯度越高，对样本分类的不

7、确定性越低。n一个属性的信息增益，就是用这个属性对样本分类而导致的熵的期望值下降。因此，ID3算法在每一个节点选择取得最大信息增益的属性。2003-11-112期望熵n假设属性A的所有不同值的集合为Values(A)，Sv是S中属性A的值为v的样本子集，即Sv=sSA(s)=v，在选择属性A后的每一个分支节点上，对该节点的样本集Sv分类的熵为E(Sv)。选择A导致的期望熵定义为每个子集Sv的熵的加权和，权值为属于Sv的样本占原始样本S的比例，即期望熵为：n其中，E(Sv)是将S v中的样本划分到c个类的信息熵。AValuesvvvSESSASE,2003-11-113信息增益n属性A相对样本集

8、合S的信息增益Gain(S,A)定义为：Gain(S,A)=E(S)E(S,A)nGain(S,A)是指因知道属性A的值后导致的熵的期望压缩。Gain(S,A)越大，说明选择测试属性A对分类提供的信息越多。Quinlan的ID3算法就是在每个节点选择信息增益Gain(S,A)最大的属性作为测试属性。2003-11-114过度拟合 n在创建决策树时，由于训练样本数量太少或数据中存在噪声和孤立点，许多分支反映的是训练样本集中的异常现象，建立的决策树会过度拟合训练样本集。过度拟合也称过学习，指推出过多与训练数据集相一致的假设。过度拟合将导致作出的假设泛化能力过差。2003-11-115决策树的剪枝

9、n剪枝用于解决过度拟合的问题。剪枝的原则包括：（1）奥卡姆剃刀原则“如无必要，勿增实体”。即在与观察相容的情况下，应当选择最简单的一个；（2）决策树越小就越容易理解，其存储与传输的代价也就越小；（3）决策树越复杂，节点越多，每个节点包含的训练样本个数越少，则支持每个节点的假设的样本个数就越少，可能导致决策树在测试集上的分类错误率较大。但决策树过小也会导致错误率较大，因此，需要在树的大小与正确率之间寻找均衡点。2003-11-116剪枝技术n常用的剪枝技术有预剪枝（Pre-pruning）和后剪枝（Post-pruning）两种。预剪枝技术限制决策树的过度生长（如CHAID、和ID3家族的ID3

10、、C4.5算法等），后剪枝技术则是待决策树生成后再进行剪枝（如CART算法等）。n预剪枝：最直接的预剪枝方法是事先限定决策树的最大生长高度，使决策树不能过度生长。n后剪枝：后剪枝技术允许决策树过度生长，然后根据一定的规则，剪去决策树中那些不具有一般代表性的叶节点或分支。2003-11-117决策树算法的改进 nBratko的研究小组在用ID3算法构造决策树时发现，按照信息增益最大的原则，ID3算法首先判断的属性（靠近决策树的根节点）有时并不能提供较多的信息。Konenko等人认为信息增益度量偏向取值较多的属性。n几种改进的算法：二叉树决策算法、按增益比率进行估计的方法、按分类信息估值、按划分距

11、离估值的方法。2003-11-118决策树算法的可伸缩性n面对海量数据集上的数据挖掘任务，决策树算法的有效性和可伸缩性是值得关注的问题。n为改善算法的可伸缩性，早期的策略有数据采样、连续属性离散化、对数据分片构建决策树等，这些策略是以降低分类准确性为代价的。nSLIQ和SPRINT算法能够在非常大的训练样本集上进行决策树归纳学习。“雨林”（RainForest）算法框架关注于提高决策树算法的伸缩性，该框架可用于大多数决策树算法（例如SPRINT和SLIQ），使算法获得的结果与将全部数据放置于内存所得到的结果一致。2003-11-119第八章：分类与预测n8.1 简介n8.2 决策树n8.3 贝

12、叶斯分类n8.4 基于遗传算法分类n8.5 分类法的评估n8.6 预测n本章小结2003-11-120简介n贝叶斯学派奠基性的工作，是英国学者贝叶斯的一篇具有哲学性的论文关于几率性问题求解的讨论。1958年英国历史最长的统计杂志Biometrika重新全文刊载了贝叶斯的论文。n贝叶斯理论在人工智能、机器学习、数据挖掘等方面有广泛应用。20世纪80年代，贝叶斯网络被用于专家系统的知识表示，90年代可学习的贝叶斯网络被用于数据挖掘和机器学习。n贝叶斯分类是一种统计学分类方法，可以预测类成员关系的可能性。2003-11-121朴素贝叶斯分类n朴素贝叶斯分类将训练样本I分解成特征向量X和决策类别变量C

13、。假定一个特征向量的各分量相对于决策变量是独立的，也就是说各分量独立地作用于决策变量。这一假定叫作类条件独立。n一般认为，只有在满足类条件独立的情况下，朴素贝叶斯分类才能获得精确最优的分类效果；在属性相关性较小的情况下，能获得近似最优的分类效果。2003-11-122朴素贝叶斯分类的工作过程n1.用n维特征向量X=x1,x2,xn表示每个数据样本，用以描述对该样本的n个属性A1,A2,An的度量。n2.假定数据样本可以分为m个类C1,C2,Cm。给定一个未知类标号的数据样本X，朴素贝叶斯分类将其分类到类Ci，当且仅当 P(Ci|X)P(Cj|X)，1jm，ji P(Ci|X)最大的类Ci称为最

14、大后验假定。由贝叶斯公式可知 XPCPCXPXCPiii2003-11-123朴素贝叶斯分类的工作过程（续）n3.由于P(X)对于所有类都为常数，只需要P(X|Ci)P(Ci)最大即可。如果类的先验概率未知，通常根据贝叶斯假设，可取P(C1)=P(C2)=P(Cm)，从而只需P(X|Ci)最大化。类的先验概率也可以用P(Ci)=si/s计算，其中si是类Ci中的训练样本数，s是训练样本总数。n4.当数据集的属性较多时，计算P(X|Ci)的开销可能非常大。如果假定类条件独立，可以简化联合分布，从而降低计算P(X|Ci)的开销。给定样本的类标号，若属性值相互条件独立，即属性间不存在依赖关系，则有：

15、2003-11-124朴素贝叶斯分类的工作过程（续）其中，概率P(x1|Ci),P(x2|Ci),P(xn|Ci)可以由训练样本进行估值。如果Ak 是离散值属性，则P(xk|Ci)=sik/si。其中，sik是类Ci中属性Ak的值为xk的训练样本数，而si是Ci中的训练样本数。如果Ak是连续值属性，通常假定该属性服从高斯分布（正态分布）。从而有 nkikiCxPCXP12221exp21,iiiiiCkCCCCkikxxgCxP2003-11-125朴素贝叶斯分类的工作过程（续）其中，给定类Ci的训练样本属性Ak的值，是属性Ak的高斯密度函数，分别为均值和标准差。n5.对每个类Ci，计算P(X

16、|Ci)P(Ci)。把样本X指派到类Ci的充分必要条件是 P(X|Ci)P(Ci)P(X|Cj)P(Cj)，1jm，ji 也就是说，X被分配到使P(X|Ci)P(Ci)最大的类Ci。),g(iiCCkxiCiC2003-11-126贝叶斯网络简介n一般来说，贝叶斯信念网络通过指定一组条件独立性假定（有向无环图），以及一组局部条件概率集合来表示联合概率分布。贝叶斯信念网络也称作贝叶斯网络、信念网络或概率网络。贝叶斯网络允许在变量的子集间定义类条件独立性，并且提供一种因果关系的图形，可以在其上进行学习。2003-11-127贝叶斯网络的定义 n给定一个随机变量集X=X1,X2,Xn，其中Xi是一个

17、m维向量。贝叶斯网络说明X上的一条联合条件概率分布。贝叶斯网络定义如下：B=G,G是一个有向无环图，顶点分别对应于有限集X中的随机变量X1,X2,Xn，每条弧代表一个函数依赖关系。如果有一条由变量Y到X的弧，则Y是X的双亲或称直接前驱，而X则是Y的后继。一旦给定双亲，图中的每个变量就与其非后继节点相独立。在图G中，Xi的所有双亲变量用集合Pa(Xi)表示。2003-11-128贝叶斯网络的定义（续）n 代表用于量化网络的一组参数。对于每一个Xi的取值xi，参数 ，表明在给定Pa(Xi)发生的情况下，事件xi 发生的条件概率。实际上，贝叶斯网络给定了变量集合X上的联合条件概率分布：|()(|()

18、iix Pa xiiP xPa XniiiBnBXPaXPXXXP121)(|(),.,(2003-11-129贝叶斯网络的构造 n(1)确定为建立模型所需的有关变量及其解释。包括：n 确定模型的目标，即确定问题相关的解释。n 确定与问题有关的可能观测值，并确定值得建立模型的子集。n 将这些观测值组织成互不相容的而且穷尽所有状态的变量。n(2)建立一个表示条件独立断言的有向无环图。n(3)指派局部概率分布。在离散的情况下，需要为每一个变量Xi的各个父节点的状态指派一个分布。2003-11-130贝叶斯网络的学习 n依据数据是否完备及网络结构是否已知，贝叶斯网络的学习可分为4种：网络结构已知且数

19、据完备、网络结构已知且数据不完备、网络结构未知且数据完备、网络结构未知且数据不完备。2003-11-131贝叶斯网络的学习（续）n在已知网络结构，并且变量可以从训练样本中完全获得时，通过学习比较容易得到条件概率表，可以采用的方法有最大似然估计方法、贝叶斯方法等。n如果只有一部分变量值能在数据中观察到，学习贝叶斯网络就要困难得多，类似于在人工神经网络中学习隐藏单元的权值，其中输入和输出节点值由训练样本给出，但隐藏单元的值未指定。可以采用的方法有蒙特卡洛方法、高斯近似方法、基于梯度的方法和EM算法等。2003-11-132基于梯度的方法nRussell等人于1995年提出一个简单的基于梯度的方法以

20、学习条件概率表中的项。这一基于梯度的方法搜索一个假设空间，它对应于条件概率表中所有可能的项。在梯度上升中最大化的目标函数是Ph(D)，即在给定假设h下观察到训练数据D的概率。n梯度上升规则使用相应于定义条件概率表参数lnPh(D)的梯度来使Ph(D)最大化。令wijk为在给定双亲节点Ui 取值uik时，网络变量Yi值为yij的概率，即wijk代表某个条件概率表中的一个CPT项。2003-11-133基于梯度的方法（续）n给定网络结构和wijk的初值，算法步骤如下：n(1)对于每个wi jk，lnPh(D)的梯度由下式计算的导数给出：n(2)沿梯度上升方向更新每个wi jk：n其中，是一小的常量

21、，称为学习率。DXijkdikiijiijkhdwXuUyYPwDP,ln ijkhijkijkwDPwwln2003-11-134基于梯度的方法（续）n(3)将权值wi jk归一化，以满足当权值wi jk更新时，其取值属于区间0,1，使其成为有效的概率，并且对所有的i，k，都有j wi jk 等于1。n梯度方法的优点是灵活，适应性强，并可借鉴人工神经网络的学习方法。但梯度方法需要在合理的参数空间中搜索，而且存在局部极值问题。2003-11-135贝叶斯网络的优势：n可以综合先验信息和后验信息；n适合处理不完整和带有噪声的数据集；n与“黑匣子”知识表示方式（如人工神经网络）相比，贝叶斯网络可以

22、解释为因果关系，其结果易于理解，并利于进行深入研究。2003-11-136第八章：分类与预测n8.1 简介n8.2 决策树n8.3 贝叶斯分类n8.4 基于遗传算法分类n8.5 分类法的评估n8.6 预测n本章小结2003-11-137遗传算法的发展n最早意识到自然遗传算法可以转化为人工智能算法的是J.H.Holland教授。n1967年，Holland教授的学生J.D.Bagley在其博士论文中首次提出了“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文，从而创立了自适应遗传算法的概念。nJ.D.Bagley发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法

23、。n1970年，Cavicchio把遗传算法应用于模式识别。nHollstien最早把遗传算法应用于函数优化。2003-11-138遗传算法的发展n70年代初，Holland教授提出了遗传算法的基本定理模式定理，从而奠定了遗传算法的理论基础。n1975年，Holland教授出版了第一本系统论述遗传算法和人工自适应系统的专著自然系统和人工系统的自适应性。同年，K.A.De Jong在博士论文遗传自适应系统的行为分析中结合模式定理进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，为遗传算法及其应用打下了坚实的基础，他所得出的许多结论迄今仍具有普遍的指导意义。2003-11-139遗传算

24、法的发展n80年代，Holland教授实现了第一个基于遗传算法的机器学习系统分类器系统（Classifier Systems，简称CS），开创了基于遗传算法的机器学习的新概念，为分类器系统构造出了一个完整的框架。n1989年，D.J.Goldberg出版了专著搜索、优化和机器学习中的遗传算法。n1991年，L.Davis编辑出版了遗传算法手册一书，书中包括了遗传算法在科学计算、工程技术和社会经济中的大量应用样本，为推广和普及遗传算法的应用起到了重要的指导作用。2003-11-140遗传算法的发展n1992年，J.R.Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传规划（Gen

25、etic Programming，简称GP）的概念。2003-11-141遗传算法简介n遗传算法（Genetic Algorithm，简称GA）是模拟生物进化过程的计算模型，是自然遗传学与计算机科学相互结合、相互渗透而形成的新的计算方法。n在遗传算法中染色体对应的是一系列符号序列，在标准的遗传算法（即基本遗传算法）中，通常用0，1组成的位串表示，串上各个位置对应基因座，各位置上的取值对应等位基因。遗传算法对染色体进行处理，染色体称为基因个体。一定数量的基因个体组成基因种群。种群中个体的数目为种群的规模，各个体对环境的适应程度称适合度（Fitness）。2003-11-142遗传算法简介n遗传算

26、法为模拟生物的遗传进化，必须完成两种数据转换：一是从表现型到基因型的转换，即将搜索空间中的参数或可行解转化成遗传空间中的染色体或个体，完成编码操作；另一种是从基因型到表现型的转换，是前者的反方向操作，为译码操作，即将遗传空间中的染色体或个体转换成解空间中的最优解。2003-11-143遗传算法简介n遗传算法实质上是一种繁衍、监测和评价的迭代算法。从数学角度看，它是一种概率型搜索算法；从工程学角度看，它是一种自适应的迭代寻优过程。算法以所有个体为对象，通过选择、交叉和变异算子实现种群的换代演化，使新生代的基因种群具有更强的环境适应能力。2003-11-144遗传算法简介n遗传算法的最大优点是问题

27、求解与初始条件无关，搜索最优解的能力极强。遗传算法可以对各种数据挖掘技术进行优化，例如，神经网络、最近邻规则等。解决这些问题的关键是将复杂的现实问题解决方案转换成计算机中的模拟遗传物质（一系列的计算机符号）。2003-11-145基本概念n定义8.2 设GA的个体pBl，记集合S=0,1,*l，则称sS为模式。其中，“*”是通配符。n定义8.3 若个体p的每一位都与模式s相匹配，则称p是s的一个表示。n定义8.4 模式s的阶就是出现在模式中的“0”和“1”的数目。记为o(s)。n定义8.5 一个模式的长度就是模式中第一个确定位置和最后一个确定位置间的距离，记为(s)。2003-11-146模式

28、定理n定理8.1（模式定理）适应值在群体平均适应值之上的、长度较短的低阶模式在CA的迭代过程中将按指数增长率采样。n模式定理表明，遗传算法根据模式的适应值、长度和阶次为模式分配搜索次数。为适应值较高、长度较短、阶次较低的模式按指数增长率分配搜索次数；为适应值较低、长度较长、阶次较高的模式按指数衰减分配搜索次数。2003-11-147基本遗传算法 nGoldberg总结出一种统一的最基本的遗传算法，称为基本遗传算法（Simple Genetic Algorithms,简称SGA）。基本遗传算法是其他遗传算法的雏形和基础，它只使用选择、交叉和变异三种基本遗传算子，其遗传进化操作过程简单，容易理解。

29、SGA给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。2003-11-148基本遗传算法的构成要素 n染色体编码方法 n个体适应度评价 n遗传算子 n选择算子：按照某种策略从父代中挑选个体进入中间群体。n交叉算子：随机地从中间群体中抽取两个个体，按照某种策略互相交换两个个体的部分染色体码串，从而形成两个新的个体。n变异算子：按照一定的概率（一般都比较小），改变染色体中某些基因的值。比如使用基本位变异算子。n基本遗传算法的运行参数 2003-11-149基本遗传算法的求解过程 n编码并生成祖先群体 n计算种群中所有个体的环境适应度 n用适应度函数评价个体对环境的适应度 n选择适应度好

30、的个体进行复制 n选择适应度好的个体进行复制交叉配对繁殖 n新生代的变异操作 编码并生成祖先群体 计算当前群体中所有个体适应度 选择群体中适应度高的个体进行复制 交叉操作 变异复制 终止 是否满足最优解条件 是 2003-11-150编码方法 nDe Jong提出了两条操作性较强的实用编码原则（又称为编码规则）。n编码原则一（有意义积木块编码原则）：应使用与求问题相关的、低阶的、长度短的模式编码方案。n编码原则二（最小字符集编码原则）：应使用能自然表示或描述问题的最小编码字符集的编码方案。n二进制编码、格雷码（Gray Code）编码方法、浮点数编码方法、符号编码方法、多参数级联编码方法、多参

31、数交叉编码方法等。2003-11-151适应度函数 n评价个体适应度的一般过程是：n对个体编码串进行解码处理后，可以得到个体的表现型。n由个体的表现型可以计算出对应个体的目标函数值。n根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。2003-11-152选择算子 n遗传算法中的选择操作建立在对个体的适应度进行评价的基础之上。选择操作用来确定把种群中一些个体遗传到下一代群体。要求避免基因缺失，提高全局收敛性和计算效率。n最常用和最基本的选择算子是比例选择算子。设某一代种群规模为n，某一个体的适应度为fi，那么选取它的概率Pi为：njiiiffp12003-11-153交叉算子

32、 n交叉算子与研究的问题密切相关，既不能太多地破坏个体编码串中具有优良性状的模式，又要能够有效地产生出一些较好的新个体。另外，交叉算子的设计要和个体编码设计统一考虑。n单点交叉算子是最常用和最基本的交叉操作算子，又叫简单交叉，是指在个体编码串中随机地设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。n交叉算子还有二点交叉、多点交叉和均匀交叉等算子。2003-11-154变异算子 n变异算子是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。n最简单的变异算子是基本位变异算子。基本位变异操作是指以变异概率Pm随机指定的个体编码串的某一位或

33、某几位基因座上的基因值作变异运算。基本位变异算子的执行过程是：n对个体的每一个基因座，依变异概率Pm指定其为变异点。n对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。n为适应各种不同应用问题的求解需要，人们提出了一些其他变异算子。其中较常用的几种变异操作方法有均匀变异、非均匀变异、边界变异、高斯变异等。2003-11-155约束条件的处理方法n在实际问题求解中会有一些约束条件。在遗传算法的应用中，还未找到一种能够处理各种约束条件的一般化方法。所以对约束条件进行处理时，只能是针对具体应用问题及约束条件的特征，考虑遗传算子的能力，选用不同的处理方法。n处

34、理约束条件的常用方法主要有搜索空间限定法、可行解变换法和罚函数法三种。2003-11-156第八章：分类与预测n8.1 简介n8.2 决策树n8.3 贝叶斯分类n8.4 基于遗传算法分类n8.5 分类法的评估n8.6 预测n本章小结2003-11-157评估分类法的精度 n常见的方法有保持方法、留一法、自展法、k-折交叉验证等。n保持方法将给定数据随机地划分成两个独立的集合，即训练集和测试集。首先使用训练集导出分类法，然后在测试集上评估精度。随机子选样是保持方法的一种变形，它将保持方法重复k次。取每次迭代精度的平均值作为总体精度估计。2003-11-158评估分类法的精度（续）n留一法（Lea

35、ving-one-out）在每一阶段留出一个数据点，但每个数据点是依次被留出的，所以最终测试集的大小等于整个训练集的大小。每个仅含一个数据点的测试集独立于它所测试的模型。n自展法（Bootstrap）利用样本和从样本中轮番抽出的同样容量的子样本间的关系，对未知的真实分布和样本的关系建模。Jackknife方法也是以每次留出训练集合中的一部分数据为基础，它等价于自展方法的一种近似。2003-11-159评估分类法的精度（续）n在k-折交叉验证（k-fold cross-validation）中，原始数据被划分成k个互不相交的子集或“折”S1，S2，Sk，每个折的大小大致相等。进行k次训练和测试。

36、在第i次迭代时，Si用作测试集，其余的子集都用于训练分类法。分类精度估计是k次迭代正确分类数据除以初始数据中的样本总数。在分层交叉验证（Stratified Cross-validation）中，将每个折分层，使得每个折中样本的类分布与初始数据中的大致相同。2003-11-160提高分类法的精度 n改进分类法精度的技术主要有两种：装袋（Bagging）（或引导聚集）和推进（Boosting）。两种方法都是将学习得到的T个分类法C1，C2，CT进行组合，以求创建一个改进的分类法C*。2003-11-161装袋n假定样本集合S中含有s个样本，装袋过程如下：对于第t次（t1,2,T）迭代，从原始样本

37、集S中采用放回选样选取训练集St。通过学习训练集St，得到分类法Ct。为对一个未知的样本X分类，每个分类法Ct返回它的类预测，算作一票。装袋的分类法C*统计得票，并将得票最高的类赋予X。可以通过计算取得票的平均值，而不是多数，将装袋技术用于连续值的预测。2003-11-162推进n“推进”技术为每个训练样本赋予一个权。通过学习得到一系列分类法。学习得到分类法Ct后，更新权值，使得随后的分类法Ct+1“更关注”Ct的分类错误。最后，推进分类法C*组合每个分类法的表决，这里每个分类法的表决是其精度的函数。“推进”技术也可以扩充到连续值预测。2003-11-163第八章：分类与预测n8.1 简介n8

38、.2 决策树n8.3 贝叶斯分类n8.4 基于遗传算法分类n8.5 分类法的评估n8.6 预测n本章小结2003-11-164预测n预测是构造和使用模型评估无标号样本类，或评估给定样本可能具有的属性值或区间值。n预测的目的是从历史数据中自动推导出对给定数据的推广描述，从而能对未来数据进行预测。在这种观点下，分类和回归是两类主要预测问题。其中分类是预测离散或标称值，而回归用于预测连续或有序值。n一般认为：用预测法预测类标号为分类，用预测法预测连续值为预测。连续值的预测一般用回归统计技术建模。2003-11-165时间序列预测模型 n时间序列是指按时间先后顺序将某个变量的取值排列起来形成的序列。时

39、间序列模型主要用来对未来进行预测，属于趋势预测法。n简单一次移动平均预测法 n加权一次移动平均预测法 n指数平滑预测法 2003-11-166简单一次移动平均预测法 n设yt为时间序列，取移动平均的项数为n，设yt是第t期的实际值，则第(t+1)期预测值的计算公式为：njjntntttttynnyyyMy111)1(112003-11-167加权一次移动平均预测法 n计算公式如下：niiniitinntntttWyWWWWyWyWyWy11121112112003-11-168指数平滑预测法 n一次指数平滑预测法n二次指数平滑预测法)1(1)1(1)1(ttttSaySyTbaySSSSayS

40、ttTttttttt)1()1()2(1)2()2()1(1)1(2003-11-169一元线性回归模型 n一元线性回归模型可描述为：y=b0+b1x+u 其中，b0和b1是未知参数，u是剩余残差项或称随机扰动项，它反映了所有其他因素对因变量y的影响。n建立一元线性回归模型的步骤如下：建立理论模型、估计参数、进行检验、进行预测。2003-11-170多元线性回归模型 n当影响因变量y的自变量不止一个时，比如有m个x1，xm，这时y和x之间的线性回归模型为 y=+1x1+mxm+此时响应变量y可以看作是一个多维特征向量的线性函数。可以用最小二乘法求解，1，m。2003-11-171非线性回归 n

41、非线性回归对不呈现线性依赖的数据建模，可以通过对变量进行变换，将非线性模型转换成线性的，然后用最小二乘法求解。2003-11-172其他回归模型 n线性回归用于对连续值函数进行建模。广义线性模型提供了将线性回归用于分类响应变量建模的理论基础。与线性回归不同，在广义线性模型中，响应变量y的方差是y的平均值的函数，而在线性回归中，y的方差为常数。广义线性模型的常见形式包括对数回归和泊松回归。对数回归将某些事件发生的概率看作预测变量集的线性函数。对数数据常常呈泊松分布，并通常使用泊松回归建模。对数线性模型近似离散的多维概率分布，可以使用它们估计与数据立方体单元相关的概率值。2003-11-173马尔

42、可夫链模型简介n马尔可夫链模型是以俄国数学家Markov的名字命名的一种动态随机数学模型，它通过分析随机变量现时的运动情况来预测这些变量未来的运动情况。n设考察对象为一系统，若该系统在某一时刻可能出现的事件集合为E1,E2,EN，E1,E2,EN两两互斥，则称Ei为状态，i=1,2,N。称该系统从一种状态Ei变化为另一种状态Ej的过程为状态转移，并把整个系统不断实现状态转移的过程称为马尔可夫过程。2003-11-174基本概念n定义8.1 具有下列两个性质的马尔可夫过程称为马尔可夫链：（1）无后效性，即系统的第n次实验结果出现的状态，只与第(n1)次时系统所处的状态有关，而与它以前的状态无关；

43、（2）具有稳定性，该过程逐渐趋于稳定状态，与初始状态无关。n定义8.2 向量u=(u1,u2,un)称为概率向量，如果u满足：1,2 ,1 01njjjunju2003-11-175基本概念n定义8.3 如果方阵P的每行都为概率向量，则称此方阵为概率矩阵。n定义8.4 系统由状态Ei经过一次转移到状态Ej的概率记为Pij，称矩阵 为一次（或一步）转移矩阵。NNNNNNPPPPPPPPP2122221112112003-11-176基本概念n定义8.5 对概率矩阵P，若幂次方Pm的所有元素皆为正数，则矩阵P称为正规概率矩阵（此处M2）。n定理8.1 正规概率矩阵P的幂次方序列P,P2,P3,趋近

44、于某一方阵T，T的每一行均为同一概率向量t，且满足tP=t。（证明略）2003-11-177马尔可夫链模型n设系统在k=0时的初始状态 为已知，经过k次转移后的状态向量 ，则 此式即为马尔可夫预测模型。显然，系统在经过k次转移后的状态只取决于初始状态和转移矩阵。),(0)0(2)0(1)0(NSSSS),2,1)(,()()(2)(1)(kSSSSkNkkkkNNNNNNkPPPPPPPPPSS212222111211)0()(2003-11-178第八章：分类与预测n8.1 简介n8.2 决策树n8.3 贝叶斯分类n8.4 基于遗传算法分类n8.5 分类法的评估n8.6 预测n本章小结2003-11-179本章小结n分类和预测用于提取描述重要数据类别的模型，预测未来的数据趋势，是两种重要的数据分析方法。n分类通过一个分类函数或分类模型将数据对象映射到给定的类别中，一般分为两步。第一步，通过分析由属性描述的数据集合来建立反映数据集合特性的模型，用于描述给定的数据集合；第二步，使用模型对数据对象进行分类。n预测的目的是从历史数据记录中自动推导出对给定数据的推广描述，从而能够对未知的数据进行预测。2003-11-180