决策树

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

机器学习6-决策树
决策树
决策树
决策树算法总结
机器学习 - 决策树算法[一]
机器学习系列（三十六）——回归决策树与决策树总结
[机器学习]决策树
经典机器学习系列之【决策树详解】
第5章决策树
决策树与随机森林

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 决策树的剪枝

未完待续

机器学习6-决策树
一. 决策树概述 1.1 什么是决策树决策树输入: 测试集决策树输出: 分类规则(决策树) 1.2 决策树算法概...
决策树
1、决策树决策树学习通常包括3个步骤：特征选择。决策树生成。决策树剪枝。决策树的学习目标是：根据给定的训...
决策树
决策树决策树模型与学习特征选择决策树的生成决策树的剪枝 CART 算法决策树模型呈树形结构，在分类问题中...
决策树算法总结
目录一、决策树算法思想二、决策树学习本质三、总结一、决策树（decision tree）算法思想：决策树...
机器学习 - 决策树算法[一]
1 决策树模型与学习 1.1 决策树模型决策树定义：分类决策树模型是一种描述对实例进行分类的树形结构。决策树由...
机器学习系列（三十六）——回归决策树与决策树总结
本篇主要内容：回归决策树原理、回归树学习曲线、决策树总结回归决策树原理回归决策树树是用于回归的决策树模型，回归...
[机器学习]决策树
决策树 @(技术博客)[机器学习, 决策树, python] 学习决策树首先要搞清楚决策树是什么（what），在弄...
经典机器学习系列之【决策树详解】
这节我们来讲说一下决策树。介绍一下决策树的基础知识、决策树的基本算法、决策树中的问题以及决策树的理解和解释。 ...
第5章决策树
内容一、决策树内容简介二、决策树的模型与学习三、特征选择四、决策树生成五、决策树剪枝六、CART算法 ...
决策树与随机森林
PART I 决策树 (Decision Tree) 决策树基本知识决策树何时停止生长：(I) all leaf...