《统计学习方法》 - 决策树

从根节点开始，对实例进行测试，将测试完的实例分布到子节点，之后递归的对实例进行测试，直至达到叶节点并将实例分配到叶节点的类中

互斥且完备：每一个实例都被一条路径或一项规则所覆盖，且只被一条路径或一项规则所覆盖

对特征空间进行划分，每一个小矩形都是一个单元，类的条件概率分布如下图所示

当P(Y=1 | X=c) > 0.5时，则认定该单元为属于正类

决策树的损失函数通常是正则化的最大似然函数，学习的策略就是使损失函数最小化

决策树的构建：构建根节点，将所有实例都放入根节点中，找到一个最优特征分类方法，将实例分成多个子集并传递到子节点上，如果无须继续分类，则将其划入叶节点的类中；如尚不能被正确分类，则对其递归划分子集，直到能够正确分类后放入叶节点的类中

由于上述方式的构建可能发生过拟合，因此需要对决策树进行一定的剪枝，提高泛化能力

如果特征向量过多，也可以在构建开始前，对特征进行一定的选择后再构建决策树

熵：随机变量不确定性的度量

条件熵：在已知随机变量X的条件下随机变量Y的不确定性

信息增益：得知特征X的信息使得Y的不确定性减少的程度