决策树技术

决策树技术DecisionTrees组员：贾小彦邓蓓蓓戴维内容提要简介决策树基本概念决策树的优缺点经典算法简介决策树和决策规则是解决实际应用中分类问题的数据挖掘方法。一般来说，分类是把数据项映射到其中一个事先定义的类中的这样一个学习函数的过程。由一组输入的属性值向量(也叫属性向量)和相应的类，用基于归纳学习算法得出分类。学习的目标是构建一个分类模型，通常也叫分类器。它可以根据有效的属性输入值预测一些实体(所给样本)的类。是一个在样本其他属性已知的情况下预测另外一个属性(样本的类)的模型(分类的结果)。(a)决策树方法的起源是概念学习系统CLS(b)机器学习领域前辈及大牛之一Quinlan,J.R,在1983提出ID3决策树算法；1993年正式提出了c4.5算法,并公布了源代码2002年发表C5.0（See5）商业版决策树的另一类家族：CART1984，Friedman&Breiman决策树基本概念决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。下图是一个简单的决策树。该问题有两个属性X,Y。所有属性值X1和YB的样本属于类2。不论属性Y的值是多少，值X1的样本都属于类1。决策树的表示决策树的基本组成部分：决策结点、分支和叶子。决策树中最上面的结点称为根结点是整个决策树的开始。每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或者决策通常对应待分类对象的属性。每个叶结点代表一种可能的分类结果在沿着决策树从上到下的遍历过程中，在每个结点都有一个测试。对每个结点上问题的不同测试输出导致不同的分枝，最后会达到一个叶子结点。这一过程就是利用决策树进行分类的过程，利用若干个变量来判断属性的类别决策树的优点1、推理过程容易理解，决策推理过程可以表示成IfThen形式；2、推理过程完全依赖于属性变量的取值特点；3、可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量的数目提供参考。决策树的缺点1、对连续性的字段比较难预测2、当类别太多时，错误可能会增加的比较快3、一般的算法分类的时候，只是根据一个属性来分类。不是全局最优。决策树的优、缺点经典算法——ID3学习算法决策树的生成基本算法自上而下分而治之的方法开始时，所有的数据都在根节点属性都是种类字段(如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割重要问题：哪个属性作为当前的测试节点信息论相关内容Shannon1948年提出的信息论理论。事件ai的信息I（ai）可如下度量：)(1log)()(2iiiapapaI其中p(ai)表示事件ai发生的概率。假设有n个互不相容的事件a1,a2,a3,….,an,它们中有且仅有一个发生，则其平均的信息量可如下度量：niiiniinapapaIaaaI12121)(1log)()(),...,,(niiiniinapapaIaaaIsEntropy12121)(1log)()(),...,,()(上式，对数底数可以为任何数，不同的取值对应了熵的不同单位。通常取2，并规定当p(ai)=0时=0)(1log)()(2iiiapapaI公式1在决策树分类中，假设S是训练样本集合，|S|是训练样本数，样本划分为n个不同的类C1,C2,….Cn，这些类的大小分别标记为|C1|，|C2|，…..,|Cn|。则任意样本S属于类Ci的概率为：||||)(SCSpiiEntropy（S，A）=∑（|Sv|/|S|）*Entropy(Sv)公式2∑是属性A的所有可能的值v,Sv是属性A有v值的S子集|Sv|是Sv中元素的个数；|S|是S中元素的个数。Gain（S，A）是属性A在集合S上的信息增益Gain（S，A）=Entropy(s)-Entropy（S，A）公式3Gain（S，A）越大，说明选择测试属性对分类提供的信息越多熵的计算Eg1:Eg2:假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？又：你需要多少有关这位客人的信息才能回答这个问题？计数年龄收入学生信誉归类：买计算机？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个。分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。第2-1步计算年龄的熵年龄共分三个组：青年、中年、老年青年买与不买比例为128/256S1(买)=128S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183第2-2步计算年龄的熵年龄共分三个组：青年、中年、老年中年买与不买比例为256/0S1(买)=256S2（不买）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0第2-3步计算年龄的熵年龄共分三个组：青年、中年、老年老年买与不买比例为125/127S1(买)=125S2（不买）=127S=S1+S2=252P1=125/252P2=127/252I(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.6877G（年龄信息增益）=0.9537-0.6877=0.2660（1）计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第3步计算收入的熵收入共分三个组：高、中、低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）学生信息增益=0.9537-0.7811=0.1726（3）信誉信息增益=0.9537-0.9048=0.0453（4）计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买年龄买/不买买/不买买青年中年老年叶子计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买青年买与不买比例为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青中否良不买64青低是良买64青中是优买如果选择收入作为节点分高、中、低I(0,128)=0比例:128/384=0.3333I(64,128)=0.9183比例:192/384=0.5I(64,0)=0比例:64/384=0.1667平均信息期望（加权总和）：E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.9183–0.4592=0.4591计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买ID3算法小结ID3算法是一种经典的决策树学习算法。ID3算法的基本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变为最小的属性，以构造一颗熵值下降最快的决策树，到叶子节点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于同一类。ID3算法存在的缺点（1）ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。（2）ID3算法只能对描述属性为离散型属性的数据集构造决策树针对ID3算法存在的不足它被改进为C4.5算法