machine-learning - 非二叉决策树到二叉决策树（机器学习）

Question

这是作业问题，所以我只需要帮助可能是/否，我们将不胜感激！

• 证明：任意树（NON binary tree）可以转化为等价的二叉决策树。

我的回答：每个决定都可以仅使用二元决策来生成。因此，决策树也是如此。我不知道正式的证据。就像我可以与熵（实际上是增益）争论的那样，该节点将是 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；在非 B 分支上，我们知道 C 或 D 必须为真，因为 B、C 和 D 是互斥的并且涵盖所有情况。换句话说：

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

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