admin管理员组文章数量:1663061
文章目录
- 1. C4.5
- 1.1. 1.1 Feature:
- 1.1.1. Advantage
- 1.1.2. Disadvantage
- 1.2. 1.2 Describe
- 1.2.1. 决策树剪枝
- 1.2.2. 连续型属性
- 1.2.3. 缺失值处理
- 1.2.4. 规则集诱导
- 1.3. Theory
- 1.3.1. 递归伪代码
- 1.3.2. 每个结点的特征选取
- 1.3.2.1. 信息熵计算
- 1.3.2.2. 信息熵增益
- 1.3.2.3. 信息熵增益率
- 1.3.3. 如何确定叶节点类
- 1.3.4. 剪枝问题(所有基于决策树的算法)
- 1.3.4.1. 预剪枝(prepruning)
- 1.3.4.2. 后剪枝(post-pruning)
- 1.3.5. 连续和缺失值的处理
- 1.3.5.1. 连续值处理
- 1.3.5.2. 缺失值处理
- 1.4. Scope of application
- 2.2. Theory
- 2.2.1. 划分原理
- 2.2.1.1. Gini指数的概念
- 2.2.1.2. Gini指数增益(子集划分原理)
- 2.2.2. 模型树
- 2.2.2.1. 后剪枝
- 2.3. Others
- 2.3.1. Difference of C4.5/ID3/CART
- 2.3.2. Advantages of Tree Regression
- 3. Reference
1. C4.5
1.1. 1.1 Feature:
-
有监督学习
-
ID3的一种决策树诱导算法。ID3被称为迭代分解器(iterative dichotomizers)第三代。
-
除了诱导出决策树,还可以将决策树转换成具有良好理解性的规则。
-
通过C4.5的后剪枝操作得到的分类器不能在精确地被转换会决策树。
1.1.1. Advantage
- 良好的可理解性的规则
- 剪枝能力
- 计算复杂度不高
- 中间值缺失不敏感
- 可以处理不相关特征数据
1.1.2. Disadvantage
- 可能产生过度匹配的问题
1.2. 1.2 Describe
遵循传统的递归模式,首先用根节点表示一定量的数据集,从根节点开始每个结点测试一个特定的属性(该属性有算法确定),根据这个属性将数据集划分成更小的子集,用子树表示。直到子集中所有的数据集都是同一类别,该节点停止分裂。
1.2.1. 决策树剪枝
目的:解决过拟合的问题。通常在树全部生成之后进行,而且采用自下而上的方式。
-
基于成本复杂度的剪枝(cost-complexity pruning)
-
错误消减剪枝(Reduce error pruning)是上个方法的简化版本
-
悲观剪枝(Pessimistic pruning),C4.5算法创造性的提出。
-
基于理想置信区间剪枝(confidence intervals, CI),悲观剪枝的扩展
1.2.2. 连续型属性
1.2.3. 缺失值处理
1.2.4. 规则集诱导
1.3. Theory
1.3.1. 递归伪代码
#createBranch函数:递归
检测当前数据集中每个example是否是同一个类:
if 是同一个类 or 实例总数低于某阀值
return 类标签
else
寻找划分该数据集的最好的feature
划分数据集
创建分支结点
for 每个划分的子集
越大 调用createBranch并增加返回结果到分支节点中 #递归调用自己
return 分支节点
1.3.2. 每个结点的特征选取
使用信息熵增益(gain)
和增益率(gain ratio)
。
信息熵增益
准则的一个缺陷在于过于偏向选择具有更多输出结果的测试
增益率
能够克服信息熵增益
的短板。C4.5默认使用信息熵增益率
。
1.3.2.1. 信息熵计算
对于不相关的时间x和y,同时发生的信息熵就是他们两个的和:
H ( x , y ) = H ( x ) + H ( y ) H(x,y)=H(x)+H(y) H(x,y)=H(x)+H(y)
p ( x , y ) = p ( x ) p ( y ) p(x,y)=p(x)p(y) p(x,y)=p(x)p(y) 两事件不相关
所以,对于n个事件,同时发生的信息熵为。
H ( x ) = − ∑ i = 1 n p ( x i ) l o g ( p ( x i ) ) H(x)=-\sum^n_{i=1} p(x_i)log(p(x_i)) H(x)=−i=1∑np(xi)log(p(xi))
p ( x i ) p(x_i) p(xi)代表x事件的概率。机器学习里可以表某个类的概率
n为分类的数目
- 概率越小的所含有的信息量越大。
概率发生小的事情人比较震撼,百分之百发生的事情人的反应比较小。
- 有log的原因是log可以使让累加计算变成真数相乘。选择2是普遍传统,可以自己改。
1.3.2.2. 信息熵增益
某属性下两次信息熵的差值。信息熵的下降幅度。信息熵增益越大,说明信息熵的下降幅度越高,特征选择的效果越好,纯净度越高。
划分之前的信息熵( H(D) )减去划分之后每个子集的信息熵加权平均。
G a i n ( D , a ) = H ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ H ( D v ) Gain(D,a)=H(D)-\sum^V_{v=1} \frac{|D^v|}{|D|}H(D^v) Gain(D,a)=H(D)−v=1∑V∣D∣∣Dv∣H(Dv)
H(D) 该节点的信息熵增益
∣ D v ∣ |D_v| ∣Dv∣ : D结点的分出来的第V个类所含有的example数量∣ D ∣ |D| ∣D∣: D结点总的example数量
∣ D v ∣ ∣ D ∣ \frac{|D^v|}{|D|} ∣D∣∣Dv∣: v类在D结点中的概率
H ( D v ) H(D_v) H(Dv): v类的信息熵增益
缺点:会倾向选择那些属性取向值较多的属性。
分析:当上述公式中v的种类很多,导致每个类中example很小,也就是说 ∣ D v ∣ |D_v| ∣Dv∣很小时, D v ∣ D ∣ \frac{D^v}{|D|} ∣D∣Dv趋近于0,此时如果v类中的纯净度还很高, H ( D v ) H(D^v) H(Dv)也趋近于0。所以此时信息上增益最大。但是这种划分可能毫无意义。
例如极端情况,以学生ID作为分类的属性,ID可以有很多取值。由于每个学生ID都是唯一的。所以 H ( D v ) H(D^v) H(Dv)是0。此时计算出来的Gain(D,a)是最大的。按照要求选择ID属性划分很理想,但是这种划分并不能说明什么问题,没有意义。
1.3.2.3. 信息熵增益率
用来解决信息熵增益的选择倾向问题。
G a i n R a t i o ( a ) = G a i n ( a ) E n t r o p y ( a ) GainRatio(a)=\frac{Gain(a)}{Entropy(a)} GainRatio(a)=Entropy(a)Gain(a)
Entropy(a): a的熵
Gain(a): a的信息增益
**缺点:**信息熵的增益率对属性取值较少的属性有所偏好。
C4.5并不是直接选择增益率最大的属性作为划分属性,而是之前先通过一遍筛选,先把信息增益低于平均水平的属性剔除掉,之后从剩下的属性中选择信息增益率最高的,这样的话,相当于两方面都得到了兼顾。
1.3.3. 如何确定叶节点类
所占数量最多的。
1.3.4. 剪枝问题(所有基于决策树的算法)
剪枝问题是为了解决决策树的过拟合问题,几乎所有的基于决策树的算法都有可能存在过拟合。主要原因是把训练集自身的一些特点当做该类问题共有的特点,失去了一般性。降低过拟合问题,能够提升决策树的泛化能力。
1.3.4.1. 预剪枝(prepruning)
预剪枝是在决策树生成的过程中,对每个结点在划分前进行估计,如果结点的划分并不能够提升整个树的泛化能力,那么当前节点就不再划分,标记为叶节点。
预剪枝需要对划分前后的泛化性能进行评估。这时需要验证集
参与评估。通过验证集对划分和不划分两种情况精度进行计算,从而确定是否划分该结点。如果不划分,则确定为叶节点,选择数量多的类作为这个叶子的分类。
- 预剪枝会导致决策树许多分支不用展开。降低了过拟合的风险,减少了训练的计算开销。
- 有可能给决策树欠拟合。某些结点可能划分后暂时降低了泛化能力,但是该结点后续的划分可能显著提高。由于决策树是贪心算法,这种情况就不能考虑到。
1.3.4.2. 后剪枝(post-pruning)
通过训练集已经生成一颗完整的树,然后自底向上对非叶节点进行考察,如果该节点对应的子树变成叶节点后,能够提升决策树的 泛化性能,那么子树就被替换成叶节点
后剪枝涉及树的遍历。简而言之就是自下而上遍历非叶子结点。然后尝试替换成叶节点,计算替换后在验证集上的精确度,如果能够提升,就替换,否则就继续遍历。
1.3.5. 连续和缺失值的处理
1.3.5.1. 连续值处理
属性如果不是离散值,比如某个房子的属性之一面积。需要将连续属性离散化处理。
最简单的方法就是采用二分法(bi-partition)
。C4.5就是采用的这种方法。
比如房子的面积属性为从小到大排列
{
a
1
,
a
2
,
.
.
.
a
n
}
\{a_1,a_2,...a_n\}
{a1,a2,...an},n个example可能有n个不同的取值。将这n个examples分成两个数据集,一个数据集是小于t (t是分隔线), 一个数据集大于t。
一共有n-1中分法,即有n-1个t可取。
t
i
=
a
i
+
a
i
+
1
2
,
1
≤
i
≤
n
−
1
t_i=\frac{a_i+a_{i+1}}{2} ,1 \leq i \leq n-1
ti=2ai+ai+1,1≤i≤n−1
寻找使分隔标准(信息熵增益或者增益率,看具体算法)最大的t点作为分割线。
1.3.5.2. 缺失值处理
Q1:属性值缺失时,如何进行属性划分?
引入样本的权重。每个样本的权重为
w
x
w_x
wx。所含信息较多的样本,权重就大一些。
有属性a,且a的取值有 a 1 , a 2 . . . . a v {a^1,a^2....a^v} a1,a2....av,共b种可能取值。
ρ = ∑ 无 缺 失 值 的 样 本 权 重 ∑ 所 有 样 本 的 权 重 , p ~ k = ∑ 第 k 类 上 无 缺 失 值 样 本 权 重 ∑ 无 缺 失 值 样 本 权 重 r ~ v = ∑ 属 性 值 是 v 的 无 缺 失 值 样 本 的 权 重 ∑ 无 缺 失 值 样 本 的 权 重 \rho=\frac{\sum 无缺失值的样本权重}{\sum 所有样本的权重}, \\ \tilde{p}_k = \frac{\sum 第k类上无缺失值样本权重}{\sum 无缺失值样本权重} \\ \tilde{r}_v = \frac{\sum 属性值是v的无缺失值样本的权重}{\sum 无缺失值样本的权重} ρ=∑所有样本的权重∑无缺失值的样本权重,p~k=∑无缺失值样本权重∑第k类上无缺失值样本权重r~v=∑无缺失值样本的权重∑属性值是v的无缺失值样本的权重
ρ \rho ρ 无缺失值样本所占的比例
p ~ k \tilde{p}_k p~k无缺失值样本中第k类所占的比例
r ~ v \tilde{r}_v r~v无缺失值样本中在属性a上取 a v a^v av的样本所占的比例。
信息熵变为:
E n t ( D ~ ) = − ∑ i = 1 n p ~ ( x i ) l o g ( p ~ ( x i ) ) Ent(\tilde{D})=-\sum^n_{i=1} \tilde {p}(x_i)log(\tilde{p}(x_i)) Ent(D~)=−i=1∑np~(xi)log(p~(xi))
信息熵增益:
G
a
i
n
(
D
,
a
)
=
ρ
×
G
a
i
n
(
D
~
,
a
)
=
ρ
×
(
E
n
t
(
D
~
)
−
∑
v
=
1
V
r
~
v
E
n
t
(
D
~
v
)
)
Gain(D,a)=\rho \times Gain(\tilde{D},a) \\ =\rho \times (Ent(\tilde D)-\sum^V_{v=1} \tilde{r}_v Ent(\tilde{D}^v))
Gain(D,a)=ρ×Gain(D~,a)=ρ×(Ent(D~)−v=1∑Vr~vEnt(D~v))
Q2: 在某个属性上,若样本在该属性上的属性值确实,怎么划分这个样本?
选择划分属性为
a
v
a^v
av时,对于
a
v
a^v
av属性未知的样本x,就把样本x以不同的概率同时划分到
a
v
a^v
av属性下的每个子节点中,x的权重w在对应的子节点中调整为
r
~
v
⋅
w
x
\tilde{r}_v\cdot w_x
r~v⋅wx。
1.4. Scope of application
数据行和标称型
- 处理分类问题
- 专家系统
2.2. Theory
2.2.1. 划分原理
2.2.1.1. Gini指数的概念
Gini是一种不等性的度量,比如用来度量收入不平衡。
取值返回是0~1,0代表完全相等,1代表完全不相等。总体内部包含的类别越杂乱,Gini指数越大。类似熵的概念
G i n i ( T ) = 1 − ∑ j = 1 n p j 2 Gini(T)=1-\sum_{j=1}^{n}p_j^2 Gini(T)=1−j=1∑npj2
n代表T集合中的类别数)-\
p j p_j pj代表该类别的概率
2.2.1.2. Gini指数增益(子集划分原理)
G i n i G a i n ( T ) = ∑ N i N G i n i ( T i ) GiniGain(T)=\sum{\frac{N_i}{N}Gini(T_i)} GiniGain(T)=∑NNiGini(Ti)
i:特征的第i个取值。
对于二分法,选取某个特征,会将集合T分成两个子集合,T1和T2。
则该特征的GiniGain(Gini增益)
G i n i G a i n ( T ) = N 1 N G a i n ( T 1 ) + N 2 N G a i n ( T 2 ) GiniGain(T)=\frac{N_1}{N}Gain(T_1)+\frac{N_2}{N}Gain(T2) GiniGain(T)=NN1Gain(T1)+NN2Gain(T2)
Ni为Ti集合中example数量
N为T集合中example数量
计算每个特征的GiniGain,选择最小的那个特征的GiniGain。
2.2.2. 模型树
用数来对数据建模,出了吧叶节点简单设置为常数,还有一种方法是设定为分段的线性函数。有多个现行片断组成所需要建立的模型。
2.2.2.1. 后剪枝
2.3. Others
2.3.1. Difference of C4.5/ID3/CART
- ID3决策树利用信息熵增益来划分结点
- C4.5决策树:先算信息熵增益,去掉低于平均值的,然后取增益率最高的
- CART决策树(Classification And Regression Tree):可用于分类和回归,划分结点基于GINI
ID3 :对于连续变量必须进行离散化,但是离散化后的变量会失去一部分联系。
2.3.2. Advantages of Tree Regression
- 可以对复杂和非线性的数据建模。
3. Reference
Perter Harrington.机器学习实战[M]
周志华.机器学习[M]
版权声明:本文标题:机器学习——基于决策树的C4.5、CART算法原理和区别 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1729982569a1218412.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论