人工智能之决策树.ppt

决策树,决策树基本概念信息论基础应用实例及ID3算法决策树总结一些思考,目录,生活中的决策树1(DecisionTree),决策树基本概念,Adecisiontreeisaflowchart-likestructureinwhicheachinternalnoderepresentsatestonanattribute(e.g.whetheracoinflipcomesupheadsortails),eachbranchrepresentstheoutcomeofthetest,andeachleafnoderepresentsaclasslabel(decisiontakenaftercomputingallattributes).Thepathsfromroottoleafrepresentclassificationrules.决策树是一种类似于流程图的结构，其中每个内部节点代表一个属性上的“测试”（例如，一个硬币的翻转是正面还是反面），每个分支代表测试的结果，每个叶节点代表一个类标签（在计算所有属性之后做出的决定）。从根到叶子的路径表示分类规则。,定义,决策树基本概念,生活中的决策树2(DecisionTree),属性测试,属性测试,决定,决定,分支,构建决策树的关键问题：1.以何种属性进行测试2.以何种顺序进行测试3.何时做出决定,决策树基本概念,连接主义者认为，机器学习分为监督学习，无监督学习和强化学习。监督学习就是训练样本带有属性标签。监督学习又可分为“回归”和“分类”问题。机器学习中的分类技术一般是用一种学习算法确定分类模型，该模型可以很好地拟合类标号和属性集之间的映射关系。常用的分类算法包括：决策树分类法、逻辑回归分类法、神经网络、支持向量级、朴素贝叶斯分类方法等。,机器学习中的决策树（1/2）,决策树基本概念,在机器学习中，决策树是一个带有标签的监督式学习预测模型，代表的是对象属性与对象值之间的一种映射关系。算法ID3，C4.5和C5.0是基于信息学理论中熵的理论而设计的。相比大多数分类算法，如kNN等，决策树易于理解和实现，使用者无需了解很多背景知识。它能够对数据集合进行分析，挖掘其中蕴含的知识信息。,机器学习中的决策树（2/2）,决策树基本概念,决策树算法采用自上至下递归建树的技术，该算法的产生源于CLS系统，即概念学习系统。,决策树算法发展历史(1/2),决策树基本概念,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),决策树基本概念,决策树重要概念,决策树基本概念,信息的大小可以度量么？信息量的大小与概率有关！概率越小，信息量越大。出现概率为0，信息量无穷大概率越大，信息量越小。出现概率为1，信息量为0.,信息量,2.信息论基础,1948年10月，香农在贝尔系统技术学报上发表论文AMathematicalTheoryofCommunication，首次建立通讯过程的数学模型，成为现代信息论研究的开端。香农理论的重要特征是熵（entropy）的概念，他证明熵与信息内容的不确定程度有等价关系。,信息论,2.信息论基础,消息发生后所含有的信息量，反映了消息发生前的不确定性：,信息量,譬如袋子里有红球和黑球，取红球的概率为0.4，取黑球的概率为0.6。取出红球的信息量为1.322，取出黑球的信息量0.737。,2.信息论基础,熵(entropy)这一词最初来源于热力学。1948年，克劳德爱尔伍德香农将热力学中的熵引入信息论，所以也被称为香农熵(Shannonentropy)，信息熵(informationentropy)。表示系统的不确定性。公式：,信息熵,譬如袋子里有红球和黑球，取红球的概率为0.4，取黑球的概率为0.6。取出红球的信息量为1.322，取出黑球的信息量0.737。取出1个球的加权平均信息量为1.322*0.4+0.737*0.6。思考：什么情况下，熵最大？,2.信息论基础,条件熵H(X|Y)表示在已知随机变量Y的条件下随机变量X的不确定性。H(X|Y)，其实质是给定Y情况下X条件概率分布的熵，对Y的数学期望：,条件熵,2.信息论基础,条件熵和互信息量,2.信息论基础,互信息量，又称信息增益,Y代表性别，取值为男和女；X代表穿着，取值为裙子和裤子。,信息增益计算实例,注意：H（Y/X）代表已知某人穿着，其性别的不确定性,2.信息论基础,求信息增益：I(X;Y)=H(Y)-H（Y/X）,首先计算条件熵,2.信息论基础,Step1：计算信息熵,Step2：计算给定X条件下，Y条件概率的熵,Step3：Y条件概率的熵值对X求数学期望,其次计算信息增益,2.信息论基础,互信息量，也就是随机变量X对随机变量Y的信息增益,ID3由RossQuinlan在1986年提出。其核心是根据“最大信息熵增益”原则选择划分当前数据集的最好特征，减少数据的熵(混乱度)。ID3是一种贪心算法：1）从根结点(rootnode)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征。2）由该特征的不同取值建立子节点，再对子节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；3）最后得到一个决策树。每次选取的分割数据的特征都是当前的最佳选择，并按照该特征的所有取值来切分，也就是说如果一个特征有4种取值，数据将被切分4份。,ID3算法简介,3.应用实例及ID3算法,ID3算法伪代码,应用实例：是否放贷的决策树,对特征进行标注（预处理）年龄：0代表青年，1代表中年，2代表老年；有工作：0代表否，1代表是；有自己的房子：0代表否，1代表是；信贷情况：0代表一般，1代表好，2代表非常好；类别(是否给贷款)：no代表否，yes代表是。,3.应用实例及ID3算法,信息熵计算公式,采用频率替代概率。数据集D为是否放贷的类别，Ck代表该类别的某一取值的出现频率，如不放贷出现的频次,特征A有n种取值，H(Di)代表在A属性的第i个取值下，D的条件概率熵H(D/Ai),信息增益，即特征A对D的信息增益,注意：要计算所有特征（属性）A、B、C的信息增益，选择信息增益最大的特征作为节点；然后以该节点的取值为分支，在剩余的特征（属性）中选取信息增益最大的特征作为子节点,3.应用实例及ID3算法,Python程序展示,3.应用实例及ID3算法,决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知测试数据的分类缺没有那么精确，即会出现过拟合现象。过拟合产生的原因在于在学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决方法是考虑决策树的复杂度，对已经生成的树进行简化。剪枝（pruning）：从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型。实现方式：极小化决策树整体的损失函数或代价函数来实现,决策树剪枝,3.应用实例及ID3算法,损失函数定义(1/2),Ntk代表t个叶子上的第k种类型个数,3.应用实例及ID3算法,损失函数定义(2/2),3.应用实例及ID3算法,C4.5是RossQuinlan在1993年在ID3的基础上改进而提出的。ID3采用的信息增益度量存在一个缺点，它一般会优先选择有较多属性值的Feature,因为属性值多的Feature会有相对较大的信息增益?(信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大)。为了避免这个不足C4.5中是用信息增益比率(gainratio)来作为选择分支的准则。信息增益比率通过引入一个被称作分裂信息(Splitinformation)的项来惩罚取值较多的Feature。除此之外，C4.5还弥补了ID3中不能处理特征属性值连续的问题。但是，对连续属性值需要扫描排序，会使C4.5性能下降，有兴趣可以参考博客。,C4.5算法简介,3.应用实例及ID3算法,信息增益比率定义,3.应用实例及ID3算法,1.决策树又叫判定树，是一种基本的分类与回归方法。2.优点：可读性强，分类速度快，容易转换成if-then分类规则3.通常分为3个步骤：特征（属性）选择、决策树的生成、决策树的修剪。4.特征选择即选择分裂属性，又叫属性选择度量，把数据划分成较小的分区。5.决策树的生成又叫决策树学习或者决策树归纳。6.决策树生成时采用贪心（即非回溯的、局部最优的）方法，以自顶向下递归的分治方式构造，只考虑局部最优。7.决策树修剪时递归地从树的叶节点向上回缩，考虑全局最优。8.决策算法之间的差别包括在创建树时如何选择属性和用于剪枝的机制。9.决策算法主要为：ID3算法，C4.5算法和CART算法。,决策树总结(1/2),4.决策树总结,10.ID3算法和C4.5算法只有决策树的生成，没有对决策树进行剪枝。CART算法包括决策树的剪枝。11.在进行特征选择时，各个算法采用的选择分裂准则不同:ID3算法使用信息增益准则，选择信息增益最大(熵最小)的特征作为分裂属性。C4.5算法使用信息增益比准则，选择信息增益比最大的特征作为分裂属性。CART算法使用基尼指数准则，选择基尼指数最小的特征作为分裂属性。12.以信息增益准则划分训练数据集的特征时，偏向于选择属性取值较多的作为分裂属性；信息增益比准则调整了这种偏倚，但它倾向于产生不平衡的划分，其中一个分区比其他分区小得多；基尼指数准则也是偏向于多值属性，并且当类的数量很大时会有困难。13.所有的属性选择度量都具有某种偏倚。14.决策树归纳时的时间复杂度一般随树的高度指数增加。因此，倾向于产生较浅的树（如多路划分而不是二元划分）的度量可能更可取。但是，较浅的树趋向于具有大量树叶和较高的准确率。15.信息增益的度量标准：熵。熵越大，随机变量的不确定性就越大，分类能力就越低.,决策树总结(2/2),4.决策树总结,10.ID3算法和C4.5算法只有决策树的生成，没有对决策树进行剪枝。CART算法包括决策树的剪枝。11.在进行特征选择时，各个算法采用的选择分裂准则不同:ID3算法使用信息增益准则，选择信息增益最大(熵最小)的特征作为分裂属性。C4.5算法使用信息增益比准则，选择信息增益比最大的特征作为分裂属性。CART算法使用基尼指数准则，选择基尼指数最小的特征作为分裂属性。12.以信息增益准则划分训练数据集的特征时，偏向于选择属性取值较多的作为分裂属性；信息增益比准则调整了这种偏倚，但它倾向于产生不平衡的划分，其中一个分区比其他分区小得多；基尼指数准则也是偏向于多值属性，并且当类的数量很大时会有困难。13.所有的属性选择度量都具有某种偏倚。14.决策树归纳时的时间复杂度一般随树的高度指数增加。因此，倾向于产生较浅的树（如多路划分而不是二元划分）的度量可能更可取。但是，较浅的树趋向于具有大量树叶和较高的准确率。15.信息增益的度量标准：熵。熵越大，随机变量的不确定性就越大，分类能力就越低.,决策树总结(2/2),4.决策树总结,决策树仅仅是一种分类