思维导图：决策树是如何做出决策的呢？

思维导图（内容概述）

指标

对于统计学习方法来说，我们需要从模型+决策+算法一步步开始。 但在理解模型之前，特征的选择尤为重要。 在决策树方法中，有一些重要的概念，即选择特征的标准。

熵：用来表示随机变量的不确定性（混沌）程度，记为 H(X) = -\sum_{i=1}^n p_i \log p_i

条件熵：在随机变量X恒定的条件下，随机变量Y的不确定性（混乱程度）记为 H(Y|X) = \sum_{i=1}^np_iH(Y|

信息增益：通过了解特征X的信息而降低Y类信息的不确定性的程度，记为g(D,A) = H(D) - H(D|A)

信息增益比：

基尼指数（K 为类别数，Pk 为属于类别 k 的概率）定义为： Gini(p) = \sum_{k=1}^Kp_k(1-p_k) = 1 - \sum_{ k=1}^Kp ^2_k

在特征A的条件下，集合D的基尼指数定义为： Gini(D, A) = \frac{|D_1|}{D}Gini(D_1) + \frac{D_2}{D}Gini(D_2)决策树模型定义：分类决策树模型是描述实例分类的树结构。 决策树由节点和有向边组成。 节点有两种类型：内部节点和叶节点。 内部节点表示特征或属性，叶节点表示类。 使用决策树分类，从根节点开始，测试实例的某个特征，并根据测试结果将实例分配给其子节点； 此时，每个子节点对应一个特征的值。 这种递归一直持续到到达叶节点。 最后，对所有实例进行分类。

决策树模型图：

损失函数和 () 策略

在决策模型中，有一个非常重要的步骤，就是剪枝。 剪枝可以决定最终决策树的外观。

当我们遇到一系列连续的值时该怎么办？ 这时需要对连续值进行离散化，即需要选择连续值的分割点。

DT模型是为了最小化决策树的整体损失函数或成本函数，可以定义如下：

C_\alpha(T) = C(T) + \alpha * |T_(叶)|

决策树生成算法的类别：每种算法不同，衡量标准也不同。 ID3算法

ID3算法的核心是利用信息增益准则在决策树的每个节点上选择特征并递归地构造决策树。

算法说明：

输入：训练数据集D、特征集A、阈值\;\\输出：决策树T.\\ (1) 如果D中的所有实例都属于同一类C_K，则T是单节点树，且C_K作为节点的类标号，返回T；\\ (2) 若A=\phi，则T为单节点树，以D中实例数最多的类C_K作为节点的类别标签，T。\\ (3)否则，计算A到D中特征的信息增益，选择信息增益最大的特征A_g;\\ (4)如果A_g的信息增益小于阈值，设置T为单节点树，选择D中最大实例的类作为该节点的类标记，返回T； \\ (5) 否则，对于A_g的每个可能值a_i，根据A_g=a_i将D划分为多个非空子集D_i，并选择D_i中实例数最多的类作为该节点的标记，\ \构建子节点，树T由该节点和子节点组成，返回T；\\ (6)对于第i个子节点，用D_i作为训练集，用A-\{ A_g\}为特征集，递归调用(1)~(5)，得到子树T_i，返回T。

C4.5算法

C4.5算法与ID3算法类似，并对ID3算法进行了改进。 其核心是利用信息增益比来选择特征。

输入：训练数据集D、特征集A、阈值\;\\输出：决策树T.\\ (1) 如果D中的所有实例都属于同一类C_K，则T是单节点树，且C_K作为节点的类标号，返回T；\\ (2) 若A=\phi，则T为单节点树，以D中实例数最多的类C_K作为节点的类别标签，T。\\ (3)否则，计算A到D中特征的信息增益比，选择信息增益比最大的特征A_g;\\ (4)如果信息增益A_g的小于阈值\，设置T为单节点树，将实例添加到D中最大的类作为该节点的类标签，返回T； \\ (5) 否则，对于A_g的每个可能值a_i，根据A_g=a_i将D划分为多个非空子集D_i，并最大化D_i中实例的数量，其类别即为该节点的标签，\\构造子节点，树T由该节点和子节点组成，返回T；\\ (6) 对于第i个子节点，用D_i作为训练集，用A-\{A_g \} 为特征集，递归调用(1)~(5)，得到子树T_i，返回T。

CART算法

CART算法由决策树生成和决策树剪枝两个步骤组成。

CART生成

决策树生成是递归构造二叉决策树的过程。 回归树采用平方误差最小化准则，分类书采用GINI INDEX群笑话准则进行特征选择并生成二叉树。

回归树的生成

最小二乘回归树生成算法通常用于生成回归树。

s\} \hat{c_m}=\frac{1}{N_m}\sum{y_i},x\in R_m,m=1,2 \\ (3) 继续调用步骤(1), ( 2),直至满足条件； \\ (4) 将输入空间划分为M个区域R_1、R_2、R_3...R_M，生成决策树。 \\ f(x)=\sum^M_{m=1}\hat{c_m}I(x\in R_m)">输入：训练数据集 D;\\ 输出：回归树 f(x).\\在训练集所在的输入空间中，递归地将每个区域划分为两个子区域，并确定每个子区域上的输出值，构建决策树： \\ (1) 选择最优分割变量 j 和分割点s，求解 \\ min_{j,s}[min_{c_j}\sum_{x_j\in R_1(j,s)}(y_i-c_i)^2+min_{c_j}\sum_{x_j\in R_2( j ,s)}(y_i-c_i)^2]，遍历j，选取最小的(j,s)作为j的分割点s；\\ (2)除以选取的对(j,s)面积，确定对应的输出值：\\ R_1(j,s)=\{x|s(j) \leq s\},R_2(j,s)=\{x|s(j) > s\} \hat{ c_m}=\frac{1}{N_m}\sum{y_i},x\in R_m,m=1,2 \\ (3) 对两个子区域继续调用步骤(1)、(2)，直到满足条件；\\ (4) 将输入空间划分为M个区域R_1,R_2,R_3...R_M，生成决策树。\\ f(x)=\sum^M_{m=1} \hat{ c_m}I(x\in R_m) 分类树的生成

分类树利用基尼指数来选择最优特征，并确定特征的最优二值分割点。

CART生成算法说明：

输入：训练数据集D，停止计算的条件；\\输出：CART决策树。\\根据训练数据集，从根节点开始，对每个节点递归执行以下操作，构建决策树：\ \ (1) 设节点的训练集为D，计算数据集上现有特征的基尼指数。 此时，对于每个特征A，对于每个可能取值a，\\根据样本点对A=a，检验“是”或“否”，将D分为D_1和D_2，计算出基尼系数A=索引。 \\ (2) 在所有可能的特征A和可能的切割点a中，选择基尼指数最小的特征和对应的切割点。 \\ 由此，从当前节点生成两个子节点，并根据特征将训练集分配给这两个子节点。 \\ (3) 在两个子节点上递归调用(1)和(2)，直到满足条件； \\ (4) 生成CART决策树。