三大决策树的比较——ID3、C4.5、CART
·
| 类型 | ID3 | C4.5 | CART |
|---|---|---|---|
| 解决问题 | 分类 | 分类 | 分类、回归 |
| 划分指标 | 信息增益 | 增益率 | 基尼指数 |
| 指标特点 | 会偏向可取值数目加多的属性 | 会偏向可取值数目较少的属性 | |
| 属性选择 | 选择信息增益最大的属性 | 先找出信息增益高于平均水平的属性，再从中选择增益率最高的 | 选择划分后基尼指数最小的属性 |
| 划分规则 | 多叉的 | 多叉的 | 二叉的，所以选择最优特征后还需要决定该特征的最优二值切分点 |
| 优缺点 | DI3会偏向可取值数目加多的属性 ID3算法并未给出处理连续数据的方法 ID3算法不能处理带有缺失值的数据集 ID3算法只有树的生成, 所以容易过拟合 | C4.5可以处理连续值 C4.5时间耗费大 | CART可以解决回归问题 |
其中，
- 信息熵定义：
Ent(D)=−∑k=1npklog2pkEnt(D)=-\sum_{k=1}^{n}p_klog_2p_kEnt(D)=−k=1∑npklog2pk
其中 nnn 为D中的类别数。 - 信息增益定义：
离散属性a有V个可能取值，使用a对样本集D划分，产生V个子样本集Dv{D^v}Dv，则用属性a对样本集D进行划分所获得的信息增益为$Gain(D,a)=Ent(D)−∑v=1VC(Dv)C(D)Ent(Dv)Gain(D,a)=Ent(D)-\sum_{v=1}^{V}{\frac{C(D^v)}{C(D)}Ent(D^v)}Gain(D,a)=Ent(D)−v=1∑VC(D)C(Dv)Ent(Dv)
其中 C(D) 表示集合 D 的大小。 - 增益率定义：
Gain_ratio(D,a)=Gain(D,a)IV(a)Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}Gain_ratio(D,a)=IV(a)Gain(D,a)
其中，IV(a)=−∑v=1VC(Dv)C(D)log2C(Dv)C(D)IV(a)=-\sum_{v=1}^V{\frac{C(D^v)}{C(D)}log_2\frac{C(D^v)}{C(D)}}IV(a)=−v=1∑VC(D)C(Dv)log2C(D)C(Dv)称为属性 a 的“固有值”。属性 a 的可能取值数目越多，则 IV(a) 的值通常会越大。 - 基尼指数定义：
Gini_index(D,a)=∑v=1VC(Dv)C(D)Gini(Dv)Gini\_index(D,a)=\sum_{v=1}^V\frac{C(D^v)}{C(D)}Gini(D^v)Gini_index(D,a)=v=1∑VC(D)C(Dv)Gini(Dv)
其中 Gini(D)=1−∑k=1npk2Gini(D)=1-\sum_{k=1}^np_k^2Gini(D)=1−k=1∑npk2称为数据集 D 的基尼值。
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
0
0- 0
已为社区贡献9条内容
所有评论(0)