机器学习——决策树和随机森林
决策树（decision tree）是一种基本的分类与回归方法，决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布，其主要优点是模型具有可读性，分类速度快。决策树学习通常包括三个步骤：特征选择，决策树的生成和决策树的修剪。而随机森林则是由多个决策树所构成的一种分类器，更准确的说，随机森林是由多个弱分类器组合形成的强分类器。
熵
熵 (entropy) 这一词最初来源于热力学。1948年，克劳德·爱尔伍德·香农将热力学中的熵引入信息论，所以也被称为香农熵 (Shannon entropy)，信息熵 (information entropy)。
信息熵
信息是一个很抽象的概念，泛指人类社会传播的一切内容。引入“信息熵”概念是为了将信息量化。一条信息的信息量大小和它的不确定性有直接的关系，若要弄清楚一件非常不确定的事，就需要了解大量的信息。相反，若对某件事已经有了较多的了解，那么就不需要太多的信息就能把它搞清楚。所以，从这个角度我们可以认为，信息量的度量就等于不确定性的多少。
就被称为随机变量的熵，它是表示随机变量不确定的度量，是对所有可能发生的事件产生的信息量的期望。
随机变量的取值个数越多，状态数也就越多，信息熵就越大，混乱程度就越大。当随机分布为均匀分布时，熵最大。
将一维随机变量分布推广到多维随机变量分布，则其联合熵 (Joint entropy) 为：
1、熵只依赖于随机变量的分布,与随机变量取值无关，所以也可以将的熵记作。
2、令0log0=0(因为某个取值概率可能为0)。
条件熵
条件熵表示在已知随机变量的条件下，随机变量的不确定性。
定义为给定条件下的条件概率分布的熵对的数学期望：
条件熵相当于联合熵减去单独的熵，即
描述和所需的信息是描述自己所需的信息,加上给定的条件下具体化所需的额外信息。
相对熵（KL散度）
设是离散随机变量中取值的两个概率分布，则对的相对熵是：
性质：
1、
如果和两个分布相同，那么相对熵等于0；
2、
3、
相对熵可以用来衡量两个概率分布之间的差异，上面公式的意义就是求与之间的对数差在上的期望值。
交叉熵
现在有关于样本集的两个概率分布和，其中为真实分布，为非真实分布。如果用一个样本的分布来衡量整体预测分布：
当为常量时（在机器学习中，训练数据分布是固定的），最小化相对熵等价于最小化交叉熵也等价于最大化似然估计。交叉熵可以用来计算学习模型分布与训练分布之间的差异，交叉熵广泛用于逻辑回归的Sigmoid和Softmax函数中作为损失函数使用。
决策树
决策树分类从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点。每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶节点，最后将实例分配到叶节点的类中。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行划分。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。通常特征选择的准则是信息增益或信息增益比，特征选择的常用算法有ID3，C4.5，CART。
ID3 信息增益
当熵和条件熵中的概率由数据估计(特别是,极大似然估计)得到时,所对应的熵和条件熵分别称为经验熵和经验条件熵。
信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。
特征对训练数据集D的信息增益：定义为集合的经验熵与特征给定条件下的经验条件熵之差,即:
遍历所有特征，对于特征:
1、计算特征对数据集的经验条件熵；
2、计算特征的信息增益：；
3、选择信息增益最大的特征作为当前的分裂特征。
C4.5 信息增益率
为了避免ID3算法偏向于选择可取值数目较多的属性，定义了信息增益率。信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在分类为题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。因此，使用信息增益比可以对这一问题进行校正，这是另一种特征选择算法，也即C4.5算法。
定义：特征对训练数据集的信息增益比定义为其信息增益与训练集的经验熵之比：
CART树 基尼指数
ID3和C4.5都使用了大量的对数运算，计算量大。CART树是二叉树，因此每次选择最优属性后，再选择该属性的一个取值进行划分。用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
定义：假设有K个类，样本点属于第k类的概率为，则概率分布的基尼指数如下
对于给定的样本集合D，其基尼指数为：
一个特征的信息增益/基尼系数越大，表明特征对样本的熵减少的能力更强，这个特征使得数据由不确定性变成确定性的能力越强。
未完待续！