在决策树中查找最佳属性

Question

我遇到过一个问题

Color   Flavor  Edibility
Red     Grape      Yes
Red     Cherry     Yes
Green   Grape      Yes
Green   Cherry     No
Blue    Grape      No
Blue    Cherry     No

在这个问题中,它只是在没有任何计算的情况下进行分析,猜测最佳属性(颜色或味道)

有人可以解释如何在不计算熵的情况下猜测这一点,等等

Answer 1

我知道这个问题有点老了,但是如果你仍然感兴趣的话:一般来说,更短更宽的树会"更好".考虑这样一个事实,它将需要额外的决定来到达高大树中的节点.

你真正要看的是每个内部决策节点的熵和增益.

熵是具有特定变量的不确定性或随机性的量.考虑另一种方式,它是衡量特定节点的训练样本的同质性的度量.例如,考虑一个具有两个类的分类器,YES和NO(在您的情况下为true或false).如果一个特定的变量或属性,比如x有三个类YES的训练样例和三个训练样例NO(总共六个),则熵将为1.这是因为这两个类的数量相等变量,是你可以得到的最"混乱".同样地,如果x具有特定类的所有六个训练示例,例如YES,则熵将为0,因为该特定变量将是纯的,因此使其成为我们的决策树中的叶节点.

熵可以通过以下方式计算:

熵方程http://dms.irb.hr/tutorial/images/entropy_eq.gif

现在考虑收益.请注意,决策树的每个级别,我们选择为该节点提供最佳增益的属性.增益只是通过学习随机变量x的状态实现的熵的预期减少.增益也称为Kullback-Leibler分歧.可以通过以下方式计算增益:

http://dms.irb.hr/tutorial/images/gain_eq.gif

虽然问题要求您不要计算增益或熵,但解释为什么我选择特定属性是必要的.在您的情况下,我将假设可行性是学习属性.

如果您选择风味或颜色,请注意您在两种情况下都具有1 [0-1]的熵,因为您具有相同数量的训练实例,其可用性为"是"和"否",无论属性如何.在这一点上,你应该看看收益.如果使用属性"color"锚定树,则由于属于集合S的每个属性的比例将更小,因此您将具有更少的熵.例如,请注意"Red"和"Green"的叶节点已经是纯粹的,分别为"yes"和"no".从那时起,你有一个属性可以使用,味道.显然,如果剩下一个以上,你必须计算每个属性的增益,以找出哪个最好并将其用作下一个"层"

另外,尝试将其绘制出来并使用Color属性锚定树并计算增益 - 您会发现您更快地收敛到您的答案(纯节点).