一、决策树简介
决策树是一种既能做分类，又能做回归的算法。
基本形状为：
理解上图中的重要概念（根节点，分支，内部节点，叶子节点）
二、信息熵的概念（entropy）
假设有两个篮子A和B：
A装了 [鸡蛋、苹果、香蕉、橘子、芒果、牛奶]
B装了 [鸡蛋、鸡蛋、鸡蛋、鸡蛋、鸡蛋、牛奶]
从上面两个篮子中随机取一个出来，A有6中结果，B有2种结果
A的不确定性大，B的不确定性小，A的熵 > B的熵 H(A) >H(B)
理解：若一个数据集合内，越混乱，那么熵就越大
信息熵的公式（规定0log(0)=0 ）
理解熵的公式
尝试计算上面例子中的H(A)与H(B)
H(A) = {- 1 6 \frac{1}{6} 61 * log 2 ( 1 / 6 ) \log_2 (1/6) log2(1/6)}*6 = 2.58
H(B) = - 5 6 \frac{5}{6} 65 * log 2 ( 5 / 6 ) \log_2 (5/6) log2(5/6) - 1 6 \frac{1}{6} 61 * log 2 ( 1 / 6 ) \log_2 (1/6) log2(1/6) = 0.65
这里对数中，为什么要以2为底数？
遵循信息论的普遍传统，使用2作为对数的底
另外，基尼系数，与熵的概念类似，计算方法为：
Gini ( P ) (P) (P) = ∑ i = 1 k \sum_{i=1}^{k} ∑i=1k P k P_k Pk ( 1 − P k ) (1-P_k) (1−Pk)
三、构造决策树（结合简单案例）
案例来源：https://blog.csdn.net/wsp_1138886114/article/details/80955528
基本思想：希望节点的熵迅速降低
案例：特征分别为：性别、车型、衬衣尺码，分类结果为 C0或C1
ID3算法——信息增益（information gain）
-
先计算一下，不考虑3个特征的信息熵：C0出现10次，C1出现10次
H = - P C 0 P_{C0} PC0* log 2 ( P C 0 ) \log_2 (P_{C0}) log2(PC0) - P C 1 P_{C1} PC1* log 2 ( P C 1 ) \log_2 (P_{C1}) log2(PC1)
H = 2*(-0.5* log 2 ( 0.5 ) \log_2 (0.5) log2(0.5))
H = 1
- 计算一下，如果根节点是性别，那么信息熵为：
机器学习笔记_决策树一、决策树简介二、信息熵的概念（entropy）三、构造决策树（结合简单案例）四、决策树的过拟合问题以及剪枝策略
gain(性别）= 0.029
同理可得
gain(车型）= 0.62
gain(性别）= 0.029
因此，这里根节点，应选择车型
C4.5算法——信息增益率
如果将上述顾客ID也作为一个特征值，那么顾客ID的信息增益 肯定是最大的
因为一个ID 对应一个结果
这时，就引入信息增益率算法
信息增益率 = 信息增益/自身的熵值
CART算法——基尼系数
与信息增益算法类似
四、决策树的过拟合问题以及剪枝策略
决策树的过拟合（Overfitting）：
决策树训练得过于复杂，高度高，节点多。训练集数据表现很高，误差非常小，但是测试数据的表现不好。
预剪枝
在构建决策树的过程中，提前停止学习
- 可以指定决策树的深度
- 可以指定决策树的节点的最小样本数（min_sample），如果节点的样本数小于指定值，那么也停止裁剪
后剪枝
决策树构建好之后，开始裁剪
定义损失函数：
C α C_\alpha Cα(T) = C(T) + α \alpha α| T l e a f T_{leaf} Tleaf|
举例：
假设一个非叶子节点，分裂成了3个叶子节点
试算
分裂之后的 C α C_\alpha Cα(T) = 3个叶子节点的基尼系数 + α \alpha α*3
与 分裂之前的 C α C_\alpha Cα(T) = 自身的基尼系数 α \alpha α*1 进行比较