机器学习决策树

机器学习决策树

基本流程

决策树是一种用于解决分类问题的机器学习方法。

一棵决策树包含一个根节点、若干个内部节点和若干个叶节点。叶节点对应于决策结果,其他每个节点则对应于一个特征测试。每个节点包含的样本集合根据特征值被划分到子节点中,根节点包含样本全集。从根节点到每个叶节点的路径对应了一个判定测试序列。

决策树学习的目的是为了产生一棵泛化能力强,即处理未见示例能力强的决策树。决策树学习的流程如下所示,这是一个递归过程,函数的输入D为样本集合:

def createTree(D):
 if D中所有样本都属于同一类别C:
   return C 
 if 所有特征都已经使用过了: 
   return D中样本数最多的那种类别
 从还未使用的特征中选择最优划分的特征a
 创建在特征a上的分支节点
 for a 的每一个值 a_v:
   令D_v表示D中在特征a上取值为a_v的样本子集
   分支节点在特征a上取值为a_v的分支 = createTree(D_v)
 return 分支节点

划分选择

决策树学习的关键是如何选择最优划分的特征,随着划分过程不断进行,我们希望决策树的分支节点所包含的样本尽可能属于同一个类别,即节点的纯度越来越高。

信息熵

信息熵是度量样本集合纯度最常用的一种指标。假定样本集合D中包含n种类别,其中第k类样本所占的比例为p_k(k=1,2,...,n),则D的信息熵定义为:

    \[Ent(D)=-\sum_{k=1}^np_klog_2p_k\]

Ent(D)的值越小,则D的纯度越高。

信息增益

假定特征a有V个可能的取值{a^1,a^2,...,a^V},若使用a来对样本集合D进行划分,则会产生V个分支节点,其中第v个分支节点包含了D中所有在特征a上取值为a^v的样本,记为D^v。我们可以根据上式计算出D^v的信息熵,再考虑到不同分支节点所包含的样本数不同,给分支节点赋予权重|D^v|/|D|,即样本数越多的分支节点的影响越大,于是可以计算出用特征a对样本集D进行划分所获得的信息增益:

    \[Gain(D,a) = Ent(D) - \sum_{v=1}^V\frac {|D^v|}{|D|}Ent(D^v)\]

一般而言,信息增益越大,则意味着使用特征a进行划分所获得的纯度提升越大。因此,我们可以用信息增益来进行决策树的划分特征选择,即选择使Gain(D,a)最大化的特征a。

著名的ID3决策树学习算法就是以信息增益为准则来选择划分特征的。

发表评论

电子邮件地址不会被公开。 必填项已用*标注