机器学习--决策树理论知识（一）
机器学习 | 决策树理论知识（一）
今天我们将要开始用于分类的决策树模型的学习。
决策树模型呈树状结构，是以实例为基础的归纳学习，它的每个非叶子节点存储的是用于分类的特征，其分支代表这个特征在某个值上的输出，而每个叶子节点存储的就是最终的类别信息，可以认为是if-then规则的集合。简而言之，利用决策树进行预测的过程就是从根节点开始，根据样本的特征属性选择不同的分支，直到到达叶子结点，得出预测结果的过程。决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。其主要优点是模型具有可读性、分类速度快、只需一次构建，可反复使用。
决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。在这周的文章中，我们主要讲解该如何进行特征选择。
首先我们要先介绍一些相关概念，以便我们进行特征选择。
相关概念
信息熵
信息熵(entropy)用来度量一个属性的信息量。熵表示样本的混乱程度，熵越小表示样本对目标属性的分布越纯，反之熵越大表示样本对目标属性的分布越混乱。假设样本用D表示，D的目标属性C具有m个可能的类标号值，\(C = C \lbrace{C_1,C_2,...,C_m}\rbrace\)，\(C_i\)在所有样本中出现的概率为\(p_i\)，(i = 1, 2, ..., m)，则信息熵定义为： \[ Ent(D) = -\sum^m_{i = 1}p_ilog_2(p_i) \] 可以考虑通过比较划分特征前后样本信息熵的变化来确定样本的纯度变化。
信息增益
信息增益是划分前样本数据集的信息熵和划分后样本数据集的信息熵的差值。
假设划分前样本数据集为D，并用特征（属性）a来划分样本集D，则按特征a划分D的信息增益Gain(D, a)为样本集D的熵减去按特征a划分D后的样本子集的熵, 可定义为: \[ Gain(D,a) = Ent(D)-\sum^V_{v = 1}\frac{|D^v|}{|D|}Ent(D^v) \] 其中，a代表划分的特征，特征a有V个可能的取值\((a_1,a_2,...,a_V)\)，D中在特征\(a^v\)上取值的所有样本定义为\(D^v\)，|D|表示D中样本个数。
信息增益越大，说明使用特征a划分后的样本子集越纯，所获得的“纯度提升越大”，越有利于分类。因此可以遍历所有特征，选取使得信息增益最大的特征作为当前结点的分裂特征。
信息增益准则对可取值数目较多的特征有所偏好，不过，要注意一味地选择可取值数目较多的特征可能会导致过拟合，降低模型的泛化能力。
增益率
增益率是在信息增益偏向多取值特征的特性上做出的改进，减少了该偏向可能带来的不利影响。具体定义为： \[ GainRatio(D,a) = \frac{Gain(D,a)}{IV(a)} \] 其中IV(a)的公式如下： \[ IV(a) = -\sum^V_{v = 1}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|} \] IV(a)表示特征a的一个特性，特征的取值数目越多，则IV的值通常会越大，可以达到消除多取值特征带来的不利影响。
特征选择可以看做是一个“提纯”，挑选可以使得分裂后各个节点数据的“纯度”最高的特征，即分裂后的熵与分裂前的熵差别最大。
下面我们来看一个例子：
由题意可知：
S=14，类标号属性“购买电脑”有两个不同值（即{会购买，不会购买}），因此有两个不同的类（即m=2）。设类C1对应于“会购买”，类C2对应于“不会购买”。则s1=9，s2=5，p/14，p2=5/14。
计算给定样本分类所需的期望信息： \[ I(s_1,s_2) = I(9,5) = -\sum^2_{i = 1}p_ilog_2(p_i) = -\frac{9}{14}log_2\frac{9}{14}-\frac{5}{14}log_2\frac{5}{14} = 0.940 \]
我们以年龄为例来计算其信息熵
对于年龄为“<=30”：s11 = 2，s21 = 3，p11 = 2/5，p21 = 3/5: \[ I(s_{11},s_{21}) = I(2,3) = -\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5} = 0.971 \] 对于年龄为“30...40”：s12 = 4，s22 = 0，p12 = 4/4 = 1， p22 = 0: \[ I(s_{12},s_{22}) = I(4,0) = -\frac{4}{4}log_2\frac{4}{4}-0 = 0 \] 对于年龄=“>40”：s13 = 3，s23 = 2， p13 = 3/5，p23 = 2/5:
\[ I(s_{13},s_{23}) = I(3,2) = -\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5} = 0.971 \]
如果样本按照“年龄”划分，对一个给定的样本分类所需的期望信息为 \[ E(年龄) = \frac{5}{14}(s_{11},s_{21})+\frac{4}{14}(s_{12},s_{22})+\frac{5}{14}(s_{13},s_{23}) = 0.694 \] 因此，按照年龄划分的信息熵增益为： \[ Gain(年龄) = I(s_1,s_2) - E(年龄) = 0.246 \] 之后再计算根据“收入”、“是否为学生”，“信用等级”划分的信息增益，互相进行比较，选择增益最大的即可作为划分的属性，之后再对划分后的叶子节点进行以上步骤进行特征选择即可。
下周我们将进行决策树的构建教学，谢谢大家的观看！