机器学习决策树总结

决策树是广泛用于分类和回归任务的模型。

其本质上是从一层一层的if/else问题中进行学习并得出结论，从下面的一个例子就可以较好的理解了。
如果你现在想要区分下面四种动物：熊、老鹰、企鹅和海豚，这里的目标是要用尽可能少的if/else问题来得到正确的答案。比如可以问有没有羽毛，这个问题的答案只有“有”和“没有”，如果有，则答案的可能性减少到只有2种，“老鹰和企鹅”，那么你可以再问一个问题，比如说能不能飞，如果能飞就只能是老鹰了。
通过上面的例子可以更好的理解决策树的基本模型，而构造决策树的一个原则是要使得该树最简洁，这就需要每一次“使用”if/else时得到的分类效果最好，那么应该怎么样才能达到该原则呢？这就需要每次用来分类的特征有较好的分类效果，这里指的是特征重要性。
熵
熵在物理学上是对系统”混乱”程度的度量，系统越有序，熵值越低，系统越混乱或者说是分散熵值越高。
假如事件A的分类划分是（A1,A2,…An）,每个分类发生的概率为（p1,p2,…,pn），那该信息熵的定义公式为：

如果通过某个特征进行分类使得系统的熵值达到最小，比如说一组数据从树的根节点出发按照某个特征进行分类，使得该数据分成两组不同的数据，这两种不同的数据里面都只包含有一种数据，那么该特征对数据的分类效果就很好，每个子节点的数据也足够“纯”。

信息增益及增益率
信息增益：用某一特征来对数据进行分类时得到的数据集与分类前相比熵值的减小值。
信息增益公式如下：
D：为样本集
Ent(D):整体熵
a:离散型属性
v: 是a属性里可能的取值节点
D^v：第v个分支节点包含了D中所有在属性a上取值为a^v的样本

由以下例子来解释该概念：
如下图，第一列为论坛号码，第二列为性别，第三列为活跃度，最后一列用户是否流失


其中Positive为正样本（ 已流失） ， Negative为负样本
（ 未流失） ， 下面的数值为不同划分下对应的人数。可得到三个熵：
整体熵：

性别熵：

所以性别信息增益为：

同理：活跃度信息增益为：

基尼值和基尼指数：
基尼值：Gini（D）：从数据集中随机抽取两个样本，这两个样本不是同一类的概率，即Gini（D）的值越小，数据集D的纯度越高。
基尼系数的公式如下所示：

基尼指数Gini_index(D):在划分数据后基尼指数最小的属性作为最优划分属性。
基尼指数公式如下：

基尼增益：

具体步骤如下例题所示：

统计总结：

对数据集分别计算他们的Gini系数增益，取Gini系数增益值最大的属性作为决策树的根节点属性。
如果根据是否有房来进行划分是，Gini系数增益计算过程为：
Gini（左子节点）=

Gini（右子节点）=
所以是否有房的基尼系数增益为：

其他属性也按同理计算其基尼系数增益。
总结：
（1）开始时将所有的数据记录看作一个节点；
（2）遍历所有可以划分的属性（按照规定原则选择最好的划分属性）；
（3）分割成两个节点P1，P2；
（4）对N1和N2分别执行第二第三步的操作直到节点的数据足够纯为止。
在构造决策树的过程中为了避免过拟合或者其他一些不确定因素（如数据有噪声、样本冲突或者属性不能够完全作为分类的标准）造成树的结构过于复杂有时应该对决策树进行剪枝。
常见的剪枝方法：
预剪枝：在构造树之前做规定使其达到某种程度停止继续扩大
（1）每一个节点所包含的最小数目，例如10，若该节点的样本数小于10时则不再继续分
（2）指定树的深度，如当数的深度达到某个数（如4）时不再继续分
（3）给一个指定的熵值，当某个节点的熵值小于某个数时则停止划分。
后剪枝：在已经生成过拟合决策树上进行剪枝。