algorithm - 有关ID3算法如何选择最佳属性以将节点分支到子树的一些问题

Question

我正在为一个大学的例子学习id3算法，我有一些问题来理解如何选择最好的属性来创建在根中属性较少的新子树（直到达到叶子的创建）
所以我会举一个在老师讲稿上找到的实际例子，希望有人能给我一些实际的帮助来解决我的疑惑。
这是我要建立的最终决策树：
这个决策树简单地说，当我在餐厅时，我是否必须等待。
所以，例如：如果有很多顾客（顾客属性=很多），而且他们很饿（饥饿属性=是），而且菜肴类型是法式（类型属性=法式），那么这意味着我会等待。相反，如果没有赞助人（赞助人属性=否），我可以立即得出结论，我将不必等待。
好的，所以使用决策树非常简单。
这是表示上一个决策树示例的域的表（还有一些属性，但我认为这并不重要）：
所以，如果我说错了，请纠正我，这个表提供了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个例子分为两类，分别对应于：正面例子（与情况相关：我将在餐厅等待）和负面例子（与情况相关：我将不在餐厅等待）
因此，在前面的表中，我的决策树的根节点有以下情况：
+：x1、x3、x4、x6、x8、x12（正面示例）
-：x2、x5、x7、x9、10、x11（反例）
与这些示例相关的属性是上表中的属性：Fri、Hun、Pat、Price、Rain、Res、Type、Est
我认为这些属性并没有全部用于我的决策树，因为我达到了目标（一个结论），而没有使用全部。
现在我的情况是，我把我的例子分为正反两种情况，我必须选择第一个最好的属性（这是所有先前属性中更相关的属性）。
实际上，我必须执行第一步：
他选择赞助人属性作为第一个分支步骤的最佳属性。
这个属性可以有以下值：none（餐厅里没有顾客）、some（顾客很少）、full（餐厅里满是顾客），所以我必须在3个子树中分支（并在这些树的相关根节点标签中放置相关案例）
我的问题是：如何选择最佳节点？
我知道我必须使用熵值：
用于计算所有属性的信息增益：
在对所有属性都做了这些之后，我必须选择对信息增益有更高价值的属性作为最佳属性
但是我在前面的例子中发现了一些问题。有人可以告诉我如何将这些公式应用到我选择“顾客属性”作为“第一最佳属性”的具体情况中？
TNX太多了
安德莉亚

Answer 1

看起来你是从Wikipedia page on ID3中提取的符号，它不是标准的机器学习符号它告诉你要计算的是：
每一类样本在x类中的概率p（x）。这只是x类所考虑的集合的比例。
整个训练集的熵h（s）。公式很简单。
对于每个属性（变量、特征）A：
由于在A上分裂而产生的子集集。
t的每个元素t的熵h（t）（使用与之前相同的公式；可能缓存此公式以避免重复计算）。
信息增益ig（a），它是上一步分裂熵的函数。
如果您这样做，那么您就可以对特性A上的拆分质量进行度量。