英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料

二、初步

我们简要描述一些描述树的必要术语(更多细节见Aho et al.[3]):

定义

1. 图G = (V. E)由有限的非空节点集V和边集E组成，如果边是顶点的有序对(u, w)，则说图是有向的。
2. 图中的路径是(v₁,v₂), (v2, v3),...(v_n-1，v_n)形式的边序列。我们说路径是从v₁到v_n长度为n。
3. 无环的有向图称为有向无环图。有向(或有根)树是一个有向无环图，它满足以下性质:

a)只有一个节点，称为根节点，它没有边进入。根节点包含所有类标签。

b)除了根节点，每个节点都恰好有一条进入边。

c)从根到每个节点有一个唯一的路径。

4)如果(v, w)是树中的一条边，则v被称为父，w是v的子;如果v到w(v不等于w)有一条路径，则v是w的真父集，w是v的真子集。

5）没有适当后代的节点称为叶(终端)。所有其他节点(根除外)称为内部节点。

6)树中节点w的深度是从根到d的路径长度，树中节点v的高度是。从v到叶节点的最大路径。树的高度就是它的根的高度。树中节点v的级别等于树的高度减去深度。

7)有序树是每个节点的子节点都是有序的(通常从左到右)。

8)二叉树是一种有序树

a)节点的每个子节点可以区分为左子节点或右子节点:

b)没有节点有一个以上的左子节点或一个以上的右子节点。

9)平衡二叉树的一个节点v (1 L) / (2 L R), L和R是左一个右子树的节点数的v。平衡二叉树,O lt;alpha;le; 1,如果每个节点之间的平衡处于alpha;和1-alpha;，平衡二叉树也称为完全树。

我们用t表示任意一棵树。图1显示了一个属判定树的例子。

1. 如果两个内部节点包含至少一个公共类，则称节点具有重叠类。参见图2
2. 从根到终端的平均层数节点被称为树的平均深度。树的每一层内部节点的平均数量，称为树的平均宽度。一般来说，树的平均宽度将反映给分类器准确性的相对权重，而平均深度树将反映给效率的权重{77}。

让我们也介绍以下内容：

设（X,Y）是联合分布的随机向量，q维向量X表示一个模式或特征向量，Y表示X的相关类标签，X的组成部分是特征。

定义：

1. X被称为有序或数值模式(参见Breiman等人[7])，如果它的特征从一个有序集合中取值，而如果它的特征从一个没有自然顺序的集合中取值。有序特征或数值特征可以具有离散值或连续值。为简单起见，我们假设X是连续有序类型;此外，让X从R^q取值，让Y取整数值{1,2,hellip;,J};i.e,有不同J级别的关注。一般来说，任何分类方案的目标，特别是DTC，都是基于观察X来估计Y。
2. 决策规则d(·)是用d(X)将R^q映射到表示特征向量x的类标号的{1.2,hellip;,J}的函数，d的真实误分类率用R^＊(d)表示，

R^＊(d)=p(d(X)ne;Y) (1)

p(·)表示概率。

让我们将可用的标记样品表示为￡={(X_n,Y_n).n=1,2,...,N}。

1. 通常可用的标记样本分为两部分:训练样本￡⁽¹⁾和测试样本￡⁽²⁾。一般取￡⁽¹⁾随机抽取￡的2/3，￡⁽²⁾取￡的1/3。
2. 由于真实误分类率R^＊(d)的计算比较困难，所以通常从训练集或者测试集来估计。让我们将估计的误分类率表示为R(d)。当用训练集估计R^＊(d)时，R(d)称为R^＊(d)的再替换估计，当用测试样本估计R^＊(d)，R(d)称为R^＊(d)的测试样本估计，在这种情况下，误分类率简单地用被微分类地样本数与用于测试地样本总数的比值来估计。确定误分类率的一种更为复杂的方法是K-fold交叉实验方法。在这里，数据被￡分为k个几乎相等的部分￡¹，￡²,...,￡^k（通常K=10)。然后￡-￡^k用于训练样本，￡^k用于测试样本，然后找出每个K的误分类率的测试样本估计值，并在K上取平均值。注意，当K=N(标记样本大小）时N-fold交叉验证也被称为“遗漏”估计值。

三、DCT的潜力和问题

DTC具有吸引力的原因如下[40]，[52]，[53]，[59]，[77]，[81]

1. 全局复杂决策区域(特别是在高维空间中)可以通过合并树的各级较简单的局部决策区域来近似表示。
2. 与传统的单级分类器不同，在单级分类器中，每个数据样本都针对所有的类进行测试，从而降低了效率，在树分类器中，一个样本只针对特定的类子集进行测试，从而消除了不必要的强制要求。
3. 在单级分类器中，只使用一个特征子集进行分类。这个特征子集通常是用全局最优准则来选择的，例如最大平均类间可分性[77]。DTC的另一方面，我们可以在树的不同内部节点上灵活地选择不同的特征子集，这样，选择的特征子集可以在该节点上的类中进行最佳区分。这种灵活性实际上可以提供比单级分类器更好的性能[58],[97]。
4. 多变量分析中，特征数和类，我们通常需要估计高维，通常分布(可能是多模态的)或某些参数或类分布，如先验概率，从一个给定的小尺寸训练数据集。这样做时，人们通常会面临“高维度”的问题。在DTC中，通过在每个内部节点上使用较少数量的特性，可以避免这个问题，而不会过度降低性能。

另一方面，DTC可能存在的缺点如下：

1. 重叠(定义见第2节)，特别是类的数量较大时，会导致终端的数量远远大于实际类的数量，从而增加搜索时间和内存空间需求。对这个问题可能的解决办法将在第四节讨论。
2. 在树中，误差会逐级累积，Wu等人[95]指出，不能同时优化精度和效率;对于任何给定的任何精度，必须满足效率的一个界限。
3. 最后，设计一个最优的直接转矩控制系统可能会遇到困难。DTC的性能很大程度上取决于树的设计。
4. DTC的设计

DTC的主要目标是:

1. 尽可能多地对训练样本进行正确分类;
2. 对训练样本以外的样本进行泛化，使不可见样本能够以尽可能高的准确率进行分类;
3. 当有更多的训练样本可用时，易于更新。（即递增的，参见第4节）

那么我们尽可能建立一个简单的结构，使得DTC的设计可以分解为以下任务[45]，(49)，[50]:

1. 适当选择树型结构;
2. 选择在每个内部节点上使用的特征子集;
3. 每个内部节点的决策规则或策略的选择。

当采用Bayes的观点时，最优树设计可提出如下优化问题:

受限于:有限的培训样本容量

其中Pe为出错的总体概率，T为树结构的具体选择，F和d分别为内部节点要使用的特征子集和决策规则。上述约束的含义是，在有限的训练样本容量下，类条件密度估计的准确性可能会随着特征数量的增加而下降。这也是众所周知的休斯现象[38]。在实践中，这就限制了可以使用的特性的数量。也就是说，在￡之外，可用的特性，形成一个大小为N的新特性集。例如，通过子集选择或结合特性,通常在。注意固定大小N,选择作为最佳特征子集，错误决策规则的最小概率，根据定义，是单阶段贝叶斯规则。但是如果允许选择不同的特征子集来区分不同的组类（例如，一个是树形结构），那么可以得到比贝叶斯决策规则预测的更小的错误概率。

前面的优化问题可以分两步解决问题[50]：

步骤一 对于给定的T和F，求d^＊=d^＊(T,F),使

步骤二 很好的处理T^＊和F^＊

这里需要指出的是，到目前为止还没有提到时间复杂度和计算速度。包括这些因素将使优化问题更加困难。Swain和Hauska [77]， Wang和sun[81]-[84]提出了一些包括时间效率的方法进入分析（例如：速度）。这些问题将在本文的后半部分进行讨论。

然而，当采用信息论的观点时，树的优化设计涉及到最大化树的每一层的平均互信息增益。我们稍后将回到这一点。

1. 决策树结构设计
2. 熵减少和信息论方法
3. DTC中的特征选择
4. 决策树和神经网络

近年来，神经网络在信号处理和模式识别等领域的研究已成为热门课题。实际上，神经网络在模式识别问题上的应用可以追溯到20世纪50年代的简单感知器。在文献(cf. Rumelhart et al. [67]和Lippmann[55]中引用了神经网络的Manv优势。最重要的对于模式识别问题，它们似乎是基于神经网络的方法通常是非参数化的事实，即使可能合并统计信息以提高其性能（收敛速度等）。此外，神经网络可以提取特征的非线性组合，而得到的判别曲面可能非常复杂。神经网络的这些特征在决策树分类器中非常有吸引力，因为在决策树分类器中，必须确定适当的特征子集和每个内部节点的决策规则。“目前有各种各样的神经网络模型，如Hopfield网络、Boltzmann机器和Kohonen自组织特征映射等；然而，目前最流行的网络是多层前馈网络。

一个多层前馈神经网络是一个简单的无环有向图，由几个称为神经元的简单处理元素组成。每一层的神经元与前一层的神经元完全连接，每个神经元将其加权输入相加，然后通过某种非线性(通常为s形函数)将其传递出去。第一层是输入层，最后一层是输出层，中间层称为隐藏层。参见图6。然后在超级学习中，将训练样本分配给网络的输入，并调整神经元之间的连接权值，使网络的实际输出与期望输出之间的误差最小。

常用的误差准则是实际输出与期望输出之间的总和方误差。有许多学习算法来执行这个学习任务；一个常用的学习规则是反向传播算法，它基本上是一种(有噪声或随机)辐射下降优化方法。请注意，一旦确定了网络的结构，即选择隐藏层数和每个隐藏层中的神经元数，然后通过学习规则调整网络权值，直到获得最优权值。相应的权值(连同网络结构)在特征空间中创建决策边界。如何选择网络结构的问题超出了本文的研究范围，是当前神经网络研究的一个热点。值得一提的是，在大多数实际应用中，只使用一个隐藏层的网络。参见第5节和[55]中的注释。

神经网络如何帮助我们设计决策树？Gelfand和Guo[31]提出如下建议。回想一下,在每个内部节点t树的一个想找到最优（在当地的意义）和相应的表面决定分区特征子集C (t), t组类,为C (t_l)和C (t_R),两个子集类节点t_l和t_R分别。也就是说，这里涉及两个嵌套优化任务。外部优化循环搜索类的最优划分为两个(可能不相关联的)类子集，内部优化循环搜索特征空间中的最优决策曲面，执行外部优化任务。假设现在我们知道了C(t)划分为C (t_l)和C (t_R)，并且只在特征空间中寻找(最优)决策面。当然，这可以很容易地通过一个简单的多层前馈网络来实现。剩下的问题是如何将C(t)分割成C (t_l)和C (t_R)。如第四章A节所述，各种各样的分割规则。其中一个可能的规则是图CART中使用的杂质还原准则。也就是说，我们可以将考虑C(t)划分为C (t_l)和C (t_R)的各种分区，然后选择杂质减少最大的分区(详见4-A节和[7])。当然，当类的数量很大时，穷举搜索可能是不切实际的。在第三种情况下，可以执行某种类型的贪婪搜索。

1. DTC的决策规则和搜索策略
2. 其他与树有关的问题
3. 增量树设计

对于训练样本，有两种可能:

1. 在决策树形成时，整个训练样本都是可用的设计;

2)训练样本以流的形式到达。

对于情况1，一旦设计了一棵树，任务就完成了，这样的设计算法被称为非增量算法。然而，对于第二种情况，我们有两种选择:

a)当新的训练样本可用时，丢弃当前树并使用扩大的训练集构造一个替换树

b)根据新的可用信息修改现有的树。

与b)相对应的过程称为增量决策树设计算法。当然，如果在设计时所有的训练样本都是可用的，那么增量决策树设计算法产生的树应该与这些树相同。Utgoff [79]开发了一种这样的增量算法。

1. 树泛化

在设计DTC时，必须始终牢记设计的树将用于分类未见过的测试样本。

考虑到这一点，我们有两个选择:

1. 设计一个正确分类所有训练样本的决策树，也被称为完美树[62]，[63];然后选择最小的完全树;
<l

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[587738]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

</l