决策数及随机森林

2018-10-19 本文已影响36人阿童89

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

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

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

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

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

决策数及随机森林

猜你喜欢

热点阅读