1,决策树概念简介
不同的算法模型适合于不同类型的数据。

首先，在了解树模型之前，自然想到树模型和线性模型有什么区别呢？其中最重要的是，树形模型是一个一个特征进行处理，之前线性模型是所有特征给予权重相加得到一个新的值。
决策树与逻辑回归的分类区别也在于此，逻辑回归是将所有特征变换为概率后，通过大于某一概率阈值的划分为一类，小于某一概率阈值的为另一类；而决策树是对每一个特征做一个划分。另外逻辑回归只能找到线性分割（输入特征x与logit之间是线性的，除非对x进行多维映射），而决策树可以找到非线性分割。

而树形模型更加接近人的思维方式，可以产生可视化的分类规则，产生的模型具有可解释性（可以抽取规则）。树模型拟合出来的函数其实是分区间的阶梯函数。

决策树学习：采用自顶向下的递归的方法，基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处熵值为0（叶节点中的实例都属于一类）。

其次，需要了解几个重要的基本概念：根节点（最重要的特征）；父节点与子节点是一对，先有父节点，才会有子节点（增加节点相当于在数据中切一刀）；叶节点（最终标签）。所有的数据最终都会落到叶子节点，既可以做分类也可以做回归

2，决策树的训练与测试
2.1 训练阶段：
从给定的训练集构造出来一棵树（从跟节点开始选择特征（节点），如何进行特征切分使得分类的效果更好）。通过一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当成根节点，以此类推。

衡量标准-熵：熵是表示随机变量不确定性的度量（在物理化学中，物体内部的混乱程度）。例如杂货市场里面什么都有，肯定混乱（熵值高），而专卖店里面只卖一个牌子的那就很稳定多（熵值低）。

熵的表达式：

P代表概率值，当P接近于1时（概率大），H接近于0（熵值低）。不确定性越大，得到的熵值也就越大。当p=0或p=1时，H§=0,随机变量完全没有不确定性。当p=0.5时，H§=1,此时随机变量的不确定性最大

信息增益：表示特征X使得类Y的不确定性减少的程度（遍历所有特征，选择使分类后的信息增益最大化的特征作为根节点，然后从剩下地特征重复上述操作，直至决策树构造完成）。

决策树构造实例：

数据：14天打球情况； 特征：4种环境变化；

划分方式有4种：

在历史数据中（14天）有9天打球，5天不打球，所以当前系统的熵应为：

然后在4个特征逐一分析，先从outlook特征开始：

根据熵的表达式可以计算得：Outlook = sunny时，熵值为0.971；Outlook = overcast时，熵值为0；Outlook = rainy时，熵值为0.971

根据历史数据统计outlook取值分别为sunny,overcast,rainy的概率分别为：5/14, 4/14, 5/14

熵值计算：

系统的熵值从原始的0.940下降到了0.693，增益为0.247。同样的方式可以计算出其他特征的信息增益，那么我们选择最大的那个相当于是遍历了一遍特征，找出来了根节点，然后再其余的中继续通过信息增益找下面的节点。

以上算法步骤称为ID3算法，对于稀疏特征（属性非常多，样本量非常少），利用该算法计算得到的熵值较低，使得信息增益很大，而这些特征对最终的分类的结果没有太大影响，我们却根据以上算法将这些特征定为根节点，显然这样做是不合理的。

信息增益率（解决了ID3问题，考虑自身熵），对于稀疏特征的自身熵值一般都比较大，通过信息增益/自身熵，会发现稀疏特征的信息增益率极低。

还有其他算法例如：
CART使用GINI系数来当做衡量标准，GINI系数的表达式：

概率越接近1，GINI系数越小，和熵的衡量标准类似，计算方式不相同。

2.2 测试阶段：
根据构造出来的树模型从上到下去走一遍就好了

3，决策树剪枝策略

想象一下，如果树足够大，每一个数据就都可以分配到每个叶子节点上了（理论上可以完全分得开数据）。但是这样的决策树过拟合（在训练集上表现很好，但在测试集上表现很差）风险很大，泛化能力弱。

剪枝策略有预剪枝，后剪枝两种
3.1 预剪枝：边建立决策树边进行剪枝的操作（很实用，易实现），限制深度（特征数），叶子节点个数，叶子节点样本数，信息增益量等抑制树结构的伸展。

后剪枝：当建立完决策树后来进行剪枝操作，通过一定的衡量标准（叶子节点越多，损失C越大）：

损失C=（GINI系数*叶子节点中的样本数）的累和，T代表叶子节点数。