决策树

什么是决策树？解决什么问题？

基于树结构进行决策，希望从给定数据训练数据集中学得一个模型用以对新示例进行分类，这个把样本分类的任务，即对问题的“决策”或判定过程。
决策过程的结论对应了我们希望的判定结果。

决策过程中提出的每个判定问题都是对某个属性的测试
每个测试结果或是导出最终结论，或者导出进一步的判定问题。
并且其考虑范围是在上一次决策结果的限定范围之内。

一棵决策树包含一个根结点、若干个内部结点和若干个叶节点。
叶节点对应决策的结果，其他每个节点对应于一个属性的测试，每个结点包含了样本集合根据属性测试的结果被划分到子结点中。
根节点包含样本全集。根结点到每个叶结点的路径对应了一个判定测试序列。
决策树学习目的是为了产生一棵泛化能力强的决策树。

度量样本集合纯度的指标。信息熵越大，不确定性越大，信息越不纯。
决策树要选择什么属性作为根结点呢？

信息熵是针对整个样本集合的，不按属性划分。
条件熵是我们根据划分的条件求出不同子集样本的信息熵。结果越纯，则条件熵越小。
条件熵是各个子集的信息熵基础上乘上权重。(子集与总样本的总比)

那信息熵又是怎么度量纯度的呢？
在已知属性(特征)a的取值后y的不确定性减少的量，也叫纯度的提升。信息论里面的信息熵减去信息论里面的条件熵便是信息增益。

以信息增益为准则来划分属性的决策树就叫ID3决策树。以信息增益最大的属性作为最优的划分属性。

信息增益准则对取值数目过多的属性有所偏好。对一个所有值都不同的属性，信息增益率很大，但是该属性一般是无意义的。为了解决这个问题，引入了信息增益率，即对随机变量可取值过多的进行平衡。

在ID3决策树基础上做的改进，使用“增益率”代替“信息增益”。
但是又对可取值数目较少的属性有所偏好，所以C4.5算法不是直接选择增益率最大的候选划分属性，而是启用启发式的：从候选划分属性中找出信息增益高于平均水平的，在从中选择增益率最高的。

从样本集合D中随机抽取两个样本，其类别标记不一致的概率。基尼值越小，碰到异类的概率就越小，纯度就越高。
(类比信息熵)

按某个属性条件划分后的子集的纯度。
(类比条件熵)

选择基尼指数最小的属性作为最优划分属性。
构造的是二叉树，对取值划分有要求。
问题：为什么取划分点？

ID3，C4.5和CART决策树做特征选择都是选择一个最优的特征来做分类决策，而分类决策更加准确可能是由多个变量特征来决定，这样多变量的决策树，非叶子结点不再是对某个属性，而是对属性的线性组合进行测试。
(暂时未做深究)

度量样本纯度的都可以用到决策树中来。
属性值有离散和分类类型取值划分。ID3不支持连续值和缺失值处理，C4.5和CART可以。
信息熵和条件熵一个从整个集合上考虑，一个上从所分得子集计算。(基尼值和基尼指数类比)
ID3决策树通过信息熵来判定样本的纯度，根据信息增益来进行划分结点。C4.5决策树是在ID3决策树的基础上提出信息增益率，用启发式方式，从候选划分属性中选择信息增益高于平均水平的属性，再从中选增益率最高的。CART决策树采用简单二叉树(ID3和C4.5则可能是多叉数)，可以做分类和回归模型。
ID3和C4.5和CART都是单变量决策树。