技术标签: 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)
文章浏览阅读1.6k次。安装配置gi、安装数据库软件、dbca建库见下:http://blog.csdn.net/kadwf123/article/details/784299611、检查集群节点及状态:[root@rac2 ~]# olsnodes -srac1 Activerac2 Activerac3 Activerac4 Active[root@rac2 ~]_12c查看crs状态
文章浏览阅读1.3w次,点赞45次,收藏99次。我个人用的是anaconda3的一个python集成环境,自带jupyter notebook,但在我打开jupyter notebook界面后,却找不到对应的虚拟环境,原来是jupyter notebook只是通用于下载anaconda时自带的环境,其他环境要想使用必须手动下载一些库:1.首先进入到自己创建的虚拟环境(pytorch是虚拟环境的名字)activate pytorch2.在该环境下下载这个库conda install ipykernelconda install nb__jupyter没有pytorch环境
文章浏览阅读5.2k次,点赞19次,收藏28次。选择scoop纯属意外,也是无奈,因为电脑用户被锁了管理员权限,所有exe安装程序都无法安装,只可以用绿色软件,最后被我发现scoop,省去了到处下载XXX绿色版的烦恼,当然scoop里需要管理员权限的软件也跟我无缘了(譬如everything)。推荐添加dorado这个bucket镜像,里面很多中文软件,但是部分国外的软件下载地址在github,可能无法下载。以上两个是官方bucket的国内镜像,所有软件建议优先从这里下载。上面可以看到很多bucket以及软件数。如果官网登陆不了可以试一下以下方式。_scoop-cn
文章浏览阅读4.5k次,点赞2次,收藏3次。首先要有一个color-picker组件 <el-color-picker v-model="headcolor"></el-color-picker>在data里面data() { return {headcolor: ’ #278add ’ //这里可以选择一个默认的颜色} }然后在你想要改变颜色的地方用v-bind绑定就好了,例如:这里的:sty..._vue el-color-picker
文章浏览阅读640次。基于芯片日益增长的问题,所以内核开发者们引入了新的方法,就是在内核中只保留函数,而数据则不包含,由用户(应用程序员)自己把数据按照规定的格式编写,并放在约定的地方,为了不占用过多的内存,还要求数据以根精简的方式编写。boot启动时,传参给内核,告诉内核设备树文件和kernel的位置,内核启动时根据地址去找到设备树文件,再利用专用的编译器去反编译dtb文件,将dtb还原成数据结构,以供驱动的函数去调用。firmware是三星的一个固件的设备信息,因为找不到固件,所以内核启动不成功。_exynos 4412 刷机
文章浏览阅读2w次,点赞24次,收藏42次。Linux系统配置jdkLinux学习教程,Linux入门教程(超详细)_linux配置jdk
文章浏览阅读3.3k次,点赞5次,收藏19次。xlabel('\delta');ylabel('AUC');具体符号的对照表参照下图:_matlab微米怎么输入
文章浏览阅读119次。顺序读写指的是按照文件中数据的顺序进行读取或写入。对于文本文件,可以使用fgets、fputs、fscanf、fprintf等函数进行顺序读写。在C语言中,对文件的操作通常涉及文件的打开、读写以及关闭。文件的打开使用fopen函数,而关闭则使用fclose函数。在C语言中,可以使用fread和fwrite函数进行二进制读写。 Biaoge 于2024-03-09 23:51发布 阅读量:7 ️文章类型:【 C语言程序设计 】在C语言中,用于打开文件的函数是____,用于关闭文件的函数是____。
文章浏览阅读3.4k次,点赞2次,收藏13次。跟随鼠标移动的粒子以grid(SOP)为partical(SOP)的资源模板,调整后连接【Geo组合+point spirit(MAT)】,在连接【feedback组合】适当调整。影响粒子动态的节点【metaball(SOP)+force(SOP)】添加mouse in(CHOP)鼠标位置到metaball的坐标,实现鼠标影响。..._touchdesigner怎么让一个模型跟着鼠标移动
文章浏览阅读178次。项目运行环境配置:Jdk1.8 + Tomcat7.0 + Mysql + HBuilderX(Webstorm也行)+ Eclispe(IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持)。项目技术:Springboot + mybatis + Maven +mysql5.7或8.0+html+css+js等等组成,B/S模式 + Maven管理等等。环境需要1.运行环境:最好是java jdk 1.8,我们在这个平台上运行的。其他版本理论上也可以。_基于java技术的停车场管理系统实现与设计
文章浏览阅读3.5k次。前言对于MediaPlayer播放器的源码分析内容相对来说比较多,会从Java-&amp;gt;Jni-&amp;gt;C/C++慢慢分析,后面会慢慢更新。另外,博客只作为自己学习记录的一种方式,对于其他的不过多的评论。MediaPlayerDemopublic class MainActivity extends AppCompatActivity implements SurfaceHolder.Cal..._android多媒体播放源码分析 时序图
文章浏览阅读2.4k次,点赞41次,收藏13次。java 数据结构与算法 ——快速排序法_快速排序法