决策树算是比较常见的数据挖掘算法了，最近也想写点算法的东西，就先写个决策树吧。

一. 什么是决策树

决策树是什么，我们来“决策树”这个词进行分词，那么就会是决策/树。大家不妨思考一下，重点是决策还是树呢？其实啊，决策树的关键点在树上。

我们平时写代码的那一串一串的If Else其实就是决策树的思想了。看下面的图是不是觉得很熟悉呢？

当然决策树算法比这复杂那么一丢丢，所以在说决策树之前，我们需要先了解一些基本知识，先来说说信息论中的信息熵。

二.决策树介绍

决策树之所以叫决策树，就是因为它的结构是树形状的，如果你之前没了解过树这种数据结构，那么你至少要知道以下几个名词是什么意思。

• 根节点：最顶部的那个节点
• 叶子节点：每条路径最末尾的那个节点，也就是最外层的节点
• 非叶子节点：一些条件的节点，下面会有更多分支，也叫做分支节点
• 分支：也就是分叉

学过树这种数据结构的同学可能一看就明白了，没有学过也没关系，我们可以用上面的图来说明各部分分别是什么。

三.信息熵

要说决策树，那信息熵是绕不过去的一座山~

3.1 信息熵是什么？

假设你要知道一件未知的事情，比如明天会不会下雨。这时候你就需要去获取一些信息，比如空气干湿度，今天是万里无云还是多云等等（假设没有天气预报）。这些信息中，有的可以让你能更加准确判断明天会不会下雨（比如今天有没有云），而有信息些则不会（比如今天晚餐吃什么）。如何度量这些信息对你决策的帮助呢？这里要使用到的就是信息熵了，信息熵正是对信息量有效性的一种度量方法。

如果你还记得高中化学的知识的话，那对熵这个字应该不会陌生。熵在化学中是表示分子的混乱程度，分子越混乱，它的熵就越大，而若分子越有序，熵值就越小。

信息熵也是一样的，它能对信息的不确定性进行恒量，如果某个信息让我们的判断更加有序，清晰，则它信息熵越小，反之越大。

还是接上面的例子，现在你知道了空气的湿度，那么你就能更准确得判断明天是否会下雨。你得到的信息让你的结论更加清晰，准确，所以它的熵值就比较小，因为它让信息更加准确。而对今天晚餐吃什么这个信息，显然它对你判断明天会不会下雨是没什么帮助的，所以它的信息熵是比较大的，因为这个信息和明天有没有下雨没有关系，它并没有让我们的判断更加清晰，甚至让我们的判断趋于混乱。

计算信息熵的公式如下：

其中U指的是某一信息，pi则是指信息中各种可能出现的结果的概率。

比如U为空气湿度，空气湿度一共有3中（干燥，微湿，湿润），则可以p1表示空气干燥的概率，p2表示空气微湿的概率，p3表示空气湿润的概率，这些概率都是可以通过样本统计出来的。

然后空气湿度的信息熵就可以计算出来了：

H(空气湿度) = p1 * log(p1) + p2 * log(p2) + p3 * log(p3)

我们可以举吴军老师的「数学之美」中的一个例子来解释这条式子。

假设2018年，有32支球队参加世界杯，每只球队最终获得冠军的概率一样。在世界杯之后，你去问别人世界杯冠军是哪个国家的？那个人不直接跟你说，让你猜！并且每猜一次，你需要支付1块钱，这时你怎么才能花最少的钱呢？

学过算法的我们自然知道可以用二分法，把32支球队分成两半，猜对猜错之后自然知道球队在哪一半，再二分再猜，这样最终你需要猜5次，也就是需要支付5块钱，没错吧。这样一来，这条信息的价值就是5块钱，而在计算机中，则用***bit***表示。假如一共有64支球队，那我们就需要多猜一次，这条信息的价格就变成了6。从这里我们就可以看出信息的度量跟log有关，log32=5，log64=6嘛。

现在我们来运用上面的公司，我们让p1,p2,p3...p32表示每支球队获胜的概率，运用公式，则

H(获胜) = p1*logp1 + p2*logp2 + ... + p32*log32

这样最终算出的结果正是等于5，就是说哪个国家获胜这条信息的信息熵是5。

3.2 信息熵与决策树

信息熵最早是用在通信领域的，而决策树的诞生是缘于澳大利亚计算机科学家昆兰，在一次研究生课程大作业中，引入了信息增益准则来改进程序。而后在1979年发表这一相关论文后，决策树算法正式问世，并掀起一股决策树算法的研究热潮。

那么它被用在哪里呢？

我们知道决策树由许多属性和分支组成，那么如何决定哪个属性在前，哪个在后呢。这里就需要用到信息熵了。

前面我们提到过信息熵是对信息不确定性的度量，既然信息可以度量，那每次我们只要找到信息熵的值最小，也就是让决策更加清晰的那个属性来作为根进行分支，那不就行了吗？什么，你说分支后怎么办，对树处理的基本方法就是递归，分支后，每一分支节点都可以当作一棵新的树，然后再来重复上面的步骤啦。

今天先介绍决策树的一些基础知识，后面我们会通过一个实际的例子以及代码来看看决策树的运行原理。

以上~

推荐阅读：
Scala 函数式编程指南（一） 函数式思想介绍
Actor并发编程模型浅析
大数据存储的进化史 –从 RAID 到 Hadoop Hdfs
C，java，Python，这些名字背后的江湖！