目录
1. 概述
1.1 算法导入
1.2 决策树定义
1.3 决策树发展
1.4 结构
1.5 从树到规则
2.决策树的构建
2.1 基本原理
2.2 特征选择
2.3 实例分析--ID3
2.4 增益率--C4.5算法
2.5 基尼指数--CART算法
3. 决策树剪枝
3.1 预剪枝
3.2 后剪枝
3.3 预剪枝vs后剪枝
4. 连续值与缺失值处理
4.1 连续值处理
4.2 缺失值处理
5. 决策树的本质
6. 决策树算法总结
1. 概述
1.1 算法导入
决策树基于“树”结构来进行决策。
1.2 决策树定义
- 决策树( Decision Tree) 又称为判定树，是数据挖掘技术中的一-种重要的分类与回归方法，它是一种以树结构(包括二叉树和多叉树)形式来表达的预测分析模型。
- 决策树(Decision Tree) 是有监督学习的一种算法。
- 决策树有两种:分类树和回归树。
1.3 决策树发展
- 第一个决策树算法: CLS (Concept Learning System)
- 使决策树受到关注、成为机器学习主流技术的算法: ID3
- 最常用的决策树算法: C4.5
- 可以用于回归任务的决策树算法: CART (Classification and Regression Tree
- 基于决策树的最强大算法: RF (Random Forest)
1.4 结构
- 决策树由节点和分支组成。
- 节点有三种类型:根节点，内部节点和叶节点。-般的，一棵决策树包含一个根节点，若干个内部节点和若干个叶节点。
- 分支:用于连接各个节点。
决策树学习的目的是为了产生一棵泛化能力强的决策树
1.5 从树到规则
决策树转换成if- then规则:
●由决策树的根 节点到叶节点的每一条路径构建一 条规则;
●路径上内部节点的特征对应着规则的条件，而叶节点的类标签对应着规则的结论。
互斥并且完备:每一个实例都被有且仅有一条路径或一条规则所覆盖。
2.决策树的构建
2.1 基本原理
策略:自上而下分而治之
●.自根至叶的递归过程， 在每个中间结点寻找一 个“划分” 属性。
●1)开始:构建根节点;所有训练数据都放在根节点，选择-个最优特征，按着这一特征将训练数据集分割成子集，进入子节点。
●2)所有子集按内部节点的属性递归的进行分割。
●3)如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。
●4)每个子集都被分到叶节点.上，即都有了明确的类，这样就生成了一颗决策树。
策略:分而治之”(divide- -and-conquer)
自根至叶的递归过程，在每个中间结点寻找一个“划分”(split or test)属性
三种停止条件:
(1)当前结点包含的样本全属于同一类别，无需划分;
(2)当前属性集为空，或是所有样本在所有属性.上取值相同，无法划分;
(3)当前结点包含的样本集合为空，不能划分.
伪代码：
解释：
训练集D={(x1,y1),(x2,y2).....} x表示输入，y表示标签；x中有许多属性；属性集A={a1,a2,.....}
属性：要学习，不要学习；学习则为属性；
类别：要学习，不要学习；属于两种类别；C表示类别.
终止条件1：样本进来属于同一个类别，直接输出结果是C类返回。
终止条件2：没法划分了，特征向量中所有属性都用完了；或者D样本中的属性A都相同；然后将此节点标记为叶子节点，将样本D中数目最多的类当做类别返回。
终止条件3：当对数据进行划分成多个分支，如果存在分支中没有数据（分支为空），将划分前类别数目多的当做类别返回。
决策树算法的核心：如何选择最优划分属性。
2.2 特征选择
特征(属性)选择
●特征选择 是决定用哪个特征来划分特征空间。
●特征选择表示从众多 的特征中选择-个特征作为当前节点分裂的标准。
●如何选择特征有 不同的量化评估方法，从而衍生出不同的决策树。
◆特征选择的准则是什么?什么样的划分属性是最优的?
我们希望决策树的内部节点所包含的样本尽可能属于同一类别，即节点的纯度”越来越高，可以高效地从根结点到达叶节点，得到决策结果。
信息熵(entropy)是度量样本集合“ 纯度”最常用的一种指标
●假定当前样本集合D中第k类样本所占的比例为pk
●则D的信息熵定义为
若p=0，则plog2 p=0。Ent(D )的最小值为0，最大值为log2 |y|
Ent (D)的值越小，则D的纯度越高。
信息增益直接以信息熵为基础，计算当前划分对信息熵所造成的变化。离散属性a的取值: {a,.,.,a"} Dv:D中在a,上取值为aV的样本集合
以属性a对数据集D进行划分所获得的信息增益为:
●信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。
●决策树算法第8行选择属性: 著名的ID3决策树算法
2.3 实例分析--ID3
该数据集包含17个, 训练样例 |y|= 2, 其中正例占p1= 反例占p2=
根节点的信息熵为:
●以属性“色泽”为例，其对应的3个数据
子集分别为:D1(色泽=青绿)、D2(色泽=乌黑)、D3(色泽=浅白)
●(色泽=青绿)包含的编号为:{1,4,6,10,13,1 7}
●其中正样本占3/6、负样本占3/6
分别计算(色泽=青绿）、
（色泽=乌黑）、
（色泽=浅白）
属性“色泽”的信息增益为:
再计算其他五个属性的信息增益：
显然，属性“纹理”的信息增益最大，选为划分属性
开始递归：
●第一个分支( "纹理=清晰" )
●该分支包含的样例集合D1中有编号为{1,2,3,4,5,6,8,10,15}的9个样例
●用属性集合为{色泽，根蒂，敲声，脐部，触感}，基于D1计算出各属性的信息增益:
"根蒂"、"脐部"、"触感" 3个属性均取得了最大的信息增益，可任选其中之一作为划分属性.
●对每个分支做进一 步划分，最终得到决策树
分析发现信息增益会对对属性越多被选中的概率越大，属性较少的选中概率越小...
2.4 增益率--C4.5算法
信息增益:对可取值数目较多的属性有所偏好( 缺点)
增益率:
- 属性a的可能取值数目越多(即V越大)，则IV(a)的值通常就越大。
- 启发式:先从候选划分属性中找出信息增益高于平均水平的，再从中选取增益率最高的。
2.5 基尼指数--CART算法
反映了从D中随机抽取两个样例,其类别标记不一致的概率
Gini(D)越小，数据集D的纯度越高
属性a的基尼指数:
在候选属性集合中，选取那个使划分后基尼指数最小的属性
3. 决策树剪枝
研究表明:划分选择的各种准则虽然对决策树的尺寸有较大影响,但对泛化性能的影响很有限；例如信息增益与基尼指数产生的结果，仅在约2%的情况下不同；剪枝方法和程度对决策树泛化性能的影响更为显著；剪枝是决策树防止过拟合的手段，在数据带噪时甚至可能将泛化性能提升25%
为了尽可能正确分类训练样本，有可能造成分支过多，出现过拟合可通过主动去掉一些分支来降低过拟合的风险
基本策略:
◆预剪枝(pre-pruning):提前终止某些分支的生长
◆后剪枝(post-pruning):生成一棵完全树， 再“回头”剪枝
原先的决策树只有训练集；现在我们挑选10个数据当做训练集，另外7个当做验证集
使用训练集后生成的决策树，我们再使用验证集的数据对生成的决策树进行验证。验证后发现7个数据有4个数据是错误的，模型很不理想；模型出现过拟合，如何解决这个问题？——剪枝
3.1 预剪枝
若不划分，则将其标记叶节点，类别标记为训练样例中最多的”类别，若选“好瓜”验证集中，{4,5,8}被分类正确， 得到验证集精度为3/7=42.9%
若划分,根据结点2,3,4的训练“好瓜”、集分别标记为‘好瓜”、“坏瓜”验证集中，{4,5,8,11,12} 的样例被划分正确，验证集精度提升为5/7=71.4%
根据“脐部”划分完成后是否需要根据“色泽"来划分？我们分析划分后的精度。
3.2 后剪枝
先生成一棵完整的决策树，其验证集精度测得为42.9%
首先考虑结点6若将其替换为叶结点，根据落在其上的训练样例{7,15}将其标记为“好瓜”，测得验证集精度提高至57.1%，于是可以剪枝。
剪枝后的决策树:
考虑结点5若将其替换为叶结点，根据落在其上的训练样例{6,7,15}将其标记为“好瓜”，测得验证集精度仍为57.1%，于是可以不剪枝。
再考虑父节点结点2若将其替换为叶结点，根据落在其.上的训练样例{1,2,3,14}将其标记为“好瓜”，测得验证集精度提升至71 .4%，于是可以剪枝。剪枝后的决策树:
考虑结点3,1若将其替换为叶结点，先后替换为叶结点，均未测得验证集精度提升，不需要剪枝。
最终经过后剪枝得到的决策树：
3.3 预剪枝vs后剪枝
时间开销:
●预剪枝:训练时间开销降低，测试时间开销降低
●后剪枝:训练时间开销 增加，测试时间开 销降低
过/欠拟合风险:
●预剪枝:过拟合风险降低，欠拟合风险增加
●后剪枝:过拟合风险降低，欠拟合风险基本不变
泛化性能:
后剪枝通常优于预剪枝
4. 连续值与缺失值处理
4.1 连续值处理
连续属性如何划分?
由于连续属性的可取值数目不再有限,因此不能直接根据连续属性的可取值来对结点进行划分。基本思路:连续属性离散化，常见做法:二分法。
4.2 缺失值处理
现实应用中，经常会遇到属性值“缺失”(missing)现象仅使用无缺失的样例->对数据的极大浪费
使用带缺失值的样例，需解决:
Q1:如何进行划分属性选择?
Q2:给定划分属性，若样本在该属性上的值缺失，如何进行划分?
基本思路:样本赋权，权重划分
假设还是这个数据集，并且数据集有部分数据是缺失的。学习开始时，根结点包含样例集D中
全部17个样例，权重均为1
划分前：以属性“色泽”为例，该属性上无缺失值的样例子集D包含14 个样例，信息熵为
划分后：令(色泽=青绿）、
（色泽=乌黑）、
（色泽=浅白）分别表示在属性“色泽”上样本子集，有
因此，样本子集上属性“色泽”的信息增益为
于是，样本集D上属性“色泽”的信息增益为
类似地可计算出所有属性在数据集上的信息增益:
5. 决策树的本质
树的分类本质--轴平行分类
- 每个属性视为坐标空间中的一个坐标轴d个属性描述的样本就对应了d维空间中的一个数据点对样本分类===》在这个坐标空间中寻找不同类样本之间的分类边界
- 决策树的分类边界特点: 轴平行，即它的分类边界由若干个与坐标轴平行的分段组成
产生“轴平行”分类面实例分析：当属性是连续属性，我们使用二分法将其分类并构造一个决策树，通过构造密度与含糖率数据的值分布，我们就可以找到一个与轴平行区分好瓜与坏瓜的分类面。
当学习任务所对应的分类边界很复杂时，需要非常多段划分才能获得较好的近似
我们可以给决策树叠加一些东西，让他可以实现更加平滑的分类边界——斜决策树
“斜决策树”(oblique decision tree)不是为每个非叶结点寻找最优划分属性而是建立一个线性分类器
所以决策树不单纯是一棵树，而是一颗可以挂载东西嵌入很多模型算法 的树，更复杂的“混合决策树”甚至可以在结点嵌入神经网络或其他非线性模型
6. 决策树算法总结
优点:
(1)速度快:计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。
(2)准确性高:挖掘出的分类规则准确性高，便于理解，决策树可以清晰的显示哪些字段比较重要。
(3) 非参数学习，不需要设置参数。
缺点:
(1)缺乏伸缩性:由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。
(2)为了处理大数据集或连续值的种种改进算法(离散化、取样)不仅增加了分类算法的额外开销，而且降低了分类的准确性,对连续性的字段比较难预测，当类别太多时，错误可能就会增加的比较快，对有时间顺序的数据，需要很多预处理的工作。
决策树算法实现：
from sklearn.tree import Decis ionTreeClassifier
model = Decis ionTreeClassifier( )