纠错输出码 ECOC 是什么？用编码的思想把多分类拆成多个二分类

纠错输出码（Error-Correcting Output Codes，ECOC）是一种把多分类问题拆分成多个二分类问题来解决的方法，由 Thomas Dietterich 和 Ghulum Bakiri 在 1995 年提出。它借鉴了通信领域中纠错码的思想：即使其中一部分二分类器判断错了，整体上仍然有可能得出正确的类别。

为什么要拆分多分类问题

很多分类算法，比如支持向量机、逻辑回归的基本形式，天然只能处理二分类问题，也就是区分两个类别。当需要区分多个类别时，比如识别 0 到 9 十个数字，就需要把多分类问题拆分成多个二分类问题。最常见的拆分方式有两种：一对多，也叫一对其余，为每个类别训练一个分类器，判断样本“是不是这个类别”，十个类别就需要十个分类器；一对一，为每两个类别训练一个分类器，十个类别就需要四十五个分类器，最后通过投票决定。纠错输出码是一种更一般、更灵活的拆分框架，一对多和一对一都可以看作它的特殊情况。

它是怎么工作的

编码：为每个类别分配一个由若干位二进制数字组成的码字，所有类别的码字排列起来，构成一个编码矩阵。矩阵的每一行对应一个类别，每一列对应一个二分类器。在每一列中，码字为 1 的那些类别被当作正类，码字为 0 的那些类别被当作负类，用这样的划分训练一个二分类器。比如有四个类别、使用五位编码，就要训练五个二分类器，每个分类器都把四个类别以不同的方式分成两组。

解码：预测时，让这五个分类器分别对新样本做出判断，每个分类器输出 0 或 1，把这五个输出依次排列起来，就得到了这个样本的一个预测编码。然后把这个预测编码与每个类别的码字进行比较，计算它们之间的距离，通常是海明距离，也就是有多少位不相同，距离最小的那个类别就是最终的预测结果。

“纠错”体现在哪里

这种方法的妙处在于容错。在通信中，为了防止数据在传输过程中因为干扰而出错，人们会在数据中加入额外的冗余信息，即使少数几位出了错，接收方也能根据编码的规则发现并纠正错误。纠错输出码借鉴了同样的思想：如果各个类别的码字之间相互差别足够大，也就是码字之间的海明距离足够大，那么即使有一两个二分类器判断错了，预测编码仍然会离正确类别的码字最近，最终的结果依然正确。一般来说，码字越长，纠错的能力越强，但需要训练的分类器也越多；码字之间的距离越大，纠错的能力也越强。

设计编码的注意事项

好的编码需要满足几个条件：不同类别的码字之间距离要大，这决定了纠错的能力；不同的列之间也要有足够的差异，避免训练出几个做同样事情的分类器，因为如果它们犯的错误相同，冗余就失去了纠错的作用；同时，每一列的划分方式应该让对应的二分类问题不至于太难学。编码矩阵可以用随机的方法生成，也可以根据数据的特点进行优化设计。scikit-learn 等机器学习库中提供了纠错输出码的实现。