《商务智能理论与应用5-决策树精编版》由会员分享，可在线阅读，更多相关《商务智能理论与应用5-决策树精编版（53页珍藏版）》请在金锄头文库上搜索。
1、1,决策树(Decision Tree),2020/8/11,2,1、分类的意义,数据库,了解类别属性与特征,分类模型 决策树,分类模型 聚类,一、分类(Classification),2020/8/11,3,数据库,分类标记,2020/8/11,2、分类的技术,（1）决策树,4,（2）聚类,2020/8/11,3、分类的程序,5,模型建立(Model Building) 模型评估(Model Evaluation) 使用模型(Use Model),2020/8/11,决策树分类的步骤,6,数据库,2020/8/11,训练样本(training samples),建立模型,测试样本(testi
2、ng samples),评估模型,例：,7,错误率为66.67%,2020/8/11,4、分类算法的评估,8,预测的准确度：指模型正确地预测新的或先前未见过的数据的类标号的能力。 训练测试法(training-and-testing) 交叉验证法(cross-validation) 例如，十折交叉验证。即是将数据集分成十分，轮流将其中9份做训练1份做测试，10次的结果的均值作为对算法精度的估计，一般还需要进行多次10倍交叉验证求均值，例如10次10倍交叉验证，更精确一点。,2020/8/11,2020/8/11,9,速度：指产生和使用模型的计算花费。 建模的速度、预测的速度 强壮性：指给定噪声
3、数据或具有缺失值的数据，模型正确预测的能力。 可诠释性：指模型的解释能力。,10,2020/8/11,决策树归纳的基本算法是贪心算法，它以自顶向下递归各个击破的方式构造决策树。 贪心算法：在每一步选择中都采取在当前状态下最好/优的选择。 在其生成过程中，分割方法即属性选择度量是关键。通过属性选择度量，选择出最好的将样本分类的属性。 根据分割方法的不同，决策树可以分为两类：基于信息论的方法（较有代表性的是ID3、C4.5算法等）和最小GINI指标方法（常用的有CART、SLIQ及SPRINT算法等）。,二、决策树(Decision Tree),信息增益,信息越明确，所包含的信息量越大，熵越小，信
4、息增益越大，反正，熵越大 比如明天太阳从东边出来,熵最小 比如投硬币，谁都不知道下一次将会是那一面，熵最大 决策树分裂的基本原则是数据集被分裂为若干个子集后，要使每个子集中的数据尽可能的纯，也就是说子集中的记录要尽可能属于同一个类别，即要使分裂后各子集的熵尽可能的小。 要让树尽可能的简洁，不能太复杂，因此选择熵最小的属性作为分裂节点,2020/8/11,11,（一）决策树的结构,12,根部节点(root node),中间节点(non-leaf node) (代表测试的条件),分支(branches) (代表测试的结果),叶节点(leaf node) (代表分类后所获得的分类标记),2020/8
5、/11,2020/8/11,13,（二）决策树的形成,例：,14,根部节点 中间节点 停止分支,？,2020/8/11,（三）ID3算法(C4.5,C5.0),15,2020/8/11,Quinlan(1979)提出，以Shannon(1949)的信息论为依据。 ID3算法的属性选择度量就是使用信息增益，选择最高信息增益的属性作为当前节点的测试属性。 信息论：若一事件有k种结果，对应的概率为Pi。则此事件发生后所得到的信息量I(熵，视为Entropy)为：I=-(p1*log2(p1)+ p2*log2(p2)+ pk*log2(pk),Example 1： 设 k=4p1=0.25,p2=0
6、.25,p3=0.25,p4=0.25 I=-(.25*log2(.25)*4)=2 Example 2： 设k=4p1=0,p2=0.5,p3=0,p4=0.5I=-(.5*log2(.5)*2)=1 Example 3： 设 k=4p1=1,p2=0,p3=0,p4=0 I=-(1*log2(1)=0,2020/8/11,16,2020/8/11,17,信息增益,18,Example(Gain),n=16 n1=4,I(16,4)=(4/16)*log2(4/16)+(12/16)*log2(12/16)=0.8113,E(年龄)=(6/16)*I(6,1)+(10/16)*I(10,3)
7、=0.7946 Gain(年龄)=I(16,4)-E(年龄)=0.0167,Gain(年龄)=0.0167,Max:作为第一个分类依据,2020/8/11,Gain(性别)=0.0972,Gain(家庭所得)=0.0177,Example(续),19,Gain(家庭所得)=0.688,I(7,3)=-(3/7)*log2(3/7)+(4/7)*log2(4/7)=0.9852,Gain(年龄)=0.9852,Gain(年龄)=0.2222,I(9,1)=-(1/9)*log2(1/9)+(8/9)*log2(8/9)=0.5032,Gain(家庭所得)=0.5032,2020/8/11,Exa
8、mple(end)ID3算法,20,分类规则： IF性别=Female AND家庭所得= 低所得THEN购买RV房车=否 IF性别=Female AND家庭所得= 小康THEN购买RV房车=否 IF性别=Female AND家庭所得= 高所得THEN购买RV房车=是 IF性别=Male AND年龄35 THEN购买RV房车=否 IF性别=Male AND年龄35 THEN购买RV房车=是,资料,Decision Tree,2020/8/11,决策树算法,第1步计算决策属性的熵,决策属性“买计算机？”。该属性分 两类：买/不买 S1(买)=641 S2（不买）= 383 S=S1+S2=1024
9、 P1=641/1024=0.6260 P2=383/1024=0.3740 I(S1,S2)=I(641,383) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9537,决策树算法,第2步计算条件属性的熵,条件属性共有4个。分别是年龄、 收入、学生、信誉。 分别计算不同属性的信息增益。,决策树算法,第2-1步计算年龄的熵,年龄共分三个组： 青年、中年、老年 青年买与不买比例为128/256 S1(买)=128 S2（不买）= 256 S=S1+S2=384 P1=128/384 P2=256/384 I(S1,S2)=I(128,256) =-P
10、1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183,决策树算法,第2-2步计算年龄的熵,年龄共分三个组： 青年、中年、老年 中年买与不买比例为256/0 S1(买)=256 S2（不买）= 0 S=S1+S2=256 P1=256/256 P2=0/256 I(S1,S2)=I(256，0) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0,决策树算法,第2-3步计算年龄的熵,年龄共分三个组： 青年、中年、老年 老年买与不买比例为125/127 S1(买)=125 S2（不买）=127 S=S1+S2=252 P
11、1=125/252 P2=127/252 I(S1,S2)=I(125，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157,决策树算法,第2-4步计算年龄的熵,年龄共分三个组： 青年、中年、老年 所占比例 青年组 384/1025=0.375 中年组 256/1024=0.25 老年组 384/1024=0.375 计算年龄的平均信息期望 E（年龄）=0.375*0.9183+ 0.25*0+ 0.375*0.9157 =0.6877 G（年龄信息增益） =0.9537-0.6877 =0.2660 （1）,决策树算法,第3步计算收入的
12、熵,收入共分三个组： 高、中、低 E（收入）=0.9361 收入信息增益=0.9537-0.9361 =0.0176 (2),决策树算法,第4步计算学生的熵,学生共分二个组： 学生、非学生 E（学生）=0.7811 年龄信息增益=0.9537-0.7811 =0.1726 （3）,决策树算法,第5步计算信誉的熵,信誉分二个组： 良好，优秀 E（信誉）= 0.9048 信誉信息增益=0.9537-0.9048 =0.0453 （4）,决策树算法,第6步计算选择节点,年龄信息增益=0.9537-0.6877 =0.2660 （1） 收入信息增益=0.9537-0.9361 =0.0176 （2）
13、年龄信息增益=0.9537-0.7811 =0.1726 （3） 信誉信息增益=0.9537-0.9048 =0.0453 （4）,决策树算法,年龄,青年,中年,老年,买/ 不买,买,买/ 不买,叶子,决策树算法,青年买与不买比例为128/256 S1(买)=128 S2（不买）= 256 S=S1+S2=384 P1=128/384 P2=256/384 I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183,决策树算法,如果选择收入作为节点 分高、中、低,平均信息期望（加权总和）： E(收入）= 0.333
14、3 * 0 + 0.5 * 0.9183 + 0.1667 * 0 = 0.4592 Gain(收入) = I(128, 256) - E(收入)=0.9183 0.4592 = 0.4591,I(0,128)=0 比例: 128/384=0.3333 I(64,128)=0.9183 比例: 192/384=0.5 I(64,0)=0 比例: 64/384=0.1667,注意,决策树算法,第6章 决策树,年龄,青年,中年,老年,学生,买,信誉,叶子,否,是,优,良,买,不买,买/ 不买,买,叶子,叶子,叶子,决策树算法,ID3 决策树建立算法 1 决定分类属性； 2 对目前的数据表，建立一个
15、节点N 3 如果数据库中的数据都属于同一个类，N就是树叶，在树叶上 标出所属的类 4 如果数据表中没有其他属性可以考虑，则N也是树叶，按照少 数服从多数的原则在树叶上标出所属类别 5 否则，根据平均信息期望值E或GAIN值选出一个最佳属性作 为节点N的测试属性 6 节点属性选定后，对于该属性中的每个值： 从N生成一个分支，并将数据表中与该分支有关的数据收集形 成分支节点的数据表，在表中删除节点属性那一栏 如果分支数据表非空，则运用以上算法从该节点建立子树。,决策树算法,（四）Decision Tree的建立过程,37,1、决策树的停止 决策树是通过递归分割(recursive partitio
16、ning)建立而成，递归分割是一种把数据分割成不同小的部分的迭代过程。 如果有以下情况发生，决策树将停止分割： 该群数据的每一笔数据都已经归类到同一类别。 该群数据已经没有办法再找到新的属性来进行节点分割。 该群数据已经没有任何尚未处理的数据。,2020/8/11,2、决策树的剪枝(pruning),38,决策树学习可能遭遇模型过度拟合（over fitting）的问题，过度拟合是指模型过度训练，导致模型记住的不是训练集的一般性，反而是训练集的局部特性。 如何处理过度拟合呢？对决策树进行修剪。 树的修剪有几种解决的方法，主要为先剪枝和后剪枝方法。,2020/8/11,（1）先剪枝方法,39,在先剪枝方法中，通过提前停止树的构造（例如，通过决定在给定的节点上不再分裂或划分训练
