决策树会有哪些特性?

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

相关文章

来自专栏语言、知识与人工智能

基于深度学习的FAQ问答系统

| 导语 问答系统是信息检索的一种高级形式,能够更加准确地理解用户用自然语言提出的问题,并通过检索语料库、知识图谱或问答知识库返回简洁、准确的匹配答案。相较于...

8.8K10
来自专栏贾老师の博客

【笔记】ejoy2d —— matrix

994
来自专栏利炳根的专栏

学习笔记CB001:NLTK库、语料库、词概率、双连词、词典

聊天机器人知识主要是自然语言处理。包括语言分析和理解、语言生成、机器学习、人机对话、信息检索、信息传输与信息存储、文本分类、自动文摘、数学方法、语言资源、系统评...

25210
来自专栏书山有路勤为径

第四天-模型选择

每次将不同的包用作测试集,剩下的作为训练集,然后求结果的平均值,得到最终模型。

421
来自专栏人工智能

利用神经网络算法的C#手写数字识别

尽管在过去几年已经有许多系统和分类算法被提出,但是手写识别任然是模式识别中的一项挑战。

1.1K11
来自专栏月色的自留地

从锅炉工到AI专家(9)

1746
来自专栏深度学习之tensorflow实战篇

r语言ggplot2包学习笔记(上代码+注释)

#ggplot2学习笔记##第一节:尝试ggplot library(ggplot2) #使用的是R内置数据(mpg) qplot(displ,hwy,data...

2185
来自专栏素质云笔记

相似性︱python+opencv实现pHash算法+hamming距离(simhash)(三)

pHash跟simhash很多相近的地方。一个是较多用于图像,一个较多用于文本。 之前写关于R语言实现的博客: R语言实现︱局部敏感哈希算法(LSH)解决文...

6135
来自专栏大数据文摘

手把手:使用OpenCV进行面部合成— C++ / Python

25612
来自专栏章鱼的慢慢技术路

Direct3D 11 Tutorial 3: Shaders and Effect System_Direct3D 11 教程3:着色器和效果系统

在上一个教程中,我们设置了一个顶点缓冲区并将一个三角形传递给GPU。 现在,我们将逐步完成图形管道并查看每个阶段的工作原理。 将解释着色器和效果系统的概念。

461

扫码关注云+社区