Data-Method-03DecisionTree我们所知道的是非常微小的，我们不知道的是巨大的。人只追随幻影。--Pierre-SimonLaplace数据系列：目录｜配置｜代码仓库｜实战对应《数据挖掘导论》第4章，《机器学习》第4章，《统计学习方法（第2版）》第5章。1.决策树模型定义决策树（DecisionTree）是一种基本的分类和回归方法。它可以被认为是一组if-then规则，定义在特征空间和类空间和类空间中的条件概率分布。主要优点：模型可读性强，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则，建立决策树模型。示意图“元素”叶子节点（leftnode）或终端节点（terminalnode）：决策结果内部节点（internalnode）或非终端节点（non-terminalnode）：属性测试条件决策树学习本质：来自一组分类规则是从训练数据集中导出的。决策树学习使用损失函数，通常是正则化的最大似然函数，决策树学习的策略是将损失函数最小化作为目标函数。三个关键步骤：特征选择（分区选择）、决策树的生成和决策树的剪枝。决策树的生成对应模型的局部选择，决策树的剪枝对应模型的全局选择。在决策树的生成过程中使用特征选择，在生成前后都可以进行剪枝。常用算法：ID3、C4.5和CART2。特征选择特征选择（分区选择）是决策树学习的关键，即如何选择最优的分区属性。特征选择就是选择对训练数据具有分类能力的特征，即提高节点的纯度。以下是特征选择常用的几个指标：信息增益、信息增益比、基尼指数信息增益信息熵（informationentropy）：最常用的衡量样本集纯度的指标。第k类样本在样本集$D$中所占的比例为$p_k(k=1,2,..,|y|)$，则D的信息熵定义为：$Ent(D)=-\sum^{|y|}_{k=1}p_k\log_2p_k$$Ent(D)$的值越小，$D$的纯度越高。信息增益（informationgain）属性a划分样本集D。“信息增益”$Gain(D,a)=Ent(D)-\sum^V_{v=1}\frac{|D^v|}{|D|}Ent(D^v)$一般来说，信息增益越大，使用属性a进行划分得到的“纯度提升”越大。存在的问题：偏向于选择取值更多的特征。InformationgainratioInformationgainratio（增益率，信息增益比）$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$Intrinsicvalue（内在价值）：$IV(a)=-\sum^V_{v=1}\frac{|D|^v}{|D|}\log_2(\frac{|D^v|}{|D|})$缺陷：增益C4.5采用启发式算法从候选划分属性中选择信息增益高于平均水平的属性，然后选择增益率最高的基尼系数Gini最高的属性。系数（Gini指数）：CART决策树使用的$Gini(D)=\sum^{|y|}_{k=1}\sum_{k'\neqk}p_kp_{k'}=1-\sum^{|y|}_{k=1}p_k^2$$Gini(D)$反映了两个样本是从数据集D中随机抽取的，它们的类标签不一致的概率。$Gini(D)$越小，数据集D的纯度越高。属性a的Gini指数定义为：$Gini\_index(D,a)=\sum^V_{v=1}\frac{|D^v|}{|D|}Gini(D^v)$选择划分后基尼系数最小的属性作为最优划分属性，即$a_*=\arg\min_{a\inA}Gini\_index(D,a)$3。决策树生成由于搜索空间的大小呈指数级增长，因此找到最佳决策树在计算上是不可行的。因此人们开发了一些有效的算法来构建次优决策树。这些算法通常采用贪心策略，采用一系列局部最优策略来构造决策树。Hunt算法Hunt算法将训练记录依次划分为相对纯的子集，递归构建决策树。它是许多决策树算法的基础，包括ID3、C4.5和CART。算法：令$D_t$为与节点t相关联的训练记录集，$y={y_1,y_2,...,y_c}$为类标签，如果$D_t$中的所有记录都属于同一类$y_t$，则$t$为叶节点，$y_t$表示如果$D_t$包含属于多个类的记录，则选择一个属性测试条件，将记录划分为更小的子集。对于测试条件的每一次输出，创建一个子节点，根据测试结果将$D_t$中的记录分发给子节点。然后，对于每个子节点，递归地调用该算法。补充附加条件：处理特殊情况当创建的子节点为空时，即没有与这些节点关联的记录，该节点为叶节点，类标签为父节点上训练记录的多数类.当与$D_t$关联的所有记录具有相同的属性值且不可分，但类别不同时，标签被标记为该节点关联的训练记录中的多数类。ID3算法ID3算法的核心是应用信息增益准则在决策树的每个节点上选择特征，递归构建决策树。相当于用最大似然法来选择概率模型。算法：输入：训练数据集$D$，特征集$A$阈值$\epsilon$输出：决策树$T$如果$D$中的所有实例都属于同一个类$C_k$，则$T$是一个单节点树，使用类$C_k$作为节点的类标号，返回$T$；如果$A=\emptyset$，则$T$为单节点树，将$D$$C_k$中实例数最多的类作为该节点的类标记，返回$T$;否则计算$A$到$D$中每个特征的信息增益，选择信息增益最大的特征$A_g$$Gain(D,a)=Ent(D)-\sum^V_{v=1}\frac{|D^v|}{|D|}Ent(D^v)$;如果$A_g$的信息增益小于阈值$\epsilon$，则将$T$设置为单节点树，并使用$D$中实例数最多的类$C_k$作为类节点标签，返回$T$；否则，对于$A_g$$a_i$的每一个可能取值，根据$A_g=a_i$，将$D$划分为若干个非空子集$D_i$，$D_i$中实例数最多的类作为标记构造子节点，由节点及其子节点树$T$组成，返回$T$；对于第$i$个节点，以$D_i$为训练集，以$A-\{A_g\}$为特征集，递归调用步骤1~5，得到子树$T_i$，返回$T_i$.C4.5算法C4.5算法在生成过程中使用信息增益比来选择特征，其他步骤相同。信息增益比：$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$内在价值（intrinsicvalue）：$IV(a)=-\sum^V_{v=1}\frac{|D|^v}{|D|}\log_2(\frac{|D^v|}{|D|})$CART算法分类回归树（classificationandregressiontree,CART)模型，这是一种广义的决策树学习方法。它还包括特征选择、树生成和修剪，可用于分类和回归。Composition:Generation：根据训练数据集生成决策树，生成的决策树尽量大；剪枝：利用验证数据集对生成树进行剪枝，选择最优子树，以损失函数最小作为剪枝标准。生成回归树：平方误差最小化准则平方误差：$\sum_{x_i\inR_{m}}(y_i-f(x_i))^2$找到最优分裂变量（splittingvariable），分裂点（splittingpoint），即求解：$\min_{j,s}[\min_{c_1}\sum_{x_i\inR_1(j,s)}(y_i-c_1)^2+\min_{c_2}\sum_{x_i\inR_2(j,s)}(y_i-c_2)^2]$$R_1(j,s)=\{x|x^{(j)}\les\}$;$R_2(j,s)=\{x|x^{(j)}>s\}$分类树：基尼指数最小化准则基尼指数最小化$Gini\_index(D,a)=\sum^V_{v=1}\frac{|D^v|}{|D|}Gini(D^v)$pruning两步剪枝形成子树序列（损失函数参考下一节剪枝内容容易理解）计算损失函数：$C_\alpha(T)=C(T)+\alpha|T|$从小增加$\alpha$，形成一系列区间$[\alpha_i,\alpha_{i+1})$，得到$T_0$的任意一个内部节点$t$对应区间的最优子树$T_i$，将$t$作为单节点树的损失函数：$C_\alpha(t)=C(t)+\alpha$以$t$为根节点的子树$T_t$的损失函数：$C_\alpha(T_t)=C(T_t)+\alpha|T_t|$$\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$，即当$C_\alpha(T_t)=C_\alpha(t)$时，$T_t$和$t$有同样的损失函数，而$t$的节点更少，所以$t$比$T_t$更可取，$T_t$被剪枝了。因此，$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$，也就是说剪枝后整体损失函数的缩减程度为$\alpha_k=\alpha，T_k=T$，剪枝会一直持续到根节点。在得到的子树序列中通过交叉验证选择最优子树$T_0,T_1,...,T_n$使用独立的验证数据集测试子树序列中各子树的平方误差或基尼指数，最小的考虑到成为最优决策树。步骤设置$k=0，T=T_0$。让$\alpha=+\infty$。从下到上为每个内部节点$t$计算$C(T_t)$、$|T_t|$和$g(t)$和$\alpha$$T_t$，以$t$为根节点$C(T_t)$是训练数据的预测误差，$|T_t|$是$T_t$的叶节点个数$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$,$\alpha=\min(\alpha,g(t))$剪枝$g(t)=\alpha$的内部节点$t$，剪枝的叶子节点$t$决定其以多数投票方式分类，得到树$T$。设$k=k+1,\alpha_k=\alpha,T_k=T$如果$T_k$不是由根节点和两个叶节点组成的树，则返回步骤（2）；否则令$T_k=T_n$使用交叉验证的方法在子树序列$T_0,T_1,...,T_n$4中选择最优子树$T_\alpha$。剪枝过程在上一节Pruningprocessing中已经提到了它在CART算法中的作用，本节将对剪枝过程本身做一些描述。这里主要做一些描述性的介绍，不再做更具体详细的描述。如果不确定，可以自己找一些例子。剪枝是决策树学习算法处理过拟合的主要方法。它可以通过主动移除一些分支来降低过度拟合的风险。基本策略包括“预剪枝”（prepruning）和“后剪枝”（postpruning）两者。预剪枝是指在决策树生成过程中，在划分前对每个节点进行估计。如果当前节点的划分不能带来决策树泛化性能的提升，则停止划分，将当前节点标记为叶节点；后剪枝是从训练集生成一棵完整的决策树，然后自下而上检查非叶子节点，如果将该节点对应的子树替换为叶子节点，则以提高泛化性能决策树，用叶节点替换子树。剪枝方法：通过最小化决策树的整体损失函数（lossfunction）或成本函数（costfunction）来实现。损失函数：$C_\alpha(T)=C(T)+\alpha|T|$$C(T)$：训练数据的预测误差，即模型与训练的拟合程度data（如基尼指数）$|T|$：子树的叶子节点个数，即模型复杂度训练数据和模型的复杂度Larger：更简单Smaller：更复杂的模型$\alpha=0$：只考虑模型和训练数据的拟合度，不考虑模型剪枝的复杂度，即当$\alpha$确定后，选择损失函数为最小的模型，即损失函数最小的子树。决策树生成学习局部模型，而决策树剪枝学习全局模型。5.其他相关内容决策树相关的内容还有一些，但是对于决策树的基础不是很重要，就不介绍了，只提一下词汇。有兴趣的可以参考三本书中的内容。包括，连续值和缺失值处理（《机器学习》4.4，《数据挖掘（导论）完整版》），多元决策树（《机器学习》4.5，《数据挖掘（导论）》）。参考《数据挖掘导论》第4章《统计学习方法（第2版）》第5章《机器学习》第4章
