第4课时课程笔记（第四课的课堂笔记）

本节课程讲述得是有监督学习中的分类算法—决策树，主要涉及到的知识点包括：决策树的简介、熵和条件熵、属性选择度量方法、常见的决策树算法、决策树的剪枝等。

以下我将记录学习到的知识点：

决策树是一个类似于流程图的树结构，每个内部结点表示在一个属性上的分类，每个分支代表一个属性值输出，每个叶结点代表类或类分布，树的最顶层是根结点。

决策树中涉及到熵和条件熵的概念：

熵，指信息的不确定性，用于信息量的度量，要搞清楚一件非常非常不确定的事情或者我们一无所知的事情，需要了解大量信息，因此，信息量的度量就等于不确定性的多少。熵的表达式：

H(X)=−∑xp(x)log2p(x)H(X)=-\sum_{x}{p(x)}log_{2}p(x)

其中， p(x)p(x) 表示样本 xx 的概率。

条件熵，指在已知随机变量 XX 的条件下，随机变量 YY 的不确定性。随机变量 XX 给定的条件下随机变量 YY 的条件熵 H(Y|X)H(Y|X) 定义为： XX 给定条件下， YY 的条件概率分布的熵对 XX 的数学期望：

H(Y|X)=∑i=1npiH(Y|X=xi)H(Y|X)=\sum_{i=1}^{n}{p_{i}H(Y|X=x_{i})} ，其中， pi=P(X=xi)p_{i}=P(X=x_{i}) 。

常用的决策树算法有三种：ID3算法，C4.5算法，CART算法。

三种算法的共同点：都是自上而下的贪心算法。 不同点：分裂特征时，最优属性选择的度量方法不同，分别为信息增益、信息增益比和基尼系数。

信息增益，表示得知特征 AA 的信息而使得类 YY 的信息不确定性减少的程度。

信息增益是相对于特征而言的，特征 AA 对训练数据集 DD 的信息增益 g(D,A)g(D,A) 定义为集合 DD 的经验熵 H(D)H(D) 与特征 AA 给定条件下 DD 的经验条件熵 H(D|A)H(D|A) 之差，即： g(D,A)=H(D)−H(D|A)g(D,A)=H(D)-H(D|A) . 依据信息增益对特征进行最优分裂选择时的算法被称为ID3算法。

信息增益的大小是相对于训练数据集而言的，并没有绝对意义，在分类问题困难时，也就是说在训练数据集经验熵大的时候，信息增益值会偏大，反之，增益值会偏小，于是有，信息增益比可以对这个问题进行纠正。

信息增益比： gR(D,A)=g(D|A)H(D)g_{R}(D,A)=\frac{g(D|A)}{H(D)} ，依据信息增益比对特征进行最优分裂选择时的算法被称为C4.5算法。

无论ID3算法和C4.5算法都是基于信息论的熵模型，会涉及大量的对数运算，CART算法简化了模型，并保持了熵模型的优点，它是使用基尼系数来代替信息增益比，基尼系数代表了模型的纯度，基尼系数越小，表示被选中的样本被分错的概率越小，特征越好，这和信息增益（比）是相反的。

一个集合的基尼指数定义为： Gini(D)=∑k=1Kpk(1−pk)=1−∑k=1Kpk2Gini(D)=\sum_{k=1}^{K}{p_{k}(1-p_{k})}=1-\sum_{k=1}^{K}{p_{k}^{2}} , 其中 ∑k=1Kpk=1\sum_{k=1}^{K}{p_{k}}=1 。

样本集 DD 的基尼系数表达式：对于样本集 DD ，如果根据特征 AA 的某个值 aa ，把 DD 分成 D1D_{1} 和 D2D_{2} 两部分，则在特征 AA 的条件下， DD 的基尼系数表达式为： Gini(D,A)=|D1||D|Gini(D1)+|D2||D|Gini(D2)(D1={(x,y)|A(x)=a})Gini(D,A)=\frac{|D_{1}|}{|D|}Gini(D_{1})+\frac{|D_{2}|}{|D|}Gini(D_{2})(D_{1}=\left\{ (x,y)|A(x)=a \right\})

CART算法和ID3、C4.5算法在处理问题上的不同： CART算法采用的思路是不停地二分离散特征，由于上次没有把特征 AA 的取值完全分开，后面还有机会在其他子结点继续选择特征 AA 来划分；而在ID3、C4.5中的一颗子树中，特征只会参与一次结点的建立，即ID3、C4.5算法生成的决策树可以是多叉的，而CART算法生成的决策树都是二叉树。

决策树的剪枝：分为预剪枝和后剪枝。 预剪枝：在决策树的生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分，即结束树的构建，并将当前结点标记为叶结点。 后剪枝：从训练集生成一颗完整的决策树，然后自底向上地对叶结点进行考察，若将该叶结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。

预剪枝与后剪枝各有优缺点： 预剪枝，使得决策树的很多分支没有展开，降低过拟合的风险，同时显著减少了训练时间开销和预测时间开销，但有些分支的当前划分虽不能提升泛化性能，甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能带来性能显著提升； 后剪枝，通常比预剪枝保留了更多的分支，一般后剪枝决策树的欠拟合风险较小，泛化性能往往优于预剪枝决策树，但训练时间和测试时间较长。

通过这节课的学习，我对决策树如何分类有了系统且细致的了解，对一些关键概念都有了深刻的认识，后续还需要根据相关文献对决策树进行深入学习并手动编码，在实践中体会决策树的优缺点，提高自己的动手能力。