用多位的“码”作为样本和类的标记，则可借助编码理论。编码用于训练、解码用于预测。

纠错输出码

用多位的“码”作为样本和类的标记，能看到一片新天地。 纠错输出码是借助二分类器处理多分类问题，这里从理解的角度对【西瓜书第3.5节】作些补充。

编码

编码用于训练。

对于多分类（如，有4个类：$C_1,C_2,C_3,C_4$），我们将“类别”归并成“大类”，则总可以变为两“大类”（即有某种未知的特征将各“类”归入“正类”和“反类”中），可以利用已充分讨论的二分类法实现该分类，
如图3.2所示。

即
{ { x + } = C 2 { x − } = C 1 ⋃ C 3 ⋃ C 4 \begin{align} \begin{cases} \{\boldsymbol{x}^+\}=C_2 \\ \{\boldsymbol{x}^-\}=C_1\bigcup C_3\bigcup C_4 \\ \end{cases} \tag{1} \end{align} {{x+}=C2​{x−}=C1​⋃C3​⋃C4​​​(1)​

将符号数字化，为保持对称性，用 { + 1 , − 1 } \{+1,-1\} {+1,−1}作为标记空间，则图3.2变为图3.3。

可以用上述方法从各种角度进行上述归并，如再添加另一种归并情况，得图3.4。

如此若干次（例如5次），则得到（转置一下）图3.5，即为【西瓜书图3.5(a)中间的矩形】。

图3.5横着看，如：$C_1=(-1,+1,-1,+1,+1)$即为$C_1$的二元编码，码长为5。 这样就完成了对$C_1,C_2,C_3,C_4$各类别的编码。 另外，若将$+1$换为$a$、$-1$换为$b$，则$C_1=babaa$，等等。

图3.5纵向看，每列是一个二分类，例如，第一列即表示式(1)，依此可将原训练集变为二分类训练集，则可训练了一个二分类模型实例$f_1$，对其余列也同样处理。 则可训练出一组模型实例（$f_1,f_2,f_3,f_4,f_5$）。

综上，编码步骤：

• 指定各类别 的编码（得横向）。
• 训练出一组二分类器（依纵向）。

解码

解码用于预测。

设$\mathbf{x}$是要预测的样本，将上述训练好了的二分类器组作用于它，如：$f_1(\mathbf{x})=-1,f_2(\mathbf{x})=-1,f_3(\mathbf{x})=+1,f_4(\mathbf{x})=-1,f_5(\mathbf{x})=+1,$即得到【西瓜书图3.5(a)中最后一行】$(-1,-1,+1,-1,+1)$，这就是样本$\mathbf{x}$的编码。

将该编码与上述各类别的编码进行比较，选取最“接近”的类别作为样本$\mathbf{x}$的类别。 比较中用到“距离”，常用的有：

（1）海明距离

比较样本与类的编码，两编码不一致的位的个数即为两编码的距离，如图3.6所示，$\mathbf{x}$与$C_1$的海明距离为$3$。 同样，计算样本$\mathbf{x}$与其他类的海明距离，得到【西瓜书图3.5(a)中右至左的第二列】。

（2）欧氏距离

将样本与类的编码相减（如图3.7），再应用欧氏距离计算公式。

$$\begin{array}{r}\sqrt{\sum (x_i-y_i{)}^2}=\sqrt{0^2+2^2+(-2{)}^2+2^2+0^2}=\sqrt{12}=2\sqrt{3}\end{array}$$
故$\mathbf{x}$与$C_1$的欧氏距离为$2\sqrt{3}$。

同样，计算样本$\mathbf{x}$与其他类的欧氏距离，得到【西瓜书图3.5(a)中右至左的第一列】。

综上，解码步骤：

• 利用训练好的二分类器组计算测试样本的编码。
• 比较该样本编码与类别编码的距离。
• 解码出该样本的类别（样本属于距离最近的类别）。

上述为二元ECOC码，若在编码过程中使用“停用类”（记为$0$类），则得到三元ECOC码，即【西瓜书图3.5(b)】。

另外，理论上有如下重要结论：

（1）设类的编码间的最小距离为$d$，则可以容许样本的编码$\lfloor \frac{d-1}{2}\rfloor$位（$\lfloor x\rfloor$表示不超过$x$的最大整数）出错。 这是因为，样本的编码在类的编码“之间”，故样本的编码与最近的类编码距离小于$\frac{d}{2}$（$d$为奇数时）或小于等于$\frac{d}{2}$（$d$为偶数时），即不论奇偶都有小于等于$\lfloor \frac{d-1}{2}\rfloor$，即：预测时，取距离样本的编码最近的类编码作为样本的正确编码（样本的类别）。

（2）设有$k$类，则可构造出类间等距离的长度为$2^{k-1}-1$的类编码。 方法：以$k$位所有二进制码作为表（【西瓜书图3.5(a)）的列，则有$2^k$列，去掉互补的，则删除了一半的列，余下$2^{k-1}$列，再去掉全是1（或全0）的一列，余下$2^{k-1}-1$列，这表的行即可作为类的编码，长度为$2^{k-1}-1$，根据对称性，任两个编码的距离相等且不超过$\lfloor \frac{2^{k-1}-1}{2}\rfloor =2^{k-2}$。

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权

上一篇：3.3 线性判别分析LDA（将平面上点投影到线上）
下一篇：4.1 决策树算法（不是规划论中的决策树）