参考blog 和onenote 2016-summer总结 及一个ppt
决策树
- 如何构建决策树
- 如何分裂
- 分裂属性
- 离散/连续变量处理
- 如何停止
- 节点为纯
- 节点样本数量小于阈值
- 没有属性进行分割
- 如何分裂
- 如何判定
- 对应的样本数在叶子节点中最多
随机森林
- 构建树：构建k个决策树，每棵树按照如下方式生长
- 选择构建树数据
- sample N cases at random but with replacement, from the original data
- 如何分裂
- 在每个节点，随机选择m个特征，选择分裂属性最好的特征进行分裂。
- 每棵树无剪枝生长
- 选择构建树数据
- 如何判定
- 综合k棵树的结果
分裂属性
- 信息增益（information gain、KL divergence）
- 增益比率Gain Ratio
基于信息增益进行属性选择有一个很大的缺陷，它会倾向于选择属性值多的属性。一个较为极端的例子是某种属性将预测属性完全分割，也就是在该属性分割后预测属性在每个分割集中，只有一种可能，分割后的预测属性的不确定性很小。但这样的分割方式往往没有任何意义，缺乏泛化能力。
信息增益比率对上面的情况进行了改进，它引入了一个分裂信息
$SplitInfo_R(D) = -\sum_{j=1}^{k} \frac{|D_j|}{|D|} * lg(\frac{|D_j|}{|D|})$
- Gini指标
| 信息增益 | 用父节点信息熵-子节点的条件信息熵，选择下降最多的一个。 | 信息，即熵，用于衡量系统带有的信息多少（混乱程度）。越是混乱，其值越高$H(p)=-\sum_i {p_i}*lg({p_i})$ |
| 增益比率 | ||
| Gini指标 | Gini纯度，用于衡量节点内样本是否单一性。$Gini(D) = 1 - \sum_i{P_i}^2$ | 在CART(分类回归树)算法中, 基尼不纯度表示一个随机选中的样本在子集中被分错的可能性。总体内包含的类别越杂乱，GINI指数就越大（跟熵的概念很相似） |