Decision tree入门

ist707-week5

Posted by renjie on February 14, 2020


Decision Tree

707-5

算法

树的分叉方式: 两分叉或者多分叉

1.Categorical Attributes

2.Continuous Attributes

树选择哪个属性作为node?

Entropy (熵)

类似理工科中的熵,形容混乱的程度

measure the impurity of a data set (Noise Level)

一半一半的时候熵值为1, 全为某个值的时候熵为0(极限)

Information Gain (IG) -信息增益

A statistical measure that measures how well a given attribute separates the training examples according to their target classification. (Mitchell,1990)

ig意义就是经过分支后,熵的变化程度

树的分支就是选择最高ig的分支方案, 直到pure为止,或者达到某一设定值,或者满足最大分支数

总熵-分支的熵的和即为ig的值

Gain Ratio -信息增益率

Impurity measures tend to favor attributes that have a large number of distinct values

按照信息增益选择,总是会倾向于选择分支多的属性,这样会是的每个子集的信息熵最小。例如给每个数据添加一个第一无二的id值特征,则按照这个id值进行分类是获得信息增益最大的,这样每个子集中的信息熵都为0,但是这样的分类便没有任何意义,没有任何泛化能力,类似过拟合。

因此使用一个值SplitInfo来作为分组过多的惩罚,讲ig除以SplitInfo的值定为Gain Ratio

Gini impurity -基尼不纯度

这里引用化学狗码砖的日常的知乎回答

基尼系数,也就是另外一种作为分离依据的公式,应用在其他树算法中

Decision Tree 的解释

看作if else 的嵌套进行理解

Decision Tree 的应用范围:非线性关系

overfitting -过拟合

模型越复杂,越容易过拟合,所以应该选择适当的树大小,也是一种bias和variance的trade-off

  • Prepruning -预剪枝

该方法是在建立决策树的过程中,判断当决策树的node满足一定条件(比如当树的深度达到事先设定的值,或者当该node下的样例个数小于等于某个数)时,不在继续建立子树,所以也叫Early stopping。

选择合适的threshold很难

  • Post-pruning -后剪枝

先建立完整的决策树,然后通过一定的算法,将某个非leaf node设为leaf node(即将该node下的子树丢弃)实现pruning。

使用非训练集的数据来决定怎么剪

小结

  • 树的优点:预测快, 可解释性强, 抗噪声强

  • 树的缺点:容易过拟合,不适用于太多class的分类, 计算废资源

作业使用weka的J48算法,这里不再描述。