【已读分享】《CART》中文版 原文翻译 Chp2 介绍树分类器

第一章已在知乎分享，打开此链接查看《CART》Chp1 前言、背景及基本定义，个人翻译，仅供学习

2.1 船舶分类问题

船舶分类项目（Hooper和Lucero，1976，数据与文献均找不到线上资料）涉及通过雷达测距剖面 识别六种船舶。

数据是由一架飞机沿着六种不同结构类型的船，绕大圈飞行而收集的。

机载雷达中的电子器件给出了雷达回波强度作为距离(或距离)的函数，飞机到反射雷达脉冲的物体的间隔为2英尺。

在每一小段时间内，飞机就会对飞船做一个轮廓图，这个轮廓图是由雷达从飞船各个部分传回的强度和这些部分与飞机的距离组成的

从海洋返回的雷达强度很小。对轮廓进行平滑处理后，就不难发现船只返回起点和终点的范围。对数据进行归一化，以使平滑轮廓的一端对应于x = 0，另一端对应于x =1。然后，所得雷达距离轮廓为连续曲线，间隔为0≤x≤1，在端点处为零。否则为正（参见图2.1）。

图 2.1 经典的距离剖面图

每个剖面上的峰值对应着船上作为反射器的主要结构元素。

不幸的是，轮廓线的形状随着船和飞机中心线的夹角θ而改变，见图2.2

图2.2

在宽边角(θ = 90°，θ = 270°)，舰上离飞机最近和最远的点可能只相差几十英尺。剖面包含的信息非常少，可能只有一个峰。在船头和船尾(θ = 0°，θ = 180°)的剖面最详细。

这些数据包括了围绕罗盘以大约20度的角度拍摄的不同船级的许多剖面图。目标是构建一个分类器，它可以从六个类中的一个以未知角度输入一个概要文件，并产生可靠的类隶属度预测。

经过一些初步的检查，我们注意到，虽然轮廓线随着角度的变化而变化，但峰的位置保持相对不变。也就是说，在属于特定船类的剖面中，只要一个峰值没有消失，它的x坐标就保持不变(如果船头和船尾有适当的标记)。

这个项目最初的困难之一是减少维度。任何资料中的大部分信息都是多余的。与邻近x值对应的轮廓高度相关。考虑到对轮廓的初步观察，决定从每个轮廓中提取局部极大值位置的向量。因此，每个剖面都有一个向量的形式(x1, x2，…)，其中x1是第一个局部最大值的位置，等等。

这带来了新的困难。数据具有可变维度，从低的1到高的15。所有可用的分类方法似乎都不适合这种数据结构。

最令人满意的解决方案是下面几节中概述的树形结构方法。

2.2 树结构分类器

树型结构化分类器，或者更准确地说是二叉树型结构化分类器，是通过将X的子集重复拆分为从X本身开始的两个后代子集来构造的。

对于一个假设的六类树，这个过程如图2.3所示。

图2.3 以集合理论方式标记的树模型

在图2.3中，X2和X3是不相交的，有X = X2 U X3。同理，X4 与 X5 不相交 且 X4 U X5 = X2、 X6 ∪ X7 = X3。

没有被分割的子集，如X6、X8、X10、X11、X12、X14、X15、X16、X17，称为终端子集（ terminal subsets ），用矩形表示（后续亦是如此）。

非终结符子集（nonterminal subsets）用圆圈表示。

性质：

1.终端子集是 X 的一部分，每个终端子集由一个类标号（class label）指定。

2.可能有两个或多个终端子集具有相同的类标签。

分类器对应的划分是将同一个类对应的所有终端子集放在一起得到的。

所以：

A1 = X15

A3 = X10 ∪ X16

A5 = X8

A2 = X11 ∪ X14

A4 = X6 ∪ X17

A6 = X12.

3.划分（splits）是由 x = (x1, x2, ...)坐标上的条件 组成的

例如：把X划分成X2和X3的划分1（split 1） ，可以是这样的形式

X2 = {x ; x4 ≤ 7}，X3 = {x ; x4 ＞ 7} （2.1）

把X3划分为X6和X7的划分3（split 3） 可以是这样的形式

X6 = {x ∈ X3; x3 + x5 ≤ -2}

X7= {x ∈ X3; x3 + x5 > -2}

分类步骤：

树分类器预测测量向量x的类别的方式是这样的：

从第一次划分的定义，可以决定某个x是分到 X2还是 X3。例如，如果使用（2.1），若x4 ≤ 7，则分到X2，若x4 ＞ 7，则分到X3。然后从划分3的定义，可以决定 x 是分到X6还是X7。

The tree classifier predicts a class for the measurement vector x in this way: From the definition of the first split, it is determined whether x goes into X2 or X3. For example, if (2.1) is used, x goes into X2 if x4 ≤ 7, and into X3 if x4 > 7. If x goes into X3, then from the definition of split 3, it is determined whether x goes into X6 or X7.

当 x 最终移动到一个终端子集时，它的预测类由附加到该终端子集的类标签给出

When x finally moves into a terminal subset, its predicted class is given by the class label attached to that terminal subset.

在这一点上，我们把术语改为树形理论。

At this point we change terminology to that of tree theory. From now on,

从现在开始，一个节点t = X的子集

A node t = a subset of X and

根节点t1 = X 本身

The root node t1 = X.

终端子集成为终端节点，非终端子集成为非终端节点。图2.3重新标记，如图2.4所示。

Terminal subsets become terminal nodes, and nonterminal subsets are nonterminal nodes. Figure 2.3

becomes relabeled as shown in Figure 2.4.

图2.4 以树形理论方式标记的树模型

因此，树的整个构造过程围绕着三个元素展开:

1. 选择：划分条件

2. 判定：是声明为终端节点 还是继续拆分它

3. 分类：将每个终端节点分配给一个类

问题的关键是如何使用数据L来确定划分、终端节点和它们的类。

事实证明，类的分配问题很简单。关键在于找到合适的划分方式，以及知道何时停止划分。

2.3 树形分类器的构造过程

之后涉及到很多公式，不太好分享，等整理成pdf后再分享给大家。

部分翻译截图