一．决策树概念
决策树：从根节点开始一步步走到叶子节点
节点（特征）：
- 根节点：第一个选择点
- 非叶子节点与分支：中间过程
- 叶子节点：最终的决策结果（容易理解错误）
增加节点相当于在数据中切一刀（节点并不是越多越好）
说明：所有的数据最终都会落到叶子节点；决策树既可以做分类也可以做回归
例子：一家人谁爱玩游戏
二．构造一棵树：切分特征（选择节点）
目标：分类效果最好
依据：
- 信息增益；
- 信息增益率；
- GINI系数
衡量标准-熵：随机变量不确定性的度量。越混乱，熵越大。（如杂货市场里面什么都有，那肯定混乱呀，专卖店里面只卖一个牌子的那就稳定多啦）
公式：H(X)=-Σ pi * logpi, i=1,2, ... , n （pi为概率，属于[0,1]）
图像：
1.ID3算法：信息增益（熵值减少，gain）
表示特征X使得类Y的不确定性减少的程度。信息增益最大，作为根节点。（分类后的专一性，希望分类后的结果是同类在一起）
特征作为根节点的信息增益 = 系统熵值-某一特征的熵值
构造实例：实例学习
2.C4.5算法：信息增益率（考虑自身熵）
信息增益率/自身熵值，如ID信息增益大，自身熵值大
3.CART算法：GINI系数（和熵的衡量标准类似，计算方式不相同）
计算公式：
4.说明：连续值处理
贪婪算法
离散化：排序—》二分（合适位置选择）
三．决策树剪枝：决策树过拟合风险很大
剪枝策略：预剪枝，后剪枝
预剪枝：边建立决策树边进行剪枝的操作（更实用）
后剪枝：当建立完决策树后来进行剪枝操作
1.预剪枝
预剪枝：限制深度，叶子节点个数，叶子节点样本数，信息增益量等
2.后剪枝
通过一定的衡量标准，每个节点要不要分裂（比较分裂与不分裂的下式值）
（叶子节点越多，损失越大）
损失：C(T) = 样本个数* GINI系数
Tleaf为叶子节点的个数