决策树(哈佛大学笔记)

基于数据挖掘算法的客户行为分析系统 文献翻译 1 决策树 哈佛大学笔记 决策树 哈佛大学笔记 计 074 曹琦 摘要 大多数的商业决策包括一些不确定的种类 可以决定药品公司的研发投资 例 如 不知道 FDA 可能会批准其产品 汽车制造商可以选择建造大型工厂来扩大经济规 模 而在不知道这个市场是否足够大的前提下允许工厂竭尽全力地工作 虽然不确定 性会让人生畏 然而你会发现 通过对事件设置集合 会产生一种系统的方法 根据 决议的不确定性预测你的行为 你可以做出更好的决定 这个笔记阐述了一套技术来分析不确定性的决策 你将能够运用这些技术来分级 有三个特点 1 替代选择是明确定义的 2 关键的不确定因素是可以被量化的 3 目的是清楚的 不是所有的决定都有这些特点 然而许多决定可以用上述三种性能拥有的一种方 式简化 因为带着这三个特性的决策可以直接地解决 你会发现优秀的决策者的能力 是把复杂的问题以上述特征的方式简化 你将学会如何构建这些被称作决策树的图形设备 决策树遵从两个宗旨 首先 他们 告诉你哪些备选方案可以选择 第二 他们把这些确定的备选方案的价值放在第一位 关键词 决策树 概率树 实例 1 一个简单的商业问题 Allison TAte 经营一家小公司 生产低成本的 符合人体工学的椅子在互联网上出 售 她的公司有几种流行的模型 每个年销售额达 20 万美元到 45 万美元 她的研究人员已经生产了一个模型 在几个方面把模型升级到顶级 然而由于新 椅子的改造数量 Allison 不期望有能力去用她现有工厂设施去生产 Allison 知道 一 个新的设备将花费 30 万美元 还不确定是否有足够的椅子需求来回报这么大的投资 如果市场良好 她认为她可能卖出 8000 把椅子 每把椅子获利 100 美元 产生 80 万 美元的现金流量 而另一方面 如果市场很萧条 她认为她可能只会卖出 1000 把椅子 产生现值只有 10 万美元的现金流量 她该怎么做出决定呢 在决定的结果不确定的情况下 当我们可以确定如何做出决定之前 我们需要一 个方法来确定未知的价值前景 不确定的利润和损失的评估可以利用一种被称作概率 树的装置 在接下来的章节 我们展示如何让 Allison 用概率树来进行投资价值的评估 然后 在接下来的部分里 我们允许 Allison 做序列决定 这是需要使用一种被称为决 策树的设备来完成 2 概率树 Allison 投资机会的价值是什么 基于数据挖掘算法的客户行为分析系统 文献翻译 2 如果 Allison 投资该工厂生产新椅子 要花费 30 万美元 如果市场很大 销售的 现金流量将达 80 万美元 如果 Allison 预先知道将是巨大的市场 那么她的决定很容 易 她要开始投资 因为这个项目值得你花 50 万美元 约合 80 万减去的投资成本 30 万 美元 然而她的决定很艰难 因为她不知道市场会是大还是小 如果椅子的市场很小 现金流销售额将只有 10 万美元 在这种情况下 她就会损失 20 万美元 10 万美元减去 的投资 30 万美元成本 她该怎么考虑现在的投资机会呢 她开始列出可供选择的结 果 如果她投资 如图 2 1 图图 2 12 1 她已确定投资成本为 30 万美元的前提下 她该如何权衡有可能获得 80 万美元与 毫无疑问地获得 10 万美元呢 直觉地 Allison 会更倾向于做这样一个投资 这个市场 将很大 不太可能是很小的 这样的一个事件可发生的概率用数字来表示 如果这个 事件是不可能的 我们将它们分配给概率为 0 在另一端的频率 如果一个事件是肯定 要发生的概率 我们给它分配一个概率 1 世界上的大多数真实的事件都发生在这二种 极端之间 它们发生的几率在 0 到 1 之间 更有可能被指派更高的可能性 为了决定是否在工厂投资 Allison 需要确定市场将会很大的可能有多少 考虑到 她所知道的市场 她推论 椅子是崭新的设计 并且小市场的可能性略略大于大市场 的可能性 那就是 小市场的可能性超过一半 另一方面 仍然有机会是大市场 她 决定的大市场的可能性为 0 40 由于概率的总和的两个结果必须等于一个 小市场的 可能性为 0 60 评估很大的市场的概率为 40 为意味着她认为这是可能会从一个含有 40 红色和 60 黑球的罐子得出一个红色球 有了这些信息 她现在可以构建一个简单的 概率树来代表价值的投资机会 图图 2 22 2 基于数据挖掘算法的客户行为分析系统 文献翻译 3 什么是她的投资期望值 假设我们重放的情景很多次 40 的次数 Allison 期望建 立 80 万美元 其中 60 的时候 她期望能获得 10 万美元 然而 她总是所投资的成 本的 30 万英镑 她期待平均现金流量遵从下面 图图 2 32 3 以上方程计算的是预期投资机会的货币价值 预期概率树的金融价值是概率加权 的平均结果 Allison 的投资预期的货币价值是这棵树预期的货币价值 去除了她的投 资花费 Allison 有一个预计为 8 万美元货币价值的机会 为了最大化回报她的股东 Allison 应选择投资 因为它提供了一个预期较高的货币价值而不是投资 2 1 评估更复杂的概率的树 另一个更加复杂的 有风险的前景的评估可以以同样的方式存在一个简单问题之 上 假设这是一个机会 创新且极具争议的椅子会出现在美国的电视观众面前 这将 使销售额增加到四倍 320 万美元 如果市场很大 如果市场很小 则增加到 40 万美元 Allison 估计 如果市场很大 她的产品出现在电视上的几率为 10 如果市场很小则 只有 1 我们能像下面一样扩充树 图图 2 42 4 这树的价值是什么 一如既往 概率树的预期货币价值是概率加权平均的结果 为得到某一结果 我们在树的树枝上乘以概率 因此 市场良好可能性并且有电视推 广就等于 0 40 x 0 10 0 04 同样 市场良好的可能性和没有宣传片等于 0 40 x 0 90 0 36 我们为树的每个树枝做如下的计算 基于数据挖掘算法的客户行为分析系统 文献翻译 4 图图 2 52 5 如果做得好 金额结果的概率应该等于 1 我们检查 0 04 0 36 0 006 0 594 1 得到预期的货币价值 我们采取概率加权平均这四个结果 总结产品的产出与每个 产出的可能性 这提供给我们 0 04x3 200 000 0 36x800 000 0 006x400 000 0 594x100 000 477 800 因此投资机会的价值 净成本是 477 800 300 000 177 800 根据我们刚刚分析过的概率树 Allison 一点也不需要随着解决的不确定性而做任 何决定 她之要通过计算的概率树找出投资机会的价值预期的货币的价值 通过辨识 出这个价值 她只需要简单的比较成本的投资 我们如何修改分析来考虑这样的事实 我们经常可以随着时间的推移通过做出决策来控制部分事件 为了分析了一系列的决 定 搞清楚哪里有不确定性 决策者经常使用了一种叫做决策树的设备 它像一个概 率树一样 提出了一个简单的图形的方式代表一个发生时间的先后顺序 决策树也允 许解决沿途的不确定性 我们从左到右地画决策树 强调决策的时序自然 决策树遵循两个主要的目标 首先 他们帮助你确定哪些决定风险较大 在每个 决定节点 你将面临着一些选择 通过使用决策树 你将能够在两者之间做出正确的 选择 第二 决策树识别任何特定决策的价值或者选项集 例如 你可能不但想知道 你是否比起一个选择更钟情另一个 还要想知道有多钟情 有时 你可能也想知道在 某一个点上做出决策 有多少价值 决策树有三种重要元素 1 决策被表示成一个正方形 或决策节点 这个节点可用来借鉴决定投资或不 投资 购买一台设备或者不购买 或要花费多少在拍卖中竞价 2 不确定事件被描绘成一个圆圈 或机会节点 不确定的事件的决策可能发生 之前或之后的 或两者之前和之后 3 结果描绘成一个三角形 决策过程到达这样一个结果 当所有的不确定性被 解决 也没有进一步的决定 在这一点上 决策者知道他将会得到回报 结果可以发 生在一个复杂的决定的不同阶段 例如 如果决策是要继续还是放弃 当继续的选择 可能会导致未来决策或导致不确定时 放弃的选择就是结果 决策树的三个要素与决策树线联系在一起 虽然我们不画出它们 你可以认为箭 头的方向的从左到右去 在相同的方向的年代的决定 这条线通常被叫做 分支 因 为做出决策可能会导致以后的决定 等等 基于数据挖掘算法的客户行为分析系统 文献翻译 5 决策树链接的外形的次序是非常重要的 例如 一个正方形后面跟着一个圆 意 味着决定在不确定问题的解决之前就被制定了 相比之下 一个圆接着一个正方形代 表着不确定问题的解决之后的才做的决策 3 一个简单的决策问题 Allison 的人体工程学椅子 让我们回到我们的简单的例子来说明相关的原则在构建和求解决策树 之前我们 看到 Allison TAte 面临着决定是否在新工厂上投资 30 万美元 当她无法确定椅子是否 有足够的需求来产生巨大的投资回报 她知道如果市场很大 她将出售 8000 把椅子 产生每人 100 美元的利润 80 万美元的现金流量 另一方面 如果市场很小 她将只 能卖出 1000 把椅子 产生只有 10 万美元的现金流量 一家市场研究公司曾提出一项提案用来评估椅子的潜在的市场 Allison 相信 这 次将解决不确定的市场是大还是小的问题 但她不知道它是否值得 5 万美元来进行调 查 她该怎么决定 是否支付市场调查 3 1 设计树 第一步 列出备选方案 决策树是向前设计的 一次一根树枝 从第一个决定开始 Allison 必须决定是否 投资市场研究 在她做出投资决策之后再做市场投资研究是毫无意义的 因为研究价 值是可以帮助人们做出投资决策 因为我们从决策开始 有两种选择 我们画一个正 方形 两条线从中穿过 图图 3 13 1 我们追踪了他们产生的成本 和福利 低于最顶端的树枝 我们标注了 5 万的成 本 如果 Allison 不研究 她则没有成本 因此我们在底部树枝写个零 现在该做什么了呢 我们从顶部开始 市场调研会确认市场机会是好或坏 Allison 不确定这些事件是否会发生 基于数据挖掘算法的客户行为分析系统 文献翻译 6 图图 3 23 2 因为市场调研的结果超出了她的掌控 我们用一个圆圈标记不确定性的决议 为 什么没有现金流量和这两个分支有关联呢 尽管研究结果可能会影响她的行动的方向 然而没有直接的现金流量和研究调查结果有关 接下来会发生些什么呢 根据研究结果调查 Allison 能购买新设备 或放弃生产 新椅子 如果市场很大 她若采购新设备则需花费 30 万美元 她将收到随后的 80 万 美金的收入 相反 如果市场很小 那么如果她采购新设备要花费 30 万美元现金流量 产量为 10 万美元 在这两种情况下 如果她放弃该项目 她的现金流将被初始化为 0 图图 3 33 3 最后 我们重复这些步骤 Allison 不打算花钱做市场研究 注意 树的一部分不 含进一步的决定 就像我们更早些时候分析的概率树 树的上 下部分的差别是在下 半部分 Allison 必须在不确定市场规模的前提下做出决定 然而上半部分已经知道了市 场容量在她使她来做出投资决策 据此 最后的决策树是 基于数据挖掘算法的客户行为分析系统 文献翻译 7 图图 3 43 4 第二步 量化的不确定性 正如概率树所描述的那样 Allison 必须估计 每个分支机构概率的结果发生的不 确定性 我们已经在前面的章节为树的下半部分做好了这点 回想起 Allison 相信好 机会的可能性是 0 4 而不好的机会则为 0 6 如果我们观察决策树半段的顶部 会发现只有一个带两个结果的机会节点 符合 销售机会是好或坏的研究结论 Allison 认为研究报告是 100 准确的 所以研究结果说 这个市场很大的可能性是什么 该研究将报告指出一个大市场的准确时间市场其实很 大 根据 Allison 所说 发生的概率为 0 4 同样概率的研究报告说小市场的概率为 0 6 我们现在有足够的信息填写其余的树 图图 3 53 5 为便于查询 我们把决策树的重要节点标记为 A B C D 第三步 指定目标 当 Allison 在备选方案里选择的时候 她的目标应该是什么 在我们以往的分析中 我们假定 Allison 的目标是做出决策来提供最高的货币价值 这个目标的选择可能出现的问题 因为似乎认为 Allison 是中性风险者 也就是说 她 基于数据挖掘算法的客户行为分析系统 文献翻译 8 所评估的概率树是在预期货币价值的时候 Allison 认为 80 万美元的几率为 40 10 万美元的几率是 60 预计货币价值为 38 万美元 作为相当于 38 万美元是毫无疑问 的 然而 多数人都喜欢风险规避 也就是说 他们喜欢得到一场赌博的期望值而不 是赌博本身 在 Allison 的案例中 这意味着她可能更喜欢投资而获得 30 万美元 而 毫无疑问的获得 38 万美元的回报 举一个简单的例子 大多数人都宁愿选择毫无疑问 地获得 100 美元而不是有 50 的几率获得 200 美元 然而 最大化的期望值对于大多数商业决策是一个合理的起点 以这个决策规则 为基础的是两条重要的假设 首先 我们认为决策者正试图代表多样化的投资者做出 最好的决定 如果每个投资者只持有 Allison 的公司比例仅有很小的一部分投资组合 Allison 公司的风险几乎没有影响投资者的整体的财富 其次 我们假设树的不确定性 与投资者的投资组合的风险无关 在我们的例子背景下这意味着人体工程学椅子的市 场优惠的可能性与的证券市场的整体表现无关 当然 这些假设可能有时会被违反 如果 Allison 是她公司的唯一拥有人 并且她 的大部分财富套牢在公司 然后她可以采取规避风险的方式 避免投资的时候 遇到 一个非常具有风险的预期货币价值 风险规避程度可以纳入我们的分析 通过使决策 者为每一个结局指定一个实用工具 测量她对那个结果增加或是减弱的满意程度 然后允许她最大化期望效用而不是期望价值 预计的货币的价值最大化是一个想当简单的决策规则 然而当决策者面临的风险都不 是很大的大多数情况下 这是个好的第一近似 所以在这个笔记里 我们将继续假设 Allison 的关于预期货币价值的一组不确定的价值观 这就是说 当面对两个或两个以 上的选择 她总是要选择有最高预期的货币的价值 无论什么风险 在决策节点 我 们总是选择最高预期货币价值的那个分支 3 2 解决树 Allison 现在正准备解决决策树 解决任何复杂的决策问题 我们打破决策树成一 系列更小的决策问题 回顾决策树图 我们计算出 4 个决定节点 A B C D Allison 必须在每个决定去做什么 我们从哪开始 树的年代让它变得很容易 我们开始着手于树的右手边并且逆向 操作 为什么我们在末端开始 当看起来似乎有悖常理的逆向操作的时候 事实上我 们经常做这样的日常决策 假如你正在考虑是否值得付出更多的时间和精力去到城里 去吃 还是在当地的餐馆吃 你可能会考虑如果去城镇的话吃什么 或者你就在本地 吃什么 换句话说 你可以想象 你已经走了进城 想一想你会怎样采取下一步 在 解决了这个问题之后 你会逆向做出你第一个决定 比较下你有多喜欢在城镇里吃你 挑的食物而不是在本地吃 这些是以用额外时间和精力进城为代价的 类似地 Allison 开始想象她已经做了市场调查 发现市场良好 也就是说 她起 初假设她是在树下的 A 位置 她会做什么呢 基于数据挖掘算法的客户行为分析系统 文献翻译 9 图图 3 63 6 如果 Allison 发现自己在一个 A 她就不得不选择是投资还是不投资 由于是在这 种情况下 她知道市场很好 而且 投资相比不投资 将会产生 50 万美元的现金流量 这将会使产量为零 因此 她知道如果她最终达到点 她就会总是选择投资 图图 3 73 7 因为她知道 如果在 A 点她就会去做 她知道价值在这一点上是和当她在那里可 以做出的最好决定 50 万美元是一样的 沿着相同的技术 她考虑如果在点 B 她投资于市场调研和不合时宜 她该怎么 做 如果她投资 0 如果她不投资 对比着这确定的 200 300 100 损失 她选择不投 资 图图 3 83 8 最后 她考虑如果她在点 C 该怎么做 她在这里的决策会更复杂 因为她不知道 她的行为的后果 她对比树的每个分支的预期货币价值 并选择最好的 因为投资的 预期货币价值 0 40 x800 000 0 60 x100 000 30 8 万 超过不投资 0 40 x 0 0 x 0 0 0 的预期货币价值 所以她会选择投资 当我们看到在我们概率树分析之前 这个 基于数据挖掘算法的客户行为分析系统 文献翻译 10 决策的价值是预期货币价值的最好决定 或是 8 万美元 Allison 的估价 在 C 点为 8 万美元 图图 3 93 9 在这一点上 我们知道 Allison 会做点 A B 和 C 我们可以浓缩树到一组更小的 决策 图图 3 103 10 根据我们的简化树 我们现在可以问 Allison 应该在 D 吗 她对比第一个路径 通 过市场研究 的预期货币价值与第二路径 不做市场调研 的预期货币价值 在路径顶端 她得到 50 万的可能性为 0 4 0 的可能性所 0 60 但成本为 5 万 在选择做市场调查佣 金之后的预期现金流就因此为 50 万 0 4 0 0 6 20 万 减去研究本身的 5 万成本 可以创造出一个 15 万美元之间的净预期现金流量 在路径底部 她有一个 8 万美元的 预期现金流量 所以她需要支付市场研究增加她的预期现金流到 7 万美元从