LLM And Search

机器学习-决策树

发表于 更新于 分类于 ， 阅读次数： Valine：

决策树是机器学习中非常容易理解机模型，是最基础最常见的有监督学习模型，被用于分类或者回归，由于树结构与销售、教育、医疗诊断场景决策过程相似，因此在该领域应用广泛。

决策树的生成包括三个部分：特征选择，构造树，树剪枝

决策树算法的特点

1
2
3
优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题。
适用数据类型：数值型和标称型。

样例

姓名 年龄 长相 工资 写代码 类别
A 老 帅 高 不会 不见
B 年轻 一般 中等 会 见
C 年轻 丑 高 不会 不见
D 年轻 一般 高 会 见
E 年轻 一般 低 不会 不见

这是一个典型的是否进行约会的样例，数据中包含A-E五个人，包含年龄，长相，工资，会写代码五个属性，通过这五个属性来确定是否进行约会。整个数据集中包含特征为$A$=[年龄，长相，工资，写代码]=$$[A1,A2,A3,A4]$$

对于构建决策树过程中的第一步：特征选择，目前存在三种特征选择的启发函数：最大信息增益，信息增益比，基尼指数。接下来的几个计算实例都是使用这个样例。

ID3-最大信息增益

熵

熵是一种信息的度量方式，表示信息的混乱程度，也就是说：信息越有序，信息熵越低。例如：火柴有序放在火柴盒里，熵值很低，相反，熵值很高。假设样本空间D中的的概率分布为：
$$
p_{i}=\frac{|C_{i}|}{D}
$$

  • $C_{i}$为样本集合D中属于第$i$类标签的样本子集
  • $|C_{i}|$表示该子集的样本个数
  • $|D_{i}|$表示整个样本集的个数

数据集$D$的熵为
$$
H(D)=-\sum_{i=1}^{n}p_{i}log_{2}p_{i}
$$

  • 一定要注意前面的负号
  • $n$表示标签数
  • 指数可以使用以$2$位底或以$e$为底

在样例中，包含去见的2人，不去见的为3人，总共为5人，因此可以得到数据集$D$的熵为：
$$
H(D)=-(\frac{3}{5}*log_{2}\frac{3}{5}+\frac{2}{5}*log_{2}\frac{2}{5})=0.971
$$

为了决定创建决策树时使用哪个特征，这个时候就要针对不同的特征计算该特征的信息熵，由此引入条件熵，其计算公式为： $$ H(D|A)=-\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}(\sum_{k=1}^{k}\frac{|D_{ik}|}{|D_{i}|}log_{2}\frac{|D_{ik}|}{|D_{i}|}) $$
  • $D_{i}$表示$D$中特征$A$取第$i$个值的样本子集
  • $D_{ik}$表示$D_{i}$中属于第k类的样本子集
  • 存在等式关系$D_{i}=\sum_{k=1}^{k}D_{ik}$和$D=\sum_{i=1}^{n}D_{i}$

计算$A1$的条件熵，$A1$包含两个值$$[A11,A12]$$=[年龄:老, 年龄:年轻]，其中年龄老的会见的在整个样本中的人数为1，其中人数0，不见的人数为1；年龄年轻的在整个样本的人数为4，其中会见的人数为2，不见的人数为2。由此分析，求得特征$A1$对应的条件熵

$$
\begin{equation}
\begin{aligned}
H(D|A_{1})&=-\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}(\sum_{k=1}^{k}\frac{|D_{ik}|}{|D_{i}|}log_{2}\frac{|D_{ik}|}{|D_{i}|})
\&=-(\frac{1}{5}H(D_{1})+\frac{4}{5}H(D_{2}))
\&=-[\frac{1}{5}*(-0)+\frac{4}{5}(-\frac{2}{4}log_{2}\frac{2}{4}-\frac{2}{4}log_{2}\frac{2}{4})]
\&=0.8
\end{aligned}
\end{equation}
$$

由此可以得到所有特征对应的条件熵。

在ID3算法，使用的是启发函数为信息增益，所谓信息增益是针对样本内的特征而言的，对于不同的特征，使用样本集的熵与特征的条件熵的差作为该特征的信息增益。因此信息增益的定义如下

数据集的熵减去特征的条件熵
$$
g(D,A)=H(D)-H(D|A)
$$

算法流程

  • 给定样本集$D$以及提取存在的特征$A$

  • 根据整个样本集$D$以及标签计算$H(D)$

  • 根据特征$A_{i}$，求解特征对应的条件熵$H(D|A_{i})$，及信息增益$g(D,A_{i})$

  • 选择最大的信息增益对应的特征作为当前节点的划分标准

不足

使用增大信息增益作为节点的划分规则，由于信息增益反应的是数据不确定性减小的程度，所以对于取值较多的特征，这就意味着该特征的确定性越高，对应的条件熵也就越低，信息增益越大。因此使用最大信息增益偏向取值较多的特征。

C4.5-信息增益率

为了改进使用最大信息增益偏向取值较多的特征这一个不足，引入了信息增益率。

信息增益率

定义如下
$$
g_{g}(D,A)=\frac{g(D,A)}{H_{A}(D)}
$$
式子中的$H_{A}(D)$如下所示

$$
H_{A}(D)=-\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}log_{2}\frac{|D_{i}|}{|D|}
$$
求得信息增益之后，将信息增益与数据集关于特征$A$的取值的熵作比，得到信息增益率。

对于示例，继续条件熵的计算，$H_{A_{1}}(D)$表示数据集关于年龄这个特征的，对于年龄这个特征，在整个样本空间内有4个年轻的去见，一个年老的不去见，因此该特征的熵为：
$$
H_{A_{1}}(D)=-\frac{1}{5}log_{2}\frac{1}{5}-\frac{4}{5}log_{2}\frac{4}{5}=0.722
$$

取值较多的特征对应的信息增益较大，但是对应的特征的取值的熵也较大，一定程度上对取值较多的特征进行了惩罚和抑制。

C4.5算法流程

1
2
3
4
5
6
7
8
输入：数据集D，特征集A,类别集C,阈值thresh
输出：决策树T
if any(D) in Ci: T为单节点树，ci作为该节点的类，返回T；
elif A is None: T为单节点树，D中实例数最大的类别Ci作为该节点的类，返回T；
elif Ai=max(cal_info_gain_ratio(A)) 
	if Ai<thresh: T为单节点树，D中实例数最大的类别Ci作为该节点的类，返回T
	else：计算Ai总每个可能只ai，使用Ai=ai将D划分若干非空Di，将Di中实例最多的类别Ci作为标记构建子节点，有节点及子节点构成的数T，返回Ti；
对节点i，以Di为训练集，以A-Ai为特征集，递归上述步数得到子树Ti

CART

CART-classification and regression tree分类回归树

该算法即可用于回归又可以用于分类。构建树时使用特征的取值对样本空间进行二值划分，不仅可以处理离散数据同时可以处理连续数据。

CART分类-Gini指数

与信息熵相似，信息熵描述的是数据的混乱程度，基尼指数描述的是数据的纯度，基尼指数越小，对应的信息纯度越高。分类决策树使用基尼指数进行最优特征的选择，同时决定改特征的最优二值切分点。

Gini定义

分类问题中，假设存在$K$个类，样本点属于$k$的概率为$p_{k}$，则概率分布的基尼指数为
$$
\begin{align}
Gini(p)=\sum_{k=1}^{K}p_{k}(1-p_{k})& =1-\sum_{k=1}^{K}p_{k}^{2}\
& where :::::: p_{k}=\frac{|C_k|}{D}
\end{align}
$$
对于二分类问题，如果样本属于第1个类的概率为$p$，则概率分布的基尼指数可以表示为
$$
\begin {equation}
Gini(p)=2p(1-p)
\end{equation}
$$
假设存在$K$个类，则数据集$D$的基尼指数为：
$$
Gini(D)=1-\sum_{k=1}^{K}(\frac{|C_{k}|}{|D|})^{2}
$$

  • 公式内的符号定义与熵的公式中的含义相应。

  • $|C_{k}|$为样本集合$D$中属于第$k$类标签的样本子集的样本数量，$K$是类的个数

特征$A$的$Gini$指数为：
$$
Gini(D|A)=\sum_{k=1}^{K}\frac{|D_{k}|}{|D|}Gini(D_{k})
$$
每次选择$Gini$指数最小的特征及其对应的切分点进行分类

如果样本$D$根据特征$A$是否取某一可能值$a$被分割成$D_{1}$和$D_{2}$两部分，则$D_{1}={(x,y)\in D|A=a}$并且$D_{2}=D-D_{1}$则在特征条件$A$的条件下，集合$D$的基尼指数可以定义为：
$$
Gini(D|A)=\frac{|D_{1}|}{|D|}Gini(D_{1})+\frac{|D_{2}|}{|D|}Gini(D_{2})
$$
基尼指数值越大，对应的样本的不确定性越大，与熵相似，因此选择最小的基尼指数作为划分标准。

同样是上面的例子，计算特征$A_{1}$对应的基尼指数，当$A_{1}$中的特征为年轻时，会将样本集一分为2，一部分为年轻，对应4人；一部分为年老，对应1人，基于此进行该特征值下的基尼指数的计算
$$
\begin{equation}
\begin{aligned}
Gini(D|A_{1}=年轻)&=\frac{1}{5}Gini(D_{1})+\frac{4}{5}Gini(D_{2})
\&=\frac{1}{5}[21*(1-1)]+\frac{4}{5}(2\frac{2}{4}[1-\frac{2}{4})]
\&=\frac{2}{5}
\end{aligned}
\end{equation}
$$
同理，可以得到
$$
\begin{equation}
\begin{aligned}
Gini(D|A_{1}=老)&=\frac{1}{5}Gini(D_{1})+\frac{4}{5}Gini(D_{2})
\&=\frac{1}{5}[21(1-1)]+\frac{4}{5}(2\frac{2}{4}*[1-\frac{2}{4})]
\&=\frac{2}{5}
\end{aligned}
\end{equation}
$$
依次可以得到不同特征值取值下的$Gini$指数，并选择最小的$Gini$指数作为特征进行决策树创建。

CART回归-最小平方差损失

给定训练数据集
$$
D={ (x_1,y_2),(X_2,y_2),…,(x_N,y_N) }
$$
对于决策树的核心问题是：如何选择划分点?如何决定节点的输出值？

对于上面的分类树使用的是信息论中的评价指标，信息增益，信息增益率，基尼指数；而对于回归树使用的是启发式的方法。假设数据中存在$n​$个特征，每个特征有$s_{i}(i \in (1,n))​$个取值，选择第j个变量$x^{(j)}​$和它的取值s作为切分变量和切分点并将整个数据集划分为两个数据空间
$$
R_j(j,s)= { x|x^{(j)} \leq s } :::::::: R_j(j,s)= { x|x^{(j)} > s }
$$
如上图所示，每个节点将数据空间划分为两个部分，划分点的选择基于最小平方差损失。遍历所有的特征，并尝试该特征的所有取值对空间进行划分，直到特征j的取值s使的损失函数最小，对于CART回归树使用最小平方差损失，具体的求解方式为
$$
\min {j,s} [\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]
$$
式中的$c_m=ave(y_i|x_i \in R_m)​$

遍历所有的变量$j​$，对固定的切分变量$j​$扫描切分点$s​$，选择使得上述公式取值最小的$(j,s)​$

假设输入空间被划分为M个单元$R_2,R_2,R_3,R_m​$，那么每个区域的输出值就是该区域内所有点$y​$值的平均值$c_m=ave(y_i|x_i \in R_m)​$，也就是
$$
\begin{align}
& R_1(j,s)={x|x^{(j)} \ge s }, :::::: R_2(j,s)={x|x^{(j)} > s } \
& c_m=\frac{1}{N_m} \sum_{x_i \in R_m(i,s)}y_i, ::::x \in R_m, :::m=1,2
\end{align}
$$

总结

决策树算法名称 算法特点
ID3 只用于分类
只处理离散数据
偏向样本较多的特征
泛化能力较差，容易过拟合
对于缺失值比较敏感
节点下生成多叉分支，特征在层间不会复用
通过剪枝权衡数的准确性和泛化能力
C4.5 只用于分类
可以处理离散和连续数据
添加取值较多的特征惩罚
泛化能力相较ID3较好
节点下生成多叉分支，特征在层间不会复用
通过剪枝权衡数的准确性和泛化能力
CART 用于分类和回归
可以处理离散和连续数据
回归使用最小平方差，分类使用最小基尼指数
每个节点产生两个分支，最后形成一个二叉树，特征层间复用
利用全部数据发现所有可能的树结构

参考文献

赏杯咖啡！