决策树算是比较常见的数据挖掘算法了, 最近也想写点算法的东西, 就先写个决策树吧.
一. 什么是决策树
决策树是什么, 我们来 "决策树" 这个词进行分词, 那么就会是决策 / 树. 大家不妨思考一下, 重点是决策还是树呢? 其实啊, 决策树的关键点在树上.
我们平时写代码的那一串一串的 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 年发表这一相关论文后, 决策树算法正式问世, 并掀起一股决策树算法的研究热潮.
那么它被用在哪里呢?
我们知道决策树由许多属性和分支组成, 那么如何决定哪个属性在前, 哪个在后呢. 这里就需要用到信息熵了.
前面我们提到过信息熵是对信息不确定性的度量, 既然信息可以度量, 那每次我们只要找到信息熵的值最小, 也就是让决策更加清晰的那个属性来作为根进行分支, 那不就行了吗? 什么, 你说分支后怎么办, 对树处理的基本方法就是递归, 分支后, 每一分支节点都可以当作一棵新的树, 然后再来重复上面的步骤啦.
今天先介绍决策树的一些基础知识, 后面我们会通过一个实际的例子以及代码来看看决策树的运行原理.
以上~
来源: https://www.cnblogs.com/listenfwind/p/10178207.html