决策树知识和介绍.doc

1. 决策树的概念 如图所示，每个非叶子节点代表了一个属性，父子节点之间的连接线代表了父节点属性的取值或取值范围，叶子节点代表了分类。上述决策树所代表的输入对象包含了3个属性年龄，是否学生，信誉，年龄属性的取值为青，中，老，要分类的标签为买，不买。路径中的每一个分支是其连接的父节点所代表的属性的取值。父节点属性可能是离散的或者是连续的。2. CLS（Concept Learning System）算法 从一棵空决策树开始，选择某一属性（分类属性）作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集，如果该子集为空（样本空间中没有样本取该值），或该子集中的样本属于同一个类(样本空间中属性取该值得样本都属于同一分类)，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。示例： 请根据眼睛颜色和头发颜色构造一个决策树判定所属人种。 过程： step 1 ：选择眼睛颜色（ec）作为根节点，该属性有黑色black，蓝色blue，灰色gray3个取值,black取值的样本为,，子集不属于同一类样本，因此还要考虑另外的属性。如图所示： step 2：选择属性头发颜色黑，金，红。在上图的第一个分支集合1,6中，头发颜色为黑色的子集为，该子集可以作为叶子节点存在 头发颜色为金色的子集为，该子集可以作为叶子节点存在 头发颜色为红色的子集为空集，该子集可以作为叶子节点存在，也可以不做任何处理。最终的结果如下图所示：算法的关键点：给定了样本空间集合S和属性集合T，我们的目的是构建一个决策树Tree 算法CreateTree 输入：S和T 输出：Tree 初始变量： 空树Tree过程： 1) if S is empty or T is empty then return Tree end 2) select t from T and create a tree node parentNode as the root 3) split S in S1,S2,.,Sk by the value of t(根据t的k个可能取值，将S划分为子集S1,S2,.Sk) 4) for each Si do if the samples in si have same class label then insert the class lable as the child node for parentNode else childTree = CreateTree(Si,T-t) add childTree root as the childNode for parentNode end end 5) T-T-t and goto 1)算法的注意点：在步骤2中 select t from T表示从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(ai)=1的时，信息量I(ai)=0，也就是不可能事件和必然事件的信息量为0. 信息熵的定义：一个变量X，它可能的取值有n多种，分别是x1，x2，xn，每一种取到的概率分别是P1，P2，Pn，那么X的熵就定义为：意思就是一个变量可能的变化越多（反而跟变量具体的取值没有任何关系，只和值的种类多少以及发生概率有关），它携带的信息量就越大。对分类系统来说，类别C是变量，它可能的取值是C1，C2，Cn，而每一个类别出现的概率是P(C1)，P(C2)，P(Cn)，因此n就是类别的总数。此时分类系统的熵就可以表示为：文本分类系统的作用就是输出一个表示文本属于哪个类别的值，而这个值可能是C1，C2，Cn，因此这个值所携带的信息量就是上式中的这么多。结论：ID3 信息量大小的度量 Gain（S，A）是属性A在集合S上的信息增益Gain（S，A）= Entropy（S） -Entropy（S，A）Entropy（S，A）=（|Sv|/|S|）* Entropy（Sv）是属性A的所有可能的值v,Sv是属性A有v值的S子集|Sv|是Sv 中元素的个数；|S|是S中元素的个数。用P(Ci,Sv)表示Sv中包含有属于分类Ci的样本概率，I(Ci,Sv)表示子集合Sv中属于分类Ci的样本信息，则熵 Entropy（Sv）=I(Ci,Sv)，求和发生在C=c1,c2,.,Ck上。示例： 分类C标签为C1=买,C2=不买。则I(S)=I(C1)+I(C2)。样本中买的人数为641，不买的人数为383，总样本为1024。则可以算的熵I(S)=I(C1)+I(C2)=I(641,383)=0.9537 现在考虑属性年龄Y=青，中，老。I(S(Y=青)=I(买=64+64，不买=64+64+128)=I(128,256)=0.9183，同样求得I(S(Y=中)=0，I(S(Y=老)=0.9157. 所以I(S，Y)=I(S)-I(S,Y)=0.9537-（|Sv|/|S|）*I（Sv）=0.9537-（384/1025*0.9183+0.25*0+0.375*0.9157）=0.2660。 收入信息增益=0.9537-0.9361=0.0176 学生信息增益=0.9537-0.7811=0.1726 信誉信息增益=0.9537-0.9048=0.0453构造了第一步图如下： 对于青年分支，在S(Y=青)样本空间条件下计算收入，学生和信誉属性的信息增益。如果选择收入作为节点分高、中、低，则： I(0,128)=0 收入高的青年人中，有0个买，128个不买比例: 128/384=0.3333I(64,128)=0.9183比例: 192/384=0.5I(64,0)=0比例: 64/384=0.1667Gain(收入) =I(128, 256)- E(收入)=0.9183 0.4592 = 0.4591。特别需要注意的是，I(128,256)已经在前面被计算过了，因此需要，实际上不需要再计算了。理解图： 一个父亲节点，被分解为了k个子节点。节点中n表示样本数，I(n)表示这n个样本中，根据分类标签得到的熵I(n)=I(c1,c2,.ch)，其中ci表示n个样本中属于分类ci的样本数。该图所表示的属性信息增益为I(n)-ni/n*I(ni)。 属性的增益率为：属性的内在信息为：上公式中Si表示属性A取值为i得到的S的子集Si。信息增益率为：gainRatio(S,A)=Gain(S,A)/IntrinsicInfo(S,A)属性的增益率比增益有更高的好处，因为是对信息增益做了归一化处理。对于属性增益来说，其值通常和分支数有很大关系，分支越多的，增益值越大。另外一个示例： 首先进行预处理，方法是： 另外一个示例：判断电信客户是否流失的示例， step 1:属性删除：将有大量不同取值且无概化操作符的属性或者可用其它属性来代替它的较高层概念的那些属性删除。比如客户信息表中的用户标识、身份证号码等，它们的取值太多且无法在该取值域内找到概化操作符，应将其删除，得到表1。 表1中的其他无用属性就是需要删除的属性。 step 2：属性概化，用属性概化阈值控制技术沿属性概念分层上卷或下钻进行概化。文化程度分为3类：W1初中以下(含初中)，W2高中(含中专)，W3大学(专科、本科及以上)；职业类别：按工作性质来分共分3类：Z1一Z3；缴费方式：托收：T1,营业厅缴费：T2,充值卡：T3。 step 3：连续型属性概化为区间值，表中年龄、费用变化率和在网时间为连续型数据，由于建立决策树时，用离散型数据进行处理速度最快，因此对连续型数据进行离散化处理，根据专家经验和实际计算信息增益，在“在网时长”属性中，通过检测每个划分，得到在阈值为5年时信息增益最大，从而确定最好的划分是在5年处，则这个属性的范围就变为5：H1,H2。而在“年龄”属性中，信息增益有两个锋值，分别在40和50处，因而该属性的范围变为40-50即变为青年，中年，老年：N1,N2,N3；费用变化率：指（当月话费近3个月的平均话费）/近3个月的平均话费）0，F1:=y,Yy),y,令y=2668变化。 最终得到的表格如表2所示： 最终得到的决策树为： 在图中，NO表示客户不流失，YES表示客户流失。从图可以看出，客户费用变化率为100%的客户肯定已经流失；而费用变化率低于30%的客户；即每月资费相对稳定的客户一般不会流失，费用变化率在30%99%的客户有可能流失，其中年龄在4050岁之间的客户流失的可能性非常大，而年龄低于40岁的客户，用充值卡缴费的客户和在网时间较短的客户容易流失；年龄较大的客户，则工人容易流失。 关于连续变量的阈值确定方法： 很简单，把需要处理的样本（对应根节点）或样本子集（对应子树）按照连续变量的大小从小到大进行排序，假设该属性对应的不同的属性值一共有N个，那么总共有N-1个可能的候选分割阈值点，每个候选的分割阈值点的值为上述排序后的属性值链表中两两前后连续元素的中点，那么我们的任务就是从这个N-1个候选分割阈值点中选出一个，使得前面提到的信息论标准最大。举个例子，对于Golf数据集，我们来处理温度属性，来选择合适的阈值。首先按照温度大小对对应样本进行排序如下那么可以看到有13个可能的候选阈值点，比如middle64,65, middle65,68.,middle83,85。那么最优的阈值该选多少呢？应该是middle71,72，如上图中红线所示。为什么呢？如下计算：通过上述计算方式，0.939是最大的，因此测试的增益是最小的（前面讲到的是采用最大的，根据个人理解应该是采用最小的）。（测试的增益和测试后的熵是成反比的，这个从后面的公式可以很清楚的看到）。根据上面的描述，我们需要对每个候选分割阈值进行增益或熵的计算才能得到最优的阈值，我们需要算N-1次增益或熵（对应温度这个变量而言就是13次计算）。能否有所改进呢？少算几次，加快速度。答案是可以该进，如下图该图中的绿线代表可能的最优分割阈值点，根据信息论知识，像middle72,75（红线所示）这个分割点，72,75属于同一个类，这样的分割点是不可能有信息增益的。（把同一个类分成了不同的类，这样的阈值点显然不会有信息增益，因为这样的分类没能帮上忙，减少可能性）决策树研究问题 理想的决策树有三种： (1)叶子结点数最少； (2)叶子结点深度最小； (3)叶子结点数最少且叶子结点深度最小。 然而，洪家荣等人已经证明了要找到这种最优的决策树是NP难题。因此，决策树优化的目的就是要找到尽可能趋向于最优的决策树。 ID3决策树算法增长树的每一个分支的深度，直到恰好能对训练样例比较完美地分类。实际应用中，当数据中有噪声或训练样例的数量太少以至于不能产生目标函数的有代表性的采样时，该策略可能会遇到困难。在以上情况发生时，这个简单的算法产生的树会过渡拟合训练样例（过渡拟合：Over Fitting）. 过度拟合的定义：对于一个假设h，当存在其它的假设对训练样例的拟合比它差，但事实上在实例的整个分布上（包含训练集合以外的实例）表现得却更好时，则称该假设过度拟合训练样例。对学习算法是否成功的真正测试是看它对于训练中未见到的数据的执行性能。训练过程应该包含训练样本和验证样本。验证样本用于测试训练后的性能。如果验证结果差，则需要考虑采用不同的结构重新进行训练，例如使用更大的样本集，或者改变从连续值到离散值得数据转换等。通常应该建立一个验证过程，在训练最终完成后用来检测训练结果的泛化能力。 一般可以将分类模型的误差分为：1、训练误差（Training Error）；2、泛化误差（Generalization Error）。训练误差是在训练记录上误分类样本比例； 泛化误差是模型在未知记录上的期望误差；一个好的模型不仅要能够很好地拟合训练数据，而且对未知样本也要能够准确地分类。一个好的分类模型必须具有低的训练误差和泛化误差。因为一个具有低训练误差的模型，其泛化误差可能比具有较高训练误差的模型高。（训练误差低，泛化误差高，称为过渡拟合）解决过度拟合的手段： 1） 及早停止树增长； 2） 后修剪法。1） 及早停止树增长 由于决策树学习要从候选集合众选择满足给定标准的最大化属性，并且不回溯，也就是我们常说的爬山策略，其选择往往会是局部最优而不是全局最优。树结构越复杂，则过渡拟合发生的可能性越大。因此，要选择简单的模型。 Occan法则（又称Occan剃刀 Occan Razor）:具有相同泛化误差的两个模型，较简单的模型比复杂的模型更可取。2）后修剪法（后剪枝法） 在训练过程中允许对数据的过渡拟合，然后再对树进行修剪该方法称为后剪枝法。验证集合 对以上的决策树通过上面的验证集合进行测试，发现其有5个错分类。首先将决策树转化为规则：再统计规则的精度：然后对规则进行修剪：最后得到最终的规则集合为：还要对规则集合进行排序：C4.5 分