西瓜书第四章决策树

这一章主要介绍了决策树是什么，如何构建决策树；前三节针对离散值来对决策树的构建进行说明，而第四小节针对连续值如何处理构建决策树进行说明。

4.1基本流程

决策树：基于树状结构，根据样本的属性来对样本进行判断、决策。如：给一个西瓜的各种属性，色泽=“青绿”、根蒂=“缩卷”、声音=“浊响”，通过这些属性来判断这一个西瓜是否为好瓜。
决策树的叶结点对应决策结果，而其他结点则对应一个属性的测试，根结点则是包括全部样本。

决策树学习基本方法.png

上面便是决策树的学习算法。看起来有点复杂。我简单的说明一下。
首先是要找到让分类最优的属性，以这个属性为节点，接着在这个属性下找下一个最优属性（如何选择在下一节有介绍）作为下一个节点，从而不断形成树状，而遇到以下三种情况则将该节点作为叶节点不在往下划分。
【说明】(1)就是图中的递归情形①，当前的节点包含的样本全属性属于同一类别，无需再划分了。
(2)递归情形二，当前属性集为空集了或者所有样本在所有属性上取值都相同，没办法划分了。
(3)递归情形三，当前的节点所含样本为空，没办法划分了。

4.2划分选择

怎样来选择最优属性呢？按属性来划分目的就是让决策树的每一分结点的样本尽可能是同一类，即结点的“纯度”越来越高。
判断纯度的高低有三种常用的指标，也是三种决策树算法常使用的。

①信息增益

我们先来看一个新定义，信息熵用来度量样本集合纯度的常用指标。假定当前样本集合D中第K类样本所占比例为 $p_k(K=1,2...|\gamma|)$ ,则D的信息熵为： $Ent(D)=-\sum_{k=1}^{|\gamma|}p_k\log_2p_k$
【注】 $Ent(D)$ 信息熵越小，D的纯度越高

假定离散属性 $a$ 有V个可能取值 ${a^1,a^2,...,a^v}$ ，若用 $a$ 属性对样本集合D进行分类则有V个分支结点，第v个分支结点包含D中所有在属性 $a$ 取值为 $a^v$ 的样本，记为 $D^v$ ； $Ent(D^v)$ 表示 $D^v$ 的信息熵； $|D^v|/|D|$ 表示属性 $a$ 取值为 $a^v$ 的样本占总样本的比重。
定义都清楚后，我们就来看看什么是信息增益了。信息增益： $Gain(D,a)=Ent(D)-\sum_{v=1}^V{\frac{|D^v|}{|D|}Ent(D^v)}$ ，简单点说就是D的信息熵减去按 $a$ 属性分类后各子集的信息熵的加权平均。
**【注】信息增益越大，说明按这个属性分类后对纯度的提高越大；信息增益是ID3决策树学习算法的常用指标。

②增益率

增益率是C4.5决策树算法的常用指标，它是信息增益的改进。
定义： $Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)},其中IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}$ ,被称为属性a的“固有值”。
先将各个属性的信息增益算出来。得到其平均值，将高于平均值的那些属性选出，再选择其中增益率最高的属性。

③基尼指数

基尼指数：反映从数据集D中随机抽取两个样本，其类别标记不一致的概率，也可以理解为1-随机抽取两个样本类别一致的概率。
公式： $Gini(D)=\sum_{k=1}^{|\gamma|}\sum_{k'≠k}p_kp_{k'}=1-\sum_{k=1}^{|\gamma|}p_k^2$
当我们要计算一个属性a的基尼指数时： $Gini\_index(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$
【注】基尼指数最小的属性为最优划分属性

4.3剪枝处理

剪枝处理是决策树学习算法应付“过拟合”的主要手段，基本策略有“预剪枝”和“后剪枝”。
预剪枝：在生成决策树过程中，对每个结点在划分前先估计，若划分后可以提高决策树的泛化能力则划分，否则就以当前结点为叶结点。
后剪枝：先从训练集生成完整的决策树，再自底向上进行判断，将当前结点替换为叶结点能否提高泛化能力，若可以则替换。
要如何判断泛化性能是否提高，这用到前面第二章提到的性能评估，以留出法为例，预剪枝在生成结点前判断生成前后的精度，精度大则泛化能力强，来看是否生成；后剪枝则生成决策树后判断替代前后的精度，看是否替换（书本的例子简单易懂，我这里就不过多简述）。

4.4连续值与缺失值

前面三节的决策树生成都以离散值为例，这里讲一下连续值如何生成决策树。
额外提一下：第三章的线性回归则需要将离散值化通过序连续化或向量化转化为连续值。第四章决策树则需要将连续值离散化。

连续值

二分法：假定连续属性 $a$ 在样本集D上有n个不同的取值，将这些值从小到大排序，记为 $\{a^1,a^2,...,a^n{\}}$ ,我们可以取一个划分点t将D分为子集 $D_t^-和D_t^+$ ，其中 $D_t^-$ 包含那些在属性a上取值小于t的样本，而 $D_t^+$ 则是取值大于t的样本集合。将集合D一分为二，故称为二分法。
【注】t一般选择两个相邻属性值的中心点， $t=\{\frac{a^i+a^{i+1}}{2}|i≤i≤n-1|\}$
在使用二分法后，对于划分的点，我们需要判断这样划分是否最优，所以就需要用到前面提到的信息增益，连续值的信息增益： $Gain(D,a)=\max_{t∈T_a}Gain(D,a,t)=\max_{t∈T_a}Ent(a)-\sum_{\lambda∈\{-,+\}}{\frac{|D_t^\lambda|}{|D|}}Ent(D_t^\lambda)$ .
【注】信息增益越大，则其划分越优；且连续值属性作为当前结点的划分属性后，该属性还能作为后代结点的划分属性，这是与离散值属性不同的地方。

缺失值处理

面对样本部分属性缺失的情况下，丢弃这些样本会造成信息浪费，且样本数本来有限丢失后有可能使学习器欠拟合。
面对缺失部分属性值的样本集，我们需要解决两个问题：①如何确定划分属性②给定划分属性后，那些缺失属性值的样本怎么划分。
首先，确定划分属性，我们从没有属性值缺失的样本入手来判断属性a的优劣；划分则将给样本赋予一个权重，有确定属性值的样本权重为一，缺失属性值的样本按权重划分。
给定训练集D和属性 $a$ ,令 $\tilde{D}$ 表示D中在属性 $a$ 上没有缺失值的样本子集，假定 $a$ 有V个取值 $\{a^1,a^2,....,a^v\}$ ,令 $\tilde{D^v}$ 表示 $\tilde{D}$ 中在属性 $a$ 上取值为 $a^v$ 的样本子集， $\tilde{D_k}$ 表示 $\tilde{D}$ 中属于第k类 $(k=1,2...,|\gamma|)$ 的样本子集，给每个样本 $x$ 赋予一个权重 $w_x$ ，并定义：
$\rho={\frac{\sum_{x∈\tilde{D}}{w_x}}{\sum_{x∈{D}}{w_x}}},$ 对属性a,表示缺失值样本所占比例。
$\tilde{p}_k={\frac{\sum_{x∈\tilde{D}_k}{w_x}}{\sum_{x∈\tilde{D}}{w_x}}}(1≤k≤|\gamma|),$ 对属性a,表示无缺失值样本中第k类所占的比例。
$\tilde{r}_v=\frac{\sum_{x∈\tilde{D}^v}{w_x}}{\sum_{x∈\tilde{D}}{w_x}}(1≤k≤V).$ 对属性a,表示无缺失值样本中在属性a上取值 $a^v$ 的样本所占比例。
信息增益： $Gain(D,a)=\rho\times{Gain(\tilde{D},a)}=\rho\times(Ent(\tilde{D})-\sum_{v=1}^V\tilde{r}_vEnt(\tilde{D}^v))$ ,其中 $Ent(\tilde{D})=-\sum_{k=1}^{|\gamma|}{\tilde{p}_k\log_2\tilde{p}_k}$
通过上面的信息增益来判断出将哪个属性作为划分属性最优，这样划分属性就确定下来了，第二个问题就是将缺失属性值的样本按权重分入各个分支中。举个例子更容易懂：如以属性a为划分属性，a有三个取值1,2,3先将有确定属性值的样本放入分支，假设共有10个样本其a属性有确定属性值，属性值为1有5个，属性值为2有3个，属性值为3有2个，那么这时候某个没有确定属性值的样本则在各分支点权重为 $\frac{5}{10},\frac{3}{10},\frac{2}{10}$ 。

4.5多变量决策树

将每个属性视为坐标空间的一个坐标轴，那么d个属性的样本对于d维空间的一个点。
决策树形成的分类边界有一个明显特点：轴平行，即它的分类边界若干个与坐标轴平行的分段组成。

决策树对应边界.png

如上图，此时的决策树相当复杂，需要对大量属性进行测试，时间开销很大；而多变量决策树的边界可以以斜线划分将大为简化决策树模型。
多变量决策树不再以单一属性作为划分而是以适合的线性分类器（参考第三章）作为划分。

最后编辑于：2020.02.06 00:24:54

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,547评论 6赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,399评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,428评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,599评论 1赞 274
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,612评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,577评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,941评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,603评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,852评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,605评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,693评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,375评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,955评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,936评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,172评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 43,970评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,414评论 2赞 342

西瓜书 第四章 决策树