当前位置：首页 > news >正文

机器学习之决策树（DecisionTree）

news 来源：原创 2025/6/11 9:35:54

决策树中选择哪一个特征进行分裂，称之为特征选择。
特征选择是找出某一个特征使得分裂后两边的样本都有最好的“归宿”，即左边分支的样本属于一个类别、右边分支的样本属于另外一个类别，左边和右边分支包含的样本尽可能分属同一类别，此时分裂节点的纯度（purity）高，能够表征这种纯度高低的常用指标是信息熵（information entropy）。
假设有一个数据集 $D$ ，包含 $N$ 个样本（ $n = 1, 2, 3, ..., N$ ），每一个样本有 $k$ 个属性（ $k = 1, 2, 3, ..., K$ ），样本共计有 $C$ 个类别（ $c = 1, 2, 3, ..., C$ ），则 $D$ 的信息熵可定义为：
$Entropy(D)=-\sum_{c=1}^{C}p_c \log {p_c}=-\sum_{c=1}^{C}\frac{N_c}{N} \log \frac{N_c}{N}\tag{1}$
式 $(1)$ 中， $p_c$ 表示数据集 $D$ 中第 $c$ 类样本所占的比例， $N_c$ 表示第 $c$ 类样本的数量， $E n t ro p y (D)$ 的值越小，则 $D$ 的纯度越高。

假设离散属性 $A$ 有个取值 $M$ （ $m = 1, 2, 3, ..., M$ ），若使用属性A对样本集 $D$ 进行分裂，则会将数据集划分为 $M$ 个子集 $D^m$ ，每个子集包含的样本数记为 $N_m$ ，根据式 $(1)$ 计算出 $D^m$ 的信息熵，考虑到不同的子集所包含的样本数不同，分别给每个子集赋予权重 $N_m/N$ ，计算属性A对于样本集 $D$ 进行划分所得的信息增益（information gain）：
$\begin{aligned} Gain(D,A)&=Entropy(D)-\sum_{m=1}^{M}\frac{N_m}{N}Entropy(D^m)\\ &=Entropy(D)-\sum_{m=1}^{M}\frac{N_m}{N}\sum_{c=1}^{C}(-\frac{N_{mc}}{N_m}\log\frac{N_{mc}}{N_m})\tag{2} \end{aligned}$
式 $(2)$ 中， $N_{mc}$ 表示子集 $D^m$ 中类别为 $c$ 的样本的个数。

表1 西瓜数据集

编号	色泽	根蒂	敲声	纹理	脐部	触感	好瓜
1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	是
3	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	是
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	是
5	浅白	蜷缩	浊响	清晰	凹陷	硬滑	是
6	青绿	稍蜷	浊响	清晰	稍凹	软粘	是
7	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	是
8	乌黑	稍蜷	浊响	清晰	稍凹	硬滑	是
9	乌黑	稍蜷	沉闷	稍糊	稍凹	硬滑	否
10	青绿	硬挺	清脆	清晰	平坦	软粘	否
11	浅白	硬挺	清脆	模糊	平坦	硬滑	否
12	浅白	蜷缩	浊响	模糊	平坦	软粘	否
13	青绿	稍蜷	浊响	稍糊	凹陷	硬滑	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	否
15	乌黑	稍蜷	浊响	清晰	稍凹	软粘	否
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	否
17	青绿	蜷缩	沉闷	稍糊	稍凹	硬滑	否

以表1中的西瓜数据集为例，数据集包含17个样本（ $n = 1, 2, 3, ..., 17$ ），每个样本有6个属性（ $k = 1, 2, 3, ..., 6$ ），样本共计有2个类别（ $c = 是, 否$ ）。

1.17个样本中，好瓜样本有8个、差瓜样本有9个，数据集 $D$ 的信息熵为：
$Entropy(D)=-\frac{8}{17} \log \frac{8}{17}-\frac{9}{17} \log \frac{9}{17}=0.9975\tag{3}$

2.计算属性集合{色泽, 根蒂, 敲声, 纹理, 脐部, 触感}中每个属性的信息增益，以属性"触感"为例，有{硬滑, 软粘}两个取值：

$D^1$ (触感=硬滑)：包含编号为{1,2,3,4,5,8,9,11,13,14,16,17}的12个样本，其中好瓜有{1,2,3,4,5,8}的6个样本、差瓜有{9,11,13,14,16,17}的6个样本；
$D^2$ (触感=软粘)：{6,7,10,12,15}的5个样本，其中好瓜有{6,7}的2个样本、差瓜有{10,12,15}的3个样本。

根据式 $(1)$ 计算上述两个子集的信息熵：
$\begin{aligned} Entropy(D^1)&=-\frac{6}{12} \log \frac{6}{12}-\frac{6}{12} \log \frac{6}{12}=1.000\\ Entropy(D^2)&=-\frac{2}{5} \log \frac{2}{5}-\frac{3}{5} \log \frac{3}{5}=0.9709 \end{aligned}$

3.根据式 $(2)$ 计算属性"触感"的信息增益：
$\begin{aligned} Gain(D,触感)&=Entropy(D)-\sum_{m=1}^{M}\frac{N_m}{N}Entropy(D^m)\\ &=0.9975-(\frac{12}{17}\times1.0000+\frac{5}{17}\times0.9709)\\ &=0.0061 \end{aligned}$
4.根据式 $(2)$ 计算其他属性的信息增益：
$\begin{aligned} Gain(D,色泽)&=0.9975-[\frac{6}{17}\times Entropy(色泽=青绿)+\frac{6}{17}\times Entropy(色泽=乌黑)+\frac{5}{17}\times Entropy(色泽=浅白)]\\ &=0.9975-[\frac{6}{17}\times(-(\frac{3}{6}\log\frac{3}{6}+\frac{3}{6}\log\frac{3}{6}))+\frac{6}{17}\times(-(\frac{4}{6}\log\frac{4}{6}+\frac{2}{6}\log\frac{2}{6}))+\frac{5}{17}\times(-(\frac{1}{5}\log\frac{1}{5}+\frac{4}{5}\log\frac{4}{5}))]\\ &=0.1081\\ Gain(D,根蒂)&=0.9975-[\frac{8}{17}\times Entropy(根蒂=蜷缩)+\frac{7}{17}\times Entropy(根蒂=稍蜷)+\frac{2}{17}\times Entropy(根蒂=硬挺)]\\ &=0.9975-[\frac{8}{17}\times(-(\frac{5}{8}\log\frac{5}{8}+\frac{3}{8}\log\frac{3}{8}))+\frac{7}{17}\times(-(\frac{3}{7}\log\frac{3}{7}+\frac{4}{7}\log\frac{4}{7}))+\frac{2}{17}\times(-(\frac{0}{2}\log\frac{0}{2}+\frac{2}{2}\log\frac{2}{2}))]\\ &=0.1426\\ Gain(D,敲声)&=0.9975-[\frac{10}{17}\times Entropy(敲声=浊响)+\frac{5}{17}\times Entropy(敲声=沉闷)+\frac{2}{17}\times Entropy(敲声=清脆)]\\ &=0.9975-[\frac{10}{17}\times(-(\frac{6}{10}\log\frac{6}{10}+\frac{4}{10}\log\frac{4}{10}))+\frac{5}{17}\times(-(\frac{2}{5}\log\frac{2}{5}+\frac{3}{5}\log\frac{3}{5}))+\frac{2}{17}\times(-(\frac{0}{2}\log\frac{0}{2}+\frac{2}{2}\log\frac{2}{2}))]\\ &=0.1407\\ Gain(D,纹理)&=0.9975-[\frac{9}{17}\times Entropy(纹理=清晰)+\frac{5}{17}\times Entropy(纹理=稍糊)+\frac{3}{17}\times Entropy(纹理=模糊)]\\ &=0.9975-[\frac{9}{17}\times(-(\frac{7}{9}\log\frac{7}{9}+\frac{2}{9}\log\frac{2}{9}))+\frac{5}{17}\times(-(\frac{1}{5}\log\frac{1}{5}+\frac{4}{5}\log\frac{4}{5}))+\frac{3}{17}\times(-(\frac{0}{3}\log\frac{0}{3}+\frac{3}{3}\log\frac{3}{3}))]\\ &=0.3805\\ Gain(D,脐部)&=0.9975-[\frac{7}{17}\times Entropy(脐部=凹陷)+\frac{6}{17}\times Entropy(脐部=稍凹)+\frac{3}{17}\times Entropy(脐部=平坦)]\\ &=0.9975-[\frac{7}{17}\times(-(\frac{5}{7}\log\frac{5}{7}+\frac{2}{7}\log\frac{2}{7}))+\frac{6}{17}\times(-(\frac{3}{6}\log\frac{3}{6}+\frac{3}{6}\log\frac{3}{6}))+\frac{4}{17}\times(-(\frac{0}{4}\log\frac{0}{4}+\frac{4}{4}\log\frac{4}{4}))]\\ &=0.2891\\ \end{aligned}$
上述计算过程中有一种特殊情况：某属性（根蒂=硬挺、敲声=清脆、纹理=模糊、脐部=平坦）分裂时，属性某个取值对应的样本全是反例，正例数量为0，此时其信息熵为：
$E=-(1\times \log(1)+0\times \log(0))$
在数学上，由于 $lim_{x→0}x\log(x)=0$ ，因此上述情况的信息熵为0

5.根据最大信息增益选择分裂属性，即选择属性"纹理"进行分裂，分裂后的样本分布：

属性: 取值	样本	好瓜	差瓜	信息熵
纹理:清晰	{1,2,3,4,5,6,8,10,15}	{1,2,3,4,5,6,8}	{10,15}	$E(纹理=清晰)=-(\frac{7}{9}\log\frac{7}{9}+\frac{2}{9}\log\frac{2}{9})=0.7642$
纹理:稍糊	{7,9,13,14,17}	{7}	{9,13,14,17}	$E(纹理=稍糊)=-(\frac{1}{5}\log\frac{1}{5}+\frac{4}{5}\log\frac{4}{5})=0.7219$
纹理:模糊	{11,12,16}	{}	{11,12,16}	$)=-(\frac{0}{3}\log\frac{0}{3}+\frac{3}{3}\log\frac{3}{3})=0.0000$

表2 西瓜数据集——纹理=清晰

编号	色泽	根蒂	敲声	纹理	脐部	触感	好瓜
1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	是
3	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	是
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	是
5	浅白	蜷缩	浊响	清晰	凹陷	硬滑	是
6	青绿	稍蜷	浊响	清晰	稍凹	软粘	是
8	乌黑	稍蜷	浊响	清晰	稍凹	硬滑	是
10	青绿	硬挺	清脆	清晰	平坦	软粘	否
15	乌黑	稍蜷	浊响	清晰	稍凹	软粘	否

$\begin{aligned} Gain(D^{纹理=清晰},色泽)&=0.7642-[\frac{4}{9}\times Entropy(色泽=青绿)+\frac{4}{9}\times Entropy(色泽=乌黑)+\frac{1}{9}\times Entropy(色泽=浅白)]\\ &=0.7642-[\frac{4}{9}\times(-(\frac{3}{4}\log\frac{3}{4}+\frac{1}{4}\log\frac{1}{4}))+\frac{4}{9}\times(-(\frac{3}{4}\log\frac{3}{4}+\frac{1}{4}\log\frac{1}{4}))+\frac{1}{9}\times(-(\frac{1}{1}\log\frac{1}{1}+\frac{0}{1}\log\frac{0}{1}))]\\ &=0.0430\\ Gain(D^{纹理=清晰},根蒂)&=0.7642-[\frac{5}{9}\times Entropy(根蒂=蜷缩)+\frac{3}{9}\times Entropy(根蒂=稍蜷)+\frac{1}{9}\times Entropy(根蒂=硬挺)]\\ &=0.7642-[\frac{5}{9}\times(-(\frac{5}{5}\log\frac{5}{5}+\frac{0}{0}\log\frac{0}{0}))+\frac{3}{9}\times(-(\frac{2}{3}\log\frac{2}{3}+\frac{1}{3}\log\frac{1}{3}))+\frac{1}{9}\times(-(\frac{0}{1}\log\frac{0}{1}+\frac{1}{1}\log\frac{1}{1}))]\\ &=0.4581\\ Gain(D^{纹理=清晰},敲声)&=0.7642-[\frac{6}{9}\times Entropy(敲声=浊响)+\frac{2}{9}\times Entropy(敲声=沉闷)+\frac{1}{9}\times Entropy(敲声=清脆)]\\ &=0.7642-[\frac{6}{9}\times(-(\frac{5}{6}\log\frac{5}{6}+\frac{1}{6}\log\frac{1}{6}))+\frac{2}{9}\times(-(\frac{2}{2}\log\frac{2}{2}+\frac{0}{0}\log\frac{0}{0}))+\frac{1}{9}\times(-(\frac{0}{0}\log\frac{0}{0}+\frac{1}{1}\log\frac{1}{1}))]\\ &=0.3308\\ Gain(D^{纹理=清晰},脐部)&=0.7642-[\frac{5}{9}\times Entropy(脐部=凹陷)+\frac{3}{9}\times Entropy(脐部=稍凹)+\frac{1}{9}\times Entropy(脐部=平坦)]\\ &=0.7642-[\frac{5}{9}\times(-(\frac{5}{5}\log\frac{5}{5}+\frac{0}{5}\log\frac{0}{5}))+\frac{3}{9}\times(-(\frac{2}{3}\log\frac{2}{3}+\frac{1}{3}\log\frac{1}{3}))+\frac{1}{9}\times(-(\frac{0}{0}\log\frac{0}{0}+\frac{1}{1}\log\frac{1}{1}))]\\ &=0.4581\\ Gain(D^{纹理=清晰},触感)&=0.7642-[\frac{6}{9}\times Entropy(触感=硬滑)+\frac{3}{9}\times Entropy(触感=软粘)]\\ &=0.7642-[\frac{6}{9}\times(-(\frac{6}{6}\log\frac{6}{6}+\frac{0}{6}\log\frac{0}{6}))+\frac{3}{9}\times(-(\frac{2}{3}\log\frac{2}{3}+\frac{1}{3}\log\frac{1}{3}))]\\ &=0.4581\\ \end{aligned}$
“根蒂”、“脐部”、"触感"3个属性的信息增益均达到最大，可任选其一继续分裂。

表3 西瓜数据集——纹理=稍糊

编号	色泽	根蒂	敲声	纹理	脐部	触感	好瓜
7	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	是
9	乌黑	稍蜷	沉闷	稍糊	稍凹	硬滑	否
13	青绿	稍蜷	浊响	稍糊	凹陷	硬滑	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	否
17	青绿	蜷缩	沉闷	稍糊	稍凹	硬滑	否

$\begin{aligned} Gain(D^{纹理=稍糊},色泽)&=0.7219-[\frac{4}{5}\times Entropy(色泽=青绿)+\frac{4}{5}\times Entropy(色泽=乌黑)+\frac{1}{5}\times Entropy(色泽=浅白)]\\ &=0.7219-[\frac{2}{5}\times(-(\frac{0}{2}\log\frac{0}{2}+\frac{2}{2}\log\frac{2}{2}))+\frac{2}{5}\times(-(\frac{1}{2}\log\frac{1}{2}+\frac{1}{2}\log\frac{1}{2}))+\frac{1}{5}\times(-(\frac{0}{1}\log\frac{0}{1}+\frac{1}{1}\log\frac{1}{1}))]\\ &=0.3219\\ Gain(D^{纹理=稍糊},根蒂)&=0.7219-[\frac{4}{5}\times Entropy(根蒂=稍蜷)+\frac{1}{5}\times Entropy(根蒂=蜷缩)]\\ &=0.7219-[\frac{4}{5}\times(-(\frac{1}{4}\log\frac{1}{4}+\frac{3}{4}\log\frac{3}{4}))+\frac{1}{5}\times(-(\frac{0}{1}\log\frac{0}{1}+\frac{1}{1}\log\frac{1}{1}))]\\ &=0.0728\\ Gain(D^{纹理=稍糊},敲声)&=0.7219-[\frac{2}{3}\times Entropy(敲声=浊响)+\frac{3}{5}\times Entropy(敲声=沉闷)]\\ &=0.7219-[\frac{2}{5}\times(-(\frac{1}{2}\log\frac{1}{2}+\frac{1}{2}\log\frac{1}{2}))+\frac{3}{5}\times(-(\frac{0}{3}\log\frac{0}{3}+\frac{3}{3}\log\frac{3}{3}))]\\ &=0.3219\\ Gain(D^{纹理=稍糊},脐部)&=0.7219-[\frac{3}{5}\times Entropy(脐部=稍凹)+\frac{2}{5}\times Entropy(脐部=凹陷)]\\ &=0.7219-[\frac{3}{5}\times(-(\frac{1}{3}\log\frac{1}{3}+\frac{2}{3}\log\frac{2}{3}))+\frac{2}{5}\times(-(\frac{0}{2}\log\frac{0}{2}+\frac{2}{2}\log\frac{2}{2}))]\\ &=0.1709\\ Gain(D^{纹理=稍糊},触感)&=0.7219-[\frac{1}{5}\times Entropy(触感=软粘)+\frac{4}{5}\times Entropy(触感=硬滑)]\\ &=0.7219-[\frac{1}{5}\times(-(\frac{1}{1}\log\frac{1}{1}+\frac{0}{1}\log\frac{0}{1}))+\frac{4}{5}\times(-(\frac{0}{4}\log\frac{0}{4}+\frac{4}{4}\log\frac{4}{4}))]\\ &=0.7219\\ \end{aligned}$
"触感"属性的信息增益达到最大，选择"触感"属性继续分裂。

表4 西瓜数据集——纹理=模糊

编号	色泽	根蒂	敲声	纹理	脐部	触感	好瓜
11	浅白	硬挺	清脆	模糊	平坦	硬滑	否
12	浅白	蜷缩	浊响	模糊	平坦	软粘	否
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	否

当前节点包含的样本全属于同一类别，即差瓜，因此无需再分。

相关文章：