决策树分类ppt课件.ppt

《决策树分类ppt课件.ppt》由会员分享，可在线阅读，更多相关《决策树分类ppt课件.ppt（96页珍藏版）》请在三一办公上搜索。

1、t课件,1,决策树分类,王成（副教授）计算机科学与技术学院,主要内容,什么是决策树ID3算法算法改进C4.5算法CART算法,Decision Tree Modeling决策树是一种简单且应用广泛的预测方法,决策树,图3.1 常见的决策树形式,决策树主要有二元分支（binary split）树和多分支（multiway split）树。一般时候采用二元分裂，因为二元分裂在穷举搜索中更加灵活。,决策树形式,决策树,决策树（Decision Tree）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点（internal node）代表对某个属性的一次测试，每条边代表一个测试结果，叶结点（l

2、eaf）代表某个类（class）或者类的分布（class distribution），最上面的结点是根结点决策树提供了一种展示在什么条件下会得到什么类别这类规则的方法。下例是为了解决这个问题而建立的一棵决策树，从中可以看到决策树的基本组成部分：决策结点、分支和叶结点,决策树,下图给出了一个商业上使用的决策树的例子。它表示了一个关心电子产品的用户是否会购买PC（buys_computer）的知识，用它可以预测某条记录（某个人）的购买意向,决策树,这棵决策树对销售记录进行分类，指出一个电子产品消费者是否会购买一台计算机“buys_computer”。每个内部结点(方形框)代表对某个属性的一次检测。

3、每个叶结点(椭圆框)代表一个类:buys_computers=yes 或者 buys_computers=no在这个例子中，特征向量为： (age, student, credit_rating, buys_computers)被决策数据的格式为: (age, student, credit_rating)输入新的被决策的记录，可以预测该记录隶属于哪个类。,使用决策树进行分类,第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程第2步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结

4、点，从而找到该记录所在的类,主要内容,什么是决策树ID3算法算法改进C4.5算法CART算法,如何从训练数据中学习决策树?,贷款申请数据集,如何从训练数据中学习决策树?,两种可能的根节点选取方式,哪种更好？,ID3算法,ID3算法主要针对属性选择问题使用信息增益度选择测试属性,ID3决策树建立算法,1 决定分类属性集合；2 对目前的数据表，建立一个节点N3 如果数据库中的数据都属于同一个类，N就是树叶，在树叶上 标出所属的类(纯的类别)4 如果数据表中没有其他属性可以考虑，则N也是树叶，按照少 数服从多数的原则在树叶上标出所属类别(不纯的类别)5 否则，根据平均信息期望值E或GAIN值选出一个

5、最佳属性作 为节点N的测试属性6 节点属性选定后，对于该属性中的每个值： 从N生成一个分支，并将数据表中与该分支有关的数据收集形 成分支节点的数据表，在表中删除节点属性那一栏 7如果分支数据表属性非空，则转1，运用以上算法从该节点建立子树,信息熵 (Entropy),我们常说信息很多，或信息很少，但却很难说清楚信息到底有多少比如一本50多万字的史记有多少信息量？或一套莎士比亚全集有多少信息量？这个问题几千年来都没有人给出很好的解答，直到1948年，香农(Claude Shannon)在他著名的论文“通信的数学原理”中提出了信息熵的概念，才解决了信息的度量问题，并且量化出信息的作用,信息熵 (E

6、ntropy),一条信息的信息量和它的不确定性有着直接的关系比如，要搞清楚一件非常不确定的事，或是我们一无所知的事情，就需要了解大量信息。相反，如果我们对某件事已经有了较多了解，那么不需要太多信息就能把它搞清楚从这个角度看，信息量就等于不确定性的多少如何量化信息的度量呢？,信息熵 (Entropy),假如我错过了一个有32支球队参加的足球赛，赛后我问一个知道比赛结果的观众“哪支球队是冠军”？他不愿意直接告诉我，而让我猜，每猜一次，他要收一元钱才肯告诉我是否猜对，那我需要付多少钱才能知道谁是冠军呢？,我可以把球队编号，从1到32，然后问“冠军球队在1-16号中吗？”，假如他告诉我猜对了，我就接着

7、问“冠军在1-8号中吗？”，假如他说猜错了，那我就知道冠军在9-16号中。这样只要5次，我就能知道哪支球队是冠军,当然，香农不是用钱，而是用比特(bit)来度量信息量，在上例中，这条消息的信息量是5比特,信息量的比特数和所有可能情况的对数有关，例如本例中，信息量 = log (球队数)，即 5 = log (32),信息熵 (Entropy),实际上可能不需要5次就能猜出谁是冠军，因为一些强队得冠的可能性更高，因此第一次猜测时可以把少数几支强队分成一组，其它球队分成另一组，然后猜冠军球队是否在那几支强队中这样，也许三次或四次就能猜出结果。因此，当每支球队夺冠的可能性(概率)不等时，这条信息的信

8、息量比5比特少香农指出，它的准确信息量应该是,1,p2,.,p32分别是这32支球队夺冠概率，香农把它称作信息熵，单位为比特；可以算出，当32支球队夺冠概率相同时，对应的信息熵为5比特。,信息熵 (Entropy),对于任意一个随机变量X(比如夺冠球队)，它的熵定义为,变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大,数据集的信息熵,设数据集D中有m个不同的类C1, C2, C3, ., Cm设 Ci,D是数据集D中Ci类的样本的集合, |D|和 |Ci,D|分别是D和 Ci,D中的样本个数,其中pi是数据集D中任意样本属于类Ci的概率，用 估计,数据集D的信息熵:,例: 计算

9、对下列数据集分类所需的信息熵,|D|=14|C1,D|=5|C2,D|=9,使用熵衡量数据纯度,假设有一个数据集合D，其中只有两个类，一个是正例类，一个是负例类计算D中正例类和负例类在三种不同的组分下熵的变化情况。（1）D中包含有50%的正例和50%的负例。 H(D) = -0.5 * log20.5 - 0.5 * log20.5 = 1（2）D中包含有20%的正例和80%的负例。 H(D) = -0.2 * log20.2 - 0.8 * log20.8 = 0.722（3）D中包含有100%的正例和0%的负例。 H(D) = -1 * log21 - 0 * log20 =0可以看到一个

10、趋势，当数据变得越来越“纯”时，熵的值变得越来越小。当D中正反例所占比例相同时，熵取最大值。当D 中所有数据都只属于一个类时，熵得到最小值。因此熵可以作为数据纯净度或混乱度的衡量指标。这正是决策树学习中需要的。,数据集的信息熵,假设按属性 A 划分 D 中的样本，且属性 A 根据训练数据的观测具有 v 个不同取值 a1, a2, ., aj , ., av 。如果 A 是离散值，可依属性 A 将 D 划分为 v 个子集 D1, D2, ., Dj , ., Dv 其中，Dj为D中的样本子集，它们在A上具有属性值aj 这些划分将对应于从该节点A出来的分支。,按属性A对D划分后，数据集的信息熵:,

11、其中， 充当第 j 个划分的权重。,InfoA(D)越小，表示划分的纯度越高,信息增益,选择具有最高信息增益Gain(A)的属性A作为分裂属性,按照能做“最佳分类”的属性A划分，使完成样本分类需要的信息量最小,确定第一次分裂的属性：按年龄划分,年龄40的有5个, 其中2个为“否”,Info年龄(D),Gain(年龄) = Info(D) - Info年龄(D)= 0.940 - 0.694 = 0.246,确定第一次分裂的属性：按收入划分,收入=高的有4个, 其中2个为“否”收入=中的有6个, 其中2个为“否”收入=低的有4个, 其中1个为“否”,Info收入(D),Gain(收入) = In

12、fo(D) - Info收入(D)= 0.940 - 0.911 = 0.029,确定第一次分裂的属性：按学生划分,是学生的有7个, 其中1个为“否”不是学生的有7个, 其中4个为“否”,Info学生(D),Gain(学生) = Info(D) - Info学生(D)= 0.940 - 0.788 = 0.152,确定第一次分裂的属性：按信用划分,信用好的有6个, 其中3个为“否”信用一般的有8个, 其中2个为“否”,Info信用(D),Gain(信用) = Info(D) - Info信用(D)= 0.940 - 0.892 = 0.048,确定第一次分裂的属性,年龄,30,30-40,40

13、,“年龄”属性具体最高信息增益，成为分裂属性,Info收入(D)= 2/5 * (-2/2 * log2/2 - 0/2 * log0/2) + 2/5 * (-1/2 * log1/2 - 1/2 * log1/2) + 1/5 * (-1/1 * log1/1 - 0/1 * log0/1)= 0.400,Info学生(D)= 3/5 * (-3/3 * log3/3 - 0/3 * log0/3) + 2/5 * (-2/2 * log2/2 - 0/2 * log0/2)= 0,Info信用(D)= 3/5 * (-2/3 * log2/3 - 1/3 * log1/3) + 2/5

14、* (-1/2 * log1/2 - 1/2 * log1/2)= 0.951,“学生”属性具体最高信息增益，成为分裂属性,确定第二次分裂的属性,年龄,30,30-40,40,学生,不买,买,不是学生,是学生,.,买,ID3决策树建立算法,1 决定分类属性；2 对目前的数据表，建立一个节点N3 如果数据库中的数据都属于同一个类，N就是树叶，在树叶上 标出所属的类4 如果数据表中没有其他属性可以考虑，则N也是树叶，按照少 数服从多数的原则在树叶上标出所属类别5 否则，根据平均信息期望值E或GAIN值选出一个最佳属性作 为节点N的测试属性6 节点属性选定后，对于该属性中的每个值： 从N生成一个分支

15、，并将数据表中与该分支有关的数据收集形 成分支节点的数据表，在表中删除节点属性那一栏7如果分支数据表属性非空，则转1，运用以上算法从该节点建立子树,它首先对数据进行处理，利用归纳法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树技术发现数据模式和规则的核心是采用递归分割的贪婪算法。,决策树的基本原理,分类决策树,A decision tree is so called because the predictive model can be represented in a tree-like structure. the targe

16、t is categorical, the model is a called a classification tree.,分类树采用的标准： 分类错误率: Gini 指数: 信息熵:,主要内容,什么是决策树ID3算法算法改进C4.5算法CART算法,C4.5算法对ID3的改进,改进1：用信息增益率代替信息增益来选择属性改进2：能够完成对连续值属性的离散化处理改进3：能处理属性值缺失的情况改进4：在决策树构造完成之后进行剪枝,十大数据挖掘算法,C4.5,k-Means,SVM,Apriori,EM,PageRank,AdaBoost,kNN,Nave Bayes,CART,改进1：信息增益的

17、问题,假设按属性 A 划分 D 中的样本，且属性 A 根据训练数据的观测具有 v 个不同取值 a1, a2, ., aj , ., av 。如果 A 是离散值，可依属性 A 将 D 划分为 v 个子集 D1, D2, ., Dj , ., Dv 其中，Dj为D中的样本子集，它们在A上具有属性值aj 这些划分将对应于从该节点A出来的分支。信息增益度量偏向于对取值较多的属性进行测试，即它倾向于选择v较大的属性A,举个极端的例子：考虑充当唯一标识的属性PID。对PID的分裂将产生大量划分（与样本个数一样多），每个分类只包含一个样本，且每个划分都是纯的。,对属性PID划分得到的信息增益最大，显然，这种

18、划分对分类没有用处。,改进1：信息增益率,C4.5使用分裂信息(split information)将信息增益规范化,该值表示数据集D按属性A分裂的v个划分产生的信息,选择具有最大信息增益率的属性作为分裂属性,改进1：信息增益率,Info(D) = 0.940Info收入(D) = 0.911Gain(收入) = 0.029,高收入的有4个中等收入的有6个低收入的有4个,SplitInfo收入(D),= - 4/14 * log4/14 - 6/14 * log6/14 - 4/14 * log4/14= 1.557,GainRatio(收入) = Gain(收入) / SplitInfo收入

19、(D)= 0.029 / 1.557 = 0.019,改进2：连续值属性与分裂点,对于连续值属性，按属性值大小从小到大排序，取每对相邻值的中点作为可能的分裂点split_point。假设一连续值属性共有N个不同的属性值，则可找到N-1个可能的分裂点。检查每个可能分裂点，取能使得信息增益最大的分裂点，将D分裂成D1: A split_point(一个分裂点，二分法，二叉树),5,6,10,5.5,8,=8,8,C4.5不使用中点，而是直接使用一对值中较小的值作为可能的分裂点，如本例中将使用5, 6作为可能分裂点,多个分裂点？多分法，多叉决策树,改进3：缺失值的处理,在某些情况下，可供使用的数据可

20、能缺少某些属性的值，例如,一种简单的办法是赋予它该属性最常见的值，例如将“晴”或“雨”赋予第6个实例的天气属性,一种更复杂的策略是为A的每个可能值赋予一个概率,改进3：缺失值的处理,建树过程（学习过程）选定训练样本实例有缺失值，如何知道要将其分配到哪个分支？分类过程（测试过程或者工作过程）待分类实例有缺失值，如何测试该实例属于哪个分支？,天气,晴,多云,雨,(天气=缺失，温度=72，湿度=90.),改进3： C4.5中缺失值的处理 - 建树过程（学习过程）,Gain(A) = F ( Info(D) InfoA(D),其中 F 为属性值未缺失的实例所占比例；计算 Info(D) 和 InfoA

21、(D) 时忽略属性值缺失的实例,Info(D) = -8/13log(8/13) - 5/13log(5/13)= 0.961 bits,Info天气(D) = 5/13(-2/5log(2/5) - 3/5log(3/5) + 3/13(-3/3log(3/3) - 0/3log(0/3) + 5/13(-3/5log(3/5) - 2/5log(2/5)= 0.747 bits,Gain(天气)= 13/14 (0.961 - 0.747)= 0.199 bits,改进3： C4.5中缺失值的处理 - 建树过程（学习过程）,计算 SplitInfo 时，将缺失的属性值当作一个正常值进行计算

22、，本例中，当作天气有四个值，分别是晴, 多云, 雨, ?，再计算其 SplitInfo,SplitInfo天气(D)= - 5/14log(5/14) - 3/14log(3/14) - 5/14log(5/14) - 1/14log(1/14)= 1.809 bits,晴,多云,雨,缺失,GainRatio(天气)= Gain(天气) / SplitInfo天气(D)= 0.199 / 1.809,改进3： C4.5中缺失值的处理 - 建树过程（学习过程）,分裂时，将属性值缺失的实例分配给所有分支，但是带一个权重,T1: (天气=晴),T1: (天气=多云),T1: (天气=雨),本例14个

23、实例中共13个实例天气属性值未缺失：其中5个实例的天气属性为“晴”，3个实例的天气属性为“多云”， 5个实例的天气属性为“雨”本例14个实例中共1个实例天气属性值缺失，因此估算出天气属性值缺失的第6个实例：天气是晴的概率是5/13，天气是多云的概率是3/13，天气是雨的概率是5/13,改进3： C4.5中缺失值的处理 - 建树过程（学习过程）,T1: (天气=晴),湿度 75 5/13玩，3不玩,湿度,玩 (2.0),不玩 (3.4/0.4),=75,75,叶节点以 (N/E) 的形式定义，其中 N 为到达该叶节点的实例数，E 为其中属于其它分类的实例数。例如，不玩(3.4/0.4) 表示3.

24、4个实例到达“不玩”节点，其中0.4个实例不属于“不玩”,改进3： C4.5中缺失值的处理 - 分类过程,湿度,玩 (2.0),不玩 (3.4/0.4),=75,75,天气,晴,(天气=晴，温度=90，湿度=缺失 .),对于任一实例，湿度 75 的可能性是 3.4/(2.0 + 3.4)当湿度 75 时， 分类为玩的可能性 = 0.4/3.4=12% 分类为不玩的可能性 = 3/3.4=88%最终分类的概率分布为：玩 = 2.0/5.4100% + 3.4/5.412% = 44%不玩 = 3.4/5.488% = 56%,改进4：学习过程中的过度拟合,上述的决策树算法增长树的每一个分支的深度

25、，直到恰好能对训练样例比较完美地分类。实际应用中，当训练样本中有噪声或训练样例的数量太少以至于不能产生目标函数的有代表性的采样时，该策略可能会遇到困难在以上情况发生时，这个简单的算法产生的树会过度拟合训练样例 (过度拟合: Over fitting)过度拟合产生的原因：训练样本中有噪声，训练样例太小等,改进4：欠拟合、合适拟合、过拟合,欠拟合,合适拟合,过拟合,改进4：过度拟合,训练样本中噪声导致的过度拟合错误的类别值/类标签，属性值等训练样本中缺乏代表性样本所导致的过度拟合根据少量训练记录作出的分类决策模型容易受过度拟合的影响。由于训练样本缺乏代表性的样本，在没有多少训练记录的情况下，学习算

26、法仍然继续细化模型就会导致过度拟合,改进4：缺乏代表性样本所导致的过度拟合,哺乳动物分类的训练样例,按照训练模型。人和大象都不是哺乳动物。决策树作出这样的判断是因为只有一个训练样例具有这些特点（鹰，恒温，不冬眠）被划分为非哺乳动物。该例清楚表明，当决策树的叶节点没有足够的代表性时，可能会预测错误。,哺乳动物分类的测试样例,改进4：决策树剪枝,改进4：预剪枝,最直接的方法：事先限定树的最大生长高度,如果设为3，则如图剪枝,改进4：后剪枝,训练过程中允许对数据的过度拟合，然后再利用测试集对树进行修剪,树叶用被替换的子树最频繁的类标号,改进4：后剪枝,在测试集上定义损失函数C，我们的目标是通过剪枝使

27、得在测试集上C的值下降。例如通过剪枝使在测试集上误差率降低。,1. 自底向上的遍历每一个非叶节点(除了根节点)，将当前的非叶节点从树中减去，其下所有的叶节点合并成一个节点，代替原来被剪掉的节点。2. 计算剪去节点前后的损失函数，如果剪去节点之后损失函数变小了，则说明该节点是可以剪去的，并将其剪去；如果发现损失函数并没有减少，说明该节点不可剪去，则将树还原成未剪去之前的状态。3. 重复上述过程，直到所有的非叶节点(除了根节点)都被尝试了。,从决策树导出产生式规则,大型决策树可读性较低，可通过从决策树导出产生式规则以提高可读性把从根结点到叶子结点的路径中遇到的所有测试条件联合起来，便可建立相对应的

28、规则集,从决策树导出产生式规则,但这样的规则会导致某些不必要的复杂性可用类似的方法对规则集进行剪枝对于某一规则，将它的单个条件暂时去除，在测试集上估计误差率，并与原规则的误差率进行比较，若新规则的结果较好，则删除这个条件,IF 天气=晴 AND 湿度 = 75THEN 玩,IF 天气=晴THEN 玩,主要内容,什么是决策树ID3算法算法改进C4.5算法CART算法,CART算法,分类回归树（CART:Classification and Regression Tree）其特点是在计算过程中充分利用二分支树的结构（Bianry Tree-structured），即根节点包含所有样本，在一定的分裂

29、规则下根节点被分裂为两个子节点，这个过程又在子节点上重复进行，直至不可再分，成为叶节点为止。,回归树（Regression Tree）,因变量-continuous ，叶子为因变量的预测值。,Boston Housing Data,Leaves = Boolean Rules（布尔规则）,Leaf12345678,RM6.56.56.56.5, 6.9)6.96.9, 7.4)7.46.9,NOX.51.51, .63).63, .67).67.67.66.66.66,Predicted MEDV2219272714334616,If RM values & NOX values, then

30、MEDV=value,CART算法,CART: Classification And Regression Trees可用于分类和回归(数值预测)使用GINI指标来选择分裂属性使用二元切分(将生成二叉树)基于代价-复杂度剪枝,Gini指标,电脑销售数据集中，9个样本属于“购买电脑”，5个样本属于“未购买电脑”,Gini指标,Gini指标最小，划分越纯。选择具有最小Gini指标(或最大Gini)的属性作为分裂属性,处理离散值属性,以收入为例，对收入属性的所有可能子集：低，中，高，低，中，低，高，中，高，低，中，高考虑所有可能的二元划分，并计算划分前后的Gini指标，选择能产生最小Gini指标的子

31、集作为分裂子集,收入中，高,.,.,是,否,回归树的生成, 数据：N个观测，p个自变量，1个因变量(连续型) 目标：自动地选择分裂变量及其分裂点假设有一个分裂把自变量空间分成M个区域:在每个区域，我们用一个常数来拟合因变量：,优化目标：误差平方和最小 上最优的拟合解为,从根节点开始，考虑一个分裂变量j和分裂点s，得到2个区域：最优的变量j和分裂点s，要满足对于给定的j和s，最里层的优化问题的解为而对于给定的j,分裂点s很快能找到.这样，遍历所有的自变量，就能找到最佳的一对j和s.,递归分割-greedy algorithm,剪枝,最大的决策树能对训练集的准确率达到100%，最大的分类树的结果会

32、导致过拟合（对信号和噪声都适应）。因此建立的树模型不能很好的推广到总体中的其他样本数据。同样，太小的决策树仅含有很少的分支，会导致欠拟合。一个好的树模型有低的偏倚和低的方差，模型的复杂性往往在偏倚和方差之间做一个折中，因此要对树进行剪枝。这里介绍cost-complexity pruning。,最大树,决策树能长到每个叶子都是纯的。最大的分类可以达到100%的准确，最大的回归树残差为0。,恰当的树,先生成一个大的树 考虑一个子树 子树就是由大树进行删减内部节点而得到. 用|T|表示树T 的叶节点（最终节点）的个数.定义cost complexity criterion:对于每个 ，寻找子树 使

33、得 达到最小.而 则起到了平衡树的大小和数据拟合好坏的作用. 较大会得到较小的树， 较小则会得到较大的树.,对于每个 ，可以证明存在唯一的最小的子树 使得达到最小.To find we use weakest link pruning: we successively collapse the internal node that produces the smallest per-node increase in , and continue until we produce the single-node (root) tree. This gives a sequence of subt

34、rees, and this sequence must contains Estimation of is achieved by cross-validation: we choose the value to minimize the cross-validation sum of squares.,用于回归,要预测的属性是数值属性，非离散值属性不纯度度量：计算所有数据的均值，再计算每条数据的值到均值的差值的平方和叶子结点用均值表示,C4.5,k-Means,SVM,Apriori,EM,PageRank,AdaBoost,kNN,Nave Bayes,CART,高伸缩性决策树算法,SL

35、IQ、SPRINT、BOAT,决策树基本概念,决策树的优点1、推理过程容易理解，决策推理过程可以表示成If Then形式；2、推理过程完全依赖于属性变量的取值特点；3、可自动忽略目标变量没有贡献的属性变量，也为判断属性 变量的重要性，减少变量的数目提供参考。,决策树基本概念,关于归纳学习(1),决策树技术发现数据模式和规则的核心是归纳算法。 归纳是从特殊到一般的过程。归纳推理从若干个事实中表征出的特征、特性和属性中，通过比较、总结、概括而得出一个规律性的结论。 归纳推理试图从对象的一部分或整体的特定的观察中获得一个完备且正确的描述。即从特殊事实到普遍性规律的结论。归纳对于认识的发展和完善具有重

36、要的意义。人类知识的增长主要来源于归纳学习。,决策树基本概念,关于归纳学习(2),归纳学习的过程就是寻找一般化描述的过程。这种一般性描述能够解释给定的输入数据，并可以用来预测新的数据。 锐角三角形内角和等于180度； 钝角三角形内角和等于180度； 三角形内角和 直角三角形内角和等于180度； 等于180度,已知三角形ABC，A角等于76度，B角等于89度，则其C角等于15度,归纳学习由于依赖于检验数据，因此又称为检验学习。归纳学习存在一个基本的假设： 任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函数。该假定是归纳学习的有效性的前提条件。,决策树

37、基本概念,关于归纳学习(3),决策树基本概念,关于归纳学习(4),归纳过程就是在描述空间中进行搜索的过程。归纳可分为自顶向下，自底向上和双向搜索三种方式。 自底向上法一次处理一个输入对象。将描述逐步一般化。直到最终的一般化描述。 自顶向下法对可能的一般性描述集进行搜索，试图找到一些满足一定要求的最优的描述。,决策树基本概念,从机器学习看分类及归纳推理等问题（1）,从特殊的训练样例中归纳出一般函数是机器学习的中心问题；从训练样例中进行学习通常被视为归纳推理。每个例子都是一个对偶（序偶）（x, f(x)），对每个输入的x，都有确定的输出f(x)。 学习过程将产生对目标函数f的不同逼近。F的每一个逼

38、近都叫做一个假设。假设需要以某种形式表示。例如，y=ax+b。通过调整假设的表示，学习过程将产生出假设的不同变形。在表示中通常需要修改参数（如a, b）。,决策树基本概念,从机器学习看分类及归纳推理等问题（2）,从这些不同的变形中选择最佳的假设（或者说权值集合）。一般方法如定义为使训练值与假设值 预测出的值之间的误差平方和E最小为最佳。,学习是在假设空间上的一个搜索。概念学习也可以看作是一个搜索问题的过程。它在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合度。多数情况下，为了高效地搜索，可以利用假设空间中一种自然形成的结构，即一般到特殊的偏序关系。,决策树基本概念,从机器学习看分类及归

39、纳推理等问题（3）,分类模型的性能根据模型正确和错误预测也可以根据的检验记录计数进行评估。这些计数存储在混同矩阵（Confusion Matrix）的表格中，二元分类问题混淆矩阵如下：,实际的类,类1,f11,类0,f01,f10,f00,类1,类0,预测的类,准确率=正确的预测数/预测总数=（f11+f00）/(f11+f01+f10+f00),差错率=错误的预测数/预测总数=（f10+f01）/(f11+f01+f10+f00),归纳学习假设 机器学习的任务是在整个实例集合X上确定与目标概念c相同的假设 。一般H表示所有可能假设。H中每个假设h表示X上定义的布尔函数。由于对c仅有的信息只是

40、它在训练样例上的值，因此归纳学习最多只能保证输出的假设能与训练样例相拟合。若没有更多的信息，只能假定对于未见实例最好的假设就是训练数据最佳拟合的假设。 定义 归纳学习假设：任一假设如果在足够大的训练样例中很好地逼近目标函数，则它也能在未见实例中很好地逼近目标函数。（Function Approximation）。,决策树基本概念,从机器学习看分类及归纳推理等问题（4）,决策树学习是以实例为基础的归纳学习。从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。概念分类学习算法：来源于Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习单个概念。1979年, J.R

41、. Quinlan 给出ID3算法，并在1983年和1986年对ID3 进行了总结和简化，使其成为决策树学习算法的典型。Schlimmer 和Fisher 于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高了效率。1993年，Quinlan 进一步发展了ID3算法，改进成C4.5算法。另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。其基本思想是以信息熵为度量构造一棵熵值下降最快的树

42、，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。,决策树的基本原理,决策树学习采用的是自顶向下的递归方法。决策树的每一层节点依照某一属性值向下分为子节点，待分类的实例在每一节点处与该节点相关的属性值进行比较，根据不同的比较结果向相应的子节点扩展，这一过程在到达决策树的叶节点时结束，此时得到结论。从根节点到叶节点的每一条路经都对应着一条合理的规则，规则间各个部分（各个层的条件）的关系是合取关系。整个决策树就对应着一组析取的规则。决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练例子进行较好的标注，就能够进行学习。如果在应用中发现不符

43、合规则的实例，程序会询问用户该实例的正确分类，从而生成新的分枝和叶子，并添加到树中。,决策树的基本原理,树是由节点和分枝组成的层次数据结构。节点用于存贮信息或知识，分枝用于连接各个节点。树是图的一个特例，图是更一般的数学结构，如贝叶斯网络。决策树是描述分类过程的一种数据结构，从上端的根节点开始，各种分类原则被引用进来，并依这些分类原则将根节点的数据集划分为子集，这一划分过程直到某种约束条件满足而结束。,可以看到，一个决策树的内部结点包含学习的实例，每层分枝代表了实例的一个属性的可能取值，叶节点是最终划分成的类。如果判定是二元的，那么构造的将是一棵二叉树，在树中每回答一个问题就降到树的下一层，这

44、类树一般称为CART（Classification And Regression Tree）。判定结构可以机械的转变成产生式规则。可以通过对结构进行广度优先搜索，并在每个节点生成“IFTHEN”规则来实现。如图6-13的决策树可以转换成下规则： IF “个子大” THEN IF “脖子短” THEN IF “鼻子长” THEN 可能是大象形式化表示成,构造一棵决策树要解决四个问题：收集待分类的数据，这些数据的所有属性应该是完全标注的。设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更令人满意。设计分类停止条件，

45、实际应用中数据的属性很多，真正有分类意义的属性往往是有限几个，因此在必要的时候应该停止数据集分裂：该节点包含的数据太少不足以分裂，继续分裂数据集对树生成的目标(例如ID3中的熵下降准则)没有贡献，树的深度过大不宜再分。通用的决策树分裂目标是整棵树的熵总量最小，每一步分裂时，选择使熵减小最大的准则，这种方案使最具有分类潜力的准则最先被提取出来,它首先对数据进行处理，利用归纳法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树技术发现数据模式和规则的核心是采用递归分割的贪婪算法。,决策树的基本原理,决策树应用,决策树有很多的优点，可解释性

46、、计算快捷、缺失值的处理、对于多值名义变量不需要建立哑变量、对输入变量异常值稳健。一些树模型作为最后模型并不合适。它经常作为很多熟悉模型（如回归模型）的辅助工具。标准的回归模型具有线性和可加性。他们需要更多的数据准备阶段：如缺失值的处理、哑变量编码。他们统计计算的有效性严重的被许多不相关和冗余的输入变量影响。,对数据的要求,进行分析时，决策树对变量的量纲的差异、离群值的存在以及有偏分布不太敏感，也就是说对数据准备要求不高。当每一类的训练样本数较小时，决策树是容易出错的，有好多分支的树或者每个节点有太多枝的树最有可能这样，决策树对输出结果的密度很敏感；有的研究表明， regression模型样本

47、量选择中，最好各组样本含量大于解释变量数的20倍。,决策树方法之所以经常被选用是因为它能理顺一些可以理解的规则。然而这些能力有时有些夸大，确实对于某一个已经分过类的记录来说，为了产生这种分类，很简单只要沿着从根到叶的路径走就可以了，然而一个较复杂的决策树可能包含成千上万的叶，这么一棵树从整体上很难提供有关问题可以理解的信息。而回归模型的回归系数具有可解释性，在流行病学研究中，对致病因素的效应，常用一些危险度指标来衡量因素与发病（或死亡）的联系程度或对人群发病的致病作用的大小均可通过拟合该模型得出。,决策树所建立的算法把最胜任的拆分字段变量放在树的根节点（并且同一个字段在树的其他层也可以出现）。在用于预测时，重要的变量会漂浮到树的顶端，这种方式产生的一个有用的结果是使得我们很容易就能发现哪些解释变量最胜任预测工作。也可为regression模型变量的筛选和决策提供指导。,谢谢！,