没有合适的资源?快使用搜索试试~ 我知道了~
【监督学习】- 分类(决策树)
6 下载量 73 浏览量
2020-12-21
13:34:26
上传
评论
收藏 600KB PDF 举报
温馨提示
试读
14页
决策树 决策树(decision tree) 是一种基本的分类与回归方法。本博客主要讨论用于分类的决策树。决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。学习时,利用训练数据,根据损失函数最小化的原则建立决策树模型。预测时,对新的数据,利用决策树模型进行分类。 决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的修剪。这些决策树学习的思想主要来源于由Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法,以及由Breiman等人在1984年提出的CART算法。本文首先介绍决策树的基本概念,然后介绍特征的选择、决策树的生成以及决策树的修剪,最后通过
资源推荐
资源详情
资源评论
【监督学习】【监督学习】- 分类(决策树)分类(决策树)
决策树决策树
决策树决策树(decision tree) 是一种基本的分类与回归方法。本博客主要讨论用于分类的决策树。决策树模型呈树形结构,在分类
问题中,表示基于特征对实例进行分类的过程。学习时,利用训练数据,根据损失函数最小化的原则建立决策树模型。预测
时,对新的数据,利用决策树模型进行分类。
决策树学习通常包括3个步骤:特征选择特征选择、决策树的生成决策树的生成和决策树的修剪决策树的修剪。这些决策树学习的思想主要来源于由Quinlan在
1986年提出的ID3算法和1993年提出的C4.5算法,以及由Breiman等人在1984年提出的CART算法。本文首先介绍决策树的基
本概念,然后介绍特征的选择、决策树的生成以及决策树的修剪,最后通过案例实现决策树模型。
相关学习链接:相关学习链接:
1:监督学习框架::监督学习框架:思维导图-python.
1:机器学习:机器学习GitHub代码:代码:点我下载.
1:机器学习实战视频::机器学习实战视频:ApacheCN_机器学习实战.
目录目录决策树相关学习链接:1 决策树模型1.1 决策树场景1.2 决策树与条件概率分布2 决策树的构造2.1 信息增益2.2 代码计算
经验熵2.3 代码计算信息增益3 决策树的生成与修剪3.1 ID3算法3.2 C4.5生成算法3.3 决策树的修剪4 测试案例1:决策树预测
隐形眼镜类型一:导入sklearn库二:决策树的使用三:预测类型5 测试案例2:鸢尾花数据集分类
1 决策树模型决策树模型
1.1 决策树场景决策树场景
决策树 场景
特征:
1.不浮出水面是否可以生存
2.是否有脚蹼
案例案例1: 判定鱼类和非鱼类判定鱼类和非鱼类
根据以上2 个特征,将动物分成两类:鱼类和非鱼类鱼类和非鱼类。
决策树由结点(node)和有向边(directed edge)组成。结点有两种类型:内部结点内部结点(intermal node)和和叶结点叶结点(leaf node)。内
部结点表示一个特征或属性,叶结点表示一个类。
用决策树对鱼类和非鱼类分类,从根结点开始,对实例的两类特征进行测试,根据测试结果,将实例分配到其子结点中,
这时,每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配,直至达到叶结点,最后将所有实例分到叶
结点的类中。
1.2 决策树与条件概率分布决策树与条件概率分布
决策树还表示给定特征条件下类的条件概率分布。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组
成。假设X为表示特征的随机变量,Y为表示类的随机变量,那么这个条件概率分布可以表示为P(Y|X)。 X取值于给定划分下
单元的集合,Y 取值于类的集合。各叶结点(单元)上的条件概率往往偏向某概率较大一个特定的类。 决策树分类时将该结点的
实例强行分到条件概率大的那一类中。
将特征空间划分为互不相交的单元(cell) 或区域(region), 并在每个单元定义一个类的概率分布就构成了一个条件概率分
布。决策树的每一条路径对应于划分中的一个单元。
图(a)表示了特征空间的一个划分,图中的大正方形表示特征空间。这个大正方形被若干个小矩形分割,每个小矩形表示
一个单元,特征空间划分上的单元构成了一个集合,X取值为单元的集合,为简单起见,假设只有两类:正类和负类,即r取值
为+1和-1。小矩形中的数字表示单元的类,此次模型被分成2类4个单元。
在决策树学习中,假设给定训练数据集 D={(x1,y1),(x2,y2),⋯ ,(xN,yN)}D = \left\{ {\left( {{x_1},{y_1}} \right),\left( {{x_2},
{y_2}} \right), \cdots ,\left( {{x_N},{y_N}} \right)} \right\}D={(x1,y1),(x2,y2),⋯,(xN,yN)}其中,x=(xi(1),xi(2),⋯ ,xi(n))Tx = {\left(
{x_i^{\left( 1 \right)},x_i^{\left( 2 \right)}, \cdots ,x_i^{\left( n \right)}} \right)^T}x=(xi(1),xi(2),⋯,xi(n))T为输入实例(特征向量),n
为特征个数,yi∈{1,2,⋯ ,K}{y_i} \in \left\{ {1,2, \cdots ,K} \right\}yi∈{1,2,⋯,K}为类标记,i=1,2,⋯ ,Ni = 1,2, \cdots
,Ni=1,2,⋯,N,N为样本容量。学习的目标是根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。
2 决策树的构造决策树的构造
特征选取:特征选取: 在训练特征数据(属性)中选取具有分类能力最强的特征。
如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的。经验上扔掉这样的
特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。
1:特征的选择是决定用哪个特征来划分特征空间。:特征的选择是决定用哪个特征来划分特征空间。
例如:申请贷款的人有4种特征属性,
1.年龄:青年、中年、老年
2.有无工作:是、否
3.有无房子:是、否
4.信贷情况:非常好、好、一般
在对上述的特征制定一个贷款申请的决策树,用以对未来的贷款申请进行分类,即当新的客户提出贷款申请时,根据申请
人的特征利用决策树决定是否批准贷款申请。
2:于是选取哪个特征作为根节点?:于是选取哪个特征作为根节点?
以下有两种(a)(b)不同特征作为根节点,决定的是不同的决策树。
(a)所示的根结点的特征是年龄,有3个取值,对应于不同的取值有不同的子结点。(b)所示的根结点的特征是有工作,有2
个取值。对应于不同的取值有不同的子结点。两个决策树都可以从此延续下去。
3:究竞选择哪个特征更好些:究竞选择哪个特征更好些?
于是就要求一种能够确定选择特征的准则,信息增益信息增益(information gain) 就能够很好地表示这一直观的准则.
2.1 信息增益信息增益
了解信息增益,首先引入熵的定义。
熵:熵: 熵(entropy) 是表示随机变量不确定性的度量。在不同的学科中也有引申出的更为具体的定 义,是各领域十分重要的
参量。
设X是一个取有限个值的离散随机变量,其概率分布为
P(X=xi)=pi,i=1,2,…..,nP\left( {X = {x_i}} \right) = {p_i},{\kern 1pt} {\kern 1pt} {\kern
1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} i = 1,2,…..,nP(X=xi)=pi,i=1,2,
…..,n
则随机变量X的熵定义为
H(X)=−∑i=1npilogpiH\left( X \right) = – \sum\limits_{i = 1}^n {{p_i}\log
{p_i}}H(X)=−i=1∑npilogpi
由定义可知,熵只依赖于X的分布,而与X的取值无关。
例如:当随机变量只取两个值1、0时,及X的分布为:
P(X=1)=p,P(X=0)=1−p,0≤p≤1P\left( {X = 1} \right) = p{\kern 1pt} {\kern 1pt} {\kern 1pt} ,
{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} P\left( {X = 0} \right) = 1 –
p{\kern 1pt} {\kern 1pt} {\kern 1pt} ,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt}
{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 0 \le p \le 1P(X=1)=p,P(X=0)=1−p,0≤p≤1
熵为:
H(p)=−plog2p−(1−p)log2(1−p)H\left( p \right) = – p{\log _2}p – \left( {1 – p} \right){\log
_2}\left( {1 – p} \right)H(p)=−plog2p−(1−p)log2(1−p)
我们发现当p=0或p=1时,H(p)H\left( p \right)H(p)=0,随机变量完全没有不确定性。当p=0.5 时,H(p)H\left( p \right)H(p)=1,
熵取值最大,随机变量不确定性最大。
信息熵(香农熵)信息熵(香农熵): 是一种信息的度量方式,表示信息的混乱程度,也就是说:信息越有序,信息熵越低。
条件熵条件熵H(Y| X): 表示在已知随机变量X的条件下随机变量Y的不确定性。
随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y\X), 定义为X给定条件下Y的条件概率分布的熵对X
的数学期望。
H(Y∣X)=∑i=1npiH(Y∣X=xi)H\left( {Y|X} \right) = \sum\limits_{i = 1}^n {{p_i}H\left( {Y|X = {x_i}}
\right)}H(Y∣X)=i=1∑npiH(Y∣X=xi) 其中,pi=P(X=xi)i=1,2,…..,n{p_i} = P\left( {X = {x_i}} \right){\kern 1pt} {\kern 1pt} {\kern
1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} i = 1,2,…..,npi=P(X=xi)i=1,2,…..,n
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵与条件熵分别称为经验熵经验熵(empiricalentropy)
和经验条件熵经验条件熵(empiricalconditional entropy)。
信息增益信息增益: 在划分数据集前后信息发生的变化称为信息增益。
特征 A对训练数据集D的信息增益g(D,4),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,
即:
g(D,A)=H(D)−H(D∣A)g\left( {D,A} \right) = H\left( D \right) – H\left( {D|A}
\right)g(D,A)=H(D)−H(D∣A)
在模式识别书籍中, 熵H(Y)与条件熵H(Y |X)之差称为互信息(mutual information)。决策树学习中的信息增益等价于训练
数据集中类与特征的互信息。
2.2 代码计算经验熵代码计算经验熵
设训练数据集为D, ∣D∣|D|∣D∣表示其样本容量,即样本个数。设有K个类Ck{C_k}Ck, k=1,2…,K,∣D∣|D|∣D∣为属于类
Ck{C_k}Ck的样本个数,∑k=1k∣Ck∣=∣D∣\sum\limits_{k = 1}^k {|{C_k}|} = |D|k=1∑k∣Ck∣=∣D∣。设特征A有n个不同的取
值{a1,a2,…,an}\left\{ {{a_1},{a_2},…,{a_n}} \right\}{a1,a2,…,an}根据特征A的取值将D划分为n个子集 D1,D2,…,Dn{{D_1},
{D_2},…,{D_n}}D1,D2,…,Dn,∣Di∣|D_i|∣Di∣为DiD_iDi的样本个数,∑i=1n∣Di∣=∣D∣\sum\limits_{i = 1}^n {|{D_i}|} =
|D|i=1∑n∣Di∣=∣D∣。 记子集DiD_iDi中属于类CkC_kCk的样本的集合为Dik{D_{ik}}Dik,即Dik=Ck∩Di{D_{ik}} = {C_k} \cap
{D_i}Dik=Ck∩Di,∣Dik∣|{D_{ik}}|∣Dik∣为Dik{D_{ik}}Dik的样本个数。
(1) 计算数据集计算数据集D的经验熵的经验熵:H(D)H\left( D \right)H(D)
H(D)=−∑k=1K∣Ck∣∣D∣log2∣Ck∣∣D∣H\left( D \right) = –
\sum\limits_{k = 1}^K {\frac{{|{C_k}|}}{{|D|}}} {\log _2}\frac{{|{C_k}|}}{{|D|}}H(D)=−k=1∑K∣D∣∣Ck∣log2∣D∣∣Ck∣
剩余13页未读,继续阅读
资源评论
weixin_38726186
- 粉丝: 5
- 资源: 895
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功