定量分析决策树算法

1. 决策树原理及算法比较

决策树是什么？

    和线性回归一样是一种模型，内部节点和叶节点。实现分类，内部节点和叶节点通过有向线（分类规      则）连接起来

决策树的目标是什么？

    决策树通过对数据复杂度的计算，建立特征分类标准，确定最佳分类特征。

    表现为“熵”（entropy）和信息增益（information gain），基于决策树思想的三种算法：ID3，C4.5,CART算法，三种算法的信息衡量的指标也不同.

    熵来表示信息的复杂度，熵越大，信息也就越复杂，公式如下：

那些算法能够实现决策树？

    在决策树构建过程中，什么是比较重要的。特征选择（按照熵变计算），算法产生最重要的部分，

决策树中叶节点的分类比较纯，

节点顺序的排列规则：

熵变：

数据的预处理：

改进思路一般有两个1，换算法；2，调参数

做好数据的预处理：

1，做好特征选择；

2，做好数据离散化、异常值处理、缺失填充

分类器：

在决策树中，从根到达任意一个叶节点的之间最长路径的长度，表示对应的算法排序中最坏情况下的比较次数。这样一个比较算法排序中的最坏情况的比较次数就与其决策树的高度相同，同时如果决策树中每种排列以可达叶子的形式出现，那么关于其决策树高度的下界也就是关于比较排序算法运行时间的下界，

ID3算法存在的缺点：

    1，ID3算法在选择根节点和内部节点分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性

    2，当数据为连续性变量的时候，ID3算法就不是一个合理的算法的模型了

C4.5信息增益比率，

     1，在信息增益的基础上除以split-info，是将信息增益改为信息增益比，以解决取值较多的属性的问题，另外它还可以处理连续型属性，其判别标准是θ，

      2，C4.5算法利用增益/熵值，克服了树生长的过程中，总是‘贪婪’选择变量分类多的进行分类

      3，处理来内需型变量，C4.5的分类树的分支就是两条

衡量指标：

（1）信息增益

基于ID3算法的信息增益对于判定连续型变量的时候病不是最优选择，C4.5算法用了信息增益率这个概念。

分类信息类的定义如下：

这个值表示将训练数据集D划分成对应属性A测试的V个输出v个划分产生的信息，信息增益率定义为：

选择最大信息增益率的属性作为分裂属性

Gini指标，CART

表明样本的“纯净度”。Gini系数避免了信息增益产生的问题，

过拟合问题，非常好的泛化能力，有很好的推广能力

Gini系数的计算：

在分类问题中，假设有k个类，样本点属于第k类的概率为Pk，则概率分布的gini指数的定义为：

如果样本集合D根据某个特征A被分割为D1，D2两个部分，那么在特征A的提哦啊见下，集合D的gini指数的定义为：

Gini指数代表特征A不同分组下的数据集D的不确定性，gini指数越大，样本集合的不确定性也就越大，这一点和熵的概念相类似

决策树原理介绍：

第三步：对于每个属性执行划分：

（1）该属性为离散型变量

记样本中的变量分为m中

穷举m种取值分为两类的划分

对上述所有划分计算GINI系数

（2）该属性为连续型变量

将数据集中从小到大划分

按顺序逐一将两个相临值的均值作为分割点

对上述所有划分计算GINI系数

学历的划分使得顺序的划分有个保证，化为连续型变量处理。

决策树的生成算法分为两个步骤：

预剪枝和后剪枝  CCP（cost and complexity）算法：在树变小和变大的的情况有个判断标准。误差率增益值：α值为误差的变化

决策树的终止条件：

      1，某一个节点的分支所覆盖的样本都是同一类的时候

      2，某一个分支覆盖的样本的个数如果小于一个阈值，那么也可以产生叶子节点，从而终止Tree-Growth

确定叶子结点的类：

      1，第一种方式，叶子结点覆盖的样本都属于同一类

      2， 叶子节点覆盖的样本未必是同一类，所占的大多数，那么该叶子节点的类别就是那个占大多数的类

2. 决策树法分为那几个步骤

1、特征选择

特征选择决定了使用哪些特征来做判断。在训练数据集中，每个样本的属性可能有很多个，不同属性的作用有大有小。因而特征选择的作用就是筛选出跟分类结果相关性较高的特征，也就是分类能力较强的特征。在特征选择中通常使用的准则是：信息增益。

2、决策树生成

选择好特征后，就从根节点触发，对节点计算所有特征的信息增益，选择信息增益最大的特征作为节点特征，根据该特征的不同取值建立子节点；对每个子节点使用相同的方式生成新的子节点，直到信息增益很小或者没有特征可以选择为止。

3、决策树剪枝

剪枝的主要目的是对抗“过拟合”，通过主动去掉部分分支来降低过拟合的风险。

【简介】

决策树是一种解决分类问题的算法，决策树算法采用树形结构，使用层层推理来实现最终的分类。

3. 决策树的算法

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

4. 决策树分类算法有哪些

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

问题二：数据挖掘分类方法决策树可以分多类么 数据挖掘,也称之为数据库中知识发现是一个可以从海量数据中智能地和自动地抽取一些有用的、可信的、有效的和可以理解的模式的过程.分类是数据挖掘的重要内容之一.目前,分类已广泛应用于许多领域,如医疗诊断、天气预测、信用证实、顾客区分、欺诈甄别. 现己有多种分类的方法,其中决策树分类法在海量数据环境中应用最为广泛.其原因如下：
1、决策树分类的直观的表示方法较容易转化为标准的数据库查询
2、决策树分类归纳的方法行之有效,尤其适合大型数据集.
3、决策树在分类过程中,除了数据集中已包括的信息外,不再需要额外的信息.
4、决策树分类模型的精确度较高. 该文首先研究了评估分类模型的方法.在此基础上着重研究了决策树分类方法,并对决策树算法的可伸缩性问题进行了具体分析,最后给出了基于OLE DB for DM开发决策树分类预测应用程序.

问题三：基于规则的分类器（比如用RIPPER算法）和决策树的区别在哪，使用场景有什么不同？ 决策树实际上是规则分类器。基于转换的错误驱动学习方法的提出者曾经在论文中论证过这个问题，他的学习方法是规则学习器，但和决策树等价。

问题四：决策树的优缺点是什么啊 决策树(Decision Tree)是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。
决策树的优缺点：
优点：

1) 可以生成可以理解的规则。

2) 计算量相对来说不是很大。

3) 可以处理连续和种类字穿。

4) 决策树可以清晰的显示哪些字段比较重要

缺点：

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

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

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

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

问题五：c4.5决策树算法怎么得到分类结果 决策树主要有ID3，C4.5，CART等形式。ID3选取信息增益的属性递归进行分类，C4.5改进为使用信息增益率来选取分类属性。CART是Classfication and Regression Tree的缩写。表明CART不仅可以进行分类，也可以进行回归。

问题六：决策树分类算法的适用领域，不要概括成经济、社会、医疗领域，具体到实际问题。且用什么软件实现较方便。 决策树算法主要用于数据挖掘和机器学习，数据挖掘就是从海量数据中找出规律。一个有名的例子就是啤酒和尿布的例子，这是数据挖掘的典型。决策树算法包括ID3，C4.5，CART等，各种算法都是利用海量的数据来生成决策树的，决策树能帮助人或者机器做出决策。最简单的一个例子就是你去看病，根据决策树，医生能够判断这是什么病。软件的话用VISUAL STUDIO就可以，C语言，C++,C#，java都可以。

问题七：贝叶斯网络和贝叶斯分类算法的区别 贝叶斯分类算法是统计学的一种分类方法，它是一类利用概率统计知识进行分类的算法。在许多场合，朴素贝叶斯(Na?ve Bayes，NB)分类算法可以与决策树和神经网络分类算法相媲美，该算法能运用到大型数据库中，而且方法简单、分类准确率高、速度快。
由于贝叶斯定理假设一个属性值对给定类的影响独立于其它属性的值，而此假设在实际情况中经常是不成立的，因此其分类准确率可能会下降。为此，就衍生出许多降低独立性假设的贝叶斯分类算法，如TAN(tree augmented Bayes network)算法。

5. 数据挖掘-决策树算法

决策树算法是一种比较简易的监督学习分类算法，既然叫做决策树，那么首先他是一个树形结构，简单写一下树形结构（数据结构的时候学过不少了）。

树状结构是一个或多个节点的有限集合，在决策树里，构成比较简单，有如下几种元素：

在决策树中，每个叶子节点都有一个类标签，非叶子节点包含对属性的测试条件，用此进行分类。
所以个人理解，决策树就是 对一些样本，用树形结构对样本的特征进行分支，分到叶子节点就能得到样本最终的分类，而其中的非叶子节点和分支就是分类的条件，测试和预测分类就可以照着这些条件来走相应的路径进行分类。

根据这个逻辑，很明显决策树的关键就是如何找出决策条件和什么时候算作叶子节点即决策树终止。

决策树的核心是为不同类型的特征提供表示决策条件和对应输出的方法，特征类型和划分方法包括以下几个：

注意，这些图中的第二层都是分支，不是叶子节点。

如何合理的对特征进行划分，从而找到最优的决策模型呢？在这里需要引入信息熵的概念。

先来看熵的概念：

在数据集中，参考熵的定义，把信息熵描述为样本中的不纯度，熵越高，不纯度越高，数据越混乱（越难区分分类）。

例如：要给（0，1）分类，熵是0，因为能明显分类，而均衡分布的（0.5，0.5）熵比较高，因为难以划分。

信息熵的计算公式为：
其中 代表信息熵。 是类的个数， 代表在 类时 发生的概率。
另外有一种Gini系数，也可以用来衡量样本的不纯度：
其中 代表Gini系数，一般用于决策树的 CART算法 。

举个例子：

如果有上述样本，那么样本中可以知道，能被分为0类的有3个，分为1类的也有3个，那么信息熵为：
Gini系数为：
总共有6个数据，那么其中0类3个，占比就是3/6，同理1类。

我们再来计算一个分布比较一下：

信息熵为：
Gini系数为：

很明显，因为第二个分布中，很明显这些数偏向了其中一类，所以 纯度更高 ，相对的信息熵和Gini系数较低。

有了上述的概念，很明显如果我们有一组数据要进行分类，最快的建立决策树的途径就是让其在每一层都让这个样本纯度最大化，那么就要引入信息增益的概念。

所谓增益，就是做了一次决策之后，样本的纯度提升了多少（不纯度降低了多少），也就是比较决策之前的样本不纯度和决策之后的样本不纯度，差越大，效果越好。
让信息熵降低，每一层降低的越快越好。
度量这个信息熵差的方法如下：
其中 代表的就是信息熵（或者其他可以度量不纯度的系数）的差， 是样本(parent是决策之前， 是决策之后)的信息熵（或者其他可以度量不纯度的系数）， 为特征值的个数， 是原样本的记录总数， 是与决策后的样本相关联的记录个数。

当选择信息熵作为样本的不纯度度量时，Δ就叫做信息增益 。

我们可以遍历每一个特征，看就哪个特征决策时，产生的信息增益最大，就把他作为当前决策节点，之后在下一层继续这个过程。

举个例子：

如果我们的目标是判断什么情况下，销量会比较高（受天气，周末，促销三个因素影响），根据上述的信息增益求法，我们首先应该找到根据哪个特征来决策，以信息熵为例：

首先肯定是要求 ，也就是销量这个特征的信息熵：

接下来，就分别看三个特征关于销量的信息熵，先看天气，天气分为好和坏两种，其中天气为好的条件下，销量为高的有11条，低的有6条；天气坏时，销量为高的有7条，销量为低的有10条，并且天气好的总共17条，天气坏的总共17条。

分别计算天气好和天气坏时的信息熵，天气好时：

根据公式 ，可以知道，N是34，而天气特征有2个值，则k=2，第一个值有17条可以关联到决策后的节点，第二个值也是17条，则能得出计算：

再计算周末这个特征，也只有两个特征值，一个是，一个否，其中是有14条，否有20条；周末为是的中有11条销量是高，3条销量低，以此类推有：


信息增益为：

另外可以得到是否有促销的信息增益为0.127268。

可以看出，以周末为决策，可以得到最大的信息增益，因此根节点就可以用周末这个特征进行分支：

注意再接下来一层的原样本集，不是34个而是周末为“是”和“否”分别计算，为是的是14个，否的是20个。
这样一层一层往下递归，直到判断节点中的样本是否都属于一类，或者都有同一个特征值，此时就不继续往下分了，也就生成了叶子节点。

上述模型的决策树分配如下：

需要注意的是，特征是否出现需要在分支当中看，并不是整体互斥的，周末生成的两个分支，一个需要用促销来决策，一个需要用天气，并不代表再接下来就没有特征可以分了，而是在促销决策层下面可以再分天气，另外一遍天气决策下面可以再分促销。

决策树的模型比较容易解释，看这个树形图就能很容易的说出分类的条件。

我们知道属性有二元属性、标称属性、序数属性和连续属性，其中二元、标称和序数都是类似的，因为是离散的属性，按照上述方式进行信息增益计算即可，而连续属性与这三个不同。

对于连续的属性，为了降低其时间复杂度，我们可以先将属性内部排序，之后取相邻节点的均值作为决策值，依次取每两个相邻的属性值的均值，之后比较他们的不纯度度量。

需要注意的是，连续属性可能在决策树中出现多次，而不是像离散的属性一样在一个分支中出现一次就不会再出现了。

用信息熵或者Gini系数等不纯度度量有一个缺点，就是会倾向于将多分支的属性优先分类——而往往这种属性并不是特征。

例如上面例子中的第一行序号，有34个不同的值，那么信息熵一定很高，但是实际上它并没有任何意义，因此我们需要规避这种情况，如何规避呢，有两种方式：

公式如下：

其中k为划分的总数，如果每个属性值具有相同的记录数，则 ，划分信息等于 ，那么如果某个属性产生了大量划分，则划分信息很大，信息增益率低，就能规避这种情况了。

为了防止过拟合现象，往往会对决策树做优化，一般是通过剪枝的方式，剪枝又分为预剪枝和后剪枝。

在构建决策树时，设定各种各样的条件如叶子节点的样本数不大于多少就停止分支，树的最大深度等，让决策树的层级变少以防止过拟合。
也就是在生成决策树之前，设定了决策树的条件。

后剪枝就是在最大决策树生成之后，进行剪枝，按照自底向上的方式进行修剪，修剪的规则是，评估叶子节点和其父节点的代价函数，如果父节点的代价函数比较小，则去掉这个叶子节点。
这里引入的代价函数公式是：
其中 代表的是叶子节点中样本个数， 代表的是该叶子节点上的不纯度度量，把每个叶子节点的 加起来，和父节点的 比较，之后进行剪枝即可。

6. 决策树计算公式

决策树计算公式公式：H(X)=–∑P(x)log[P(x)]H(x)：表示熵 P(x)：表示x事件发生的概率。

决策树法的具体计算过程：

①绘制决策树图形，按上述要求由左向右顺序展开。

②计算每个结点的期望值，计算公式为：

状态结点的期望值=Σ（损益值×概率值）×经营年限

③剪枝，即进行方案的选优。

方案净效果=该方案状态结点的期望值-该方案投资额