决策树算法过程

‘壹’ 决策树法的步骤

决策树法的几个关键步骤是：

1、画出决策树，画决策树的过程也就是对未来可能发生的各种事件进行周密思考、预测的过程，把这些情况用树状图表示出来．先画决策点，再找方案分枝和方案点．最后再画出概率分枝。

(1)决策树算法过程扩展阅读

决策树的优点

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

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

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

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

5、对缺失值不敏感

6、可以处理不相关特征数据

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

决策树的缺点

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

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

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

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

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

‘贰’ 决策树算法的典型算法

决策树的典型算法有ID3，C4.5，CART等。
国际权威的学术组织，数据挖掘国际会议ICDM （the IEEE International Conference on Data Mining）在2006年12月评选出了数据挖掘领域的十大经典算法中，C4.5算法排名第一。C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。C4.5算法产生的分类规则易于理解，准确率较高。不过在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，在实际应用中因而会导致算法的低效。
决策树算法的优点如下：
（1）分类精度高；
（2）生成的模式简单；
（3）对噪声数据有很好的健壮性。
因而是目前应用最为广泛的归纳推理算法之一，在数据挖掘中受到研究者的广泛关注。

‘叁’ 决策树算法是按什么来进行分类的

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

‘肆’ 决策树之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算法优缺点分析
优点：构建决策树的速度比较快，算法实现简单，生成的规则容易理解。
缺点：在属性选择时，倾向于选择那些拥有多个属性值的属性作为分裂属性，而这些属性不一定是最佳分裂属性；不能处理属性值连续的属性；无修剪过程，无法对决策树进行优化，生成的决策树可能存在过度拟合的情况。

‘伍’ 决策树算法的介绍

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

‘陆’ 决策树的算法

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 模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确，且数据越复杂、变量越多，算法的优越性就越显着。模型的关键是预测准则的构建，准确的。
定义：
分类和回归首先利用已知的多变量数据构建预测准则, 进而根据其它变量值对一个变量进行预测。在分类中, 人们往往先对某一客体进行各种测量, 然后利用一定的分类准则确定该客体归属那一类。例如, 给定某一化石的鉴定特征, 预测该化石属那一科、那一属, 甚至那一种。另外一个例子是, 已知某一地区的地质和物化探信息, 预测该区是否有矿。回归则与分类不同, 它被用来预测客体的某一数值, 而不是客体的归类。例如, 给定某一地区的矿产资源特征, 预测该区的资源量。

‘柒’ 机器学习故事汇-决策树算法

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

决策树模型是机器学习中最经典的算法之一啦，用途之广泛我就不多吹啦，其实很多机器学习算法都是以树模型为基础的，比如随机森林,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系数）来找到最合适的当家的就可以啦！

‘捌’ 常见决策树分类算法都有哪些

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