数据挖掘复习笔记（三）

2020-11-22 本文已影响0人陨落的小白

分类算法

将决策树之前，首先提一下分类问题。在机器学习中，预测问题是一类很重要的问题。所谓预测，就是根据一些特征的取值，去推断它可能的标记。例如，根据一家公司的经营情况，财务数据，资本实力等特征，去预测这家公司是否会在贷款后违约，以此帮助银行作出相应的决策。

在预测问题中，如果标记是连续值，那么该问题是一个回归问题；如果标记是离散值，那该问题是分类问题；如果标记为空值，那就可能是一个聚类问题。此外，根据有无标记，又可以分为监督学习（有标记）和无监督学习（无标记）。

所谓分类，就是利用训练数据集通过一定的算法模型而得到分类规则，也就是得到一个 $y=f(x)$ ，其中 $x$ 是一个样本的特征向量，也就是各个特征的取值。 $y$ 则是输出的结果，考虑到这是分类问题，所以 $y$ 一般取成离散值。而 $f$ ，就是我们的想要得到的分类规则。

常见的分类算法有决策树算法、贝叶斯&朴素贝叶斯、支持向量机、逻辑回归、神经网络等等。本篇文章我们对决策树进行介绍。

决策树的构建

这是一个基本的决策树模型，是已经求解出的规则。当我们拿出一个新的西瓜，想要判断它是不是好瓜时，我们就需要从上往下去进行判断。它的纹理怎么样？如果纹理模糊，我们就推测他是一个坏瓜；如果纹理稍微模糊一些，我们再去看看触感；如果纹理很清晰，我们就去看看根蒂怎么样。一步步往下走，我们就可以得到最终的预测结果。

所以问题来了，这棵树是怎么构造出来的？为什么要先看它的纹理，为什么纹理清晰后要看根蒂，纹理稍糊要看触感而纹理模糊就直接判断是坏瓜呢？

这就涉及到决策树学习的关键问题，如何选择划分枝干的最优属性。

我们希望划分后，会有怎样的效果呢？显然，我们希望在不断地划分过程中，可以使得每一个分支节点所包含的样本尽可能属于同一类别，节点的纯度越来越高。

例如上面的决策树，倘若我们从样本数据中发现，所有触感硬滑的都是好瓜，所有触感软滑的都是坏瓜，那我们何必把纹理当作第一个判断属性呢？直接判断触感就可以区分出好瓜坏瓜了。

因此，我们可以认为，选择划分属性的一个重要标准，就是它可以尽可能地使相应分出去的节点所包含的样本，具有一样的类别，具有更高的纯度。

那如何来衡量这种纯度呢？

我们使用熵，来衡量这种纯度。

信息熵

信息熵是度量样本集合纯度最常用的一种指标。假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k(k=1,2,3,...|y|)$ ，则 $D$ 的信息熵定义为
$Ent(D)=-\sum_{k=1}^{|y|}p_klog_2(p_k)$
其中 $|y|$ 是标记的取值个数。同时我们约定， $p=0$ 时， $log_2p=0$ 。

此时，当某一个 $p_i=1$ ，而其他的 $p_j=0,j=1,2,..,|y|且j \ne i$ 时，该样本集合的纯度最高（只存在一种标记）而熵 $Ent(D) =0$ 达到最小。当所有的 $p_i=\frac{1}{|y|}$ 时，样本集合的纯度最低（此时等比例的存在所有标记）而熵 $Ent(D)=log_2|y|$ 达到最大。

由上面的例子我们可以知道，当样本集合的熵越大，说明样本集合纯度越低；熵越小，其纯度越高。当我们推广到一棵树上，我们有理由认为，如果我们每一步都选择使系统的熵降低最多的属性，相应的叶子节点的纯度会更高，我们也就能更快而准确的作出预测。

于是，我们引入了信息增益的概念。

信息增益和属性选择

假定离散属性 $a$ 有 $V$ 个不同的取值 $\{a^1,a^2,...,a^V\}$ ，如果使用 $a$ 这一属性对样本集 $D$ 进行划分，则会产生 $V$ 个分支节点。其中第 $v$ 个节点包含了 $D$ 中所有属性 $a$ 上取值为 $a^v$ 的样本，记为 $D^v$ 。我们可以根据上面的公式，计算出 $D^v$ 的信息熵 $Ent(D^v)$ 。

考虑到每一个分支节点所包含的样本数目不同，给每个分支节点赋予权重 $\frac{|D^v|}{|D|}$ ， $|D|$ 表示集合 $D$ 中的样本数目。这样，样本数越多的分支节点的影响力越大，我们便可以计算出根据属性 $a$ 对样本集 $D$ 进行划分后所得到的信息增益
$Gain(D,a)=Ent(D)-\sum_{v=1}^V\frac{|D^v|}{|D|} Ent(D^v)$
即信息熵的减少量。而 $\sum_{v=1}^V \frac{|D^v|}{|D|} Ent(D^v)$ 就是集合 $D$ 根据属性 $a$ 划分后，相应的子树的信息熵。

如上文所述，我们需要选择的用于划分的属性，就是使得信息熵减小最多的属性，这样子叶结点的整体纯度会更高。因此，我们需要计算出所有属性的信息增益，选择信息增益最大的属性作为划分依据。

基本算法

接下来简单描述一下构造决策树的基本算法（贪心）。

Step 1：所有的数据都在根节点，属性都是种类字段（连续属性离散化）。

Step 2：计算所有属性的信息增益，选择信息增益最大的进行划分，生成相应的叶子节点

Step 3：在达到终止条件之前，不断重复第二步，对叶子节点进行划分

那算法的终止条件是什么呢？

一般而言，如果一个叶子节点包含的所有样本都属于同一类，则不需要继续划分了。如果当前的数据集没有任何属性可用于划分，但依然不完全纯净，那按照少数服从多数的原则设定其标记值，并停止划分。如果分到某个节点时，某个值（例如纯度）达到了给定的阈值，则停止划分，设定标记值。

举个例子

对于上述数据集，我们首先计算总体样本的熵 $Ent(D)$ 。可以发现， $|y|=17,p_1=\frac{8}{17},p_2=\frac{9}{17}$ ，所以 $Ent(D)=-p_1*log_2 p_1-p_2*log_2p2=0.998$

下面我们来计算一下，使用“色泽”作为划分属性的信息增益。色泽这一属性有三个取值，所以相应的集合被划分为 $D^1,D^2,D^3$ 。 $D^1$ 代表色泽为青绿，包含六个样例 $\{1,4,6,10,13,17\}$ 。其中正例有3个，负例有3个，所以其信息熵
$Ent(D^1)=-( \frac{3}{6}log_2\frac{3}{6}+\frac{3}{6}log_2\frac{3}{6})=1.000$

$D^2$ 代表色泽为乌黑，包含六个样例 $\{2,3,7,8,9,15\}$ 。其中正例有4个，负例有2个，所以其信息熵 $Ent(D^2)=-(\frac{4}{6}log_2\frac{4}{6}+\frac{2}{6}log_2\frac{2}{6})=0.918$

$D^3$ 代表色泽为浅白，包含五个样例 $\{5,11,12,14,16\}$ 。其中正例有1个，负例有4个，所以其信息熵 $Ent(D^3)=-(\frac{1}{5}log_2\frac{1}{5}+\frac{4}{5}log_2\frac{4}{5}) =0.722$

所以其信息增益 $\begin{align} Gain(D,色泽)&=Ent(D)-\sum_{v=1}^V \frac{|D^v|}{|D|} Ent(D^v)\\ & = 0.988-(\frac{6}{17}*1.000+\frac{6}{17}*0.918+\frac{5}{17}*0.722) \\ & =0.109 \end{align}$