Machine Learning-经典模型之DT Learning

本篇文章整理一下decision tree learning的知识点。

下面是维基百科的定义:

Decision tree learning uses a decision tree (as a predictive model) to go from observations about an item (represented in the branches) to conclusions about the item's target value (represented in the leaves).

决策树主要分两类:

  • Classification tree analysis is when the predicted outcome is the class to which the data belongs.
  • Regression tree analysis is when the predicted outcome can be considered a real number (e.g. the price of a house, or a patient's length of stay in a hospital).

Decision tree learning is the construction of a decision tree from class-labeled training tuples. A decision tree is a flow-chart-like structure, where each internal (non-leaf) node denotes a test on an attribute, each branch represents the outcome of a test, and each leaf (or terminal) node holds a class label. The topmost node in a tree is the root node.

关于决策树有许多的算法,下面是一些经典的算法:

  • ID3 (Iterative Dichotomiser 3)
  • C4.5 (successor of ID3)
  • CART (Classification And Regression Tree)
  • CHAID (CHi-squared Automatic Interaction Detector). Performs multi-level splits when computing classification trees.
  • MARS: extends decision trees to handle numerical data better.
  • Conditional Inference Trees. Statistics-based approach that uses non-parametric tests as splitting criteria, corrected for multiple testing to avoid overfitting. This approach results in unbiased predictor selection and does not require pruning.

熵(Entropy)

度量信息的不确定性;以比特(bits)为单位;完全确定的分类,其熵为0比特;其公式为

其中,nn是样本的数量,P(xi)P(xi)是第ii个样本的概率;bb一般取2或ee或10;前面加符号是为了熵为非负数;

信息增益(information gain)

父结点熵 H(T)H(T)与子节点熵加权均值的差;应该选择信息增益最大的解释变量进行结点划分;

其中,xa∈val(s)xa∈val(s)表示解释变量aa的样本xx;{x∈T|xa=v}{x∈T|xa=v} 表示解释变量aa的值等于vv样本数量;H(x∈T|xa=v)H(x∈T|xa=v)是解释变量a的值等于vv的样本熵;

基尼不纯度(gini impurity)

在使用CART方法时,按照集合中子集标签的概率分布对集合中元素指定标签,基尼不纯度用来衡量被错误指定标签的元素被随机抽取的概率;

计算公式:假设集合共有jj个子集,tt是结点样本的子集,其中P(i|t)P(i|t)表示从结点子集中选择一个类型ii的概率;

一个栗子:

由上面的公式我们可以看出其实信息熵就是信息的期望值,所以我们可知,信息熵越越小,信息的纯度越高,也就是信息越少,在分类领域来讲就是里面包含的类别越少,所以我们可以得出,与初始信息熵的差越大分类效果越好。

我一般买苹果的时候,从外观上评判一个苹果甜不甜有两个依据:红不红 和 圆不圆。(数据如下)

计算5个苹果是好苹果的信息熵:(结果为0.970954)

按红不红和圆不圆来分类,分别计算信息熵及其信息增益:

红不红:信息熵是0.5509775,信息增益是0.419973

圆不圆:信息熵是0.8,信息增益是0.17095

显然第一种分类的信息增益较大,可以分别看下划分的结果集:

决策树构建的基本步骤:

1>> 开始,所有记录看做一个结点;
2>> 遍历每个变量的每一种分割方式(如信息增益最大、基尼不纯度差最大),找到最好的分割点;
3>> 分割成两个结点N1N1和N2N2
4>> 对N1N1和N2N2分别继续执行2-3步,直到每个结点足够纯为止;

参考文献:

1)维基百科 https://en.wikipedia.org/wiki/Decision_tree_learning

2)<机器学习笔记-05 ><scikit-learn 05>决策树 & 随机森林

https://blog.csdn.net/qq_25040013/article/details/52565414

3)机器学习笔记之信息熵、信息增益和决策树(ID3算法)

https://blog.csdn.net/zhurui_idea/article/details/54646932

4)Python3《机器学习实战》学习笔记(二):决策树基础篇之让我们从相亲说起

https://blog.csdn.net/c406495762/article/details/75663451

5)决策树算法及python实现

https://blog.csdn.net/huahuazhu/article/details/73167610?locationNum=2&fps=1

6)Scikit-learn中的决策树

http://python.jobbole.com/86911/

—End—

原文发布于微信公众号 - SAMshare(gh_8528ce7b7e80)

原文发表时间:2018-04-17

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券