分类决策树_ID3算法

决策树决策树基本概念决策树算法主要内容决策树基本概念决策树算法决策树基本概念关于分类问题分类（Classification）任务就是通过学习获得一个目标函数（TargetFunction）f,将每个属性集x映射到一个预先定义好的类标号y。分类任务的输入数据是纪录的集合，每条记录也称为实例或者样例。用元组(X,y)表示，其中，X是属性集合，y是一个特殊的属性，指出样例的类标号（也称为分类属性或者目标属性）决策树基本概念关于分类问题名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类恒温毛发是否否是否哺乳动物海龟冷血鳞片否半否是否爬行类鸽子恒温羽毛否否是是否鸟类鲸恒温毛发是是否否否哺乳类Xy分类与回归分类目标属性y是离散的，回归目标属性y是连续的决策树基本概念解决分类问题的一般方法分类技术是一种根据输入数据集建立分类模型的系统方法。分类技术一般是用一种学习算法确定分类模型，该模型可以很好地拟合输入数据中类标号和属性集之间的联系。学习算法得到的模型不仅要很好拟合输入数据，还要能够正确地预测未知样本的类标号。因此，训练算法的主要目标就是要建立具有很好的泛化能力模型，即建立能够准确地预测未知样本类标号的模型。分类方法的实例包括：决策树分类法、基于规则的分类法、神经网络、支持向量级、朴素贝叶斯分类方法等。决策树基本概念解决分类问题的一般方法通过以上对分类问题一般方法的描述，可以看出分类问题一般包括两个步骤：1、模型构建（归纳）通过对训练集合的归纳，建立分类模型。2、预测应用（推论）根据建立的分类模型，对测试集合进行测试。决策树基本概念解决分类问题的一般方法TIDA1A2A3类1Y100LN2N125SN3Y400LY4N415MN学习算法学习模型模型应用模型TIDA1A2A3类1Y100L？2N125S？3Y400L？4N415M？训练集（类标号已知）检验集（类标号未知）归纳推论决策树基本概念决策树决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树基本概念决策树的优点1、推理过程容易理解，决策推理过程可以表示成IfThen形式；2、推理过程完全依赖于属性变量的取值特点；3、可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量的数目提供参考。主要内容决策树基本概念决策树算法决策树算法与决策树相关的重要算法1、Hunt,Marin和Stone于1966年研制的CLS学习系统，用于学习单个概念。2、1979年,J.R.Quinlan给出ID3算法，并在1983年和1986年对ID3进行了总结和简化，使其成为决策树学习算法的典型。3、Schlimmer和Fisher于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。4、1988年，Utgoff在ID4基础上提出了ID5学习算法，进一步提高了效率。1993年，Quinlan进一步发展了ID3算法，改进成C4.5算法。5、另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。CLS,ID3，C4.5，CART决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？又：你需要多少有关这位客人的信息才能回答这个问题？决策树的用途计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买谁在买计算机？年龄？学生？信誉？买青中老否是优良不买买买不买决策树的用途决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买谁在买计算机？年龄？学生？信誉？买青中老否是优良不买买买不买决策树的用途决策树算法决策树算法决策树的表示决策树的基本组成部分：决策结点、分支和叶子。年龄？学生？信誉？买青中老否是优良不买买买不买决策树中最上面的结点称为根结点。是整个决策树的开始。每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或者决策.通常对应待分类对象的属性。每个叶结点代表一种可能的分类结果在沿着决策树从上到下的遍历过程中，在每个结点都有一个测试。对每个结点上问题的不同测试输出导致不同的分枝，最后会达到一个叶子结点。这一过程就是利用决策树进行分类的过程，利用若干个变量来判断属性的类别ID3决策树算法ID3算法主要针对属性选择问题。是决策树学习方法中最具影响和最为典型的算法。该方法使用信息增益度选择测试属性。当获取信息时，将不确定的内容转为确定的内容，因此信息伴着不确定性。从直觉上讲，小概率事件比大概率事件包含的信息量大。如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的信息量大。如何度量信息量的大小？ID3–信息量大小的度量决策树算法Shannon1948年提出的信息论理论。事件ai的信息量I（ai）可如下度量：其中p(ai)表示事件ai发生的概率。假设有n个互不相容的事件a1,a2,a3,….,an,它们中有且仅有一个发生，则其平均的信息量可如下度量：niiiniinapapaIaaaI12121)(1log)()(),...,,()(1log)()(2iiiapapaIID3–信息量大小的度量决策树算法niiiniinapapaIaaaI12121)(1log)()(),...,,(上式，对数底数可以为任何数，不同的取值对应了熵的不同单位。通常取2，并规定当p(ai)=0时=0)(1log)()(2iiiapapaI信息增益–用来衡量给定的属性区分训练样例的能力，中间（间接）表示属性–ID3算法在生成树的每一步使用信息增益从候选属性中选择属性用熵度量样例的均一性决策树算法信息增益用熵度量样例的均一性–熵刻画了任意样例集合S的纯度–给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类（函数）的熵为–信息论中对熵的一种解释：熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数；熵值越大，需要的位数越多。–更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为决策树算法用信息增益度量熵的降低程度–属性A的信息增益，使用属性A分割样例集合S而导致的熵的降低程度–Gain(S,A)是在知道属性A的值后可以节省的二进制位数–例子，注意是对当前样例集合计算上式()(,)()()vvvValuesASGainSAEntropySEntropySS理解信息熵1、信息熵是用来衡量一个随机变量出现的期望值，一个变量的信息熵越大，那么它出现的各种情况也就越多，也就是包含的内容多，我们要描述它就需要付出更多的表达才可以，也就是需要更多的信息才能确定这个变量。2、信息熵是随机变量的期望。度量信息的不确定程度。信息的熵越大，信息就越不容易搞清楚（杂乱）。3、一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。信息熵也可以说是系统有序化程度的一个度量。4、信息熵用以表示一个事物的非确定性，如果该事物的非确定性越高，你的好奇心越重，该事物的信息熵就越高。5、熵是整个系统的平均消息量。信息熵是信息论中用于度量信息量的一个概念。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。6、处理信息就是为了把信息搞清楚，实质上就是要想办法让信息熵变小。理解信息增益–熵：表示随机变量的不确定性。–条件熵：在一个条件下，随机变量的不确定性。–信息增益：熵-条件熵。表示在一个条件下，信息不确定性减少的程度。例如：–假设X(明天下雨)的信息熵为2（不确定明天是否下雨），Y(如果是阴天则下雨）的条件熵为0.01（因为如果是阴天就下雨的概率很大，信息就少了）信息增益=2-0.01=1.99。信息增益很大。说明在获得阴天这个信息后，明天是否下雨的信息不确定性减少了1.99，是很多的，所以信息增益大。也就是说阴天这个信息对下雨来说是很重要的。ID3–信息量大小的度量决策树算法Gain（S，A）是属性A在集合S上的信息增益Gain（S，A）=Entropy（S）-Entropy（S，A）Gain（S，A）越大，说明选择测试属性对分类提供的信息越多计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第1步计算决策属性的熵决策属性“买计算机？”。该属性分两类：买/不买S1(买)=641S2（不买）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9537决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2步计算条件属性的熵条件属性共有4个。分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-1步计算年龄的熵年龄共分三个组：青年、中年、老年青年买与不买比例为128/256S1(买)=128S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-2步计算年龄的熵年龄共分三个组：青年、中年、老年中年买与不买比例为256/0S1(买)=256S2（不买）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1