> For the complete documentation index, see [llms.txt](https://louisazhou.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://louisazhou.gitbook.io/notes/chapter3-model/nonlinear-models.md). # Nonlinear Models Decision Tree, Ensemble Learning and Random Forest, SVM and KNN ## Decision Tree Decision Tree是supervised prediction model，可以做regression，也可以做classification。 一棵决策树的生成过程主要分为下3个部分： ​ 1、特征选择：从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准，从而衍生出不同的决策树算法。 ​ 2、决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则决策树停止生长。树结构来说，递归结构是最容易理解的方式。 ​ 3、剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。 在特征选择上，描述信息系统所带的信息量的物理量不同，有Gini index，有entropy. ### 以ID3为例 熵：度量随机变量的不确定性。这里的负号是因为想取到正值，因为 $$log\_{2}p\_{i}$$ 是负的。 $$ I\_{e}=-\log *{2} p*{i} $$ 定义：假设随机变量X的可能取值有 $$x\_{1},x\_{2},...,x\_{n}$$ ，对于每一个可能的取值 $$x\_{i}$$ ，其概率为 $$P(X=x\_{i})=p\_{i},i=1,2...,n$$ 。随机变量的熵为： $$ H(X)=-\sum\_{i=1}^{n}p\_{i}log\_{2}p\_{i} $$ ​对于样本集合，假设样本有k个类别，每个类别的概率为 $$\frac{|C{k}|}{|D|}$$ *其中* $${|C{k}|}$$为类别为k的样本个数， $$|D|​$$ 为样本总数。样本集合D的熵为： $$ H(D)=-\sum\_{k=1}^{k}\frac{|C\_{k}|}{|D|}log\_{2}\frac{|C\_{k}|}{|D|} $$ 熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。 ​ 假设划分前样本集合D的熵为H(D)。使用某个特征A划分数据集D，计算划分后的数据子集的熵为H(D|A)。 信息增益： $$g(D,A)=H(D)-H(D|A)$$ ​ 在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集D。\ ​ 思想：计算所有特征划分数据集D，得到多个特征划分数据集D的信息增益，从这些信息增益中选择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。\ ​ > 理解：为什么说Decision Tree是一个非线性模型？ > > 因为取值不仅与x有关，还与x所处的为止有关；位置又是所有的x一起决定的。 > > 假如我们把Decision Tree Model写成这样的函数关系$$f(X)=v\_{root}+\sum\_{k=1}^{K} \operatorname{contribution}\left(x\_{k}\right)$$， $$v\_{root}$$ 是根节点上的值，contribution是输入数据第k个feature对输出结果产生的作用（eg Entropy的减小、Gini Impurity的减小等），那和linear regression的 $$f(X)=a+\sum\_{k=1}^{K} b\_{k} x\_{k}$$ 相比，LR里的每一项x对f(X)的contribution取决于x的值和系数b，而DT中的f(X)和path的先后顺序有关、和x的位置有关。这是一种非线性关系。 ID3: Entropy C4.5: Gain Rate CART (Classification and Regression Tree): Gini Impurity **决策树算法的缺点**： 1、对连续性的字段比较难预测。 2、容易出现过拟合。 3、当类别太多时，错误可能就会增加的比较快。 4、在处理特征关联性比较强的数据时表现得不是太好。 5、对于各类别样本数量不一致的数据，在决策树当中，信息增益的结果偏向于那些具有更多数值的特征。 #### 剪枝处理的作用及策略: 剪枝处理是决策树学习算法用来解决过拟合问题的一种办法。 ​ 在决策树算法中，为了尽可能正确分类训练样本， 节点划分过程不断重复， 有时候会造成决策树分支过多，以至于将训练样本集自身特点当作泛化特点， 而导致过拟合。 因此可以采用剪枝处理来去掉一些分支来降低过拟合的风险。 ​ 剪枝的基本策略有预剪枝（pre-pruning）和后剪枝（post-pruning）。 ​ 预剪枝：在决策树生成过程中，在每个节点划分前先估计其划分后的泛化性能， 如果不能提升，则停止划分，将当前节点标记为叶结点。 ​ 后剪枝：生成决策树以后，再自下而上对非叶结点进行考察， 若将此节点标记为叶结点可以带来泛化性能提升，则修改之。 但其实在工业界中更常用的是Ensemble Learning的方法。 ## Ensemble Learning Ensemble learning的intuition是CLT，取足够多的sample后，得到的均值接近population mean。 ### Bagging (Bootstrap Aggregating) 本质是Sampling with replacement, 有放回的抽样，这其实是Bootstrap的工作。通过引入随机性来解决overfitting的问题。 如果原先有800行数据，那么bagging就是让不同树看到这800行数据的不同行，但是每棵树看到的数据总数是相同的，这就意味着每棵树都会看到一些重复的数据，这个重复的来源就是每次抽样时的有放回抽样。boostrap有放回抽样也保证了数据的分布相同，这和普通的做sampling相比就更好了。 ### Boosting ——放在Gradient Boosting和SD Boost的section了 ### **区别** bagging就是大家都是学渣，每道题都由随机选出的一群学渣投票决定，这样需要的学渣比较多，而且每个学渣还都得很努力学习。boosting也是一群学渣，但每个人虽然总分菜，却是因为偏科导致的，每个学渣都贡献自己最擅长的那个题目。**比如**小明擅长做数学，小红擅长做语文。第一次只有小明参加考试，成绩出来，数学不错但语文低的一笔；于是小明机智的在第二次考试的时候喊上小红帮他替考语文。这样boosting需要的每个学渣都豪不费力，但是整体上更强了。xgb的学渣还通过预习，让自己偏科的科目学得更省力。所以整体上xgb看起来是非常省力的一群学渣组成，但是拿到的分数却很高。 ## Random Forest 简单来说是把很多Decision Tree组合在一起，再引入一些randomness **Decision Tree + Bagging + Feature Sampling =Random Forest** 假设总数据有N行，M个feature 1. 每次从原数据中有放回地随机选取N个观测值（有重复，也有没被包含的数据） 2. 从Feature中每次抽不同的K个特征，K\