在加州大学，圣地亚哥医疗中心，当一个心脏病发作的病人被收诊后，在头24小时期间有19个变量被测量。包括血压、年龄以及另外17个顺序排列的二元变量。这些变量用来概括说明医疗症状作为病人情况重要的指示器。
最近医疗研究的目标（见第6章）是研究出一种方法，基于最初24小时的数据识别出高危险病人（他们的存活时间将不超过30天）。
图1.1描述了在该研究中产生的树型结构分类规则。字母F代表不是高危险；G代表高危险。
这些规则通过至多三个问题的Yes-No的回答将新进病人归类为F或G。有人可能会简单地提了猜疑，即用常规的统计分类方法可能会产生更加精确的分类规则。当我们进行试验后发现，用常规的统计方法产生的规则复杂的多，而精确度却差得多。
用于构造树型结构规则的方法论是这本专著的主要内容。
一般的分类问题同上面所述的医疗诊断问题相类似。对一些实例或对象进行度量。基于这些度量，我们预测给定的实例应该归入哪一类。
例如，我们可以根据臭氧水平将洛杉矶盆地的时间分成以下三类：
类一：不用警戒（低臭氧）
类二：第一阶段警戒（中等程度臭氧）
类三：第二阶段警戒（高臭氧）
对于当前日期，度量是在很多气象学的变量上作出的，例如温度、湿度、上层大气情况以及空气传播的污染物的当前数量水平。由加州空气资源委员会（Zeldin和Cassmassi,1978））提供基金的是一个项目目的是探索出一些方法用当前日期的度量来预测随后日期的类别。
美国环保署的工程有一个目标：完全分析一个复杂的化学化合物的原子组成速度慢而费用昂贵。测量它的质谱做起来将回更快而且相对来说费用比较低廉。测量质谱能否精确地预测，举例来说，化合物是在类1（包含一个或更多个氯原子），或是在
类2（不包含氯原子）中？
（进一步讨论请见第7章）
这些问题它们的目标都是一致的。给定一系列实例或对象的变量，找出一个系统化的方法预测该实例或对象属于哪一类。对任何问题，一个分类器或一套分类规则是预测一个实例归属哪一类的系统化的方法。
为了给出一个更加精确的简洁明白的陈述，将这些度量采用预先指定的次序进行排列。即将度量分别记为x1、x2，……这里，x1表示年龄，x2表示血压等等。定义作用在实例上的度量（x1、x2，……）作为相应实例的度量向量X。度量空间X被定义为包含所有可能的度量向量。
例如，在心脏病发作的实例中，X是一个19维的空间，其中第一个坐标x1（年龄）的范围为0到200的所有整数值；第二个坐标，血压可能被定义为范围50到150的连续值。对于X可能有一些不同的定义。重要的是对于X的任何定义具有这样的性质：相对于任何实例我们希望度量向量X在空间X中分类到一个点。
假定实例或对象分成J个类。给类编号为1，2，……J，C记为分类集，即C={1，……，J}。
预测类成员的一个系统化的方法是：指定C中的类成员到X中的每一个度量向量X的规则，即，对于任何X∈X，该规则指派类{1，……，J}中的一个给X。
定义1.1，分类器或分类规则是定义在X上的一个函数d(x)，对于每一个X，d(x)等于数1，2，……，J之一。
另外一种考虑分类的方法是，定义Aj满足d(x)=j的X的一个子集，即：
Aj={x;d(x)=j}
集合A1，……，AJ相互之间不相交，并且X
=
，这样，Aj构成了X的一个分割，下面给出等价定义：
定义1.2
分类器是将X分割为J个互不相交的子集A1，……，Aj，X
=
，对于每一个X∈Aj，预测的类为j。
1.2 使用数据来构造类
分类器的构造并非空穴来风。它们建立在过去经验的基础上。例如，医生知道，年纪较大的心脏发作病人如果伴有低血压通常情况下是高危险的。洛杉矶人知道炎热、高污染的天气将延续到下一天。
构造系统分类器时，过去的经验是根据学习样本概括出来的。这包括观察过去的N个实例的度量数据以及它们实际的分类。
医疗诊断项目的学习样本包括被医院收诊的215个心脏病人的记录。这些病人在最初的24小时里都是存活的。记录包含了最初的19个度量值以及那些没有活过至少30天的病人的标识。
臭氧分类项目的学习样本包含长达6年（1972—1977）的超过400个气象学变量的每天的度量值以及每小时一次的在洛杉矶盆地30个测位的空气污染度量。
对于氯项目的数据包含已知分子结构的大约30，000种化合物的质谱。对于每种化合物的质谱能够表达成与分子重量相等的向量维的度量。30，000个度量向量的集合，其维数变化的范围是50左右一直到超过1000。
我们假设这本专著后面的所有部分对分类器都建立在学习样本的基础上。
定义1.3
学习样本包含N个实例的数据（X1，j2），……（XN，jN），其中Xn∈X，
学习样本记为L，即，
L={（X1，j2），……（XN，jN）}
我们区分出现在度量向量中的两类普通变量类型。
定义1.4
如果一个变量的度量值是一个真实的数据，则称该变量为顺序型或数值型，如果一个变量在一个有限的没有自然顺序的集合中取值，则该变量称为类别类型。
例如，类别类型的变量，可以在集合{red，blue，green}中取值，在医疗数据中，血压、年龄为顺序型的变量。
定义1.5
如果所有度量向量Xn，具有固定的维数，那么这些数据具有标准的结构。
在医疗和臭氧项目中，固定数目的变量集对每一个实例（或日期）进行度量，数据具有标准的结构。质谱数据不具有标准结构。
1.3 分类分析的目的
根据问题的不同，分类研究的基本目的或者是为了产生一个准确的分类器，或者是为了揭示问题的结构。如果我们的目标是后者，则我们应设法理解是什么变量或者变量间的交互作用来驱动现象——即，给出条件的简单特性的描述（度量变量X∈X）决定何时一个对象属于一个类而不是另一类。这两个目的并不是排斥的。根据我们的经验，在通常情况下，分类目标既是为了准确地预测也是为了准确地理解，有时这个或者那个目的强调的更多一些。
在质谱项目中，强调的是预测。其目的是产生一个有效的、准确的在线算法，接受未知化合物质谱的输入，将化合物分类到含氯或不含氯的类中。
在臭氧项目中两个目标都有。研究理解大气变量及其相互之间的作用与警报水平的日期联系起来是产生分类器的一个必要的组成部分。
图1.1所示的树结构分类规则给出了对医疗诊断问题的一些有趣的知识深入观察。所有血压小于或等于91的病例都被预测为高危险，对于血压高于91的病例，分类依赖于年龄以及是否出现静脉窦心动过速的现象。为了达到区分高或低危险病例的目的，一旦年龄被记录，则只有两个变量需要进行测量。
良好分类过程的一个重要标准不仅是要产生一个准确的分类器（在有限数据的基础上），而且还要提供深入可理解的数据的预测结构。
目前许多可利用的统计技术适合于所有变量具有相同类型，具有标准结构的规模较小的数据集，其潜在的假设为现象是同类的。也就是说，整个度量空间变量之间的关系是相同的，这导致模型只有少量必要的参数来跟踪所包含的各种要素的作用。
包含许多变量、更多结构的大数据集能够被识别并尝试用各种不同的方法。但是大本身并非必然包含丰富的结构。
对数据集感兴趣的原因不仅仅是它的大小还有它的复杂性，复杂性可能包含如下一些考虑：
高维
混合的数据类型
不标准性
以及不均匀性，这可能是最具有挑战性的。即，在度量空间的不同部分变量之间的相互关系也不同。
随同复杂数据集出现的是“维的咒语”（Bellman提出的一个词组，1961）。其困难是维数越高，数据点的分布就越稀少，伸展得越分散。在一个单元间隔中10个点还算近邻，但是10个点分布在具有10维的单元矩形上就象是沙漠里的绿洲。
例如，用100个点，在一个单元间隔中构建一个10单元柱状图是一个合情合理的过程。若有M维，在每个维上使用10个间隔的柱状图将产生的10M单元，即使M是一个中等大小的数，也需要一个非常大的数据集来得到一个可觉察到的柱状图。
另外一种观察“维的咒语”的方法是在M维上指定分布所需的参数数目。
一般：O（M2）
二元：O（2M）
除非给出强制的假定变量之间无关，否则需要详述M维分布的参数数目将比O（M）增加得快很多。换一句话说，数据集的复杂性随同维数的增长快速增长。
随着计算机的加速使用，具有变量维或混合数据类型、不均匀性等性质的复杂的高维数据库将不再稀有。
针对数据集维数的不断增长，最广泛使用的多元过程都包含有对维的约简处理。回归和判别式分析中的渐近式变量选择和变量子集选择是维的约简处理的一些例子。
虽然目前多元约简工具的缺点被广泛认识到，但它们是针对明确需求的。为了分析和理解复杂的数据集，需要找出一些方法来智能地选择数据中显著的特征，排除背景噪音，并以可理解的概述信息反馈给分析者。
给定一个分类器，也就是说，给定定义在x上的函数d(x)，x的值取自C，我们记R*(d)为其“事实的错误分类率”。在本节提出的问题是：哪些是事实及怎样评估。
观察分类器的准确性（也就是评估R*(d)）的方法之一是用已知分类的数据测试分类器的准确度。例如，在臭氧项目中，分类器用1972-1975年的数据建立，准确性用1976-1977年的数据评估。即，用以前的数据建立函数d(x)，然后用1976-1977年的数据被错误分类的比例来评估R*(d)。
在大数据量光谱项目中，30,000个光谱数据随机分入两个集合，一个有20,000个数据，一个有10,000个数据。前者用以构建分类器，后者运行分类器，错误分类的比例用来评估R*(d)。
R*(d)的值可以由以下方法赋以概念：用L构建d 。然后，抽取另一很大的（实质上无限）的，与L取自同一人群的数据集，找出这些数据的正确分类，并用d(x)预测其分类。用d错误分类的比例就是R*(d)的值。
为精确定义前述的概念，需要建立概率模型。定义空间X×C为所有点对（x,j）的集合，其中x∈X，j是类标签，j∈C。让P(A,j)
为X×C上A
X、j∈C(注意Borel度量等被忽略)的概率。P(A,j)的解释是：从相关的人群随机抽取的一个数据具有概率P(A,j)，它的度量向量x在A中，它的类别为j。假设训练样本L包含N个数据（x1,y1）,
(x2,y2) ,…, (xn, yn) 独立地按分布P(A,j)
随机取出。用L构造d(x)，然后定义R*（d）为d在用与L同样分布取出的新样本上错误分类的概率。
定义1.6
（x，Y）为按概率分布P(A,j)
得到的新样本，其中x∈X，Y∈C，也就是
（i.）
P(x∈A, Y = j) =
P(A, j)；
（ii.）
（x，Y）独立于L。
定义
R*（d）=p(d(x)≠Y)。
为估计概率p(d(x)≠Y)，设集合L不变，更精确地标记为p(d(x)≠Y|L)，即对于训练样本集L，新样本被错误分类的概率。
这个模型必须小心应用。臭氧数据的连续的日期对不是独立的。模型的有效性在于它给“事实”的定义以一个初始的概念框架。
怎样来估计R*（d）呢？在本专著的模拟数据案例中这并不困难。L中的数据是从由伪随机数生成器产生的期望的分布数据中独立抽样出来的。构造d(x)后，另有5000个数据按相同的分布独立于L抽取出来，用d分类。这5000个数据被错误分类的比例就是R*（d）的估计值。
在实际问题中，只有L中的数据是可得的，几乎不可能得到另外的大量的已分类样本。所以L既要被用于构造d(x)，也要用于估计R*（d）。我们称这样的估计为内部估计。Toussaint(1974)中有此类估计的总结和大量文献。
分类器d构造好以后，用L中的数据运行这个分类器，被错误分类的数据的比例为取代估计。这可以记为公式形式如下：
定义1.7
定义如果括号内的表达式为真，指示函数X（·）为1，否则为0。
取代估计记为R(d)，为
。
取代估计的问题在于它是用构造d的数据，而不是独立的样本来计算的。所有的分类过程，不论是直接的还是间接的，都试图减小R(d)。用一系列的R(d)作为R*(d)的估计是对d的准确性太乐观了。
作为一个夸张的例子，用分片A1，…，Aj定义d(x)，Aj包含L中所有的度量向量x，jn=j，不等于xn的x∈X被随机归入Aj或其他分片，那么R(d)=0，但难以确信R*(d)在0附近。
第二种方法是测试样本估计。L中的样本划分为L1和L2，L1中的样本中用以构造d，L2的样本用以估计R*(d)。N2为L2的样本个数，则测试样本估计Rts(d)为
。
在这种方法中，仍然需要小心，使L2的样本与L1中的样本独立，且按同一分布取出。用以保证上述特性最常用的方法是从L中随机抽取L2。通常L2取L中1/3的数据，但是并不知道这种1/3、2/3划分的任何理论合理性。
测试样本方法的缺点是它减小了有效样本的尺寸。在1/3、2/3划分中，仅有2/3数据用以构建d，仅有1/3的数据用以估计R*(d)。如果样本尺寸足够大，如在大数据量的光谱问题中，这没什么困难，测试样本估计可靠且有效。
对于小样本空间，可以用另一种称为V-折叠交叉验证的方法较好（见M.
Stone在1977年的综述）。L中的样本随机分入V个子集中，这些子集的尺寸尽可能相等，记这些子集为L1，L2，…，LV。假设构造分类器的过程能够应用于任何训练样本。对每个v，v=1,…,V，应用此过程于训练样本集L-
LV，也就是在L中但不在LV中的数据上，d(v)(x)为分类器的结果。由于LV中的数据没有用于构造d(v)，R*(d)
的测试样本估计为
（1.10）
其中NV
=N/V为LV中的数据个数。然后将同样的过程应用于全集L上构造分类器d。
如果V较大，这些分类器（V个）由N（1-1/V）个训练样本构造，与L几乎同样大。交叉验证的基本假设是这个过程是“稳定”的，也就是说，对分类器d(v)，v=1,…,V，每个都用L的几乎全部的数据构造，错误分类率R*(
d(v) )几乎等于R*(d)。由这种启发式方法，定义V-折叠交叉验证估计R(cv)(d)为
(1.11)
N-折叠交叉验证是“排除一个”估计。对每个n，n=1,…,N，第n个数据被排除，分类器由其余N-1个数据构造，第n个数据用作单情形测试样本，R*(d)用式(1.11)估计。
交叉验证对数据很节省，每个数据都用来构造d，每个数据有一次用作测试样本。在树型结构分类器中，用到10-折叠交叉验证，生成的估计器在模拟数据上与R*(d)很接近，达到满意程度。
靴带式方法也能用于估计R*(d)，但用在树型结构分类器上效果不好（见11.7节）。
1.5 贝页斯规则与当前的分类过程
用于构造分类器的主要思想是Bayes法则的概念。如果数据按概率分布P(A,j)取出，那么最精确的规则形式可用P(A,j)的形式给出，这个规则就称为Bayes法则，记为dB(x)。
为更精确起见，假设（x,Y），其中x∈X,
Y ∈C，是X×C上按概率分布P(A,j)随机取出的样本，也就是说，P(x∈A,
Y = j) = P(A,j)。
定义1.12
dB(x)为Bayes法则，如果对任何其他分类器d(x)，
那么Bayes错误分类率为
为举例说明dB(x)是怎样从P(A,j)导出的，我们在一个重要的案例中给出它的形式。
定义1.13
定义优先类概率π(j)，j=1,…,J， 有π(j)=P（Y=
j），第j个类度量向量的概率分布为
假设1.14
X为M维欧几里德空间，对任意j,
j=1,…,J，P(A|j)
有概率密度fj(x)；也就是对集合A
X，
那么有
定理1.15
在假设1.14下，Bayes法则定义为
on
(1.16)
Bayes错误分类率为
(1.17)
dB虽然称为Bayes法则，它也被看作最大似然法则：将x分类为j使
最大。不太重要的一点是：式(1.16)并不唯一地在点x上定义dB(x)，所以
从两个或多个不同j得到。在这种情形下，灵活定义dB(x)为
的最大值。
定理1.15的证明很简单。对任意分类器d，在假设1.14下，
对x的定值，
，
当d(x)等于j时取等号，那时
取最大值。因此，式(1.16)给出的法则dB想对于其他分类器d具有特性：
。
这表示dB是Bayes法则，估计(1.17)是
Bayes错误分类率的正确公式。
在我们后面用到的模拟样本中，数据用已知的概率分布产生。对这些样本导出dB，计算其值。由于RB是可得的最小错误分类率，知道RB并将其与树型结构分类器的准确率比较，得出它们的效果。
实际中，π(j)
与fj(x)
都不知道。π(j)
可用L中类j数据的比例来估计或由与问题相关的其他知识提供。比较难的是关于fj(x)的问题。三个最常见的分类过程是：
判别式分析；
核心密度估计；
K近邻方法。
在不同的方法中，都试图逼近Bayes法则，用训练样本L得到fj(x)的估计。
判别式分析方法假设所有的fj(x)
都是普通协方差矩阵Γ，不同的方法向量{uj}的多元正态密度。用通常的方法估计Γ和uj，以此来估计fj(x)。这些用以替代Bayes最优法则，给以分类分片
。
步进方法版本的线性判别式分析方法是使用最广泛的方法，通常应用时不必考虑缺少常态。它并不是为处理分类变量而设计，而是用将分类变量编码为哑元的技巧来处理。看到运行在不同数据集上的程序的结果，我们的反应是惊讶，它完成的如此完美。它提供了通过使用区别对待的坐标洞察数据结构的方法（深入讨论见Gnanadesikan，1977）。然而，J类问题（取决于J线性组合的最大值）的分类器形式难以进行解释。
密度估计和K近邻方法是较新的方法，由观察包含类的部分而不是全部数据集而产生，这些类以普通协方差矩阵的正态分布。
对每个密度fj(x)，密度方法使用一个无参估计，最通用的方法是使用估计的核心类型（见Hand，1982）。简要地说，定义X上的矩阵||x||
和核心函数K（||x||）≥0，在||x||=0时K（||x||）≥0取最大值，在||x||增大时趋向0，有
这样fj(x)由下式估计：
其中Nj为第j个类中数据的个数，所求和超过相应于第j个类中数据的度量向量xn。
K近邻方法由Fix和Hodges(1951)提出，具有简单的形式：定义X上的矩阵||x||和一个固定的整数k＞0。对任意点x，寻找x在L中的k个最近邻居，将x归为类j如果k在类j中的k最近邻居数大于在其它类中的k最近邻居数。（这相当于基于在k最近邻居中属于类j的点数，对fj使用密度估计。）
核心密度估计和K近邻方法对潜在的分布形式做了最小假设，但是这两种方法有如下严格的限制：
1. 它们都有对矩阵||x||的选择敏感，而且通常在本质上没有更好的定义。
2. 没有一种自然的或简单的方法来控制类别变量和丢失值。
3. 作为分类器，它们的计算很昂贵；必须存储L，对每一个新的点x，点间距离和d(x)都得重新计算。
4. 最重要的是，它们对数据的结构没有给出什么有用的信息。
关于这些方法及其它方法的综述在Kanal(1974)和Hand(1981)中。
分类树的使用并非是为了抽象的练习，而是由于上面讨论的任何一种方法都不能用简单、自然的方法解决分类问题。我们将以其中一个问题的描述开始下一章。
第2章
分类树导论
船只分类工程（Hooper
与
Lucero，1976）包括雷达范围内的六个船只类。六只船的结构不同，在船只的周围区域里，有一架飞机在收集数据。空中雷达的电子系统给出了雷达反馈的密度，它是一个距离的函数，物体以2英尺间隔反射雷达波到飞机。
在每个时间间隔里，飞机都获取船只的航空剖面，包括：从船只的不同部分反射的雷达波与它们与飞机的距离。
从海洋反射回来的雷达波密度相当小。当航空剖面平滑时，检测到船只反射波的起始与结束并不困难。为了让数据正常，平滑后的航空剖面的一端对应于x=0，另一端对应于x=1。结果，雷达航空剖面是一组0<x<1
的连续波，在终点变为0，否则为正。（见图2.1）
密度
0
x
图2.1
典型的航空剖面
每个航空剖面的顶点对应于船只上反射雷达波的主要结构元件。
不幸的是，航空剖面的形状随着角度而改变，角度是船只中线与飞机的夹角（见图2.2）
q
图2.2
在较宽的角度上，离飞机最近与最远的点可是只有几十英尺。航空剖面包含了非常少的信息，也许只有一个峰值顶点。在0度与180度的时候，航空剖面的信息最完全。
每一只不同的船的数据都包括了大量的航空剖面，它们的分布大概是罗盘的20度左右。现在我们的目标是构造一个分类，它把六个类中的任意一个在未知角度的航空剖面作为输入，输出可信的预测分类。
初始观测之后，注意到，当航空剖面随着角度改变时，峰值的位置相对稳定。也就是说，对给定的某类船只的航空剖面，只要峰值不消失，它的x坐标不变（如果弓角与锐角可以近似地给出）
树型结构分类，或者，更准确的说，二叉树结构分类，从x本身开始，反复对x分裂，成为两个子集，然后再对子集进行分裂。对于假设的六个类的树进行这个过程处理，如图2.3所示。
在图2.3中，x2与x3是分开的，x=x2∪x3。同样的，x=x4∪x5，x6∪x7=x3。x6,x8,x10,x11,x12,x14,x15,x16这些子集是没有被分裂的，它们称为终结子集。在此以后的图表里，将用矩形来表示终结子集；非终结子集则用圆圈来表示。
终结子集形成了x的一个分区。为每个终结子集分配一个类标签。可能有两个或两个以上的子集分配到同一个类标签。通过合并同类的子集就可以得到分区，每个分区对应于一个类。这样，就有：
A1=X15
A2=X11∪X14
A3=X10∪X16
A4=X6∪X17
A5=X8
A6=X12
我们根据坐标x=(x1,x2,…)的情况来决定分裂条件。例如，分裂1将x分裂为x2与x3，它的形式可以写为：
x2={x;x4≤7},
x3={x;x4＞7}
分裂3将x3分裂为x6与x7，形式可以写为：
x6={x∈x3；x3+x5≤-2}
x7={x∈x3；x3+x5＞-2}
这样，树型分类预测了向量x的类别：定义好了第一次分裂的条件，就决定了x是属于x2还是x3。例如，如果使用了(2.1)，如果x4≤7，则x属于x2；如果x4＞7，则x属于x3。而如果x属于x3，则可以根据分裂三的定义决定x是属于x6还是x7。
当x最终分配到一个终结子集时，x的预测类就是终结子集相关的类标签。
从现在开始，我们的术语改用树理论里面的术语。从现在开始，结点t=x的一个子集，根结点t1=x。最终子集就是最终结点，非最终子集就是非终结结点。图2.4重新为图2.3分配了类标签。
然后，整个树的构造包括了三个因素：
1．
选择分裂；
2．
决定是否继续分裂结点
；
3．
为每个终结结点分配一个类。
图2.4
问题的关键在于如何使用数据L决定分裂、终结结点和它们的分类。分类问题是简单的，主要要做的事情是寻找好的分裂与合适停止分裂。
2.3 树分类的构造
构造树的第一个问题是如何使用数据L决定把x分裂为越来越小的集合。基本的想法是，选择一个子集的每个分裂，这些分裂使得下面的子集比父结点的数据更“纯”。
例如，在六类船只问题中，p1，…，p6表示了类1，…，6在某个结点的比例。对根结点t1来说，(p1，…，p6)=(1/6，…，1/6)。T1的一个好的分裂将t1分裂为两个结点：左边的结点为类别1，2，3；类别4，5，6的剖面分配到右子结点（如图2.5）
一旦寻找到t1的一个好的分裂，接着就为两个子结点t2，t3寻找好的分裂。
为结点寻找分裂，使得子结点更“纯”，这个过程的思想是这样的：
1．
定义：结点概率p（j|t）,j=1,…,6，为对象xn属于类j的比例，
p(1|t)+…+p(6|t)=1
2．
定义：t的不纯度i(t)为p(1|t)，…，p(6|t)的非负函数，其中（1/6，…，1/6）为最大值，也就是说，当所有的类相等地混合在一起时，结点的不纯度是最大的，当结点只包含一个类时，它的不纯度是最小的。
对于任意一个结点t来说，假设有一个候选分裂，它把结点分裂为tL与tR，因此，t的一部分pL到了tL中，而另一部分pR到了tR中。（如图2.6）
图2.6
这样，分裂的好坏可以定义为不纯度的降低：
最后一步是：
3．
定义：每个结点二元分裂Ω的候选集S。一般来说，想象一下，分裂集S可以看作是一组问题产生的，其中的每个问题具有这样的形式
Is x∈A？，AÌX
然后，相关的分裂将t中所有回答“是”的xn分配到tL，而把回答“否”的xn分配到tR中。
在船只问题里，结点的不纯度定义为
对于这个具体的公式，没有令人信服的证明。仅仅是因为它是一个常用的函数，并且拥有第2步所要求的性质，所以选择了它。在以后的工作里，i(t)的其他定义可能会更好。
问题集Ω的形式定义为：
在区间[a,b]里有没有局部最大？其中a≤b，a、b从0到1，间隔为0.01。
这样，Ω的一个典型的问题是：在[0.31,0.53]区间有没有局部最大？由于简化的数据向量组成了局部最大的位置，因此稍微有点不同，问题变为：在区间[0.31,0.53]有没有相等的？
这样的问题一共有100*101/2=5000个。所以S的大小与候选分裂差不多。
树的建造是这样的：对根结点t1，搜索所有的5000个候选分裂寻找出使不纯度减少最多的分裂；例如：
然后使用分裂，将t1分裂为t2和t3，同样的，分别为t2和t3选择最佳分裂。
我们设计了启发式规则来终结树的增长。当结点t的不纯度不可能有显著的降低时，t不再分裂，成为终结结点。
用纯度规则来决定终结结点的类特征。具体的，如果
，则t为类j0的终结结点。
树的分类结果是显而易见的。如果属于未知类的剖面被输入树中，最后分配在类j的终结结点里，则它的分类为j。
我们认为，给定数据限制，以上的过程可被认为是问题的比较成功的解决方案。实际树的开始几个结点如图2.7所示。
图2.7
在讨论后面的开发方法之前，我们首先使用于构造分类树的初始化方法更形式化。
在一个J类的问题中，学习样本为L，Nj是类j里的对象数。通常，预定义的概率为比例{Nj/N}。但是学习样本中的比例并没有反映将来样本的比例。在大规模的光谱问题里，数据集只有十分之一包含了氯。但是由于并不知道分类的哪些对象是包含氯的，预概率使用了[1/2,1/2]。
在任何一种情况下，概率集{π（j）}既可以从数据中估计出{
Nj/N }，也可以由分析者给定。
对于结点t，设N(t)为L里所有xn∈t的总数量，Nj(t)为t中属于类j的对象数量。类j的对象数占L中t中对象数的比例为Nj(t)/
Nj。如果给定一组预定义的概率，则Nj(t)/
Nj为类j的对象加入树的概率。因此，我们把
作为对象属于类j并且在结点t中的概率的重替换概率。
任何一个对象分配到结点t的重替换概率p(t)定义为：
给定对象分配到结点t，则它属于类j的重替换概率为：
，满足：
当
时，
，则
是结点t中类别为j的对象的相对概率。
注意，在整本书中，小写的p代表估计概率，而大写的P代表理论概率。
树增长的初始化过程包括四个要素：
1．
二元问题集Ω，形式为{Is
x∈A?},A
ÌX
2．
分裂好坏的标准Φ(δ,t)，它可以评估出任何一个结点t的任何一个分裂
3．
分裂停止规则
4．
把每个终结结点分配到一个类的规则
二元问题集为每个结点t生成了分裂集。T中回答“是”的对象分配到左子结点tL，回答“否”的对象分配到右子结点tR。事实上，如果问题是{Is
x∈A？}，则tL=t∩A，并且
，AC是A在X的补集。对于每个中间结点t，选择使函数值Φ(δ,t)
最大的分裂。
2.4 初始树成长方法
2.4.1 问题标准集
如果数据结构标准化，问题的类也可以标准化。假设度量向量的形式为x={x1,…,xM},M是给定的维，变量x1,…,xM是序数类和分类属性的混合。标准问题集Ω按如下定义：
1．
每个分裂依赖于单个变量的值
2．
对每个序数变量xm，问题集Ω包含了下面形式的问题：{Is
xm ≤c?}
3．
如果xm是分类属性，比如,值在{b1,b2…,bL}中，则包括这些问题，它们的形式为{
Is xm ∈S?}}，S涵盖了所有的子集{b1,b2…,bL}。
对于所有的M个变量进行第2步与第3步的分裂，就组成了标准集。
设，M=4，x1，x2，x3是序数变量，x4∈{b1，b2，b3}，则包含了这些形式的问题：
Is x1
≤3.2?
Is x3
≤–6.8?
Is x4
∈{b1,b3}?等等
数据的不同分裂是有限的。例如，如果x1是序数变量，则L中的数据点包括至多x1的N个不同的值。由问题集产生的分裂至多有N个。它由问题{Is
x1≤cn?}给出，cn是x1的值中不连续的不同数据值。
对于一个分类属性的变量值xm，由于{xmÎS}和{xmÏS}产生的分裂是相同的，仅仅是tL与tR交换了一下，如果xm有L个不同的值，则在xm的值上可以定义2L-1-1个分裂。
对每个结点，树算法都要检查所有的变量，从x1到xm。对于每个变量它都寻找最佳的分裂。然后，比较m个单个变量的分裂，寻则最佳中的最佳。
计算机程序CART（Classification
and Regression Trees）(分类与回归树)完成了这个分裂的标准集。因为通常碰到的大部分问题都有标准化的数据结构，CART成为了一个容易改变和广泛使用的工具。
如果给定维数的数据只有序数变量，看待树结构过程的另一个方法是数据矩形空间的回归分区。
考虑一个两个类的树，它使用的数据由两个序数变量组成，x1，x2。假设数据表如图2.8所示。
图2.8
这棵树的另一种表现形式如图2.9所示，它被分为几个矩形单元。
图2.9
从地理学的观点来看，树过程将分区x回归到各个矩形，使得每个矩形里面的人口种族变得越来越类似。
2.4.2 分裂规则与分裂停止规则
分类标准的好坏可以从不纯度函数中得出。
定义2.5
不纯度函数：一个定义在所有的J－元组集的函数f，(p1,p2,…pj)，满足pj³0，j=1,…,J，åjpj＝1，它有性质：
Ⅰ）f在点（1/j,1/j,…,1/j）上有唯一的最大值;
Ⅱ）f只在点（1,0,…,0），（0,1,0,…,0）上有最小值
Ⅲ）f是p1,p2,…,pj
的对称函数
定义2.6
给定不纯度函数，定义结点t的不纯度度量i(t)为
如果结点t的分裂d将t中数据对象的pR分到tR中，pL分到tL中,定义不纯度的降低为：
分裂f（d，t）的好坏评价标准就是Di(d，t)。
假设我们做了一些分裂工作，得到了一些目前的最终结点。使用的分裂集和使用分裂集的顺序决定了二叉树T。用
表示目前的终结结点集，令I(t)=i(t)p(t)，则定义树T的不纯度为I（T），
很容易看出选择使Di(d，t)最大的分裂，就是使整个树的不纯度I(T)最小的分裂。选择任何一个结点t，使用一个分裂d，将结点分裂成tL与tR。新树T’的不纯度为
树的不纯度的减少为
它取决于结点t和分裂。因此，对t分裂后，要使树的不纯度减少量最大，就是要让下面的表达式最大：
（2.7）
定义：结点t的对象分配到tL和tR的比例分别为pL与pR，则
（2.7）可以写为
因为DI(d,t)与Di(d,t)的不同是源于p(t)的不同，所以同样的分裂d*使得两个表达式都最大。这样，选择分裂过程可以被看作使整棵树的不纯度最小的反复的过程。
初始的停止分裂条件使简单的（而且是不令人满意的）。设域值b>0，如果
，则称结点t是终结结点。
2.4.3 类分配规则与重替换估计
假设树T已经构造出来，终结结点集为
。
定义2.9
类分配规则把一个类j分配到每一个终结结点t，jÎ{1，…，j}，
t的结点tÎ
，用j(t)来表示。
在船只分类的例子里，分配类使用了规则——j(t)等于使p(j|t)最大的类。如果用{Nj/N}来表示预概率{p(J)}，则，只有纯度规则——把t分到Nj(t)最大的类。
对任何预概率集合与分类规则j(t)，
给定一个对象分配到结点t，错误分类概率的重替换估计为
。设类分配规则j*(t)使估计最小。
定义2.10
类分配规则j*(t)由下列方法给出：如果
，则j*(t)＝j。如果对两个或两个以上的不同的类，j*(t)为任意一个最大化的类。
使用上面的规则，我们有：
定义2.11
一个对象分配到结点t，错误分类的重替换概率
，设
，则分类树T的全局错误分类率的重替换估计R*(T)为
到现在为止，我们已经对类别为j的对象分类为i的花费与损失作出了严格的假设。在一些分类问题里面，这个设置并不很现实。因此，我们引进一组错误分类花费C(i|j)
定义2.12
C(I|j)使把类对象错误分类为I的花费，它满足：
Ⅰ）
Ⅱ）
给定结点t，它的估计结点概率为p(j|t)，
j=1,…,J，如果一个随机选择的未知类分配到结点t，并被分类为类i，则估计的期望错误分类花费为
：
一个自然的结点分配规则是这样的，选择i使表达式最小化。因此
定义2.13
如果i0使
最小，令j*(t)=i0，定义错误分类花费的重替换估计为
，树T的错误花费重替换估计为
，R(t)=r(t)p(t)。
我们注意到，在单元错误花费对象上，C(I|j)=1，i¹j，
最小花费规则减少到定义2.13给定的规则。
自此以后，我们把j*(t)作为类分配规则，不做进一步的考虑。
R（T）的一个重要性质：它分裂得越多，R(T)越小。更精确地来说，如果通过分裂一个终结结点T,得到T’，则
换一种说法：
命题2.14
对一个结点t的任何分裂，tL，tR，有
。
证明是简单的，整个过程见第4章（命题4.2）
2.5 方法论的开发
尽管我们列举了树型结构分类的种种优点，很明显地，在船只分类工程中使用的树增长方法有严重的缺陷。
以后的三章，9－12，提出了如何对付缺陷的方法，以及如何使树型分类更易变化、更精确，同时，他们也是建立在更深厚的理论基础上的。
2.5.1生成适当大小的树：一个主要问题
最大的困难是，分类树经常给出错误的结果。例如，假设使用停止规则(2.)，域值设得太低，使得每个终结结点都只有一个数据点。这时，p(j|t)都为0或1。R(t)为0，错误分类率得重替换估计R(T)为0。一般来说，R(T)随着终结结点的数量增多而减小。分裂的次数越多，你可能会觉得自己做得越好。
如果在初始建立的树上运行样本检测，很少可以成立。重替换估计R(T)不现实的低，树比数据本身所要求的信息要大。这是树增长过程的自然结果，在树的增长过程中，连续的使学习集里的类边界最优化。
使用更复杂的停止规则并没有用。分裂取决于域值，要么在一些终结结点停止得太早，要么在树的其它一些部分走的太远。一个满意的解决方法是，改变我们的基本注意力集中对象。我们并不试图在适当的终结结点集停止分裂，而是继续分裂直到所有的终结结点都很小，也就是说，会生成一棵很大的树。对这棵树进行向上选择性剪枝，这样，就可以产生一系列的递减的子树。然后使用交叉验证或样本估计测试，选择出具有最小估计错误率的子树。
这个过程在方法学上是中心过程，我们将在接下来的一章中详细介绍。
2.5.2 分裂规则
为了选择每个结点上的最佳分裂，可能会定义许多不同的标准。正如我们已经指出的，在船只分类工程里，选择的分裂是哪些使结点不纯度减少最多的分裂，结点不纯度被定义为：
第4章讨论了不同的分裂规则和他们的性质。变量错误分裂花费和预定义分布{p(j)}被放入分裂结构中。拿出了两个分裂规则以供使用。例如，一个规则使用了密度的Gini
索引作为结点不纯度的度量：
另一个使twoing
规则：对一个结点t，分裂t为tL与tR，选择使
最大的分裂d，这个规则与结点不纯度度量无关。
然而，我们所得到的实验性结论是：在大范围的分裂标准里，最终选择的树的性质对选择的分裂规则极度不敏感。用于剪枝或向上重新组合的标准则重要的多。
2.5.3变量组合
在树中使用标准结构的另一个缺陷是：所有的分裂都是基于单变量的。换一种说法，所有的分裂都是垂直于坐标轴的。当类结构依赖于变量组合时，标准树程序在发现结构上将做得很差。例如，考虑2.10所示的两个类、两个变量的数据。
图2.10将
在这个数据集里，分开的分析会更好。为了用矩形来近似地表达超平面，标准树的程序会分裂许多次。从树的输出里看出数据的线性结构很难。
如果怀疑问题里含有线性数据结构，分裂集被扩展成包含了所有的线性组合分裂，形式为：Is
？
我们开发了一个算法，搜索这些分裂，试图找出使得分裂标准最佳的一个。
完成线性组合分裂后，对于如图2.10所示的问题，分类树的结果将与线性区别分析的结果相当或者更好。
对于另一种类型的分类问题，变量可能以某些布尔组合出现。例如，在医疗诊断上，诊断问题经常是这样的形式：病人有（症状A和症状B）或症状C吗？
如果怀疑问题里包含布尔组合结构，并且度量空间是高维的，则扩展分裂集，使之包括布尔组合分裂是有用的。但是，由于这样的分裂数可以随着布尔表达式允许的长度迅速地增长，我们设计了逐步过程，使得搜索的计算复杂度可以接受。
这两种变量组合方法都将在第5章提出。
2.5.4 丢失值
可以从两个方面来考虑丢失值问题。首先，L的一些对象有一些丢失度量值（我们假设类标签总是存在的）；其次，我们要完成的树为一些有丢失值的向量预测类标签。
我们将在第5章讨论丢失值算法，它使用了surrogate
分裂，并且处理了这两个问题。思想是这样的：定义一个结点t的两个分裂的相似度度量。如果t的最佳分裂是在变量xm上的分裂d，寻找在其它变量上、但与xm最相似的分裂d’。则把分裂称为分裂的最佳替代。相同地，定义第二最佳替代、第三最佳替代、依次类推。
如果对象在度量上，xm值丢失，则由最佳替代决定它应该分配到tL或tR。如果最佳替代包含的变量也丢失，则使用第二最佳替代，以此类推。
2.5.5 树解释
树型结构分类的还有一个困难是，最终分类树的简单结构可能是欺骗性的，会误导解释。例如，如果一个变量从未被分裂，一个可能的解释是，变量与类成员关系很小。但事实可能是由于它的作用被其它变量覆盖。
树型结构可能是不稳定的。如果一个变量恰好遮盖了另一个变量，则预定义或学习样本的微小变化可能将分裂从一个变量转移到另一个变量。一个结点的两个分裂可能是不相似的，但大多数情况下，分裂质量相同。小小的变化有的时候选择这个，有时候又选择另外一个。
在第5章里提出了不同的过程，以帮助进行树的解释。特别地，给出了一个方法，它按分类的潜在影响对变量进行排序。即使一个变量可能不会出现在最终的树里，它的级别也可能很高，给出被掩盖的信号。
经常地，分析家可能要得出一组参数与（或）添加、删除变量的影响。因为会生成许多树并用于比较，全面交叉验证的精确性并没有什么必要，建议使用交替快速方法生成解释树。
2.5.6结点内的错误分类率估计
我们在第4章可以看到，交叉验证给出了R*(T)的相当充分的估计。然而，交叉验证过程并不为结点内部错误分类率r*(t)给出估计。重替换估计r(t)一般是最优化的，尤其是对更小的终结结点来说。
因为，一般来说，
r*(t)的估计是分类的副产品，因此要努力提高估计。第5章给出了一个ad
hoc 的估计方法，它使用启发式验证。它的主要验证是在已经检查过的所有问题上进行的。它在终结结点的平均错误率是r(t)的一半还不到。
2.5.7计算复杂度
在大型数据集上，使用十倍交叉验证建造树时间复杂度是很高的。第5章给出了一个结点子集采样方法来提高效率。
如果结点t的样本大小大于给定的最大限度，则使用t代表的每个类的子样本来决定最佳分裂。但是，仍然对t的整个数据集进行分裂。这样，子采样在不减小样本地情况下，大大地降低了计算时间。
2.5.8 其他问题
在树过程里还有其它一些问题。简而言之，“结束剪枝”与分裂试图把一个结点分为一大一小的两个子集，在其它条件相同的情况下，更趋向于“中间分裂”。这个我们将在11.8中讨论。同样的，变量选择倾向于有更多值并提供更多分裂的变量。
最后，另一个被频繁提到的问题是，树过程是单步优化，不是全局优化。也就是说，假设树增长过程提供了11个矩形终结结点。如果搜索x分配到任何一个矩形的所有可能，寻找使得结点不纯度最小的，两个结果可能截然不同。
这个问题与线性回归问题是相似的，那是关于逐步法与“最佳子集”法相比较的问题。我们没有提出这个问题。在计算机技术的这个阶段，一个全局最优树增长过程并不是对所有可能尺寸的数据集都适应。“可靠”比“最优”更关键。建立一个好的分类树，使之可以运行未被测试的样本对我们目前来说更加实用。
2.6 两个运行例子
为了说明方法的不同部分，我们建造了两个模型来生成数据。第一个是数字识别模型，结构简单，便于分析。它是通过一个更复杂的波形辨别模型来完成的。
2.6.1数字识别问题
数字一般是用于在电子公告牌和计算器上显示的，使用七个垂直与水平的灯，进行开关组合。（见图2.11）
图2.11
对图2.11的灯进行编号。设I表示第I个数字,I=1，2，…，9，0，(xi1，…，xi7)作为一个七维向量，如果I的第m个灯是亮的，则xim=1，否则xim=0。表2.1给出了xim的值。设C={1，…，10}，X是所有可能的7元组{x1,…,x7}。
图2.12
表2.1
例子的数据是从一个错误的计算器里得出的。7个灯中的每一个都有0.1的可能出错。更精确的来说，数据包括了随机向量(x1,…,x7,Y)，其中Y是类标签，假设值1,…,10有同样的概率，x1,…,x7是0-1变量。给定Y的值，x1,…,x7互相独立，等于表2.1中对应于Y的值，如果错误，则概率为0.1。
例如，p（x1,…,x7）=(1,1,0,1,0,1,1|y=5)=(0.9)7
且p（x1,…,x7）=(1,1,0,1,0,1,1),y=5)=(0.9)7
从分布里抽出了200个样本作为训练集。也就是说，L的每个对象都有这样的形式：（x1,…,x7,j），j是一个类标签，度量向量x1,…,x7是二元变量，表2.2给出了L里的数据。
为了使用树结构分类，有必要对L进行指定：
第一：问题集W（在这个例子里，由7个问题组成，Is
xm=m=1,…,7？）
第二：选择最佳分裂的规则（在2.5.2节中提到的两个标准可以被使用）
第三：选择适当大小的树的规则（使用了第3章提到的交叉验证方法）
最后得到的树如图2.13所示。10个终结结点，每个终结结点都对应了一个类，这是偶然的。一般来说，分类树可能有任意数量的终结结点，每个对应一个类，有时候，一些类没有对应的终结结点。
每个中间结点对应了导致分裂的一个问题。如果是“yes”则分类至左边，否则就是右边。
比较一下表2.1的树，会很有趣。例如，终结结点8对应于类1，由一个度量向量组成，x5=0，x4=0,x1=0。如果计算器没有出错时，这三个条件可以确定数字1。同样的，结点9对应于数字7，它的度量向量为x5=1,x4=0,x1=1。如果计算器并没有出错，也可以确定数字7。
在这棵特定的树里，使用大小为5000，占30％的样本估计R*
(T)。重替换估计i为0.29。贝叶斯规则可能解决这个例子。贝叶斯的错误分类率为0.26。在这个例子里，不能明显地提高树分类。
数字识别问题的一个变量可以通过添加纯噪音变量来获得。用图2.14的大网格替换掉图2.12的小网格，图2.14有24个线性分区。设额外的17个灯开或关的概率为0.5，互相独立，并且与原来的7个灯保持独立。17个灯产生了17个变量，x8,…,x24，xm=0或1，对应第m个灯开或关。这些变量是纯粹的噪音，因为他们对数字识别的目的毫无用处。
图2.14
从数字识别问题地训练集里取出每个对象，就形成了这个问题的训练集，从纯噪音分布里对17个度量进行采样，把它们添加到已有的7个度量中。新的采样样本，200个对象，24个度量值。
使用这个训练集，我们生成了一棵分类树。这棵树与前面的树遇到的问题是一样的：分裂选择标准，剪枝，交叉验证方法。选择的树与图2.12的树相似。大小为5000的验证集估计R*(T)为0.30，交叉验证估计是0.31，重替换估计为0.29。
即使添加了17个噪音变量，选择出的树依然与原始的7变量数字识别树相似，这说明了树型结构分类在邻域和其它非参数方法的优势。它的一致结构是基于区分对分类有用的变量和无用的变量的。当然，要区分有用与无用变量，它们很少会像前面这个例子那样被清楚的定义出来，树型结构也不会全盘胜出。
2.6.2 波形辨别问题
由于数字辨别问题只包括了基本结构，我们构造了另一个更复杂的例子。它是一个基于波形图h1(t)，h2(t)，h3(t)的分类问题，波形图见图2.15
从带噪音的两个波形图进行整型数据的采样，组成了一个随机的凸型组合，也就是类。度量向量是21维的：x=(x1,…,x21)。为了类1的向量x，独立地生成一个统一的随机数u和21个随机数，正态分布于0与1之间。然后设
为了生成类2的向量，重复过程，设：
类3的向量的生成：
预概率为（1/3，1/3，1/3），生成300个度量向量，于是有约为100个类。每个类的前5个类的数据在图2.16里已被绘出。构造树使用的问题形式为{Is
xm£c?}，c为实数，m
1,…,21 。使用了Gini
分裂标准（见2.5.2节），通过剪枝与交叉验证选择出最后的树。
图2.17
表示了这棵树，11个终结结点。错误分类的重替换估计为0.14，交叉验证估计为0.29，5000大小的测试集R*(T)估计为0.28。图2.17的每个结点都是按类的。每个结点都代表着分裂的问题。
检查一下开始的几个分裂，以看出分裂机制是如何工作的。图2.18有层次地表明了波形hj(t)。第一个分裂是x6£2.0。第六等分处接近第一个波形的波峰。由于类1与类2都包含了第一个波形的随机比例，x6可能对这二者过高，除非比例很小或e6是大的正数。这在分裂中反映出来了，115个类3中的109个分到左边（是），大部分类1与类2分配到右边（否）。
然后，树机制试图通过分裂x11，使左边结点更纯。在第11个等分处，第三个波形达到波峰，所以x11的值可以用于区分识别类1。这个分裂将36个类对象分到左边结点，大部分类2与类3的结点被分到右边结点。
初始分裂产生的右边结点有着几乎相等的类1与类2对象（64，68）。机制试图在第三个波峰附近，通过分裂x10£2.6分开两个类。类1被希望是低于x10，而类2则是高于x10。结果是大部分类1的对象分到左边，而大部分类2的对象分到了右边，这证实了我们的思想。
每个终结结点右边的对象数是校正过的计数，这些计数按类来分，从在树上运行的大小为5000的测试样本向量得出。为了便于比较，我们对这些计数进行校正，以使结点内的总数等于训练集的总数。
图2.17
图2.18
比较一下不同终结结点的两张列表，可以看出，训练样本结点可能会偶尔给出一些误导的估计。这对小一点的结点来说，尤其如此。
在这个问题里面，可以从贝叶斯规则得出一个分析表达式。在一个大小为5000的测试样本上使用规则，错误率为0.14。
我们选择这个例子来说明树构造过程的特点。分类树错误率为贝叶斯错误率的大约两倍，这说明，单等分分裂不适合从这个特殊的数据集提取出有用的信息。5.2节给出了变量组合的用法。
2.7
树构造方法的优点
正如我们在前面几节所说的，树型分类是一个回归、反复的过程，只指定需要少数几个因素：
1.
问题集W
2.
在任意结点选择最佳分裂的规则
3.
选择树大小的标准
它也可用作一个有力的、具有适应力的分类工具。
1.
通过问题集的适当形式，可以运用于任何一个数据结构。在标准数据结构下，它既可以处理序数变量也可以处理分类变量，方式是简单直观的。
2.
最后得到的分类形式简单，可以压缩存储，并有效的对新数据进行分类。
例如，氯问题的分类算法由一组约40个问题组成。任何新的多光谱分类过程可以在几秒钟内完成。
3.
在处理非同类关系中，大大地利用条件信息。
一旦结点t分裂为tL和tR，便独立地为两个结点寻找最好的分裂。例如，在船只问题上，对那些在区间[0.13,0.29]有最大值的剖面，接下来的重要问题是在区间[0.24,0.53]是否有最大值，而对那些在区间[0.13,0.29]没有最大值的剖面，问题是不同的：包括在范围[0.54,0.76]的一个最大值。
4.
它做了自动的逐步变量选择和复杂度降低。
它是树增长结构的一个固有部分，对每个结点都作了一次搜索，以找出最重要的分裂。在这个意义上，它代表了逐步的过程而不是一个最佳子集法。每个阶段都试图从它工作的空间里抽取出最显著的信息。
5.
它不仅给出了分类，而且给出了错误分类概率的估计，并且不需要额外的工作。
例如，氯分类算法不仅输出了预测分类，而且还输出了包含未知元素的质谱的终结结点的值r(t)。如果r(t)的值为0.40，（在两个类的问题里，最大值为0.50），这说明了分类是高度不确定的，质谱分析训练所得的观点也是合意的。但是，r(t)值为0.03时，是相当可信的。（事实上，r(t)给出的不是重替换估计，而是使用独立测试集的估计。详见第7章）
6.
采用标准数据结构，在所有单调转换下，独立序数变量的是保持不变的。
例如，如果x1是标准问题的序数变量，做了变换x1’=x13，不管是使用x1还是x1’，最佳分裂应该都是一样的。如果x1的最佳分裂是x1£3，则使用x1’的最佳分裂是x1’£27，分到左边与右边的对象是相同的。
7.
考虑L里的孤立点与错误分类点，算法是健壮的。
在度量空间x里，树的健壮性类似中值。一个简单的数据对象在N个数据对象里，权重为1。评估任何分裂时，必须考虑每个类的多少对象分到左边与右边。
另一类频繁出现的错误是：对训练集里的少数几个对象标错了标签。这对线性辨别式可能带来灾难性的影响，如图2.19所示：
只有当它不被少数错误标签的点所影响时，树型结构方法再次为每个点加权重。
8.
由于预测数据结构，树型过程的输出是易于理解和易于解释的信息。
树型结构方法已经使用在各种应用上，使用人员包括：非统计方向化学家、医生、气象学家、物理学家等等。他们普遍反映，分类树提出了理解问题结构的启发的、自然的方法。
