决策树算法（decision tree） （上）
一 决策树
决策树算法（decision tree既可以作为分类算法，也可以作为回归算法，同时也特别适合集成学习比如随机森林。
决策树又称为判定树，是运用于分类的一种树结构，其中的每个内部节点代表对某一属性的一次测试，每条边代表一个测试结果，叶节点代表某个类或类的分布。
决策树的决策过程需要从决策树的根节点开始，待测数据与决策树中的特征节点进行比较，并按照比较结果选择选择下一比较分支，直到叶子节点作为最终的决策结果。
二 决策树的学习过程
- 特征选择：从训练数据的特征中选择一个特征作为当前节点的分裂标准（特征选择的标准不同产生了不同的特征决策树算法）。
- 决策树生成：根据所选特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。
- 剪枝：决策树容易过拟合，需要剪枝来缩小树的结构和规模（包括预剪枝和后剪枝）。
在介绍决策树学习算法之前，我们先简单谈几个基本的概念：
1) 熵（entropy）
在信息论和概率统计中，熵是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为：
则随机变量X的熵定义为：
熵只依赖X的分布，和X的取值没有关系，熵是用来度量不确定性，当熵越大，概率说X=xi的不确定性越大，反之越小，在机器学期中分类中说，熵越大即这个类别的不确定性更大，反之越小，当随机变量的取值为两个时，熵随概率的变化曲线如下图：
当p=0或p=1时，H(p)=0,随机变量完全没有不确定性，当p=0.5时，H(p)=1,此时随机变量的不确定性最大。
条件熵（conditional entropy）
：表示在一直随机变量X的条件下随机变量Y的不确定性度量。
2) 信息增益（information gain）
信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
特征A对训练数据集D的信息增益g(D, A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即
g(D, A)=H(D)-H(D|A)
信息增益大的特征具有更强的分类能力。
3) 信息增益比（information gain ratio）
信息增益 vs 信息增益比
之所以引入了信息增益比，是由于信息增益的一个缺点。那就是：信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项，解决了这个问题。
4) 基尼指数（gini index）
基尼指数Gini(D)表示集合D的不确定性，基尼指数越大，样本集合的不确定性也就越大，这一点与熵相似。
Gini 指数表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是，基尼指数是为了最小化误分类的概率。
Gini 指数 vs 熵
既然这两个都可以表示数据的不确定性，不纯度。那么这两个有什么区别那？
Gini 指数的计算不需要对数运算，更加高效；
Gini 指数更偏向于连续属性，熵更偏向于离散属性。
决策树小结
- 决策树学习的目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。
- 决策树学习的本质：从训练集中归纳出一组分类规则，或者说是由训练数据集估计条件概率模型。
- 决策树学习的损失函数：正则化的极大似然函数
- 决策树学习的测试：最小化损失函数
- 决策树学习的目标：在损失函数的意义下，选择最优决策树的问题。
决策树原理和问答猜测结果游戏相似，根据一系列数据，然后给出游戏的答案。
reference：