机器学习——有监督——决策树相关原理及sklearn实现(信息熵、基尼系数、信息增益、特征重要程度的量化)
一、决策树原理
决策树(Decision Tree)是一种非参数的有监督学习方法,它能够从一系列有特征和标签的数据中总结出决策规则,并用树状图的结构来呈现这些规则,以解决分类和回归问题。决策树算法容易理解,适用各种数据,在解决各种问题时都有良好表现,尤其是以树模型为核心的各种集成算法,在各个行业和领域都有广泛的应用。
我们来简单了解一下决策树是如何工作的。决策树算法的本质是一种图结构,我们只需要问一系列问题就可以对数据进行分类了。比如说,来看看下面这组数据集,这是一系列已知物种以及所属类别的数据:
根据已经收集到的数据,决策树算法为我们算出了下面的这棵决策树:
根据以上的决策树规则,当我们发现一个新的物种,我们就可以根据决策树判断它所属的类别。
根节点:没有进边,有出边。包含最初的,针对特征的提问。
中间节点(内部节点):既有进边也有出边,进边只有一条,出边可以有很多条。都是针对特征的提问。
叶子节点:有进边,没有出边,每个叶子节点都是一个类别标签。
*子节点和父节点:在两个相连的节点中,更接近根节点的是父节点,另一个是子节点。
二、构建决策树
任意一个数据集上的所有特征都可以被拿来分枝,每个特征上的任意值都可以当成一个节点*组合(例如身高可以分为<1.8米,>=1.8米,也可以分为<1米,>=1米,等等),所以一个数据集上可以发展出非常非常多棵决策树,其数量可达指数级。在这些树中,总有那么一棵树比其他的树分类效果都好,那样的树叫做”全局最优树“。
全局最优:经过组合形成的,整体来说分类效果最好的模型
局部最优:每一次分枝的时候都向着更好的分类效果分枝,但无法确认如此生成的树在全局上是否是最优的。
决策树算法的核心是要解决两个问题:
1)如何从数据表中找出最佳节点和最佳分枝?
2)如何让决策树停止生长,防止过拟合?
一个数据集可以发展的决策树数量是指数级别的,在这么多的决策树当中挑选出一颗“全局最优树”,是非常低效的,于是我们牺牲掉小部分的准确率,用逐步的“局部最优”来达到最接近“全局最优”的结果,这类算法我们统称为“贪心算法”。
贪心算法:通过实现局部最优来达到接近全局最优结果的算法,所有的树模型都是这样的算法。
最典型的决策树算法是Hunt算法,该算法是由Hunt等人提出的最早的决策树算法。现代,Hunt算法是许多决策树算法的基础,包括ID3、C4.5和CART等。Hunt算法诞生时间较早,且基础理论并非特别完善,此处以应用较广、理论基础较为完善的ID3算法的基本原理开始,讨论如何利用局部最优化方法来创建决策模型。
ID3算法原型见于J.R Quinlan的博士论文,是基础理论较为完善,使用较为广泛的决策树模型,在此基础上J.R
Quinlan进行优化后,陆续推出了C4.5和C5.0决策树算法,后二者现已称为当前最流行的决策树算法,我们先从ID3
开始讲起,再讨论如何从ID3逐渐优化至C4.5。