机器学习-决策树的基本思想

机器学习-决策树的基本思想

决策树算法是最早的机器学习算法之一。

算法框架

1.决策树主函数

各种决策树的主函数都大同小异,本质上是一个递归函数。该函数的主要功能是按照某种规则生长出决策树的各个分支节点,并根据终止条件结束算法。一般来讲,主函数需要完成如下几个功能。

(1)输入需要分类的数据集和类别标签

(2)根据某种分类规则得到最优的划分特征,并创建特征的划分节点--计算最优特征子函数

(3)按照该特征的每个取值划分数据集为若干部分--划分数据集子函数

(4)根据划分子函数的计算结果构建出新的节点,作为树生长出的新分支

(5)检验是否符合递归的终止条件

(6)将划分的新节点包含的数据集和类别标签作为输入,递归执行上述步骤。

2.计算最优特征子函数

计算最优特征子函数是除主函数外最重要的函数。每种决策树之所以不同,一般都是因为最优特征选择的标准上有所差异,不同的标准导致不同类型的决策树。如:ID3的最优特征选择标准是信息增益、C4.5是信息增益率、CART是节点方差的大小等。

在算法逻辑上,一般选择最优特征需要遍历整个数据集,评估每个特征,找到最优的那一个特征返回。

3.划分数据集函数

划分数据集函数的主要功能是分隔数据集,有的需要删除某个特征轴所在的数据列,返回剩余的数据集;有的干脆将数据集一分为二。

4.分类器

所有的机器学习算法都要勇于分类或回归预测。决策树的分类器就是通过遍历整个决策树,使测试集数据找到决策树中叶子节点对应的类别标签。这个标签就是返回的结果。

信息熵测度

特征集中的数据常常表现为定性字符串数据,称为标称数据,使用这些数据的算法缺乏泛化能力,在实际计算中需要将这些数据定量化为数字,也就是所谓的离散化。

数据特征的划分过程是一个将数据集从无序变为有序的过程。这样我们就可以处理特征的划分依据问题,即对于一个由多维特征构成的数据集,如何优选出某个特征作为根节点,如何每次都选出特征集中无序度最大的那列特征作为划分节点。

为了衡量一个事物特征取值的有(无)序程度,引入信息熵。

信息熵拆分:信息和熵

熵(Entropy)是德国物理学家克劳修斯在1850年创造的一个术语,用来表示任何一种能量在空间中分布的均匀程度。能量分布的越均匀,熵就越大。

信息就是对不确定性的消除。现实中,信息可以理解为系统从信源的消息转换的状态。在概率中我们称它是一个随机事件。通常,一个信源发送出什么事件是不确定的,可以根据其出现的概率来度量。概率越大,出现机会越多,不确定性小;概率越小,出现机会越少,不确定性越大。

不确定性函数I就称为事件的信息量,是事件U发生概率p的单调递减函数;两个独立事件所差生的不确定性应等于各自不确定性之和,即I(p1,p2) = I(p1) + I(p2),这称为可加性。同时满足这两个条件的函数I是对数函数,即

I(U) = log(1/p) = -log(p)

在一个信源中,不能仅考虑某一单个事件发生的不确定性,而需要考虑信源所有可能情况的平均不确定性。若信源事件有n种取值:U1...Ui....Un,对应概率为p1...pi...pn,且各个事件的出现彼此独立。这时,信源的平均不确定性应当为单个符号不确定性-log pi的统计平均值(E),可称为信息熵,即

机器学习-决策树的基本思想

信息熵是事物不确定性的度量标准,也称为信息的单位或测度。在决策树中,它不仅能用来度量类别的不确性,也可以用来度量包含不同特征的数据样本与类别的不确定性。即某个特征列向量的信息熵越大,就说明该向量的不确定性程度越大,即混乱程度越大,就应优先考虑从该特征向量着手来进行划分。信息熵为决策树的划分提供了最重要的依据和标准。

首先,我们使用信息熵来度量类别标签对样本整体的不确定性。设Ss个数据样本的集合。假定类别标签具有m个不同值,定义m个不同类Ci(i=1,2,...,m)。设si是类Ci中的样本数。对一个给定的样本分类所需要的信息熵由下式给出

 机器学习-决策树的基本思想

其中pi是任意样本属于Ci的概率,并用pi = si/|S|估计

接下来,我们使用信息熵来度量每种特征不同取值的不确定性。

A具有v个不同值{a1,a2,...,av}。可以用特征AS划分为v个子集{S1,S2,...Sv}。其中,Sj包含S中这样一些样本:它们在A上具有值aj。如果选A作测试特征,即最优划分特征,那么这些子集就是S节点中生长出来的决策树分支。设sij是子集Sj中类Ci的样本数。由A划分成子集的熵或期望信息由下式给出:

机器学习-决策树的基本思想

其中机器学习-决策树的基本思想是第j个子集的权,并且等于子集中的样本个数除以S中的样本总数。其信息熵值越小,子集划分的纯度越高。

机器学习-决策树的基本思想

其中,pij = sij/|Sj|Sj中的样本属于类Ci的概率。

最后,我们使用信息增益来确定决策树分支的划分依据。它是决策树某个分支上整个数据集信息熵与当前节点信息熵的差值,用Gain(A)表示,那么在A上的分支将获得的信息熵增益就是

Gain(A) = I(s1,s2,...,sm) - E(A)

它是由于知道属性A的值而导致的熵的期望压缩。具有最高信息增益的特征就可选作给定集合S的测试属性。创建一个节点,并以该特征标记,对特征的每个值创建分支,并据此划分样本。