2.2.机器学习模型:决策树随机森林ok.pdf
- 文档编号:14660304
- 上传时间:2023-06-25
- 格式:PDF
- 页数:90
- 大小:4.91MB
2.2.机器学习模型:决策树随机森林ok.pdf
《2.2.机器学习模型:决策树随机森林ok.pdf》由会员分享,可在线阅读,更多相关《2.2.机器学习模型:决策树随机森林ok.pdf(90页珍藏版)》请在冰点文库上搜索。
机器学习模型:
决策树随机森林目标任务与主要内容复习信息熵熵、联合熵、条件熵、互信息决策树学习算法信息增益ID3、C4.5、CARTBagging与随机森林CART输入数据x:
M个样本数据,每个数据包括年龄、性别、职业、每日使用计算机时间等输出y:
该样本是否喜欢计算机游戏随机森林决策树:
Level决策树定义信息量原则:
某事件发生的概率小,则该事件的信息量大。
如果两个事件X和Y独立,即p(xy)=p(x)p(y),假定X和Y的信息量分别为h(X)和h(Y),则二者同时发生的信息量应该为h(XY)=h(X)+h(Y)。
定义随机变量X的概率分布为p(x),从而定义X信息量:
思考:
事件X的信息量的期望如何计算呢?
()(log2xpxh=熵对随机事件的信息量求期望,得熵的定义:
注:
经典熵的定义,底数是2,单位是bit本例中,为分析方便使用底数e若底数是e,单位是nat(奈特)()()()=XxxpxpXHln两点分布的熵两点分布的熵()()()()()ppppxpxpXHXx=1ln1lnln继续思考:
三点分布呢?
()()()()()212122111ln1lnlnlnppppppppxpxpXHXx=公式推导()1ln!
lnNNNN()()()()()()=kiiikiiikiiikiiiikiiikiiikiiikiikiippNnNnNnnNNnnnNNNnnNnnNNnnNNnNNNnNNH111111111lnlnln1lnln1lnln1ln1ln1ln11ln!
ln1!
ln1!
ln1自封闭系统的运动总是倒向均匀分布均匀分布的信息熵以离散分布为例:
假定某离散分布可取N个值,概率都是1/N,计算该概率分布的熵。
解:
概率分布律计算熵:
思考:
连续均匀分布的熵如何计算?
NiNpi,2,1,1=()=NiNiNiiiNNNNNpppH111lnln11ln1ln最大熵的理解熵是随机变量不确定性的度量,不确定性越大,熵值越大;若随机变量退化成定值,熵最小:
为0若随机分布为均匀分布,熵最大。
以上是无条件的最大熵分布,若有条件呢?
最大熵模型思考:
若只给定期望和方差的前提下,最大熵的分布形式是什么?
()XXHlog0引理:
根据函数形式判断概率分布正态分布的概率密度函数对数正态分布该分布的对数是关于随机变量x的二次函数根据计算过程的可逆性,若某对数分布能够写成随机变量二次形式,则该分布必然是正态分布。
()()22221=xexp()()+=xxxxp2222ln21lnln举例Gamma分布的定义对数形式若某连续分布的对数能够写成随机变量一次项和对数项的和,则该分布是Gamma分布。
注:
Gamma函数:
Gamma分布的期望为:
()()()0,0,;1=常系数xexxfx()()()CxBxAxxxf+=+=lnlnln1ln,;ln()=XE()=01dtett()()!
1=nn给定方差的最大熵分布建立目标函数使用方差公式化简约束条件显然,此问题为带约束的极值问题。
Lagrange乘子法()()()()()()=2.lnmaxargXVarXEtsxpxpXHxxp()()()()()()222222+=+=XVarXEXEXEXEXVar建立Lagrange函数,求驻点P(x)的对数是关于随机变量x的二次形式,所以,该分布p(x)必然是正态分布!
()()()()()()+=222.lnmaxargXEXEtsxpxpXHxxp()()()()()()()()()()()()()1ln01lnlnln1222212222122221+=+=+=+=xxxpxxxppLxpxxxpxpxpXEXExpxppLxxxx联合熵和条件熵两个随机变量X,Y的联合分布,可以形成联合熵JointEntropy,用H(X,Y)表示H(X,Y)H(X)(X,Y)发生所包含的熵,减去X单独发生包含的熵:
在X发生的前提下,Y发生“新”带来的熵该式子定义为X发生前提下,Y的熵:
条件熵H(Y|X)推导条件熵的定义式=+=+=+=yxyxyxyxxyyxxyxxypyxpxpyxpyxpxpyxpyxpyxpxpyxpyxpyxpxpxpyxpyxpXHYXH,)|(log),()(),(log),()(log),(),(log),()(log),(),(log),()(log)(),(log),()(),(根据条件熵的定义式,可以得到()=xxyxyxyxyyxxXYHxpxypxypxpxypxypxpxypxypxpxypyxpxypyxpXHYXH|)()|(log)|()()|(log)|()()|(log)|()()|(log),()|(log),()(),(,相对熵相对熵,又称互熵,交叉熵,鉴别信息,Kullback熵,Kullback-Leible散度等设p(x)、q(x)是X中取值的两个概率分布,则p对q的相对熵是说明:
相对熵可以度量两个随机变量的“距离”在“贝叶斯网络”、“变分推导”等章节会再次遇到一般的,D(p|q)D(q|p)D(p|q)0、D(q|p)0:
凸函数中的Jensen不等式()()()()()()()xqxpExqxpxpqpDxpxloglog|=思考假定已知随机变量P,求相对简单的随机变量Q,使得Q尽量接近P方法:
使用P和Q的K-L距离。
难点:
K-L距离是非对称的,两个随机变量应该谁在前谁在后呢?
假定使用KL(Q|P),为了让距离最小,则要求在P为0的地方,Q尽量为0。
会得到比较“窄”的分布曲线;假定使用KL(P|Q),为了让距离最小,则要求在P不为0的地方,Q也尽量不为0。
会得到比较“宽”的分布曲线;两个KL散度的区别绿色曲线是真实分布p的等高线;红色曲线是使用近似p(z1,z2)=p(z1)p(z2)得到的等高线左:
KL(p|q):
zeroavoiding右:
KL(q|p):
zeroforcing两个KL散度的区别蓝色曲线是真实分布p的等高线;红色曲线是单模型近似分布q的等高线。
左:
KL(p|q):
q趋向于覆盖p中、右:
KL(q|p):
q能够锁定某一个峰值互信息两个随机变量X,Y的互信息,定义为X,Y的联合分布和独立分布乘积的相对熵。
()()()()()()()()()=yxypxpyxpyxpypxpyxpDYXI,log,|,计算条件熵的定义式:
H(Y)-I(X,Y)|()|(log),()(),(log),()()(),(log),()(log),()()(),(log),()(log),()()(),(log),()(log)(),()(,XYHxypyxpxpyxpyxpypxpyxpyxpypyxpypxpyxpyxpypyxpypxpyxpyxpypypYXIYHyxyxyxyxyxyxyxy=整理得到的等式H(Y|X)=H(X,Y)-H(X)条件熵定义H(Y|X)=H(Y)-I(X,Y)根据互信息定义展开得到有些文献将I(X,Y)=H(Y)H(Y|X)作为互信息的定义式对偶式H(X|Y)=H(X,Y)-H(Y)H(X|Y)=H(X)-I(X,Y)I(X,Y)=H(X)+H(Y)-H(X,Y)有些文献将该式作为互信息的定义式试证明:
H(X|Y)H(X),H(Y|X)H(Y)互信息:
I(X,Y)=H(X)+H(Y)-H(X,Y)()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()=+=+=+=+=yxyxyxyxyxyxyxxyyxyxypxpyxpyxpypxpyxpyxpyxpyxpypyxpxpyxpyxpyxpypyxpxpyxpyxpyxpypypxpxpYXHYHXHYXI,log,loglog,log,log,log,log,log,log,log,log,loglog,强大的Venn图:
帮助记忆决策树的实例(自带测试数据)注:
Weka的全名是怀卡托智能分析环境(WaikatoEnvironmentforKnowledgeAnalysis),是一款免费的,非商业化(与之对应的是SPSS公司商业数据挖掘产品-Clementine)的,基于JAVA环境下开源的机器学习(machinelearning)以及数据挖掘(dataminining)软件。
它和它的源代码可在其官方网站下载。
决策树示意图决策树(DecisionTree)决策树是一种树型结构,其中每个内部结点表示在一个属性上的测试,每个分支代表一个测试输出,每个叶结点代表一种类别。
决策树学习是以实例为基础的归纳学习。
决策树学习采用的是自顶向下的递归方法,其基本思想是以信息熵为度量构造一棵熵值下降最快的树,到叶子节点处的熵值为零,此时每个叶节点中的实例都属于同一类。
决策树学习算法的特点决策树学习算法的最大优点是,它可以自学习。
在学习的过程中,不需要使用者了解过多背景知识,只需要对训练实例进行较好的标注,就能够进行学习。
显然,属于有监督学习。
从一类无序、无规则的事物(概念)中推理出决策树表示的分类规则。
决策树学习的生成算法建立决策树的关键,即在当前状态下选择哪个属性作为分类依据。
根据不同的目标函数,建立决策树主要有一下三种算法。
ID3IterativeDichotomiserC4.5CARTClassificationAndRegressionTree信息增益概念:
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵和条件熵分别称为经验熵和经验条件熵。
信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。
定义:
特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即:
g(D,A)=H(D)H(D|A)显然,这即为训练数据集D和特征A的互信息。
基本记号设训练数据集为,表示样本个数。
设有K个类,为属于类的样本个数,有:
设特征A有n个不同的取值,根据特征A的取值将D划分为n个子集,为的样本个数,有:
记子集中属于类的样本的集合为,为的样本个数。
DkCKkCk2,1,=DCkk=naaa21,nDDD21,iDiDDDii=iDkCikDikDikDkCD信息增益的计算方法计算数据集D的经验熵遍历所有特征,对于特征A:
计算特征A对数据集D的经验条件熵H(D|A)计算特征A的信息增益:
g(D,A)=H(D)H(D|A)选择信息增益最大的特征作为当前的分裂特征()=KkkkDCDCDH1log经验条件熵H(D|A)()()()()()()()()()()()()=niiikiikKkiniikikKkiniikikiKkkiikikikiikikDDDDDDADpADpApADpADpApADpADpApADpADpADH111111,log|log|log|log|log,|其他目标信息增益率:
gr(D,A)=g(D,A)/H(A)Gini系数:
()()21121111=KkkKkkKkkkDCppppGini关于Gini系数的讨论(一家之言)考察Gini系数的图像、熵、分类误差率三者之间的关系将f(x)=-lnx在x=1处一阶展开,忽略高阶无穷小,得到f(x)1-x()()=KkkkKkkkppppXH111lnGini系数的生成Gini系数的第二定义给定M个样本,计算样本最大值max和最小值min,等分成N份,计算每份的样本数目xi(i=1,2,N),则每份的近似概率为计算累积概率另:
NiMxpii,2,1,=NixMMxpijjijjiji,2,1,1111=1,00=N推导Gini系数阴影B的面积:
gini系数:
()=+=+=+=+=12211212121121111111111NiiNiiNiiNiiNiiNiiiNiiiBNNNNNS=100N()=+=1211212/12/11NiiBBBAANSSSSSxGiniNixMiiii2,1,11=三种决策树学习算法ID3:
使用信息增益/互信息g(D,A)进行特征选择取值多的属性,更容易使数据更纯,其信息增益更大。
训练得到的是一棵庞大且深度浅的树:
不合理。
C4.5:
信息增益率gr(D,A)=g(D,A)/H(A)CART:
基尼指数一个属性的信息增益(率)/gini指数越大,表明属性对样本的熵减少的能力更强,这个属性使得数据由不确定性变成确定性的能力越强。
决策树的评价假定样本的总类别为K个。
对于决策树的某叶结点,假定该叶结点含有样本数目为n,其中第k类的样本点数目为nk,k=1,2,K。
若某类样本nj=n而n1,nj-1,nj+1,nK=0,称该结点为纯结点;若各类样本数目n1=n2=nk=n/K,称该样本为均结点。
纯结点的熵Hp=0,最小均结点的熵Hu=lnK,最大对所有叶结点的熵求和,该值越小说明对样本的分类越精确。
各叶结点包含的样本数目不同,可使用样本数加权求熵和评价函数:
由于该评价函数越小越好,所以,可以称之为“损失函数”。
()()=leaftttHNTC鸢尾花数据决策树决策树的过拟合决策树对训练属于有很好的分类能力,但对未知的测试数据未必有好的分类能力,泛化能力弱,即可能发生过拟合现象。
剪枝随机森林剪枝三种决策树的剪枝过程算法相同,区别仅是对于当前树的评价标准不同。
信息增益、信息增益率、基尼系数剪枝总体思路:
由完全树T0开始,剪枝部分结点得到T1,再次剪枝部分结点得到T2直到仅剩树根的树Tk;在验证数据集上对这k个树分别评价,选择损失函数最小的树T剪枝系数的确定根据原损失函数叶结点越多,决策树越复杂,损失越大,修正:
当=0时,未剪枝的决策树损失最小;当=+时,单根结点的决策树损失最小。
假定当前对以r为根的子树剪枝:
剪枝后,只保留r本身而删掉所有的叶子考察以r为根的子树:
剪枝后的损失函数:
剪枝前的损失函数:
令二者相等,求得:
称为结点r的剪枝系数。
()()=leaftttHNTC()()leafTTCTC+=()()+=rCrC()()leafRRCRC+=()()1=leafRRCrC剪枝算法对于给定的决策树T0:
计算所有内部节点的剪枝系数;查找最小剪枝系数的结点,剪枝得决策树Tk;重复以上步骤,直到决策树Tk只有1个结点;得到决策树序列T0T1T2TK;使用验证样本集选择最优子树。
使用验证集做最优子树的标准,可以使用评价函数:
()()=leaftttHNTCBootstrapingBootstraping的名称来自成语“pullupbyyourownbootstraps”,意思是依靠你自己的资源,称为自助法,它是一种有放回的抽样方法。
注:
Bootstrap本义是指高靴子口后面的悬挂物、小环、带子,是穿靴子时用手向上拉的工具。
“pullupbyyourownbootstraps”即“通过拉靴子让自己上升”,意思是“不可能发生的事情”。
后来意思发生了转变,隐喻“不需要外界帮助,仅依靠自身力量让自己变得更好”。
Bagging的策略bootstrapaggregation从样本集中重采样(有重复的)选出n个样本在所有属性上,对这n个样本建立分类器(ID3、C4.5、CART、SVM、Logistic回归等)重复以上两步m次,即获得了m个分类器将数据放在这m个分类器上,最后根据这m个分类器的投票结果,决定数据属于哪一类AnotherdescriptionofBaggingOOB数据可以发现,Bootstrap每次约有36.79%的样本不会出现在Bootstrap所采集的样本集合中,将未参与模型训练的数据称为袋外数据OOB(OutOfBag)。
它可以用于取代测试集用于误差估计。
Breiman以经验性实例的形式证明袋外数据误差估计与同训练集一样大小的测试集精度相同;得到的模型参数是无偏估计。
Bagging随机森林随机森林在bagging基础上做了修改。
从样本集中用Bootstrap采样选出n个样本;从所有属性中随机选择k个属性,选择最佳分割属性作为节点建立CART决策树;重复以上两步m次,即建立了m棵CART决策树这m个CART形成随机森林,通过投票表决结果,决定数据属于哪一类应用实例:
KinectReal-TimeHumanPoseRecognitioninPartsfromSingleDepthImages,JamieShottonetc,2011,随机森林/Bagging和决策树的关系当然可以使用决策树作为基本分类器但也可以使用SVM、Logistic回归等其他分类器,习惯上,这些分类器组成的“总分类器”,仍然叫做随机森林。
举例回归问题回归问题离散点为臭氧(横轴)和温度(纵轴)的关系试拟合变化曲线使用Bagging算法过程做100次bootstrap,每次得到的数据Di,Di的长度为N对于每一个Di,使用局部回归(LOESS)拟合一条曲线(图中灰色线是其中的10条曲线)将这些曲线取平均,即得到红色的最终拟合曲线显然,红色的曲线更加稳定,并且没有过拟合明显减弱记原始数据为D,长度为N(即图中有N个离散点)Code投票机制简单投票机制一票否决(一致表决)少数服从多数有效多数(加权)阈值表决贝叶斯投票机制投票机制举例假定有N个用户可以为X个电影投票(假定投票者不能给同一电影重复投票),投票有1、2、3、4、5星共5档。
如何根据用户投票,对电影排序?
本质仍然是分类问题:
对于某个电影,有N个决策树,每个决策树对该电影有1个分类(1、2、3、4、5类),求这个电影应该属于哪一类(可以是小数:
分类问题变成了回归问题)一种可能的方案WR:
加权得分(weightedrating)R:
该电影的用户投票的平均得分(Rating)C:
所有电影的平均得分v:
该电影的投票人数(votes)m:
排名前250名的电影的最低投票数根据总投票人数,250可能有所调整按照v=0和m=0分别分析CmvmRmvvWR+=样本不均衡的常用处理方法假定样本数目A类比B类多,且严重不平衡:
A类欠采样Undersampling随机欠采样A类分成若干子类,分别与B类进入ML模型基于聚类的A类分割B类过采样Oversampling避免欠采样造成的信息丢失B类数据合成SyntheticDataGeneration随机插值得到新样本SMOTE(SyntheticMinorityOver-samplingTechnique)代价敏感学习CostSensitiveLearning降低A类权值,提高B类权值使用RF建立计算样本间相似度原理:
若两样本同时出现在相同叶结点的次数越多,则二者越相似。
算法过程:
记样本个数为N,初始化NN的零矩阵S,Si,j表示样本i和样本j的相似度。
对于m颗决策树形成的随机森林,遍历所有决策树的所有叶子结点:
记该叶结点包含的样本为sample1,2,k,则Sij累加1。
样本i、jsample1,2,k样本i、j出现在相同叶结点的次数增加1次。
遍历结束,则S为样本间相似度矩阵。
使用随机森林计算特征重要度随机森林是常用的衡量特征重要性的方法。
计算正例经过的结点,使用经过结点的数目、经过结点的gini系数和等指标。
或者,随机替换一列数据,重新建立决策树,计算新模型的正确率变化,从而考虑这一列特征的重要性。
selectionfrequencyginiimportancepermutationimportance再谈北京市区域犯罪率分析CodeIsolationForest随机选择特征、随机选择分割点,生成一定深度的决策树iTree,若干颗iTree组成iForest计算iTree中样本x从根到叶子的长度f(x)。
计算iForest中f(x)的总和F(x)异常检测:
若样本x为异常值,它应在大多数iTree中很快从根到达叶子,即F(x)较小。
降采样CodeCodeCode决策树:
Level随机森林:
30,重现随机森林:
30,Level随机森林:
4,Tree鸢尾花数据决策树PDFGraphviz决策树随机森林100决策树用于拟合多输出的决策树回归再谈北京市区域犯罪率分析Code总结决策树/随机森林的代码清晰、逻辑简单,在胜任分类问题的同时,往往也可以作为对数据分布探索的首要尝试算法。
随机森林的集成思想也可用在其他分类器的设计中。
如果通过随机森林做样本的异常值检测?
统计样本间位于相同决策树的叶结点的个数,形成样本相似度矩阵。
如果正负样本数量差别很大,如何处理?
思考:
在得到新决策树后,对样本的权值进行合理的调整分类正确的则降低权值,分类错误的则增大权值是否可行?
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2.2 机器 学习 模型 决策树 随机 森林 ok