CMake简单使用

前言

在本章中主要学习决策树的构建，决策树就是使用“分而治之”的思想对样本进行处理。决策树学习的目标是为了产生一棵泛化能力强的模型。

算法介绍

算法结束

决策算法使用递归方式构建模型，有三种情况会导致递归返回：

1. 当前节点包含的样本全部属于同一类别，无需划分；
2. 当前属性集为空，或时所有样本在属性上取值相同，无法划分；
3. 当前节点包含的样本集合为空，不能划分。

属性划分原则

决策树中，如何选择最优的划分属性？在划分过程中，希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”（purity）越高越好。

信息增益——ID3决策树算法

概念

信息熵是衡量样本集合纯度最常用的一种指标。假定当前样本集合D中，第k类样本所占比例为p_k,(k=1,2…,|y|),则信息熵的定义为：
$$
Ent(D)=-\sum^{|y|}_{k=1}p_k\log p_k
$$
Ent(D)的值越小，D的纯度越高，不确定性越小，决策树往熵减的方向划分。

说到信息熵不得不说到信息（参考来源），衡量不确定性，衡量方式：$-log(x)$。

信息增益(Indormation Gain)描述的是划分前后信息熵的变化。假定属性a有V个值${a^1,a^2,\ldots,a^v}$，第v个分支表示属性a取值为a^v的全部样本D^v,表达式如下：
$$
Gain(D,a)=Ent(D)-\sum^{V}_{v=1}\frac{|D^v|}{|D|}Ent(D^v)
$$

ID3决策树算法使用信息增益选择划分属性。

增益率——C4.5决策树算法

概念

增益率表达如下:
$$
Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}
$$

其中IV(a)为属性a的固有值，计算方式如下：
$$
IV(a)=-\sum^V_{v=1}\frac{|D^v|}{|D|}\log^{\frac{|D^v|}{|D|}}_{2}
$$

基尼指数——CART决策树算法

概念

基尼值：

$$
\begin{align}
Gini(D) &=\sum^{|y|}_{k=1}\sum_{k\neq k’}p_kp_{k’}\\
&=1-\sum^{|y|}_{k=1}p^2_k
\end{align}
$$

其中k为样本类型。Gini(D)越小，D的纯度越高。

基尼指数：
$$
Gini\_index(D,a)=\sum^V_{v=1}\frac{|D^v|}{|D|}Gini(D^v)
$$

决策树剪枝

剪枝是为了防止决策树算法过拟合的方法。

预剪枝

定义

对每个节点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶结点。经过预剪枝的决策树不易造成过拟合，并且可以减少训练时间和开销，但是有欠拟合的风险。

后剪枝

定义

先从训练集中生成一棵完整的决策树，然后自底向上考察非叶结点，如果将该子树替换为叶结点能带来决策树泛化性能提高，则将该子树他替换为叶结点。后剪枝欠拟合风险小，泛化性能优于预剪枝，但是训练时间和开销较大。

连续值处理

即连续值离散化处理

对连续属性a，可考察包含n-1个元素的候选划分点集合。

$$
T_a=\{\frac{a^i+a^{i+1}}{2}|1 \leqslant i \leqslant n-1\}
$$

逐个对划分点进行考察，选择最佳划分点：

$$
\begin{align}
Gain(D,a)&=Gain(D,a,t)\\
&=\max_{t\in T_a}Ent(D)-\sum_{\lambda\in\{-,+\}}\frac{|D^\lambda_t|}{|D|}Ent(D^\lambda_t)
\end{align}
$$

计算出来的信息熵增益值可以离散属性相比较。

缺失值处理

在实际中存在不完整样本，即样本的某些属性缺失。

假设数据集为$D$，属性值完整的样本构成$\widetilde D$,并且每个样本赋予一个权重$\omega_x$,则：

未缺失属性样本比例：
$$
\rho=\frac{\sum_{x\in\widetilde D}\omega_x}{\sum_{x\in D}\omega_x}
$$

未缺失属性样本中k标签的比例：
$$
\widetilde p_k=\frac{\sum_{x\in\widetilde D_k}\omega_x}{\sum_{x\in {\widetilde D}}\omega_x},(1\leqslant k\leqslant|y|)
$$

无缺失样本中a取值v的比例：

$$
\widetilde r_v=\frac{\sum_{x\in\widetilde D^v}\omega_x}{\sum_{x\in {\widetilde D}}\omega_x},(1\leqslant v\leqslant V)
$$

插值信息增益

$$
\begin{align}
Gain(D,a)&=\rho×Gain(\widetilde D,a)\\
&=\rho×(Ent(\widetilde D)-\sum^V_{v=1}\widetilde r_vEnt(\widetilde D^v))
\end{align}
$$

其中，

$$
Ent(\widetilde D)=-\sum^{|y|}_{k=1}\widetilde p_k \log^{\widetilde p_k}_2
$$

若属性已知则$\omega_x$不变，若为未知，则将x同时划入所有节点中，且样本中的权值调整为：$\widetilde r_v·\omega_x$

多变量决策树

多变量决策树的主要作用在于简化决策树结构

在非叶结点中，不是对单个属性进行判断，而是对属性的线性组合进行判断。

主要算法：OC1

增量学习

用于收到新样本之后调整模型。

算法：ID4、ID5R、ITI

相关概念

后验概率：先知道结果，由结果估计原因的概率分布，P(交通方式|交通时间)–先知道花费的时间，估算使用交通工具的概率。

先验概率：先于结果，估计原因的概率分布。

似然估计： 先确定原因，根据原因估计结果的概率估计。

参考资料

《机器学习》作者：周志华；

详解信息熵

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 qinzhtao@163.com