决策树中的信息熵

决策树是机器学习中常用的一种分类算法,常被用于专家系统中。直观来说,这种分类技术基于问题答案来构建决策树,每个问题对应于一个特征,不同的答案将会形成不同的分支。下面是一个具体示例图:

上面的决策树是对邮件进行分类,首先是看邮件的发送地址是否为“myEmployer.com”,如果是,就把它归到必读邮件类别,否则,再判断邮件内容中是否含有“曲棍球”,如果包含有,则邮件是来自朋友,归到马上需要阅读的类别,否则,可视为垃圾邮件,归到非必读类别。

还是以上面的图为例,决策树的叶子节点表示某个类别,其它节点表示数据的特征,通过判断数据是否具有该特征,来做进一步的分类,也就是生成新的分支。那什么时候不再进行分支呢?是当具有该特征的所有数据都可以归到同一个类别时,或者所有特征都已经参与判断后,就不需要进行分支了,因为这时候已经得出确定的答案。比如上面图中的第一个特征是发送邮件地址,通过地址判断邮件是否来自公司,如果是的话,这些邮件都可以归到必读类别,因此不需要再分支,必读类别就作为一个叶子节点了。

但有一个问题,就是训练数据中有多个特征,我们怎么知道应该先选择哪个特征进行判断呢,比如典型的,选择哪个特征作为决策树的根节点呢?这里就需要引入信息熵的概念,这是构建决策树非常关键的地方。

熵是香农信息论中的一个概念,用来衡量信息的混乱程度,熵值越高,表示信息越混乱。而我们在决策树的构建过程中,在选择某特征值进行判断时,需要结合熵这个概念来进行。选择哪个特征进行分支,都会分割数据集,我们需要算出分割数据集后的信息熵,然后将分割之前的信息熵值减去按这种方式分割后的信息熵。相减之后得到的值叫信息增益,信息增益值越大,表示这样分割后数据的混乱程度越低,因此就优先选择这个特征来分割数据。到这里我们就知道了,特征选择的依据是信息增益。

上面的描述可能还是让人云里雾里。再详细一点说,熵是信息的期望值,而信息的定义是:L(x) = log2p(x),其中p(x)表示数据属于x类别的概率。而如果有多个数据信息值,我们就有多个x值,于是熵的计算公式为:

也就是将每个信息值乘以属于该类别的概率值后累加,再取负数。假设我们在分割数据集之前,熵值为H1,分割后熵值为H2(有多个特征这里就有多个值),那每次在选择特征进行数据集分割时,只需要看看H1-H2(多值)得到的值中哪个最大,就选择相应的特征进行分割就好了。

这篇文章,我只是把信息熵、信息增益这些初学者容易迷糊的概念描述一下,决策树中还有不少其它的内容,需要学习的,建议去读机器学习方面的专业书籍。

微信扫码,进入【技术人成长】社群逛逛。