决策树完整性与非分类数据

Question

我编写了一个程序，在ID3算法的基础上，使用信息增益函数(Shanon熵)训练决策树，用于特征选择(split)。一旦我训练了一棵决策树，我就对它进行了分类，我意识到有些数据实例不能被分类：树上没有路径来对实例进行分类。

一个示例(这是一个示例，但我遇到了一个更大、更复杂的数据集的相同问题)：

• f1和f2是预测变量(特性)，y是范畴变量，值范围为：
  • f1：a1；a2；a3
  • f2：b1；b2；b3
  • y：y1；y2；y3

​

• 培训数据： ("a1“、"b1”、"y1")；("a1“、"b2”、"y2")；("a2“、"b3”、"y3")；("a3“、"b3”、"y1")；
• 受过训练的树： f2 / b1 \b1 b2 b3 /b3\ y1 y2 f1 /\ a2 a3 /\ y3 y1

实例("a1", "b3")不能用给定的树进行分类。有几个问题问到我：

1. 这种情况有名字吗？树不完整之类的？
2. 是否有一种方法可以知道决策树是否涵盖所有未知实例的组合(所有功能、值、组合)？
3. 这种“不完全性”的原因是数据集的拓扑，还是用于训练决策树的算法(在这种情况下是ID3)(或者其他)？
4. 是否有方法用给定的决策树对这些不可分类的实例进行分类？或者必须使用另一种工具(随机森林，神经网络.)？

Answer 1

这种情况不会发生在ID3决策树学习者身上--不管它是使用信息增益还是使用其他启发式来进行拆分选择。(例如，参见维基百科上的ID3算法。)

上面示例中的“经过训练的树”不可能由ID3决策树学习算法返回。

这是因为当算法选择一个d-valued属性(即一个带有d可能值的属性)来分割给定的叶子时，它将创建d新的子属性(每个属性值一个)。特别是，在上面的示例中，节点[f1]将有三个子节点，对应于属性值a1、a2和a3。

从上一段(通常，从ID3算法的工作方式来看)，任何格式良好的向量--表单(v1, v2, ..., vn, y)，其中vi是i-th属性的值，y是类值--都应该按照算法在给定的训练集上学习的决策树进行分类。

你介意提供一个链接到你用来学习“不完整”树的软件吗？

回答你的问题：

1. 就我所知没有。学习这种“不完整的树”是没有意义的。如果我们知道某些属性值永远不会发生，那么首先我们就不会将它们包括在规范(列出属性及其值的文件)中。
2. 使用ID3算法，您可以证明--正如我在答案中所描述的--该算法返回的每一棵树都将涵盖所有可能的组合。
3. 你用错了算法。数据与此无关。
4. 在决策树学习中不存在不可分类的实例.通常定义决策树学习问题如下。给定形式的示例S集x1,x2,...,xn，其中vji是j-th属性的值，yi是示例xi中的类值，学习一个函数(由决策树表示) f: X -> Y，其中X是所有可能的格式良好的向量(即所有可能的属性值组合)的空间，Y是所有可能的类值的空间，该空间最小化了错误函数(例如，错误分类示例的数目)。从这个定义中，您可以看到，函数f需要能够将任何组合映射到类值；因此，根据定义，每个可能的实例都是可以分类的。