决策树与随机森林算法

浅浅的花香味﹌ 2022-08-10 03:53 183阅读 0赞

决策树(分类树)是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。决策树只需要构建一次，每一次预测分类的最大计算次数不超过决策树的深度。

#### 决策树学习算法 ####

##### ID3算法 #####

通过自顶向下构造决策树来进行学习，构造过程是从”选取分类能力最好的属性作为根节点被测试”开始，然后为根节点属性的每个可能值产生一个分支。选择合适的分割点，将分类的各个子集都很”纯净”。  
ID3算法是一种贪心算法，在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准。

###### 量化纯度 ######

如果属性被分为n类，每一类的比例P(i)=第i类的数目/总数目。  
(1)Gini不纯度  
![Gini][]  
(2)熵、信息增益和信息增益率  
![熵][15154348-d876ac3d134c4b94a50acab198ead570.png]

设D是样本训练集，D的熵为  
![InfoD][]  
假设按照属性A划分D中的样本，属性A将D划分为v个不同的类。划分之后，训练集的熵为:  
![InfoA][]  
信息增益为:  
![Gain][]  
信息增益的缺点是偏向具有较多属性值的属性，某个属性所取的不同值的个数越多，越有可能拿它作为分裂属性。  
C4.5算法采用信息增益率。  
![分裂信息][201207252246316876.png]  
![信息增益率][201207252246328894.png]  
选择具有最大增益率的属性作为分裂属性。

(3)错误率  
![错误率][15154351-9f6110dd38664ef1a6f286809a29e8dc.png]  
三个公式的值越大，表示越“不纯”，分类效果越差。

###### 停止条件 ######

决策树的构建过程是一个递归的过程。一种最直观的方式是当每个子节点只有一种类型的记录时停止，这样往往会使得树的节点过多，导致过拟合问题。另一种方法就是当前节点中的记录数低于一个最小的阈值，就停止分割，将max(P(i))对应的分类(当前节点的记录中最大概率的类型)作为当前节点的分类。

###### 优化 ######

1.修剪枝叶  
决策树过拟合导致节点过多。剪裁枝叶的策略对决策树的正确率影响很大，主要有两种剪裁策略。  
**前置剪裁**  
**后置剪裁**

2.K-Fold Cross Validation

3.随机森林  
随机森林是用训练数据随机的计算出许多决策树，形成一个森林。然后用森林对未知数据进行预测，选取投票最多的分类。随机森林算法能降低错误率。一个决策树预测正确的概率可能不高，但是集体预测正确的概率却很高。

(1)随机森林中的每一颗决策树之间是没有联系的。  
(2)建立决策树时，采样与完全分裂。  
首先是两个随机采样过程，随机森林对输入的(样本，特征)进行行、列采样。  
对于行采样，采用有放回的方式，在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的也为N个。这样在每个决策树训练时，输入的样本都不是全部的样本。这样做相对不容易过拟合。  
对于列采样，从M个特征中，选择m个(m小于M)。  
对采样之后的数据使用完全分裂的方式建立决策树，完全分裂的方式就是对于所有可能的分支都扩展。直到某个叶节点无法继续分裂下去，里面所有的样本都属于同一类。  
一般的决策树算法都使用剪枝法进行优化，随机森林的决策树构建不需要进行剪枝，因为随机采样过程已经保证了随机性。

[Gini]: /images/20220731/9e27abd3a46947689075080cd37870ad.png
[15154348-d876ac3d134c4b94a50acab198ead570.png]: /images/20220731/7c5a864328b14d47a7666cb74b9fe634.png
[InfoD]: /images/20220731/f73b3b2b876742f1af0a56d2de8bbb8b.png
[InfoA]: /images/20220731/a8c730d0062c4d8e812f21ebfef2c31c.png
[Gain]: /images/20220731/bef200656e69461aa576ea78ad08475e.png
[201207252246316876.png]: /images/20220731/5ca00c82f35f4bfea10733327f784f15.png
[201207252246328894.png]: /images/20220731/b118c6f0192e4e0195ebced5672d4d0e.png
[15154351-9f6110dd38664ef1a6f286809a29e8dc.png]: /images/20220731/7704f66743444fcfb4f2dc2c9b0bf46a.png