当前位置: 首页 > >

matlab使用决策树实现西瓜数据集分类_决策树 笔记

发布时间:





很久没做笔记是因为我高估了自己的毅力。现如今都是各种XGBoost的天下了,谈这些ID3、C4.5、CART有何用,还是那句话,模型算法不管复杂不复杂,输出了才能理解的更深刻,理解了才是自己的。


从LR到决策树

简单的线性分类器面对下面的相亲问题是这样的:







RL

每一个权重W都通过训练数据的标签SGD梯度下降得以更新。


但换个人的思考方式,要是你去相亲,只要他没钱,无论他是帅破天际,也会去的,毕竟大家看重的是内在。







决策树

简单,解释性好,逻辑没毛病。


专业表达


决策树是基于树结构来对实例进行决策的一种基本的分类和回归的机器学*方法。决策树由结点和有向边组成,结点分为内部结点(表示一个特征的划分)和叶子结点(表示一个类别或输出)。


    每个“内部结点”对应于某个属性上的“测试”

2?每个分支对应于该测试的一种可能结果(即该属性的某个取值)


3.每个“叶结点”对应于一个“预测结果”


学*过程:通过对训练样本的分析来确定“划分属性”(即内部结点所对应的属性)


预测过程:将测试示例从根结点开始,沿着划分属性所构成的“判定测试序列”下行,直到叶结点(人话先看是不是丑的,行那再看有房吗,再看有车波。。。我不相了,欺负人)


决策树学*(训练过程)(生成树的过程)

训练数据集:





其中,



是为第


个特征向量(实例), (


为第


个样本,


为标签)





的类别标记,(n说明一个特征有n个特征)


。学*的目标数是根据给定的训练数据集构建一个决策树模型,使得可对实例进行正确的分类或回归。

决策树学*包括3个步骤:特征选择、决策树生成、决策树修剪。


特征选择

特征选择在于选取对于训练数据具有分类能力的特征。这里这里不得不提下信息熵(entropy)和信息增益(information gain)。


信息熵







信息熵

假设箱子里有红黄蓝3类球,想要知道这个箱子纯不纯,使用上图公式:极端最纯的情况是清一色,就是一类占了100%,其他2类个数为0,带入上面公式(这里K = 3,P 1= 1,P2 = 0,P3 = 0),那么Ent(D) = -(0+0+0) = 0 ;现在算下最杂乱的情况,每个类占



,那Ent(D) =


=


。总结,Ent(D)越大,D越不纯(杂乱),不确定越大,反之自己总结。

如果你要产生一棵树去做决策,肯定需要确定性越大越好的。

信息增益


单有信息熵成不了事,信息增益



闪亮登场,

下面将Ent(D)简写为H(D)



,特征A对训练集D的信息增益。


好理解,就是反映训练集D的确定性程度。


是条件熵,定义如下,随机变量


给定的条件下随机变量


的条件熵 :


,即,


给定条件下


的条件概率分布的熵对


的数学期望,其中




举个例子,



是个陌生人,那



很大,表示我对这个陌生人不确定大;信息增益说的是这么个事,



是我的一个要好的朋友,那



在朋友



的条件下,对



的不确定性就增加了。增加了多少确定性就是前后的差值,即






那依次选特征(看车,还是先看房)去生成一棵树做预测,就可以优先选择让信息增益最大的特征作为结点。显然,Gain(D,a) 越大,获得的纯度提升越大,此次划分的效果越好。


ID3






信息增益

公式推导

输入:训练数据集



和特征




输出:特征



对训练数据集


的信息增益




这里的



是所有的特征,就是说把所有的特征依次对


求信息增益,比较出使最大信息增益的那个特征,当作树的第一个结点。

设训练数据集为






表示其样本容量,即样本个数。(

看下图西瓜数据集,17个瓜)

设有



个类,


为属于类


的样本的个数。(西瓜就只有


两类 )

设特征






个不同的特征取值


,根据特征


的取值将


划分为


个子集








的样本数。(A有色泽,根蒂 ... 当


= 色泽时,则对应


的取值为青绿,乌黑,浅白,但


=根蒂,则对应


的取值蜷缩 ,稍蜷,硬挺)

记子集



中属于类


的样本的集合为









推导

举个西瓜书上的例子






该数据17个瓜,分为2类,8个好瓜,9个不好,



,根结点的信息熵为






下一步就是计算每个属性对应的信息增益,













= 0.109









C4.5

唯一变化的一点就是将信息增益换成信息增益率(gain_ratio)




,其中




既然是ID 3改进版,思考下ID3的缺点,不考虑分母就是ID3,举个例子,还是上面西瓜的例子,我把编号一部小心加到属性里面去了,大家都知道编号对分类一点帮助都没有的,西瓜的根节点0.998信息熵不变,17个编号,17个子数据集,因为每一个样本的编号都是不同的(由于编号独特唯一,条件熵为0了,每一个结点中只有一类,纯度非常高啊),也就是说,来了一个预测样本,你只要告诉我编号,其它特征就没有用了,那编号的信息增益绝对最大最后也是0.998。分母的作用就体现出来了,属性a的可能取值数目越多(即V越大),则 IV(a)的值通常就越大。对这类似(编号)的属性进行惩罚。


CART

这个算法改进在于将信息熵换成基尼指数。但其实基尼指数和信息熵是亲兄弟


基尼指数长这样



,同样,基尼指数越小,纯度越高。

信息熵长这样



,高等数学


的一阶泰勒展开为









,这不就是基尼指数?数学真奇妙

这里不叫信息增益,叫属性a 的基尼指数:





决策树修剪

说到现在树生成没问题了,但我一直没讲长到什么时候停,停止条件:


1、当前结点包含的样本属于同一类别。(假设当出现纹理。不管啥纹理都是好瓜,停止)


2、当前属性集为空或样本集合为空。(没有怎么分裂,停止)


3、无法划分。(所有样本在所有属性下居然还有分不出来,停止)


4、当所有信息增益值均小于一个阈值时也可停止。


但机器学*还有个烦人的东西叫过拟合,这树不能长的太茂盛,对上面停止生长的树修剪。


输入:决策树



,参数




输出:输出:修剪后的子树





计算每个结点的信息熵。递归地从树的叶结点向上回缩,设一组叶结点回缩到其父结点之前与之后的整体树分别为




,其对应的损失函数值分别是





,其中


,+前表示整棵树的纯度,


是惩罚项,不要


过大。
如果

则进行剪枝,即将父结点变为新的叶结点。

回归树

回归树CART回归树讲的都是CART这种二叉树,以前的线性回归就是拟合出



这条直线,类比,在树结构做回归同样要拟合出一条线(虽然不是直线)


,这条线的表达式长的虽然奇怪,但它就是条线,其中


类似于


代求参数,


是指示函数,当


属于


,则为1,否为0。

假设输入空间划分为

个单元


。其中


是区域


上的回归决策树输出。

举个例子







图片来源:https://blog.csdn.net/Albert201605/article/details/81865261

根据不同的结点划分空间,坐标系里面的每根线就是分割路径,把坐标切割成



个单元,


是该单元的所i有值的*均(质心)。

如何求出回归树



,即求出



,最根本来说怎么划分空间。


输入:训练数据集





输出:回归树










回归树

第一步目的就是根据最优属性和分割点,找到最好的切割的路径完成空间划分,这个最优标准就是以前的最小二乘法。只不过它分划分后左(上)或右(下)求最小二乘法。


第二步,根据划分好的最优空间求出



( 每个空间的所i有值的*均(质心)。






线性回归(红线),回归树(树深:1,3)

看公式也猜到这根线长的就不是直线,但如果树的深度足够大,也就直了(过拟合了)。


随机森林,Xgboost. ...


未完待续







相关资源:matlab实现决策树cart算法



友情链接: hackchn文档网 营销文档网 爱linux网 爱行业网 时尚网