决策数及随机森林

本来以为决策树很简单，所以初次写这篇帖子的时候也没仔细深究，后来学到xgboost的时候有些环节怎么想不明白，后来才知道原来核心原因还是CART的原理没有搞清楚，于是回来老老实实重写这片帖子，尤其是CART部分！

帖子目录：
1、CART原理
2、信息熵及其他决策树简介
2、随机森林

一、CART原理
CART全称为Classification and Regression Trees，即分类和回归树，既能处理回归问题也能处理分类问题，CART应该是应用最广泛的决策树了，其他高级算法（例如随机森林，Adaboost和xgboost等）的基分类器也是用的CART，所以务必要仔细弄清楚CART的原理，
本节数据集：

image.png

1、基尼指数
对于给定的样本D，其基尼指数为：

Gini(D)=1-\sum_{k=1}^{K}\frac{|C_{k}|^{2}}{|D|}

其中，Ck是D中属于第k类的样本子集，K是类的个数。|Ck|和D分别表示子集的个数和样本的个数。

如果样本集合D根据特征A是否取某一可能的值分割成 $D_{1},D_{2}$
在特征A的条件下集合D的基尼指数为
$Gini(D,A)=\frac{|D_{1}|}{|D|}Gini(D_{1})+\frac{|D_{2}|}{|D|}Gini(D_{2})$

2、分类树
当CART是分类树的时候，采用GINI值作为分裂节点的依据

举例：利用看电视时长，职业和年龄预测是否已婚
因为CART属于二分叉树，所以如果某个特征有三个以上属性，这需要两两划分，例如对于职业这个特征，有三种划分情况{“学生”}，{“老师”，“上班族”}以及{“老师”，“学生”}、{“上班族”}，最后一种为{“学生”，“上班族”}、{“老师”}
对于
1）对于第一种情况 $R_{1}$ ={“学生”}, $R_{2}$ ={“老师”，“上班族”}

image.png

$Gini(D,\text{职业_1})=(\frac{|D_{1}|}{|D|}Gini(D_{1})+\frac{|D_{2}|}{|D|}Gini(D_{2})$

职业_1_1={“学生”}，包含3个样本，1个是，2个否
$\frac{|D_{1}|}{|D|}=\frac{3}{7}$
$Gini(D_{1})=1-((\frac{1}{3})^{2}+(\frac{2}{3})^{2})=\frac{4}{9}$
职业_1_2={“老师”，“上班族”}，包含4个样本，3个是，1个否
$\frac{|D_{2}|}{|D|}=\frac{4}{7}$
$Gini(D_{2})=1-((\frac{1}{4})^{2}+(\frac{3}{4})^{2})=\frac{3}{8}$
最终：
$Gini(D,\text{职业_1})=\frac{3}{7}\cdot\frac{4}{9}+\frac{4}{7}\cdot\frac{3}{8}=\frac{17}{42}$

计算特征职业其他两种情况的基尼指数，选择最小的

对于年龄这个特征，因为年龄属于连续型变量按照数值的大小顺序排为12,18,21,26,29,36,47，可被分为6中情况，
对于第一种情况是{12}，{18,21,26,29,36,47}
$Gini(D,\text{年龄_1})=(\frac{|D_{1}|}{|D|}Gini(D_{1})+\frac{|D_{2}|}{|D|}Gini(D_{2})$
年龄_1_1={12}，包含1个样本，0个是，1个否
$\frac{|D_{1}|}{|D|}=\frac{1}{7}$
$Gini(D_{1})=1-1=0$

年龄_1_2={18,21,26,29,36,47},包含6个样本，包含4个是，2个否
$\frac{|D_{2}|}{|D|}=\frac{6}{7}$
$Gini(D_{2})=1-((\frac{4}{6})^{2}+(\frac{2}{6})^{2})=\frac{4}{9}$
最终：
$Gini(D,\text{年龄_1})=\frac{1}{7}\cdot0+\frac{6}{7}\cdot\frac{4}{9}=\frac{8}{21}$

计算年龄其他5种情况的基尼指数，选择最小的

所有的基尼指数计算出来之后，选择最小那个作为当前节点的分割依据，例如，如果最终职业的第一种情况的基尼指数最小，那么此时的决策树为
$f(x)=\left\{\begin{matrix} 0 & \text{{'学生'}}\\ 1& \text{{'上班族'，'老师'}} \end{matrix}\right.$
注：
a)其中0代表未婚，1代表已婚
b)当前叶子节点各样本类别值的众数即为预测值
c)xgboost会在此处计算gain和权值，可详见下篇帖子

3、回归树
当CART作为回归树的时候，使用样本的最小方差作为分裂节点的依据,追小方差公式为：

举例：根据看电视时间，是否已婚和职业队年龄进行预测
对于职业这个特征，有三种划分情况{“学生”}，{“老师”，“上班族”}以及{“老师”，“学生”}、{“上班族”}，最后一种为{“学生”，“上班族”}、{“老师”}
对于
1）对于第一种情况R_{1}={“学生”},R_{2}={“老师”，“上班族”}

image.png

职业_1_1={“学生”}，包含3个样本，年龄均值为：
$c1=(12+18+21)/3=17$
$c2=(26+47+36+29)/4=34.5$

$m=min\left [ \sum (y_{i}-c_{1})^{2}+min\sum(y_{i}-c_{1})^{2} \right ]$
$y_{i}\in (\text(23))=\left ( {12,18,21} ,{26,47,36,29}\right )$
最小平方误差计算得：
$m=42+261=303$

计算领完两种情况m2=742.6,m3=238.8,m3的值最小，因此此时的决策树为：
$f(x)=\left\{\begin{matrix} 41.5 & \text{{'上班族'}}\\ 21.2& \text{{'学生'，'老师'}} \end{matrix}\right.$

注：
a)当前叶子节点各样本y真实值的均值即为预测值

4、sklearn代码
max_depth树的最大深度，min_samples_split 样本数>10,继续分支

image.png

二、信息熵及其他决策树简介
数据集

image.png

0、信息熵
信息熵是最基础的东西
$Ent(D)=-\sum_{k=1}^{|y|}p_{k}log_{2}p_{k}$
举例：
1)对于西瓜数据集根节点（好瓜） |y|=2，p(好瓜=是)=8/19，p(好瓜=否)=7/19
$Ent(D)=-(\frac{8}{19}log_{2}\frac{8}{19}+\frac{7}{19}log_{2}\frac{7}{19})=0.998$

2)对于变量色泽|y|=3(青绿，乌黑，浅白)
$Ent(D^{1})=(\frac{3}{6}log_{2}\frac{3}{6}+\frac{3}{6}log_{2}\frac{3}{6})=1.00$
$Ent(D^{1})=(\frac{4}{6}log_{2}\frac{4}{6}+\frac{2}{6}log_{2}\frac{2}{6})=0.918$
$Ent(D^{1})=(\frac{1}{5}log_{2}\frac{1}{5}+\frac{4}{5}log_{2}\frac{4}{5})=0.722$

1、信息增益
$Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}Ent(D^{v})$
a是数据集的自变量，V是某一个自变量可分成几个样本集（例如自变量色泽可按照青绿，乌黑和浅白三个属性将变量分为三个样本集，则V=3）

image.png

$Gain(D,\text{色泽})=Ent(D)-\sum_{v=1}^{3}\frac{|D^{v}|}{|D|}Ent(D^{v})$
$=Ent(D)-(\frac{|D^{1}|}{|D|}Ent(D^{1})+\frac{|D^{2}|}{|D|}Ent(D^{2})+\frac{|D^{3}|}{|D|}Ent(D^{3}))$
$=0.998-(\frac{6}{17}\times1.00 +\frac{6}{17}\times0.918 +\frac{6}{17}\times0.722 )=0.109$

image.png

选择信息增益最大的变量作为划分属性，对每个分支节点进行类似的操作，最终得到如下决策树：

决策树.png

2、信息增益率
信息增益准则对可取数值较多的属性有所偏好，为减少这种偏好可能带来的不利影响，选择用增益率作未选取划分属性的标准
信息增益率计算公式：

最后编辑于：2018.11.12 22:53:58

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

决策数及随机森林

推荐阅读更多精彩内容