第五节--决策树_预测变量空间划分怎么对应树-程序员宅基地

技术标签: ML  

第五节–决策树

决策树(decision tree)是一种基本的分类与回归方法.决策树呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程,它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布,其主要优点是模型具有可读性,分类速度快.决策树学习通常包括3个步骤:特征选择,决策树的生成决策树的修剪

一.决策树模型与学习

1.决策树模型

分类决策树是一种描述对实例进行分类的树形结构.决策树由结点(node)和有向边(directed edge)组成.结点有三种类型:根结点(root node),内部结点(internal node)和叶结点(leaf node).内部结点表示一个特征或属性,叶结点表示一个类

用决策树分类,从根结点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子结点;这时每一个子结点对应着该特征的一个取值.如此递归地对实例进行测试并分配,直至达到叶结点,最后将实例分到叶结点的类中

下图是一个决策树的示意图

from IPython.display import Image
Image(filename="./data/5_1.png",width=500)

在这里插入图片描述

2.决策树与if-then规则

可以将决策树看成一个if-then规则的集合.将决策树转换成if-then规则的过程是这样的:由决策树的根结点到叶结点的每一条路径构建一条规则;路径上内部结点的特征对应着规则的条件,而叶结点的类对应着规则的结论.决策树的路径或其对应的if-then规则集合具有一个重要的性质;互斥并且完备.这就是说,每一个实例都被一条路径或一条规则所覆盖,而且只被一条路径或一条规则所覆盖.这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件

3.决策树与条件概率分布

决策树还表示给定特征条件下类的条件概率分布,这一条件概率分布定义在特征空间的一个划分(partition)上.将特征空间划分为互不相交的单元(cell)或区域(region),并在每个单元定义一个类的概率分布就构成了一个条件概率分布.决策树一条路径对应于划分中的一个单元.决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成.假设X为表示通知的随机变量,Y为表示类的随机变量,那么这个条件概率分布可以表示为 P ( Y ∣ X ) P(Y | X) P(YX).X取值于给定划分下单元的集合,Y取值于类的集合.各叶结点(单元)上的条件概率往往偏向某一个类,即属于某一类的概率较大.决策树分类时将该结点的实例强行分到条件概率大的那一类去

Image(filename="./data/5_3.png",width=500)

在这里插入图片描述

图a示意地表示了特征空间的一个划分.图中的大正方形表示特征空间.这个大正方形被若干个小矩形分割,每个小矩形表示一个单元.特征空间划分上的单元构成了一个集合,X取值为单元的集合.为简单起见,假设只有两类:正类和负类,即Y取值为+1和-1.小矩形中的数字表示单元的类.图b示意地表示特征空间划分确定时,特征(单元)给定条件下类的条件概率分布.图b中条件概率分布对应于图a的划分.当某个单元c的条件概率满足 P ( Y = + 1 ∣ X = c ) > 0.5 P(Y=+1 | X=c)>0.5 P(Y=+1X=c)>0.5时,则认为这个单元属于正类,即落在这个单元的实例都被视为正例.图c为对应于图b中条件概率分布的决策树

4.决策树学习

决策树学习,假设给定训练数据集:
D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\} D={ (x1,y1),(x2,y2),,(xN,yN)}

其中, x i = ( x i ( 1 ) , x i ( 2 ) , ⋯   , x i ( n ) ) T x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(n)}\right)^{\mathrm{T}} xi=(xi(1),xi(2),,xi(n))T为输入实例(特征向量),n为特征个数, y i ∈ { 1 , 2 , ⋯   , K } y_{i} \in\{1,2, \cdots, K\} yi{ 1,2,,K}为类标记, i = 1 , 2 , ⋯   , N i=1,2, \cdots, N i=1,2,,N,N为样本容量.学习的目标是根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类

决策树学习本质上是从训练数据集中归纳出一组分类规则.与训练数据集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个,也可能一个也没有.我们需要的是一个与训练数据矛盾较小的决策树.同属具有很好的泛化能力.从另一个角度看,决策树学习是由训练数据集估计条件概率模型.基于特征空间划分的类的条件概率模型有无穷多个.我们选择的条件概率模型应该不仅对训练数据有很好的拟合,而且对未知数据有很好的预测

二.条件选择

1.特征选择问题

特征选择在于选取对训练数据具有分类能力的特征.这样可以提高决策树学习的效率.如果利用一个特征进行分类的结果与随机分类的结果没有很大差别.则称这个特征是没有分类的能力的.经验上扔掉这样的特征对决策树学习的精度影响不大,通常特征选择的准则是信息增益信息增益比

首先通过一个例子来说明特征选择问题

ID 年龄 有工作 有自己的房子 信贷情况 类别
1 青年 一般
2 青年
3 青年
4 青年 一般
5 青年 一般
6 中年 一般
7 中年
8 中年
9 中年 非常好
10 中年 非常好
11 老年 非常好
12 老年
13 老年
14 老年 非常好
15 老年 一般

希望通过所给的训练数据学习一个贷款申请的决策树,用以对未来的贷款申请进行分类,即当新的客户提出贷款申请时,根据申请人的特征利用决策树决定是否批准贷款申请

from IPython.display import Image
Image(filename="./data/5_4.png",width=500)

在这里插入图片描述

两个决策树都可以从此延续下去,问题是:究竟选择哪个特征更好些?这就要求确定选择特征的准则.直观上,如果一个特征具有更好的分类能力,或者说按照这一特征将训练数据集分割成子集,使得各个子集在当前条件下有最好的分类,那么就更应该选择这个特征.信息增益(information gain)就能够很好地表示这一直观的准则

2.信息增益

在信息论与概率统计中,熵(entropy)是表示随机变量不确定性的度量.设X是一个取有限个值的离散随机度量,其概率分布为:
P ( X = x i ) = p i , i = 1 , 2 , ⋯   , n P\left(X=x_{i}\right)=p_{i}, \quad i=1,2, \cdots, n P(X=xi)=pi,i=1,2,,n

则随机变量X的熵定义为:
H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X)=-\sum_{i=1}^{n} p_{i} \log p_{i} H(X)=i=1npilogpi

p i = 0 p_{\mathrm{i}}=0 pi=0,则定义 0 log ⁡ 0 = 0 0 \log 0=0 0log0=0.通常对数以2为底数或以e为底(自然对数),这时熵的单位分布称作比特(bit).由定义可知,熵只依赖X的分布.而与X的取值无关,所以也可将X的熵记作 H ( p ) H(p) H(p),即:
H ( p ) = − ∑ i = 1 n p i log ⁡ p i H(p)=-\sum_{i=1}^{n} p_{i} \log p_{i} H(p)=i=1npilogpi

熵越大,随机变量的不确定性就越高.从定义可验证:
0 ⩽ H ( p ) ⩽ log ⁡ n 0 \leqslant H(p) \leqslant \log n 0H(p)logn

当随机变量只取两个值,例如1,0时,即X的分布为:
P ( X = 1 ) = p , P ( X = 0 ) = 1 − p , 0 ⩽ p ⩽ 1 P(X=1)=p, \quad P(X=0)=1-p, \quad 0 \leqslant p \leqslant 1 P(X=1)=p,P(X=0)=1p,0p1

熵为:
H ( p ) = − p log ⁡ 2 p − ( 1 − p ) log ⁡ 2 ( 1 − p ) H(p)=-p \log _{2} p-(1-p) \log _{2}(1-p) H(p)=plog2p(1p)log2(1p)

这时,熵 H ( p ) H(p) H(p)随概率p变化的曲线如下图(单位为比特):

Image(filename="./data/5_5.png",width=500)

在这里插入图片描述

当p=0或p=1时 H ( p ) = 0 H(p)=0 H(p)=0,随机变量完全没有不确定性.当p=0.5时, H ( p ) = 1 H(p)=1 H(p)=1,熵取值最大,随机变量不确定性最大

设有随机变量 ( X , Y ) (X, Y) (X,Y),其联合概率分布为:
P ( X = x i , Y = y j ) = p i j , i = 1 , 2 , ⋯   , n ; j = 1 , 2 , ⋯   , m P\left(X=x_{i}, Y=y_{j}\right)=p_{i j}, \quad i=1,2, \cdots, n ; j=1,2, \cdots, m P(X=xi,Y=yj)=pij,i=1,2,,n;j=1,2,,m

条件熵 H ( Y ∣ X ) H(Y | X) H(YX)表示在已知随机变量X的条件下随机变量Y的不确定性.随机变量 X X X给定的条件下随机变量 Y Y Y的条件熵(conditional entropy) H ( Y ∣ X ) H(Y | X) H(YX).定义为 X X X给定条件下Y的条件概率分布的熵对 X X X的数学期望:
H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) H(Y | X)=\sum_{i=1}^{n} p_{i} H\left(Y | X=x_{i}\right) H(YX)=i=1npiH(YX=xi)

这里, p i = P ( X = x i ) , i = 1 , 2 , ⋯   , n p_{i}=P\left(X=x_{i}\right), \quad i=1,2, \cdots, n pi=P(X=xi),i=1,2,,n

信息增益(information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度

特征A对训练数据集D的信息增益 g ( D , A ) g(D, A) g(D,A),定义为集合D的经验熵 H ( D ) H(D) H(D)与特征A给定条件下D的经验条件熵 H ( D ∣ A ) H(D | A) H(DA)之差,即:
g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D, A)=H(D)-H(D | A) g(D,A)=H(D)H(DA)

一般地,熵 H ( Y ) H(Y) H(Y)与条件熵 H ( Y ∣ X ) H(Y | X) H(YX)之差称为互信息(mutual information).决策树学习中的信息增益等价于训练数据集中类与特征的互信息

根据信息增益准则的特征选择方法是:对训练数据集(或子集)D,计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征

设训练数据集为D,|D|表示其样本容量,即样本个数.设有K个类 C k C_{k} Ck,k= 1 , 2 , ⋯   , K 1,2, \cdots, K 1,2,,K, ∣ C k ∣ \left|C_{k}\right| Ck为属于类 C k C_{k} Ck的样本个数, ∑ k = 1 K ∣ C k ∣ = ∣ D ∣ \sum_{k=1}^{K}\left|C_{k}\right|=|D| k=1KCk=D.设特征A有n个不同的取值 { a 1 , a 2 , ⋯   , a n } \left\{a_{1}, a_{2}, \cdots, a_{n}\right\} { a1,a2,,an},根据特征A的取值将D划分为n个子集 D 1 , D 2 , ⋯   , D n D_{1}, D_{2}, \cdots, D_{n} D1,D2,,Dn, ∣ D t ∣ \left|D_{t}\right| Dt D i D_{i} Di的样本个数, ∑ i = 1 n ∣ D i ∣ = ∣ D ∣ \sum_{i=1}^{n}\left|D_{i}\right|=|D| i=1nDi=D.记子集 D i D_{i} Di中属于类 C k C_{k} Ck的样本的集合为 D i k D_{i k} Dik,即 D l k = D i ∩ C k D_{l k}=D_{i} \cap C_{k} Dlk=DiCk, ∣ D i k ∣ \left|D_{i k}\right| Dik D i k D_{i k} Dik的样本个数,于是信息增益的算法如下:

信息增益的算法
输入:训练数据集D和特征A
输出:特征A对训练数据集D的信息增益 g ( D , A ) g(D, A) g(D,A)

  1. 计算数据集D的经验熵 H ( D ) H(D) H(D)
    H ( D ) = − ∑ k = 1 K ∣ C k ∣ ∣ D ∣ log ⁡ 2 ∣ C k ∣ ∣ D ∣ H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|} H(D)=k=1KDCklog2DCk
  2. 计算特征A对数据集D的经验条件熵 H ( D ∣ A ) H(D | A) H(DA)
    H ( D ∣ A ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ H ( D i ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ ∑ k = 1 K ∣ D i k ∣ ∣ D i ∣ log ⁡ 2 ∣ D i k ∣ ∣ D i ∣ H(D | A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D| } \sum_{k=1}^{K} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} H(DA)=i=1nDDiH(Di)=i=1nDDik=1KDiDiklog2DiDik
  3. 计算信息增益
    g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D, A)=H(D)-H(D | A) g(D,A)=H(D)H(DA)

实例1:对前面贷款所给的训练数据集D,根据信息增益准则选择最优特征

Image(filename="./data/5_6.png",width=500)

在这里插入图片描述

最后,比较各特征的信息增益值,由于特征 A 3 A_{3} A3(有自己的房子)的信息增益值最大,所以选择特征 A 3 A_{3} A3作为最优特征

3.信息增益比

信息增益比的大小是相对于训练数据集而言的,并没有绝对意义.在分类问题困难时,也就是说在训练数据集的经验熵大的时候,信息增益值会偏大,反之,信息增益值会偏小.使用信息增益比(information gain ratio)可以对这一问题进行校正.这是特征选择的另一准则

特征A对训练数据集D的信息增益比 g R ( D , A ) g_{R}(D, A) gR(D,A)定义为其信息增益 g ( D , A ) g(D, A) g(D,A)与训练数据集D的经验熵 H ( D ) H(D) H(D)之比:
g R ( D , A ) = g ( D , A ) H ( D ) g_{R}(D, A)=\frac{g(D, A)}{H(D)} gR(D,A)=H(D)g(D,A)

三.决策树的生成

1.ID3算法

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征,递归地构建决策树.具体方法是:从根结点(root node)开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子结点;再从子结点递归地调用以上方法,构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止.最后得到一个决策树.ID3相当于用极大似然法进行概率模型的选择

ID3算法
输入:训练数据集D,特征集A,阈值 E \mathcal{E} E
输出:决策树T

实例2:对贷款表的训练数据集,利用ID3算法建立决策树

from IPython.display import Image

Image(filename="./data/5_7.png",width=500)

在这里插入图片描述

选择信息增益最大的特征 A 2 A_{2} A2(有工作)作为结点的特征.由于 A 2 A_{2} A2有两个可能取值,从这一结点引出两个子结点:一个对应"是"(有工作)的子结点,包含3个样本,它们属于同一类,所以这是一个叶结点,类标记为"是";另一个是对应"否"(无工作)的子结点,包含6个样本,它们也属于同一类,所以这也是一个叶结点,类标记为"否"

这样生成一个如下图所示的决策树,该决策树只用了两个特征(有两个内部结点):

Image(filename="./data/5_8.png",width=500)

在这里插入图片描述

实例:用ID3对天气数据集样本数据分析,生成决策树

Day Outlook Temperature Humidity Wind Play ball
D1 Sunny Hot High Weak No
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Weak Yes
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong Yes
D13 Overcast Hot Normal Weak Yes
D14 Rain Mild High Strong No
from IPython.display import Image

Image(filename="./data/5_12.png",width=500)

在这里插入图片描述

Outlook属性有三种取值—sunny,overcast和rain,分对应3个分支,将数据集划分为3个子集 S s u n n y S_{sunny} Ssunny, S o v e r c a s t S_{overcast} Sovercast S r a i n S_{rain} Srain

Image(filename="./data/5_13.png",width=500)

在这里插入图片描述

然后,在Sunny分支下,递归调用Decision Tree( S s u n n y S_{sunny} Ssunny,R-outlook,C)分别计算得Temperature属性的信息增益增益度为0.57,Humidity属性的信息增益度为0.97,Wind属性的信息增益度为0.02.因此在此分支下再以属性Humidity对子集 S s u n n y S_{sunny} Ssunny划分,得到子集 S S h i g n SS_{hign} SShign S S n o r m a l SS_{normal} SSnormal,这两个子集的所有样本都属于同一类别,因此停止树的分裂,添加两个叶子节点,并写上子集的类别即可

Image(filename="./data/5_14.png",width=500)

在这里插入图片描述

在生成决策树以后,可以方便地提取决策树描述的知识,并表示成if-then形式的分类规则.沿着根节点到叶子节点每一条路径对应一条决策规则.如IF {Outlook=Sunny,Humidity=High} then {Play ball=No}

在生成决策树的过程中,除了要选择测试属性,还要判断是否停止树的分裂.停止树的分裂的条件如下,只要满足以下3个条件中的一条,即可停止树的分支构造:

  1. 子集中的所有记录属于同一类时
  2. 所有的记录具有相同的属性值
  3. 提前终止树的分裂

ID3采用信息增益度作为评价标准.信息增益度的缺点是倾向于选择取值较多的属性,但在有些情况下这类属性可能不会提供太多有价值的信息.其次ID3算法只能对离散型属性的数据集构造决策树

ID3算法只有树的生成,所以该算法生成的树容易产生过拟合

2.C4.5的生成算法

C4.5算法与ID3算法相似,C4.5算法对ID3算法进行了改进.C4.5在生成的过程中,用信息增益比来选择特征

C4.5对ID3算法进行了以下几方面的改进:

  1. 信息增益率来选择最佳分裂属性,弥补了用信息增益选择属性时偏向选择取值多的属性的不足
  2. 在树构造过程中进行剪枝
  3. 能够完成对连续属性的离散化处理
  4. 能够对不完整数据进行处理

C4.5的生成算法
输入:训练数据集D,特征集A,阀值 E \mathcal{E} E
输出:决策树T

根据信息增益率来选择属性

信息增益率(gain ratio)定义为:
G a i n R a t i o ( X , T ) = Gain ⁡ ( X , T )  SplitInfo  ( X , T ) GainRatio(X, T)=\frac{\operatorname{Gain}(X, T)}{\text { SplitInfo }(X, T)} GainRatio(X,T)= SplitInfo (X,T)Gain(X,T)

S p l i t I n f o ( O u t l o o k , T ) = − 5 / 14 × log ⁡ 2 ( 5 / 14 ) − 4 / 14 × log ⁡ 2 ( 4 / 14 ) − 5 / 14 × log ⁡ 2 ( 5 / 14 ) = 1.577 SplitInfo(Outlook,T )=-5 / 14 \times \log _{2}(5 / 14)-4 / 14 \times \log _{2}(4 / 14)-5 / 14 \times \log _{2}(5 / 14)=1.577 SplitInfo(Outlook,T)=5/14×log2(5/14)4/14×log2(4/14)5/14×log2(5/14)=1.577
Outlook的增益率是0.25/1.577=0.16

构造过程中进行剪枝

通常进行剪枝是为了处理由于数据中的噪声和离群点导致的过分拟合问题,剪枝一般采用自下而上的方式,在生成决策树后进行

处理连续属性值

C4.5算法对连续属性的处理有两种方法:一种是基于信息增益度的;另一种是基于Risannen的最小描述长度原理

实例:用下表的数据,使用C4.5建立决策树的算法

天气 温度 湿度 风速 适动
炎热 取消
炎热 取消
炎热 进行
适中 进行
寒冷 正常 进行
寒冷 正常 取消
寒冷 正常 进行
适中 取消
寒冷 正常 进行
适中 正常 进行
适中 正常 进行
适中 进行
炎热 正常 进行
适中 取消
from IPython.display import Image
Image(filename="./data/5_15.png",width=500)

在这里插入图片描述

Image(filename="./data/5_16.png",width=500)

在这里插入图片描述

Image(filename="./data/5_17.png",width=500)

在这里插入图片描述

四.决策树的剪枝

决策树生成算法递归地产生决策树,直到不能继续下去为止.这样产生的树往往对训练数据的分类很准确,但对未知的测试数据的分类却没有那么准确,即出现过拟合现象.过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树,解决这个问题的办法是考虑决策树的复杂度,对已生成的决策树进行简化

在决策树学习中将已生成的树进行简化的过程称为剪枝(pruning).具体地,剪枝从已生成的树上裁掉一些子树或叶结点,并将其根结点或父结点作为新的叶结点,从而简化分类树模型

介绍一种简单的决策树学习的剪枝算法

决策树的剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数(cost function)来实现

决策树生成只考虑了通过提高信息增益(或信息增益比)对训练数据进行更好的拟合,而决策树剪枝通过优化损失函数还考虑了减小模型复杂度.决策树生成学习局部的模型,而决策树剪枝学习整体的模型

树的剪枝算法
输入:生成算法产生的整个T,参数 α \alpha α
输出:修剪后的子树 T α T_{\alpha} Tα

  1. 计算每个结点的经验熵
  2. 递归地从树的叶结点向上回缩
  3. 返回(2),直至不能继续为止,得到损失函数最小的子树 T α T_{\alpha} Tα
Image(filename="./data/5_9.png",width=500)

在这里插入图片描述

决策树的剪枝算法可以由一种动态规划的算法实现.类似的动态规划算法可参考文献

五.CART算法

CART同样由特征选择,树的生成及剪枝组成,既可以用于分类也可以用于回归.以下将用于分类与回归的树统称为决策树

CART的输入和输出变量可以是离散型和连续型,而C4.5的输出变量只能是离散型

CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法.CART假设决策树是二叉树,内部结点特征的取值为"是"和"否",左分支时取值为"是"的分支,右分支是取值为"否"的分支.这样的决策树等价于递归地二分每个特征,将输入空间即特征空间划分为有限个单元,并在这些单元上确定预测的概率分布,也就是在输入给定的条件下输出的条件概率分布

CART算法由以下两步组成:

  1. 决策树生成:基于训练数据集生成决策树,生成的决策树要尽量大
  2. 决策树剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树,这时用损失函数最小作为剪枝的标准

1.CART生成

决策树的生成就是递归地构建二叉决策树的过程.对回归树用平方误差最小化准则,对分类树用基尼指数(Gini index)最下化准则,进行特征选择,生成二叉树

基尼指数:在分类问题中,假设有K个类,样本点属于第k类的概率为 p k p_{k} pk,则概率分布的基尼指数定义为:
Gini ⁡ ( p ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 \operatorname{Gini}(p)=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2} Gini(p)=k=1Kpk(1pk)=1k=1Kpk2

对于二类分类问题,若样本点属于第1个类的概率是p,则概率分布的基尼指数为:
Gini ⁡ ( p ) = 2 p ( 1 − p ) \operatorname{Gini}(p)=2 p(1-p) Gini(p)=2p(1p)

对于给定的样本集合D,其基尼指数为:
Gini ⁡ ( D ) = 1 − ∑ k = 1 K ( ∣ C k ∣ ∣ D ∣ ) 2 \operatorname{Gini}(D)=1-\sum_{k=1}^{K}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2} Gini(D)=1k=1K(DCk)2
这里, C k C_{k} Ck是D中属于第k类的样本子集,K是类的个数

如果样本结合D根据特征A是否取某一可能值 a a a被分割成 D 1 D_{1} D1 D 2 D_{2} D2两部分,即:
D 1 = { ( x , y ) ∈ D ∣ A ( x ) = a } , D 2 = D − D 1 D_{1}=\{(x, y) \in D | A(x)=a\}, \quad D_{2}=D-D_{1} D1={ (x,y)DA(x)=a},D2=DD1

则在特征A的条件下,集合D的基尼指数定义为:
Gini ⁡ ( D , A ) = ∣ D 1 ∣ ∣ D ∣ Gini ⁡ ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ Gini ⁡ ( D 2 ) \operatorname{Gini}(D, A)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right) Gini(D,A)=DD1Gini(D1)+DD2Gini(D2)

基尼指数 Gini ⁡ ( D ) \operatorname{Gini}(D) Gini(D)表示集合D的不确定性,基尼指数 Gini ⁡ ( D , A ) \operatorname{Gini}(D, A) Gini(D,A)表示经A=a分割后集合D的不确定性,基尼指数值越大,样本结合的不确定性也就越大,这一点与熵相似

Image(filename="./data/5_10.png",width=500)

在这里插入图片描述

实例3:根据贷款表所给训练数据集,应用CART算法生成决策树

Image(filename="./data/5_11.png",width=500)

在这里插入图片描述

3.CART剪枝

CART剪枝算法从"完全生长"的决策树的底端剪去一些子树,便决策树变小(模型变简单),从而能够对未知数据有更准确的预测.CART剪枝算法由两步组成,首先从生成算法产生的决策树 T 0 T_{0} T0底端开始不断剪枝,直到 T 0 T_{0} T0的根结点,形成一个子树序列 { T 0 , T 1 , ⋯   , T n } \left\{T_{0}, T_{1}, \cdots, T_{n}\right\} { T0,T1,,Tn};然后通过交叉验证法在独立的验证数据集上对子树序列进行测试,从中选择最优子树

3.树选择

因为在树生成过程中可能存在不能提高分类纯度的划分节点,且存在过拟合训练数据的情况,这时需要使用一份单独的测试数据来评估每棵剪枝树的预测性能,从而选取最优树

实例:割草机制造商欲把城市中的家庭成分愿意购买割草机和不愿意购买的两类.在这个城市中随机抽取12个拥有割草机的家庭和12个非拥有割草机的家庭作为样本.这里的自变量是收入( x 1 x_{1} x1)和草地面积( x 2 x_{2} x2).类别边浪有两个类别:拥有和非拥有

观察序号 收入(千美元) 草地面积(平方尺) 拥有者=1,非拥有者=2
1 60 18.4 1
2 80.5 16.8 1
3 64.8 21.6 1
4 61.5 20.8 1
5 87 23.6 1
6 110.1 19.2 1
7 108 17.6 1
8 82.8 22.4 1
9 69 20 1
10 93 20.8 1
11 51 22 1
12 81 20 1
13 75 19.6 2
14 52.8 20.8 2
15 64.8 17.4 2
16 52.8 20.2 2
17 84 17.6 2
18 49.2 17.6 2
19 59.4 16 2
20 66 18.4 2
21 47.4 16.4 2
22 33 18.8 2
23 51 14 2
24 63 14.8 2

将表图例

from IPython.display import Image
Image(filename="./data/5_18.png",width=800)

在这里插入图片描述

在使用CART算法时,首先使用 x 2 = 19 x_{2}=19 x2=19进行分类.由图可以直观地发现两个矩形部分更加同质(即统一类别的点更多地聚集在一起)

Image(filename="./data/5_19.png",width=500)

在这里插入图片描述

通过观察得知,每一个矩形都是同质的.即包含一种类别的点.该算法每一次划分都将节点划分为两个子节点

Image(filename="./data/5_20.png",width=600)

在这里插入图片描述

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/V_lq6h/article/details/89493861

智能推荐

什么是内部类?成员内部类、静态内部类、局部内部类和匿名内部类的区别及作用?_成员内部类和局部内部类的区别-程序员宅基地

文章浏览阅读3.4k次,点赞8次,收藏42次。一、什么是内部类?or 内部类的概念内部类是定义在另一个类中的类;下面类TestB是类TestA的内部类。即内部类对象引用了实例化该内部对象的外围类对象。public class TestA{ class TestB {}}二、 为什么需要内部类?or 内部类有什么作用?1、 内部类方法可以访问该类定义所在的作用域中的数据,包括私有数据。2、内部类可以对同一个包中的其他类隐藏起来。3、 当想要定义一个回调函数且不想编写大量代码时,使用匿名内部类比较便捷。三、 内部类的分类成员内部_成员内部类和局部内部类的区别

分布式系统_分布式系统运维工具-程序员宅基地

文章浏览阅读118次。分布式系统要求拆分分布式思想的实质搭配要求分布式系统要求按照某些特定的规则将项目进行拆分。如果将一个项目的所有模板功能都写到一起,当某个模块出现问题时将直接导致整个服务器出现问题。拆分按照业务拆分为不同的服务器,有效的降低系统架构的耦合性在业务拆分的基础上可按照代码层级进行拆分(view、controller、service、pojo)分布式思想的实质分布式思想的实质是为了系统的..._分布式系统运维工具

用Exce分析l数据极简入门_exce l趋势分析数据量-程序员宅基地

文章浏览阅读174次。1.数据源准备2.数据处理step1:数据表处理应用函数:①VLOOKUP函数; ② CONCATENATE函数终表:step2:数据透视表统计分析(1) 透视表汇总不同渠道用户数, 金额(2)透视表汇总不同日期购买用户数,金额(3)透视表汇总不同用户购买订单数,金额step3:讲第二步结果可视化, 比如, 柱形图(1)不同渠道用户数, 金额(2)不同日期..._exce l趋势分析数据量

宁盾堡垒机双因素认证方案_horizon宁盾双因素配置-程序员宅基地

文章浏览阅读3.3k次。堡垒机可以为企业实现服务器、网络设备、数据库、安全设备等的集中管控和安全可靠运行,帮助IT运维人员提高工作效率。通俗来说,就是用来控制哪些人可以登录哪些资产(事先防范和事中控制),以及录像记录登录资产后做了什么事情(事后溯源)。由于堡垒机内部保存着企业所有的设备资产和权限关系,是企业内部信息安全的重要一环。但目前出现的以下问题产生了很大安全隐患:密码设置过于简单,容易被暴力破解;为方便记忆,设置统一的密码,一旦单点被破,极易引发全面危机。在单一的静态密码验证机制下,登录密码是堡垒机安全的唯一_horizon宁盾双因素配置

谷歌浏览器安装(Win、Linux、离线安装)_chrome linux debian离线安装依赖-程序员宅基地

文章浏览阅读7.7k次,点赞4次,收藏16次。Chrome作为一款挺不错的浏览器,其有着诸多的优良特性,并且支持跨平台。其支持(Windows、Linux、Mac OS X、BSD、Android),在绝大多数情况下,其的安装都很简单,但有时会由于网络原因,无法安装,所以在这里总结下Chrome的安装。Windows下的安装:在线安装:离线安装:Linux下的安装:在线安装:离线安装:..._chrome linux debian离线安装依赖

烤仔TVの尚书房 | 逃离北上广?不如押宝越南“北上广”-程序员宅基地

文章浏览阅读153次。中国发达城市榜单每天都在刷新,但无非是北上广轮流坐庄。北京拥有最顶尖的文化资源,上海是“摩登”的国际化大都市,广州是活力四射的千年商都。GDP和发展潜力是衡量城市的数字指...

随便推点

java spark的使用和配置_使用java调用spark注册进去的程序-程序员宅基地

文章浏览阅读3.3k次。前言spark在java使用比较少,多是scala的用法,我这里介绍一下我在项目中使用的代码配置详细算法的使用请点击我主页列表查看版本jar版本说明spark3.0.1scala2.12这个版本注意和spark版本对应,只是为了引jar包springboot版本2.3.2.RELEASEmaven<!-- spark --> <dependency> <gro_使用java调用spark注册进去的程序

汽车零部件开发工具巨头V公司全套bootloader中UDS协议栈源代码,自己完成底层外设驱动开发后,集成即可使用_uds协议栈 源代码-程序员宅基地

文章浏览阅读4.8k次。汽车零部件开发工具巨头V公司全套bootloader中UDS协议栈源代码,自己完成底层外设驱动开发后,集成即可使用,代码精简高效,大厂出品有量产保证。:139800617636213023darcy169_uds协议栈 源代码

AUTOSAR基础篇之OS(下)_autosar 定义了 5 种多核支持类型-程序员宅基地

文章浏览阅读4.6k次,点赞20次,收藏148次。AUTOSAR基础篇之OS(下)前言首先,请问大家几个小小的问题,你清楚:你知道多核OS在什么场景下使用吗?多核系统OS又是如何协同启动或者关闭的呢?AUTOSAR OS存在哪些功能安全等方面的要求呢?多核OS之间的启动关闭与单核相比又存在哪些异同呢?。。。。。。今天,我们来一起探索并回答这些问题。为了便于大家理解,以下是本文的主题大纲:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JCXrdI0k-1636287756923)(https://gite_autosar 定义了 5 种多核支持类型

VS报错无法打开自己写的头文件_vs2013打不开自己定义的头文件-程序员宅基地

文章浏览阅读2.2k次,点赞6次,收藏14次。原因:自己写的头文件没有被加入到方案的包含目录中去,无法被检索到,也就无法打开。将自己写的头文件都放入header files。然后在VS界面上,右键方案名,点击属性。将自己头文件夹的目录添加进去。_vs2013打不开自己定义的头文件

【Redis】Redis基础命令集详解_redis命令-程序员宅基地

文章浏览阅读3.3w次,点赞80次,收藏342次。此时,可以将系统中所有用户的 Session 数据全部保存到 Redis 中,用户在提交新的请求后,系统先从Redis 中查找相应的Session 数据,如果存在,则再进行相关操作,否则跳转到登录页面。此时,可以将系统中所有用户的 Session 数据全部保存到 Redis 中,用户在提交新的请求后,系统先从Redis 中查找相应的Session 数据,如果存在,则再进行相关操作,否则跳转到登录页面。当数据量很大时,count 的数量的指定可能会不起作用,Redis 会自动调整每次的遍历数目。_redis命令

URP渲染管线简介-程序员宅基地

文章浏览阅读449次,点赞3次,收藏3次。URP的设计目标是在保持高性能的同时,提供更多的渲染功能和自定义选项。与普通项目相比,会多出Presets文件夹,里面包含着一些设置,包括本色,声音,法线,贴图等设置。全局只有主光源和附加光源,主光源只支持平行光,附加光源数量有限制,主光源和附加光源在一次Pass中可以一起着色。URP:全局只有主光源和附加光源,主光源只支持平行光,附加光源数量有限制,一次Pass可以计算多个光源。可编程渲染管线:渲染策略是可以供程序员定制的,可以定制的有:光照计算和光源,深度测试,摄像机光照烘焙,后期处理策略等等。_urp渲染管线