机器学习——决策树_单变量决策树和多变量决策树的区别

一、决策树

1.定义

        决策树是一种基于树形结构的分类模型，它通过将数据集划分为不同的分支和叶节点来进行决策。

        其中每个节点代表一个特征或属性，每个分支代表一个可能的决策规则，而叶子节点代表最终的类别或结果。决策树通过一系列的问题和条件来分割数据集，以便最终能够对新的数据点进行分类或预测。

2.基本流程

        决策树的生成是一个自根结点一直到叶结点的递归生成过程，其基本流程遵循简单而直观的 分而治之 策略，也可以将决策树看成是一个if-then规则的集合，根据规则，逐次判断条件，最终依据路径归于特定类别。如下图：

• 当前结点包含的样本全部属于同一个类别，无需划分；（第3行）
• 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分。在这种情况下，把当前结点标记为叶结点，并且将其类别设定为该结点所含样本最多的类别；（第6行）
• 当前结点包含的样本集和为空，当前结点标记为叶节点，类别=该结点的父节点所含样本最多的类别 （第12行）

3. 最优划分属性

        在决策树的构建过程中，选择最佳划分属性（特征）是非常重要的。一般而言我们希望选择一个属性之后，其分支节点所包含的样本尽可能属于同一类别，即结点的纯度 (Purity) 越来越高。

        简单来说，当我们有了输入数据，并且输入的数据有自己的属性特征。那么决策要做的就是决定用那个特征来划分特征空间。并且我们希望节点内部样本的相似程度或同质性较高，即提高纯度。

经典的属性划分方法：

• 信息增益： ID 3
• 增益率：C 4.5
• 基尼指数：CART

3.1  信息熵

        在介绍属性划分方法之前，需先引入一个概念：信息熵。

        信息熵是度量样本集合纯度最常用的一种指标，假定当前样本集合D中第k类样本所占的比例为 pk (K=1, 2, ..., |y|) ，则D的信息熵定义为

Ent(D)的值越小，则D的纯度越高。Ent(D)的最小值为0，最大值为log2|y|

3.2 信息增益- ID 3

         信息增益（information gain）：离散属性a有V个可能的取值{a1, a2, ..., aV}，用a来进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为av的样本，记为Dv。则可计算出用属性a对样本集D进行划分所获得的“信息增益”：一般而言，信息增益越大则意味着用属性 a 来进行划分所获得的“纯度提升”越大（信息增益越大越好）。

3.3 增益率- C 4.5

        信息增益比（information gain ratio），也称为增益率：信息增益的大小是相对训练数据集而言的，并没有绝对意义。在分类问题困难时，也就是说在训练数据即的经验熵大的时候，信息增益值会偏大，反之信息增益值会偏小。

 

 

   称为属性a的“固有值” ，属性a的可能取值数目越多（即V越大），则IV(a)的值通常就越大 。

3.4 基尼指数-CART

        分类问题中，假设D有K个类，样本点属于第k类的概率为