决策树

0. Motivation

Can you draw single division line for these classes?

We need two lines one for threshold of x and threshold for y .

Decision Tree Classifier, repetitively divides the working area(plot) into sub part by identifying lines.

1. 基本流程

递归返回：

（1）当前结点包含的样本全属于同一类别，无需划分

（2）当前属性集为空，或是所有样本在所有属性上的取值相同，无法划分。把当前结点标记为叶结点，类别为该节点所含样本最多的类别。

（3）当前结点包含的样本集合为空，不能划分。把当前结点标记为叶结点，类别设定为其父结点所含样本最多的类别。

2. 划分选择

2.1 信息增益

假定当前样本集合D中第k类样本所占的比例为 $p_k(k=1,2,...,|y|)$

信息熵：度量样本集合纯度

$Ent(D)=-\sum_{k=1}^{|y|}p_k\log_2 p_k$

信息熵越小，样本集合的纯度越高

假定离散属性a有V个可能的取值 $\{a^1,a^2,...,a^V\}$ ， $D^v$ ：D中所有在属性a上取值为 $a^v$ 的样本

$\frac{|D^v|}{|D|}$ ：根据不同分支结点所包含的样本数，给分支结点赋予权重，样本数越多的分支结点影响越大

信息增益： $Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|} Ent(D^v)$

信息增益越大，意味着使用属性a来进行划分所获得的“纯度”提升越大

ID3以信息增益为准则选择划分属性，即在图4.2第八行选择属性 $a_*=\arg \max_{a\in A}Gain(D,a)$

判别是否是好瓜： $|y|=2$ ，正例 $p_1=\frac{8}{17}$ ,反例 $p_1=\frac{9}{17}$

（1）计算根结点信息熵： $Ent(D)=-\sum_{k=1}^{2}p_k\log_2 p_k =0.998$

（2）计算当前属性集合{色泽，根蒂，敲声，纹理，脐部，触感}中每个属性的信息增益。

“色泽”={青绿，乌黑，浅白}

$D^1$ (色泽=青绿)={1，4，6，10，13，17}，正例 $p_1=\frac{3}{6}$ ，反例 $p_2=\frac{3}{6}$ ， $Ent(D^1)=1.000$

$D^2$ (色泽=乌黑)={2，3，7，8，9，15}，正例 $p_1=\frac{4}{6}$ ，反例 $p_2=\frac{2}{6}$ ， $Ent(D^2)=0.918$

$D^3$ (色泽=浅白)={5，11，12，14，16}，正例 $p_1=\frac{1}{5}$ ，反例 $p_2=\frac{4}{5}$ ， $Ent(D^3)=0.722$

$Gain(D,色泽)=Ent(D)-\sum_{v=1}^{3}\frac{|D^v|}{|D|}Ent(D^v)=0.109$

同理

$Gain(D,根蒂)=0.143，Gain(D,敲声)=0.141，Gain(D,纹理)=0.381$

$Gain(D,脐部)=0.289，Gain(D,触感)=0.006$

选择“纹理”作为划分属性：

基于“纹理”属性对根节点进行划分

针对“纹理=清晰”的分支结点，基于 $D^1$ 计算出各属性的信息增益：

$Gain(D^1,根蒂)=0.458，Gain(D^1,敲声)=0.331$

$Gain(D,色泽)=0.043，Gain(D,脐部)=0.458，Gain(D,触感)=0.458$

不断对每个分支结点进行上述操作，最终得到

信息增益准则对可取值数目较多的属性有所偏好。

C4.5使用“增益率”来选择最优划分属性。

2.2 增益率

增益率： $Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$

属性a的固有值： $IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}\log_2 \frac{|D^v|}{|D|}$

属性a的可取值数目越多（V越大），则IV(a）通常会越大

增益率准则对可取值数目较少的属性有所偏好。

因此，C4.5算法没有直接选择增益率最大的候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

2.3 基尼指数

CART决策树是用“基尼指数”来选择划分属性。

基尼值： $Gini(D)=\sum_{k=1}^{|y|}\sum_{k^{\prime}\neq k}p_kp_{k^{\prime}}=1-\sum_{k=1}^{|y|}p^2_k$ ，反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。

Gini值越小，数据集D的纯度越高。

属性a的基尼指数： $Gini\_index(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$

在侯选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即 $a_*=\arg \min_{a\in A}Gini_index(D,a)$

3. 剪枝处理

预剪枝：在决策树的生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶节点。

后剪枝：先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该结点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。

划分训练集和验证集

采用信息增益准则生成决策树

3.1 预剪枝

（1）若根结点“脐部”不进行划分，被标记为叶结点，其类别标记为训练样例数最多的类别，假设标记为“好瓜”。用验证集进行评估，编号{4,5,8}被正确分类，{9,11,12,13}被错误分类，精度为42.9%。用属性“脐部”划分后，{4,5,8,11,12}被正确分类，验证集精度为71.4%。因此，用“脐部”划分得以确定。

（2）对②进行划分，基于信息增益准则挑选出”色泽“，{5}会被错分，划分后验证集精度下降，于是将禁止结点②被划分。

（3）对③，最优划分属性为”根蒂“，划分前后精度一样，禁止划分。

（4）对④，其所含训练样例已属于同一类，不再进行划分。

优点：降低过拟合风险，显著减少了训练和测试的时间开销

缺点：基于”贪心“，有欠拟合风险。有些分支当前划分虽然不能提升泛化性能，但在其基础上进行后续划分却有可能导致性能显著提高。

3.2 后剪枝

先从训练集生成一颗完整的决策树。图4.5中决策树的验证集精度为42.9%。

（1) 首先考虑结点⑥，剪枝后的叶结点包含编号{7,15}的训练样本，于是，该叶结点的类别标记为”好瓜“，此时验证集精度提高至57.1%。因此决定剪枝。

（2）考察结点⑤，替换后的叶结点包含{6,7,15}，标记为”好瓜“，验证集精度仍为57.1%，可以不进行剪枝。

（3）对结点②，替换后的叶结点包括{1,2,3,14}，标记为”好瓜”，此时验证集精度提高至71.4%，于是，决定剪枝。

（4）对结点③和①，替换后精度均未得到提高，于是得以保留。

后剪枝决策树通常比预剪枝决策树保留更多的分支。一般情况下，后剪枝决策树欠拟合风险很小，但其训练时间开销较大。

4. 连续与缺失值

4.1 连续值处理

二分法：给定样本集D和连续属性a，假定a在D上出现了n个不同的取值，捡这些值从小到大进行排序，记为 $\{a^1,a^2,...,a^n \}$ 基于划分点t可将D分为子集 $D^-_t$ 和 $D^+_t$ ，其中 $D^-_t$ 包含那些在属性a上取值不大于t的样本，而 $D^+_t$ 则包含那些在属性a上大于t的样本。

$Gain(D,a)=\max_{t \in T_a}Ent(D)-\sum_{\lambda \in \{-,+\}}\frac{|D^v|}{|D|} Ent(D^\lambda)$

与离散属性不同，若当前结点划分属性为连续属性，则该属性还可作为其后代结点的划分属性。例如在父结点上使用了“密度<=0.381”，不会禁止在子结点上使用“密度<=0.294”.

4.2 缺失值处理

问题：（1）如何在属性值缺失的情况下进行划分属性选择？

给定训练集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类的样本子集，显然有 $\tilde{D}= \bigcup_{k=1}^{{y}} \tilde{D}_k$ , $\tilde{D}= \bigcup_{v=1}^{{V}} \tilde{D}^v$ 。

假定我们为每个样本x赋予一个权重 $w_x$ ,并定义

$\rho =\frac{\sum_{\tilde{D}} w_x}{\sum_{D} w_x}$ ，表示无缺失值样本所占的比例

$\tilde{p_k} =\frac{\sum_{\tilde{D_k}} w_x}{\sum_{\tilde{D}} w_x}$ ，表示无缺失值样本中第k类所占的比例， $\sum_{k=1}^{|y|} \tilde{p_k}=1$

$\tilde{r_v} =\frac{\sum_{\tilde{D^v}} w_x}{\sum_{\tilde{D}} w_x}$ ，表示无缺失值样本中在属性a上取值为 $a^v$ 的样本所占的比例， $\sum_{v=1}^{V} \tilde{r_v}=1$

$Gain(D,a)=\rho \times Gain(\tilde{D},a)=\rho \times \Bigg(Ent(\tilde{D})-\sum_{v=1}^{V}{\tilde{r_v}} Ent(\tilde{D^v})\Bigg)$

以表4.4的数据为例生成一颗决策树：

学习开始时，根节点包含样本集D中全部17个样例，各样例的权值为1.

属性“色泽”上无缺失值的样例子集 $\tilde{D}=\{2,3,4,6,7,8,9,10,11,12,14,15,16,17\}$ ，共14个样例。

信息熵 $Ent(\tilde{D})=-\sum_{k=1}^{2} \tilde{p_k}\log_2 \tilde{p_k}=-(\frac{6}{14}\log_2 {\frac{6}{14}} +\frac{8}{14}\log_2 {\frac{8}{14}} )=0.985$

令 $\tilde{D}^1,\tilde{D}^2,\tilde{D}^3$ 分别表示在属性“色泽”上取值为“”青绿，“乌黑”，“浅白”的样本子集。

$Ent(\tilde{D}^1)=-(\frac{2}{4}\log_2 {\frac{2}{4}} +\frac{2}{4}\log_2 {\frac{2}{4}} )=1.000$

$Ent(\tilde{D}^2)=-(\frac{4}{6}\log_2 {\frac{4}{6}} +\frac{2}{6}\log_2 {\frac{2}{6}} )=0.918$

$Ent(\tilde{D}^3)=-(\frac{0}{4}\log_2 {\frac{0}{4}} +\frac{4}{4}\log_2 {\frac{4}{4}} )=0.000$

样本子集 $\tilde{D}$ 上属性“色泽”的信息增益为

$Gain(\tilde{D},a)=Ent(\tilde{D})-\sum_{v=1}^{3}{\tilde{r_v}} Ent(\tilde{D^v})$

$=0.985-(\frac{4}{14} \times 1.000+\frac{6}{14}\times 0.918+\frac{4}{14}\times 0.918)=0.306$

于是，样本集D上属性“色泽”的信息增益为

$Gain(D,色泽)=\rho \times Gain(\tilde{D},色泽)=\frac{14}{17} \times 0.306=0.252$

类似地可计算出所有属性在D上的信息增益

$Gain(D,根蒂)=0.171，Gain(D,敲声)=0.145，Gain(D,纹理)=0.424$

$Gain(D,脐部)=0.289，Gain(D,触感)=0.006$

“纹理”取得最大的信息增益，被用于对根节点进行划分。

问题：（2）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

若样本x在划分属性a上的取值已知，则将x划入与其取值对应的子结点，且样本权值在子结点中保持为 $w_x$ .

若样本x在划分属性a上的取值未知，则将x划入与所有的子结点，且样本权值与属性值 $a^v$ 对应的子结点中调整为 $\tilde{r_v}\cdot w_x$ 。

就是让同一个样本以不同的概率划入到不同的子结点中去。

{1,2,3,4,5,6,15}进入“纹理=清晰”分支，{7,9,13,14,15}进入“纹理=稍糊”分支，{11,12,16}进入“纹理=模糊”分支，且样本在各子结点中权重保持1.

{8}在“纹理”上属性缺失，将同时进入三个分支中，但权重在三个子结点中分别调整为 $\frac{7}{15} 、\frac{5}{15} 、\frac{3}{15}$ 。{10}类似。

5 多变量决策树

决策树分类边界的特点：轴平行，这是的学习结果有较好的可解释性，每一段划分都直接对应某个属性取值。

但在真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似。

多变量决策树：斜划分，非叶结点对属性的线性组合进行测试，不再针对某个属性。

最后编辑于：2019.03.04 10:31:18

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

决策树