人工智能之决策树PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,决策树,1,决策树基本概念,信息论基础,应用实例及,ID3,算法,决策树总结,一些思考,目录,2,生活中的决策树,1(Decision Tree),决策树基本概念,3,A decision tree is a flowchart-like structure in which each internal node represents a test on an attribute(e.g.whether a coin flip comes up heads or tails),each branch represents the outcome of the test,and each leaf node represents a class label(decision taken after computing all attributes).The paths from root to leaf represent classification rules.,决策树是一种类似于流程图的结构，其中每个内部节点代表一个属性上的“测试”（例如，一个硬币的翻转是正面还是反面），每个分支代表测试的结果，每个叶节点代表一个类标签（在计算所有属性之后做出的决定）。从根到叶子的路径表示分类规则。,定义,决策树基本概念,4,生活中的决策树,2(Decision Tree),属性测试,属性测试,决定,决定,分支,构建决策树的关键问题：,1.,以何种属性进行测试,2.,以何种顺序进行测试,3.,何时做出决定,决策树基本概念,5,连接主义者认为，机器学习分为监督学习，无监督学习和强化学习。监督学习就是训练样本带有属性标签。监督学习又可分为“回归”和“分类”问题。,机器学习中的分类技术一般是用一种学习算法确定分类模型，该模型可以很好地拟合类标号和属性集之间的映射关系。,常用的分类算法包括：决策树分类法、逻辑回归分类法、神经网络、支持向量级、朴素贝叶斯分类方法等。,机器学习中的决策树（,1/2,）,决策树基本概念,6,在机器学习中，决策树是一个带有标签的监督式学习预测模型，代表的是对象属性与对象值之间的一种映射关系。算法,ID3,，,C4.5,和,C5.0,是基于信息学理论中熵的理论而设计的。,相比,大多数分类算法，如,kNN,等,，决策树易于理解和实现，使用者无需了解很多背景知识。,它能够对数据集合进行分析，挖掘其中蕴含的知识信息,。,机器学习中的决策树（,2/2,）,决策树基本概念,7,决策树算法采用自上至下递归建树的技术，该算法的产生源于,CLS,系统，即概念学习系统,。,决策树算法发展历史,(1/2),决策树基本概念,8,1980,年,，,戈登,V.,卡斯,创建,CHAID,（卡方自动交叉检验）,1979,年,，,J.R.Quinlan,给出,ID3,算法，,在,1983,年和,1986,年进行总结和简化,1986,年,，,Schlimmer,和,Fisher,于对,ID3,进行改造，使决策树可以递增式生成，得到,ID4,算法。,1988,年，,Utgoff,在,ID4,基础上提出了,ID5,学习算法,1993,年，,Quinlan,进一步发展了,ID3,算法，改进成,C4.5,算法。,另一类决策树算法为,CART,，与,C4.5,不同的是，,CART,的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例,决策树算法发展历史,(2/2),决策树基本概念,9,决策树重要概念,决策树基本概念,10,信息的大小可以度量么？,信息量的大小与概率有关！,概率越小，信息量越大。出现概率为,0,，信息量无穷大,概率越大，信息量越小。出现概率为,1,，信息量为,0.,信息量,2.,信息论基础,11,1948,年,10,月，香农在贝尔系统技术学报上发表论文,A Mathematical Theory of Communication,，首次建立通讯过程的数学模型，成为现代信息论研究的开端。,香农理论的重要特征是熵（,entropy,）的概念，他证明熵与信息内容的不确定程度有等价关系。,信息论,2.,信息论基础,12,消息 发生后所含有的信息量，反映了消息 发生前的不确定性：,信息量,譬如袋子里有红球和黑球，取红球的概率为,0.4,，取黑球的概率为,0.6,。取出红球的信息量为,1.322,，取出黑球的信息量,0.737,。,2.,信息论基础,13,熵,(entropy),这一词最初来源于热力学。,1948,年，克劳德,爱尔伍德,香农将热力学中的熵引入信息论，所以也被称为香农熵,(Shannon entropy),，信息熵,(information entropy),。表示系统的不确定性。,公式：,信息熵,譬如袋子里有红球和黑球，取红球的概率为,0.4,，取黑球的概率为,0.6,。取出红球的信息量为,1.322,，取出黑球的信息量,0.737,。取出,1,个球的加权平均信息量为,1.322,*,0.4+0.737,*,0.6,。,思考：什么情况下，熵最大？,2.,信息论基础,14,条件熵,H(X|Y),表示在已知随机变量,Y,的条件下随机变量,X,的不确定性。,H(X|Y),，其实质是给定,Y,情况下,X,条件概率分布的熵，对,Y,的数学期望：,条件熵,2.,信息论基础,15,条件熵和互信息量,2.,信息论基础,互信息量，又称信息增益,16,Y,代表性别，取值为男和女；,X,代表穿着，取值为裙子和裤子。,信息增益计算实例,男,女,裙子,0.2,0.5,0.7,裤子,0.2,0.1,0.3,0.4,0.6,注意：,H,（,Y/X,代表已知某人穿着，其性别的不确定性,2.,信息论基础,求信息增益：,I(X;Y)=H(Y)-H,（,Y/X,）,17,首先计算条件熵,2.,信息论基础,Step1,：计算信息熵,Step2,：计算给定,X,条件下，,Y,条件概率的熵,Step3,：,Y,条件概率的熵值对,X,求数学期望,18,其次计算信息增益,2.,信息论基础,互信息量，也就是随机变量,X,对随机变量,Y,的信息增益,19,ID3,由,Ross Quinlan,在,1986,年提出。其核心是根据“最大信息熵增益”原则选择划分当前数据集的最好特征，减少数据的熵,(,混乱度,),。,ID3,是一种贪心算法：,1,）从根结点,(root node),开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征。,2,）由该特征的不同取值建立子节点，再对子节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；,3,）最后得到一个决策树。,每次选取的分割数据的特征都是当前的最佳选择，并按照该特征的所有取值来切分，也就是说如果一个特征有,4,种取值，数据将被切分,4,份。,ID3,算法简介,3.,应用实例及,ID3,算法,20,ID3,算法伪代码,21,ID,年龄,有工作,有房子,信贷情况,类别,(,是否,放贷,),1,青年,否,否,一般,否,2,青年,否,否,好,否,3,青年,是,否,好,是,4,青年,是,是,一般,是,5,青年,否,否,一般,否,6,中年,否,否,一般,否,7,中年,否,否,好,否,8,中年,是,是,好,是,9,中年,否,是,非常好,是,10,中年,否,是,非常好,是,11,老年,否,是,非常好,是,12,老年,否,是,好,是,13,老年,是,否,好,是,14,老年,是,否,非常好,是,15,老年,否,否,一般,否,应用实例：是否放贷的决策树,对特征进行标注（预处理）,年龄：,0,代表青年，,1,代表中年，,2,代表老年；,有工作：,0,代表否，,1,代表是；,有自己的房子：,0,代表否，,1,代表是；,信贷情况：,0,代表一般，,1,代表好2,代表非常好；,类别,(,是否给贷款,),：,no,代表否，,yes,代表是。,3.,应用实例及,ID3,算法,22,信息熵计算公式,采用频率替代概率。数据集,D,为是否放贷的类别，,C,k,代表该类别的某一取值的出现频率，如不放贷出现的频次,特征,A,有,n,种取值，,H(Di),代表在,A,属性的第,i,个取值下，,D,的条件概率熵,H(D/Ai),信息增益，即特征,A,对,D,的信息增益,注意：要计算所有特征（属性）,A,、,B,、,C,的信息增益，选择信息增益最大的特征作为节点；,然后以该节点的取值为分支，在剩余的特征（属性）中选取信息增益最大的特征作为子节点,3.,应用实例及,ID3,算法,23,ID3,算法,Python,程序展示,3.,应用实例及,ID3,算法,24,决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知测试数据的分类缺没有那么精确，即会出现过拟合现象。过拟合产生的原因在于在学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决方法是考虑决策树的复杂度，对已经生成的树进行简化。,剪枝（,pruning,）：,从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型。,实现方式：,极小化决策树整体的损失函数或代价函数来实现,决策树剪枝,3.应用实例及,ID3,算法,25,损失函数定义,(1/2),N,tk,代表,t,个叶子上的第,k,种类型个数,3.,应用实例及,ID3,算法,26,损失函数定义,(2/2),3.,应用实例及,ID3,算法,27,C4.5,是,Ross Quinlan,在,1993,年在,ID3,的基础上改进而提出的。,ID3,采用的信息增益度量存在一个缺点，它一般会优先选择有较多属性值的,Feature,因为属性值多的,Feature,会有相对较大的信息增益,?(,信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大,),。为了避免这个不足,C4.5,中是用信息增益比率,(gain ratio),来作为选择分支的准则。信息增益比率通过引入一个被称作分裂信息,(Split information),的项来惩罚取值较多的,Feature,。除此之外，,C4.5,还弥补了,ID3,中不能处理特征属性值连续的问题。但是，对连续属性值需要扫描排序，会使,C4.5,性能下降，有兴趣可以参考博客。,C4.5,算法简介,3.,应用实例及,ID3,算法,28,信息增益比率定义,3.,应用实例及,ID3,算法,29,1.,决策树又叫判定树，是一种基本的分类与回归方法。,2.,优点：可读性强，分类速度快，容易转换成,if-then,分类规则,3.,通常分为,3,个步骤：特征（属性）选择、决策树的生成、决策树的修剪。,4.,特征选择即选择分裂属性，又叫属性选择度量，把数据划分成较小的分区。,5.,决策树的生成又叫决策树学习或者决策树归纳。,6.,决策树生成时采用贪心（即非回溯的、局部最优的）方法，以自顶向下递归的分治方式构造，只考虑局部最优。,7.,决策树修剪时递归地从树的叶节点向上回缩，考虑全局最优。,8.,决策算法之间的差别包括在创建树时如何选择属性和用于剪枝的机制。,9.,决策算法主要为：,ID3,算法，,C4.5,算法和,CART,算法。,决策树总结,(1/2),4.,决策树总结,30,10.ID3,算法和,C4.5,算法只有决策树的生成，没有对决策树进行剪枝。,CART,算法包括决策树的剪枝。,11.,在进行特征选择时，各个算法采用的选择分裂准则不同,:,ID3,算法使用信息增益准则，选择信息增益最大,(,熵最小,),的特征作为分裂属性。,C4.5,算法使用信息增益比准则，选择信息增益比最大的特征作为分裂属性。,CART,算法使用基尼指数准则，选择基尼指数最小的特征作为分裂属性。,12.,以信息增益准则划分训练数据集的特征时，偏向于选择属性取值较多的作为分裂属性；信息增益比准则调整了这种偏倚，但它倾向于产生不平衡的划分，其中一个分区比其他分区小得多；基尼指数准则也是偏向于多值属性，并且当类的数量很大时会有困难。,13.,所有的属性选择度量都具有某种偏倚。,14.,决策树归纳时的时间复杂度一般随树的高度指数增加。因此，倾向于产生较浅的树（如多路划分而不是二元划分）的度量可能更可取。但是，较浅的树趋向于具有大量树叶和较高的准确率。,15.,信息增益的度量标准：熵。熵越大，随机变量的不确定性就越大，分类能力就越低,.,决策树总结,(2/2),4.,决策树总结,31,10.ID3,算法和,C4.5,算法只有决策树的生成，没有对决策树进行剪枝。,CART,算法包括决策树的剪枝。,11.,在进行特征选择时，各个算法采用的选择分裂准则不同,:,ID3,算法使用信息增益准则，选择信息增益最大,(,熵最小,),的特征作为分裂属性。,C4.5,算法使用信息增益比准则，选择信息增益比最大的特征作为分裂属性。,CART,算法使用基尼指数准则，选择基尼指数最小的特征作为分裂属性。,12.,以信息增益准则划分训练数据集的特征时，偏向于选择属性取值较多的作为分裂属性；信息增益比准则调整了这种偏倚，但它倾向于产生不平衡的划分，其中一个分区比其他分区小得多；基尼指数准则也是偏向于多值属性，并且当类的数量很大时会有困难。,13.,所有的属性选择度量都具有某种偏倚。,14.,决策树归纳时的时间复杂度一般随树的高度指数增加。因此，倾向于产生较浅的树（如多路划分而不是二元划分）的度量可能更可取。但是，较浅的树趋向于具有大量树叶和较高的准确率。,15.,信息增益的度量标准：熵。熵越大，随机变量的不确定性就越大，分类能力就越低,.,决策树总结,(2/2),4.,决策树总结,32,决策树仅仅是一种分类算法，其实并不能体现决策过程。,决策树算法的基本原理是每次选择与类别相关性最大的属性进行分裂。,ID3,算法使用了熵，熵是对概率倒数的对数求数学期望。由于条件熵是对条件概率的熵求数学期望，本质上条件熵反映了两个随机变量的相关性。,ID3,算法的的实质仍是选择与类别相关性最大的属性来进行分裂。只是这个相关性是用互信息量来衡量的。,决策树算法并没有考虑各属性之间的相关性。,尽管有剪枝等等方法，一棵树的生成肯定还是不如多棵树，因此就有了随机森林，解决决策树泛化能力弱的缺点（三个臭裨将顶个诸葛亮）。,一些思考,5.,一些思考,33,