相亲、交友与决策树

决策树学习方法初探——一个初学者的视角从我国的一个社会问题说起这是一个–愁坏父亲母亲–捧红了江苏卫视–却乐坏了马云（和宝强）–的问题从我国的一个社会问题说起剩男剩女问题引爆的商机–双十一的购物狂欢–交友婚介网站/节目的盛行–于是……尼玛希望能够帮助单身男女青年更好地选择交友对象–现状：尼玛已经收集了一些男同胞的资料–目标：为优秀的女性推荐与之匹配的男性–ButHow？•先看看现在相亲的基本的特征从我国的一个社会问题说起相亲的常见场景–有一些还没开始就失败了–有一些还是可能成功的•母亲：尼美，给你介绍个男朋友吧。•尼美：多大年纪了？•母亲：26。•尼美：长的怎么样？•母亲：挺帅的。•尼美：收入高不？•母亲：不算很高，中等情况。•尼美：是公务员不？•母亲：是，在税务局上班呢。•尼美：那好，我去见见。公务员教师财会程序猿见不见见见决策树的基本思想尼美（女，23岁，企业白领）是如何选择相亲对象的–尼美对对象的属性建模•性别，长相，年龄，收入，职业–尼美心中对对象筛选过程•性别：当然不能是女的•长相：要帅的•年龄：比自己大但小于30•收入：中等或以上•职业：收入中等则要稳定体面–尼美根据属性将男同胞们分类•见or不见2330不见不见中职业低高见不见23-30收入女不见不见不帅年龄帅男长相性别决策树的基本思想尼玛分析了尼美相亲判断过程的基本组成–测试结点•表示某种作为判断条件的属性–分支•根据条件属性取值选取的路径–叶子•使判断终止的结论尼美做选择时，其实用的是决策树–关键在于决策树如何构造2330不见不见公务员教师财会程序猿见不见见见中职业低高见不见23-30收入女不见不见不帅年龄帅男长相性别测试节点分支叶子决策树的基本思想尼玛得知尼美相亲决策树构造的基本思路–从一棵空决策树开始，选择某一属性作为分裂属性；–根据分裂属性的值的不同，可将训练样本分成若干子集；–如果该子集为空，或当前子集中的样本属于同一个类，则该子集为叶子结点；–否则继续以该子集作为测试结点，选择一个新的分类属性重复上述步骤对该子集进行划分，直至属性集为空或每个子集中的样本均属于同一各类。决策树的最基本功能——分类这个思路就是CLS算法–Hunt，Marin和Stone于1966年提出，决策树的雏形尼玛交友推荐系统的构造和优化尼玛决定开始构造自己的决策树–数据就是王道，尼玛公开了16组数据序号姓名职业分类职位评级收入水平有房有车债务情况评级1A金融A类高1低钻石男2BITA类中3高经适男3C行政A类中2低经适男4D司法A类高0低钻石男5E行政B类中3中牛奋男6F金融B类高3低钻石男7GITB类中2中牛奋男8H司法A类中2低经适男9J行政A类中0低经适男10K教育C类低3低牛奋男11L司法A类高3中钻石男12M教育C类低2低牛奋男13NITB类高0低牛奋男14P教育A类高2中经适男15Q教育C类低2低经适男16RITB类高2高牛奋男尼玛交友推荐系统的构造和优化尼玛构造的决策树–看上去像模像样–但是•两个绿圈里是什么鬼？IT金融司法行政教育0,1,32,1,00,2,10,2,22,0,0ABCABABBC1,1,00,2,1中1,1,031,1,0中低低0,1,121职业分类职位评级职位评级职位评级职位评级钻石男职位评级经适男牛奋男钻石男收入水平经适男牛奋男经适男收入水平有房有车债务水平经适男牛奋男有房有车经适男牛奋男尼玛交友推荐系统的构造和优化尼玛的导师愤怒了尼玛交友推荐系统的构造和优化面对老板之怒，尼玛决定求助尼美Yao尼玛尼美尼美，跪求你的相亲决策树如何去掉那些不必要的判断，5555构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。尼玛交友推荐系统的构造和优化面对老板之怒，尼玛决定求助尼美Yao尼玛尼美尼美，别光说“纯”好不好，我知道要“纯”，但怎么看“纯不纯”？55551948年，香农提出了“信息熵”的概念，解决了对系统信息的量化度量问题。尼美，shang是啥？这种概念我不懂，听了就觉得很受伤……5555别打岔，好好听！熵是描述系统混乱程度的度量。一个系统越是有序，信息熵就越低；反之，一个系统越乱，信息熵就越高。尼玛交友推荐系统的构造和优化尼美对熵的论述（其实应该是转述）–熵的数学定义•根据Shannon1948信息论理论。事件ai的信息量I可如下度量：其中p(ai)表示事件ai发生的概率。•给定样本S，包含n个互不相容的事件a1,a2,a3,….,an,它们中有且仅有一个发生，则其S平均的信息量可如下度量：)p(a)p(a)p(a)p(a)I(aiiiii22log-1logniiiniiapapaII121)(1log)()()S(尼玛交友推荐系统的构造和优化决策树的目标是让分裂子集尽量地“纯”–越纯则“熵”越低•因此使用“信息增益”定义每次属性分裂带来的熵的变化–将样本集S按属性A进行划分为一次属性分裂，则定义这一次分裂的期望熵为•其中v为分裂后子样本集的个数•I(Sj)为子样本集对目标分类的熵。–在定义好一次分裂的期望熵后，可以定义信息增益)(S1jAjvjSISSI)()()(AASISISGain尼玛交友推荐系统的构造和优化依据信息增益，可以辅助分裂属性的选择–选取信息增益最大的属性作为分裂属性–避免CLS中盲目选择导致的无意义选择节点ID3决策树算法的基本思路Hi，Guys！我是RossQuinlan，ID3是我的创造，希望大家喜欢，虽然ID3已经32岁了，但在我看来他还是个孩子。尼玛交友推荐系统的构造和优化尼玛使用ID3重新构造了自己的决策树–先计算目标分类的熵•S1=钻石男，S2=经适男，S3=牛奋男•|S1|=4，|S2|=6，|S3|=6•p1=0.25，p2=0.375，p3=0.375•I1=0.5，I2=0.5306，I3=0.5306•I(S)=1.5612序号姓名评级1A钻石男2B经适男3C经适男4D钻石男5E牛奋男6F钻石男7G牛奋男8H经适男9J经适男10K牛奋男11L钻石男12M牛奋男13N牛奋男14P经适男15Q经适男16R牛奋男尼玛交友推荐系统的构造和优化尼玛使用ID3重新构造了自己的决策树–再逐个计算各分裂属性的期望熵•职业分类5类•以从事IT行业的为例设为类1•经适男1个，牛奋男3个•I(S1)=0+（-0.25*log20.25）+(-0.75*log20.75)=0.8113序号职业分类评级1金融钻石男2IT经适男3行政经适男4司法钻石男5行政牛奋男6金融钻石男7IT牛奋男8司法经适男9行政经适男10教育牛奋男11司法钻石男12教育牛奋男13IT牛奋男14教育经适男15教育经适男16IT牛奋男尼玛交友推荐系统的构造和优化尼玛使用ID3重新构造了自己的决策树–再逐个计算各分裂属性的期望熵•职业分类5类•以从事金融行业的为例设为类2•钻石男2个•I(S2)=0序号职业分类评级1金融钻石男2IT经适男3行政经适男4司法钻石男5行政牛奋男6金融钻石男7IT牛奋男8司法经适男9行政经适男10教育牛奋男11司法钻石男12教育牛奋男13IT牛奋男14教育经适男15教育经适男16IT牛奋男尼玛交友推荐系统的构造和优化尼玛使用ID3重新构造了自己的决策树–再逐个计算各分裂属性的期望熵•职业分类5类•以从事行政行业的为例设为类3•经适男2个，牛奋男1个•I(S3)=0+（-0.6667*log20.6667）+(-0.3333*log20.3333)=0.9183序号职业分类评级1金融钻石男2IT经适男3行政经适男4司法钻石男5行政牛奋男6金融钻石男7IT牛奋男8司法经适男9行政经适男10教育牛奋男11司法钻石男12教育牛奋男13IT牛奋男14教育经适男15教育经适男16IT牛奋男尼玛交友推荐系统的构造和优化尼玛使用ID3重新构造了自己的决策树–再逐个计算各分裂属性的期望熵•职业分类5类•以从事司法行业的为例设为类4•钻石男2个，经适男1个•I(S4)=（-0.6667*log20.6667）+(-0.3333*log20.3333)+0=0.9183序号职业分类评级1金融钻石男2IT经适男3行政经适男4司法钻石男5行政牛奋男6金融钻石男7IT牛奋男8司法经适男9行政经适男10教育牛奋男11司法钻石男12教育牛奋男13IT牛奋男14教育经适男15教育经适男16IT牛奋男尼玛交友推荐系统的构造和优化尼玛使用ID3重新构造了自己的决策树–再逐个计算各分裂属性的期望熵•职业分类5类•以从事教育行业的为例设为类5•经适男2个，牛奋男2个•I(S1)=0+（-0.5*log20.5）+(-0.5*log20.5)=1序号职业分类评级1金融钻石男2IT经适男3行政经适男4司法钻石男5行政牛奋男6金融钻石男7IT牛奋男8司法经适男9行政经适男10教育牛奋男11司法钻石男12教育牛奋男13IT牛奋男14教育经适男15教育经适男16IT牛奋男尼玛交友推荐系统的构造和优化尼玛使用ID3重新构造了自己的决策树–综合得到按照职业分类进行属性分裂的期望熵•IA(S)=0.7972–同理可得按照其他属性分裂的期望熵•职为评级-IB(S)=1.0173•收入水平-IC(S)=1.3325•有房有车-ID(S)=1.2420•债务水平-IE(S)=1.7011–选取职业分类作为分裂属性时信息增益最高尼玛交友推荐系统的构造和优化尼玛使用ID3重新构造了自己的决策树–按职业分类分裂–接下去，如何选取下一级分裂属性？•以司法分支为例•对职业分类为司法的子表重新进行ID3运算IT金融司法行政教育0,1,32,1,00,2,10,2,22,0,0职业分类？？？？钻石男序号姓名职业分类职位评级收入水平有房有车债务情况评级4D司法A类高0低钻石男11L司法B类中3低钻石男8H司法B类中3中经适男尼玛交友推荐系统的构造和优化–以司法分支为例•目标分类的熵–0.9182•以职位评级分裂–1•以收入水平分裂–1•以有房有车分裂–1•以债务情况分裂–0–直接选取债务情况分裂序号姓名职业分类职位评级收入水平有房有车债务情况评级4D司法A类高0低钻石男11L司法B类中3低钻石男8H司法B类中3中经适男IT金融司法行政教育0,1,32,1,00,2,10,2,22,0,0职业分类？？？钻石男中低经适男牛奋男债务情况尼玛交友推荐系统的构造和优化–基于ID3的决策树的最终结构•成功消除了不该存在的无效分裂属性减少了搜索深度IT金融司法行政教育2,1,00,2,10,2,22,0,0职业分类钻石男中低经适男牛奋男债务情况0,1,3AB职位评级经适男牛奋男AB经适男牛奋男职位评级21有房有车经适男牛奋男尼玛交友推荐系统的构造和优化yao尼玛尼美尼美，你太棒了，现在可以回去跟老板交差了慢着！ID3还是有很多缺陷的：1、ID3选择分裂属性时趋向于多值属性；2、ID3无法处理连续的属性值；3、ID3不包含剪枝，易受噪声影响。就这样交差，肯定还是会被批评的……，还有这么多麻烦……，你举个栗子？尼玛交友推荐系统的构造和优化假如尼玛的数据是这样的(注意红字)序号姓名职业分类职位评级收入有房有车债务情况评级1A金融A类40W1低钻石男2BITA类18W3高经适男3C行政A类19W2低经适男4D司法A类35W0低钻石男5E行政B类11W3中牛奋男6F金融B类37.5W3低钻石男7GITB类12W2中牛奋男8H司法A类19.8W2低经适男9J行政A类24.2W0低经适男10K教育C类9.5W3低牛奋男11L司法A类50W3中钻石男12M教育C类11.8W2低牛奋男13NITB类17W0低牛奋男14P教育A类32W2中经适男15Q教育C类14W2低经适男16RIT