decision-tree - 在决策树中找到最佳属性

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（在您的情况下为真或假）。如果一个特定的变量或属性，比如 x 有 3 个 YES 类的训练样本和 3 个 NO 类的训练样本（总共 6 个），则熵将为 1。这是因为这两个类的数量相同变量并且是您可以获得的最“混淆”。同样，如果 x 具有特定类的所有六个训练示例，假设是，那么熵将为 0，因为该特定变量将是纯的，因此使其成为我们决策树中的叶节点。

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

_{（来源：dms.irb.hr）}

现在考虑增益。请注意，在决策树的每一层，我们选择为该节点呈现最佳增益的属性。增益只是通过学习随机变量 x 的状态而实现的熵的预期减少。增益也称为 Kullback-Leibler 散度。增益可以通过以下方式计算：

_{（来源：dms.irb.hr）}

虽然这些问题要求您不要计算增益或熵，但有必要进行解释以说明我为什么选择特定属性。在您的情况下，我将假设可食用性是学习的属性。

如果您选择风味或颜色，请注意在这两种情况下您的熵均为 1 [0-1]，因为无论属性如何，您都有相同数量的可食用性“是”和“否”的训练实例。在这一点上，你应该看看增益。如果你用属性“颜色”锚定你的树，你将拥有更少的熵，因为属于集合 S 的每个属性的比例会更少。例如，注意“Red”和“Green”的叶子节点已经是纯的，分别是“yes”和“no”。从那时起，您就剩下一个属性可以使用，风味。显然，如果剩下的不止一个，则必须计算每个属性的增益，以确定哪个效果最好，并将其用作下一个“层”

此外，尝试绘制它并使用 Color 属性锚定树并计算增益 - 您会发现您更快地收敛到您的答案（纯节点）。

Answer 2

熵和增益绝对是信息论中更好的启发式方法，有助于选择最佳特征。然而，一种选择不如熵准确但效果很好的最佳属性的方法是 1 步前瞻，其工作原理如下：

CHOOSEBESTATTRIBUTE(S)
choose j to minimize J, computed as follows:
    S0 = all <x,y> in S with xj = O;
    S1 = all <x,y> in S with xj = 1;
    Y0 = the most common value of y in S0
    Y1 = the most common value of y in S1
    J0 = number of examples <x, y> in S0 with y not equal to y0
    J1 = number of examples (x, y) in S1 with y not equal to y1
    Ji = J0 + J1 (total errors if we split on this feature)
return j

资料来源：机器学习：Tom M. Mitchell，第 3 章