一文搞懂决策树算法

原文链接

有一个房间，里面有 100 个人，每个人有 100 元。每过一会，每个有钱的人给随机的其他人 1 元，经过一段时间后，房间内的资金分配情况是怎样？

也许有人会认为最终大家的钱趋于平均数，其实不然，你可以使用自己熟悉的编程语言来实现，下图的结果是模拟 45 人初始为 45 元的结果，100 个人结果也是一样的。

这个结果和现实世界中的财富占比是一致的，我想，这大概就是运气吧。

不确定性才是客观世界的本质属性。换句话说，上帝还真就掷骰子。不确定性的世界只能使用概率模型来描述，通过概率模型来量化信息量，进而做出各种预测，来帮助决策。本文介绍机器学习中的决策树算法，如果你能看懂，我的目的就达到了。

先提出一个问题：如何让计算机生成一个树，根据眼睛、头发、身高来区分一个人是不是东方人？训练数据集如下所示：

no	eye	hair	height	result
1	Black	Black	Short	Yes
2	Black	White	Tall	Yes
3	Black	White	Short	Yes
4	Black	Black	Tall	Yes
5	Brown	Black	Tall	Yes
6	Brown	White	Short	Yes
7	Blue	Gold	Tall	No
8	Blue	Gold	Short	No
9	Blue	White	Tall	No
10	Blue	Black	Short	No
11	Brown	Gold	Short	No

为了让你有个直观的认识，这里先给出答案：

有了这个树，再依据眼睛、发色、身高来判断是否是东方人，就非常简单了，这个树就是决策树。

你肯定想知道，这是怎么做到的？

程序、算法都是人脑设计的，想弄明白电脑是如何做的，先思考人脑会如何解决这个问题。

为了创建决策树，我们先要选择一个节点作为根节点，有三个特征，该选哪个呢？理论上所有特征都可以作为根节点，但如果选择不恰当，会导致树有非常多的分叉，变得臃肿，决策时效率非常低下。最简化的情况是树只有一层，只使用一个特征就可以满足判断。因此选择根节点时要选择最有区分度的那个特征作为根节点，也就是说仅凭这个特征就可以判断出大多数结果，本例中眼睛这个特征就符合这个条件，如果眼睛是蓝色和黑色，可以直接判断结果，只有是棕色时，需要借助其他特征。

根节点确定之后，在剩余特征中选择最有区分度的特征作为子节点，本例子中就是头发。通过分析发现，仅使用眼睛、头发两个特征就可以将所有结果判断完毕，因此也就不需要身高加入决策树。

总结一下，就是选择最有区分度的特征作为根节点，次有区分度的作为子节点，再次之，直到特征用完。

人脑可以靠观察分析判断，电脑如何量化这种区分度呢？这里就要引用信息量，信息熵，信息增益这些概念，不用慌，这个其实好理解。

熵的本质，是一个系统内存的混乱程度，熵越大，代表越混乱，越无序。比如气体扩散后不可能自己缩回去，温度只能自发从高温传到低温，这些都是熵增的过程。而我们整理混乱的房间，系统性的学习知识，努力的工作，则是熵减的过程。

在生活中，信息的载体是消息，而不同的消息带来感觉也是不同的。比如，“中国男子足球队获得世界杯冠军”的信息显然要比“中国男子乒乓球队获得世界杯冠军”的信息量要大得多。究其原因，国足勇夺世界杯是小概率事件，发生的可能性微乎其微；而男乒夺冠已经让国人习以为常，丢掉冠军才是意外。因此，以不确定性来度量信息是一种合理的方式。不确定性越大的消息可能性越小，其提供的信息量就越大。

“熵”这个词来源于百科全书式的科学家约翰·冯诺伊曼，香农把它引申到信息论，用于量化信息量。

信息量.png

信息量的单位为比特，假如中国男子足球队获得世界杯冠军的概率为 1/1000，则其信息量约为 10 比特，国乒夺冠概率为 1/2 的话，则其信息量仅为 1 比特，如果一件事情百分之百发生，那么信息量为 0 比特。

因此概率越小，其熵越大，说明信息量越大。

假如一个信息包含多个信源，求得这些信源信息量的数学期望，就可以得到信源熵（信息熵），上述例子中判断是否为东方人这一信息就包含头发，眼睛，身高这三个信源。

信息熵的差就是信息增益。

例子一：一个盒子中分别有 5 个白球和 5 个黑球，随机取出一个球判断它的颜色？这个问题信息量多大呢？由于黑球和白球出现的概率都是1/2，那么就可以得到其信息熵为：

H(x1)= - (1/2log2(1/2)+1/2log2(1/2)) = 1

是的，这里的信息熵是 1 比特。

例子二：有黑白两个盒子，黑色装 5 个黑球，白色装 5 个白球，随意从这两个盒子取一个球，颜色不用判断了，这个问题的信息量有多大呢？

H(x2)= - (1/21log2(1)+1/21log2(1)) = 0

信息增益为 Gain(2) = H(x1) - H(x2) = 1-0=1

例子三：有黑白两个盒子，黑色装 4 个黑球 1 个白球，白色装 4 个白球 1 个黑球，随意从这两个盒子取一个球，判断颜色，这个问题的信息量有多大呢？

H(x3)= - (1/2(1/5log2(1/5)+4/5log2(4/5))+1/2(1/5log2(1/5)+4/5log2(4/5))) = 0.7219280948873623

信息增益为 Gain(3) = H(x1) - H(x3) = 1 -0.7219280948873623 = 0.2780719051126377

因为 Gain(2) > Gain(3) ，因此例子二的分法更有区分度。从概率上也能说明问题：从例子二的盒子中拿到黑球的概率是 100%，从例子三中拿到黑球的概率是 80%（4/5）,从例子一中拿到黑球的概率是 50%。

同样的道理，我们计算眼睛、发色、身高三个特征的信息增益来选择最佳的特征。

第一步：计算训练数据集的总信息熵

数据共 11 条，有 6 条结果是 yes， 有 5 条结果是 no。
H(总)= -(6/11log2(6/11)+5/11log2(5/11)) = 0.9940302114769565

第二步：分别计算每个特征的信息熵和信息增益

先看眼睛，眼睛为 Black 的有 4 条，其中全部是东方人

H(eye=Black)=-1*log2(1) = 0

眼睛为 Blue 的有 4 条，其中全部不是东方人

H(eye=Blue)=-1*log2(1) = 0

眼睛为 Brown 的有 3 条，其中 2 个是东方人，1 个不是东方人：
H(eye=Brown)=-(2/3log2(2/3)+1/3log2(1/3)) = 0.9182958340544896

总条数为 11 条，其中 eye = Black 的占 4 条，eye = Blue 的占 4 条，eye = Brown 的占 3 条，对三种颜色求期望可得到眼睛的信息熵为：
H(eye)=4/11 * H(eye=Black) + 4/11H(eye=Blue)+3/11H(eye=Brown)=0+0+3/11*0.9182958340544896 = 0.2504443183784972

信息熵与概率的关系如下图所示：

可以看出，当概率 P(x) 越接近 0 或者 1 时，信息熵越小，其不确定性越小，即数据越纯信息熵越小，说明越有序。

因此眼睛这个特征的 信息增益 为
Gain(眼睛)= H(总)-H(eye) = 0.9940302114769565-0.2504443183784972
= 0.7435858930984593

信息增益越大，说明特征的信息熵越小，则说明该特征越有序，更有区分度。

我们在选择特征时，选择信息增益最大的特征，即，让数据尽量往更纯净的方向上变换，因此，信息增益是用来衡量数据变得更有序、更纯净的指标。

我们按第二步的方法求出所有特征的信息增益，并排序。

Gain(眼睛信息增益) = 0.7435858930984593

Gain(头发信息增益) = 0.4040097573248599

Gain(身高信息增益) = 0.00723448672483451

因此我们可以按照 眼睛-> 头发 -> 身高 的顺序来构建决策树。

第三步：构建决策树

眼睛做为根节点确认之后，发现眼睛的取值有 3 个，因此从眼睛出发，有 3 条线，分别为 Black、Bule、Brown，其中 Black 和 Bule 的结果都是一致的 yes 或 no，因此也可直接得出结论，不需要再有子节点。

当为眼睛 Brown 时结果有两个 yes 和 一个 no，此时需要借助具有第二区分度的特征 头发 来再次判断。

处理头发时，道理是一致的，编码时可以递归处理，最终发现不需要借助 身高 这个特征就可以将所有数据判断完毕，此时树构建完毕。

获取源代码

创建决策树的函数如下：

def createTree(dataSet, labels):
    """
    Desc:
        创建决策树
    Args:
        dataSet -- 要创建决策树的训练数据集
        labels -- 训练数据集中特征对应的含义的labels，不是目标变量
    Returns:
        myTree -- 创建完成的决策树
    """
    classList = [example[-1] for example in dataSet]
    # 如果数据集的最后一列的第一个值出现的次数=整个集合的数量，也就说只有一个类别，就只直接返回结果就行
    # 第一个停止条件：所有的类标签完全相同，则直接返回该类标签。
    # count() 函数是统计括号中的值在list中出现的次数
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 如果数据集只有1列，那么最初出现label次数最多的一类，作为结果
    # 第二个停止条件：使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组。
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)

    # 选择最优的列，得到最优列对应的label含义
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 获取label的名称
    bestFeatLabel = labels[bestFeat]
    # 初始化myTree
    myTree = {bestFeatLabel: {}}
    # 注：labels列表是可变对象，在PYTHON函数中作为参数时传址引用，能够被全局修改
    # 所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示'no surfacing' is not in list
    del(labels[bestFeat])
    # 取出最优列，然后它的branch做分类
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        # 求出剩余的标签label
        subLabels = labels[:]
        # 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
        # print('myTree', value, myTree)
    return myTree

关注公众号 somenzz，后台回复「决策树」获取完整源码。如果有任何疑问欢迎加微信与我交流。

（完）