1. 什么是决策树
决策树又称为判定树,decision tree。 决策树与平时我们常画的流程图十分相似。
根据数据:
可以创造出类似以下的决策树:
每一个内部结点表示对某一个属性的测试(流程图中的菱形), 每个分支的产生代表一个属性的一个可取值,而树叶结点表示类的分布。
应用最广的分类算法之一,模型学习的结果是一棵决策树,这棵决策树可以被表示成多个if-else的规则。决策树实际上是将空间用超平面进行划分的一种方法,每次分割的时候,都将当前的空间一分为二,比如说下面的决策树:
这样使得每一个叶子节点都是在空间中的一个不相交的区域。学习得到如上这棵决策树之后,当输入一个待分类的样本实例进行决策的时候,我们就可以根据这个样本的两个特征(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 —— 使用信息增益作为属性选择的度量方法
上面的数据整体的信息熵中,
有age的信息熵:
所以 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作为属性选择度量方法
信息增益: , 其中S是所有样本,|S|是样本数量,A是信息A,H(S)是熵。Sv是依据A分出的子样本,|Sv|是子样本数量。即没有A的熵 – A的所有子集的熵之和
, 反应子样本数量引起的不确定性,即子集越多,splitEntropy 越大
则 。 分裂属性时,希望增益大、子集数量小。可以降低过拟合
(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