从数据创建决策树

create decision tree from data

我正在尝试根据数据创建决策树。我将这棵树用于猜动物游戏类型的应用程序。用户用 yes/no 回答问题，程序猜测答案。该程序用于作业。

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

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

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

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

I searched Whosebug 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. 选择一个属性圆周率
  3. 将 S 分成两组 S1、S2 - S1 持有 pi，而 S2 不持有。为当前节点创建两个子节点，分别将S1和S2移动到它们
  4. 如果样本子集不为空，则对每个样本子集重复 S'=S1、S'=S2。

一些建议：

  • 在每次迭代中，您基本上将当前数据分成 2 个子集，包含 pi 的样本和不包含 pi 的数据。然后创建两个新节点，它们是当前节点的子节点，并为每个节点重复该过程，每个节点都有相关的数据子集。
  • 智能算法选择 属性 pi（在步骤 2 中），以尽可能降低树的高度（找到最佳解决方案是 NP-Hard, but there are greedy approaches to minimize entropy，例如）。
  • 创建树后，一些pruning to it is done, in order to avoid overfitting。
  • 此算法的一个简单扩展是使用多个独立工作的决策树 - 这称为 Random Forests，根据经验通常会得到很好的结果。