决策树算法的改进与应用

① 决策树算法原理是什么

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

多叉树(ID3)的内部结点是属性，边是该属性的所有取值，有几个 属性值就有几条边。树的叶子节点都是类别标记。

由于数据表示不当、有噪声或者由于决策树生成时产生重复的子树等原因，都会造成产生的决策树过大。

因此，简化决策树是一个不可缺少的环节。寻找一棵最优决策树，主要应解决以下3个最优化问题：①生成最少数目的叶子节点；②生成的每个叶子节点的深度最小；③生成的决策树叶子节点最少且每个叶子节点的深度最小。

(1)决策树算法的改进与应用扩展阅读：

决策树算法的优点如下：

（1）分类精度高；

（2）生成的模式简单；

（3）对噪声数据有很好的健壮性。

因而是目前应用最为广泛的归纳推理算法之一，在 数据挖掘中受到研究者的广泛关注。

② 常见决策树分类算法都有哪些

在机器学习中，有一个体系叫做决策树，决策树能够解决很多问题。在决策树中，也有很多需要我们去学习的算法，要知道，在决策树中，每一个算法都是实用的算法，所以了解决策树中的算法对我们是有很大的帮助的。在这篇文章中我们就给大家介绍一下关于决策树分类的算法，希望能够帮助大家更好地去理解决策树。
1.C4.5算法
C4.5算法就是基于ID3算法的改进，这种算法主要包括的内容就是使用信息增益率替换了信息增益下降度作为属性选择的标准；在决策树构造的同时进行剪枝操作；避免了树的过度拟合情况；可以对不完整属性和连续型数据进行处理；使用k交叉验证降低了计算复杂度；针对数据构成形式，提升了算法的普适性等内容，这种算法是一个十分使用的算法。
2.CLS算法
CLS算法就是最原始的决策树分类算法，基本流程是，从一棵空数出发，不断的从决策表选取属性加入数的生长过程中，直到决策树可以满足分类要求为止。CLS算法存在的主要问题是在新增属性选取时有很大的随机性。
3.ID3算法
ID3算法就是对CLS算法的最大改进是摒弃了属性选择的随机性，利用信息熵的下降速度作为属性选择的度量。ID3是一种基于信息熵的决策树分类学习算法，以信息增益和信息熵，作为对象分类的衡量标准。ID3算法结构简单、学习能力强、分类速度快适合大规模数据分类。但同时由于信息增益的不稳定性，容易倾向于众数属性导致过度拟合，算法抗干扰能力差。
3.1.ID3算法的优缺点
ID3算法的优点就是方法简单、计算量小、理论清晰、学习能力较强、比较适用于处理规模较大的学习问题。缺点就是倾向于选择那些属性取值比较多的属性，在实际的应用中往往取值比较多的属性对分类没有太大价值、不能对连续属性进行处理、对噪声数据比较敏感、需计算每一个属性的信息增益值、计算代价较高。
3.2.ID3算法的核心思想
根据样本子集属性取值的信息增益值的大小来选择决策属性，并根据该属性的不同取值生成决策树的分支，再对子集进行递归调用该方法，当所有子集的数据都只包含于同一个类别时结束。最后，根据生成的决策树模型，对新的、未知类别的数据对象进行分类。
在这篇文章中我们给大家介绍了决策树分类算法的具体内容，包括有很多种算法。从中我们不难发现决策树的算法都是经过不不断的改造趋于成熟的。所以说，机器学习的发展在某种程度上就是由于这些算法的进步而来的。

③ 决策树算法的介绍

决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树方法最早产生于上世纪60年代，到70年代末。由J Ross Quinlan提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。决策树算法构造决策树来发现数据中蕴涵的分类规则．如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步，决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数据集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除。

④ 决策树算法原理

决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。

如果不考虑效率等，那么样本所有特征的判断级联起来终会将某一个样本分到一个类终止块上。实际上，样本所有特征中有一些特征在分类时起到决定性作用，决策树的构造过程就是找到这些具有决定性作用的特征，根据其决定性程度来构造一个倒立的树--决定性作用最大的那个特征作为根节点，然后递归找到各分支下子数据集中次大的决定性特征，直至子数据集中所有数据都属于同一类。所以，构造决策树的过程本质上就是根据数据特征将数据集分类的递归过程，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。

一棵决策树的生成过程主要分为以下3个部分:

特征选择：特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。

决策树生成： 根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。 树结构来说，递归结构是最容易理解的方式。

剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

划分数据集的最大原则是：使无序的数据变的有序。如果一个训练数据中有20个特征，那么选取哪个做划分依据？这就必须采用量化的方法来判断，量化划分方法有多重，其中一项就是“信息论度量信息分类”。基于信息论的决策树算法有ID3、CART和C4.5等算法，其中C4.5和CART两种算法从ID3算法中衍生而来。

CART和C4.5支持数据特征为连续分布时的处理，主要通过使用二元切分来处理连续型变量，即求一个特定的值-分裂值：特征值大于分裂值就走左子树，或者就走右子树。这个分裂值的选取的原则是使得划分后的子树中的“混乱程度”降低，具体到C4.5和CART算法则有不同的定义方式。

ID3算法由Ross Quinlan发明，建立在“奥卡姆剃刀”的基础上：越是小型的决策树越优于大的决策树（be simple简单理论）。ID3算法中根据信息论的信息增益评估和选择特征，每次选择信息增益最大的特征做判断模块。ID3算法可用于划分标称型数据集，没有剪枝的过程，为了去除过度数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值）。使用信息增益的话其实是有一个缺点，那就是它偏向于具有大量值的属性--就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性，而这样做有时候是没有意义的，另外ID3不能处理连续分布的数据特征，于是就有了C4.5算法。CART算法也支持连续分布的数据特征。

C4.5是ID3的一个改进算法，继承了ID3算法的优点。C4.5算法用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。C4.5算法产生的分类规则易于理解、准确率较高；但效率低，因树构造过程中，需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描，C4.5只适合于能够驻留于内存的数据集。

CART算法的全称是Classification And Regression Tree，采用的是Gini指数（选Gini指数最小的特征s）作为分裂标准,同时它也是包含后剪枝操作。ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但其生成的决策树分支较大，规模较大。为了简化决策树的规模，提高生成决策树的效率，就出现了根据GINI系数来选择测试属性的决策树算法CART。

决策树算法的优点：

（1）便于理解和解释，树的结构可以可视化出来

（2）基本不需要预处理，不需要提前归一化，处理缺失值

（3）使用决策树预测的代价是O(log2m)，m为样本数

（4）能够处理数值型数据和分类数据

（5）可以处理多维度输出的分类问题

（6）可以通过数值统计测试来验证该模型，这使解释验证该模型的可靠性成为可能

（7）即使该模型假设的结果与真实模型所提供的数据有些违反，其表现依旧良好

决策树算法的缺点:

（1）决策树模型容易产生一个过于复杂的模型,这样的模型对数据的泛化性能会很差。这就是所谓的过拟合.一些策略像剪枝、设置叶节点所需的最小样本数或设置数的最大深度是避免出现该问题最为有效地方法。

（2）决策树可能是不稳定的，因为数据中的微小变化可能会导致完全不同的树生成。这个问题可以通过决策树的集成来得到缓解。

（3）在多方面性能最优和简单化概念的要求下，学习一棵最优决策树通常是一个NP难问题。因此，实际的决策树学习算法是基于启发式算法，例如在每个节点进行局部最优决策的贪心算法。这样的算法不能保证返回全局最优决策树。这个问题可以通过集成学习来训练多棵决策树来缓解,这多棵决策树一般通过对特征和样本有放回的随机采样来生成。

（4）有些概念很难被决策树学习到,因为决策树很难清楚的表述这些概念。例如XOR，奇偶或者复用器的问题。

（5）如果某些类在问题中占主导地位会使得创建的决策树有偏差。因此，我们建议在拟合前先对数据集进行平衡。

（1）当数据的特征维度很高而数据量又很少的时候，这样的数据在构建决策树的时候往往会过拟合。所以我们要控制样本数量和特征的之间正确的比率；

（2）在构建决策树之前，可以考虑预先执行降维技术（如PCA，ICA或特征选择），以使我们生成的树更有可能找到具有辨别力的特征；

（3）在训练一棵树的时候，可以先设置max_depth=3来将树可视化出来，以便我们找到树是怎样拟合我们数据的感觉，然后在增加我们树的深度；

（4）树每增加一层，填充所需的样本数量是原来的2倍，比如我们设置了最小叶节点的样本数量，当我们的树层数增加一层的时候，所需的样本数量就会翻倍，所以我们要控制好树的最大深度，防止过拟合；

（5）使用min_samples_split（节点可以切分时拥有的最小样本数） 和 min_samples_leaf（最小叶节点数）来控制叶节点的样本数量。这两个值设置的很小通常意味着我们的树过拟合了，而设置的很大意味着我们树预测的精度又会降低。通常设置min_samples_leaf=5；

（6）当树的类比不平衡的时候，在训练之前一定要先平很数据集，防止一些类别大的类主宰了决策树。可以通过采样的方法将各个类别的样本数量到大致相等，或者最好是将每个类的样本权重之和(sample_weight)规范化为相同的值。另请注意，基于权重的预剪枝标准（如min_weight_fraction_leaf）将比不知道样本权重的标准（如min_samples_leaf）更少偏向主导类别。

（7）如果样本是带权重的，使用基于权重的预剪枝标准将更简单的去优化树结构，如mn_weight_fraction_leaf，这确保了叶节点至少包含了样本权值总体总和的一小部分；

（8）在sklearn中所有决策树使用的数据都是np.float32类型的内部数组。如果训练数据不是这种格式，则将复制数据集，这样会浪费计算机资源。

（9）如果输入矩阵X非常稀疏，建议在调用fit函数和稀疏csr_matrix之前转换为稀疏csc_matrix，然后再调用predict。 当特征在大多数样本中具有零值时，与密集矩阵相比，稀疏矩阵输入的训练时间可以快几个数量级。

⑤ 决策树之ID3算法及其Python实现

决策树之ID3算法及其Python实现

1. 决策树背景知识
??决策树是数据挖掘中最重要且最常用的方法之一，主要应用于数据挖掘中的分类和预测。决策树是知识的一种呈现方式，决策树中从顶点到每个结点的路径都是一条分类规则。决策树算法最先基于信息论发展起来，经过几十年发展，目前常用的算法有：ID3、C4.5、CART算法等。
2. 决策树一般构建过程
??构建决策树是一个自顶向下的过程。树的生长过程是一个不断把数据进行切分细分的过程，每一次切分都会产生一个数据子集对应的节点。从包含所有数据的根节点开始，根据选取分裂属性的属性值把训练集划分成不同的数据子集，生成由每个训练数据子集对应新的非叶子节点。对生成的非叶子节点再重复以上过程，直到满足特定的终止条件，停止对数据子集划分，生成数据子集对应的叶子节点，即所需类别。测试集在决策树构建完成后检验其性能。如果性能不达标，我们需要对决策树算法进行改善，直到达到预期的性能指标。
??注：分裂属性的选取是决策树生产过程中的关键，它决定了生成的决策树的性能、结构。分裂属性选择的评判标准是决策树算法之间的根本区别。
3. ID3算法分裂属性的选择——信息增益
??属性的选择是决策树算法中的核心。是对决策树的结构、性能起到决定性的作用。ID3算法基于信息增益的分裂属性选择。基于信息增益的属性选择是指以信息熵的下降速度作为选择属性的方法。它以的信息论为基础，选择具有最高信息增益的属性作为当前节点的分裂属性。选择该属性作为分裂属性后，使得分裂后的样本的信息量最大，不确定性最小，即熵最小。
??信息增益的定义为变化前后熵的差值，而熵的定义为信息的期望值，因此在了解熵和信息增益之前，我们需要了解信息的定义。
??信息：分类标签xi 在样本集 S 中出现的频率记为 p(xi)，则 xi 的信息定义为：?log2p(xi) 。
??分裂之前样本集的熵：E(S)=?∑Ni=1p(xi)log2p(xi)，其中 N 为分类标签的个数。
??通过属性A分裂之后样本集的熵：EA(S)=?∑mj=1|Sj||S|E(Sj)，其中 m 代表原始样本集通过属性A的属性值划分为 m 个子样本集，|Sj| 表示第j个子样本集中样本数量，|S| 表示分裂之前数据集中样本总数量。
??通过属性A分裂之后样本集的信息增益：InfoGain(S,A)=E(S)?EA(S)
??注：分裂属性的选择标准为：分裂前后信息增益越大越好，即分裂后的熵越小越好。
4. ID3算法
??ID3算法是一种基于信息增益属性选择的决策树学习方法。核心思想是：通过计算属性的信息增益来选择决策树各级节点上的分裂属性，使得在每一个非叶子节点进行测试时，获得关于被测试样本最大的类别信息。基本方法是：计算所有的属性，选择信息增益最大的属性分裂产生决策树节点，基于该属性的不同属性值建立各分支，再对各分支的子集递归调用该方法建立子节点的分支，直到所有子集仅包括同一类别或没有可分裂的属性为止。由此得到一棵决策树，可用来对新样本数据进行分类。
ID3算法流程：
(1) 创建一个初始节点。如果该节点中的样本都在同一类别，则算法终止，把该节点标记为叶节点，并用该类别标记。
(2) 否则，依据算法选取信息增益最大的属性，该属性作为该节点的分裂属性。
(3) 对该分裂属性中的每一个值，延伸相应的一个分支，并依据属性值划分样本。
(4) 使用同样的过程，自顶向下的递归，直到满足下面三个条件中的一个时就停止递归。
??A、待分裂节点的所有样本同属于一类。
??B、训练样本集中所有样本均完成分类。
??C、所有属性均被作为分裂属性执行一次。若此时，叶子结点中仍有属于不同类别的样本时，选取叶子结点中包含样本最多的类别，作为该叶子结点的分类。
ID3算法优缺点分析
优点：构建决策树的速度比较快，算法实现简单，生成的规则容易理解。
缺点：在属性选择时，倾向于选择那些拥有多个属性值的属性作为分裂属性，而这些属性不一定是最佳分裂属性；不能处理属性值连续的属性；无修剪过程，无法对决策树进行优化，生成的决策树可能存在过度拟合的情况。

⑥ 机器学习故事汇-决策树算法

机器学习故事汇-决策树算法
【咱们的目标】系列算法讲解旨在用最简单易懂的故事情节帮助大家掌握晦涩无趣的机器学习，适合对数学很头疼的同学们，小板凳走起！

决策树模型是机器学习中最经典的算法之一啦，用途之广泛我就不多吹啦，其实很多机器学习算法都是以树模型为基础的，比如随机森林,Xgboost等一听起来就是很牛逼的算法（其实用起来也很牛逼）。
首先我们来看一下在上面的例子中我想根据人的年龄和性别（两个特征）对5个人（样本数据）进行决策，看看他们喜不喜欢玩电脑游戏。首先根据年龄（根节点）进行了一次分支决策，又对左节点根据性别进行了一次分支决策，这样所有的样本都落到了最终的叶子节点，可以把每一个叶子节点当成我们最终的决策结果（比如Y代表喜欢玩游戏，N代表不喜欢玩游戏）。这样我们就通过决策树完成了非常简单的分类任务！

再来看一下树的组成，主要结构有根节点（数据来了之后首先进行判断的特征），非叶子节点（中间的一系列过程），叶子节点（最终的结果），这些都是我们要建立的模块！

在决策中树中，我们刚才的喜欢玩电脑游戏的任务看起来很简单嘛，从上往下去走不就OK了吗！但是难点在于我们该如何构造这棵决策树（节点的选择以及切分），这个看起来就有些难了，因为当我们手里的数据特征比较多的时候就该犹豫了，到底拿谁当成是根节点呢？

这个就是我们最主要的问题啦，节点究竟该怎么选呢？不同的位置又有什么影响？怎么对特征进行切分呢？一些到这，我突然想起来一个段子，咱们来乐呵乐呵！

武林外传中这个段子够我笑一年的，其实咱们在推导机器学习算法的时候，也需要这么去想想，只有每一步都是有意义的我们才会选择去使用它。回归正题，我们选择的根节点其实意味着它的重要程度是最大的，相当于大当家了，因为它会对数据进行第一次切分，我们需要把最重要的用在最关键的位置，在决策树算法中，为了使得算法能够高效的进行，那么一开始就应当使用最有价值的特征。

接下来咱们就得唠唠如何选择大当家了，我们提出了一个概念叫做熵（不是我提出的。。。穿山甲说的），这里并不打算说的那么复杂，一句话解释一下，熵代表你经过一次分支之后分类的效果的好坏，如果一次分支决策后都属于一个类别（理想情况下，也是我们的目标）这时候我们认为效果很好嘛，那熵值就很低。如果分支决策后效果很差，什么类别都有，那么熵值就会很高，公式已经给出，log函数推荐大家自己画一下，然后看看概率[0,1]上的时候log函数值的大小（你会豁然开朗的）。

不确定性什么时候最大呢？模棱两可的的时候（就是你犹豫不决的时候）这个时候熵是最大的，因为什么类别出现的可能性都有。那么我们该怎么选大当家呢？（根节点的特征）当然是希望经过大当家决策后，熵值能够下降（意味着类别更纯净了，不那么混乱了）。在这里我们提出了一个词叫做信息增益（就当是我提出的吧。。。），信息增益表示经过一次决策后整个分类后的数据的熵值下降的大小，我们希望下降越多越好，理想情况下最纯净的熵是等于零的。

一个栗子：准备一天一个哥们打球的时候，包括了4个特征（都是环境因素）以及他最终有木有去打球的数据。
第一个问题：大当家该怎么选？也就是我们的根节点用哪个特征呢？

一共有4个特征，看起来好像用谁都可以呀，这个时候就该比试比试了，看看谁的能力强（使得熵值能够下降的最多）

在历史数据中，首先我们可以算出来当前的熵值，计算公式同上等于0.940，大当家的竞选我们逐一来分析，先看outlook这个特征，上图给出了基于天气的划分之后的熵值，计算方式依旧同上，比如outlook=sunny时，yes有2个,no有三个这个时候熵就直接将2/5和3/5带入公式就好啦。最终算出来了3种情况下的熵值。

再继续来看！outlook取不同情况的概率也是不一样的，这个是可以计算出来的相当于先验概率了，直接可以统计出来的，这个也需要考虑进来的。然后outlook竞选大当家的分值就出来啦（就是信息增益）等于0.247。同样的方法其余3个特征的信息增益照样都可以计算出来，谁的信息增益多我们就认为谁是我们的大当家，这样就完成了根节点的选择，接下来二当家以此类推就可以了！

我们刚才给大家讲解的是经典的ID3算法，基于熵值来构造决策树，现在已经有很多改进，比如信息增益率和CART树。简单来说一下信息增益率吧，我们再来考虑另外一个因素，如果把数据的样本编号当成一个特征，那么这个特征必然会使得所有数据完全分的开，因为一个样本只对应于一个ID，这样的熵值都是等于零的，所以为了解决这类特征引入了信息增益率，不光要考虑信息增益还要考虑特征自身的熵值。说白了就是用 信息增益/自身的熵值 来当做信息增益率。

我们刚才讨论的例子中使用的是离散型的数据，那连续值的数据咋办呢？通常我们都用二分法来逐一遍历来找到最合适的切分点！

下面再来唠一唠决策树中的剪枝任务，为啥要剪枝呢？树不是好好的吗，剪个毛线啊！这个就是机器学习中老生常谈的一个问题了，过拟合的风险，说白了就是如果一个树足够庞大，那么所有叶子节点可能只是一个数据点（无限制的切分下去），这样会使得我们的模型泛化能力很差，在测试集上没办法表现出应有的水平，所以我们要限制决策树的大小，不能让枝叶太庞大了。

最常用的剪枝策略有两种：
（1）预剪枝：边建立决策树边开始剪枝的操作
（2）后剪枝：建立完之后根据一定的策略来修建
这些就是我们的决策树算法啦，其实还蛮好的理解的，从上到下基于一种选择标准（熵，GINI系数）来找到最合适的当家的就可以啦！

⑦ 决策树（Decision Tree）

  决策树（Decision Tree）是一种基本的分类与回归方法，其模型呈树状结构，在分类问题中，表示基于特征对实例进行分类的过程。本质上，决策树模型就是一个定义在特征空间与类空间上的条件概率分布。决策树学习通常包括三个步骤： 特征选择 、 决策树的生成 和 决策树的修剪 。

  分类决策树模型是一种描述对实例进行分类的树形结构，决策树由节点（node）和有向边（directed edge）组成。节点有两种类型：内部节点（internal node）和叶节点（leaf node）。内部节点表示一个特征或属性，叶节点表示一个类。

  利用决策树进行分类，从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点；这时，每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶节点。最后将实例分到叶节点的类中。

  决策树是给定特征条件下类的条件概率分布，这一条件概率分布定义在特征区间的一个划分（partiton）上。将特征空间划分为互不相交的单元（cell）或区域（region），并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应划分中的一个单元，决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X为表示特征的随机变量，Y为表示类的随机变量，那么这个条件概率分布可以表示成P(Y|X)。X取值于给定划分下单元的集合，Y取值于类的集合，各叶节点（单元）上的条件概率往往偏向于某一个类，即属于某一类的概率较大，决策树分类时将该节点的实例分到条件概率大的那一类去。也就以为着决策树学习的过程其实也就是由数据集估计条件概率模型的过程，这些基于特征区间划分的类的条件概率模型由无穷多个，在进行选择时，不仅要考虑模型的拟合能力还要考虑其泛化能力。

  为了使模型兼顾模型的拟合和泛化能力，决策树学习使用正则化的极大似然函数来作为损失函数，以最小化损失函数为目标，寻找最优的模型。显然从所有可能的决策树中选取最优决策树是NP完全问题，所以在实际中通常采用启发式的方法，近似求解这一最优化问题： 通过递归的选择最优特征，根据该特征对训练数据进行划分直到使得各个子数据集有一个最好的分类，最终生成特征树 。当然，这样得到的决策树实际上是次最优（sub-optimal）的。进一步的，由于决策树的算法特性，为了防止模型过拟合，需要对已生成的决策树自下而上进行剪枝，将树变得更简单，提升模型的泛化能力。具体来说，就是去掉过于细分的叶节点，使其退回到父节点，甚至更高的节点，然后将父节点或更高的节点改为新的叶节点。如果数据集的特征较多，也可以在进行决策树学习之前，对数据集进行特征筛选。

  由于决策树是一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型，决策树的生成对应模型的局部选择，决策树的剪枝对应着模型的全局选择。

   熵（Entropy） 的概念最早起源于物理学，最初物理学家用这个概念度量一个热力学系统的无序程度。在1948年， 克劳德·艾尔伍德·香农 将热力学的熵，引入到 信息论 ，因此它又被称为 香农熵 。在信息论中，熵是对不确定性的量度，在一条信息的熵越高则能传输越多的信息，反之，则意味着传输的信息越少。

  如果有一枚理想的硬币，其出现正面和反面的机会相等，则抛硬币事件的熵等于其能够达到的最大值。我们无法知道下一个硬币抛掷的结果是什么，因此每一次抛硬币都是不可预测的。因此，使用一枚正常硬币进行若干次抛掷，这个事件的熵是一 比特 ，因为结果不外乎两个——正面或者反面，可以表示为 0, 1 编码，而且两个结果彼此之间相互独立。若进行 n 次 独立实验 ，则熵为 n ，因为可以用长度为 n 的比特流表示。但是如果一枚硬币的两面完全相同，那个这个系列抛硬币事件的熵等于零，因为 结果能被准确预测 。现实世界里，我们收集到的数据的熵介于上面两种情况之间。

  另一个稍微复杂的例子是假设一个 随机变量 X ，取三种可能值 ，概率分别为 ，那么编码平均比特长度是： 。其熵为 。因此<u>熵实际是对随机变量的比特量和顺次发生概率相乘再总和的</u> 数学期望 。

  依据玻尔兹曼H定理，香农把随机变量X的熵 定义为：

  其中 是随机变量X的信息量，当随机变量取自有限样本时，熵可以表示为：

  若 ，则定义 。

  同理可以定义条件熵 :

  很容易看出，条件熵（conditional entropy） 就是X给定条件下Y的条件概率分布的熵对X的数学期望。当熵和条件熵中的概率有极大似然估计得到时，所对应的熵和条件熵分别称为检验熵（empirical entropy）和经验条件熵（empirical conditional entropy）.

  熵越大，随机变量的不确定性就越大，从定义可以验证:

  当底数 时，熵的单位是 ；当 时，熵的单位是 ;而当 时，熵的单位是 .

  如英语有26个字母，假如每个字母在文章中出现的次数平均的话，每个字母的信息量 为：

  同理常用汉字2500有个，假设每个汉字在文章中出现的次数平均的话，每个汉字的信息量 为：

  事实上每个字母和汉字在文章中出现的次数并不平均，少见字母和罕见汉字具有相对较高的信息量，显然，由期望的定义，熵是整个消息系统的平均消息量。

  熵可以用来表示数据集的不确定性，熵越大，则数据集的不确定性越大。因此使用 划分前后数据集熵的差值 量度使用当前特征对于数据集进行划分的效果（类似于深度学习的代价函数）。对于待划分的数据集 ，其划分前的数据集的熵 是一定的，但是划分之后的熵 是不定的， 越小说明使用此特征划分得到的子集的不确定性越小（也就是纯度越高）。因此 越大，说明使用当前特征划分数据集 时，纯度上升的更快。而我们在构建最优的决策树的时候总希望能更快速到达纯度更高的数据子集，这一点可以参考优化算法中的梯度下降算法，每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向。同理：在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集 。

  显然这种划分方式是存在弊端的，按信息增益准则的划分方式，当数据集的某个特征B取值较多时，依此特征进行划分更容易得到纯度更高的数据子集，使得 偏小，信息增益会偏大，最终导致信息增益偏向取值较多的特征。

  设 是 个数据样本的集合，假定类别属性具有 个不同的值： ,设 是类 中的样本数。对于一个给定样本，它的信息熵为：

  其中， 是任意样本属于 的概率，一般可以用 估计。

  设一个属性A具有 个不同的值 ，利用属性A将集合 划分为 个子集 ，其中 包含了集合 中属性 取 值的样本。若选择属性A为测试属性，则这些子集就是从集合 的节点生长出来的新的叶节点。设 是子集 中类别为 的样本数，则根据属性A划分样本的信息熵为：

  其中 , 是子集 中类别为 的样本的概率。最后，用属性A划分样本子集 后所得的 信息增益(Gain) 为：

  即，<u>属性A的信息增益=划分前数据的熵-按属性A划分后数据子集的熵</u>。 信息增益（information gain）又称为互信息（matual information）表示得知特征X的信息而使得类Y的信息的不确定性减少的程度 。信息增益显然 越小， 的值越大，说明选择测试属性A对于分类提供的信息越多，选择A之后对分类的不确定程度越小。

  经典算法 ID3 使用的信息增益特征选择准则会使得划分更偏相遇取值更多的特征，为了避免这种情况。ID3的提出者 J.Ross Quinlan 提出了 C4.5 ,它在ID3的基础上将特征选择准则由 信息增益 改为了 信息增益率 。在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大（类似于正则化）。这个惩罚参数就是 分裂信息度量 的倒数 。

  不同于 ID3 和 C4.5 , CART 使用基尼不纯度来作为特征选择准则。基尼不纯度也叫基尼指数 , 表示在样本集合中一个随机选中的样本被分错的概率 则<u>基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率</u>。Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。

样本集合的基尼指数：
样本集合 有m个类别， 表示第 个类别的样本数量,则 的Gini指数为：

基于某个特征划分样本集合S之后的基尼指数：
  CART是一个二叉树，也就是当使用某个特征划分样本集合后，得到两个集合：a.等于给定的特征值的样本集合 ；b.不等于给定特征值的样本集合 。实质上是对拥有多个取值的特征的二值处理。

对于上述的每一种划分，都可以计算出基于划分特=某个特征值将样本集合划分为两个子集的纯度：

因而对于一个具有多个取值（超过2个）的特征，需要计算以每个取值为划分点，对样本集合划分后子集的纯度 ( 表示特征 的可能取值)然后从所有的划分可能 中找出Gini指数最小的划分，这个划分的划分点，就是使用特征 对样本集合 进行划分的最佳划分点。

参考文献 ：

决策树--信息增益，信息增益比，Geni指数的理解

【机器学习】深入理解--信息熵（Information Entropy）

统计学习方法 （李航）

  为了便于理解，利用以下数据集分别使用三种方法进行分类：

  在进行具体分析之前，考虑到收入是数值类型，要使用决策树算法，需要先对该属性进行离散化。
  在机器学习算法中，一些分类算法（ID3、Apriori等）要求数据是分类属性形式，因此在处理分类问题时经常需要将一些连续属性变换为分类属性。一般来说，连续属性的离散化都是通过在数据集的值域内设定若干个离散的划分点，将值域划分为若干区间，然后用不同的符号或整数数值代表落在每个子区间中的数据值。所以，离散化最核心的两个问题是：如何确定分类数以及如何将连续属性映射到这些分类值。常用的离散化方法有 等宽法 ， 等频法 以及 一维聚类法 等。

在实际使用时往往使用Pandas的 cut() 函数实现等宽离散化:

  可以看到与手工计算的离散化结果相同，需要注意的是，<u> 等宽法对于离群点比较敏感，倾向于不均匀地把属性值分布到各个区间，导致某些区间数据较多，某些区间数据很少，这显然不利用决策模型的建立。 </u>

使用四个分位数作为边界点，对区间进行划分：

<u> 等频率离散化虽然避免了等宽离散化的数据分布不均匀的问题,却可能将相同的数据值分到不同的区间以满足每个区间具有相同数量的属性取值的要求。 </u>

使用一维聚类的离散化方法后得到数据集为：

  在本次实例中选择使用基于聚类的离散化方法后得到的数据集进行指标计算。为了预测客户能否偿还债务，使用A（拥有房产）、B（婚姻情况）、C（年收入）等属性来进行数据集的划分最终构建决策树。

单身 ：

离婚 ：

已婚 ：

显然，由B属性取值'已婚'划分得到的子数据集属于同一个叶节点，无法再进行分类。
接下来，对由B属性取值'单身'划分得到的子数据集 再进行最优特征选择：

1）计算数据集 总的信息熵，其中4个数据中，能否偿还债务为'是'数据有3，'否'数据有1,则总的信息熵：

2）对于A(拥有房产)属性，其属性值有'是'和'否'两种。其中，在A为'是'的前提下，能否偿还债务为'是'的有1、'否'的有0；在A为'否'的前提下，能否偿还债务为'是'的有2、为'否'的有1，则A属性的信息熵为：

3)对于B（婚姻情况）属性，由于已被确定，在这个数据子集信息熵为0

4)对于C（年收入）属性，其属性值有'中等输入'、'低收入'两种。在C为'中等收入'的前提下，能否偿还作为为'是'的有1,为'否'的有0；在C为'低收入'的前提下，能否偿还作为为'是'的有2,为'否'的有1;则C属性的信息熵为：

5）最后分别计算两个属性的信息增益值：


信息增益值相同，说明以两个属性对数据子集进行划分后决策树的纯度上升是相同的，此时任选其一成为叶节点即可。
同理，对数据子集 进行最优特征选择，发现信息熵为0：
整理得到最终的决策树：

⑧ 决策树的算法

C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；
2) 在树构造过程中进行剪枝；
3) 能够完成对连续属性的离散化处理；
4) 能够对不完整数据进行处理。
C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。
具体算法步骤如下；
1创建节点N
2如果训练集为空，在返回节点N标记为Failure
3如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N
4如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类；
5for each 候选属性 attribute_list
6if 候选属性是连续的then
7对该属性进行离散化
8选择候选属性attribute_list中具有最高信息增益率的属性D
9标记节点N为属性D
10for each 属性D的一致值d
11由节点N长出一个条件为D=d的分支
12设s是训练集中D=d的训练样本的集合
13if s为空
14加上一个树叶，标记为训练集中最普通的类
15else加上一个有C4.5（R - {D},C，s）返回的点 背景：
分类与回归树(CART——Classification And Regression Tree)) 是一种非常有趣并且十分有效的非参数分类和回归方法。它通过构建二叉树达到预测目的。
分类与回归树CART 模型最早由Breiman 等人提出，已经在统计领域和数据挖掘技术中普遍使用。它采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。由CART 模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确，且数据越复杂、变量越多，算法的优越性就越显着。模型的关键是预测准则的构建，准确的。
定义：
分类和回归首先利用已知的多变量数据构建预测准则, 进而根据其它变量值对一个变量进行预测。在分类中, 人们往往先对某一客体进行各种测量, 然后利用一定的分类准则确定该客体归属那一类。例如, 给定某一化石的鉴定特征, 预测该化石属那一科、那一属, 甚至那一种。另外一个例子是, 已知某一地区的地质和物化探信息, 预测该区是否有矿。回归则与分类不同, 它被用来预测客体的某一数值, 而不是客体的归类。例如, 给定某一地区的矿产资源特征, 预测该区的资源量。