非二元决策树到二元决策树（机器学习）

Question

这是作业问题，所以我只需要帮助可能是/不会，很少有评论将不胜感激！

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

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

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

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