决策树算是比较常见的数据挖掘算法了,最近也想写点算法的东西,想着这期的 就先写个决策树吧。
决策树是什么,我们来“决策树”这个词进行分词,那么就会是 大。家不妨思考一下,重点是决策还是树呢?其实啊,决策树的关键点在 上。
我们平时写代码的那一串一串的,如果其他其实就是决策树的思想了。看下面的图是不是觉得很熟悉呢?
当然决策树算法比这复杂那么一丢丢,所以在说决策树之前,我们需要先了解一些基本知识,先来说说信息论中的信息熵。
决策树之所以叫决策树,就是因为它的结构是树形状的,如果你之前没了解过树这种数据结构,那么你至少要知道以下几个名词是什么意思。
根节点:最顶部的那个节点
叶子节点:每条路径最末尾的那个节点,也就是最外层的节点
非叶子节点:一些条件的节点、下面会有更多分支,也叫做分支节点
分支:也就是分叉
学过树这种数据结构的同学可能一看就明白了,没有学过也没关系,我们可以用上面的图来说明各部分分别是什么。
要说决策树,那信息熵是绕不过去的一座山~
3.1信息熵是什么?
假设你要知道一件未知的事情,比如明天会不会下雨。这时候你就需要去获取一些信息,比如空气干湿度,今天是万里无云还是多云等等(假设没有天气预报)。这些信息中,有的可以让你能更加准确判断明天会不会下雨(比如今天有没有云),而有信息些则不会(比如今天晚餐吃什么)。如何度量这些信息对你决策的帮助呢?这里要使用到的就是信息熵了,信息熵正是对信息量有效性的一种度量方法。
如果你还记得高中化学的知识的话,那对 这个字应该不会陌生。 。
信息熵也是一样的,它能对信息的不确定性进行恒量,
还是接上面的例子,现在你知道了空气的湿度,那么你就能更准确得判断明天是否会下雨。你得到的信息让你的结论更加清晰,准确,所以它的熵值就比较小,因为它让信息更加准确。而对今天晚餐吃什么这个信息,显然它对你判断明天会不会下雨是没什么帮助的,所以它的信息熵是比较大的,因为这个信息和明天有没有下雨没有关系,它并没有让我们的判断更加清晰,甚至让我们的判断趋于混乱。
计算信息熵的公式如下:
其中U指的是某一信息,π则是指信息中各种可能出现的结果的概率。
比如U为空气湿度,空气湿度一共有3中( ),则可以p1表示空气干燥的概率,p2表示空气微湿的概率,p3表示空气湿润的概率,这些概率都是可以通过样本统计出来的。
然后空气湿度的信息熵就可以计算出来了:
H(空气湿度)=p1 *日志(p1) + p2 *日志(p2) + p3 *日志(p3)
我们可以举吴军老师的“数学之美”中的一个例子来解释这条式子。
2018年假设,有32支球队参加世界杯,每只球队最终获得冠军的概率一样。在世界杯之后,你去问别人世界杯冠军是哪个国家的?那个人不直接跟你说,让你猜!并且每猜一次,你需要支付1块钱,这时你怎么才能花最少的钱呢?
