目录

预备知识

解决分类问题的一般方法

决策树归纳

决策树的工作原理

如何建立决策树

表示属性测试条件的方法

选择最佳划分的度量【需要反复看】

决策树归纳算法

例子：Web机器人检测

决策树归纳的特点

分类任务就是确定对象属于哪个预定义的目标类。本章介绍分类的基本概年，讨论诸如模型的过分拟合等关键问题，并提供评估和比较分类技术性能的方法。

预备知识

分类的类标号必须是离散属性，而回归是一种预测建模任务，其目标属性y是连续的。

分类（classification）：分类任务就是通过学习得到一个目标函数（target function）f，把每个属性集x映射到一个预先定义的类标号y。目标函数也称分类模型（classification model），分类模型可以用于描述性建模和预测性建模。描述性建模，分类模型可以作为解释性的工具，用于区分不同类中的对象，例如有助于说明那些特征决定了物体的分类；预测性建模，分类模型用于预测未知记录的类标号，例如下图所示，可以看作是一个黑箱。

上传失败

分类技术非常适合预测或描述二元或标称类型的数据集，对于序数分类（例如把人分类为高收入、中等收入或低收入组），分类技术不太有效，因为分类技术不考虑隐含在目标类中的序关系。

解决分类问题的一般方法

分类技术（或分类法）是一种根据输入数据集建立分类模型的系统方法，例如决策树分类法、基于规则的分类法、神经网络、支持向量机和朴素贝叶斯分类法。这些技术都使用一种学习算法（learning algorithm）确定分类模型，该模型能够很好地拟合输入数据中类标号和属性集之间的联系。训练算法的主要目标是建立具有很好的泛化能力模型，即建立能够准确地预测未知样本类标号的模型。

下图展示解决分类问题的一般方法，首先需要一个训练集（training set），使用训练集建立分类模型，该模型随后将运用于检验集（test set）。

分类模型的性能根据模型正确和错误预测的检验记录计数进行评估，这些计数放在称作混淆矩阵（confusion matrix）的表格中。表格中的每个表项f_{ij}表示实际类标号为i但被预测为类j的记录数。

虽然混淆矩阵能提供衡量分类模型性能的信息，但是用一个数汇总这些信息更便于比较不同模型的性能。可以使用性能度量（performance metric），如准确率（accuracy），错误率（error rate）：

决策树归纳

决策树（decision tree）分类法。

ps：这里的标题“决策树归纳”的原文是“decision tree induction”，我觉得取induction training 入门训练 的意思更好，个人认为更好的翻译是“决策树入门”。这里好像理解有误，”归纳“大概是指”递归“？

决策树的工作原理

通过体术一系列精心构思的关于检验记录属性的问题，可以解决分类问题，每当一个问题得到答案，后续的问题将随之而来，知道我们得到记录的类标号。这一系列的问题和这些问题的可能回答可以组织成决策树的形式，决策树是一种由结点和有向边组成的层次结构，树中包含三种节点：根结点（root node）、内部结点（internal node）、叶结点（leaf node）或终结点（terminal node）。

如何建立决策树

原则上讲，对于给定的属性集，可以构造的决策树的数目达指数级。尽管某些决策树比其他决策树更准确，但是由于搜索空间是指数规模的，找出最佳决策树在计算上不可行。尽管如此，人们还是开发了一些有效的算法，能够在合理的时间内构造出具有一定准确率的次最优决策树，这些算法通常都采用贪心策略，在选择划分数据的属性时，采取一系列局部最优决策来构造决策树，Hunt算法就是这样的算法。Hunt算法时许多决策树算法的基础，包括ID3、C4.5和CART。

我的理解就是从叶子结点向根结点倒退。

如果属性值的每种组合都在训练数据中出现，并且每种组合都具有唯一的类标号，则Hunt算法是有效的。但是对于大多数实际情况，这些假设太苛刻了，因此，需要附加条件来处理一下情况：

（1）算法的第二步所创建的子女结点可能为空，即不存在与这些结点相关联的记录。如果没有一个训练记录包含与这样的结点相关联的属性值组合，这种情形就可能发生。这是，该结点成为叶结点，类标号为其父结点上训练记录中的多数类。

（2）在第二步，如果与D_{t}相关联的所有记录都具有相同的属性值（目标属性除外），则不可能进一步划分这些记录。在这种情况下，该结点为叶结点，其标号为与该结点相关联的训练记录中的多数类。

决策树归纳的设计问题

表示属性测试条件的方法

决策树归纳算法必须为不同类型的属性提供表示属性测试条件和其对应输出的方法。

二元属性：二元属性的测试条件产生两个可能的输出。

标称属性：由于标称属性有多个属性值，测试条件可以多路划分。而某些决策树算法（如CART）只产生二元划分，则考虑创建k个属性值的二元划分的所有组合。

序数属性：序数属性也可以产生二元或多路划分，只要不违背序数属性值的有序性，就可以对属性值进行分组。

连续属性：对于连续属性来说，测试条件可以是具有二元输出的比较测试（A＜m）或（A≥m），也可以是多个输出范围。对于二元划分，决策树算法必须考虑所有可能的划分点，并从中选择产生最佳划分的点。对于多路划分，算法必须考虑所有可能的连续值区间。可以采用离散化策略，离散化之后，每个离散化区间赋予一个新的序数值，只要保持有序性，相邻的值还可以聚集成较宽的区间。

选择最佳划分的度量【需要反复看】

有很多度量可以用来确定划分记录的最佳方法，这些度量用划分前和划分后记录的类分布定义。

决策树归纳算法

以下为TreeGrowth的决策树归纳算法的框架，输入是训练记录集E和属性集F。算法递归地选择最优地属性来划分数据（步骤7），并扩展树的叶结点（步骤11和12），直到满足结束条件（步骤1）。

建立决策树之后，可以进行树剪枝（tree-pruning），以减小决策树的规模。决策树过大容易受所谓过分拟合（overfitting）现象的影响。通过修剪初始决策树的分支，剪枝有助于提高决策树的泛化能力。

例子：Web机器人检测

决策树归纳的特点

非参数方法：不要求任何先验假设。

许多决策树算法都采取启发式的方法知道对假设空间的搜索。

即使训练集非常大，也可以快速建立模型。

相对容易解释，特别是小型的决策树。

决策树是学习离散值函数的典型代表，然而不能很好地推广到某些特定的布尔问题。

对于噪声的干扰具有相当好的鲁棒性。

冗余属性不会对决策树的准确度造成不利的影响，特征选择计数能够帮助提高决策树的准确率。

数据碎片（data fragmengtation）问题，解决方法是当样本数小于某个特定阈值时，停止分裂。

子树重复问题。

决策边界（decision boundary）是直线，限制了决策树对连续属性之间复杂关系建模的表达能力。斜决策树（oblique decision tree）可以克服以上局限；构造归纳（constructive induction）提供另一种将数据划分成齐次非矩形区域的方法。

研究表明不纯性度量方法的选择对决策树算法的性能影响很小。实际上，树剪枝对最终决策树的影响比不纯性度量的选择的影响更大。

文章来源: dujiahei.blog.csdn.net，作者：dujiahei，版权归原作者所有，如需转载，请联系作者。

原文链接：dujiahei.blog.csdn.net/article/details/102644240