决策树算法

算法概述
- 分类算法与分类器
- 决策树算法
- - 树模型
  - 决策树的原理
  - 决策树算法的关键
  - 决策树构造的基本思路
算法基本思想
- 决策树的训练与测试
- 三种经典的决策树生成算法
- - 基于信息增益的ID3算法
  - 基于信息增益率的C4.5算法
  - - C4.5算法
    - C5.0算法
  - 基于基尼系数的CART算法
算法流程
算法关键问题
- CART算法关键问题
- - 过拟合问题
  - 过拟合问题的解决
算法实例
- 决策树的简单使用
- 算法案例
- 算法改进与优化

算法概述

分类算法与分类器

分类算法利用训练集获得分类模型（分类器），从而实现将数据集中的样本划分到各个类中。
分类模型通过学习训练样本中属性集与类别之间的潜在关系，并以此为依据对新样本属于哪一类别进行预测。

决策树算法

树模型

决策树由决策结点、分支和叶子结点组成：

决策结点表示在样本的一个属性上进行的划分（中间过程 or 根节点）。
分支表示对于决策结点进行划分的输出（中间过程）。
叶节点代表经过分支到达的类（最终的决策结果）。
从决策树根节点出发，自顶向下移动，在每个决策结点都会进行一次划分，通过划分的结果将样本进行分类，导致不同的分支，最后到达各叶子结点，这个过程就是利用决策树进行分类的过程。
所有的数据最终都会落到叶子节点，即可做分类也可做回归。
决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

决策树的原理

决策树通过把数据样本分配到某个叶子结点来确定数据集中样本所属的分类。
决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。
决策树学习是以实例为基础的归纳学习。
决策树是一种树型结构的分类器，通过顺序询问分类点的属性决定分类点最终的类别。通常根据特征的信息增益或其他指标，构建一棵决策树。在分类时，只需要按照决策树中的结点依次进行判断，即可得到样本所属类别。
例如：

根据上图这个构造好的分类决策树，一个无房产、单身、年收入<80k的人会被归入无法偿还信用卡这个类别。
决策树算法比较适合分析离散数据，如果是连续数据要先转成离散数据再做分析。

决策树算法的关键

建立决策树的关键，即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数，建立决策树主要有以下3种方法：

ID3算法
C4.5算法
CART算法
例如：

选取age属性作为根节点，构造出以下决策树：

决策树构造的基本思路

1.根据某种分类规则得到最优的划分特征，计算最优特征子函数，并创建特征的划分节点，按照划分节点将数据集划分为若干个数据集。
2.在子数据集上重复使用判别规则，构建出新的节点，作为树的新分支。
3.重复递归执行，直到满足递归终止条件。

算法基本思想

决策树的训练与测试

训练阶段：从给定的训练集构造出一棵树（从根节点开始选择特征，如何进行特征切分）。
测试阶段：根据构造出来的树模型从上到下走一遍就好。
一旦构造好了决策树，那么分类或者预测任务就很简单了，只需要走一遍就可以了，那么难点就在于如何构造出来一棵树，这就没那么容易了，需要考虑的问题还有很多。

三种经典的决策树生成算法

如何切分特征（选择节点）？
问题：根节点的选择该用哪个特征呢？接下来呢？如何切分呢？
我们的目标应该是根节点就像一个老大似的能更好的切分数据（分类的效果更好），根节点下面的节点自然是二当家了。
目标：通过一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当做根节点，依次类推。
熵？
熵是表示随机变量不确定性的度量，说白了就是物体内部的混乱程度。
信息熵？
一条信息的信息量大小和它的不确定性有直接的关系，要搞清楚一件非常非常不确定的事情，或者是我们一无所知的事情，需要了解大量信息->信息量的度量就等于不确定性的多少。
公式：
$\sum_{x}^{}p(x)*\log_{2} p(x)$
假如有一个普通骰子A，扔出1-6的概率都是1/6
有一个骰子B，扔出6的概率是50%，扔出1-5的概率都是10%
有一个骰子C，扔出6的概率是100%
那么他们的信息熵的计算为：
骰子A： $-(\frac{1}{6}×\log_{2}\frac{1}{6})×6≈2.585$
骰子B： $-(\frac{1}{10}×\log_{2}\frac{1}{10})×5-\frac{1}{2}×\log_{2}\frac{1}{2}≈2.161$
骰子C： $1×\log_{2} 1)=0$

基于信息增益的ID3算法

ID3算法：以信息增益最大的属性为分类特征，基于贪心策略自顶向下地搜索遍历决策树空间，通过递归方式构建决策树。
换言之，ID3决策树算法使用信息增益确定决策树分支的划分依据，每次选择信息增益最大的特征作为结点。
信息增益即决策树上某个分支上整个数据集信息熵与当前结点信息熵的差值。

举例1

Info(D)是根据分类结果即buys_computer的值来计算的， $Info_{age}(D)$ 的计算原理为：age特征分为三类：youth、middle_aged和senior，它们在数据集中的数量分别为5、4、5，在每一个类别中，如youth中对应的分类结果为no、no、no、yes、yes，判定为yes的情况5次中有2次，所以p(x)= $\frac{2}{5}$ ，以此类推。
即：
举例2
数据：14天打球情况
特征：4种环境变化
目标：构造决策树

划分方式：4种

问题：谁当根节点？
依据：信息增益
决策树构造实例：

在历史数据中（14天）有9天打球，5天不打球，所以此时的熵应为：
$-\frac{9}{14}\log_{2}\frac{9}{14}-\frac{5}{14}\log_{2}\frac{5}{14}=0.940$
4个特征逐一分析，先从outlook特征开始：
outlook=sunny时，熵值为0.971
outlook=overcast时，熵值为0
outlook=rainy时，熵值为0.971
根据数据统计，outlook取值分别为sunny、overcast、rainy的概率分别为：5/14、4/14、5/14。
熵值计算：5/140.971+4/140+5/14*0.971=0.693
信息增益：系统的熵值从原始的0.940下降到了0.693，增益为0.247
同样的方式可以计算出其他特征的信息增益，那么我们选择最大的那个就可以了，相当于是遍历了一遍特征，找出来了大当家，然后再其余的中继续通过信息增益找二当家！

小结

ID3算法中根据信息论的信息增益评估和选择特征，每次选择选择信息增益最大的候选特征，作为判断模块。
信息增益与属性的值域大小成正比。属性取值种类越多，越有可能成为分裂属性。
ID3也不能处理连续分布的数据特征。

基于信息增益率的C4.5算法

C4.5算法

信息增益的方法倾向于首先选择因子数较多的变量
信息增益的改进：增益率。

C4.5算法总体思路与ID3类似，都是通过构造决策树进行分类，其区别在于分支的处理，在分支属性的选取上，ID3算法使用信息增益作为度量，而C4.5算法引入了信息增益率作为度量：
$Gain_ratio(A)=\frac{Gain(A)}{-\sum_{i=1}^{v}\frac{|S_i|}{|S|}\log_{2}\frac{|S_i|}{|S|}}$
由信息增益率公式中可见，当v比较大时，信息增益率会明显降低，从而在一定程度上能够解决ID3算法存在的往往选择取值较多的分支属性的问题。
在前面例子中，假设选择“outlook”作为分支属性，其信息增益率为：
$Gain_ratio(A)=\frac{Gain(A)}{-\sum_{i=1}^{v}\frac{|S_i|}{|S|}\log_{2}\frac{|S_i|}{|S|}}=\frac{0.247}{-(\frac{5}{14}\log_{2}\frac{5}{14}+\frac{5}{14}\log_{2}\frac{5}{14}+\frac{4}{14}\log_{2}\frac{4}{14})}$

小结
C4.5使用信息增益率代替信息增益，进行特征选择，克服了信息增益选择特征时偏向于特征值个数较多的不足；
其具体算法步骤与ID3类似；
C4.5能够完成对连续属性的离散化处理；能够对不完整数据进行处理；
分类规则易于理解、准确率较高；
效率低，只适合于能够驻留于内存的数据集

C5.0算法

C5.0算法是Quinlan在C4.5算法的基础上提出的商用改进版本，目的是对含有大量数据的数据集进行分析
C5.0算法与C4.5算法相比有以下优势：

决策树构建时间要比C4.5算法快上数倍，同时生成的决策树规模也更小，拥有更少的叶子结点数。
使用了提升法(boosting)，组合多个决策树来做出分类，使准确率大大提高。
提供可选项由使用者视情况决定，例如是否考虑样本的权重、样本错误分类成本等。

基于基尼系数的CART算法

CART决策树的生成就是递归地构建二叉决策树的过程，CART用基尼（Gini）系数最小化准则来进行特征选择，生成二叉树。
CART算法采用的是一种二分循环分割的方法，每次都把当前样本集划分为两个子样本集，使生成的决策树的结点均有两个分支，显然，这样就构造了一个二叉树。如果分支属性有多于两个取值，在分裂时会对属性值进行组合，选择最佳的两个组合分支。假设某属性存在q个可能取值，那么以该属性作为分支属性，生成两个分支的分裂方法共有 $2^{q−1}−1$ 种。
CART算法在分支处理中分支属性的度量指标是Gini指标：
$Gini(S)=1-\sum_{i=1}^{m}{p_i}^2,p_i=\frac{C_i}{S}$
在前面例子中，假设选择“windy”作为分支属性，其Gini指标为：
$Gini(windy)=\frac{|S_1|}{|S|}Gini(S_1)+\frac{|S_2|}{|S|}Gini(S_2)=\frac{8}{14}×[1-(\frac{6}{8})^2-(\frac{2}{8})^2]+\frac{6}{14}×[1-(\frac{3}{6})^2-(\frac{3}{6})^2]$

算法流程

计算数据集S中每个属性的熵 $H(x_i)$ 。
选取数据集S中熵值最小（或者信息增益最大，两者等价）的属性。
在决策树上生成该属性结点。
使用剩余结点重复以上步骤生成决策树的属性结点。

算法关键问题

CART算法关键问题

1.递归结束条件

叶子节点纯了，即仅包含一类实例
达到最大深度
达到某一性能指标
2.连续属性离散化
分类数据有二元属性、标称属性等几种不同类型的离散属性。
二元属性只有两个可能值，如“是”或“否”、“对”或“错”，在分裂时，可以产生两个分支。对于二元属性，无需对其数据进行特别处理。
标称属性存在多个可能值，针对所使用的决策树算法不同，标称属性的分裂存在两种方式：多路划分和二元划分。
对于ID3、C4.5等算法，均采用多分支划分的方法，标称属性有多少种可能的取值，就设计多少个分支。
CART算法采用二分递归分割的方法，因此该算法生成的决策树均为二叉树。
标称属性中有类特别的属性为序数属性，其属性的取值是有先后顺序的。对于序数属性的分类，往往要结合实际情况来考虑。
3.过拟合问题
训练误差代表分类方法对于现有训练样本集的拟合程度。
泛化误差代表此方法的泛化能力，即对于新的样本数据的分类能力如何。
模型的训练误差比较高，则称此分类模型欠拟合。
模型的训练误差低但是泛化误差比较高，则称此分类模型过拟合。
对于欠拟合问题，可以通过增加分类属性的数量、选取合适的分类属性等方法，提高模型对于训练样本的拟合程度。

过拟合问题

例子
问题描述：对口罩销售定价进行分类。
样本集：

测试集：

三层决策树，训练误差为0，测试误差高达2/5。

过拟合问题的解决

解决过拟合问题，一方面要注意数据训练集的质量，选取具有代表性样本的训练样本集。另一方面要避免决策树的过度增长，通过限制树的深度来减少数据中的噪声对于决策树构建的影响，一般可以采取剪枝的方法。
剪枝是用来缩小决策树的规模，从而降低最终算法的复杂度并提高预测准确度，包括预剪枝和后剪枝两种。
**预剪枝：**提前终止决策树的增长，在形成完全拟合训练样本集的决策树之前就停止树的增长，避免决策树规模过大而产生过拟合。
**后剪枝：**先让决策树完全生长，之后针对子树进行判断，用叶子结点或者子树中最常用的分支替换子树，以此方式不断改进决策树，直至无法改进为止。

错误率降低剪枝

错误率降低剪枝（ REP ）是后剪枝策略中最简单的算法之一，该算法从叶子结点向上，依次将决策树的所有子树用其样本中最多的类替换，使用一个测试集进行测试，记录下对于决策树的每棵子树剪枝前后的误差数之差，选取误差数减少最少的子树进行剪枝，将其用子样本集中最多的类替换。按此步骤自底向上，遍历决策树的所有子树，当发现没有可替换的子树时，即每棵子树剪枝后的误差数都会增多，则剪枝结束。
REP剪枝方法简单、快速，在数据集较大时效果不错，但由于需要比对模型子树替换前后的预测错误率，因此需要从数据集中划分出单独的测试集，故而当数据集较小时，REP剪枝策略的效果会有所下降。

代价复杂度剪枝策略

代价复杂度剪枝策略（CCP）定义了代价与复杂度的概念，代价是指在剪枝过程中因为子树被替换而增加的错分样本，复杂度表示剪枝后减少的叶节点数。
CCP算法使用α作为衡量代价与复杂度之间关系的值，其计算公式如下：
$α=\frac{R(t)-R(T_t)}{|N_1|-1}$
CCP的具体方法为：计算决策树T的每个非叶子结点的α值，每次计算之后剪掉具有最小α值的子树，循环此过程直至只剩下根结点，进行n次剪枝，生成n个决策树，从这n个决策树中根据真实误差估计选择最佳决策树。

预剪枝vs.后剪枝
一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝训练时间比未剪枝和预剪枝决策树都要大得多。

算法实例

决策树的简单使用

在sklearn库中，可以使用sklearn.tree.DecisionTreeClassifier创建一个决策树用于分类，其主要参数有：

criterion：用于选择属性的准则，可以传入"gini"表示基尼系数，或者"entropy"代表信息增益。
max_features：表示在决策树结点进行分裂时，从多少个特征中选择最优特征。可以设定固定数目、百分比或其他标准。它的默认值是使用所有特征个数。

简单使用

from sklearn import tree
X=[[0,0],[1,1]]
Y=[0,1]
clf=tree.DecisionTreeClassifier()#初始化
Clf=clf.fit(X,Y)#训练决策树
res=Clf.predict([[2.,2.]])#根据训练出的模型预测样本
print(res)

鸢尾花数据集分类

1.首先，我们导入sklearn内嵌的鸢尾花数据集
from sklearn.datasets import load_iris
2.接下来，我们使用import语句导入决策树分类器，同时导入计算交叉验证值的函数cross_val_score
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_score
3.使用默认参数，创建一棵基于基尼系数的决策树，并将该决策树分类器赋值给变量clf
clf=DecisionTreeClassifier()
4.将鸢尾花数据赋值给变量iris
iris=load_iris()
5.将决策树分类器作为待评估的模型，iris.data鸢尾花数据作为特征，iris.target鸢尾花分类标签作为目标结果，通过设定cv=10，使用10折交叉验证。最终得到的交叉验证得分
print(cross_val_score(clf,iris.data,iris.target,cv=10))
6.仿照之前的K近邻分类器的用法，利用fit()方法训练模型并使用predict()函数预测
clf.fit(X,y)
clf.predict(x)

算法案例

1、使用sklearn的决策树算法对葡萄酒数据集进行分类，要求：

划分训练集和测试集（测试集占20%）
对测试集的预测类别标签和真实标签进行对比
输出分类的准确率
调整参数比较不同算法（ID3，C4.5，CART）的分类效果。

#导入sklearn内嵌的葡萄酒数据集
from sklearn.datasets import load_wine
#导入决策树分类器和计算交叉验证值的函数cross_val_score
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
#获取葡萄酒数据
wine=load_wine()
#要求1：
#数据集划分为测试集占20% 训练集占80%
X_train,X_test,y_train,y_test=train_test_split(wine.data,wine.target,test_size=0.8)
#创建决策树
clf=DecisionTreeClassifier()
#基于信息增益的ID3算法
#clf=DecisionTreeClassifier(criterion='entropy')
#基于基尼系数的CART算法
#clf=DecisionTreeClassifier(criterion='gini')
#训练
for epoch in range(100):
    clf.fit(X_train,y_train)
#预测
predict=clf.predict(X_test)
print(predict)
print(y_test)
#评价模型准确率
#基于测试集的准确率
test_score=clf.score(X_test,y_test)
print('test score is {test_score:.6f}'.format(test_score=test_score))