我正在研究大学考试的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 这么多
安德烈亚