机器学习笔记——决策树（Decision Tree）_决策树的时间空间复杂度

什么是决策树

简书作者：格物致知Lee的文章决策树(Decision Tree)开场对决策树的描述很直观。相亲确实是一个决策的过程，比如女方对男方身高、学历、工作、家庭等特征与自己心里预期进行比较，比较的过程就是一个决策的过程，决策的结果就是女方愿不愿意与男方谈对象。

学习决策树（或者说任何机器学习的算法），我们需要明确三个方面的内容

1. 决策树的前推过程（公式）
2. 有那些参数？
3. 训练方法（参数求解办法）

决策树中的分类器

决策树的每一次决策就是一次分类，而这一次分类可以使用任何方法：

1. 线性分类——感知机
2. 非线性
   • logistic回归
   • 高阶多项式
   • BP网络
3. 比大小
   对于决策树，每一次决策是在叶子节点处做出分类决策，所以每一个叶子节点都是一个分类模型，可能是二分类，也可能是多分类。

决策树中的参数

1. 每个分类器的决策阈值
2. 决策树的层数
3. 分类器模型的参数

以比大小的分类方法，作为决策树的决策函数举例。
假设，有这样的10个样本：
$$[x1,x2,x3,...,x10]$$
每个样本有3个特征值
$$[w1,w2,w3]$$
第一层的决策阈值假设为P，当前决策使用w1作为决策函数与阈值P做比较，得出分类结果：

之后，继续使用比大小的方法，选择一个特征值作为决策函数，选择一个阈值与决策函数比较，从而再次将子节点的数据进行分类；如此往复，直到将样本数据全部分开，或者到达指定层数为止。
从上面的方法，我们了解了使用比大小的方法构成的决策树，每一层的参数就是阈值P和决策函数Wi。那么问题来了，我们从三个特征中选择哪一个作为该节点的决策函数呢？我们又应该以多大的阈值去判定决策函数呢？

如何求解参数

对于上面使用比大小决策的决策树，求解参数就是选出每个分类节点使用那个特征作为决策函数，那个阈值比较合适。
方法步骤：

1. 设定一个评价分类结果好坏的准则；
2. 用遍历的方法迭代
   • 设定一个阈值列表P[p1,p2,p3,…]；
   • 遍历阈值列表P，在选择每一个阈值后，对[w1,w2,w3]进行遍历；
   • 所以时间复杂度是nm，并且会得到nm个分类结果
   • 使用评价准则找出最好的一种分类结果，那么这种分类结果对应的决策特征和阈值就是该决策节点的参数。
3. 那评价准则如何设定呢？
   • 信息增益——ID3
   • 信息增益率——C4.5
   • 基尼系数——CART

ID3与C4.5

评价分类好坏的ID3与C4.5方法，是依据分类前的信息熵和分类后的信息熵作比较得出分类好坏的指标。
什么是信息熵？
$$-\sum _i^n{p}_i\sum _j^m{p}_{j}lo{g}_2(p_j)$$$$p_i就是第i类的概率，p_j是第i类中j类样本出现的概率$$

• 比如：我们有10个样本，在没有进行决策前，计算机认为只有1类，但是每一个样本都是不同类别
  

  所以$$n=1$$$$m=10$$$$p_i=1$$$$p_j=0.1$$所以此时，样本的信息熵为 $$-\sum _i^{1}1\sum _j^{10}0.1lo{g}_2(0.1)=3.32$$如果，这10个样本其中有2个是一个类别，其他8个都是不同类别
  
  这时候信息熵的值为
  $$-\sum _i^1{p}_i\sum _j^9{p}_{j}lo{g}_2(p_j),p_i=1,n=1,m=9$$$$-2/10lo{g}_2(2/10)-1/10lo{g}_2(1/10)\ast 8=3.12$$

• 我们会使用遍历特征和阈值，将样本进行第一次分类，假设有一种方法把10个样本中的x1,x3,x7分为了A类，把x2,x4,x5,x6,x8,x9,x10分为了B类
  

  那么我们再次计算熵，得到如下结果：
  $$A类：p_i=3/10，p_j=1/3$$$$A类熵：-\sum _i^{1}3/10\sum _j^{3}1/3lo{g}_2(1/3)=0.48$$$$B类：p_i=7/10，p_j=1/7$$$$B类熵：-\sum _i^{1}7/10\sum _j^{7}1/7lo{g}_2(1/7)=1.97$$所以，分类后的样本总熵为
  $$0.48+1.97=2.45$$

• 从两次计算的熵来看，分类后的熵要比分类前的熵值小。而熵越小，样本的确定性越高，类别越纯净，已知的信息量会越多。

ID3(Iteration Dichotomister 3)

ID3用到的方法就是计算信息增益（Information Gain），这里的信息就是指已知信息增加的量。
如果按照上面的方法将10个样本分成两类，分类结果的信息增益为：
$$IG=3.32-2.45=0.87$$信息增益的计算公式：
$$IG=E(S)-E(S_v)$$

• $$E：信息熵$$
• $$S：决策前的分类$$
• $$S_v：决策后的分类$$

所以，在所有分类情况都做了一遍后，用决策前的信息熵和每一种分类结果的信息熵求信息增益，在所有信息增益值中选择最大的那个，其所对应的分类结果就是我们想要的，同时它的参数就是该决策节点需要的参数。
但是，如果数据集中有一些数据特别不合群，而我们通过信息增益去找信息熵最小的情况时，这个节点分出来的种类就会很多（有些分出来的类可能指针对一个数据，而这个数据可能还是一个无效数据），这样训练出来的模型存在过拟合现象。

C4.5

C4.5是在ID3的基础上改进，就是为了让分类结果不要过多，在一定程度上解决了过拟合问题。用到的方法是信息增益率(Gain Ratio)。从字面意思理解，就是信息增益的变化率。
信息增益率的计算公式：
$$GR=IG/SG$$由上文ID3知道$$IG=E(S)-E(S_v)$$$$SG(分裂熵)=-\sum _{j=1}^m{D}_j/Dlo{g}_2(D_j/D)$$$$D_j:第j类样本数量(不区分种类)$$$$D:样本总数$$
以上面ID3的分类结果（初始有10个样本，每个样本都不同类），计算信息增益率
$$SG=-3/10lo{g}_2(3/10)-7/10lo{g}_2(7/10)=0.88$$$$GR=0.87/0.88=0.988$$