3

我正在研究大学考试的ID3 算法,我有一些问题要了解如何选择最佳属性来创建根中属性较少的新子树(直到创建叶子)

所以我将在我的老师讲义上找到一个实际的例子,我希望有人能给我一些实际的帮助来解决我的疑惑。

这是我要构建的最终决策树:

在此处输入图像描述

这个决策树只是说明我在餐厅时是否必须等待。因此,例如:如果有很多顾客顾客属性 = many)并且他们很饿饥饿属性 = yes)并且菜式是法国菜type 属性 = French),那么这意味着我会等待)。相反,如果没有顾客顾客属性 = no),我可以立即得出结论,我不必等待。

好的,所以使用决策树非常简单。

这是代表前面决策树示例域的表(还有一些属性,但我认为这不是那么重要):

在此处输入图像描述

所以,如果我说错了,请纠正我,这张表为我提供了12 个显示常见情况的示例,ID3 算法将使用这些示例来构建我的决策树。

这是ID3算法的伪代码:

ID3 (Examples, Target_Attribute, Attributes)
    Create a root node for the tree
    If all examples are positive, Return the single-node tree Root, with label = +.
    If all examples are negative, Return the single-node tree Root, with label = -.
    If number of predicting attributes is empty, then Return the single node tree Root,
    with label = most common value of the target attribute in the examples.
    Otherwise Begin
        A ← The Attribute that best classifies examples.
        Decision Tree attribute for Root = A.
        For each possible value, v_i, of A,
            Add a new tree branch below Root, corresponding to the test A = v_i.
            Let Examples(v_i) be the subset of examples that have the value v_i for A
            If Examples(v_i) is empty
                Then below this new branch add a leaf node with label = most common target value in the examples
            Else below this new branch add the subtree ID3 (Examples(v_i), Target_Attribute, Attributes – {A})
    End
    Return Root

所以这个算法从创建一个根节点开始,在这个节点中,我把上表提供的所有示例按照我将事件分类的类进行了划分。

因此,在这种情况下,我将前面的 12 个示例仅分为 2 个类,它们对应于:正例(与情况相关:我将在餐厅等)和负例(与情况相关:我不会在餐厅等)餐厅

因此,查看上表,我的决策树的根节点有以下情况:

+:X1、X3、X4、X6、X8、X12(正例)

-:X2、X5、X7、X9、10、X11(反例)

与这些示例相关的属性是上表中的属性:Fri、Hun、Pat、Price、Rain、Res、Type、Est

我认为这些属性并未全部用于我的决策树中,因为我没有使用所有属性就达到了目标(结论)。

现在我的情况是,我将示例分为正例和负例,我必须选择第一个最佳属性(这是所有先前属性中更相关的)。

在实践中,我必须执行这第一步:

在此处输入图像描述

他选择顾客属性作为第一个分支步骤的最佳属性

这个属性可以有以下值:None(餐厅里没有顾客),Some(顾客很少),Full(餐厅里挤满了顾客),所以我必须在 3 个子树中分支(并放入这些树的相关根节点标签相关案例)

我的问题是:我必须如何选择最好的节点?

我知道我必须使用值:

在此处输入图像描述

用于计算所有属性的信息增益

在此处输入图像描述

在对所有属性执行此操作后,我必须选择具有更高信息增益值的属性作为最佳属性

但我发现在前面的例子中做这件事有些问题。有人可以告诉我如何将这些公式应用于我选择Patrons 属性作为第一个最佳属性的具体案例?

Tnx 这么多

安德烈亚

4

1 回答 1

0

看起来您从ID3 上的 Wikipedia 页面获取了符号,这不是标准的机器学习符号。这是它告诉您计算的内容:

  • 对于每个类别,样本在类别 x 中的概率 p(x)。这只是 x 类中所考虑的集合的比例。
  • 整个训练集的熵 H(S)。公式很简单。
  • 对于每个属性(变量、特征)A:
    • 在 A 上分裂产生的子集 T 的集合。
    • T 的每个元素 t 的熵 H(t)(使用与以前相同的公式;可能缓存它以避免重复计算)。
    • 信息增益 IG(A),它是上一步的分裂熵的函数。

如果你这样做了,那么你就可以衡量特征 A 的分割质量。

于 2013-06-15T18:38:37.823 回答