“当代玄学”外衣下的真相——决策树算法

专注锁定 静待时机

当前数据挖掘领域中存在决策树算法、贝叶斯网络算法、人工神经网络算法、支持向量机以及其它一些基于关联规则的算法，它们涉及到数据的聚类、分类、关联规则、排序等方面。今天就跟大家说说基于树的分类算法——决策树。

决策树算法

决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。

决策树方法最早产生于上世纪60年代，到70年代末。由J Ross Quinlan提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。

决策树算法构造决策树来发现数据中蕴涵的分类规则．如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步，决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第二步，决策树的剪枝：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数据集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除。

同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。

CART算法由以下两步组成：

（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；

（2）决策树剪枝：用验证数据集对己生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

策树算法采用自上至下递归建树的技术，该算法的产生源于CLS系统，即概念学习系统，下图展示一个CLS系统的简易模型。该模型是决策树发展的理论基础，该模型定义了一个学习系统的基本结构。

特征选择

CART算法的特征选择就是基于基尼系数得以实现的，其选择的标准就是每个子节点达到最高的纯度，即落在子节点中的所有观察都属于同一个分类。下面简单介绍一下有关基尼系数的计算问题：

假设数据集D中的因变量有m个水平，即数据集可以分成m类群体，则数据集D的基尼系数可以表示为：

由于CART算法是二叉树形式，所以一个多水平(m个水平)的离散变量（自变量）可以把数据集D划分为2^m-2种可能。举个例子也许能够明白：如果年龄段可分为，则其子集可以是、、、、、、、{}。其中和空集{}为无意义的Split，所以6=2^3-2。

对于一个离散变量来说，需要计算每个分区不纯度的加权和，即对于变量A来说，D的基尼系数为：

对于一个连续变量来说，需要将排序后的相邻值的中点作为阈值（分裂点），同样使用上面的公式计算每一个分区不纯度的加权和。

根据特征选择的标准，只有使每个变量的每种分区的基尼系数达到最小，就可以确定该变量下的阈值作为分裂变量和分裂点。如果这部分读的不易理解的话，可参考《数据挖掘：概念与技术》一书，书中有关于计算的案例。

实例

为了适应市场的需要，某地准备扩大电视机生产。市场预测表明：产品销路好的概率为0.7；销路差的概率为0.3。备选方案有三个：第一个方案是建设大工厂，需要投资600万元，可使用10年；如销路好，每年可赢利200万元；如销路不好，每年会亏损40万元。第二个方案是建设小工厂，需投资280万元；如销路好，每年可赢利80万元；如销路不好，每年也会赢利60万元。第三个方案也是先建设小工厂，但是如销路好，3年后扩建，扩建需投资400万元，可使用7年，扩建后每年会赢利190万元。

各点期望：

点②：0.7×200×10+0.3×（-40）×10-600（投资）=680（万元）

点⑤：1.0×190×7-400=930（万元）

点⑥：1.0×80×7=560（万元）

比较决策点4的情况可以看到，由于点⑤（930万元）与点⑥（560万元）相比，点⑤的期望利润值较大，因此应采用扩建的方案，而舍弃不扩建的方案。把点⑤的930万元移到点4来，可计算出点③的期望利润值。

点③：0.7×80×3+0.7×930+0.3×60×（3+7）-280 = 719（万元）

最后比较决策点1的情况。由于点③（719万元）与点②（680万元）相比，点③的期望利润值较大，因此取点③而舍点②。这样，相比之下，建设大工厂的方案不是最优方案，合理的策略应采用前3年建小工厂，如销路好，后7年进行扩建的方案。

剪枝

剪枝是为了防止模型过拟合，而更加适合样本外的预测。一般决策树中的剪枝有两种方式，即预剪枝和后剪枝，而后剪枝是运用最为频繁的方法。后剪枝中又分为损失矩阵剪枝法和复杂度剪枝法，对于损失矩阵剪枝法而言，是为了给错误预测一个惩罚系数，使其在一定程度上减少预测错误的情况；对于复杂度剪枝法而言，就是把树的复杂度看作叶节点的个数和树的错误率（错误分类观察数的比例）的函数。

基本思想

1、树以代表训练样本的单个结点开始。

2、如果样本都在同一个类则该结点成为树叶，并用该类标记。

3、否则，算法选择最有分类能力的属性作为决策树的当前结点。

4、根据当前决策结点属性取值的不同，将训练样本数据集tlI分为若干子集，每个取值形成一个分枝，有几个取值形成几个分枝。匀针对上一步得到的一个子集，重复进行先前步骤，递4'I形成每个划分样本上的决策树。一旦一个属性出现在一个结点上，就不必在该结点的任何后代考虑它。

5、递归划分步骤仅当下列条件之一成立时停止：

①给定结点的所有样本属于同一类；

②没有剩余属性可以用来进一步划分样本，在这种情况下，使用多数表决，将给定的结点转换成树叶，并以样本中元组个数最多的类别作为类别标记，同时也可以存放该结点样本的类别分布；

③如果某一分枝tc，没有满足该分支中已有分类的样本，则以样本的多数类创建一个树叶。

构造方法

决策树构造的输入是一组带有类别标记的例子，构造的结果是一棵二叉树或多叉树。二叉树的内部节点(非叶子节点)一般表示为一个逻辑判断，如形式为a=aj的逻辑判断，其中a是属性，aj是该属性的所有取值：树的边是逻辑判断的分支结果。多叉树(ID3)的内部结点是属性，边是该属性的所有取值，有几个属性值就有几条边。树的叶子节点都是类别标记。

由于数据表示不当、有噪声或者由于决策树生成时产生重复的子树等原因，都会造成产生的决策树过大。因此，简化决策树是一个不可缺少的环节。寻找一棵最优决策树，主要应解决以下3个最优化问题：

①生成最少数目的叶子节点；

②生成的每个叶子节点的深度最小；

③生成的决策树叶子节点最少且每个叶子节点的深度最小。

决策树优缺点

优点：

决策树易于理解和实现人们在通过解释后都有能力去理解决策树所表达的意义。

对于决策树，数据的准备往往是简单或者是不必要的、其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。

能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。

在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

对缺失值不敏感。

可以处理不相关特征数据。

效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。

缺点：

对连续性的字段比较难预测。

对有时间顺序的数据，需要很多预处理的工作。

当类别太多时，错误可能就会增加的比较快。

一般的算法分类的时候，只是根据一个字段来分类。

在处理特征关联性比较强的数据时表现得不是太好。

容易发生过拟合（随机森林可以很大程度上减少过拟合）。

对于那些各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征（只要是使用了信息增益，都有这个缺点，如RF）。

结语

当今社会，信息化得程度日益提高，人们被各种数据所包围。数据挖掘作为一种新兴的学术领域，它的发展极大的促进了人们对海量数据中所蕴含的知识的认识程度。数据挖掘最根本的目的就是，通过各种有效的技术手段，在已知的数据中探寻有价值的信息。决策树分类算法，作为一种简单高效、容易理解的启发式算法，有着广泛的应用领域。近年来随着模糊理论与决策树的融合，使得该算法更为智能，更符合人的思维方式，极大的扩展了其应用范围。

···end···

图灵资管

图灵资管专注于AI智能、TMT、泛娱乐行业，为高净值个人客户和机构提供在行业中被低估值的“小而美”企业，实现资产合理配置、财富增值目标。

四大业务板块

· 海外资本 · 股权投资 · 图灵基金 · 综合方案