机器学习（1）——决策树

一：决策树的基本概念

1.1 基本概念

决策树（Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望大于零的概率，评估项目风险、判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。———百度百科

在机器学习（Machine Learning）中，决策树是一种预测模型、它代表的是对象属性与对象值之间的一种映射关系。树中的每个节点表示某个对象属性、每个分叉路径代表某个可能的属性值，而每个叶节点则对应从根节点到该叶节点所经历的路径所代表的对象的值。

1.2 事例

在讲解之前先举一个决策树的事例——约会选餐馆。我们在选餐馆的时候一般会考虑许多的方面，如下：

• 是否饥饿？
• 餐馆是否有空位？
• 餐馆是什么类型的餐馆？
• 餐馆是否好吃？
• 餐馆是否然人举得幸福
• 。。。

在现实生活中，我们选择餐馆一般是基于多个条件的？要求餐馆既要好吃又不需要等待；要饥饿了才会去选一家不需要等待并且让人感觉幸福的餐厅就餐等等的情况。而这个就是一个典型的决策树的例子。如下图（通过图形来表示该问题的众多种决策树表达中的一种）

（正常的决策树的应该是从上到下显示的，我这里由于没有找到合适的工具所以采用从左到右的方式来显示）

这就是将我们选餐馆时的决定用决策树表示的方式。

题外话：对于决策树来说，我们根据决策树判断一个东西是从根节点开始判断的，如果有哪些思维比较开放的小伙伴觉得是从下开始判断的话，对于决策树来说是不对的。决策树规定的从根节点开始判断。

二：决策树学习

2.1 决策树学习的基本算法结构？

2.1.1 20个问题

这里首先请大家做一个小游戏：提问20个问题猜测我心里正在想的东西的游戏，我只能够回答是/不是？如下的列表是我模拟这个游戏的过程？

• A：它是动物或者生物？
• B：是。
• A：他是人吗？（人也是动物啊）
• B：是的。
• A：他是一个名人吗？
• B：是的。
• A：我们都认识吗?
• B：不是。
• A：他已经过世了吗？
• B：是。

• 。。。。

  考虑到实际的情况，这里呢我只模拟了一部分内容，并没有把一个完整的过程写出来。剩余的部分可以自己在大脑中模拟一下。

2.1.2 分析

为什么我会选择他是动物或者生物？作为第一个问题提问？而没有先提问他是一个名人吗？这个问题。

分析问题后我们发现我们需要从数以万计的数据集（可以把他想象成一个包含时间万物的数据集）中找到我们想要的答案，并且问题有限，那么我们需要做的是什么，尽可能通过少量的提问就可以将数据集进行拆分，缩小我们查找的范围。所以我们提的每一问题都可以帮我们把这个数据集不断的缩小。而相对于第二个问题，虽然我们将他是一个名人吗？作为第一个问题也是可以的，但是相比前者，它是一个更好的属性将数据分隔开，比前者具有更好的实用性，由于文笔有限，这点可能需要大家在去自己思考一下。在编程层面如何告知机器：怎么比较两个属性那种更好，大家可以首先学习一下信息熵

而从上边我们就可以大概得到我们实现决策树学习的算法结构了，如下：

1. Find Best Attribute——最好属性，这个我们将在后续的过程中讲解到。
2. Ask Question?——提出问题。
3. Follow the answer path.——跟随提问的路径走下去。
4. 回到1，重复执行所有的操作，知道决策树符合要求。

2.2 几种基本的决策树结构以及特点

2.2.1 n-or

n-or转换为数学表达式是： n1 or n2 or n3 or…or nn 。

如果你用决策树将其表示出来，你会发现这个数会很简单。

2.2.2 n-XOR

n-XOR转换为数学表达式是： n1 XOR n2 XOR n3 XOR … XOR nn 。你如果决策树将这个表达式画出来，你会发现这个决策树可以看作是一个满的二叉树。

2.2.3 分析

针对第一种情况，决策树的增加是随着n的增加称线性增加的；而对于第二种情况，决策树的增加是虽则和n的增加成指数倍增加的。而第二类问题我们可以将其概括为奇偶性的问题。这里的n这代表我们在实际的决策树是提出的属性，所以为了避免将问题复杂化，所以我们在实际的过程中要注意怎么找到一个好的表达。而这个问题也正是AI的难点——即如何找到一个好的表达。

针对类似于奇偶性的问题，我们可以通过合并属性的方式来降低决策树的深度，这不失为一个不错的好的解决方式。

2.2.4 n维true-false类型决策树

对于n维的true-false决策树我们会有多少中情况呢？请看下表？

a1	a2	a3	a4	…	an	output
T	T	T	T	…	T
F	T	T	T	…	T
…	…	…	…	…	…	…
F	F	F	F	…	F

上表中 an 代表决策树中输入的属性，output代表最终输入的值。

那么针对n个属性的话，我们输入（Input）存在 2n 中情况；而我们的输出（Output）存在 22n 中情况，即 4n 种情况。相信大家都知道 210 是1024，那么我们可以得知，当n的值为4的时候情况会是恐怖的存在。而且我们这里还没有考虑一个属性判断之后会存在不止2中结果的情况。

这节主要是从几个方面告知，决策树如果如果选在不好的话，不仅仅是误差的存在，他的训练成本也将成指数倍增加。

2.3 ID3算法

前面讲解的都是一些比较偏理论层面的问题，这里呢我们讲解一个决策树具体的算法，由于考虑到算法讲解很长，所以具体的讲解请看我的另一篇博客——决策树算法之ID3

2.4 决策树什么时候算真正的结束？

• 所有训练集的样本归入正确分类时。在该情况下，就存在噪音的问题。例如：存在两个对象相同、实例相同但是标签不同的样本。
• 所有属性都消耗完。但是这种情况是针对离散型数据的，对于连续性的数据就不合适了。
• 没有过拟合（No Over Fitting）。该种情况一般是由于树太大，问题过于复杂，违反了奥卡姆剃刀原理。

2.5 解决过拟合问题

• 通过交叉验证和测试集来避免过拟合，以便挑选出最好的树。
• 剪枝（penning）。我们可以通过剪枝方式来处理过拟合问题，并缩小决策树。

2.6 连续性数据的分析

前边的章节都是基于离散型数据进行分析，但是对于连续性的数据我们就没办法了。这里我们不能像离散型数据那样通过误差的方式来判断，而应尝试测量事物的混乱程度。针对数据连续性的例子这里不做进一步的分析，等后续有时间在讨论。

参考文档：
1：https://baike.baidu.com/item/%E5%86%B3%E7%AD%96%E6%A0%91/10377049?fr=aladdin
2：http://blog.csdn.net/striker/article/details/3991179

---