本文共 2375 字，大约阅读时间需要 7 分钟。

1. 目的：为了让模型的不确定性降低的越快越好
2. 三个过程：特征选择、决策树的生成、决策树的剪枝
   （1）特征选择：
   信息熵：随机变量不确定性的度量
   $H(X)=-\sum_{i=1}^np_ilogp_i$
   信息增益：（ID3算法），得知特征X的信息而使类Y的信息的不确定减少的程度
   $g(D,A)=H(D)-H(D|A)$
   information gain作为划分训练数据集的特征，存在偏向于选择取值较多的特征问题。
   （对于取值多的属性如连续型数值，这个单独的属性就可以划分所有的样本，使得所有分支下的样本集合都是“纯的”，最极端的情况是每个叶子节点只有一个样本。这样的划分是极为不合理的。）
   信息增益率：（C4.5算法），在信息增益的基础上除了一项split information,来惩罚值更多的属性。
   $g_R(D,A) = \frac{g(D,A)}{H_A(D)}$
   GINI指数：（CART算法）
   $Gini(D)=1-\sum_{k=1}^{K}p_k^2$
   （2）决策树的生成
   递归选择最优特征（信息增益、信息增益比最大，GINI最小）
   递归停止条件：
   a. 当前结点包含的样本全部属于同一个类别，无需划分
   b.当前的属性集为空，或是所有样本在所有属性上的取值相同，无法划分（小于或者大于某个阈值）
   c.当前结点包含的样本集合为空，不能划分
   （3）决策树的剪枝
   目的：减轻过拟合现象
   方法：预剪枝和后剪枝
   预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
   后剪枝是先从训练集合生成一棵完整的决策树，然后自顶向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点带来决策树泛化性能提升，则将该子树替换为叶结点。
   预剪枝基于贪心本质禁止这些分支展开，给预剪枝决策树带来欠拟合的风险
   后剪枝基于极小化决策树整体的损失函数的思想进行剪枝，时间开销较大；
3. 目标函数：最小化损失函数
4. 损失函数：正则化的极大似然函数
   $C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$
   $|T|$为叶子结点的个数，t为T的叶结点，$N_t$为叶结点上样本个数，其中$k$类的样本点有$N_{tk}$个
   $N_t(T)=-\sum_k\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$
   损失化左边为经验风险最小化，右边实现了结构风险最小化（正则化项）
5. 决策回归树CART(二叉决策树）
   准则：平方误差最小化
   将输入空间划分为M个单元，每个单元有一个固定的输出值（有点像变成一个多分类问题，只是现在结果不是一个类而是一个值）
   过程：启发式
   a. 固定输入变量j寻找最优切分点s，遍历所有输入变量，寻找最优的切分变量j
   minj,s[minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2] m i n j , s [ m i n c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + m i n c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ]
   $$min_{j,s}[min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$$
   b. 用$(j,s)$划分区域并决定相应的输出值
   $c_m=ave(y_i|x_i \in R_m)$
   c. 递归调用a,b
   d. $f(x)=\sum_{m=1}{M}c_mI(x\in R_m)$
6. 决策树算法对特征的筛选过程
   对于离散变量，有求信息增益最大、信息增益率最大和Gini最小三种方法
   对于连续变量，首先将变量的值进行升序排列，每对相邻值的重点作为可能的分离点。对于每个划分，选择具有最小期望信息要求的点作为分裂点来进行后续的决策树的分裂。
7. 产生决策树过拟合的原因和解决办法
   a. 决策树生成过多考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树【剪枝操作】
   b. 较多的特征【减少特征，计算每个特征和相应变量的相关性】
   c. 噪声【K-folds交叉验证】
8. 决策树的优缺点
   优点：
   可解释性
   分类速度快（针对类别型变量和次序型变量）
   可以处理区间型变量（Interval)（训练速度视数据规模而定）
   对数据分布没有特别严格的要求
   对缺失值很宽容
   不容易受数据中极端值（异常值）影响
   可以同时对付数据中线性和非线性的关系
   可作为有效工具来帮助其他模型挑选自变量
   使用信息原理对大样本的属性进行信息量分析，并计算各属性的信息量，找出反映类别的重要属性，可准确、高效地发现哪些属性对分类最有意义。（如区间型变量的分箱操作）
   缺点：
   贪心
   连续型目标变量不太适用
   缺乏诸如回归或聚类丰富多样的检测指标和评价方法
   过拟合（某些自变量类别数量较多或者区间型自变量，需要数据转换，分箱或多模型验证和测试）
   对training set rotation敏感，可以用pca解决或者斜决策树
   对训练集数据的微小变化敏感
   决策树算法对区间型自变量进行分箱操作时，无论是否考虑了顺序因素，都有可能因为分箱丧失某些重要的信息。尤其是当分箱前的区间型变量与目标变量有明显的线性关系时，这种分箱操作造成的信息损失更为明显。

转载地址：http://ffqmi.baihongyu.com/