相亲、交友与决策树.ppt

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