决策树会有哪些特性?

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

相关文章

来自专栏yw的数据分析

gplots heatmap.2和ggplot2 geom_tile实现数据聚类和热图plot

主要步骤 ggplot2 数据处理成矩阵形式,给行名列名 hclust聚类,改变矩阵行列顺序为聚类后的顺序 melt数据,处理成ggplot2能够直接处理的数据...

5177
来自专栏图形学与OpenGL

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

1602
来自专栏崔庆才的专栏

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

2245
来自专栏崔庆才的专栏

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

在做自然语言处理的过程中,我们经常会遇到需要找出相似语句的场景,或者找出句子的近似表达,这时候我们就需要把类似的句子归到一起,这里面就涉及到句子相似度计算的问题...

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

【工具】SAS 常用函数汇总

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

2753
来自专栏Spark学习技巧

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

1393
来自专栏null的专栏

机器学习算法实现解析——libFM之libFM的训练过程概述

本节主要介绍的是libFM源码分析的第四部分——libFM的训练。 FM模型的训练是FM模型的核心的部分。 4.1、libFM中训练过程的实现 在FM模型的训练...

50511
来自专栏软件开发 -- 分享 互助 成长

最小生成树-Prim算法和Kruskal算法

Prim算法 1.概览 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里...

57210
来自专栏锦小年的博客

复杂网络(2)--图论的基本理论-最小生成树问题

连通且不含圈的无向图称为树(tree)。树中度为1的节点称为树叶,度大于1的节点称为分支点。 若图G=(V,E)的生成子图是一棵树,则称该树为图G的生成树(...

3696
来自专栏专知

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

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

4816

扫码关注云+社区

领取腾讯云代金券