决策树算法及实现

在计算机科学中,树是一种很重要的数据结构,比如我们最为熟悉的二叉查找树(Binary Search Tree),红黑树(Red-Black Tree)等,通过引入树这种数据结构,我们可以很快地缩小问题规模,实现高效的查找。

在监督学习中,面对样本中复杂多样的特征,选取什么样的策略可以实现较高的学习效率和较好的分类效果一直是科学家们探索的目标。那么,树这种结构到底可以如何用于机器学习中呢?我们先从一个游戏开始。

我们应该都玩过或者听过这么一种游戏:游戏中,出题者写下一个明星的名字,其他人需要猜出这个人是谁。当然,如果游戏规则仅此而已的话,几乎是无法猜出来的,因为问题的规模太大了。为了降低游戏的难度,答题者可以向出题者问问题,而出题者必须准确回答是或者否,答题者依据回答提出下一个问题,如果能够在指定次数内确定谜底,即为胜出。加入了问答规则之后,我们是否有可能猜出谜底呢?我们先实验一下,现在我已经写下了一个影视明星的名字,而你和我的问答记录如下:

  1. 是男的吗?Y
  2. 是亚洲人吗?Y
  3. 是中国人吗?N
  4. 是印度人吗?Y
  5.  ……

虽然只有短短四个问题,但是我们已经把答案的范围大大缩小了,那么接下,第5个问题你应该如何问呢?我相信你应该基本可以锁定答案了,因为我看过的印度电影就那么几部。我们将上面的信息结构化如下图所示:

2119554-bfc7f93e51ee6786

在上面的游戏中,我们针对性的提出问题,每一个问题都可以将我们的答案范围缩小,在提问中和回答者有相同知识背景的前提下,得出答案的难度比我们想象的要小很多。

回到我们最初的问题中,如何将树结构用于机器学习中?结合上面的图,我们可以看出,在每一个节点,依据问题答案,可以将答案划分为左右两个分支,左分支代表的是Yes,右分支代表的是No,虽然为了简化,我们只画出了其中的一条路径,但是也可以明显看出这是一个树形结构,这便是决策树的原型。

1. 决策树算法简介

我们面对的样本通常具有很多个特征,正所谓对事物的判断不能只从一个角度,那如何结合不同的特征呢?决策树算法的思想是,先从一个特征入手,就如同我们上面的游戏中一样,既然无法直接分类,那就先根据一个特征进行分类,虽然分类结果达不到理想效果,但是通过这次分类,我们的问题规模变小了,同时分类后的子集相比原来的样本集更加易于分类了。然后针对上一次分类后的样本子集,重复这个过程。在理想的情况下,经过多层的决策分类,我们将得到完全纯净的子集,也就是每一个子集中的样本都属于同一个分类。2119554-bfc7f93e51ee6786比如上图中,平面坐标中的六个点,我们无法通过其x坐标或者y坐标直接就将两类点分开。采用决策树算法思想:我们先依据y坐标将六个点划分为两个子类(如水平线所示),水平线上面的两个点是同一个分类,但是水平线之下的四个点是不纯净的。但是没关系,我们对这四个点进行再次分类,这次我们以x左边分类(见图中的竖线),通过两层分类,我们实现了对样本点的完全分类。这样,我们的决策树的伪代码实现如下: