关键词：
决策树
一.决策树基本描述
决策树是一种基本的分类与回归方法,呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程.学习时,利用训练数据根据损失函数最小化的原则建立决策树模型.预测时,对新的数据,利用决策树模型进行分类.而学习又通常包括三个步骤:特征选择,决策树生成,决策树修剪.
二.决策树模型与学习
1.决策树模型
决策树定义:
分类决策树模型是一种描述对实例进行分类的树形结构,决策树由节点(node)和有向边(directed edge)组成.节点有两种类型:内部节点(internal node)和叶节点(leaf node).内部节点表示一个特征或者属性,而叶节点表示一个类.
2.决策树与if-then规则
决策树可以看成一个if-then规则的集合.具体做法就是,从根节点到叶节点的每条路构建一个规则,路径上内部节点的特征对应着规则条件,叶节点的类则对应着规则的结论.因此决策树及其对应的if-then规则还有一个重要性质,互斥并且完备.即一对一且不会有实例对不上任何一条路.
3.决策树与条件概率分布
决策树还表示给定特征条件下类的条件分布概率,
???
4.决策树的学习
决策树学习的目标就是根据给定的训练数据集构建一个决策模型,使它能够对实例进行正确分类.但生成的决策树(能对训练数据进行正确分类)却可能不止一个.这里就用到了损失函数.
决策树学习的损失函数通常是正则化的极大似然函数(不懂),而决策树学习的策略就是以损失函数为目标函数的最小化.当损失函数确定后,学习问题就变为在损失函数意义下选择最优决策树.
学习前,若特征数量很多,可先对特征i进行选择,只留下对训练数据有足够分类能力的特征.
决策树的学习算法通常是一个递归地选择最优特征对训练数据进行分割的过程.开始,将所有数据放在根节点,选择一个最优特征(之后会说如何选择),以它来分割数据集,使得到各子集有一个在当前条件下最好的分类,然后若子集已基本正确分类就构建叶子节点,否则继续对子集选择新的最优特征,分割,如此递归下去,直到所有训练数据子集也都正确分类.(这里确定是否已基本正确分类的条件之后也会说).这样一棵决策树便构建完成.
但这样的决策树对训练数据的分类能力很好,但对测试数据却不一定,容易发生过拟合.因此便需要剪枝,使树简单点,增加其泛化能力.大概思路就是去掉过于细分的叶节点,使它退回到父节点,甚至更高节点,然后将父节点或更高i节点改为叶节点.
综上,决策树的学习算法包括,特征选择,决策树的生成,决策树的剪枝.这里还提到一点,就是决策树的生成相当于考虑局部最优,而剪枝则是考虑的全局最优.
决策树学习常用的算法有ID3,C4.5, CART等
三.特征选择
1.特征选择问题
特征选择在于选择对训练数据最具有分类能力的特征.而评判信息选择的准则通常是信息增益(信息增益比).即分类的能力强弱是通过信息增益(信息增益比)来具体化的.
2.信息增益
这里先要给出熵与条件熵的定义.
熵是表示随机变量不确定性的度量.设X为一个取值有限的离散随机变量,其概率为
$P(X = x_i)=p_i, i=1,2,cdots,n$
则随机变量X的熵定义为
$H(X)=-sum_i=1^np_ilog p_i$
通常上式是以2或e为底,此时熵的单位分别称作bit或nat.这里可知熵只和X分布有关,而与其取值无关.
且熵越大,随机变量的不确定性就越大.
设有随机变量(X,Y),其联合概率分布为:
$P(X=x_i,Y=y_j)=p_ij, i=1,2,cdots,n;j=1,2,cdots,m$
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性.并定义为
$H(Y|X)=sum_i=1^np_iH(Y|X=x_i)$
其中$p_i=P(X=x_i),i=1,2,cdots,n$
信息增益表示得知特征X的信息后而使类Y的信息的不确定性减少的程度.
定义:特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵(当熵中的概率由数据统计得到时)H(D)与特征A给定条件下D的经验条件熵(同前)H(D|A)之差,即:
$g(D,A)=H(D)-H(D|A)$
一般地,熵H(Y)与条件熵H(Y|X)之差为互信息.决策树学习中的信息增益等于训练数据集中类与特征的互信息.
决策树学习中选择特征就是以信息增益为准则的.对数据集D而言,不同的特征具有不同的信息增益,显然,信息增益打的特征具有更强的分类能力.具体实行方法是:对训练数据集D,计算每个特征的信息增益,并比较其大小,每次选择信息增益最大的特征.
信息增益算法:
例题所需的表
例题
3.信息增益比
信息增益值的大小是相对与训练数据集而言的,并无绝对意义.说白了,就是直接用信息增益来衡量不准.
所以就出现了信息增益比.
定义:
特征A对训练数据集D的信息增益比$g_R(D,A)$定义为其信息增益g(D,A)与训练集D的经验熵H(D)之比:
$g_R(D,A) = fracg(D,A)H(D)$
决策树的生成
1.ID3算法
ID3算法应用信息增益来选则特征,递归地构建决策树.具体方法:从根节点开始,对节点计算所有特征的信息增益,选择增益最大的特征作为节点的特征,由该特征的不同取值建立子节点(此后不会再选择该特征来分割了);再对子节点递归使用如上方法.边界条件:直到所有特征的信息增益均很小或没有特征可选为止.需要注意的是,ID3算法只有树的生成,因此容易产生过拟合.
算法:
例题:
2.C4.5算法
C4.5算法和ID3基本一致,只是C4.5是用信息增益比来选择特征的.
3.决策树的剪枝
决策树生成算法产生的决策树对训练数据往往分类准确,但对测试数据却表现不好,这是由于决策树过复杂导致过拟合.而解决此问题的方法就是降低树的复杂度,即剪枝.
这里介绍的是一种简单的剪枝算法.
决策树的剪枝往往是通过极小化决策树的整体损失函数或代价函数来实现的.设树T的叶节点个数为|T|,t是树T的叶节点.该叶节点有$N_t$个样本点,其中k类的样本点有$N_kt$个,k=1,2,...,K,$H_t(T)$为叶节点t上的经验熵,$alphageq0$为参数,则决策树学习的损失函数可以定义为
$C_alpha(T)=sum_t=1^|T|N_tH_t(T)+alpha|T|$
又其中经验熵为
$H_t(T)=-sum_k fracN_tkN_t logfracN_tkN_t$
所以损失函数中第一项记作
$C(T)=sum_t=1^|T|N_tH_t(T) =- sum_t=1^|T|sum_k=1^KN_tklogfracN_tkN_t$
此时有
$C_alpha(T)=C(T)+alpha|T|$
该式中,C(T)表示模型对训练数据的预测误差,即他们的拟合程度,|T|表示模型的复杂度,参数$alphageq0$控制两者之间的影响.$alpha$较大则促使较简单的模型,较小的$alpha$则促使复杂的模型.
因此,剪枝,就是在$alpha$确定时,选择损失函数最小的模型.
这里可以看出,决策树生成通过提高信息增益(比)来对训练数据更好拟合,而剪枝则优化损失函数来减小模型复杂度.
剪枝算法:
这个算法可以用动态规划来实现.
CART算法
CART是在给定输入随机变量X条件下,输出随机变量Y的条件概率分布的学习方法.CART假设决策树是二叉树,内部节点特征的取值,左为是或右为否.这样决策树就等价于递归地二分每个特征.它也包括了树的生成和剪枝.
CART生成
决策树的生成就是递归地构建二叉决策树,对回归树用平方误差最小化准则,对分类树用基尼指数最小化准则,进行特征选择,生成二叉树.
回归树的生成
设X,Y分别为输入输出变量,且Y为连续变量,给定训练数据集$D=(x_1,y_1),(x_2,y_2),cdots,(x_N,y_N)$,考虑如何生成回归树.
唉,这里实在是看不懂了,不太明白回归树和分类树的区别,感觉里面关系好混乱,网上也搜了不少来看,但都是关系很混乱,后面那道例题的思路倒还蛮清楚的.这里就暂时不往后写了.等进度到这时,那时再去问问学长或老师,然后在来补.
《统计学习方法（李航）》讲义第05章决策树
决策树(decisiontree)是一种基本的分类与回归方法。本章主要讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是... 查看详情
统计学习方法 李航 决策树
决策树一.决策树基本描述决策树是一种基本的分类与回归方法,呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程.学习时,利用训练数据根据损失函数最小化的原则建立决策树模型.预测时,对新的数据,利用决策树模型... 查看详情
决策树（统计学习方法（李航））的贷款的例子的实现(代码片段)
以统计学习方法（李航）这本书的例子为基础需要注意的地方：我用的是pycharmpython版本是3.7graphviz是一个软件，在pycharm里面下了还得去官网下下完之后得加入环境变量可能还需要重启电脑缺啥库就安啥库那个数据是我自己设置... 查看详情
李航统计学习方法(第二版)：决策树cart算法
1简介1.1介绍 1.2生成步骤CART树算法由以下两步组成:(1)决策树生成:基于训练数据集生成决策树，生成的决策树要尽量大;(2)决策树剪枝:用验证数据集对己生成的树进行剪枝并选择最优子树，这时用损失函数址小作为剪... 查看详情
李航统计学习方法(第二版)：决策树简介
1简介决策树模型是树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习... 查看详情
决策树理解
...似最优的一颗决策树，它无法保证是最优的。李航《统计学习方法》中这句话，应该是ID3提出时使用的理论依据，可以参考J.R.QUINLAN的"InductionofDecisionTrees"，我简略看了下，我个人感觉，应该是他引用的更早的文献，使用最 查看详情
统计学习五：1.决策树基本概念(代码片段)
全文引用自《统计学习方法》（李航）决策树(decisiontree)是一种常用的分类与回归方法。决策树的模型为树形结构，在针对分类问题时，实际上就是针对输入数据的各个特征对实例进行分类的过程，即通过树形结构的模型，在每... 查看详情
决策树模型本质连续值
摘自《统计学习方法》李航 第五章决策树学习通常包括3个步骤：特征选择、决策树的生成、决策树的剪枝 决策树学习本质上是从训练集中归纳出一组分类规则。决策树学习的损失函数通常是正则化的极大似然函数。决... 查看详情
机器学习决策树理论第二卷
决策树内容来至于《统计学习与方法》李航,《机器学习》周志华,以及《机器学习实战》PeterHarringTon,相互学习,不足之处请大家多多指教！本卷的大纲为1CART算法1.1CART回归树1.2CART分类树2CART剪枝3总结1CART算法CART分类与回归树(classi... 查看详情
手把手生成决策树(dicisiontree)
...,李鹏,曲亚东,王斌译.北京:人民邮电出版社,2013.李航.统计学习方法[M].北京:清华大学出版社,2012原文链接:http://blog.csdn.net/xuelabizp/article/details/509794691.什么是决策树决策树是一种主要的分类和回归方法。本文 查看详情
统计学习方法（李航）
统计学习方法概论：（一），统计学习1，统计学习的特点 2，统计学习的对象 3，统计学习的目的 4，统计学习的方法 （二），监督学习重要概念1，输入空间，特征向量空间，输出空间 （三），统计学习... 查看详情
决策树-李航(代码片段)
1、所谓决策树模型，是通过重要性依次向下绘出的，越重要的越在上面。决策树有节点和有向边组成。结点有两种类型，内部节点和叶结点，内部节点表示一个属性，叶子节点表示一个类。决策树的数学意义在于，条件概率分... 查看详情
李航统计学习方法--8.提升方法(详细推导)
目录8.1提升方法AdaBoost算法8.1.1提升方法的基本思路8.1.2AdaBoost算法8.2AdaBoost算法的训练误差分析8.3AdaBoost算法的解释8.3.1前向分步算法8.3.2前向分步算法与AdaBoost8.4... 查看详情
每月学习数理统计--《统计学习方法—李航》
现在这本书已经看完70%，在看完后我将会将每一章的内容按照自己的理解并结合其他书籍包括<<统计机器学习导论>>[1] ，<<机器学习>>[2]，<<大数据分析>>[3]这三本书总结经典的几大算法... 查看详情
李航统计学习方法(第二版)基本概念：统计学习方法三要素
1.简介统计学习方法都是由模型、策略和算法构成的2.模型在监督学习过程中，模型就是所要学习的条件概率分布或决策函数。模型的假设空间包含所有可能的条件概率分布或决策函数。2.1决策函数模型 2.2 ... 查看详情
《统计学习方法》--决策树
《统计学习方法》第五章–决策树决策树概述决策树模型呈树形结构，在分类过程中表示基于特征对实例进行分类的过程。决策树模型可以视为if-then规则的集合，也可以视为是定义在特征空间与类别空间上的条件改了分... 查看详情
统计学习方法五决策树分类
决策树分类1，概念 2，决策树算法2.1，特征选择： 熵：值越大，不确定性因素越大；条件熵：条件对结果的影响不确定性；信息增益；信息增益比 2.2... 查看详情
决策树1--id3_c4.5算法
...p; 1。本篇为个人对《2012.李航.统计学习方法.pdf》的学习总结，不得用作商用。欢迎转载，但请注明出处（即：本帖地址）。 2，因为本人在学习初始时有非常多数学知识... 查看详情