第8.1节 决策树的基本思想
各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。
本期推送内容目录如下，如果本期内容对你有所帮助，欢迎点赞、转发支持掌柜！
8.1 决策树的基本思想 8.1.1 冠军球队 8.1.2 信息的度量 8.1.3 小结 引用
8.1 决策树的基本思想
经过前面几章的介绍，我们已经学习过了3个分类算法模型，包括逻辑回归、K近邻和朴素贝叶斯。今天笔者将介绍下一个分类算法模型——决策树（Decision Tree）。
一说到决策树其实很多读者或多或少已经使用过，只是自己还不知道罢了。例如最简单的决策树就是通过输入年龄，判读其是否为成年人，即if age>=18 return True，想想自己是不是经常用到这样的语句。
8.1.1 冠军球队
关于什么是决策树，我们先来看一个例子。假如笔者错过了某次世界杯比赛，赛后笔者问一个知道比赛结果的人“哪支球队获得了冠军”？但是对方并不愿意直接说出结果，而是让笔者自己猜，且每猜一次对方都要收一元钱才肯告诉笔者是否猜对了。现在的问题是要掏多少钱才能知道哪支球队是冠军球队。
现在笔者可以把球队从1到16编上号，然后提问：“冠军球队在1~8号中吗？”。假如对方告诉笔者猜对了，笔者就会接着问：“冠军球队在1~4号中吗？”。假如对方告诉笔者猜错了，那么笔者也就自然知道冠军球队在5~8号中。这样只需4次，笔者就能知道哪支球队获得了冠军。上述过程背后所隐藏着的其实就是决策树的基本思想，并且还可以用更为直观的图来展示上述过程，如图8-1所示。
由此可以得出，决策树的每一步决策过程就是降低信息不确定性的过程，甚至还可以将这些决策看成一个ifthen的规则集合。如图8-1所示，冠军球队一开始有16种可能性，经过一次决策后变成了8种。这意味着每次决策都可以得到更多确定的信息，而减少更多的不确定性。
不过现在的问题是，为什么要像图8-1这样来划分球队呢？对于熟悉足球的读者来讲，这样的决策树似乎略显多余。因为事实上只有少数几支球队才有夺冠的希望，而大多数球队是没有希望的，因此，一种改进做法是在一开始的时候就将几个热门的可能夺冠的球队分在一边，将剩余的球队放在另一边，这样就可以大大提高整个决策过程的频率。
例如最有可能夺冠的是1、2、3、4这4支球队，而其余球队夺冠的可能性远远小于这4支球队。那么一开始就可以将球队分成1~4和5~16。如果冠军是在1~4中，则后面很快就能知道哪支球队是冠军。退一万步，假如冠军真的在5~16中，那么接下来同样可以按照类似的思路将剩余的球队划分成最有可能夺冠和最不可能夺冠两部分,这样也能快速地找出哪支球队是冠军球队。
于是这时候可以发现，如何划分球队就变成了建立这棵决策树的关键。如果存在一种划分，能够使数据的“不确定性”减少得越多（哪支球队不可能夺冠），也就意味着该划分能获取更多的信息，而我们也就更倾向于采取这样的划分，因此采用不同的划分就会得到不同的决策树，所以现在的问题就变成了如何构建一棵“好”的决策树呢？要想回答这个问题，先来解决如何描述“信息”这个问题。
8.1.2 信息的度量
关于如何定量地来描述信息，几千年来都没有人给出很好的解答。直到1948年，香农在他著名的论文《通信的数学原理》中提出了信息熵（Information Entropy）的概念，这才解决了信息的度量问题，并且还量化出信息的作用。
为你认可的知识付费，欢迎订阅本专栏阅读更多优质内容！
1. 信息熵