machine-learning - 非二元决策树到二元决策树(机器学习)

Question

这是家庭作业问题，所以我只需要帮助可能是/否，并且很少评论将不胜感激!

• 证明:任意树(非二叉树)可以转换为等效的二叉决策树。

我的回答: 每个决策都可以仅使用二元决策来生成。因此，决策树也是如此。 我不知道正式的证据。就像我可以与熵(实际上是增益)争论一样，因为该节点将是 E(S) - E(L) - E(R)。在此之前可能是 E(S) - E(Y|X=t1) - E(Y|X=t2) - 等等。

但是不知道怎么说？!

Answer 1

您可以给出类似的建设性证明，演示如何将任意决策树转换为二元决策树。

假设您位于节点 A，并且您可以根据您的示例是否满足要求 B、C 或 D 来选择遍历到 B、C 和 D。如果这是正确的决策树，则 B 、C 和D 是互斥的并且涵盖了所有情况。

A -> B
  -> C
  -> D

由于它们是互斥的，您可以想象将树分成二元决策:B 或不是 B；在 not B 分支上，我们知道 C 或 D 必须为真，因为 B、C 和 D 是互斥的并且涵盖了所有情况。换句话说:

A -> B
  -> ~B
  ---> C
  ---> D

然后，您可以将 B 之后的任何内容复制到 B 之后的分支上，执行相同的简化。 C 和 D 相同。