技术标签: ML
决策树(decision tree)是一种基本的分类与回归方法.决策树呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程,它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布,其主要优点是模型具有可读性,分类速度快.决策树学习通常包括3个步骤:特征选择,决策树的生成和决策树的修剪
分类决策树是一种描述对实例进行分类的树形结构.决策树由结点(node)和有向边(directed edge)组成.结点有三种类型:根结点(root node),内部结点(internal node)和叶结点(leaf node).内部结点表示一个特征或属性,叶结点表示一个类
用决策树分类,从根结点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子结点;这时每一个子结点对应着该特征的一个取值.如此递归地对实例进行测试并分配,直至达到叶结点,最后将实例分到叶结点的类中
下图是一个决策树的示意图
from IPython.display import Image
Image(filename="./data/5_1.png",width=500)
可以将决策树看成一个if-then规则的集合.将决策树转换成if-then规则的过程是这样的:由决策树的根结点到叶结点的每一条路径构建一条规则;路径上内部结点的特征对应着规则的条件,而叶结点的类对应着规则的结论.决策树的路径或其对应的if-then规则集合具有一个重要的性质;互斥并且完备.这就是说,每一个实例都被一条路径或一条规则所覆盖,而且只被一条路径或一条规则所覆盖.这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件
决策树还表示给定特征条件下类的条件概率分布,这一条件概率分布定义在特征空间的一个划分(partition)上.将特征空间划分为互不相交的单元(cell)或区域(region),并在每个单元定义一个类的概率分布就构成了一个条件概率分布.决策树一条路径对应于划分中的一个单元.决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成.假设X为表示通知的随机变量,Y为表示类的随机变量,那么这个条件概率分布可以表示为 P ( Y ∣ X ) P(Y | X) P(Y∣X).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=+1∣X=c)>0.5时,则认为这个单元属于正类,即落在这个单元的实例都被视为正例.图c为对应于图b中条件概率分布的决策树
决策树学习,假设给定训练数据集:
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为样本容量.学习的目标是根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类
决策树学习本质上是从训练数据集中归纳出一组分类规则.与训练数据集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个,也可能一个也没有.我们需要的是一个与训练数据矛盾较小的决策树.同属具有很好的泛化能力.从另一个角度看,决策树学习是由训练数据集估计条件概率模型.基于特征空间划分的类的条件概率模型有无穷多个.我们选择的条件概率模型应该不仅对训练数据有很好的拟合,而且对未知数据有很好的预测
特征选择在于选取对训练数据具有分类能力的特征.这样可以提高决策树学习的效率.如果利用一个特征进行分类的结果与随机分类的结果没有很大差别.则称这个特征是没有分类的能力的.经验上扔掉这样的特征对决策树学习的精度影响不大,通常特征选择的准则是信息增益或信息增益比
首先通过一个例子来说明特征选择问题
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)就能够很好地表示这一直观的准则
在信息论与概率统计中,熵(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=1∑npilogpi
若 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=1∑npilogpi
熵越大,随机变量的不确定性就越高.从定义可验证:
0 ⩽ H ( p ) ⩽ log n 0 \leqslant H(p) \leqslant \log n 0⩽H(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)=1−p,0⩽p⩽1
熵为:
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−(1−p)log2(1−p)
这时,熵 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(Y∣X)表示在已知随机变量X的条件下随机变量Y的不确定性.随机变量 X X X给定的条件下随机变量 Y Y Y的条件熵(conditional entropy) H ( Y ∣ X ) H(Y | X) H(Y∣X).定义为 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(Y∣X)=i=1∑npiH(Y∣X=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(D∣A)之差,即:
g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D, A)=H(D)-H(D | A) g(D,A)=H(D)−H(D∣A)
一般地,熵 H ( Y ) H(Y) H(Y)与条件熵 H ( Y ∣ X ) H(Y | X) H(Y∣X)之差称为互信息(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=1K∣Ck∣=∣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=1n∣Di∣=∣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=Di∩Ck, ∣ 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,根据信息增益准则选择最优特征
Image(filename="./data/5_6.png",width=500)
最后,比较各特征的信息增益值,由于特征 A 3 A_{3} A3(有自己的房子)的信息增益值最大,所以选择特征 A 3 A_{3} A3作为最优特征
信息增益比的大小是相对于训练数据集而言的,并没有绝对意义.在分类问题困难时,也就是说在训练数据集的经验熵大的时候,信息增益值会偏大,反之,信息增益值会偏小.使用信息增益比(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)
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个条件中的一条,即可停止树的分支构造:
ID3采用信息增益度作为评价标准.信息增益度的缺点是倾向于选择取值较多的属性,但在有些情况下这类属性可能不会提供太多有价值的信息.其次ID3算法只能对离散型属性的数据集构造决策树
ID3算法只有树的生成,所以该算法生成的树容易产生过拟合
C4.5算法与ID3算法相似,C4.5算法对ID3算法进行了改进.C4.5在生成的过程中,用信息增益比来选择特征
C4.5对ID3算法进行了以下几方面的改进:
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α
Image(filename="./data/5_9.png",width=500)
决策树的剪枝算法可以由一种动态规划的算法实现.类似的动态规划算法可参考文献
CART同样由特征选择,树的生成及剪枝组成,既可以用于分类也可以用于回归.以下将用于分类与回归的树统称为决策树
CART的输入和输出变量可以是离散型和连续型,而C4.5的输出变量只能是离散型
CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法.CART假设决策树是二叉树,内部结点特征的取值为"是"和"否",左分支时取值为"是"的分支,右分支是取值为"否"的分支.这样的决策树等价于递归地二分每个特征,将输入空间即特征空间划分为有限个单元,并在这些单元上确定预测的概率分布,也就是在输入给定的条件下输出的条件概率分布
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=1∑Kpk(1−pk)=1−k=1∑Kpk2
对于二类分类问题,若样本点属于第1个类的概率是p,则概率分布的基尼指数为:
Gini ( p ) = 2 p ( 1 − p ) \operatorname{Gini}(p)=2 p(1-p) Gini(p)=2p(1−p)
对于给定的样本集合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)=1−k=1∑K(∣D∣∣Ck∣)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)∈D∣A(x)=a},D2=D−D1
则在特征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)=∣D∣∣D1∣Gini(D1)+∣D∣∣D2∣Gini(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)
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};然后通过交叉验证法在独立的验证数据集上对子树序列进行测试,从中选择最优子树
因为在树生成过程中可能存在不能提高分类纯度的划分节点,且存在过拟合训练数据的情况,这时需要使用一份单独的测试数据来评估每棵剪枝树的预测性能,从而选取最优树
实例:割草机制造商欲把城市中的家庭成分愿意购买割草机和不愿意购买的两类.在这个城市中随机抽取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)
文章浏览阅读2w次,点赞7次,收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加 外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案,在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建:添加Visual C++ , Win32 项目这......_c#调用lib
文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体,挺好看的。注重颜值的网站都会使用,例如知乎:font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang
文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--action,当提交表单时,向何处发送表单中的数据,地址可以是相对地址也可以是绝对地址--><!--method将表单中的数据传送给服务器处理,get方式直接显示在url地址中,数据可以被缓存,且长度有限制;而post方式数据隐藏传输,_html表单的处理程序有那些
文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证(即Google Authenticator服务)后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器
文章浏览阅读4.3k次,点赞5次,收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距
文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节,实现了多层数据的堆叠,为用户 提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制(CoW)策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的,不建议用于生成环境。_docker 保存容器
文章浏览阅读834次,点赞27次,收藏13次。网络拓扑结构是指计算机网络中各组件(如计算机、服务器、打印机、路由器、交换机等设备)及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式,也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn
文章浏览阅读1.8k次,点赞5次,收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时,通常的做法是:new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的,而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠,也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑,需要做一些额外的特殊处理,笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数,一劳永逸,避免每次ne_date.prototype 将所有 ios
文章浏览阅读5.3k次。方法一:用PLSQL Developer工具。 1 在PLSQL Developer的sql window里输入select * from test for update; 2 按F8执行 3 打开锁, 再按一下加号. 鼠标点到第一列的列头,使全列成选中状态,然后粘贴,最后commit提交即可。(前提..._excel导入pl/sql
文章浏览阅读83次。Git常用命令速查手册1、初始化仓库git init2、将文件添加到仓库git add 文件名 # 将工作区的某个文件添加到暂存区 git add -u # 添加所有被tracked文件中被修改或删除的文件信息到暂存区,不处理untracked的文件git add -A # 添加所有被tracked文件中被修改或删除的文件信息到暂存区,包括untracked的文件...
文章浏览阅读202次。分享119个ASP.NET源码总有一个是你想要的_千博二手车源码v2023 build 1120
文章浏览阅读1.8k次。版权声明:转载请注明出处 http://blog.csdn.net/irean_lau。目录(?)[+]1、缺省构造函数。2、缺省拷贝构造函数。3、 缺省析构函数。4、缺省赋值运算符。5、缺省取址运算符。6、 缺省取址运算符 const。[cpp] view plain copy_空类默认产生哪些类成员函数