机器学习之决策树(Decision Tree)详解程序员


1. 什么是决策树

     决策树又称为判定树,decision tree。 决策树与平时我们常画的流程图十分相似。

     根据数据:

      机器学习之决策树(Decision Tree)详解程序员

         可以创造出类似以下的决策树:  

            机器学习之决策树(Decision Tree)详解程序员


        每一个内部结点表示对某一个属性的测试(流程图中的菱形), 每个分支的产生代表一个属性的一个可取值,而树叶结点表示类的分布。

         

          应用最广的分类算法之一,模型学习的结果是一棵决策树,这棵决策树可以被表示成多个if-else的规则。决策树实际上是将空间用超平面进行划分的一种方法,每次分割的时候,都将当前的空间一分为二,比如说下面的决策树:

机器学习之决策树(Decision Tree)详解程序员

这样使得每一个叶子节点都是在空间中的一个不相交的区域。学习得到如上这棵决策树之后,当输入一个待分类的样本实例进行决策的时候,我们就可以根据这个样本的两个特征(x, y)的取值来把这个样本划分到某一个叶子节点,得到分类结果了,这就是决策树模型的分类过程,决策树的学习算法有ID3算法和C4.5算法等。

2. 熵(entropy)

     详见 http://blog.csdn.net/leiting_imecas/article/details/52917077 

     信息获取量(Information Gain),又称为信息增益

     数据D中,A的信息获取量:Gain(A) = info(D) – info_A(D).  即没有A的信息-有A的信息。如果使用熵作为信息的多少判断标准,则信息增益是熵的差值。


3. 决策树的几个代表

     根据选择属性结点的方法不同,决策树有多种类型

   (1) ID3 —— 使用信息增益作为属性选择的度量方法

             上面的数据整体的信息熵中, 

                     机器学习之决策树(Decision Tree)详解程序员

              有age的信息熵:      

                    机器学习之决策树(Decision Tree)详解程序员

            所以 Gain(age) = Info(D) – Info_age(D) = 0.246。类似的,Gain(income)=0.029, Gain(student)=0.151, Gain(credit_rating) = 0.048。可见age这一个属性提供了最大的信息获取量,所以将age作为树的第一个结点

             选取age作为第一个结点后,按照age的value创造子结点。子节点循环上面的判断过程。注意,子节点不再判断age这一个属性,即子几点不再判断父结点及祖结点。

             ID3容易过拟合。 避免过拟合的方法:1.不做没必要的分裂 2. 剪枝

        (2)C4.5 ——使用 gain ratio作为属性选择度量方法

                信息增益: 机器学习之决策树(Decision Tree)详解程序员,  其中S是所有样本,|S|是样本数量,A是信息A,H(S)是熵。Sv是依据A分出的子样本,|Sv|是子样本数量。即没有A的熵 – A的所有子集的熵之和

                机器学习之决策树(Decision Tree)详解程序员, 反应子样本数量引起的不确定性,即子集越多,splitEntropy 越大

               则 机器学习之决策树(Decision Tree)详解程序员。       分裂属性时,希望增益大、子集数量小。可以降低过拟合

        (3)CART —— 使用gini index作为属性选择度量方法


4. 树剪枝 ,避免overfitting

       剪枝,顾名思义就是指除去部分树枝。

     (1)先剪枝     构造树过程中,达到一定情况就停止。例如,子节点的类的纯度达到一定的值,就不再继续构造

     (2)后剪枝    先构造完树,根据一定的规则(例如结点纯度)再剪枝。


5. 决策树的优缺点

    优点:直观

    缺点:处理连续变量不好,规模性不好; 只能线性分割数据; 贪婪算法(可能找不到最好的树)


代码参考: https://github.com/liuleigit/ML_tutorial/tree/master/DecisionTree

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/7420.html

(0)
上一篇 2021年7月17日
下一篇 2021年7月17日

相关推荐

发表回复

登录后才能评论