相亲交友与决策树

决策树学习方法初探

——一个初学者的视角嘚儿个没从我国的一个社会问题说起这是一个愁坏父亲母亲捧红了江苏卫视却乐坏了马云（和宝强）的问题从我国的一个社会问题说起剩男剩女问题引爆的商机双十一的购物狂欢交友婚介网站/节目的盛行于是……尼玛希望能够帮助单身男女青年更好地选择交友对象现状：尼玛已经收集了一些男同胞的资料目标：为优秀的女性推荐与之匹配的男性ButHow？先看看现在相亲的基本的特征从我国的一个社会问题说起相亲的常见场景有一些还没开始就失败了有一些还是可能成功的母亲：尼美，给你介绍个男朋友吧。尼美：多大年纪了？母亲：26。尼美：长的怎么样？母亲：挺帅的。尼美：收入高不？母亲：不算很高，中等情况。尼美：是公务员不？母亲：是，在税务局上班呢。尼美：那好，我去见见。决策树的基本思想尼美（女，23岁，企业白领）是如何选择相亲对象的尼美对对象的属性建模<性别，长相，年龄，收入，职业>尼美心中对对象筛选过程性别：当然不能是女的长相：要帅的年龄：比自己大但小于30收入：中等或以上职业：收入中等则要稳定体面尼美根据属性将男同胞们分类见or不见决策树的基本思想尼玛分析了尼美相亲判断过程的基本组成测试结点表示某种作为判断条件的属性分支根据条件属性取值选取的路径叶子使判断终止的结论尼美做选择时，其实用的是决策树关键在于决策树如何构造测试节点分支叶子决策树的基本思想尼玛得知尼美相亲决策树构造的基本思路从一棵空决策树开始，选择某一属性作为分裂属性；根据分裂属性的值的不同，可将训练样本分成若干子集；如果该子集为空，或当前子集中的样本属于同一个类，则该子集为叶子结点；否则继续以该子集作为测试结点，选择一个新的分类属性重复上述步骤对该子集进行划分，直至属性集为空或每个子集中的样本均属于同一各类。决策树的最基本功能——分类这个思路就是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高牛奋男尼玛交友推荐系统的构造和优化尼玛构造的决策树看上去像模像样但是两个绿圈里是什么鬼？尼玛交友推荐系统的构造和优化尼玛的导师愤怒了尼玛玛交友友推荐荐系系统统的的构构造造和和优优化化面对对老老板板之之怒怒，，尼尼玛玛决决定定求求助助尼尼美美Yao尼玛玛尼美美尼美美，，跪跪求求你你的的相相亲亲决决策策树树如如何何去去掉掉那那些些不不必必要要的的判判断断，，5555构造造决决策策树树的的关关键键步步骤骤是是分分裂裂属属性性。。所所谓谓分分裂裂属属性性就就是是在在某某个个节节点点处处按按照照某某一一特特征征属属性性的的不不同同划划分分构构造造不不同同的的分分支支，，其目目标标是是让让各各个个分分裂裂子子集集尽尽可可能能地地““纯纯””。尽尽可可能能““纯纯””就就是是尽尽量量让让一一个个分分裂裂子子集集中中待待分分类类项项属属于于同同一一类类别别。。尼玛玛交友友推荐荐系系统统的的构构造造和和优优化化面对对老老板板之之怒怒，，尼尼玛玛决决定定求求助助尼尼美美Yao尼玛玛尼美美尼美美，，别别光光说说““纯纯””好好不不好好，，我我知知道道要要““纯纯””，，但但怎怎么么看看““纯纯不不纯纯””？？55551948年，，香香农农提提出出了了““信息息熵熵”的的概概念念，，解解决决了了对对系系统统信信息息的的量量化化度度量量问问题题。。尼美美，，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序号姓名评级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运算序号姓名职业分类职位评级收入水平有房有车债务情况评级4D司法A类高0低钻石男11L司法B类中3低钻石男8H司法B类中3中经适男尼玛交友推荐系统的构构造和优化以司法分支为为例目标分类的熵熵–0.9182以职位评级分分裂–1以收入水平分分裂–1以有房有车分分裂–1以债务情况分分裂–0直接选取债务务情况分裂序号姓名职业分类职位评级收入水平有房有车债务情况评级4D司法A类高0低钻石男11L司法B类中3低钻石男8H司法B类中3中经适男尼玛交友推荐系统的构构造和优化基于ID3的决策树的最最终结构成功消除了不不该存在的无无效分裂属性性减少了搜索索深度尼玛交友推荐系统的构构造和优化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低经适男16RITB类19.2W2高牛奋男尼玛交友推荐系统统的构造和优优化尼玛使用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）使用用样样本本数数据据分分析析有五五个错错误误分分类类样样例例病毒id特征A特征B特征C类别错分类1YYY阳2YYY阳3YYY阳4YYY阳5YYY阳6YYN阴*7YYN阴*8YYN阴*9YNY阳10YNY阳11YNY阳12YNY阳13YNN阳*14YNN阳*15YNN阴16YNN阴17YNN阴18NNN阴19NYN阴20NYY阴AB负C正正负YYYNNN尼玛玛交交友友推荐荐系系统统的的构构造造和和优优化化第1步、、决决策策树树规规则则化化（（C4.5表示示决决策策树树的的方方法法））规则则1IFA=YANDB=YTHEN阳规则则2IFA=YANDB=NANDC=YTHEN阳规则则3IFA=YANDB=NANDC=NTHEN阴规则则4IFA=NTHEN阴AB负C正正负YYYNNN尼玛玛交友友推荐荐系系统统的的构构造造和和优优化化第2步规规则则精精度度的的计算算规则则1IFA=YANDB=YTHEN阳规则则2IFA=YANDB=NANDC=YTHEN阳规则则3IFA=YANDB=NANDC=NTHEN阴规则则4IFA=NTHEN阴规则分类正确的数目分类错误的数目精度1535/82404/43323/54303/3尼玛玛交友友推荐荐系系统统的的构构造造和和优优化化第3步对对规规则则进进行行修修剪剪规则则2与规规则则4精度度为为100%，保保留留规则则1和3引入入了了错错误误，，进进行行判判断断条条件件的的筛筛选选规则则1使用用特特征征A和特特征征B规则则3使用用了了特特征征A、特特征征B和特特征征C建立立特特征征子子集集引引入入错错误误率率的的对对比比表表规则去掉A去掉B去掉C去掉AB去掉BC去掉AC如何裁剪15/1011/17去掉B34/66/83/98/104/106/17去掉AB尼玛玛交友友推荐荐系系统统的的构构造造和和优优化化第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足够解决决很多问问题了非常感谢谢！但是是，我还还有个问问题……，我们公公司要面面向的是是单身女女青年们，会不会会众口难难调啊你逐渐开开窍了，，确实存存在这样样的问题题，每个个人关注注的属性性不同、、每个人人的评价价标准也也不同，，还好我我们有随随机森林林尼玛交友推荐系统统的构造造和优化化随机森林——一个很不严肃的的的解释