什么是决策树
- KNN 和 决策树 是非参数算法（大部分算法都是参数算法）；
- 可以解决分类问题，天然可以解决多分类问题；
- 可以解决回归问题；
- 具有非常好的可解释性；
问题：
- 每个节点在哪个维度上划分？
- 选好维度的话，在维度的哪个值上划分？（如：计算信息熵的方法）
信息熵
信息熵 是 信息论的基础概念，熵在信息论中表示 随机变量的不确定度。
熵源自于物理热力学，热量越大，粒子无规则运动越剧烈，不确定性越高。
数据越不确定，熵越大；数据不确定性低，熵越小。
信息熵计算公式
$ H = -\sum^k_{I=1} p_i log(p_i) $
- H：一个系统信息熵的总和；
- \(p_i\)：K 类信息，每一类信息所占的比例；
一般值小于1，所以 $ log(p_i) $ 为负，所以总公式前面有负号；
计算示例
{1, 0, 0}
H = -1 log(1) = 0 # 此时信息熵最低
如果数据只有两类
公式可以改变为：$ H = -x log(x) - (1-x)log(1-x) $
使用信息熵寻找最优划分
划分后，信息熵如何最低？---- 对划分结果进行搜索。
基尼系数
是另一个划分指标；计算比信息熵简单很多，公式： $ G = 1 - \sum^k_{i=1} p^2_i $
计算示例
基尼系数越高，整体随机性越强。
二分类问题的基尼系数
$ G = 1 - x^2 - (1-x)^2 = 1 - x^2 - 1 + 2x - x^2 = -2x^2 + 2x $
是一个抛物线，开口向下，拥有一个最大值，在抛物线的对称轴处。
当 x = 0.5 时，基尼系数最大，数据不确定程度最大。
信息熵 & 基尼系数
- 信息熵的计算 比 基尼系数 稍慢；sklearn 中默认使用基尼系数；
- 大多数情况下，二者没有特别的效果优劣，划分结果区分不大；
CART
CART: Classification And Regression Tree
以上探讨的决策树通常也叫做 CART，根据某一个维度d 和 某一个阈值 v 进行二分（得到一颗二叉树）；
sklearn 实现的决策树通常是 CART；
还有其他决策树创建方法：ID3, C4.5, C5.0 ...
决策树的复杂度
预测的时间复杂度: O(log m)
训练： O( nmlogm)
所有非参数机器学习算法，都容易产生过拟合。
一般使用对决策树进行剪枝 来降低复杂度、解决过拟合。
比如：限制树的高度；对参数进行平衡。