【机器学习 ｜西瓜书 】

西瓜书 】"/>

【机器学习 ｜西瓜书 】

从逻辑角度，一堆if else 语句的组合

从几何角度，根据某种准则划分特征空间

最终目的：将样本越分越“纯”

1 划分选择

决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。

1.1 信息增益

自信息：
I ( x ) = − log ⁡ b p ( x ) I(x)=-\log_{b}{p(x)} I(x)=−logb​p(x)
信息熵（自信息的期望）：度量随机变量 X 的不确定性，信息熵越大越不确定。
H ( x ) = E [ I ( x ) ] = − ∑ x p ( x ) log ⁡ b p ( x ) （此处以离散型为例） H(x) = E\left [ I(x) \right ] = -\sum_{x}^{}p(x)\log_{b}{p(x)} （此处以离散型为例） H(x)=E[I(x)]=−x∑​p(x)logb​p(x)（此处以离散型为例）
计算信息熵时约定：若 p ( x ) = 0 p(x)=0 p(x)=0 ，则 p ( x ) log ⁡ b p ( x ) = 0 p(x)\log_{b}{p(x)} = 0 p(x)logb​p(x)=0 ，则 X 的某个取值的概率为 1 时信息熵最小（最确定），其数值为 0. 当信息熵值为 log ⁡ b ∣ X ∣ \log_b|X| logb​∣X∣ ，信息熵数值最大，最不确定，其中|X| 表示 X 可能取值的个数。

import pandas as pd
import numpy as np
from math import log
data=pd.read_csv(r"C:\Users\DELL\Desktop\西瓜数据集.csv")
data.head()色泽	根蒂	敲声	纹理	脐部	触感	target
0	青绿	蜷缩	浊响	清晰	凹陷	硬滑	是
1	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	是
2	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	是
3	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	是
4	浅白	蜷缩	浊响	清晰	凹陷	硬滑	是

def calShanEnt(dataset,col):tarset=set(dataset[col])res=0for i in tarset:pi=np.sum(dataset[col] == i)/len(dataset)res=res-pi* log(pi, 2)return resdef ID3(dataset,fea):baseEnt = calShanEnt(dataset, "target")newEnt = 0value_set=set(dataset[fea])for v in value_set:newEnt += np.sum(dataset[fea] == v) / len(dataset) * calShanEnt(dataset[dataset[fea] == v],"target")return baseEnt-newEnt
ID3(data,"根蒂")

0.14267495956679288

可以看到，在给定西瓜"根蒂"条件的基础上，信息增益为0.142

使用信息增益进行分裂时我们的特征选择方法是：对训练集(或者子集)D,计算其每个特征的信息增益，并且比较大小，选择信息增益最大的特征。

方法也是很直接，既然给定每个特征都可以得到一个新增增益，那哪个特征的信息增益大，我们选择哪个特征不就好了？于是：

def chooseBestFea(dataset):features=[i for i in dataset.columns if i!='target']bestFet=features[0]bestInfoGain=-1for fea in features:gain=ID3(dataset,fea)if gain>bestInfoGain:bestInfoGain=gainbestFet=feaprint(set(dataset[bestFet]))print(bestInfoGain)return bestFet

chooseBestFea(data)#输出
{'清晰', '模糊', '稍糊'}
0.3805918973682686
'纹理'

可以看到，选择"纹理"进行分裂信息增益最大(0.38059189736826)。因此我们可以根据特征"纹理"将整个样本集分为三份,分别是"纹理=模糊"，“纹理=清晰”，“纹理=稍糊”.

1.2 增益率

请看 C4.5 决策树

2. ID3 决策树

将样本类别标记y 视作随机变量，各个类别再样本集合 D 中的占比 (k=1,2,…)视为各个类别取值的概率，则样本集合 D（随机变量y）的信息熵（底数b取 2）为
E n t ( D ) = − ∑ k = 1 ∣ y ∣ p k log ⁡ 2 p k Ent(D) = -\sum_{k=1}^{|y|}p_k\log_{2}p_k Ent(D)=−k=1∑∣y∣​pk​log2​pk​
此时的信息熵所代表的是“不确定性”可以转换理解为集合内样本的“纯度”。

条件熵（Y 的信息熵关于概率分布 X 的期望）：在已知 X 后 Y 的不确定性
H ( Y ∣ X ) = ∑ x p ( x ) H ( Y ∣ X = x ) H(Y|X)=\sum_{x}^{} p(x)H(Y|X=x) H(Y∣X)=x∑​p(x)H(Y∣X=x)
信息增益：在已知属性 (特征) a a a 的取值后 y y y 的不确定性减少的量, 也即纯度的提升
Gain ⁡ ( D , a ) = Ent ⁡ ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ Ent ⁡ ( D v ) \operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^V \frac{\left|D^v\right|}{|D|} \operatorname{Ent}\left(D^v\right) Gain(D,a)=Ent(D)−v=1∑V​∣D∣∣Dv∣​Ent(Dv)

一般前者数值比较大，后者数值比较小。
ID3决策树：以信息增益为准则来选择划分属性的决策树
a ∗ = arg ⁡ max ⁡ a ∈ A Gain ⁡ ( D , a ) a_*=\underset{a \in A}{\arg \max } \operatorname{Gain}(D, a) a∗​=a∈Aargmax​Gain(D,a)

3. C4.5 决策树

信息增益准则对可能取值数目较多的属性有所偏好（例如“编号”这个较为极端的例子，不过其本质原因不是取值数目过多，而是每个取值里面所包含的样本量太少），为减少这种偏好可能带来的不利影响，C4.5决策树选择使用“增益率”代替“信息增益”，增益率定义为
Gain_ratio ⁡ ( D , a ) = Gain ⁡ ( D , a ) IV ⁡ ( a ) \operatorname{Gain\_ ratio}(D, a)=\frac{\operatorname{Gain}(D, a)}{\operatorname{IV}(a)} Gain_ratio(D,a)=IV(a)Gain(D,a)​

其中
IV ⁡ ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ log ⁡ 2 ∣ D v ∣ ∣ D ∣ \operatorname{IV}(a)=-\sum_{v=1}^V \frac{\left|D^v\right|}{|D|} \log _2 \frac{\left|D^v\right|}{|D|} IV(a)=−v=1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​
称为属性 a a a 的“固有值”, a a a 的可能取值个数 V V V 越大, 通常其固有值 IV ⁡ ( a ) \operatorname{IV}(a) IV(a) 也越大。但是,增益率对可能取值数目较少的属性有所偏好。
属性a的可能取值数目越多(即V越大),则IV(a)的值通常越大。

def C4_5(dataset,fea):gain=ID3(dataset,fea)IVa=calShanEnt(dataset,fea)return gain/IVa
C4_5(data,"纹理")>>> 0.2630853587192754

若我们直接选取增益率最大的候选划分属性，则有:

def chooseBestFea(dataset):features=[i for i in dataset.columns if i!='target']bestFet=features[0]bestInfoGain=-1for fea in features:gain=C4_5(dataset,fea)if gain>bestInfoGain:bestInfoGain=gainbestFet=feaprint(set(dataset[bestFet]))print(bestInfoGain)return bestFet
chooseBestFea(data)>>>{'稍糊', '清晰', '模糊'}
>>>0.2630853587192754
>>>'纹理'

因此 C4.5 决策树并未完全使用“增益率”代替“信息增益”，而是采用一种启发式的方法：先选出信息增益高于平均水平的属性，然后再从中选择增益率最高的。

4. CART 决策树

基尼值：从样本集合 D D D 中随机抽取两个样本, 其类别标记不一致的概率。因此, 基尼值越小，碰到异类的概率就越小，纯度自然就越高。
Gini ⁡ ( D ) = ∑ k = 1 ∣ Y ∣ ∑ k ′ ≠ k p k p k ′ = ∑ k = 1 ∣ Y ∣ p k ( 1 − p k ) = 1 − ∑ k = 1 ∣ Y ∣ p k 2 \begin{aligned} \operatorname{Gini}(D) & =\sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{\prime} \neq k} p_k p_{k^{\prime}} \\ & =\sum_{k=1}^{|\mathcal{Y}|} p_k\left(1-p_k\right) \\ & =1-\sum_{k=1}^{|\mathcal{Y}|} p_k^2 \end{aligned} Gini(D)​=k=1∑∣Y∣​k′=k∑​pk​pk′​=k=1∑∣Y∣​pk​(1−pk​)=1−k=1∑∣Y∣​pk2​​
属性 a a a 的基尼指数（类比信息熵和条件熵）：
Gini ⁡ _ index ⁡ ( D , a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ Gini ⁡ ( D v ) \operatorname{Gini} \_\operatorname{index}(D, a)=\sum_{v=1}^V \frac{\left|D^v\right|}{|D|} \operatorname{Gini}\left(D^v\right) Gini_index(D,a)=v=1∑V​∣D∣∣Dv∣​Gini(Dv)

CART决策树：选择基尼指数最小的属性作为最优划分属性
a ∗ = arg ⁡ min ⁡ a ∈ A Gini ⁡ _ index  ( D , a ) a_*=\underset{a \in A}{\arg \min } \operatorname{Gini} \_ \text {index }(D, a) a∗​=a∈Aargmin​Gini_index (D,a)

CART决策树的实际构造算法如下:

• 首先, 对每个属性 a a a 的每个可能取值 v v v, 将数据集 D D D 分为 a = v a=v a=v 和 a ≠ v a \neq v a=v 两部分来计算基尼指数, 即
  Gini ⁡ _ index ⁡ ( D , a ) = ∣ D a = v ∣ ∣ D ∣ Gini ⁡ ( D a = v ) + ∣ D a ≠ v ∣ ∣ D ∣ Gini ⁡ ( D a ≠ v ) \operatorname{Gini} \_\operatorname{index}(D, a)=\frac{\left|D^{a=v}\right|}{|D|} \operatorname{Gini}\left(D^{a=v}\right)+\frac{\left|D^{a \neq v}\right|}{|D|} \operatorname{Gini}\left(D^{a \neq v}\right) Gini_index(D,a)=∣D∣∣Da=v∣​Gini(Da=v)+∣D∣ ​Da=v ​​Gini(Da=v)
• 然后, 选择基尼指数最小的属性及其对应取值作为最优划分属性和最优划分点;
• 最后, 重复以上两步, 直至满足停止条件。

def Gini(dataset,col):tarset = set(dataset[col])gini=1for i in tarset:gini=gini-(np.sum(dataset[col] == i)/len(dataset))**2return gini
Gini(data,"target")>>> 0.49826989619377154

def CART(dataset,fea):value_set=set(dataset[fea])gini = 0for v in value_set:gini += np.sum(dataset[fea] == v) / len(dataset) * Gini(dataset[dataset[fea] == v],"target")return gini
CART(data,"纹理")>>> 0.2771241830065359

def chooseBestFea(dataset):features=[i for i in dataset.columns if i!='target']bestFet=features[0]bestInfoGain=1000for fea in features:gain=CART(dataset,fea)if gain<bestInfoGain:bestInfoGain=gainbestFet=feaprint(set(dataset[bestFet]))print(bestInfoGain)return bestFet
chooseBestFea(data)>>> {'清晰', '模糊', '稍糊'}
>>> 0.2771241830065359
>>> '纹理'

5 剪枝处理

剪枝是决策树学习算法对付“过拟合”的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得“太好”了，以至于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此可以通过主动去掉一些分支来降低过拟合的风险。
    决策树剪枝的基本策略有“预剪枝”和“后剪枝”。预剪枝是指在决策树生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
    我们从西瓜数据集2.0中取一部分作为训练集采用信息增益准则来进行划分属性选择，即可生成如下的决策树

5.1 预剪枝

基于信息增益准则，我们会选取属性“脐部”来对训练集进行划分，并产生3个分支，如下图所示。是否应该进行这个划分呢？预剪枝要对划分前后的泛化性能进行估计。

在划分之前，所有样例集中在根结点。若不进行划分。则该结点被标记为叶结点，其类别标记为训练样例数最多的类别，假设我们将这个叶结点标记为“好瓜”。用验证集对这个单结点决策树进行评估，则编号为{4,5,8}的样例被分类正确，另外4个样例分类错误，于是，验证集精度为3/4×100%=42.9%.
    在用属性“脐部”划分之后，上图结点圈2、圈3、圈4分别包含编号为{1,2,3,14}、{6,7,15,17}、{10,16}的训练样例，因此这3个结点分别被标记为叶结点“好瓜”、“好瓜”、“坏瓜”。此时，验证集中编号为{4,5,8,11,12}的样例被分类正确，验证集精度为5/7×100%=71.4%>42.9%.于是“脐部”进行划分得以确定。
    然后，决策树算法应该对结点圈2进行划分，基于信息增益准则将挑选出划分属性“色泽”。然而，在使用“色泽”划分后，编号为{5}的验证集样本分类结果会由正确转为错误，使得验证集精度下降为57.1%。于是预剪枝策略将禁止结点圈2被划分。
    对结点圈3，最优划分属性为“根蒂”，划分后验证集精度仍为71.4%。这个划分不能提高验证集精度，于是，预剪枝策略禁止结点圈3被划分。
    对结点圈4，其所含训练样例已属于同一类，不再进行划分。
    于是，基于预剪枝策略得到上图的决策树，其验证集精度为71.4%。这是一颗仅有一层划分的决策树，亦称“决策树桩”。
    可以观察到预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

5.2 后剪枝

后剪枝先从训练集生成如下的完整决策树，该决策树的验证集精度为42.9%。

后剪枝首先考虑上图的结点圈6。若将其领衔的分支剪除，则相当于把圈6替换为叶结点。替换后的叶结点包含编号为{7,15}的训练样本，于是，该叶结点的类别标记为“好瓜”，此时决策树的验证集精度提高至57.1%。于是，后剪枝策略决定剪枝。
    然后考虑结点圈5，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号为{6,7,15}的训练样例，叶结点类别标记为“好瓜”，此时决策树验证集精度仍为57.1%。于是，可以不进行剪枝。
    对于结点圈2，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号为{1,2,3,14}的训练样例，叶结点标记为“好瓜”。此时决策树的验证集精度提高至71.4%。于是，后剪枝策略决定剪枝。
    对结点圈3和圈1，若将其领衔的子树替换为叶结点，则所得决策树的验证集精度分别为71.4%与42.9%，均未得到提高，于是它们被保留。
    最终基于后剪枝策略生成的决策树如下图所示，其验证集精度为71.4%。
后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情况下，侯建志决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

6. 连续与缺失值

6.1 连续值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失。
    我们需解决两个问题：(1)如何在属性值缺失的情况下进行划分属性选择？(2)给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
    给定样本集 D 和连续属性 a,假定 a在 D 上出现了 n 个不同的取值,将这些值从小到大进行排序,记为 {a1,a2,…,an}.基于划分点 t 可将 D 分为子集 D t + D_t^+ Dt+​，和 D t − D_t^- Dt−​，其中 D t − D_t^- Dt−​，包含那些在属性a上取值不大于 t 的样本,而 D t + D_t^+ Dt+​ 则包含那些在属性a 上取值大于 t 的样本。显然，对相邻的属性取值 a i a^i ai与 a i + 1 a^{i+1} ai+1 来说,t在区间 [ a i , a i + 1 ) [a^i,a^{i+1}) [ai,ai+1)中取任意值所产生的划分结果相同，因此，对连续属性a,我们可考察包含 n-1 个元素的候选划分集合。
     T a = { a i + a i + 1 2 ∣ 1 ⩽ i ⩽ n − 1 } , T_a=\left\{\frac{a^i+a^{i+1}}{2} \mid 1 \leqslant i \leqslant n-1\right\}, Ta​={2ai+ai+1​∣1⩽i⩽n−1},

即把区间 [ a i , a i + 1 ) \left[a^i, a^{i+1}\right) [ai,ai+1) 的中位点 a i + a i + 1 2 \frac{a^i+a^{i+1}}{2} 2ai+ai+1​ 作为候选划分点. 然后, 我们就可像离散属性值一样来考察这些划分点, 选取最优的划分点进行样本集合的划分. 例如,可对式(4.2)稍加改造:
Gain ⁡ ( D , a ) = max ⁡ t ∈ T a Gain ⁡ ( D , a , t ) = max ⁡ t ∈ T a Ent ⁡ ( D ) − ∑ λ ∈ { − , + } ∣ D t λ ∣ ∣ D ∣ Ent ⁡ ( D t λ ) , \begin{aligned} \operatorname{Gain}(D, a) & =\max _{t \in T_a} \operatorname{Gain}(D, a, t) \\ & =\max _{t \in T_a} \operatorname{Ent}(D)-\sum_{\lambda \in\{-,+\}} \frac{\left|D_t^\lambda\right|}{|D|} \operatorname{Ent}\left(D_t^\lambda\right), \end{aligned} Gain(D,a)​=t∈Ta​max​Gain(D,a,t)=t∈Ta​max​Ent(D)−λ∈{−,+}∑​∣D∣ ​Dtλ​ ​​Ent(Dtλ​),​

其中 Gain ⁡ ( D , a , t ) \operatorname{Gain}(D, a, t) Gain(D,a,t) 是样本集 D D D 基于划分点 t t t 二分后的信息增益. 于是, 我们就可选择使 Gain ⁡ ( D , a , t ) \operatorname{Gain}(D, a, t) Gain(D,a,t) 最大化的划分点.

6.2 缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失。
    我们需解决两个问题：(1)如何在属性值缺失的情况下进行划分属性选择？(2)给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
    给定训练集 D D D 和属性 a a a, 令 D ~ \tilde{D} D~ 表示 D D D 中在属性 a a a 上没有缺失值的样本子集. 对问题(1), 显然我们仅可根据 D ~ \tilde{D} D~ 来判断属性 a a a 的优劣. 假定属性 a a a 有 V V V 个可取值 { a 1 , a 2 , … , a V } \left\{a^1, a^2, \ldots, a^V\right\} {a1,a2,…,aV}, 令 D ~ v \tilde{D}^v D~v 表示 D ~ \tilde{D} D~ 中在属性 a a a 上取值为 a v a^v av 的样本子集, D ~ k \tilde{D}_k D~k​表示 D ~ \tilde{D} D~ 中属于第 k k k 类 ( k = 1 , 2 , … , ∣ Y ∣ ) (k=1,2, \ldots,|\mathcal{Y}|) (k=1,2,…,∣Y∣) 的样本子集, 则显然有 D ~ = ⋃ k = 1 ∣ Y ∣ D ~ k \tilde{D}=\bigcup_{k=1}^{|\mathcal{Y}|} \tilde{D}_k D~=⋃k=1∣Y∣​D~k​, D ~ = ⋃ v = 1 V D ~ v \tilde{D}=\bigcup_{v=1}^V \tilde{D}^v D~=⋃v=1V​D~v. 假定我们为每个样本 x \boldsymbol{x} x 赋予一个权重 w x w_{\boldsymbol{x}} wx​, 并定义
ρ = ∑ x ∈ D ~ w x ∑ x ∈ D w x , p ~ k = ∑ x ∈ D ~ k w x ∑ x ∈ D ~ w x ( 1 ⩽ k ⩽ ∣ Y ∣ ) , r ~ v = ∑ x ∈ D ~ v w x ∑ x ∈ D ~ w x ( 1 ⩽ v ⩽ V ) . \begin{aligned} \rho & =\frac{\sum_{\boldsymbol{x} \in \tilde{D}} w_{\boldsymbol{x}}}{\sum_{\boldsymbol{x} \in D} w_{\boldsymbol{x}}}, \\ \tilde{p}_k & =\frac{\sum_{\boldsymbol{x} \in \tilde{D}_k} w_{\boldsymbol{x}}}{\sum_{\boldsymbol{x} \in \tilde{D}} w_{\boldsymbol{x}}} \quad(1 \leqslant k \leqslant|\mathcal{Y}|), \\ \tilde{r}_v & =\frac{\sum_{\boldsymbol{x} \in \tilde{D}^v} w_{\boldsymbol{x}}}{\sum_{\boldsymbol{x} \in \tilde{D}} w_{\boldsymbol{x}}} \quad(1 \leqslant v \leqslant V) . \end{aligned} ρp~​k​r~v​​=∑x∈D​wx​∑x∈D~​wx​​,=∑x∈D~​wx​∑x∈D~k​​wx​​(1⩽k⩽∣Y∣),=∑x∈D~​wx​∑x∈D~v​wx​​(1⩽v⩽V).​

直观地看, 对属性 a , ρ a, \rho a,ρ 表示无缺失值样本所占的比例, p ~ k \tilde{p}_k p~​k​ 表示无缺失值样本中第 k k k 类所占的比例, r ~ v \tilde{r}_v r~v​ 则表示无缺失值样本中在属性 a a a 上取值 a v a^v av 的样本所占的比例. 显然, ∑ k = 1 ∣ Y ∣ p ~ k = 1 , ∑ v = 1 V r ~ v = 1 \sum_{k=1}^{|\mathcal{Y}|} \tilde{p}_k=1, \sum_{v=1}^V \tilde{r}_v=1 ∑k=1∣Y∣​p~​k​=1,∑v=1V​r~v​=1.
基于上述定义, 我们可将信息增益的计算式(4.2)推广为
Gain ⁡ ( D , a ) = ρ × Gain ⁡ ( D ~ , a ) = ρ × ( Ent ⁡ ( D ~ ) − ∑ v = 1 V r ~ v Ent ⁡ ( D ~ v ) ) , \begin{aligned} \operatorname{Gain}(D, a) & =\rho \times \operatorname{Gain}(\tilde{D}, a) \\ & =\rho \times\left(\operatorname{Ent}(\tilde{D})-\sum_{v=1}^V \tilde{r}_v \operatorname{Ent}\left(\tilde{D}^v\right)\right), \end{aligned} Gain(D,a)​=ρ×Gain(D~,a)=ρ×(Ent(D~)−v=1∑V​r~v​Ent(D~v)),​

其中由式(4.1), 有
Ent ⁡ ( D ~ ) = − ∑ k = 1 ∣ Y ∣ p ~ k log ⁡ 2 p ~ k . \operatorname{Ent}(\tilde{D})=-\sum_{k=1}^{|\mathcal{Y}|} \tilde{p}_k \log _2 \tilde{p}_k . Ent(D~)=−k=1∑∣Y∣​p~​k​log2​p~​k​.

对问题(2), 若样本 x \boldsymbol{x} x 在划分属性 a a a 上的取值已知, 则将 x \boldsymbol{x} x 划入与其取值对应的子结点, 且样本权值在子结点中保持为 w x w_{\boldsymbol{x}} wx​. 若样本 x \boldsymbol{x} x 在划分属性 a a a 上的取值未知, 则将 x \boldsymbol{x} x 同时划入所有子结点, 且样本权值在与属性值 a v a^v av 对应的子结点中调整为 r ~ v ⋅ w x \tilde{r}_v \cdot w_{\boldsymbol{x}} r~v​⋅wx​; 直观地看, 这就是让同一个样本以不同的概率划入到不同的子结点中去.

C4.5 算法使用了上述解决方案 [Quinlan, 1993]. 下面我们以表 4.4 的数据集为例来生成一棵决策树.

7.多变量决策树

若我们把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显的特点:轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。



若能使用斜的划分边界，则决策树模型将大为简化。“多变量决策树”就是能实现这样的“斜划分”甚至更复杂划分的决策树。以实现斜划分的多变量决策树为例，在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试。
若能使用斜的划分边界，如下图中红色线段所示,则决策树模型将大为简化.“多变量决策树”(multivariate decision tree)就是能实现这样的“斜划分”甚至更复杂划分的决策树.以实现斜划分的多变量决策树为例,在此类决策树中,非叶结点不再是仅对某个属性,而是对属性的线性组合进行测试;换言之,每个非叶结点是一个形如 ∑ i = 1 d w i a i = t \sum_{i=1}^{d}w_ia_i = t ∑i=1d​wi​ai​=t 的线性分类器,其中 w i w_i wi​ 是属性 a i a_i ai​ 的权重, w i w_i wi​和 t 可在该结点所含的样本集和属性集上学得.于是,与传统的“单变量决策树”(univariate decision tree)不同,在多变量决策树的学习过程中不是为每个非叶结点寻找一个最优划分属性,而是试图建立一个合适的线性分类器。可以得到以下的多变量决策树。

8 代码实现

1. 三种方法建立

### 使用三种方法建立一个决策树import pandas as pd
from math import log
import numpy as npclass DT:def __init__(self, data, model):self.data = dataself.model = modeldef calShanEnt(self, dataset, col):tarset = set(dataset[col])res = 0for i in tarset:pi = np.sum(dataset[col] == i) / len(dataset)res = res - pi * log(pi, 2)return resdef ID3(self, dataset, fea):baseEnt = self.calShanEnt(dataset, "target")newEnt = 0value_set = set(dataset[fea])for v in value_set:newEnt += np.sum(dataset[fea] == v) / len(dataset) * self.calShanEnt(dataset[dataset[fea] == v], "target")return baseEnt - newEntdef C4_5(self, dataset, fea):gain = self.ID3(dataset, fea)IVa = self.calShanEnt(dataset, fea)return gain / IVadef Gini(self, dataset, col):tarset = set(dataset[col])gini = 1for i in tarset:gini = gini - (np.sum(dataset[col] == i) / len(dataset)) ** 2return ginidef CART(self, dataset, fea):value_set = set(dataset[fea])Gini_min = 100fea_min = ""for v in value_set:Gini_index = np.sum(dataset[fea] == v) / len(dataset) * self.Gini(dataset[dataset[fea] == v], "target") + \np.sum(dataset[fea] != v) / len(dataset) * self.Gini(dataset[dataset[fea] != v], "target")if Gini_index < Gini_min:  # 越小越好Gini_min = Gini_indexfea_min = vreturn -Gini_min, fea_min  ##由于另外连个方法都是最大的值进行分裂，而Gini指数是最小，因此取负数，这样-Gini_min越大越好def chooseBestFea(self, dataset):features = [i for i in dataset.columns if i != 'target']bestFet = features[0]bestFetFea = ""bestInfoGain = -1value_fea = ""for fea in features:if self.model == "C4_5":gain = self.C4_5(dataset, fea)elif self.model == "ID3":gain = self.ID3(dataset, fea)elif self.model == "CART":gain, value_fea = self.CART(dataset, fea)else:raise ("输入的model值之只能是：C4_5,ID3,CART,但是实际输入的值为：", self.model)if gain > bestInfoGain:bestInfoGain = gainbestFet = feabestFetFea = value_feareturn bestFet, bestFetFeadef creatTree(self, dataset):if len(dataset.columns) == 1:return dataset['target'].value_counts().index[0]if len(set(dataset['target'])) == 1:return list(dataset['target'])[0]bestFea, bestFetFea = self.chooseBestFea(dataset)myTree = {bestFea: {}}if bestFetFea == "":for i in set(dataset[bestFea]):new_data = dataset[dataset[bestFea] == i].reset_index(drop=True) # drop=True 就是把原来的索引index列去掉，重置indexmyTree[bestFea][i] = self.creatTree(new_data)else:new_data = dataset[dataset[bestFea] == bestFetFea].reset_index(drop=True)myTree[bestFea][bestFetFea] = self.creatTree(new_data)new_data2 = dataset[dataset[bestFea] != bestFetFea].reset_index(drop=True)myTree[bestFea]["不等于" + bestFetFea] = self.creatTree(new_data2)return myTree
data_path=r"C:\Users\DELL\Desktop"
data = pd.read_csv(r"C:\Users\DELL\Desktop\西瓜数据集.csv")    
model = DT(data, "CART")
tree=model.creatTree(data)

{'纹理': {'清晰': {'触感': {'软粘': {'色泽': {'乌黑': '否','不等于乌黑': {'根蒂': {'稍蜷': '是', '不等于稍蜷': '否'}}}},'不等于软粘': '是'}},'不等于清晰': {'色泽': {'乌黑': {'敲声': {'沉闷': '否', '不等于沉闷': '是'}}, '不等于乌黑': '否'}}}}

2. 鸢尾花（iris）数据集sklearn决策树

# 加载数据集
data = load_iris() 
# 转换成.DataFrame形式
df = pd.DataFrame(data.data, columns = data.feature_names)
# 添加品种列
df['Species'] = data.target# 用数值替代品种名作为标签
target = np.unique(data.target)
target_names = np.unique(data.target_names)
targets = dict(zip(target, target_names))
df['Species'] = df['Species'].replace(targets)# 提取数据和标签
X = df.drop(columns="Species")
y = df["Species"]
feature_names = X.columns
labels = y.unique()X_train, test_x, y_train, test_lab = train_test_split(X,y,test_size = 0.4,random_state = 42)
model = DecisionTreeClassifier(max_depth =3, random_state = 42)
model.fit(X_train, y_train) 
# 以文字形式输出树     
text_representation = tree.export_text(model)
print(text_representation)
# 用图片画出
plt.figure(figsize=(30,10), facecolor ='g') #
a = tree.plot_tree(model,feature_names = feature_names,class_names = labels,rounded = True,filled = True,fontsize=14)
plt.show()