一、决策树模型
决策树(decision tree)是一种常用的机器学习方法，是一种描述对实例进行分类的树形结构。
决策树是一种常用的机器学习方法，以二分类为例，假设现在我们要对是否买西瓜进行判断和决策，我们会问一些问题，根据回答，我们决断是买还是不买，或者还拿补丁主意，这时会继续问问题，直到可以确定为止。
决策树基于“树”结构进行决策：
（1）内部结点：属性
（2）分支：属性值
（3）p叶结点：分类结果
学习过程：通过对训练样本的分析来确定“划分属性”（即内部结点所对应的属性）
预测过程：将测试示例从根结点开始，沿着划分属性所构成的“判定测试序列”下行，直到叶结点
学习的过程就是通过划分属性构建决策树的过程，预测过程就是将测试样本从根节点开始，沿着划分属性构成的“判定序列”下行，直到叶结点。
结构举例：
从代码角度来看，决策树其实可以看成是一堆if-else语句的集合，例如引例中的决策树完全可以看成是如下代码：
if isRed: if isCold: if hasSeed: print("buy") else: print("don‘t buy") else: if isCheap: print("buy") else: print("don‘t buy") else: print("don‘t buy")
由决策树的根结点(root node)到叶结点(leaf node)的每一条路径构建一条规则：路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。
决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。从代码角度来看，决策树的判定过程比较简单。
二、决策树简史
（1）第一个决策树算法：CLS (Concept Learning System)
[E. B. Hunt, J. Marin, and P. T. Stone’s book “Experiments in Induction” published by Academic Press in 1966]
（2）使决策树受到关注、成为机器学习主流技术的算法：ID3
[J. R. Quinlan’s paper in a book “Expert Systems in the Micro Electronic Age” edited by D. Michie, published by Edinburgh University Press in 1979]
（3）最常用的决策树算法：C4.5
[J. R. Quinlan’s book “C4.5: Programs for Machine Learning” published by Morgan Kaufmann in 1993]
（4）可以用于回归任务的决策树算法：CART (Classification and Regression Tree)
[L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone’s book “Classification and Regression Trees” published by Wadsworth in 1984]
（5）基于决策树的最强大算法：RF (Random Forest)，这是一种“集成学习”方法。
[L. Breiman’s MLJ’01 paper “Random Forest]
最初的决策树学习算法是心理学家兼计算机科学假hunt在研究概念学习过程中提出的CLS，这个算法确立了决策树“分而治之”的学习策略。后来hunt的学生写了一个类似于CLS的程序，其中最重要的改进是引入了信息增益准则，这就是ID3算法，现已经成为机器学习主流技术算法，ID3对于可能取值多的属性有所偏好，后来引入了增益率准则，就是C4.5.ID3现在决策树已经成为了一种主流的机器学习方法。
三、基本流程
策略：“分而治之”(divide-and-conquer)。
自根至叶的递归过程，在每个中间结点寻找一个“划分”(split or test)属性。
决策树算法采用分而治之的学习策略，决策树的构造过程就是一个从根节点到叶结点的递归过程。首先根据一定的准则选取最优的属性进行划分，根据属性值得到若干个子集，然后在每个子集上利用同样方法构造决策树。当下面三个条件中一个条件满足时，将含有较多样本的类别作为叶结点中对应的类别标签。
三种情形导致递归返回：
(1) 当前结点包含的样本全属于同一类别，无需划分。
(2) 当前属性集为空, 或是所有样本在所有属性上取值相同，无法划分。
(3) 当前结点包含的样本集合为空，不能划分。
《机器学习(周志华)》笔记--决策树（1）--决策树模型、决策树简史、基本流程
原文：https://www.cnblogs.com/lsm-boke/p/12251128.html