新的决策树构造方法

决策树算法介绍（DOC）3.1 分类与决策树概述3.1.1 分类与预测分类是⼀种应⽤⾮常⼴泛的数据挖掘技术，应⽤的例⼦也很多。

例如，根据信⽤卡⽀付历史记录，来判断具备哪些特征的⽤户往往具有良好的信⽤；根据某种病症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。

这些过程的⼀个共同特点是：根据数据的某些属性，来估计⼀个特定属性的值。

例如在信⽤分析案例中，根据⽤户的“年龄”、“性别”、“收⼊⽔平”、“职业”等属性的值，来估计该⽤户“信⽤度”属性的值应该取“好”还是“差”，在这个例⼦中，所研究的属性“信⽤度”是⼀个离散属性，它的取值是⼀个类别值，这种问题在数据挖掘中被称为分类。

还有⼀种问题，例如根据股市交易的历史数据估计下⼀个交易⽇的⼤盘指数，这⾥所研究的属性“⼤盘指数”是⼀个连续属性，它的取值是⼀个实数。

那么这种问题在数据挖掘中被称为预测。

总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。

3.1.2 决策树的基本原理1.构建决策树通过⼀个实际的例⼦，来了解⼀些与决策树有关的基本概念。

表3-1是⼀个数据库表，记载着某银⾏的客户信⽤记录，属性包括“姓名”、“年龄”、“职业”、“⽉薪”、......、“信⽤等级”，每⼀⾏是⼀个客户样本，每⼀列是⼀个属性（字段）。

这⾥把这个表记做数据集D。

银⾏需要解决的问题是，根据数据集D，建⽴⼀个信⽤等级分析模型，并根据这个模型，产⽣⼀系列规则。

当银⾏在未来的某个时刻收到某个客户的贷款申请时，依据这些规则，可以根据该客户的年龄、职业、⽉薪等属性，来预测其信⽤等级，以确定是否提供贷款给该⽤户。

这⾥的信⽤等级分析模型，就可以是⼀棵决策树。

在这个案例中，研究的重点是“信⽤等级”这个属性。

给定⼀个信⽤等级未知的客户，要根据他/她的其他属性来估计“信⽤等级”的值是“优”、“良”还是“差”，也就是说，要把这客户划分到信⽤等级为“优”、“良”、“差”这3个类别的某⼀类别中去。

决策树（理论篇）定义 由⼀个决策图和可能的结果（包括资源成本和风险组成），⽤来创建到达⽬的的规划。

——维基百科通俗理解 给定⼀个输⼊值，从树节点不断往下⾛，直⾄⾛到叶节点，这个叶节点就是对输⼊值的⼀个预测或者分类。

算法分类ID3（Iterative Dichotomiser 3，迭代⼆叉树3代）历史 ID3算法是由Ross Quinlan发明的⽤于⽣成决策树的算法，此算法建⽴在奥卡姆剃⼑上。

奥卡姆剃⼑⼜称为奥坎的剃⼑，意为简约之法则，也就是假设越少越好，或者“⽤较少的东西，同样可以做好的事情”，即越是⼩型的决策树越优于⼤的决策树。

当然ID3它的⽬的并不是为了⽣成越⼩的决策树，这只是这个算法的⼀个哲学基础。

引⼊ 信息熵。

熵是热⼒学中的概念，是⼀种测量在动⼒学⽅⾯不能做功的能量总数，也就是当总体熵的增加，其做功能⼒也下降，熵的量度正是能量退化的指标——维基百科。

⾹农将“熵”的概念引⼊到了信息论中，故在信息论中被称为信息熵，它是对不确定性的测量，熵越⾼，不确定性越⼤，熵越低，不确定性越低。

那么到底何为“信息熵”？它是衡量信息量的⼀个数值。

那么何⼜为“信息量”？我们常常听到某段⽂字信息量好⼤，某张图信息量好⼤，实际上指的是这段消息（消息是信息的物理表现形式，信息是其内涵——《通信原理》）所包含的信息很多，换句话说传输信息的多少可以采⽤“信息量”去衡量。

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

这也进⼀步解释了消息量的定义是传输信息的多少。

进⼀步讲，什么样的消息才能构成信息呢？ 我们为什么会常常发出感叹“某段⽂字的信息量好⼤”，得到这条消息时是不是有点出乎你的意料呢？⽐如，X男和X男在同⼀张床上发出不可描述的声⾳，这段消息对于你来讲可能就会发出“信息量好⼤”的感叹。

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

决策树原理简介一、什么是决策树决策树是一种机器学习中常用的分类和回归方法。

它通过对样本的特征进行一系列的判断，最终达到对样本进行分类或预测的目的。

决策树是一种可视化的算法，其结果可以形成一棵树状结构，每个内部节点代表一个特征判断，每个叶子节点代表一种分类或回归结果。

决策树在实践中被广泛应用，特别适用于复杂问题的决策以及数据探索性分析。

二、决策树的构造过程1. 特征选择决策树的构造过程从根节点开始，每次选择一个最好的特征作为当前节点的分裂条件。

特征选择的目标是使得对样本的划分尽可能的准确，即分类结果的纯度最高。

2. 样本划分选定了特征后，决策树根据该特征的取值将样本划分为不同的子集，每个子集对应一个子树。

划分的方式可以是二分法或多分法，具体取决于特征的类型和取值个数。

划分后，每个子树都会继续进行特征选择和样本划分的过程，直到满足终止条件。

3. 终止条件决策树的构建直到满足以下终止条件之一时才会停止： - 当前节点包含的样本属于同一类别。

- 当前节点包含的样本属于同一回归结果。

- 没有更多的特征可供选择，或者样本已经被划分得非常纯净。

4. 剪枝操作决策树的构建可能会造成过拟合现象，即模型过于复杂，对训练集的拟合程度很高，但是在新的数据上表现较差。

为了解决过拟合问题，可以对决策树进行剪枝操作。

剪枝过程可以通过删除一些节点或合并一些相邻节点来实现，目的是降低模型的复杂度，提高泛化能力。

三、决策树的优缺点1. 优点•决策树易于理解和解释，由于其树状结构，可以直观地表示特征间的关系。

•决策树能够处理混合数据类型，不需要对数据进行归一化处理。

•决策树算法可以灵活处理大型数据集。

2. 缺点•决策树容易产生过拟合，特别是在数据的噪声较大或特征维度较高时。

•决策树对于那些取值较多的属性有偏好，因为它通常选择那些能够更好地区分样本的特征进行分裂。

•决策树的稳定性较差，数据的微小变化可能导致生成完全不同的树。

四、决策树的应用场景决策树具有广泛的应用场景，包括但不限于以下几个方面：1. 医学诊断决策树可以用于医学诊断，根据患者的症状和检查结果判断患者的疾病类别。

分类分析--决策树（经典决策树、条件推断树）分类分析--决策树决策树是数据挖掘领域中的常⽤模型。

其基本思想是对预测变量进⾏⼆元分离，从⽽构造⼀棵可⽤于预测新样本单元所属类别的树。

两类决策树：经典树和条件推断树。

1 经典决策树经典决策树以⼀个⼆元输出变量（对应威斯康星州乳腺癌数据集中的良性/恶性）和⼀组预测变量（对应九个细胞特征）为基础。

具体算法如下：(1) 选定⼀个最佳预测变量将全部样本单元分为两类，实现两类中的纯度最⼤化（即⼀类中良性样本单元尽可能多，另⼀类中恶性样本单元尽可能多）。

如果预测变量连续，则选定⼀个分割点进⾏分类，使得两类纯度最⼤化；如果预测变量为分类变量（本例中未体现），则对各类别进⾏合并再分类。

(2) 对每⼀个⼦类别继续执⾏步骤(1)。

(3) 重复步骤(1)~(2)，直到⼦类别中所含的样本单元数过少，或者没有分类法能将不纯度下降到⼀个给定阈值以下。

最终集中的⼦类别即终端节点（terminal node）。

根据每⼀个终端节点中样本单元的类别数众数来判别这⼀终端节点的所属类别。

(4) 对任⼀样本单元执⾏决策树，得到其终端节点，即可根据步骤3得到模型预测的所属类别。

上述算法通常会得到⼀棵过⼤的树，从⽽出现过拟合现象。

结果就是，对于训练集外单元的分类性能较差。

为解决这⼀问题，可采⽤10折交叉验证法选择预测误差最⼩的树。

这⼀剪枝后的树即可⽤于预测。

R中的rpart包⽀持rpart()函数构造决策树，prune()函数对决策树进⾏剪枝。

下⾯给出判别细胞为良性或恶性的决策树算法实现。

（1）使⽤rpart()函数创建分类决策树：#⽣成树：rpart()函数可⽤于⽣成决策树library(rpart)set.seed(1234)dtree <- rpart(class ~ ., data=df.train, method="class",parms=list(split="information"))#rpart() 返回的cptable值中包括不同⼤⼩的树对应的预测误差，因此可⽤于辅助设定最终的树的⼤⼩。

4.3 决策树/分类树(Decision or Classification Trees)
决策树是一个多阶段决策过程，它不是一次用样本的所有特征进
行决策，而是逐次地用各个特征分量进行决策。

例如，一个6维向量x
=
(x 1, x 2, x 3, x 4, x 5, x 6)T ，决策树如图4.5所示。

决策树的构造一般有下列3个步骤：
(1) 为每一个内部节点(Internal Node)选择划分规则。

(2) 确定终节点(Terminal Nodes)。

(3) 给终节点分配类别标签(Class Labels)。

例如，根据图 4.6a 所示的二维数据分布情况，可以画出图 4.6b 所示的决策树。

x 6<2
x 5<5
x 4<1 x 1<2
ω1 ω2
ω1
ω3 ω2 Yes No
Yes Yes
Yes No
No
No
图4.5 一个决策树示意图
我们可以利用决策树的原理来解决多类别问题，例如，用一个线性分类器（例如Fisher 分类器）解决多类别问题。

图4.6a 一个二维空间样本分布示例
图4.6b 对应的决策树
x k >b 2
x k <b 1
x i <a 2 x k >b 3 ω8
ω9 ω6
ω4
Yes No
Yes Yes
Yes
No
No No x i >a 1
ω10
ω1 Yes
No。

决策树的构建步骤决策树算法应用的完整流程应包含建树和应用。

建树是从经验数据中获取知识，进行机器学习，建立模型或者构造分类器，是决策树算法的工作重点，通常又将其分为建树和剪枝两个部分。

而应用则比较简单，利用建好的决策树模型分类或者预测新数据即可。

先介绍一下建树。

建树也就是决策树算法建模的主体过程，或者说，建树便是主要规则的产生过程。

决策树构建的基本步骤如表3-3所示。

表3-3 决策树构建的基本步骤决策树的变量可以有两种：数字型(Numeric)和名称型(Nominal)。

(1)数字型：变量类型是整数或浮点数，如前面例子中的“年龄”。

用“>”“＜”等作为分割条件（排序后，利用已有的分割情况，可以优化分割算法的时间复杂度）。

(2)名称型：类似编程语言中的枚举类型，变量只能从有限的选项中选取。

如何评估分割点的好坏？如果一个分割点可以将当前的所有节点分为两类，使得每一类都很“纯”，也就是同一类的记录较多，那么就是一个好分割点。

树的主体建好后，接下来便是对其剪枝。

所谓剪枝，就是在树的主体上删除过多的条件或者直接删除一些不必要的子树，提高树的性能，确保精确度，提高其可理解性。

同时，在剪枝过程中还要克服训练样本集的数据噪声，尽可能地消除噪声造成的影响。

决策树的剪枝一般通过极小化决策树整体的损失函数或代价函数来实现。

决策树剪枝常用的方法有两种：预剪枝(Pre-Pruning)和后剪枝(Post-Pruning)。

预剪枝是指根据一些原则尽早地停止树的增长，如树的深度达到用户所要的深度、节点中样本个数少于用户指定个数等。

预剪枝在建树的过程中决定是否需要继续划分或分裂训练样本来实现提前停止树的构造，一旦决定停止分支，就将当前节点标记为叶节点。

这样可以有效减少建立某些子树的计算代价。

运用这一策略的代表性算法有PUBLIC算法。

预剪枝的核心问题是，如何事先指定树的最大深度，如果设置的最大深度不恰当，那么将会导致过于限制树的生长，使决策树的表达式规则趋于一般，不能更好地对新数据集进行分类和预测。

决策树和朴素贝叶斯算法简介本节主要介绍数据挖掘中常见的分类方法决策树和朴素贝叶斯算法。

决策树算法决策树（Decision Tree，DT）分类法是一个简单且广泛使用的分类技术。

决策树是一个树状预测模型，它是由结点和有向边组成的层次结构。

树中包含3种结点：根结点、内部结点和叶子结点。

决策树只有一个根结点，是全体训练数据的集合。

树中的一个内部结点表示一个特征属性上的测试，对应的分支表示这个特征属性在某个值域上的输出。

一个叶子结点存放一个类别，也就是说，带有分类标签的数据集合即为实例所属的分类。

1. 决策树案例使用决策树进行决策的过程就是，从根结点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子结点，将叶子结点存放的类别作为决策结果。

图1 是一个预测一个人是否会购买电脑的决策树。

利用这棵树，可以对新记录进行分类。

从根结点（年龄）开始，如果某个人的年龄为中年，就直接判断这个人会买电脑，如果是青少年，则需要进一步判断是否是学生，如果是老年，则需要进一步判断其信用等级。

图1 预测是否购买电脑的决策树假设客户甲具备以下4 个属性：年龄20、低收入、是学生、信用一般。

通过决策树的根结点判断年龄，判断结果为客户甲是青少年，符合左边分支，再判断客户甲是否是学生，判断结果为用户甲是学生，符合右边分支，最终用户甲落在“yes”的叶子结点上。

所以预测客户甲会购买电脑。

2. 决策树的建立决策树算法有很多，如ID3、C4.5、CART 等。

这些算法均采用自上而下的贪婪算法建立决策树，每个内部结点都选择分类效果最好的属性来分裂结点，可以分成两个或者更多的子结点，继续此过程直到这棵决策树能够将全部的训练数据准确地进行分类，或所有属性都被用到为止。

1）特征选择按照贪婪算法建立决策树时，首先需要进行特征选择，也就是使用哪个属性作为判断结点。

选择一个合适的特征作为判断结点，可以加快分类的速度，减少决策树的深度。