决策树基本算法

A. 决策树算法的基本思想

1）树以代表训练样本的单个结点开始。
2）如果样本都在同一个类．则该结点成为树叶，并用该类标记。
3）否则，算法选择最有分类能力的属性作为决策树的当前结点．
4）根据当前决策结点属性取值的不同，将训练样本数据集tlI分为若干子集，每个取值形成一个分枝，有几个取值形成几个分枝。匀针对上一步得到的一个子集，重复进行先前步骤，递4'I形成每个划分样本上的决策树。一旦一个属性出现在一个结点上，就不必在该结点的任何后代考虑它。
5）递归划分步骤仅当下列条件之一成立时停止：
①给定结点的所有样本属于同一类。
②没有剩余属性可以用来进一步划分样本．在这种情况下．使用多数表决，将给定的结点转换成树叶，并以样本中元组个数最多的类别作为类别标记，同时也可以存放该结点样本的类别分布，
③如果某一分枝tc，没有满足该分支中已有分类的样本，则以样本的多数类创建一个树叶。

B. 目前比较流行的决策树算法有哪些

ID3算法，最简单的决策树
c4.5 是最经典的决策树算法，选择信息差异率最大的作为分割属性。
CART算法，适合用于回归

C. 决策树算法的典型算法

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

D. 决策树的计算方法

决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。

E. 决策树算法基础 ID3与C4.5

决策树算法基础：ID3与C4.5
设X是一个取有限个值得离散随机变量，其概率分布为P(X=xi)=pi, i=1,2,…,n。则随机变量X的信息熵为
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。H(Y|X)的计算公式为
所以决策树分支后信息总熵H(D|A)=P1*H1+P2*H2+...+Pn*Hn,(特征A条件下D的经验条件熵)
所以信息增益ΔH=H(D)-H(D|A)
H(D|A)越小，ΔH越大，该特征A越适合作为当前的决策节点。
选取最佳特征伪代码：
计算信息总熵H(D)
遍历每一个特征下的关于D的经验条件熵H(D|A)
计算每一个特征的信息增益ΔH
将信息增益ΔH最大的特征作为最佳特征选为当前决策节点
ID3算法伪代码：
如果第一个标签的数量等于所有的标签数量，说明这是一个单节点树，返回这个标签作为该节点类
如果特征只有一个，说明这是一个单节点树，用多数表决法投票选出标签返回作为该节点类
否则，按信息增益最大的特征A作为当前决策节点，即决策树父节点
如果该特征的信息增益ΔH小于阈值，则用多数表决法投票选出标签返回作为该节点类
否则，对于该特征A的每一个可能值ai，将原空间D分割为若干个子空间Di
对于若干个非空子集Di，将每个Di中实例数最大的类作为标记，构建子节点
以Di为训练空间，递归调用上述步骤
由于信息增益存在偏向于选择取值较多的特征的问题，而C4.5算法中，将ID3算法里的信息增益换成信息增益比，较好地解决了这个问题。
决策树的优点在于计算量简单，适合有缺失属性值的样本，适合处理不相关的特征。而缺点是容易过拟合，可以通过剪枝来简化模型，另外随机森林也解决了这个问题。

F. 决策树算法的介绍

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

G. 决策树法的步骤

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

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

(7)决策树基本算法扩展阅读

决策树的优点

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

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

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

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

5、对缺失值不敏感

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

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

决策树的缺点

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

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

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

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

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

H. 决策树算法原理是什么

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

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

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

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

(8)决策树基本算法扩展阅读：

决策树算法的优点如下：

（1）分类精度高；

（2）生成的模式简单；

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

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

I. 决策树的算法

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

J. 决策树算法有哪些

决策树算法有随机森林，GBDT，XGboost，这些都是基于决策树的