网站应具有的功能模块,新手怎么做电商在哪个网站,wap网站开发方案,提高工作效率心得体会前言
本文是一篇关于决策树方面知识的小结#xff0c;不包含具体的例子#xff08;想看例子推荐文献[1]的第4章#xff09;#xff0c;主要总结了ID3、C4.5和CART树三者的区别#xff0c;剪枝处理#xff0c;连续值和缺失值的处理。
决策树的基本算法
决策树的学习目的…前言
本文是一篇关于决策树方面知识的小结不包含具体的例子想看例子推荐文献[1]的第4章主要总结了ID3、C4.5和CART树三者的区别剪枝处理连续值和缺失值的处理。
决策树的基本算法
决策树的学习目的是为了产生一颗泛化能力强即处理未见示例能力强的决策树其基本流程遵循“分治”的策略基本算法如下所示
***********************输入********************
训练集 D{(x1,y1),(x2,y2),...,(xm,ym)}x中有 (col1,col2,...,colk) 共k组特征
每个col下有相应的属性值(a1,a2,...,ap)y中有 (l1,l2,...,ln) 共n种类标签
***********************过程********************
if 数据集中的每个子项属于同一分类 thenreturn 类标签
else寻找划分数据集的最好特征*划分数据集创建分支结点for 每个划分的子集递归调用该函数并增加返回结果到分支结点中end forreturn 分支结点
end if
***********************输出********************
一颗决策树其中最为重要的是“寻找划分数据集的最好特征”这一步我特意打上了*号这也是不同算法的区别所在。
ID3、C4.5和CART的区别
ID3算法
在划分数据集的过程当中我们希望决策树的分支结点所包含的样本尽可能地属于同一类别即结点的纯度越来越高。 在ID3算法中利用了信息增益这一准则来划分数据集要了解信息增益首先要知道信息熵的概念。信息熵是度量样本集合纯度最常用的一项指标。假设当前样本DDD的第kkk类样本所占的比例为pk(k1,2,...,n)p_k(k1,2,...,n)pk(k1,2,...,n),则DDD的信息熵定义为
Ent(D)−∑k1npk⋅log2pkEnt(D)-\sum_{k1}^{n}p_k \cdot log_2p_kEnt(D)−k1∑npk⋅log2pk
En(D)En(D)En(D)的值越小DDD的纯度就越高。 假定特征colcolcol有VVV个可能的取值{a1,a2,...,aV}\{a^1,a^2,...,a^V\}{a1,a2,...,aV}若使用colcolcol来对样本集DDD划分则会划分成VVV个子集其中以ava^vav划分出来的子集记为DvD^vDv那么信息增益可以表示为
Gain(D,col)Ent(D)−∑v1V∣Dv∣∣D∣Ent(Dv)Gain(D,col)Ent(D)-\sum_{v1}^{V}\dfrac{|D^v|}{|D|}Ent(D^v)Gain(D,col)Ent(D)−v1∑V∣D∣∣Dv∣Ent(Dv)
其中∣D∣|D|∣D∣表示数据集中的样本个数。 ID3就是使用信息增益最大为准则来划分数据集的计算出每个colcolcol下的Gain(D,col)Gain(D,col)Gain(D,col)然后选择值最大的那一个。 但这样的做法为偏袒于属性数量较多的特征即VVV较大的colcolcol为解决这个问题就有了C4.5算法。
C4.5算法
与ID3算法不同C4.5是利用增益率来进行划分的其定义如下
Gain_ratio(D,col)Gain(D,col)IV(col)Gain\_ratio(D,col)\dfrac{Gain(D,col)}{IV(col)}Gain_ratio(D,col)IV(col)Gain(D,col)
其中
IV(col)−∑v1V∣Dv∣∣D∣log2DvDIV(col)-\sum_{v1}^{V}\dfrac{|D^v|}{|D|}log_2\dfrac{D^v}{D}IV(col)−v1∑V∣D∣∣Dv∣log2DDv
IV(col)IV(col)IV(col)称为特征colcolcol的固有值特征colcolcol的属性越多IV(col)IV(col)IV(col)的值就越大。 这样一来就可以解决ID3的弊端然而值得注意的是增益率准则对属性值数目较少的特征有所偏好故C4.5并不是直接取增益率最大的特征来划分数据集的而是采用了一种启发式的方法先从数据集中找出信息增益高于平均水平的特征然后从中选择增益率最高的。
CART算法
CART则采用了基尼指数来划分属性数据集DDD的纯度可以用基尼值来度量
Gini(D)∑k11n∑k1!k2npk1pk21−∑k1npk2Gini(D)\sum_{k11}^{n}\sum_{k1!k2}^{n}p_{k1}p_{k2}1-\sum_{k1}^{n}p_k^2Gini(D)k11∑nk1!k2∑npk1pk21−k1∑npk2
基尼值反应了从数据集中随机抽取两个样本其类标签不一致的概率因此基尼值越小数据集的纯度越高。 特征colcolcol的基尼指数定义为
Gini_index(D,col)∑v1V∣Dv∣DGini(Dv)Gini\_index(D,col)\sum_{v1}^{V}\dfrac{|D^v|}{D}Gini(D^v)Gini_index(D,col)v1∑VD∣Dv∣Gini(Dv)
CART就是选择划分后基尼指数最小的特征为最优划分特征的。
剪枝
剪枝是解决过拟合问题的重要手段主要分为“预剪枝”和“后剪枝”两种。在剪枝的时候我们要引入验证集用来帮助我们判断是否需要剪枝。
预剪枝
预剪枝是边生成决策树边剪枝的一种做法。基于信息增益准则或者增益率准则或者基尼指数我们会选出最优的特征来进行数据集的划分这个时候预剪枝做的就是判断划分前后验证集的精度是否会提高如果提高的话就进行划分否则不进行划分也就是剪枝了。 预剪枝可以降低过拟合的风险而且还显著减少了决策树的训练时间开销和测试时间开销。 不过预剪枝是一种贪心的做法有些划分可能在当前不能提高性能但在之后的划分中可以显著提高决策树的性能所以预剪枝有着欠拟合的风险。
后剪枝
后剪枝是先生成一颗完整的决策树然后自底向上地进行剪枝判断某个分支结点替换为叶子结点后是否会提高验证集的精度可以提高则将分支结点替换为叶子结点否则不替换。 后剪枝比预剪枝保留了更多的分支欠拟合的风险很小泛化性能也往往优于预剪枝。但后剪枝的训练时间开销要比预剪枝大得多。
连续值的处理
以上讨论的都是针对离散特征进行处理的如果遇到了属性为连续值的特征往往采用二分法进行处理。 给定样本集DDD和连续特征colcolcol假定在colcolcol上出现了mmm个不同的取值将这些值从小到大进行排序即为{a1,a2,...,am}\{a^1,a^2,...,a^m\}{a1,a2,...,am}。基于划分点ttt可将DDD划分为子集Dt−D_t^-Dt−和DtD_t^Dt其中Dt−D_t^-Dt−中包含了在特征colcolcol上取值小于ttt的样本而DtD_t^Dt中包含了在特征colcolcol上取值不小于ttt的样本ttt的取值属于集合
Ta{aiai12∣1≤i≤m−1}T_a\{\dfrac{a^ia^{i1}}{2}|1\leq i \leq m-1\}Ta{2aiai1∣1≤i≤m−1}
之后可以基于不同的ttt值进行数据集划分选择使得信息增益准则或者增益率准则最大或者基尼指数最小的ttt作为划分点。
缺失值的处理
现实数据中往往会遇到不完成的样本即样本的某些值有缺失这时候如果放弃该样本不用则太过浪费所以一般做如下处理。 给定训练集DDD和特征colcolcol令D^\hat{D}D^表示在特征colcolcol上没有缺失值的样本子集。我们给每个样本xxx赋予一个权重wxw_xwx并定义
ρ∑x∈D^wx∑x∈Dwx\rho\dfrac{\sum_{x \in \hat{D}}w_x}{\sum_{x \in D}w_x}ρ∑x∈Dwx∑x∈D^wx
不难看出对于特征colρ\rhoρ表示无缺失值样本所占的比例。这样一来比如信息增益就可以推广为
Gain(D,col)ρ⋅Gain(D^,col)Gain(D,col)\rho \cdot Gain(\hat{D},col) Gain(D,col)ρ⋅Gain(D^,col)
其它的准则也可以用类似的方法进行转换。
结束语
以上是对决策树部分知识的小结。如有不足还请指正~
参考文献
[1] 周志华. 机器学习 : Machine learning[M]. 清华大学出版社, 2016. [2] Peter Harrington. 机器学习实战[M]. 人民邮电出版社, 2013.
