决策树讲解

决策树（理论篇）

定义

由⼀个决策图和可能的结果（包括资源成本和风险组成），⽤来创建到达⽬的的规划。——维基百科

通俗理解

给定⼀个输⼊值，从树节点不断往下⾛，直⾄⾛到叶节点，这个叶节点就是对输⼊值的⼀个预测或者分类。

算法分类

ID3（Iterative Dichotomiser 3，迭代⼆叉树3代）

历史

ID3算法是由Ross Quinlan发明的⽤于⽣成决策树的算法，此算法建⽴在奥卡姆剃⼑上。奥卡姆剃⼑⼜称为奥坎的剃⼑，意为简约之法

则，也就是假设越少越好，或者“⽤较少的东西，同样可以做好的事情”，即越是⼩型的决策树越优于⼤的决策树。当然ID3它的⽬的并不是为

了⽣成越⼩的决策树，这只是这个算法的⼀个哲学基础。

引⼊

信息熵。熵是热⼒学中的概念，是⼀种测量在动⼒学⽅⾯不能做功的能量总数，也就是当总体熵的增加，其做功能⼒也下降，熵的量度

正是能量退化的指标——维基百科。⾹农将“熵”的概念引⼊到了信息论中，故在信息论中被称为信息熵，它是对不确定性的测量，熵越⾼，

不确定性越⼤，熵越低，不确定性越低。

那么到底何为“信息熵”？它是衡量信息量的⼀个数值。那么何⼜为“信息量”？我们常常听到某段⽂字信息量好⼤，某张图信息量好⼤，实

际上指的是这段消息（消息是信息的物理表现形式，信息是其内涵——《通信原理》）所包含的信息很多，换句话说传输信息的多少可以采

⽤“信息量”去衡量。这⾥的消息和信息并不完全对等，有可能出现消息很⼤很多，但所蕴含有⽤的信息很少，也就是我们常说的“你说了那么

多（消息多），但对我来说没⽤（信息少，即信息量少）”。这也进⼀步解释了消息量的定义是传输信息的多少。

进⼀步讲，什么样的消息才能构成信息呢？

我们为什么会常常发出感叹“某段⽂字的信息量好⼤”，得到这条消息时是不是有点出乎你的意料呢？⽐如，X男和X男在同⼀张床上发出

不可描述的声⾳，这段消息对于你来讲可能就会发出“信息量好⼤”的感叹。再⽐如，某情侣在同⼀张床上发出不可描述的声⾳，这段消息对

3 基于决策树的数据挖掘分析

3.1 决策树分类概述

决策树是一种分类技术。决策树是一种类似于流程图的树结构：其中每个内部节点(非数叶节点)表示在一个属性上的测试，每个分支代表一个测试输出，而每个叶节点(或终节点)存放一个类标号，数的最顶层节点是根节点。决策树的根节点是所有样本信息量最大的属性，数的中间节点是以该节点为根的子树所包含的样本子集中信息量最大的属性。

决策树分类技术能直观的表现知识，容易理解；决策树的构造不需要任何领域知识和参数设置，因此适合于探测式知识发现。决策树可以处理高维数据，获得的知识用树的形式表示很直观，容易理解。

3.2 决策树的基本算法

决策树的算法有很多种，例如ID3、CART、C4.5、PUBLIC、SLIQ、SPRINT、C5.0等等，早期最著名的决策树算法是由1986年Quinlan提出的ID3算法，后来经过科研工作者的共同努力，对算法进行了多方面的改善，本文决策树模型采用C4.5算法，上说C4.5只能是ID3的一个改进算法。

ID3算法

1.概念提取算法CLS

1) 初始化参数C={E},E包括所有的例子,为根.

2) IF C中的任一元素e同属于同一个决策类则创建一个叶子

节点YES终止.

ELSE 依启发式标准,选择特征Fi={V1,V2,V3,．．．Vn}并创建

判定节点

划分C为互不相交的N个集合C1,C2,C3,．．．,Cn；

3) 对任一个Ci递归.

2. ID3算法

1) 随机选择C的一个子集W (窗口).

2) 调用CLS生成W的分类树DT(强调的启发式标准在后).

3) 顺序扫描C搜集DT的意外(即由DT无法确定的例子).

4) 组合W与已发现的意外,形成新的W.

决策树构成的基本要素：

决策树的构成有四个要素：包括决策点、方案枝、决策节点、概率枝。

决策树：

决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy=系统的凌乱程度，使用算法ID3,C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

分类树（决策树）是一种十分常用的分类方法。他是一种监督学习，所谓监督学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。

组成： □——决策点，是对几种可能方案的选择，即最后选择的最佳方案。如果决策属于多级决策，则决策树的中间可以有多个决策点，以决策树根部的决策点为最终决策方案。

○——状态节点，代表备选方案的经济效果（期望值），通过各状态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。

△——结果节点，将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。

1 决策树计算方法例题讲解

决策树是一种常用的机器学习算法，用于分类和回归问题。它通过构建一棵树形结构来进行决策，每个内部节点表示一个特征，每个叶子节点表示一个类别或一个数值。下面我将通过一个具体的例题来详细讲解决策树的计算方法。

假设我们有一个数据集，其中包含了一些水果的特征（颜色、形状、纹理）以及对应的标签（是否为橙子）。我们希望通过这些特征来构建一个决策树模型，能够根据水果的特征预测其是否为橙子。

首先，我们需要将数据集划分为训练集和测试集。训练集用于构建决策树模型，测试集用于评估模型的性能。

1.特征选择

在构建决策树之前，我们需要选择一个特征作为根节点。常用的特征选择方法有信息增益、信息增益比、基尼指数等。这里我们使用信息增益来选择特征。

信息增益衡量了在给定特征条件下，类别的不确定性减少的程度。具体计算信息增益的步骤如下：

-计算整个数据集的熵（entropy）：

-首先，统计每个类别的样本数量。

-然后，计算每个类别的概率，并求和。

-最后，根据概率计算整个数据集的熵。

-对于每个特征，计算其对应的信息增益：

2 -首先，针对该特征的每个取值，将数据集划分为不同的子集。

-然后，计算每个子集的熵和权重，并求和。

-最后，用整个数据集的熵减去子集的熵和权重的乘积，得到信息增益。

选择具有最大信息增益的特征作为根节点。

2.构建决策树

选择完根节点后，我们需要递归地构建决策树。具体步骤如下：

-对于每个内部节点，选择一个最佳的特征作为其子节点。

-将数据集根据该特征的不同取值划分为多个子集。

-对于每个子集，如果所有样本都属于同一类别，则将该子集设为叶子节点，并标记为该类别。

-否则，继续递归地构建决策树，直到满足停止条件（如达到预定深度或无法继续划分）。

3.决策树的剪枝

构建完决策树后，我们需要进行剪枝操作，以避免过拟合现象。剪枝可以通过预剪枝和后剪枝来实现。

-预剪枝：在构建决策树的过程中，在划分子集之前，先进行验证集的测试，如果测试结果不好，则停止划分，将当前节点设为叶子节点。