决策树会有哪些特性?

决策树(Decision Tree)是机器学习中最常见的算法, 因为决策树的结果简单,容易理解, 因此应用超级广泛, 但是机器学习的专家们在设计决策树的时候会考虑哪些特性呢? 本文根据已有的决策树来分析, 一个想象中万能的决策树会有哪些变化?在这以前, 先总结下使用决策树的优缺点: 优点 天然的可解释性。 这是决策树最大的优点了。 可解释性有两方面的考虑。 一方面, 树结构的理解不需要机器学习专家来解读。 另一方面, 很容易转化成规则。可以处理缺失值(missing), 字符型(nominal), 数值型(numeric)等数据类型。非参数模型(non-parametric)。 没有复杂的参数设置,谁跑效果都相对一样。对相关(Correlation)属性能够比较好的处理。运算速度相对比较快。 缺点 最大的缺点就是很容易过拟合。 导致实际预测的效果并不高。决策树中,重复的部分过多难以概括, 譬如对于 ( F1 && F2 ) || ( F3 && F4 ) 的表达(如下图,划圈的部分重复), 决策树就有很大的重复。不适合处理高维数据, 当属性数量过大的时候, 部分决策树就不太适用了。对异常值(Outlier)过于敏感, 很容易导致树的结构的巨大的变换。泛化(Generalization)能力太差, 对于没有出现过的值几乎没有办法。 决策树们 CART(Classification and Regression Trees)是Breiman 提出的一个二叉树, 采用贪心的递归分支方法进行生长。 CART不仅可以用来分类,也可以做回归。 在CART里面首次使用了Missing的替代划分(surrogate splits)的技巧。 CART树首先提出并使用了Variable Importance(VI)的概念, 这是个很牛的衡量属性特征权重的概念。需要注意的是VI是随着树的变化而变化的, 所以不同树之间的VI是不能相互比较的, 细节可以参考 (https://www.salford-systems.com/videos/tutorials/how-to/variable-importance-in-cart)。另外CART也是最早引入Cross Validation来进行Pruning的。 ID3(Iterative Dichotomiser) 是C4.5的一个早期版本, 因此在后面说明中不会提及。 ID3不能处理连续值, 没有剪枝, 不能处理缺失(Missing)。但是ID3提出了很好的Information Gain的框架。 C4.5 是Quinlan提出的一系列算法的流传最广的一个。前续版本有ID3, 后续还有C5.0, 但是C5.0是商业版本的。 C4.5在ID3的基础上做了很多重大改进, 其中一个就是ID3不能处理连续数值的情况, 而C4.5通过阈值自动把连续变量分成两部分来处理。 AID(Automatic Interaction Detection) 是CHAID的早期版本,或者说一个更一般的方法, 因此在后面说明中不会提及。 AID首次提出利用F-Test来进行选择和划分,进而引入Interaction的概念。 CHAID(Chi—squared Automatic Interaction Detection)是AID的后续版本, 在认识的AID的偏差性后, 利用χ2-Test和F-Test结合的方式来选择属性,来降低偏差。 同时CHAID也意识到二叉树的复杂性, 运行多叉树合并产生更小的决策树。 FACT(Fast Algorithm for Classification Trees) 是QUEST的一个早期版本, 因此在后面说明中不会提及。FACT讲符号的属性全部转换成数值型的, 然后,利用LDA(linear discriminant analysis)来将属性进行分割的。 它进行特征选择的时候, 利用ANOVA (analysis of variance)的F-Test, 优先选择最大的F Ratio的属性进行划分。 QUEST(Quick,Unbiased,Effficient,Statistical Tree)是FACT的后续版本, 并且将FACT的基于LDA(linear discriminant analysis)的划分, 修改成了基于QDA(quadratic discrimination analysis)的划分。 并且在特征选择的时候, 连续特征和FACT一样基于F-Test, 但是离散特征是基于χ2-Test的。 在QUEST中Missing处理比较简单,就是用插值(Imputation)。 CRUISE (Classification Rule with Unbiased Interaction Selection and Estimation)是QUEST的后续算法, 除了继承了QUEST的F-Test(连续值)和χ2-Test(离散值)的划分, 还引入了叫2D的特征划分方式。 2D的划分中, 两两属性之间都要进行5次测试(2次marginal tests和3次interaction tests). 并且划分也有改变, 先进行Box-Cox Transformation预处理, 再进行LDA划分。 另外还有一个重大改变是CRUISE经过Box-Cox变换后,可以将一个属性划分成多个分支(多叉树)。 CRUISE采用了CART树处理Missing的Surrogate Splitting办法。 GUIDE(Generalized,Unbiased,Interaction Detection and Estimation)GUIDE更像一个QUEST 和CART树的一个综合体的Bagging升级版。 它继承了QUEST和CRUISE的特征划分方式, 但是加入了Variable Importance的排序和按阈值选择部分特征集。 并且GUIDE和CART类似也可以用作Regression。 由于受到Random Forest成功的影响, GUIDE自带了Bagging的两种机制(Random Forest 和Extremely Randomized Trees)。 但是GUIDE里面Missing没有采用CART的方式, 而是把Missing看成一类特殊值,但是同时根据数据类型,具有插值的mean(连续型),或者是常量(符号型)。 MARS(Multivariate Adaptive Regression Splines)是Frieman提出的一个多变量回归的线性样板。 基于多个Hinge Function把不同变量的回归部分拼接起来。 因此来说, MARS与传统的树还是差异蛮大的,因此在后面说明中不会提及。 但是这个过程中Friedman应用了Stepwise Regression的思想。这或许是他后来提出Gradient Boosting方法的一个基础。 结构特征 既然是树,树是二叉还是多叉的呢? 二叉:CART, QUEST, GUIDE 二叉或者多叉:C4.5,CHAID, CRUISE 是一颗树还是多棵树? 多颗树:GUIDE (两种Bagging方式) 生长特征在树生长过程中要判断按属性来分, 在这个过程有几个指标会带来变化。 参考一个属性还是多个属性进行划分?只支持一个属性还是支持多个属性? 一个属性: CART C4.5 CHAID QUEST CRUISE 多个属性: CART QUEST CRUISE 计算属性的什么值? 信息增益(Information Gain)的计算方式? Gini : CART Entropy: C4.5 Misclassification Error : CART F-Test / χ2-Test : QUEST CRUISE 是否对属性按重要性排序(Variable Importance)?有重要性排序:CART GUIDE 没有重要性排序: C4.5 CHAID QUEST CRUISE 连续值如何划分? Information Gain (Ratio) based Threshold: C4.5 Twoing Criteria (类似Information Gain):CART LDA/QDA based Threshold:QUEST CRUISE Adjusted p value:CHAID 数据特征是否能够处理Missing值? 如果能, 是如何处理的? 不能处理: -- 插值法(Imputation): QUEST, CRUISE 替代法(Alternate/Surrogate Splits):CART, CRUISE 缺失值单独分支(Missing value branch):CHAID, GUIDE 概率权重(Probability weights): C4.5 数值型和符号型(类别型)属性值是如何计算的? 阈值来划分连续型:CART, C4.5, CHAID 符号型变换成数值型:QUEST, CRUISE 连续型通过Box-Cox变换:GUIDE 正则化特征 剪枝(Pruning)是决策树正则化的最重要办法。一个剪枝的方法是? (Stopping rule):CHAID (Pre-pruning):C4.5 (Cross-validation pruning):CART QUEST CRUISE 剪枝参考值得计算方式? Cost-Complexity Minimization (standard misclassification cost vs number of leaves ): CART Error-Based Pruning (Wilson’s confidence intervals): C4.5 Maximum Depth: CHAID Gini, Entropy, 和Misclassification Error的异同 这些都可以作为信息增益框架下的信息计算公式。 信息增益的框架如下: 他们的公式和曲线不一样: Gini: Entropy: Missclassification Error: 根据公式衍生有如下不同: Gini更适合连续数值变量, 而Entropy更适合符号型变量。 Gini降低最小误分率, 而Entropy具有更好的概率解释性。 Gini运算要比Entropy运算快。 但是根据实际运行情况: Gini, Entropy, 和Misclassification Error 基本一致, 一般不超过2%的区别。

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2017-10-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云霄雨霁

加权有向图----无环情况下的最短路径算法

1480
来自专栏PPV课数据科学社区

【工具】SAS 常用函数汇总

? 一、数学函数 ABS(x) 求x的绝对值。 MAX(x1,x2,…,xn) 求所有自变量中的最大一个。 MIN(x1,x2,…,xn) 求所有自变量...

2413
来自专栏ml

数据挖掘之聚类算法K-Means总结

序   由于项目需要,需要对数据进行处理,故而又要滚回来看看paper,做点小功课,这篇文章只是简单的总结一下基础的Kmeans算法思想以及实现; 正文:   ...

3618
来自专栏机器学习与自然语言处理

最大子序列和问题之算法优化

算法一:穷举式地尝试所有的可能 int maxSubsequenceSum(const int a[], int n) { int i, j, k; ...

1897
来自专栏崔庆才的专栏

自然语言处理中句子相似度计算的几种方法

1815
来自专栏图形学与OpenGL

计算机图形学(OpenGL版)书中其它代码

1022
来自专栏Spark学习技巧

最大子序列和问题之算法优化

993
来自专栏崔庆才的专栏

TensorFlow Bi-LSTM实现文本分词

本节我们来尝试使用 TensorFlow 搭建一个双向 LSTM (Bi-LSTM) 深度学习模型来处理序列标注(分词)问题,主要目的是学习 Bi-LSTM 的...

6376
来自专栏专知

【论文推荐】最新6篇机器翻译相关论文—词性和语义标注任务、变分递归神经机器翻译、文学语料、神经后缀预测、重构模型

【导读】专知内容组整理了最近六篇机器翻译(Machine Translation)相关文章,为大家进行介绍,欢迎查看! 1. Evaluating Layers...

4636
来自专栏数据结构与算法

学大伟业 国庆Day2

期望得分:30+100+0=130 实际得分:30+100+20=150 忍者钩爪 (ninja.pas/c/cpp) 【问题描述】 小Q是一名酷爱钩爪的忍者,...

4504

扫码关注云+社区