2025年机器学习实战笔记——微软小冰的读心术与决策树

大家好，我是讯享网，很高兴认识大家。

原文地址：http://blog.csdn.net/geekmanong/article/details/

最近微信朋友圈很多人在转发的一个游戏叫做“微软小冰读心术”，游戏的规则很简单：参与游戏的一方在脑海里想好一个人的名字，然后微软小冰会问你15个问题，问题的答案只能用“是”、“不是”或者“不知道”回答。

微软小冰通过你的回答进行推断分解，逐步缩小待猜测人名的范围，决策树的工作原理与这些问题类似，用户输入一系列数据，然后会给出游戏的答案。

一、决策树简介

决策树（decision tree）是机器学习与数据挖掘中一种十分常用的分类和回归方法，属于有监督学习（supervised learning）算法。通俗来说，决策树分类的思想类似于找对象。现在想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：

女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。

这个女孩的决策过程就是典型的决策树方法。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑：

决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶结点代表一个类别。

决策树学习是以实例为基础的归纳学习，决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值（熵的概念请参考信息论的书籍）下降最快的树，到叶子结点处的熵值为零，此时，每个叶结点中的实例都属于同一类。

二、决策树的构造

1.创建分支

创建分支的伪代码函数createBranch()如下所示：

检测数据集中的每一个子项是否属于同一类；

If so return 类标签；

Else

寻找划分数据集的最好特征；

划分数据集；

创建分支结点；

for 每个划分的子集

调用函数createBranch()并增加返回结果到分支结点中

return 分支结点；

上面的伪代码createBranch()是一个递归函数，在倒数第二行直接调用了它本身。

上表的数据包含5个海洋生物，特征包括：不浮出水面是否可以生存，以及是否有脚蹼。

我们可以将这些生物分成两类：鱼类和非鱼类，现在我们想要决定依据第一个特征还是第二个特征来划分数据。

在讨论这个问题前，我们先了解决策树算法中的一些信息论概念：

1.信息量

定义事件X发生的信息量为：

某事件发生的概率越小，则该事件的信息量越大，一定发生和一定不会发生的必然事件的信息量为0。

例如，今天是22号，别人说明天是23号，这就没有一点信息量。

2.信息熵

信息熵是信息量的期望，定义为：

其中p(x)是，事件x发生的概率。信息熵一般用来表征事件或变量的不确定性，变量的不确定性越大，信息熵就越大。一个系统越有序，它的信息熵就越小，反之，一个混乱的系统信息熵越大，所以信息熵是系统有序化程度的一个度量。

3.联合熵和条件熵

两个随机变量X、Y的联合分布形成联合熵H(X,Y)，已知Y发生的前提下，X的熵叫做条件熵H(X|Y)。

4.互信息两个随机变量X、Y的互信息定义为X、Y的信息熵减去X、Y的联合熵。

5.信息增益

信息熵又称为先验熵，是在信息发送前信息量的数学期望，后验熵是指信息发送后，从信宿（即信息的接收者）角度对信息量的数学期望。一般先验熵大于后验熵，先验熵与后验熵的差就是信息增益，反映的是信息消除随机不确定性的程度。

决策树学习中的信息增益等价于训练集中类别与特征的互信息。

信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。

划分数据集的最大原则是：将无序的数据变得更加有序。划分数据集前后信息发送的变化就行信息增益，通过计算每个特征值划分数据集获得的信息增益，我们就可以根据获得信息增益最高的特征来选择其作为划分数据的特征。

信息增益的计算方法：

（1）计算给定数据集的信息熵

[python] view plain copy