机器学习算法_决策树

一、决策树的简介

• 核心思想: 与线性回归、逻辑回归不同，决策树将特征视为一系列条件，通过数据学习这些条件划分方式

• 特征处理: 特征作为分支条件，划分规则完全从数据中自动学习得到

• 决策树是一种树形结构：树中每个内部节点表示一个特征上的判断，每个分支表示一个判断结果，每个叶子节点代表一种分类结果

• 决策树的建立过程

  • 特征选择：选取有较强分类能力的特征
  • 决策树生成：根据选择的特征生成决策树
  • 决策树也易过拟合，采用剪枝的方法（一般是从深层开始剪枝）缓解过拟合

二、ID3决策树

混乱程度越大，则熵值越大；包含信息比较多，则比较混乱，则熵值越大

1.信息熵

• 熵（Entropy）:信息论中代表随机变量不确定度的度量

  • 熵越大，数据的不确定性度越高，信息就越多
  • 熵越小，数据的不确定性越低

• 从有序到无序的过程，就是熵增的过程

• 计算方法：$H(x)=-{\sum }_{i=0}^{n}P(x_i){\log }_{2}P(x_i)$，其中$P(x_i)$表示数据中类别出现的概率，$H(x)$表示信息的信息熵值

• 我们要尽可能地使信息熵减少得越多越好

2.信息增益

• 定义：特征a对训练数据集D的信息增益$g(D,a)$，定义为集合$D$的熵$H(D)$与特征a给定条件下$D$的熵$H(D|a)$之差

• 公式：$g(D,A)=H(D)-H(D|A)$（信息增益=熵-条件熵）

• 条件熵（即在熵值前面乘以条件所占比例）：$H(D|A)={\sum }_{v=1}^n\frac{D^V}{D}H(D^v)={\sum }_{v=1}^n\frac{D^V}{D}{\sum }_{k=1}^{kV}\log \frac{c^{kV}}{D^V}$

• 最终求得信息增益之后，找信息增益最大的结果作为分支

3.ID3决策树构建流程

• 计算每个特征的信息增益
• 使用信息增益最大的特征将数据集拆分为子集
• 使用该特征（信息增益最大的特征）作为决策树的一个节点
• 使用剩余特征对子集重复上述（1，2，3）过程

4.ID3决策树的缺点

• 对类别较多的特征比较青睐

三、C4.5决策树

1.信息增益率

• $信息增益率=\frac{信息增益}{特征熵}$
• 计算方法：$Gain\_Ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$
  • $Gain\_Ratio(D,a)$ 信息增益率
  • $IV(a)=-{\sum }_{v=1}^n\frac{D^V}{D}Ent(\frac{D^V}{D})$
• 信息增益率的本质
  • 特征的信息增益/特征的内在信息
  • 相当于对信息增益进行修正，增加了一个惩罚系数
  • 特征取值个数较多时，惩罚系数较小；特征取值个数较少时，惩罚系数较大
  • 惩罚系数：数据集D以特征a作为随机变量的熵的倒数

四、CART分类树

• 回归任务中数据是连续的，而前面两种树不适合用于连续型数据，故要做回归任务，应该是选择CART树
• CART既可以用于分类，也可以用于回归
• CART回归树使用平方误差最小化策略
• CART分类生成树采用的基尼指数最小化策略

1.Gini指数

• 基尼值Gini（D）：从数据集D中随机抽两个样本，其类别标记不一致的概率，故Gini（D）值越小，数据集D的纯度越高

  $Gini(D)={\sum }_{k=1}^{|y|}{\sum }_{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}=1-{\sum }_{k=1}^{|y|}{p}_k^2$

• 基尼指数Gini_index(D)：选择使划分后基尼系数最小的属性作为最优划分属性

  $Gini\_index(D,a)={\sum }_{v=1}^V\frac{D^v}{D}Gini(D^v)$

• 注意：基尼指数值越小，则说明优先选择该特征

• 在有多个类别时，应该划分为多个二类分来求Gini指数

2.当特征取值是连续的时候，应该怎样找到划分节点？

• 先将数值型属性升序排列，以相邻中间值作为待确定分裂点

• 以中间值将样本分为两部分，计算基尼指数

• 以此类推计算所有分割点的基尼指数，以最小基尼指数对应的值来进行划分

五、CART回归树

• CART回归树和CART分类树的不同之处：
  • CART分类树预测输出的是一个离散值，CART回归树预测输出的是一个连续值
  • CART分类树使用基尼指数进行划分，构建树的依据，CART回归树使用平方损失
  • 分类树使用叶子节点多数类别作为预测类别，回归树则采用叶子节点里均值作为预测输出
• CART回归树的平方损失：$Loss(y,f(x))=(f(x)-y{)}^2$
  • 应该选择平方差小的作为分支
  • 每一个叶子结点的输出为：挂在该节点上的所有样本的均值
• CART回归树构建过程
  • 选择一个特征，将该特征的值进行排序，取相邻点计算均值作为待划分点
  • 根据所有划分点，将数据集分为两部分R1，R2
  • R1，R2两部分的平方损失相加作为该切分点平方损失
  • 取最小的平方损失的划分点，作为当前特征的划分点
  • 以此计算其他特征的最优划分点，以及该划分点对应的损失值
  • 在所有的特征的划分点中，选择出最小平方损失的划分点，作为当前树的分裂点

六、剪枝

1.决策树正则化——剪枝

• 剪枝目的：决策树剪枝是一种防止决策树过拟合的一种正则化方法，提高其泛化能力

• 剪枝：将子树的节点全部删掉，使用叶子节点来替代

• 剪枝方法

  • 预剪枝：只在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化能力提升，则停止划分并将当前节点划分为叶子节点（划分后的精度相对划分前的精度不变或减小，则可以进行预剪枝）
  • 后剪枝：先从训练集生成一棵完整的决策树，然后自底向上对非叶节点进行考察，若该节点对应的子树替换为叶子节点能带来决策树泛化性能提升，则将该子树替换为叶节点

2.剪枝技术对比