Decision Tree 决策树

决策树是一种用于分类和回归任务的非参数监督学习算法。它是一种分层树形结构，由根节点、分支、内部节点和叶节点组成。每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

构造

剪枝

剪枝是指在决策树构造过程中，对每个节点在划分前后计算信息增益，若划分后的信息增益小于划分前，则不对该节点进行划分，即把该节点变为叶节点。

可以防止过拟合。

预剪枝

预剪枝是指在决策树构造过程中，对每个节点在划分前后计算信息增益，若划分后的信息增益小于划分前，则不对该节点进行划分，即把该节点变为叶节点。

后剪枝

后剪枝是指先从训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能够带来决策树泛化性能的提升，则将该子树替换为叶节点。

纯度和信息墒

信息墒公式：$H(X)=-\sum_{i=1}^n p_i \log_2 p_i$

信息增益（ID3算法）：

信息增益是指得知特征X的信息而使得类Y的信息的不确定性减少的程度。

信息增益公式：$g(D,A)=H(D)-H(D|A)$

信息增益比（C4.5算法）：

信息增益比是信息增益与训练集的经验熵的比值。

gini指数Gini(D,A) = 1 - \sum_{i=1}^n p_i^2

CART算法

CART算法是一种二叉树算法，它的特点是只考虑二元划分，即每次划分只考虑一个特征的两种取值。