决策树

作者: 吴金君 | 来源:发表于2018-08-06 15:04 被阅读0次

1. 引言

决策树的学习通常包括三个步骤：特征选择，决策树的生成和决策树的修剪，本文梳理一下ID3，C4.5和CART. 首先给出决策树的算法流程框架，其次分别给出ID3，C4.5和CART特征选择的依据，最后讨论决策树的修剪。

2. 决策树算法框架

先给出分类决策树的算法流程框架。

算法：决策树生成算法TreeGrowth()
输入：训练集D，特征集A
输出：决策树T
1: if stoping_cond(D,A)=ture then //如果所有记录同属于一类
2: leaf = createNode() //创建一个结点，结点为一个测试条件node.test_cond或一个类标node.label
3: leaf.label=Classify(D) //*为叶结点确定类标，一般指派为具有最多数目记录的类别
4: return leaf //返回叶结点
5:else
6: root=createNode() //创建根节点
7: root.test_cond = find_best_split(D,A) //确定哪个属性作为划分训练记录的测试条件
8: 令V={v\|v是root.test_cond的一个可能的输出}
9: for 每个 $v \in V$ do
10: $D_v$ ={ $d$ \|root.test_cond( $d$ )=v并且 $d \in D$ } //将满足测试条件的数据 $d$ 并入子集 $D_v$
11: child=TreeGrowth( $D_v$ , $A$ ) //递归调用生成树算法TreeGrowth()，生成孩子结点
12: 将child作为root的派生结点添加到树中，并将边(root $\rightarrow$ child)标记为v
13: end for
14:end if
15:return root

2 特征选择依据

2.1 ID3算法

原则：选择信息增益最大的特征作为划分依据
信息增益：
输入：训练数据集 $D$ 和特征 $A$
输出：特征 $A$ 对训练数据集D的信息增益 $g(D,A)$ .
(1) 计算数据集 $D$ 的经验熵 $D$
$H(D)=-\sum_{j=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$
(2)计算特征 $A$ 对于数据集 $D$ 的条件熵 $H(D|A)$
$H(D|A)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|}$
(3)计算信息增益 $g(D,A)$
$g(D,A)=H(D)-H(D|A)$

2.2 C4.5算法

原则：选择信息增益率最大的特征作为划分依据
信息增益率：
$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$
其中， $H_A(D)$ 是数据集 $D$ 关于特征 $A$ 的熵，n是特征A取值的个数.
$H_A(D)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{D_i}{D}$

2.3 CART算法

原则：选择基尼指数最小的特征作为划分依据
基尼指数：
$Gini(D)=\sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^{K}p_k^2$
其中， $p_k$ 表示多分类问题中样本点属于第k类的概率。
二分类中:
$Gini(D)=2p(1-p)$
多分类中:
$Gini(D)=1-\sum_{k=1}^{K}(\frac{|C_k|}{|D|})$
其中，C_k是D中属于第k类的样本子集，K是类的个数

3 决策树的剪枝

未完待续

网友评论

本文标题：决策树

本文链接：https://www.haomeiwen.com/subject/dnkwvftx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

决策树