16课 决策树——既能分类又能回归的模型

决策树

一棵决策树（Decision Tree）是一个树结构（可以是二叉树或非二叉树），每个非叶节点对应一个特征，该节点的每个分支代表这个特征的一个取值，而每个叶节点存放一个类别或一个回归函数。决策的过程就是从根节点开始，提取出待分类项中相应的特征，按照其值选择输出分支，依次向下，直到到达叶子节点，将叶子节点存放的类别或者回归函数的运算结果作为输出（决策）结果。

这三个非叶子节点（含根节点），统称决策节点，每个节点对应一个条件判断，这个条件判断的条件，我们叫做特征。上例是一个有三个特征的分类树。

训练决策树

• 准备若干的训练数据（假设 m 个样本）；
• 标明每个样本预期的类别；
• 人为选取一些特征（即决策条件）；
• 为每个训练样本对应所有需要的特征生成相应值——数值化特征；
• 将通过上面的1-4步获得的训练数据输入给训练算法，训练算法通过一定的原则，决定各个特征的重要性程度，然后按照决策重要性从高到底，生成决策树。

常用算法

ID3 缺点：ID3一般会优先选择取值种类较多的特征作为分裂特征。
C4.5 问题：当某个 |Sv| 的大小跟 |S| 的大小接近的时候,GainRatio接近无穷，导致某个其实无关紧要的特征占据根节点（可以采用启发式的思路，对每个特征先计算信息增益量，在其信息增益量较高的情况下，才应用信息增益率作为分裂标准。）
CART 基尼系数，严格二分
基尼指数（Gini Index）其实就是系数的100%表示。

17课 决策树——告诉你 Hello Kitty 是人是猫

构建决策树，剪枝优化
代码实现