# 11.12记录
决策树
决策树也是机器学习的关键算法之一。也是XGBoost算法的基本构成单元。决策树是一个树形结构，如下图所示
有个线上小游戏叫做akinator(网络精灵)，这个就是一个类似决策树的东西。
特征选择
特征选择是选择出那些具有分类能力的特征，好的特征选择可以规避很多问题，例如维度灾难（指的是由于有太多的特征，导致每个特征最深处的叶子节点可能只有几个样本），过拟合，复杂模型等。不同算法衡量特征选择的方法也不一样。
ID3
ID3算法计算原本样本的熵，然后计算条件熵（就是原来的样本集合经过特征选择之后的熵），然后原来的熵减去条件熵就是信息增益。ID3算法每次选择信息增益最高的特征来作为父节点，然后对该特征每个可能的取值生成一个叶子节点，循环往复。ID3偏向选择取值较多的特征。
C4.5
C4.5算法和ID3类似，不过C4.5用的是信息增益比，就是信息增益/数据集D以特征F作为随机变量的熵
CART
是XGboost的重要组成部分。采用二分递归，所以树是二叉树。
剪枝
剪枝是决策树中很重要的部分，因为不剪枝可能会造成过拟合的情况，当然剪枝太多也会造成欠拟合
预剪枝
分裂之前先对节点进行评估，如果可以使得模型泛化能力增加，那么就分裂，不然不分裂。
后剪枝
先构造完一颗完整的决策树，然后从底向上对叶子进行评估，如果非叶子节点剪掉有利于提升，则剪掉子树。