相亲、交友与决策树.pptx

,单击此处编辑母版标题样式,Click to edit Master text styles,Second level,Third level,Fourth level,#,决策树学习方法初探,一个初学者的视角,嘚儿个没,从我国的一个社会问题说起,这是一个,愁坏父亲,母亲,捧,红了江苏卫视,却乐坏了,马,云（和宝强）,的问题,从我国的一个社会问题说起,剩男剩女问题引爆的商机,双十一的购物狂欢,交友婚介网站,/,节目的盛行,于是,尼玛希望能够帮助单身男女青年更好地选择交友对象,现状：尼玛已经收集了一些男同胞的资料,目标：,为优秀的女性推荐与之匹配的,男性,But How,？,先,看看现在相亲的基本的特征,从我国的一个社会问题说起,相亲的常见场景,有一些还没开始就失败了,有一些还是可能成功的,母亲,：,尼美,，给,你介绍个男朋友,吧。,尼美：,多大年纪了,？,母亲,：,26,。,尼美,：,长,的怎么样？,母亲,：挺帅的,。,尼美,：,收入高不,？,母亲,：不算很高，中等情况,。,尼美,：,是公务员不,？,母亲,：是，在税务局上班呢,。,尼美,：,那好，我去见见。,决策树的基本思想,尼美（女，,23,岁，企业白领）是如何选择相亲对象的,尼美对对象的属性建模,尼美心中对对象筛选过程,性别：当然不能是,女,的,长相：要帅的,年龄：比自己大但小于,30,收入：中等或以上,职业：收入中等则要稳定体面,尼美根据属性将男同胞们分类,见,or,不见,决策树的基本思想,尼玛分析了尼美相亲判断过程的,基本组成,测试,结点,表示某种作为判断条件的属性,分支,根据条件属性取值选取的路径,叶子,使判断终止的结论,尼美做选择时，其实用的是决策树,关键在于决策树如何构造,测试,节点,分支,叶子,决策树的基本思想,尼玛得知尼美,相亲决策树构造,的基本思路,从一棵空决策树开始，选择某一,属性作为分裂属性；,根据,分裂,属性,的值,的不同,，可将训练样本,分成若干子集；,如果该,子,集为,空，,或当前子集,中的样本属于同一个类，则该子集为,叶子结点；,否则继续以该子集作为测试,结点,，选择,一个新的分类,属性重复上述步骤对,该子集进行,划分，直至属性集为空或每个子集中的样本均属于同一各类。,决策树的最基本功能,分类,这个思路就是,CLS,算法,Hunt,，,Marin,和,Stone,于,1966,年提出，决策树的雏形,尼玛,交友推荐系统的构造和优化,尼玛,决定开始构造自己的决策树,数据就是王道,，,尼玛公开了,16,组数据,序号,姓名,职业分类,职位评级,收入水平,有房有车,债务情况,评级,1,A,金融,A,类,高,1,低,钻石男,2,B,IT,A,类,中,3,高,经适男,3,C,行政,A,类,中,2,低,经适男,4,D,司法,A,类,高,0,低,钻石男,5,E,行政,B,类,中,3,中,牛奋男,6,F,金融,B,类,高,3,低,钻石男,7,G,IT,B,类,中,2,中,牛奋男,8,H,司法,A,类,中,2,低,经适男,9,J,行政,A,类,中,0,低,经适男,10,K,教育,C,类,低,3,低,牛奋男,11,L,司法,A,类,高,3,中,钻石男,12,M,教育,C,类,低,2,低,牛奋男,13,N,IT,B,类,高,0,低,牛奋男,14,P,教育,A,类,高,2,中,经适男,15,Q,教育,C,类,低,2,低,经适男,16,R,IT,B,类,高,2,高,牛奋男,尼玛,交友,推荐系统的构造和优化,尼玛构造的决策树,看上去像模像样,但是,两个绿圈里是什么鬼？,尼,玛交友,推荐系统的构造和优化,尼,玛的导师愤怒了,尼玛,交友,推荐系统的构造和优化,面对老板之怒，尼玛决定求助尼美,Yao,尼玛,尼美,尼美，跪求你的相亲决策树如何去掉那些不必要的判断，,5555,构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，,其目标是让各个分裂子集尽可能地“纯”,。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。,尼玛,交友,推荐系统的构造和优化,面对老板之怒，尼玛决定求助尼美,Yao,尼玛,尼美,尼美，别光说“纯”好不好，我知道要“纯”，但怎么看“纯不纯”？,5555,1948,年，香农提出了“,信息熵,”的概念，解决了对系统信息的量化度量问题。,尼美，,shang,是啥？这种概念我不懂，听了就觉得很受伤,5555,别打岔，好好听,！熵是描述系统混乱程度的度量。,一,个系统越是有序，信息熵就越低；反之，一个系统越乱，信息熵就越高。,尼玛,交友,推荐系统的构造和优化,尼美对熵的论述（其实应该是转述）,熵的数学定义,根据,Shannon1948,信息论,理论。,事件,a,i,的信息量,I,可如下,度量,：,其中,p(a,i,),表示事件,a,i,发生的概率。,给定样本,S,，包含,n,个互不相容的事件,a,1,a,2,a,3,.,a,n,它们中有且仅有一,个发生,，则,其,S,平均,的信息量可如下度量：,尼玛,交友,推荐系统的构造和优化,决策树的目标是让分裂子集尽量地“纯”,越纯则“熵”越低,因此使用“信息增益”定义每次属性分裂带来的熵的变化,将样本集,S,按,属性,A,进行,划分为一次属性分裂，则定义这一次分裂的期望熵为,其中,v,为分裂后子样本集的个数,I(S,j,),为子样本集对目标分类的熵。,在定义好一次分裂的期望熵后，可以定义信息增益,尼玛,交友,推荐系统的构造和优化,依据信息增益，可以辅助分裂属性的选择,选取信息增益最大的属性作为分裂属性,避免,CLS,中盲目选择导致的无意义选择节点,ID3,决策树算法的基本思路,Hi,，,Guys,！我是,Ross,Quinlan,，,ID3,是我的创造，希望大家喜欢，虽然,ID3,已经,32,岁了，但在我看来他还是个孩子。,尼玛,交友推荐系统的构造和优化,尼玛,使用,ID3,重新构造了自己的决策树,先计算目标分类的熵,S,1,=,钻石男，,S,2,=,经适男，,S,3,=,牛奋男,|S,1,|=4,，,|,S,2,|=6,，,|,S,3,|=6,p,1,=0.25,，,p,2,=,0.375,，,p,3,=0.375,I,1,=0.5,，,I,2,=0.5306,，,I,3,=0.5306,I(S)=1.5612,序号,姓名,评级,1,A,钻石男,2,B,经适男,3,C,经适男,4,D,钻石男,5,E,牛奋男,6,F,钻石男,7,G,牛奋男,8,H,经适男,9,J,经适男,10,K,牛奋男,11,L,钻石男,12,M,牛奋男,13,N,牛奋男,14,P,经适男,15,Q,经适男,16,R,牛奋男,尼玛,交友推荐系统的构造和优化,尼玛,使用,ID3,重新构造了自己的决策树,再逐个计算各分裂属性的期望熵,职业分类,5,类,以从事,IT,行业的为例,设,为类,1,经适,男,1,个，牛奋男,3,个,I(S,1,)=0+,（,-0.25,*,log,2,0.25,）,+,(-0.75*log,2,0.75)=0.8113,序号,职业分类,评级,1,金融,钻石男,2,IT,经适男,3,行政,经适男,4,司法,钻石男,5,行政,牛奋男,6,金融,钻石男,7,IT,牛奋男,8,司法,经适男,9,行政,经适男,10,教育,牛奋男,11,司法,钻石男,12,教育,牛奋男,13,IT,牛奋男,14,教育,经适男,15,教育,经适男,16,IT,牛奋男,尼玛,交友推荐系统的构造和优化,尼玛,使用,ID3,重新构造了自己的决策树,再逐个计算各分裂属性的期望熵,职业分类,5,类,以从事,金融,行业的为例,设,为类,2,钻石男,2,个,I(S,2,)=0,序号,职业分类,评级,1,金融,钻石男,2,IT,经适男,3,行政,经适男,4,司法,钻石男,5,行政,牛奋男,6,金融,钻石男,7,IT,牛奋男,8,司法,经适男,9,行政,经适男,10,教育,牛奋男,11,司法,钻石男,12,教育,牛奋男,13,IT,牛奋男,14,教育,经适男,15,教育,经适男,16,IT,牛奋男,尼玛,交友推荐系统的构造和优化,尼玛,使用,ID3,重新构造了自己的决策树,再逐个计算各分裂属性的期望熵,职业分类,5,类,以从事行政行业的为例,设,为类,3,经适,男,2,个，牛奋男,1,个,I(S,3,)=0+,（,-0.6667,*,log,2,0.6667,）,+,(-0.3333*log,2,0.3333)=0.9183,序号,职业分类,评级,1,金融,钻石男,2,IT,经适男,3,行政,经适男,4,司法,钻石男,5,行政,牛奋男,6,金融,钻石男,7,IT,牛奋男,8,司法,经适男,9,行政,经适男,10,教育,牛奋男,11,司法,钻石男,12,教育,牛奋男,13,IT,牛奋男,14,教育,经适男,15,教育,经适男,16,IT,牛奋男,尼玛,交友推荐系统的构造和优化,尼玛,使用,ID3,重新构造了自己的决策树,再逐个计算各分裂属性的期望熵,职业分类,5,类,以从事,司法,行业的为例,设,为类,4,钻石男,2,个，经适男,1,个,I(S,4,)=,（,-0.6667,*,log,2,0.6667,）,+,(-0.3333*log,2,0.3333)+0=0.9183,序号,职业分类,评级,1,金融,钻石男,2,IT,经适男,3,行政,经适男,4,司法,钻石男,5,行政,牛奋男,6,金融,钻石男,7,IT,牛奋男,8,司法,经适男,9,行政,经适男,10,教育,牛奋男,11,司法,钻石男,12,教育,牛奋男,13,IT,牛奋男,14,教育,经适男,15,教育,经适男,16,IT,牛奋男,尼玛,交友推荐系统的构造和优化,尼玛,使用,ID3,重新构造了自己的决策树,再逐个计算各分裂属性的期望熵,职业分类,5,类,以从事教育行业的为例,设,为类,5,经适,男,2,个，牛奋男,2,个,I(S,1,)=0+,（,-0.5,*,log,2,0.5,）,+,(-0.5*log,2,0.5)=1,序号,职业分类,评级,1,金融,钻石男,2,IT,经适男,3,行政,经适男,4,司法,钻石男,5,行政,牛奋男,6,金融,钻石男,7,IT,牛奋男,8,司法,经适男,9,行政,经适男,10,教育,牛奋男,11,司法,钻石男,12,教育,牛奋男,13,IT,牛奋男,14,教育,经适男,15,教育,经适男,16,IT,牛奋男,尼玛,交友推荐系统的构造和优化,尼玛,使用,ID3,重新构造了自己的决策树,综合得到按照职业分类进行属性分裂的期望熵,I,A,(S,)=,0.7972,同理可得按照其他属性分裂的期望熵,职,为,评级,-,I,B,(S)=1.0173,收入,水平,-,I,C,(S,)=,1.3325,有房有车,-,I,D,(S)=1.2420,债务,水平,-,I,E,(S)=1.7011,选取职业分类作为分裂属性时信息增益最高,尼玛,交友推荐系统的构造和优化,尼玛,使用,ID3,重新构造了自己的决策树,按职业分类分裂,接下去，如何选取下一级分裂属性？,以司法分支为例,对职业分类为司法的子表重新进行,ID3,运算,序号,姓名,职业分类,职位评级,收入水平,有房有车,债务情况,评级,4,D,司法,A,类,高,0,低,钻石男,11,L,司法,B,类,中,3,低,钻石男,8,H,司法,B,类,中,3,中,经适男,尼玛,交友,推荐系统的构造和优化,以司法分支为,例,目标分类的熵,0.9182,以职位评级分裂,1,以收入水平分裂,1,以有房有车分裂,1,以债务情况分裂,0,直接选取债务情况分裂,序号,姓名,职业分类,职位评级,收入水平,有房有车,债务情况,评级,4,D,司法,A,类,高,0,低,钻石男,11,L,司法,B,类,中,3,低,钻石男,8,H,司法,B,类,中,3,中,经适男,尼玛,交友,推荐系统的构造和优化,基于,ID3,的决策树的最终结构,成功消除了不该存在的无效分裂属性减少了搜索深度,尼玛,交友,推荐系统的构造和优化,yao,尼玛,尼美,尼美，你太棒了，现在可以回去跟老板交差了,慢着！,ID3,还是有很多缺陷的：,1,、,ID3,选择分裂属性时趋向于多值属性；,2,、,ID3,无法处理连续的属性值；,3,、,ID3,不包含剪枝，易受噪声影响。,就,这样交差，肯定还是会被批评的,，还有这么多麻烦,，你举个栗子？,尼玛,交友,推荐系统的构造和优化,假如,尼玛,的数据是这样的,(,注意,红,字,),序号,姓名,职业分类,职位评级,收入,有房有车,债务情况,评级,1,A,金融,A,类,40W,1,低,钻石男,2,B,IT,A,类,18W,3,高,经适男,3,C,行政,A,类,19W,2,低,经适男,4,D,司法,A,类,35W,0,低,钻石男,5,E,行政,B,类,11W,3,中,牛奋男,6,F,金融,B,类,37.5W,3,低,钻石男,7,G,IT,B,类,12W,2,中,牛奋男,8,H,司法,A,类,19.8W,2,低,经适男,9,J,行政,A,类,24.2W,0,低,经适男,10,K,教育,C,类,9.5W,3,低,牛奋男,11,L,司法,A,类,50W,3,中,钻石男,12,M,教育,C,类,11.8W,2,低,牛奋男,13,N,IT,B,类,17W,0,低,牛奋男,14,P,教育,A,类,32W,2,中,经适男,15,Q,教育,C,类,14W,2,低,经适男,16,R,IT,B,类,19.2W,2,高,牛奋男,尼玛,交友推荐系统的构造和优化,尼玛,使用,ID3,重新构造了自己的决策树,按照各种分类进行属性分裂的期望熵,职业分类,-,I,A,(S)=,0.7972,职位评级,-,I,B,(S)=1.0173,收入,-,I,C,(S)=,0!,(,这是感叹号，不是阶乘,),有房有车,-,I,D,(S)=1.2420,债务,水平,-,I,E,(S)=1.7011,尼玛,交友,推荐系统的构造和优化,生成的决策树会是这样滴,这样的分类可用吗？,现在有,X,男，年收入,40.1W,，查无此分支,这样的分类有意义吗？,分类不具有代表性,ID,号也会成为最佳的分裂属性,OMG,！,尼玛,交友,推荐系统的构造和优化,关于收入这个分裂属性的特征,多,值属性,分裂,子集小，所以分裂的期望熵较低,分裂,属性的值本身引入了较大的混乱度,收入是连续型变量,将其当作离散数据分析无法形成正确的分类,如何解决这些问题,尼玛,交友,推荐系统的构造和优化,C4.5,决策树算法的基本,思路,采用,信息增益率,取代信息增益作为分裂属性选取的标准,对连续型的属性值进行,离散化,Hey,，,Guys,！可以尝试下,C4.5,。我用了,三,年时间来解决这些问题。你值得拥有,尼玛,交友,推荐系统的构造和优化,信息增益率的定义,设样本集,S,按离散,属性,A,的,V,个不同的取值划分,为,S,1,S,2,S,V,，共,V,个,子集,定义分裂指数,表示这次分裂行为引入的混乱程度,则信息增益率定义为,尼玛,交友推荐系统的构造和优化,尼玛,使用,C4.5,重新评估各项分裂属性,Gain,A,(S,)=0.7640,Splite,A,(S)=1.8806GainRatio,A,=0.4063,Gain,B,(S,)=0.5439,Splite,B,(S)=1.8772,GainRatio,B,=0.2897,Gain,C,(S)=,1.5612,Splite,C,(,S,)=4.0,GainRatio,C,=,0.3903,Gain,D,(S)=,0.3192,Splite,D,(S)=,1.8606,GainRatio,D,=0.1716,Gain,E,(S)=,-,0.1399,Splite,E,(S)=,1.3766,GainRatio,E,=-0.1016,通过信息增益率，可以回避选择离散的收入作为分裂属性,尼玛,交友,推荐系统的构造和优化,事实上，,收入,是个连续变量，不能做离散值处理,对连续变量进行离散化，变为若干个离散的区间,尼玛,交友,推荐系统的构造和优化,分割区间的策略,从排序数据两端向中间移动分割边界,y,和,y,；,计算分割出的三个子集的信息增益率；,按照信息增益率最高的分割选取,y,和,y,；,新,的划分的信息增益率为：,0.5409,大于,GainRatioA=0.4063,应该选取连续型的收入作为第一级分裂属性,收入,属性按照选取的边界分割成三个区间,尼玛,交友推荐系统的构造和优化,决策树的剪枝,为什么要剪枝？,数据中有噪音、训练数据量少和过拟合,会,导致出现错误的分类,如何剪枝？,根据错误分类出现的情况，去掉部分子树,尼玛,交友推荐系统的构造和优化,剪枝的简单示例,病毒分类树（,C4.5,）,使用样本数据分析,有五,个错误分类样例,病毒,id,特征,A,特征,B,特征,C,类别,错分类,1,Y,Y,Y,阳,2,Y,Y,Y,阳,3,Y,Y,Y,阳,4,Y,Y,Y,阳,5,Y,Y,Y,阳,6,Y,Y,N,阴,*,7,Y,Y,N,阴,*,8,Y,Y,N,阴,*,9,Y,N,Y,阳,10,Y,N,Y,阳,11,Y,N,Y,阳,12,Y,N,Y,阳,13,Y,N,N,阳,*,14,Y,N,N,阳,*,15,Y,N,N,阴,16,Y,N,N,阴,17,Y,N,N,阴,18,N,N,N,阴,19,N,Y,N,阴,20,N,Y,Y,阴,A,B,负,C,正,正,负,Y,Y,Y,N,N,N,尼玛交友,推荐系统的构造和优化,第,1,步、决策树规则化（,C4.5,表示决策树的方法）,规则,1 IF A=Y AND B=Y,THEN,阳,规则,2 IF A=Y AND B=N AND C=Y,THEN,阳,规则,3 IF A=Y AND B=N AND C=N,THEN,阴,规则,4 IF A=N,THEN,阴,A,B,负,C,正,正,负,Y,Y,Y,N,N,N,尼玛,交友,推荐系统的构造和优化,第,2,步 规则精度的,计算,规则,1 IF A=Y AND B=Y,THEN,阳,规则,2 IF A=Y AND B=N AND,C=Y,THEN,阳,规则,3 IF A=Y AND B=N AND,C=N,THEN,阴,规则,4 IF A=N,THEN,阴,规则,分类正确的数目,分类错误的数目,精度,1,5,3,5/8,2,4,0,4/4,3,3,2,3/5,4,3,0,3/3,尼玛,交友,推荐系统的构造和优化,第,3,步 对规则进行修剪,规则,2,与规则,4,精度为,100%,，保留,规则,1,和,3,引入了错误，进行判断条件的筛选,规则,1,使用特征,A,和特征,B,规则,3,使用了特征,A,、特征,B,和特征,C,建立特征子集引入错误率的对比表,规则,去掉,A,去掉,B,去掉,C,去掉,AB,去掉,BC,去掉,AC,如何裁剪,1,5/10,11/17,去掉,B,3,4/6,6/8,3/9,8/10,4/10,6/17,去掉,AB,尼玛,交友,推荐系统的构造和优化,第,4,步、裁剪规则,规则,1 IF A=Y,AND B=Y,THEN,阳,18,19,20,规则,2 IF A=Y AND B=N AND C=Y,THEN,阳,9,10,11,12,规则,3,IF A=Y AND B=N AND,C=N,THEN,阴,6,7,8,13,14,15,16,17,规则,4 IF A=N,THEN,阴,1,2,3,4,5,依然,还有,13,、,14,两个错误，但是显著降低了,错误率,尼玛,交友,推荐系统的构造和优化,SB,技术员,尼美,你现在真的可以回去交差了，,C4.5,足够解决很多问题了,非常感谢！但是，我还有个问题,，我们公司要面向的是单身女青年,们,，会不会众口难调啊,你逐渐开窍了，确实存在这样的问题，每个人关注的属性不同、每个人的评价标准也不同，还好我们有随机森林,尼玛,交友,推荐系统的构造和优化,随机,森林,一个很,不严肃的的,解释,尼美有几个闺蜜,小龙包,如花,凤姐,吃货女青年,关注男士属性,究极文艺女青年,关注男士属性,拜金女青年,关注男士属性,尼玛,交友,推荐系统的构造和优化,随机,森林,一个很,不严肃的的,解释,每个闺蜜都为,SB,公司建立相亲决策树,小龙包采样,建树,剪枝,尼玛,交友,推荐系统的构造和优化,随机,森林,一个很,不严肃的的,解释,每个闺蜜都为,SB,公司建立相亲决策树,小龙包采样,建树,剪枝,如花采样,建树,剪枝,尼玛,交友,推荐系统的构造和优化,随机,森林,一个很,不严肃的的,解释,每个闺蜜都为,SB,公司建立相亲决策树,小龙包采样,建树,剪枝,如花采样,建树,剪枝,尼玛,交友,推荐系统的构造和优化,随机森林,一个很不严肃的的,解释,基于随机森林的分类,分别使用森林中的树分类,表决产生最后的分类,对每一个分类树,不需要使用样本的所有属性,尼玛,交友,推荐系统的构造和优化,SB,技术员,尼美,今天不能再讲得更多了，以后有机会再聊,叩谢大恩，可以跟老板交差去了,记得帮我推荐个好对象哈,关于决策树的未尽事宜,关于分裂属性选择参数,Gini,系数（,CART,算法最初使用）,Towing Criteria,2,分布（,CHAID,算法使用）,效果几乎没有太大差别,关于决策树的未尽事宜,关于剪枝,后,剪枝是常用手段，主要技术有,降低错误剪枝,REP,悲观,错误剪枝,PEP,基于错误剪枝,EBP,（,C4.5,的剪枝技术）,代价,-,复杂度剪枝,CCP,（,CART,算法的剪枝技术）,最小,错误剪枝,MEP,各,有各得适用场合，因地制宜地用,关于决策树的未尽事宜,其他著名而关键的算法,CART-,分类回归树,使用二叉树代替多叉数,支持回归分析,Adaboosting,严格意义上说不是决策树方法,而是对决策树的优化方法（个人见解，还需要在研究）,随机森林,涉及的技术细节很多，我讲的很不严肃,52,谢 谢,!,请批评,指正,2014/05/29,演讲完毕，谢谢观看！,