决策树知识和介绍

《决策树知识和介绍》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.决策树的概念       如图所示，每个非叶子节点代表了一个属性，父子节点之间的连接线代表了父节点属性的取值或取值范围，叶子节点代表了分类。上述决策树所代表的输入对象包含了3个属性{年龄，是否学生，信誉}，年龄属性的取值为{青，中，老}，要分类的标签为{买，不买}。路径中的每一个分支是其连接的父节点所代表的属性的取值。父节点属性可能是离散的或者是连续的。2.CLS（ConceptLearningSystem）算法   从一棵空决策树开始，选择某一属性（分类属性）作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集，如果该子集为空（样本空间

2、中没有样本取该值），或该子集中的样本属于同一个类(样本空间中属性取该值得样本都属于同一分类)，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。    示例：     请根据眼睛颜色和头发颜色构造一个决策树判定所属人种。  过程：   step1：选择眼睛颜色（ec）作为根节点，该属性有{黑色black，蓝色blue，灰色gray}3个取值,black取值的样本为{<1,黄种人>,<6,混血>}，子集不属于同一类样本，因此还要考虑另外的属性。如图所示：        step2：选择属性头发颜色

3、{黑，金，红}。在上图的第一个分支集合{1,6}中，            头发颜色为黑色的子集为{<1,黄种人>}，该子集可以作为叶子节点存在          头发颜色为金色的子集为{<6,混血>}，该子集可以作为叶子节点存在          头发颜色为红色的子集为空集，该子集可以作为叶子节点存在，也可以不做任何处理。            最终的结果如下图所示：        算法的关键点：给定了样本空间集合S和属性集合T，我们的目的是构建一个决策树Tree      算法CreateTree    输入：S和T    输出：Tree    初始变量：空树Tree       

4、 过程：          1)ifSisemptyorTisemptythen                  returnTree              end      2)selecttfromT andcreateatreenodeparentNodeastheroot          3)splitSinS1,S2,...,Skbythevalueoft(根据t的k个可能取值，将S划分为子集S1,S2,...Sk)           4)foreachSi do                  ifthesamplesinsihavesameclasslabel

5、 then                      inserttheclasslableasthechildnodeforparentNode                  else                       childTree=CreateTree(Si,T-t)                      addchildTreerootasthechildNodeforparentNode                  end              end           5)T<-T-tandgoto1)算法的注意点：在步骤2中selectt

6、fromT 表示从T中抽取出一个属性，抽取哪个属性是算法的关键；在步骤4的循环中，CreateTree(si,T.Copy()),使用的是T的一个拷贝，这样保证了对于S的每一个子集Si，使用的是相同的属性集合。    3.ID3算法   该方法使用信息增益度选择测试属性。小概率事件比大概率事件包含的信息量大。如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的信息量大。事件ai的信息量I（ai）可如下度量：   其中p(ai)表示事件ai发生的概率。假设有n个互不相容的事件a1,a2,a3,….,an,它们中有且仅有一个发生，则其平均的信息量可如下度量：  当p(ai)=0或者p

7、(ai)=1的时，信息量I(ai)=0，也就是不可能事件和必然事件的信息量为0.  信息熵的定义：一个变量X，它可能的取值有n多种，分别是x1，x2，……，xn，每一种取到的概率分别是P1，P2，……，Pn，那么X的熵就定义为：意思就是一个变量可能的变化越多（反而跟变量具体的取值没有任何关系，只和值的种类多少以及发生概率有关），它携带的信息量就越大。    对分类系统来说，类别C是变量，它可能的取值是C1，C2，……，Cn，而每一个类别出现的概