决策树基础介绍

《决策树基础介绍》由会员分享，可在线阅读，更多相关《决策树基础介绍（5页珍藏版）》请在装配图网上搜索。

1、一。介绍决策树是一种分类算法。它的算法思想是：根据单一特征对类别的重要性，将特 征进行“排序”然后分类的时候，用这些“排序”的特征，高效的分类。二。算法步骤1特征选择首先，对于特征选择下面介绍三种最普通的方法，它们有许多共同之处， 差别在于对某一特征重要性的度量不一样。i-l前两者的度量跟熵有非常密切的关系，那么什么是熵呢？ 一一熵是对不确定性的度量。对于一件事情，如果它是确定性事件，则熵为0 ；如果对于这 件事情，每种可能出现的概率相同，则熵达到最大。具体的公式见上面。计算技巧：由于要计算的是信息增益最大，在划分前信息总量 infobeforeSplit() 一定的情况下，我们完全可以直接求

2、划分后信息量最小 的特性 即可。1.1 ID3以信息增益为基础，进行特征选择。其思想是：对于某一个特征，在知道该特征 后，根据类别的信息量减少的量，对特征进行排序。GainD, =H(CX)=总的爛-已知/特征时的条件爛n科=-S P(G) * 10g2(F(G) EIX =耳)- !- a1.2 C4.5如果某一个特征只含一个纯结点，这样决策树在选择属性时，将偏向于选择该属性，但这肯定是不正确(导致过拟合)的。因此有必要使用一种更好的 方法，那就是C4.5中使用的信息增益率。其考虑了分支数量和尺寸的因素，使用称为内在信息的概念。【1】内在信息，可简单地理解为表示信息分支所需要的信息量。实际上

3、可以看出，属性的重要性会随着其内在信息(IntrinsicInformation)的增大而减小。信息增益率作为一种补偿(Compensate )措施来解决信息增益所存在的问题，但是它也有可能导致过分补偿，而选择那些内 在信息很小的属性，这一点可以尝试：首先，仅考虑那些信息增益超过平均值的 属性，其次再比较信息增益。1.3 CARTGINI指数总体内包含的类别越杂乱-GINIfi数就越犬（跟燔的概念很相似）出如体温为恒温时包含哺乳类 类2个、则:ENI = 1 - （|）2 + 倂=芻体温为非丘温时包含爬行类3个、鱼娄3个两栖类2个.匚沖=1 - （歆+ （歆+ （納=篇4264所以如果按照円体

4、温為恒温和非恒温，进行划分的话，我们得到GINI的增益（类比信息増益）：GINlJGain =加誥 + 陽154915最好的划分就是任得GINI_Gain最小的划分【2】2,剪枝假如原本有1000个特征，在经过特征选择后，就是1000个特征的排序。但是实际上，后面的很多特征是没什么参考价值的，但是却还会影响分 类的结果。所以要使用剪枝，来避免过拟合。剪枝分为预剪枝和后剪枝。预剪枝就是一边生成决策树一边将没用的枝剪掉；后剪枝是生成一整颗完整数之后再剪枝。前者好处是效率高，坏处是没能从全局的角度来剪枝，容易导致剪枝过度；（该 剪枝方法尽管不是统计有效的，但是在实践中有效。【2】）后者的好处是从全局

5、最优的思路下进行剪枝，坏处是效率低、数据量少时易过拟2.1预剪枝 在构造决策树的同时进行剪枝。所有决策树的构建方法，都是在无法进一步降低 熵的情况下才会停止创建分支的过程，为了避免过拟合，可以设定一个阈值，熵 减小的数量小于这个阈值，即使还可以继续降低熵，也停止继续创建分支。但是这种方法实际中的效果并不好。【3】2.2后剪枝REP的步骤:1从底到顶，试着删除某一个节点下的子树，给该节点最大概率的分类；2,如果删除后没有降低总体的准确率，则删除该节点的子树。3,然后往树的跟节 点方向继续删除，直到都不能删除。其它如 Minimum Error Pruning(MEP)，Critical Valu

6、e Pruning(CVP)，Optimal Pruning(OPP)，Cost-Sensitive Decision Tree Pruning(CSDTP) PEP等方法。【2】反正我没看，具体要用再看。3,分类预测通过上面的两步，已经确定了最终用于分类的决策树。或者你还在郁闷，有了这 样的一颗树，又怎么进行分类呢？实际上，这棵树从根节点到叶子的每一根树枝都有一个概率，然后不断地往叶子 方向计算其概率，就可以得到每个叶子下的概率，而叶子对应的就是类别。三。优缺点优点：这个算法总的来说，还是基于一定的统计学意义，结合信息量的知识(当 然啦，像贝叶斯等其他分类算法也都有这两点，而且也很偏重这两点

7、)进行分类。 这类算法不涉及迭代优化等，所以计算复杂度不高，效率快。这个算法其实也是有一个致命的缺点：只能对离散的特征进行处理，对连续特征 效果不好(虽然连续的特征也能转变为离散的特征，但是决策树受这些处理的影 响很大，分类效果就差了)，此外，对于特征中离散值的个数也有一定的限制(其 实主要是个数多了，每个值对应的数据量就少了），容易出现纯节点，影响特征 选择的效果，最终影响分类的结果。【1 】 735169【2】数据挖掘十大经典算法https:/wizardforcel.gitbooks.io/dm-algo-top10/content/cart.html【3】http:/www.jianshu.eom/p/794d0819 9e5e