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

Question

我编写了一个程序，使用信息增益函数(香农熵)来训练基于ID3算法构建的决策树以进行特征选择( 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  b2  b3 
    /    |   \ 
   y1   y2   [f1] 
             /  \ 
            a2   a3 
           /      \ 
          y3       y1 
  

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

1. 这种情况有名称吗？ 树不完整或类似的东西？
2. 有没有办法知道决策树是否会覆盖未知实例的所有组合(所有特征值组合)？
3. 这种“不完整性”的原因是否在于数据集的拓扑或用于训练决策树的算法(在本例中为 ID3)(或其他)？
4. 是否有一种方法可以使用给定的决策树对这些无法分类的实例进行分类？或者必须使用另一种工具(随机森林、神经网络......)？

Answer 1

这种情况不会发生在 ID3 决策树学习器中——无论它是否使用信息增益或其他启发式方法进行分割选择。 (例如，参见维基百科上的ID3 algorithm。)

ID3 决策树学习算法无法返回上面示例中的“训练树”。

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

从上一段(以及一般来说，ID3 算法的工作方式)可以看出，任何格式良好的向量 --- 形式为 (v1, v2, ..., vn, y )，其中 vi 是第 i 属性的值，y 是类值——应该可以通过以下方式分类算法在给定的训练集上学习的决策树。

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

回答您的问题:

1. 据我所知，没有。学习这样的“不完整树”​​是没有意义的。如果我们知道某些属性值永远不会出现，那么我们首先不会将它们包含在规范(列出属性及其值的文件)中。

2. 使用 ID3 算法，您可以证明(正如我在答案中概述的那样)该算法返回的每棵树都将涵盖所有可能的组合。

3. 您使用了错误的算法。数据与此无关。

4. 决策树学习中不存在不可分类的实例。人们通常将决策树学习问题定义如下。给定一个由 x1,x2,...,xn 组成的训练集 S，其形式为 xi=(v1i,v2i,...,vni,yi ) 其中 vji 是第 j 属性的值，yi 是示例 xi< 中的类值，学习一个函数(由决策树表示)f: X -> Y，其中X是所有可能的良构向量的空间(即所有属性值的可能组合)，Y 是所有可能的类值的空间，它最小化错误函数(例如错误分类示例的数量)。从这个定义中，您可以看到，要求函数 f 能够将任意组合映射到类值；因此，根据定义，每个可能的实例都是可分类的。