决策树

决策树是一种基本的分类与回归方法。
学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。
决策树学习通常包括3个步骤：特征选择、决策树的生成、决策树的修剪。
相关算法实现有 ID3，C4.5，CART。

一、模型

用决策树分类，从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子节点；这时，每一个子结点对应着改特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶节点。最后将实例分到叶节点的类中。

决策树学习的损失函数通常是正则化的极大似然函数。

二、特征选择

如果一个特征具有更好的分类能力，使得各个子集在当前条件下有最好的分类，那么就应该选择这个特征。信息增益 就能够很好地表示这一直观的准则。

信息增益

理解信息增益，需要先理解熵与 条件熵 的定义。

熵（entropy）是表示变量不确定性的度量。

设 X 是一个取有限个值的离散随机变量，其概率分布为
$P(X=x_i)=p_i，i=1,2,...,n$
则随机变量 X 的熵定义为
$H(X)=-\sum_{i=1}^np_ilogp_i$
上式中以 2 为底或以 e 为底，这时熵的单位分别称作比特或纳特。

熵越大，随机变量的不确定性就越大。

设有随机变量（X,Y），其联合概率分布为
$P(X=x_i,Y=y_j)=p_{ij}, i=1,2,...,n; j=1,2,...,m$
条件熵 H(Y|X) 表示在已知随机变量 X 的条件下随机变量 Y 的不确定性。 $H(Y|X)=\sum^n_{i=1}p_iH(Y|X=x_i)$
这里， $p_i=P(X=x_i),i=1,2,...,n.$

信息增益 表示得知 特征X 的信息而使得类Y 的信息的不确定性减少的程度。

特征A 对训练数据集 D 的信息增益 g(D,A), 定义为集合D的经验熵 H(D) 与特征A给定条件下D的经验条件熵 H(D|A) 之差，即
$g(D,A)=H(D)-H(D|A)$

根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

信息增益的算法

设训练数据集为 $D$ ， $|D|$ 表示其样本容量。
设有 $K$ 个类 $C_k$ ， $|C_k|$ 表示为属于类 $C_k$ 的样本个数， $k=1,2,...,K$ 。
设特征 $A$ 有 $n$ 个不同的取值，根据特征 $A$ 的取值将 $D$ 分为 $n$ 个子集 $D_1,D_2,...,D_n$ ， $|D_i|$ 为 $D_i$ 的样本个数。
子集 $D_i$ 中属于 $C_k$ 的样本的集合为 $D_{ik}$ ， $|D_{ik}|$ 为 $D_{ik}$ 的样本个数。

(1) 计算数据集 $D$ 的经验熵 $H(D)$
$H(D)=-\sum^K_{k=1}\frac{|C_k|}{D}log_2\frac{|C_k|}{D}$

(2) 计算特征 $A$ 对数据集 $D$ 的经验条件熵 $H(D|A)$
$H(D|A)=\sum^n_{i=1}\frac{D_i}{D}H(D_i)=-\sum^n_{i=1}\frac{D_i}{D}\sum^K_{k=1}\frac{D_{ik}}{D_i}log_2\frac{|D_{ik}|}{|D_i|}$
其中 $H(D_i)$ 为
$H(D_i)=-\sum^K_{k=1}\frac{D_{ik}}{D_i}log_2\frac{|D_{ik}|}{|D_i|}$

(3) 计算信息增益
$g(D,A)=H(D)-H(D|A)$

信息增益比

特征 A 对训练数据集 D 的信息增益比 $g_R(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练数据集 D 的经验熵 H(D) 之比：
$g_R(D,A)=\frac{g(D,A)}{H(D)}$

三、决策树的生成

ID3 算法

ID3 算法的核心思想就是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。

ID3 算法只有树的生成，容易产生过拟合。

C4.5 算法

C4.5 算法对 ID3 算法做了改进，C4.5 在生成过程中，用信息增益比来选择特征。

四、决策树的剪枝

剪枝是决策树算法对付过拟合的主要方法。基本策略有 预剪枝 和 后剪枝。

预剪枝

预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
预剪枝降低了过拟合的风险，显著减少了决策树的训练时间开销和测试时间开销，但可能带来欠拟合的风险。

后剪枝

后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树.但其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

剪枝往往通过极小化决策树整体的损失函数来实现。

设树 $T$ 的叶结点个数为 $|T|$ ， $t$ 是树 $T$ 的叶节点，该结点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_tk$ 个， $k=1,2,...,K$ ， $H_t(T)$ 为叶结点 $t$ 上的经验熵， $a \ge 0$ 为参数，则决策树学习的损失函数可以定义为
$C_a(T)=\sum^{|T|}_{t=1}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|}_{t=1}\sum_{k=1}^KN_{tk}log\frac{N_{tk}}{N_t}$
这时有
$C_a(T)=C(T)+a|T|$

上式中， $C(T)$ 表示模型对训练数据的预测误差，即模型与训练数据的拟合程度， $|T|$ 表示模型复杂度。参数 $a \ge 0$ 控制两者之间的影响。较大的 $a$ 促使选择较简单的模型，较小的 $a$ 促使选择较复杂的模型。 $a=0$ 意味着只考虑模型与训练数据的拟合程度，不考虑模型复杂度。

树的剪枝算法

(1) 计算每个结点的经验熵。
(2) 递归的从树的叶结点向上回缩。
设一组叶结点回缩到其父结点之前与之后的整体树分别为 $T_B$ 与 $T_A$ ，其对应的损失函数值分别是 $C_a(T_B)$ 与 $C_a(T_A)$ ，如果
$C_a(T_A) \le C_a(T_B)$
则进行剪枝，即将父结点变为新的叶结点。
(3) 返回 (2) 。直至不能继续为止，得到损失函数最小的子树 $T_a$ 。

五、CART 算法

CART 算法由以下两步组成：
(1) 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。
(2) 决策树剪枝：用于验证数据集对已生成的数进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

分类树的生成

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。

基尼指数

分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$ ，则概率分布的基尼指数定义为
$Gini(p)=\sum^K_{k=1}p_k(1-p_k)=1-\sum^K_{k=1}p^2_k$

对于给定的样本集合 $D$ ，其基尼指数为
$Gini(D)=1-\sum^K_{k=1}(\frac{|C_k|}{D})^2$
这里， $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集， $K$ 是类的个数。

如果样本集合 D 根据特征 A 是否取某一可能值 a 被分割成 D_1 和 D_2 两部分，则在特征 A 的条件下，集合 D 的基尼指数定义为
$Gini(D,A)=\frac{|D_1|}{D}Gini(D_1)+\frac{|D_2|}{D}Gini(D_2)$

基尼指数 $Gini(D,A)$ 表示经 $A=a$ 分割后集合 $D$ 的不确定性。基尼指数值越大，样本集合的不确定性就越大。

CART 生成算法

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

CART 剪枝

(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) 自上而下地访问内部结点 $t$ ，如果有 $g(t)=a$ ，进行剪枝，并对叶结点 $t$ 以多数表决法决定其类，得到树 $T$ 。
(5) 设 $k=k+1，a_k=a，T_k=T$ 。
(6) 如果 $T$ 不是由根结点单独构成的树，则回到步骤(4)。
(7) 采用交叉验证法在子树序列 $T_0,T_1,...,T_n$ 中选取最优子树 $T_a$ 。

六、补充

连续值处理

对连续属性的划分，最简单的策略是采用二分法对连续属性进行处理。

(1) 将连续属性的 $n$ 个数值排序。
(2) 取两两数的平均值为划分点，共 $n-1$ 个。
(3) 分别求每个划分点下的经验熵 $H(D_t^{-})$ 和 $H(D_t^+)$ 。
(4) 求每个划分点的信息增益
$g(D,a,t) = H(D) - \sum_{\lambda\in (-,+)}\frac{|D^\lambda _t |}{|D|}H(D^\lambda _t )$
(5) 找出所有划分点的最大信息增益，和其对应的划分点。

与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。

缺失值处理

最后编辑于：2019.02.21 15:56:34

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

决策树