algorithm - 从数据创建决策树

Question

我正在尝试从数据创建决策树。我将树用于猜动物游戏类型的应用程序。用户用是/否回答问题，程序猜测答案。该程序用于家庭作业。

我不知道如何从数据创建决策树。我无法知道根节点是什么。每次的数据都会不同。我不能用手做。我的数据是这样的:

Animal1: property1, property3, property5
Animal2: property2, property3, property5, property6
Animal3: property1, property6
etc.

我搜索了 stackoverflow，发现了 ID3 和 C4.5 算法。但我不知道是否应该使用它们。

有人可以指导我，在这种情况下我应该使用什么算法来构建决策树？

Answer 1

I searched stackoverflow and i found ID3 and C4.5 algorithms. But i don't know if i should use them.

是的，你应该这样做。它们是非常常用的决策树，并且有一些很好的开源实现。 ( Weka's J48 是 C4.5 的示例实现)

如果您需要从头开始实现某些内容，则实现一个简单的决策树相当简单，并且是迭代完成的:

1. 设标记样本集为 S，属性集为 P={p1,p2,...,pk}
2. 选择属性 pi
3. 将 S 拆分为两个集合 S1,S2 - S1 包含 pi，而 S2 不包含。为当前节点创建两个子节点，并将S1和S2分别移动到它们
4. 对每个样本子集重复 S'=S1、S'=S2(如果它们不为空)。

一些提示:

• 在每次迭代中，您基本上将当前数据分为 2 个子集:包含 pi 的样本和不包含 pi 的数据。然后，您创建两个新节点(它们是当前节点的子节点)，并对每个节点重复该过程，每个节点都具有相关的数据子集。
• 智能算法选择属性 pi (在步骤 2 中)，以尽可能最小化树的高度(找到最佳解决方案是 NP-Hard ，但也有贪婪的方法例如，最小化 entropy )。
• 树创建后，一些pruning就完成了，以避免 overfitting .
• 该算法的一个简单扩展是使用多个独立工作的决策树 - 这称为 Random Forests ，并且根据经验通常会得到很好的结果。