决策树会有哪些特性?

决策树(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 条评论
登录 后参与评论

相关文章

来自专栏量子位

如何捕获一只彩色卓别林?黑白照片AI上色教程很友好 | 哈佛大触

1112
来自专栏小小挖掘机

深度强化学习-Actor-Critic算法原理和实现

在之前的几篇文章中,我们介绍了基于价值Value的强化学习算法Deep Q Network。有关DQN算法以及各种改进算法的原理和实现,可以参考之前的文章: 实...

4134
来自专栏人工智能LeadAI

用 LSTM 做时间序列预测的一个小例子

问题:航班乘客预测 数据:1949 到 1960 一共 12 年,每年 12 个月的数据,一共 144 个数据,单位是 1000 下载地址(https://...

3045
来自专栏大数据挖掘DT机器学习

R语言处理缺失数据的高级方法

主要用到VIM和mice包 [plain] view plain install.packages(c("VIM","mice")) 1.处理缺失值的步骤 ...

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

R语言建立回归分析,并利用VIF查看共线性问题的例子

使用R对内置longley数据集进行回归分析,如果以GNP.deflator作为因变量y,问这个数据集是否存在多重共线性问题?应该选择哪些变量参与回归? 答: ...

3478
来自专栏AI科技大本营的专栏

技术详解 | 如何用GAN实现阴影检测和阴影去除?

作者 | 江亦凡 最近两天刚看到的论文,写一篇文章当做笔记,论文原文取自https://arxiv.org/abs/1712.02478 继去年底Phillip...

3305
来自专栏杨熹的专栏

用深度神经网络处理NER命名实体识别问题

本文结构: 什么是命名实体识别(NER) 怎么识别? ---- cs224d Day 7: 项目2-用DNN处理NER问题 课程项目描述地址 ---- 什么是...

42311
来自专栏机器学习原理

我的机器学习概率论篇排列 组合古典概率联合概率条件概率全概率公式贝叶斯公式独立事件随机变量离散型随机变量连续型随机变量期望和方差三个基本定理参数估计

前言: 概率论的理解有些抽象,掌握概率论的方法,用实际样本去无限接近真实,熟练掌握并且使用一些最基本的概念是前提,比如,均值,方差 排列 组合 计算各种...

3396
来自专栏目标检测和深度学习

如何从零开发一个复杂深度学习模型

深度学习框架中涉及很多参数,如果一些基本的参数如果不了解,那么你去看任何一个深度学习框架是都会觉得很困难,下面介绍几个新手常问的几个参数。 batch 深度学习...

4167
来自专栏机器之心

教程 | 详解如何使用Keras实现Wassertein GAN

选自Deeply Random 机器之心编译 参与:晏奇、李泽南 在阅读论文 Wassertein GAN 时,作者发现理解它最好的办法就是用代码来实现其内容。...

36910

扫描关注云+社区