关键词：
全文引用自《统计学习方法》（李航）
决策树(decision tree) 是一种常用的分类与回归方法。决策树的模型为树形结构，在针对分类问题时，实际上就是针对输入数据的各个特征对实例进行分类的过程，即通过树形结构的模型，在每一层级上对特征值进行判断，进而到达决策树叶子节点，即完成分类过程。
决策树的主要优点是模型的可读性较强，分类的速度快。在学习时，主要利用训练数据，根据损失函数最小化原则去构建决策树；在预测时，通过决策树对输入数据进行分类。
决策树的学习过程主要分为三步，即特征选择、决策树的生成、决策树的剪枝。这些决策树学习的主要思想，来源于Quinlan在1986N年提出的ID3算法和1993年提出的C4.5算法。同样，Breiman等人也在1984年提出CART算法。
本文主要介绍决策树的基本原理和其中涉及到概念，在以后介绍决策树的特征选择，ID3及C4.5等算法以及决策树的生成和剪枝等操作。
1. 决策树模型和学习
1.1 决策树模型的定义
分类决策树模型是指一种描述对实例进行分类的树形结构模型。决策树由节点和有向边组成，节点分为内部节点和叶节点，内部节点表示训练数据的某个属性或特征，用以进行分类决策，叶节点表示某种具体的类。
决策树的分类过程，就是从根节点开始，对输入实例的某一个特征进行测试，根据测试的结果选择进入哪一个子节点，而此子节点又代表了对该特征的取值。此时递归地进行测试和选择，直到到达叶节点。最后，叶节点所代表的类就是该实例的分类结果。
1.2 决策树与if-then规则
在理解决策树模型时，可以将决策树看成一组if-then规则的集合。将决策树转化为if-then规则集合，就是去搜索决策树上由根节点到所有叶子节点的所有路径，每一条路径就代表了一条规则。而路径上的内部节点，就对应着对该节点上特征的判断，而叶节点的类就代表了该条路径对应的规则。
通过决策树与if-then规则集合的转化，我们可以看出，决策树具有如下性质：
- 每个实例都有且只有一条路径可以从决策树的根节点到达叶子节点
- 决策树的每个内部节点对实例特征的判断都是互斥的，即实例在判断出到达一个子节点时，不可能存在到达另一子节点所代表的子树上。
1.3 决策树与条件概率分布
决策树模型还可以表示在给定的特征条件下，类的条件概率分布。类的条件概率分布可以表示为对特征空间的一种划分。将特征空间根据各个特征值不断进行划分，就将特征空间分为了多个不相交的单元，在每个单元上定义一个类的概率分布，这样，这条由根节点到达叶节点的路径就成了一个条件概率分布。假设X表示特征的随机变量，Y表示类的随机变量，那么这个条件概率可以表示为$P(Y|X)$,根据输入的实例，由路径找到对应单元的各个类的条件概率，并将该输入实例分为条件概率最大的一类中，就可以完成对实例的分类。
1.4 决策树的学习
决策树的学习目的是根据训练数据集构建一棵决策树模型，使它能够对新输入的实例进行正确的分类。
从if-then规则集的角度看待决策树，其学习的本质就是从训练数据集中归纳出一组分类规则。这组规则可能完美符合训练集的所有数据，也可能与训练集中的少数实例点相矛盾，而矛盾的点，我们就可以将其看做训练集中的噪声点。
从条件概率的角度看待决策树，其学习的本质就是从训练集中找出一个符合要求的估计条件概率模型。由于基于特征空间划分的类的条件概率模型理论上由无穷多个，因此学习的过程就是去寻找一个不仅对训练数据有很好的拟合效果，对测试数据也具有很好的预测能力的条件概率模型。
决策树学习用损失函数来表示学习的目标，其损失函数通常是正则化的极大似然函数，学习的策略就是以损失函数为目标函数的最小化。当损失函数确定时，模型的学习就转换为在损失函数意义下选择最优决策树的问题。
决策树学习算法通常是一种递归地进行最优特征选择，并根据所选择的特征对训练数据集进行划分，并进行树的构建的过程。具体的过程如下：
- 构建根节点，将所有数据放在根节点，选择一个最优的特征，按照这一特征将训练数据集划分为多个子集；
- 判断若一个子集中的所有实例均为一类，即通过根节点所选的特征值已经能够将此部分数据正确分类，那么就构建一个叶节点；
- 判断若一个子集中的实例不能够被正确分类，那么递归地对这些子集进行选择最优特征，并进行分类，构建相应节点，不断递归下去，直到所划分的子集能够被正确分类并构建出叶子节点为止。
通过以上过程，就可以构建出一棵对训练数据有很好的分类能力的决策树。
以上构建的决策树，对训练数据分类效果很好，但通常对未知的数据并没有很好的分类能力，即泛化能力较差，容易产生过拟合。为此，可以对生成的数据进行剪枝，去掉过于细分的叶节点，使其退回到父节点，甚至更高的节点，并将父节点或更高的节点作为叶节点。同时，若输入的训练数据集特征较多，也可以挑选出对数据分类影响最大的几类特征作为分类特征，从而减小决策树的复杂度。
由以上可以看出，决策树的学习过程主要分为特征选择、决策树的生成和决策树的剪枝。决策树可以看做为一个条件概率模型，因此决策树的深度就代表了模型的复杂度，决策树的生成代表了寻找局部最优模型，决策树的剪枝代表了寻找全局最优模型。
机器学习算法(代码片段)
机器学习常用算法一、线性回归1.基本概念2.代码实现二、逻辑回归1.基本概念Sigmoid预测函数2.代码实现三决策树1.基本概念2.代码实现四支持向量机（SVM）1.基本概念2.代码实现五全连接神经网络DNN1.基本概念全连接神经网... 查看详情
机器学习决策树分类原理(代码片段)
决策树分类原理1.熵1.1概念1.2案例2.决策树的划分依据2.1信息增益2.1.1概念2.1.2案例2.2信息增益率2.2.1概念2.2.2案例案例一案例二2.2.3为什么使用C4.5要好?2.3基尼值和基尼指数2.3.1概念2.3.2案例3.小结3.1常见决策树的启发函数比较3.1.1ID3... 查看详情
机器学习决策树算法和分类原理(代码片段)
目录1决策树算法简介2决策树分类原理2.1熵2.1.1概念2.1.2案例2.2划分依据一：信息增益2.2.1概念2.2.2案例2.3划分依据二：信息增益率2.3.1概念2.3.2案例2.3.2.1案例一2.3.2.2案例二2.3.3为什么使用C4.5要好2.4划分依据三：基尼值... 查看详情
4.sparkml学习笔记—sparkml决策树(应用案例)随机森林gbdt算法ml树模型参数详解(本篇概念多)(代码片段)
...机森林、GBDT算法4.1SparkML决策树4.1.1决策树定义4.1.2决策树学习过程4.1.3特征选择4.1.3.1特征选择:熵4.1.3.2特征选择:基尼4.1.3.3特征选择:方差4.1.4生成决策树的方法:ID3算法4.1.5使用决策树算法建立一个可扩展的分类器4.2集成学习4.2.1Bag... 查看详情
机器学习-决策树(代码片段)
最近在看周志华的《机器学习》，感觉讲的还是条理清晰，循序渐进的。但是只是看了很快概念就混淆，导致脑子里一片混乱，所以准备将看过的内容及学到的东西放在这里和大家相互学习交流。 本文转自：http://blog.csdn.net/... 查看详情
id3决策树算法|机器学习(代码片段)
目录1.ID3决策树原理1.1基本原理1.2信息熵1.3条件熵1.4信息增益2.代码实现2.1计算信息熵calEnt2.2获得数据子集splitdataset2.3获得最优特征索引2.4处理样本中只有一个特征或者特征都一样的情况2.5创建ID3决策树2.6返回一条测试数据的标... 查看详情
opencv4机器学习：决策树原理及分类实战(代码片段)
...OpenCV4，来实现一些基本的图像处理操作、经典的机器学习算法（比如K-Means、KNN、SVM、决策树、贝叶斯分类器等），以及常用的深度学习算法。系列文章，持续更新：OpenCV4机器学习（一）：OpenCV... 查看详情
决策树算法(代码片段)
0.机器学习中分类和预测算法的评估：-准确率-速度-强壮性-可规模性-可解释性1.决策树(decisiontree)决策树是一个类似于流程图的树结构：-每个内部结点表示在一个属性上的测试-每个分支代表一个属性输出-每个树叶结点代表类或... 查看详情
统计学习方法ｃ++实现之四 决策树(代码片段)
决策树前言决策树是一种基本的分类和回归算法，书中主要是讨论了分类的决策树。决策树在每一个结点分支规则是一种if-then规则，即满足某种条件就继续搜索左子树，不符合就去右子树，看起来是用二叉树实现对吧，实际的CA... 查看详情
机器学习——决策树(代码片段)
...象值（分类算法中得到某个类别）决策树中间计算过程：统计学习方法中根据下表贷款数据表生成的决策树如下， 查看详情
机器学习决策树算法和分类原理(代码片段)
...xff0c;最早的决策树就是利用这类结构分割数据的一种分类学习方法决策树：是一种树形结构，本质是一颗由多个判断节点组成的树其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最... 查看详情
统计学习方法李航学习笔记
一、决策树1、决策树是一种基本的分类与回归方法，本文主要讨轮用于分类的决策树，决策树模型呈现树形结构，在分类问题中，表示基于特征对实例进行分类的过程，学习时，利用训练数据，根据损失函数最小化的原则建立... 查看详情
机器学习笔记(代码片段)
机器学习笔记（四）文章目录机器学习笔记（四）线性判别分析多分类学习类别不平衡问题小总结决策树决策树的基本概念决策树的构造ID3算法C4.5算法CART算法线性判别分析线性判别分析（LinearDiscriminantAnalysis&... 查看详情
机器学习笔记(代码片段)
机器学习笔记（四）文章目录机器学习笔记（四）线性判别分析多分类学习类别不平衡问题小总结决策树决策树的基本概念决策树的构造ID3算法C4.5算法CART算法线性判别分析线性判别分析（LinearDiscriminantAnalysis&... 查看详情
机器学习笔记(代码片段)
机器学习笔记（四）文章目录机器学习笔记（四）线性判别分析多分类学习类别不平衡问题小总结决策树决策树的基本概念决策树的构造ID3算法C4.5算法CART算法线性判别分析线性判别分析（LinearDiscriminantAnalysis&... 查看详情
机器学习笔记(代码片段)
机器学习笔记（四）文章目录机器学习笔记（四）线性判别分析多分类学习类别不平衡问题小总结决策树决策树的基本概念决策树的构造ID3算法C4.5算法CART算法线性判别分析线性判别分析（LinearDiscriminantAnalysis&... 查看详情
决策树（统计学习方法（李航））的贷款的例子的实现(代码片段)
以统计学习方法（李航）这本书的例子为基础需要注意的地方：我用的是pycharmpython版本是3.7graphviz是一个软件，在pycharm里面下了还得去官网下下完之后得加入环境变量可能还需要重启电脑缺啥库就安啥库那个数据是我自己设置... 查看详情
统计学习方法 李航 决策树
决策树一.决策树基本描述决策树是一种基本的分类与回归方法,呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程.学习时,利用训练数据根据损失函数最小化的原则建立决策树模型.预测时,对新的数据,利用决策树模型... 查看详情