《统计学习方法》极简笔记P5：决策树公式推导

决策树学习

通过训练数据集 $T=\{(x_1,y_1),(x_2,y_2),(x_N,y_N)...,(x_1,y_1)\}$
$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T$ 为输入实例
$y_i\in\{1,2,...,K\}$ 为类标记
学习目标：对实例进行正确分类

特征选择

熵
$H(X)=-\sum_{i=1}^{n}p_ilogp_i$
条件熵
$H(Y|X)=-\sum_{i=1}^{n}p_iH(Y|X=x_i)$
信息增益的算法
输入：特征A，训练集D
输出：特征A对训练集D的信息增益 $g(D,A)$
(1)计算训练集D的经验熵
$H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$
(2)计算特征A对训练集D的经验条件熵
$H(D,A)=\sum_{k=1}^{K}\frac{|D_i|}{|D|}H(D_i)=-\sum_{k=1}^{K}\frac{|D_i|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|}$
(3)计算信息增益
$g(D,A)=H(D)-H(D|A)$
信息增益比的算法
$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$
其中 $H(D)=-\sum_{k=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$

决策树剪枝

树T的叶结点个数为|T|，t是树T的叶结点，该叶结点有 $N_t$ 个样本点，其中k类的样本点有 $N_{tk}$ 个， $H_t(T)$ 为叶结点t上的经验熵，则决策树学习的损失函数
$C_a(T)=\sum_{t=1}^{|T|}N_tH_t(T)+a|T|$
其中 $H_t(T)=-\sum_{k}\frac{|N_{tk}|}{|N_t|}log\frac{|N_{tk}|}{|N_t|}$
则 $C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_t}$
则 $C_a=C(T)+a|T|$
树的剪枝算法
输入：生成的决策树T，参数α
输出：修剪后的子树 $T_\alpha$
(1)计算每个结点经验熵
(2)递归地从树的叶结点向上回溯，若：
$C_\alpha(T_A)\leq{C_\alpha}(T_B )$ 则剪枝，其中 $T_A$ 为剪枝后, $T_B$ 为剪枝前
(3)返回(2)，直至得到损失函数最小的子树 $T_\alpha$

CART算法--回归树

对输入空间划分为M个单元 $R_1,R_2,...,R_M$ ,每个划分上有固定输出 $C_m$ ,则回归树模型表示为
$f(x)=\sum_{m=1}^{M}c_m{I}(x\in{R_m})$
预测误差： $\sum_{x\in{R_m}}(y_i-f(x_i))^2$
划分单元 $R_m$ 上的 $c_m$ 最优值 $\hat{c}_m=avg(y_i|x_i\in{R_m})$
输入空间的划分采用启发式方法
选择第j个变量 $x^{(j)}$ 和它的取值s作为切分变量和切分点，定义两个区域：
$R_1(j,s)=\{x|x^{(j)}\leq{s}\}$ , $R_2(j,s)=\{x|x^{(j)}>{s}\}$
然后寻找最优切分变量j和最优切分点s，求解：
$\mathop{min}\limits_{j,s}[\mathop{min}\limits_{c_1}\sum_{x_i\in{R_1(j,s)}}(y_i-c_1)^2+\mathop{min}\limits_{c_2}\sum_{x_i\in{R_2(j,s)}}(y_i-c_2)^2]$
对固定输入变量j，找到最优切分点s
$\hat{c}_1=avg(y_i|x_i\in{R_1(j,s)})$
$\hat{c}_2=avg(y_i|x_i\in{R_2(j,s)})$
最小二乘回归树生成算法
输入：训练集D
输出：回归树f(x)
(1)选择最优切分变量j和切分点s，求解
$\mathop{min}\limits_{j,s}[\mathop{min}\limits_{c_1}\sum_{x_i\in{R_1(j,s)}}(y_i-c_1)^2+\mathop{min}\limits_{c_2}\sum_{x_i\in{R_2(j,s)}}(y_i-c_2)^2]$
遍历j，对固定j扫描切分点s，找出使上式达到最小的(j,s)组合
(2)选择(j,s)划分区域并决定相应输出值：
$R_1(j,s)=\{x|x^{(j)}\leq{s}\}$ , $R_2(j,s)=\{x|x^{(j)}>{s}\}$

$\hat{c_m}=\frac{1}{N_m}\sum_{x_i\in{R_1(j,s)}}y_i,x\in{R_m},m=1,2$
(3)对两个子区域循环(1),(2),直至满足停止条件
(4)将输入空间划分为M个单元 $R_1,R_2,...,R_M$ ,生成决策树：
$f(x)=\sum_{m=1}^{M}\hat{c}_m{I}(x\in{R_m})$

CART算法--分类树

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点
基尼指数
K个类，属于第k类的概率 $p_k$ ,则
$Gini(p)=\sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^{K}p_k^2$
样本集D的基尼指数
$Gini(D)=1-\sum_{k=1}^{K}({\frac{|C_k|}{|D|})}^2$
样本D根据特征A是否取值a被划分为 $D_1$ , $D_2$
$D_1=\{(x,y)\in{D}|A(x)=a\},D_2=1-D_1$

$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$
CART生产算法
输入:训练数据集D，停止计算的条件;
输出:CART决策树.
(1)训练数据集D，计算现有特征对该数据集的基尼指数.此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或“否”将D分割成D1和D2两部分，根据 $Gini(D,A)$ 计算A=a时的基尼指数;
(2)在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点.依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去；
(3)对两个子结点递归地调用(1)(2)，直至满足停止条件.
(4)生成CART决策树.

CART剪枝算法

输入:CART算法生成的决策树 $T_0$ ;
输出:最优决策树 $T_\alpha$ .
(1)设 $k=0,T=T_0$ .
(2)设 $a=+\infty$
(3)自下而上地对各内部结点t计算 $C(T_t) ,|T_t|$ 以及
$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$ , $a=min(a,g(t))$
这里 $T_t$ 表示以t为根结点的子树., $C(T_t)$ 是对训练数据的预测误差， $|T_t|$ 引是 $T_t$ 的叶结点个数；
(4)对 $g(t)=a$ 的内部结点t进行剪枝，并对叶结点t以多数表决法决定其类，得到树T；
(5)设 $k=k+1,a_k=a,T_k=T$ ；
(6)如果T不是由根结点单独构成的树。则回到步骤(4)；
(7)采用交叉验证法在子树序列 $T_0,T_1,...,T_n$ 中选取最优子树 $T_a$

最后编辑于：2019.08.19 13:44:51

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