学习决策树

1决策树是什么？

百度百科：

决策树是一种数据挖掘分类算法、是直观运用概率分析的一种图解法、是一个预测模型。

由于这种决策分支画成图形很像一棵树的枝干，故称决策树。

我的理解就是：一种寻找最优方案的画图法。

前提是要知道所有可能的方案，以及每种方案的收益与发生概率。这样才能算出每种方案的理论期望值，对比各个方案，然后找到最优方案。

为了学习决策树我又看了一篇文献：《决策树（哈佛大学笔记）》

这个比较易懂，只是字多了点。

她举了个例子

说是要卖椅子，

当前情况是：每年销售额 20万--45万（这个数据之后并没有用）

这时有一个投资新设备的机会

投资新设备成本是30万

投资之后

每把椅子获利100元

市场好：能卖出8000个 共获利80万

市场不好：能卖出1000个，获利10万

用概率树来表示：

然后指出，估计市场好的几率是0.4，相反，不景气的几率为0.6

那么 投资的预期平均现金流为：

这时，增加了一些新元素。

说

在市场好的时候

能产品能上电视销售额将会达到：320万（概率0.1）

上不了电视则只有：80万（概率0.9）

市场不好的时候

上电视销售额为40万（概率为0.01%）

上不了电视则只有：10万（概率0.99）

现在，概率树为：

然后4种情况各自的平均期望值为：

最后，4个期望值的和  减去投资成本，得到这个投资机会的价值$477,800 - $300,000 =$177,800

现在，老板需要一家调查机构来告诉他们市场是好是坏，不过需要花50000元来请他们调查。

老板不知道值不值得花这50K。

从这儿开始，作者开始教我们如何画决策树：

1 列出备选方案：

从第一个决定开始，这里的话，就是决定到底要不要花钱请人调查：

成本：调查为50，不调查为0

接着，从顶端的分支开始画。如果调查，会发生哪些情况。

因为调查的结果不是老板能掌控的，具有不确定性，因此用圆圈（机会节点）来标记。

继续，在每一个调查结果中，老板会决定购买设备，或者放弃购买：

市场景气的时候，花费30K，将会收到80K收入，不投资，则为0；

市场不景气的时候，花费30K，将会收到10K收入，不头则，则为0；

现在，调查部分的决策树画完了，下面补全不进行调查部分的决策树：

老板不打算花钱做调查，因此老板是在不确定市场景气与否的前提下做出决定，那么就仅仅是：

投资OR不投资。

投资的话，分市场景气和不景气两种，分别收入80K,10K；

不投资的话，也分市场景气和不景气两种（严谨，不能因为0，就可以省略），不过收入都为0；

2  量化不确定性

好，现在此刻我们已经把所有备选方案列好了，下面，我们要量化决策树中的每个分支的不确定性。

首先确定概率，在圆圈（机会节点）的后面的分支上标注概率：

调查报告显示，市场景气的概率是0.4，不景气的概率是0.6，所以在相应的分支上标注好概率，同时呢，为了方便查询，我们在重要节点上分别标注:A、B、C、D。

3 指定目标

一般来说，目标就是选择最优的方案，而最有的方案通常都是做出货币价值最高的决策。

4解决决策树

从结果节点开始逆向操作：

在决策节点A，老板需要决定是花50K进行投资，还是不投资。

投资的话 80K-30K=50K，将会产生50K 的现金流，不投资则为0，所以投资，是最优决策：

在决策节点B，对比权衡投资于不投资的利弊，老板选择不投资：

因为：收入的10K-投资成本的30K=-20K，而不投资为0，因此老板在B这个决策节点选择不投资。

接着，老板考虑在决策点C该做什么决定。因为她不知道自己决策的后果，所以，他需要对比决策点C后面的每个结果分支，并选择最预期货币价值最好的结果：

投资:预期货币价值  0.40x800，000 + 0.60x100，000 - 30 = 8万

不投资: 预期货币价值  0.40 x 0 + 0 x 0 - 0 = 0

因为  投资（预期货币价值）>不投资（预期货币价值），所以她会选择投资。

现在，我们知道老板做出了A\B\C三个决策，于是我们可以缩小决策树：

现在做最后一个决策，D：

对比两条路径的预期货币价值做出决定。

第一条--调查的路径：

调查之后的预期现金流为：市场景气收益的50万×市场景气的概率0.4+市场不景气的收益0×市场不景气的概率0.6=20万，再减去调查成本5万，最后等于15万。

调查后的预期现金流为15万。

现在看第二条路径---不调查：

不调查产生的预期货币价值为8万

15>8，因此老板最终会做出花钱请人调查，并且在市场景气的时候进行投资这条决策。

总结：

分三步建立决策树：

1列出备选方案

2量化不确定性

3 指定目标

最后解决决策树：

1从结果开始，计算每个决策节点后面的结果的预期货币价值，做出最优的决策

over。

之后我又看了一篇文章---《白话一下什么是决策树模型》

http://www.itongji.cn/article/111429252013.html

开头，作者以CS为例，记录了玩家的4条数据

得出，条件的不同，会导致行为的不同这个结论。

然后作者将数据分为两块：

1是X，代表条件

2是Y，代表结果

在这个例子里，条件和结果都不只一个

条件是{武器类型、子弹数量、血量}

结果是{战斗、逃避}

然后作者说道建立决策树的目的是找到最合适的映射关系：

Y=F(X)

在这里就是说，武器类型、子弹数量，以及血量之间的关系将会决定结果，决定是战斗还是逃避。

同时作者还说，条件有优先级高下之分。对结果的影响也就有高矮之分。

接着，作者引入了信息论中的”熵“这个概念，它的作用是计算信息的混乱程度。

说着，作者将各个条件中的元素都求了个熵出来，

这还没完，要想得到条件的优先级，还要计算一个叫做信息增量的东西，它可以代表优先级，值与优先级成正比。

利用熵来求信息增量的公式：

Gain(Sample,Action) = E(sample) - sum(|Sample(v)|/Sample * E(Sample(v)))

over，这就是这篇文章的主要内容。

问题1：

虽然我知道公式是：E = sum(-p(I)*log(p(I)))，I=1:N，N为多少种结果

但是我无法理解这个式子是怎么写出来的：

E(机枪) = -(1/2)Log2(1/2) - (1/2)Log(1/2) = 0.5 + 0.5 = 1

问题2：

这个我也不懂怎么写出来的。

“Gain(武器类型) = E(S) - (2/4)*E(机枪) - (2/4)*E(小刀) = 1 - (2/4)*1 - (2/4)*1 = 0“这个式子的理解。

公式：

Gain(Sample,Action) = E(sample) - sum(|Sample(v)|/Sample * E(Sample(v)))

至此，对这篇文章的理解结束。

2它什么样？

决策树就是由：方块（决策节点）、圆圈（机会阶段）、三角（结果）和分支线所组成。

用来寻找具价值方案的一种画图画。

使用决策树有4个步骤：

1列出所有可能的备选方案，画出每种方案会导致的结果

2量化不确定性，也就是确定每个方案的概率

3明确你的目标，一般来说就是追求最优货币价值的决策

4从结果逆向操作，计算出每种结果的期望值，然后对比各个结果的期望值，选出最优方案。

3它有什么用？

做决策之前，使用它，可以对比出每种方案的期望值，以此来找到最优方案。

4我如何利用它？

我一切量化的决策都可以使用它。