决策树中的算法实现

决策树中的算法实现

本文主要描述以下概念及算法

  • 信息增益的计算方法
  • 信息增益比的计算方法
  • ID3 算法的实现
  • C4.5 算法的实现
  • 决策树的剪枝算法
  • 基尼指数的计算方法
  • 最小二乘回归树生成算法
  • CART 生成算法
  • CART 剪枝算法

信息增益算法($Information\ Gain$)

输入

  • 训练数据集$D$
  • 特征$A$

输出

特征$A$对训练数据集$D$的信息增益$g(D,A)$

具体实现

  1. 计算数据及$D$的经验熵

$$
H(D) = -\sum_{k=1}^K \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}\tag{1}
$$

公式说明:

  • $|D|$中竖线的意思为数据集中的个数,可以用公式表示:

    $$
    |D| = \sum_k I (c_k \in D) \tag{1.1}
    $$

  • 按照常规的熵的定义,$H(D) = - \sum_k p_k \log_2p_k$,是使用概率定义的,这里我们进行计算的时候,使用$\frac{|C_k|}{|D|}$来代表概率,即使用经验中简单的统计占比来表示。

  1. 计算特征$A$对数据集$D$的经验条件熵$H(D|A)$:

$$
H(D|A) = \sum_{i=1}^n \frac{|D_i|}{|D|} H(D_i) = - \sum_{i=1}^n \frac{|D_i|}{|D|} \sum_{k=1}^K \frac{|D_{ik}|}{|D_i|} \log_2 \frac{|D_{ik}|}{|D_i|} \tag{2}
$$

公式说明:

  • 分别求属性$A$的每个分类对应求得的熵,然后按照权重相加,其中,$\frac{|D_i|}{|D|}$就是属性$A_i$的权重。
  1. 计算总的信息增益:

$$
g(D,A) = H(D) - H(D|A) \tag{3}
$$

信息增益比

计算方法:

$$
g_R (D, A) = \frac{g(D,A)}{H_A(D)} \tag{4}
$$

ID3 算法

输入

训练数据集:$D$

特征集:$A$

阈值:$\varepsilon$

输出

决策树:$T$

具体实现

  1. 若$D$中所有实例均属于同一类$C_k$,则 T 为节点树,并将类$C_k$作为该节点的类标记,返回$T$;
  2. 若$A=\mathcal{\emptyset}$,则$T$为单节点树,并将$D$中实例数最大的类$C_k$作为该节点的类标记,返回$T$;
  3. 否则按照信息增益算法计算$A$中个特征对$D$的信息增益,选择信息增益最大的特征$A_g$;
  4. 如果$A_g$的信息增益小于阈值$\varepsilon$,则置$T$为单节点树,并将$D$中实例数最大的类$C_k$作为该节点的类标记,返回$T$;
  5. 否则,对$A_g$的每一个可能只$a_i$,依照$A_g=a_i$将$D$分割为若干非空子集$D_i$,将$D_i$中实力数最大的类作为标记,构建子节点,由节点及其子节点够成树$T$,并返回$T$;
  6. 对第$i$个子节点,以$D_i$作为训练集,以$A-\lbrace A_g \rbrace$为特征集,递归调用步骤$1$~$5$,得到子树$T_i$, 返回$T$。

C4.5 算法(和上面的算法差不多)

输入

训练数据集:$D$

特征集:$A$

阈值:$\varepsilon$

输出

决策树:$T$

具体实现

  1. 若$D$中所有实例均属于同一类$C_k$,则 T 为节点树,并将类$C_k$作为该节点的类标记,返回$T$;
  2. 若$A=\emptyset$,则$T$为单节点树,并将$D$中实例数最大的类$C_k$作为该节点的类标记,返回$T$;
  3. 否则按照信息$(4)$式计算$A$中个特征对$D$的信息增益比,选择信息增益比最大的特征$A_g$;(划重点,信息增益变成了信息增益比)
  4. 如果$A_g$的信息增益比小于阈值$\varepsilon$,则置$T$为单节点树,并将$D$中实例数最大的类$C_k$作为该节点的类标记,返回$T$;
  5. 否则,对$A_g$的每一个可能只$a_i$,依照$A_g=a_i$将$D$分割为若干非空子集$D_i$,将$D_i$中实力数最大的类作为标记,构建子节点,由节点及其子节点够成树$T$,并返回$T$;
  6. 对第$i$个子节点,以$D_i$作为训练集,以$A-\lbrace A_g \rbrace$为特征集,递归调用步骤$1$~$5$,得到子树$T_i$, 返回$T$。

决策树剪枝算法

输入

生成算法产生的整个树:$T$

参数:$ \alpha$

输出

修剪后的子树: $T_\alpha$

具体实现

  1. 计算每个节点的经验熵;

  2. 递归地从树的叶节点向上回缩;

    设一组叶节点回缩到器父节点之前与之后的整体树分别为$T_B$与$T_A$,其对应的损失函数值分别是$C_\alpha(T_B)$与$C_\alpha(T_A)$,如果符合下面的条件则进行剪枝,即将父节点变为性的叶节点,将原本的叶节点合如该节点。

$$
C_\alpha(T_A) \le C_\alpha(T_B)\tag{5}
$$

注:$(5)$式中的等于是因为如果损失函数没有变化,则没必要去在计算一层树,直接剪掉 ⚔ 就好了。

  1. 返回$(2)$,知道不能继续为止,则得到了损失函数最小的子树$T_A$

基尼指数的计算方法

分类问题中假设有$K$个类,样本点属于第$k$类的概率为$p_k$,则概率分布的基尼指数定义为:

$$
Gini(p) = \sum_{k=1}^K p_k(1 - p_k) = 1 - \sum_{k=1}^K p^2_k \tag{6}
$$

对于二分类问题,若样本点属于第一个类的概率是$p$,则概率分布的基尼为:

$$
Gini(p) = 2p(1-p) \tag{6.1}
$$

对于给定的样本集合$D$,其基尼指数为:

$$
Gini(D) = 1-\sum_{k-1}^K (\frac{|C_k|}{|D|})^2 \tag{6.2}
$$

这里同样使用了基于统计数计算概率的方法。$C_k$是$D$中属于第$k$类样本的子集,$K$是类的个数。

最小二乘回归树生成算法

输入

训练数据集:$D$;

输出

回归树:$f(x)$

具体实现

在训练数据集所在的输入空间中,递归的将每个区域划分成两个子区域,并决定每个子区域上的输出值。构建二叉决策树。

  1. 选择最优切分变量$j$与切分点$s$求解:

$$
\min_{j,s} \left [ \min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2\right ] \tag{7.1}
$$

遍历变量$j$,对固定的切分变量$j$扫描切分点$s$。选择是上式达到最小值的$(j,s)$。

  1. 用选定的$(j,s)$划分区域并决定相应的输出值:

$$
R_1(j,s) = \left \lbrace x | x^{(j)} \le s \right \rbrace, \\
R_2(j,s) = \left \lbrace x | x^{(j)} \gt s \right \rbrace, \\
\hat{c}_m = \frac{1}{N_m}
\sum_{x_i \in
R_n(j,s)}
y_i, x \in R_m, m = 1,2
\tag{7.2}
$$

  1. 继续对两个子区域调用步骤$1,2$,直至满足停止条件。
  2. 将输入空间划分为$M$个区域$R_1,R_2,\cdots,R_M$,生成决策树。

$$
f(x) = \sum_{m=1}^M \hat{c}_m I (x \in R_M) \tag{7.3}
$$

CART 生成算法

输入

训练数据集 D;

停止计算的条件;

输出

CART 决策树

具体实现

根据训练数据集,从根节点开始递归地对每个节点进行以下操作构建二叉决策树。

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

CART 剪枝算法

输入

$CART$算法生成的决策树$T_0$

输出

最优决策树$T_\alpha$

具体实现

  1. 设$k=0, T=T\alpha$;
  2. 设$\alpha = + \infty$;
  3. 自下而上地对个内部节点$t$计算$C(T_t)$,$|T_t|$以及

$$
g(t) = \frac{C(t) - C(T_t)}{|T_t| - 1} \tag{8} \\
\alpha = min(\alpha, g(t))
$$

这里,$T_t$表示以$t$为根节点的子树,$C(T_i)$是对训练数据的预测误差,$|T_t|$是$T_t$的叶子节点个数。

  1. 对$g(t)=\alpha$的内部节点$t$进行剪枝,并对叶节点$t$以多数表决法决定其类,得到树$T$
  2. 设$k=k+1$,$ \alpha_k = \alpha$, $T_k = T$;
  3. 如果$T_k$不是有根节点即两个叶节点构成的树,则糊掉步骤$(2)$;否则令$T_k=T_n$;
  4. 采用交叉验证法在字数序列$T_0,T_1,\cdots,T_n$中选择最优子树$T_\alpha$。

评论

Agile Angularjs Animation Application Artificial Intelligence BP Babel Bokeh Book C4.5 CART CD CLI CSS CentOS CheetSheet Cinder Clipboardjs Concept Continuous Delivery DeepLearning Department DevOps Develop Development Directive Distribution Django Document ECMA ES5 ES6 ES7 Echarts Engine Entropy Filter Front End Gallery Git Gradient descent Hexo Horizon ID3 ID3.5 Icarus JavaScript Javascript KVM LaTeX LeetCode LibreOffice Linux MNIST Machine Learning Matrix MiddleWare Module Native Network Nginx NodeJS Numpy OOP OpenSSH OpenStack OpenStackApi Operations Oprations PDF PLA Pandas Pipline Probability Python React Relational algebra Restful Route SVD SVM Scalar Sigmoid Team Tempest Tensor TensorFlow Testing Time TimeMachine Tips Vector Vmware Vue Vuex WSGI Web Word Cut aliyun auth babel certbot debounce decision tree dns docker dockerfile eject footer git header homebrew html5 http https jupyter jwt keystone lab loader lodash mathematics migrate nav openstack outline pdf2html pm2 proto prototype python replace request response rp rt ruby scikit-learn section singular value decomposition sklearn stylus throttle url vue-router vue-ssr webpack 事件 事件代理 事件冒泡 事件捕获 低通滤波器 入门 全局 全局变量 全局对象 全栈 公式 决策树 函数 分类器 剪枝 加速 动态变量 匹配滤波边缘检测 卷积 卷积核 原型链 双向绑定 反向传播 发布 变量类型 可视化 基尼指数 官方示例 对偶形式 对象 小技巧 平移和查分边缘检测 思维导图 感知机模型 拉格朗日乘子法 推导 提交阶段 数据 数据绑定 最大似然估计 最小二乘估计 最小二乘回归树 最小二乘法 本地 朴素贝叶斯 朴素贝叶斯算法 机器学习 条件概率 标签模板 梯度下降 梯度方向边缘检测 概念 概率 模板字符串 正则 求导 流程 源码 源码阅读 灰度 特征工程 生命周期 矩阵 神经网络 私有对象 科学计算 算法 算法实现 线性回归 缺失 联合概率 脚手架 识别 调试 贝叶斯 贝叶斯判定准则 边缘检测 边际概率 闭包 间隔 防抖动 限流 随机森林 高斯分布 高通滤波器
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×