决策树(详细易懂很多例子)

《决策树(详细易懂很多例子)》由会员分享，可在线阅读，更多相关《决策树(详细易懂很多例子)（49页珍藏版）》请在金锄头文库上搜索。

1、决策树 Decision Tree,决策树算法是一种归纳分类算法,它通过对训练集的学习,挖掘出有用的规则,用于对新集进行预测。有监督的学习。非参数学习算法。对每个输入使用由该区域的训练数据计算得到的对应的局部模型。 决策树归纳的基本算法是贪心算法，自顶向下递归方式构造决策树。贪心算法：在每一步选择中都采取在当前状态下最好/优的选择。在其生成过程中，分割方法即属性选择度量是关键。通过属性选择度量，选择出最好的将样本分类的属性。,简介,决策树的结构,决策树算法以树状结构表示数据分类的结果。每个决策点实现一个具有离散输出的测试函数，记为分支。根节点非叶子节点（决策点）叶子节点分支,决策树的结构,4,

2、根部节点(root node),非叶子节点(non-leaf node) (代表测试的条件，对数据属性的测试),分支(branches)(代表测试的结果),叶节点(leaf node) (代表分类后所获得的分类标记),2018/8/29,单变量树,每个内部节点中的测试只使用一个输入维。如果使用的输入维 是离散的，取n个可能的值之一，则该节点检测 的值，并取相应的分支，实现一个n路划分。决策点具有离散分支，而数值输入应当离散化。如果 是数值的（有序的），则测试函数是比较：其中 是适当选择阈值。该决策节点将输入空间一份为二： 和 ，称为一个二元划分。决策树根据所选取的属性是数值型还是离散型，每次将

3、数据划分成两个或n个子集。然后使用对应的子集递归地进行划分，直到不需要划分，此时，创建一个树叶节点标记它。,决策树分类,训练阶段从给定的训练数据集DB，构造出一棵决策树class = DecisionTree( DB )分类阶段从根开始，按照决策树的分类属性逐层往下划分，直到叶节点，获得概念（决策、分类）结果。y = DecisionTree( x ),Example of a Decision Tree,Another Example of Decision Tree,Apply Model to Test Data,Test Data,Start from the root of tree

4、.,Apply Model to Test Data,Test Data,Apply Model to Test Data,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,Test Data,Apply Model to Test Data,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,Test Data,Apply Model to Test Data,Refund,MarSt,TaxInc,YES,NO,N

5、O,NO,Yes,No,Married,Single, Divorced, 80K,Test Data,Apply Model to Test Data,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,Test Data,Assign Cheat to “No”,决策树原理,基本算法（贪心算法） 自上而下分而治之的方法 开始时，所有的数据都在根节点 属性都是离散值字段 (如果是连续的，将其离散化) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量 (如, informa

6、tion gain) 停止分割的条件 一个节点上的数据都是属于同一个类别 没有属性可以再用于对数据进行分割,算法：Generate_decision_tree由给定的训练数据产生一棵决策树 输入：训练数据集samples，用离散值属性表示；候选属性的集合attribute_list。 输出：一棵决策树 方法： （1）创建结点N； （2）if samples 都在同一个类C then （3）返回N作为叶结点，用类C标记； （4）if attribute_list 为空 then （5）返回N作为叶结点，标记samples中最普通的类；/多数表决 （6）选择attribute_list中的最优分类

7、属性test_attribute； /用信息增益作为属性选择度量 （7）标记结点N为test_attribute； （8）for each test_attribute中的已知值ai /划分samples （9）由结点N生长出一个条件为test_attributeai的分枝； （10）设si为samples中test_attributeai的样本集合；/一个划分 （11）if si为空 then （12）加上一个叶结点，标记为标记samples中最普通的类；/多数表决 （13）else 加上一个由Generate_decision_tree（si, attribute_list-test_at

8、tribute）返回的结点；,例子：算法过程,Refund,Yes,No,1. samples = 1,2,3,4,5,6,7,8,9,10 attribute_list = Refund, MarSt, TaxInc ,假设选择Refund为最优分割属性：,2. samples = 1,4,7 attribute_list = MarSt, TaxInc ,3. samples = 2,3,5,6,8,9,10 attribute_list = MarSt, TaxInc ,例子：算法过程,Refund,Yes,No,samples中所有样本属于同一个类Cheat=No,2. samples

9、 = 1,4,7 attribute_list = MarSt, TaxInc ,NO,例子：算法过程,Refund,Yes,No,假设选择MarSt为最优分割属性：,3. samples = 2,3,5,6,8,9,10 attribute_list = MarSt, TaxInc ,NO,MarSt,Single,Married,Divorced,4. samples = 3,8,10 , attribute_list = TaxInc 5. samples = 5,7 , attribute_list = TaxInc 6. samples = 2,9 , attribute_list

10、= TaxInc,例子：算法过程,Refund,Yes,No,选择TaxInc为最优分割属性：,4. samples = 3,8,10 attribute_list = TaxInc ,NO,MarSt,Single,Married,Divorced,TaxInc,= 80K,YES,NO,问题1：分类从哪个属性开始？选择分裂变量的标准问题2：为什么工资以80为界限？找到被选择的变量的分裂点的标准（连续变量情况）,分类划分的优劣用不纯性度量来分析。如果对于所有分支，划分后选择相同分支的所有实例都属于相同的类，则这个划分是纯的。对于节点m，令 为到达节点m的训练实例数， 个实例中 个属于 类，而

11、 。如果一个实例到节点m，则它属于 类的概率估计为：节点m是纯的，如果对于所有i， 为0或1。当到达节点m的所有实例都不属于 类时， 为0，当到达节点m的所有实例都属于 类时， 为1。一种度量不纯性的可能函数是熵函数（entropy)。,Father of information theory 证明熵与信息内容的不确定程度有等价关系系统科学领域三大论之一,C.Shannon的信息论,信息熵,熵(entropy),描述物质系统状态:该状态可能出现的程度。平均信息量 若一个系统中存在多个事件E1,E2,En每个事件出现的概率是p1,p2,pn则这个系统的平均信息量是,指的是系统的混乱的程度!,(b

12、its), 系统越无序、越混乱，熵就越大。 构造决策树，熵定义为无序性度量。 选择一个属性划分数据，使得子女节点上数据的类值（例中“yes”或“no”）大部分都相同（低无序性）。 如果一个节点上的数据类值在可能的类值上均匀分布，则称节点的熵（无序性）最大。 如果一个节点上的数据的类值对于所有数据都相同，则熵最小。 通过分裂，得到尽可能纯的节点。这相当于降低系统的熵。,例子,气象数据集，都是标称属性,什么因素影响是否去 打网球？,1.基于天气的划分,2.基于温度的划分,3.基于湿度的划分,4.基于有风的划分,构造树,训练样本的信息值 第一棵树，属性，各叶节点的信息值 第一棵树，属性，导致的信息增

13、益 依次，计算每棵树导致的信息增益 选择获得最大信息增益的属性进行划分 以此类推，递归，继续划分 当所有叶节点都是纯的，划分过程终止,（1）训练样本的信息值(基于类的比例） 训练样本（用来创建树的数据集）在包含9个yes和5个no的根节点上，对应于信息值info(9,5)=0.940位 总的信息,（2） 第一棵树，属性，各叶节点的信息值 基于天气(outlook)的划分，在叶节点的yes和no类的个数分别是2,3，4,0，和3,2，而这些节点的信息值分别是： info(2,3)=0.971位 sunny info(4,0)=0. 0位 overcast info(3,2)=0.971位 rai

14、n,（3）第一棵树，属性，导致的信息增益 计算平均信息值。 根据天气的树导致的信息增益为：基于类比例原来信息需求-基于天气属性划分之后得到的信息需求,gain(outlook)=info(9,5)-info(2,3,4,0,3,2) =0.940-0.693=0.247位,（4）依次，计算每棵树导致的信息增益 为每个属性计算信息增益 gain(outlook)=0.247位 gain(temperature)=0.029位 gain(humidity)=0.152位 gain(windy)=0.048位,（5）选择获得最大信息增益的属性进行划分 最大信息增益： gain(outlook)=0.

15、247位 选择天气作为树的根节点的划分属性，其中一个子女节点是最纯的，并且这使它明显优于其他属性。 湿度是次佳选择，它产生了一个几乎完全纯的较大的子女节点。,（6）以此类推，递归，继续划分 递归继续选择 当天气为晴时，所达到的节点上的可能的深一层的分支 除天气外，其他属性产生的信息增益分别为：gain(temperature)=0.571位gain(humidity)=0.971位gain(windy)=0.020位 继续再选择湿度(humidity)作为划分属性,天气，晴分支,纯子节点,（6）以此类推，递归，继续划分 天气，晴分支，气温，gain(temperature)=0.571位 天气，晴分支，湿度，gain(humidity)=0.971位 (纯的子女节点） 天气，晴分支，有风，gain(windy)=0.020位 天气，雨分支，气温，gain(temperature)=0.020位 天气，雨分支，湿度，gain(humidity)=0.020位 天气，雨分支，有风，gain(windy)=0.971位 （纯的子女节点）,