决策树完整性和未分类数据

Question

我制作了一个程序，使用信息增益函数（训练基于ID3算法的决策树Shanon entropy) 用于特征选择（拆分）。一旦我训练了一个决策树，我就测试它来对看不见的数据进行分类，我意识到有些数据实例无法分类：树上没有对实例进行分类的路径。

一个例子（这是一个说明性的例子，但我在更大更复杂的数据集上遇到了同样的问题）：

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  b2  b3 
  /    |   \ 
 y1   y2   [f1] 
           /  \ 
          a2   a3 
         /      \ 
        y3       y1

实例 ("a1", "b3") 无法用给定的树分类。我想到了几个问题：

Answer 1

这种情况不会发生在 ID3 decision-tree 学习者身上——无论它是否使用信息增益或其他启发式方法进行拆分选择。（例如，参见维基百科上的 ID3 algorithm。）

ID3 decision-tree 学习算法无法返回上面示例中的 "trained tree"。

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

根据上一段（一般来说，根据 ID3 算法的工作方式）可以得出任何 well-formed 向量——(v1, v2, ..., vn, y) 形式，其中 vi 是第 i 个属性的值，y 是 class 值---算法在给定列车上学习的决策树应该 class 可以设置。

您介意为您用来学习 "incomplete" 树的软件提供 link 吗？

回答您的问题：

据我所知没有。学习这样的东西没有意义 "incomplete trees." 如果我们知道某些属性值永远不会出现，那么我们一开始就不会将它们包含在规范（您列出属性及其值的文件）中。
使用 ID3 算法，您可以证明---正如我在答案中勾勒的那样---算法返回的每棵树都将涵盖所有可能的组合。
您使用了错误的算法。与数据无关。
在decision-tree 学习中没有class不可能的实例。人们通常定义一个 decision-tree 学习问题如下。给定 S 个示例 x1,x2,...,xn 的训练集 xi=(v1i,v2i,...,vni,yi)，其中 vji 是第 j 个属性的值，yi 是class 示例中的值 xi，学习一个函数（由决策树表示）f: X -> Y，其中 X 是所有可能 [=68] 的 space =] 向量（即所有可能的属性值组合）和 Y 是所有可能的 class 值的 space，它最小化误差函数（例如 misclass 化的例子）。从这个定义可以看出，需要函数 f 能够将任意组合映射到 class 值；因此，根据定义，每个可能的实例都是 class 可能的。

Decision tree completeness and unclassified data