2017-11-28
机器学习-决策树

• 分类: ml • 标签: ml

决策树

决策树由 Leo Breiman(1928-2005) 提出。

决策树一个重要任务是为了发现数据中所蕴含的知识信息，并提取出一系列的规则，这些规则也就是树结构的创建过程就是机器学习的过程。决策树算法主要是指决策树在创建过程中进行树分裂(划分数据集)的时候选取最优特征的算法，他的主要目的就是要选取一个特征能够将分开的数据集尽量的规整，也就是尽可能的纯。最大的原则就是：将无序的数据变得更加有序。

decision-tree

基本概念

常见算法

CART 1984

在数据挖掘中，决策树主要有两种类型:

分类树的输出是样本的类标。
回归树的输出是一个实数 (例如房子的价格，病人呆在医院的时间等)。

术语分类和回归树 (CART) 包含了上述两种决策树, 最先由Breiman 等提出。分类树和回归树有些共同点和不同点—例如处理在何处分裂的问题。分类回归树(CART,Classification And Regression Tree)也属于一种决策树，之前我们介绍了基于ID3和C4.5算法的决策树。这里只介绍CART是怎样用于分类的。

分类树——先说分类树，我们知道C4.5分类树在每次分枝时，是穷举每一个feature的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的熵最大的feature和阈值（熵最大的概念可理解成尽可能每个分枝的男女比例都远离1:1），按照该标准分枝得到两个新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。
回归树——回归树总体流程也是类似，不过在每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差——即（每个人的年龄-预测年龄）^2 的总和 / N，或者说是每个人的预测误差平方和除以 N。这很好理解，被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最靠谱的分枝依据。分枝直到每个叶子节点上人的年龄都唯一（这太难了）或者达到预设的终止条件（如叶子个数上限），若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。若还不明白可以Google “Regression Tree”。

ID3 1986

pass

信息熵

X如果可以取三个值：x1,x2,x3,概率分别为p1,p2,p3。
那么-log(p1),-log(p2),-log(p3)相应称为x1,x2,x3的自信息，代表了它们各自的不确定性（信息论）。X的熵指的是X的所有取值的期望，H(X)可以理解为平均值，那X总的不确定性其实也可以用3H(X)来表示。
题中N个结点，每个Nt结点都可以理解为这样的X，那么整棵树的不确定性（损失）就是所有叶结点的总熵NtHt(T)的和，而不是平均值Ht(T)的和

2017-11-28
机器学习-决策树

决策树

基本概念

常见算法

CART 1984

ID3 1986

信息熵

信息增益

C4.5 1993——分类决策树

信息增益比

参考

2017-11-28 机器学习-决策树

决策树

基本概念

常见算法

CART 1984

ID3 1986

信息熵

信息增益

C4.5 1993——分类决策树

信息增益比

参考

2017-11-28
机器学习-决策树