相亲、交友与决策树.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算法最初使用 TowingCriteria 2分