机器学习决策树
基本流程
决策树是一种用于解决分类问题的机器学习方法。
一棵决策树包含一个根节点、若干个内部节点和若干个叶节点。叶节点对应于决策结果,其他每个节点则对应于一个特征测试。每个节点包含的样本集合根据特征值被划分到子节点中,根节点包含样本全集。从根节点到每个叶节点的路径对应了一个判定测试序列。
决策树学习的目的是为了产生一棵泛化能力强,即处理未见示例能力强的决策树。决策树学习的流程如下所示,这是一个递归过程,函数的输入D为样本集合:
def createTree(D):
if D中所有样本都属于同一类别C:
return C
if 所有特征都已经使用过了:
return D中样本数最多的那种类别
从还未使用的特征中选择最优划分的特征a
创建在特征a上的分支节点
for a 的每一个值
:
令
表示D中在特征a上取值为
的样本子集
分支节点在特征a上取值为
的分支 = createTree(
)
return 分支节点
划分选择
决策树学习的关键是如何选择最优划分的特征,随着划分过程不断进行,我们希望决策树的分支节点所包含的样本尽可能属于同一个类别,即节点的纯度越来越高。
信息熵
信息熵是度量样本集合纯度最常用的一种指标。假定样本集合D中包含n种类别,其中第k类样本所占的比例为,则D的信息熵定义为:
Ent(D)的值越小,则D的纯度越高。
信息增益
假定特征a有V个可能的取值,若使用a来对样本集合D进行划分,则会产生V个分支节点,其中第v个分支节点包含了D中所有在特征a上取值为
的样本,记为
。我们可以根据上式计算出
的信息熵,再考虑到不同分支节点所包含的样本数不同,给分支节点赋予权重
,即样本数越多的分支节点的影响越大,于是可以计算出用特征a对样本集D进行划分所获得的信息增益:
一般而言,信息增益越大,则意味着使用特征a进行划分所获得的纯度提升越大。因此,我们可以用信息增益来进行决策树的划分特征选择,即选择使Gain(D,a)最大化的特征a。
著名的ID3决策树学习算法就是以信息增益为准则来选择划分特征的。