現(xiàn)實(shí)中常遇到多分類學(xué)習(xí)任務(wù)。有些二分類學(xué)習(xí)方法可直接推廣到多分類，如LR。但在更多情形下，我們是基于一些基本策略，利用二分類學(xué)習(xí)器來解決多分類問題。所以多分類問題的根本方法依然是二分類問題。

具體來說，有以下三種策略：

一、一對一 （OvO)

假如某個(gè)分類中有N個(gè)類別，我們將這N個(gè)類別進(jìn)行兩兩配對（兩兩配對后轉(zhuǎn)化為二分類問題）。那么我們可以得到個(gè)二分類器。（簡單解釋一下，相當(dāng)于在N個(gè)類別里面抽2個(gè)）

之后，在測試階段，我們把新樣本交給這個(gè)二分類器。于是我們可以得到個(gè)分類結(jié)果。把預(yù)測的最多的類別作為預(yù)測的結(jié)果。

下面，我給一個(gè)具體的例子來理解一下。

上圖的意思其實(shí)很明顯，首先把類別兩兩組合（6種組合）。組合完之后，其中一個(gè)類別作為正類，另一個(gè)作為負(fù)類（這個(gè)正負(fù)只是相對而言，目的是轉(zhuǎn)化為二分類）。然后對每個(gè)二分類器進(jìn)行訓(xùn)練?？梢缘玫?個(gè)二分類器。然后把測試樣本在6個(gè)二分類器上面進(jìn)行預(yù)測。從結(jié)果上可以看到，類別1被預(yù)測的最多，故測試樣本屬于類別1。

二、一對其余 (OvR)

一對其余其實(shí)更加好理解，每次將一個(gè)類別作為正類，其余類別作為負(fù)類。此時(shí)共有（N個(gè)分類器）。在測試的時(shí)候若僅有一個(gè)分類器預(yù)測為正類，則對應(yīng)的類別標(biāo)記為最終的分類結(jié)果。例如下面這個(gè)例子。

大概解釋一下，就是有當(dāng)有4個(gè)類別的時(shí)候，每次把其中一個(gè)類別作為正類別，其余作為負(fù)類別，共有4種組合，對于這4種組合進(jìn)行分類器的訓(xùn)練，我們可以得到4個(gè)分類器。對于測試樣本，放進(jìn)4個(gè)分類器進(jìn)行預(yù)測，僅有一個(gè)分類器預(yù)測為正類，于是取這個(gè)分類器的結(jié)果作為預(yù)測結(jié)果，分類器2預(yù)測的結(jié)果是類別2，于是這個(gè)樣本便屬于類別2。

其實(shí)，有人會有疑問，那么預(yù)測為負(fù)類的分類器就不用管了嗎？是的，因?yàn)轭A(yù)測為負(fù)類的時(shí)候有多種可能，無法確定，只有預(yù)測為正類的時(shí)候才能唯一確定屬于哪一類。比如對于分類器3，分類結(jié)果是負(fù)類，但是負(fù)類有類別1，類別2，類別4三種，到底屬于哪一種？

OvO和OvR有何優(yōu)缺點(diǎn)？

容易看出，OvR只需訓(xùn)練N個(gè)分類器，而OvO需訓(xùn)練N(N - 1)/2個(gè)分類器， 因此，OvO的存儲開銷和測試時(shí)間開銷通常比OvR更大。但在訓(xùn)練時(shí)，OvR的每個(gè)分類器均使用全部訓(xùn)練樣例，而OvO的每個(gè)分類器僅用到兩個(gè)類的樣例，因此，在類別很多時(shí)，OvO的訓(xùn)練時(shí)間開銷通常比OvR更小。至于預(yù)測性能，則取決于具體的數(shù)據(jù)分布，在多數(shù)情形下兩者差不多。

綜上:
OvO的優(yōu)點(diǎn)是，在類別很多時(shí)，訓(xùn)練時(shí)間要比OvR少。缺點(diǎn)是，分類器個(gè)數(shù)多。
OvR的優(yōu)點(diǎn)是，分類器個(gè)數(shù)少，存儲開銷和測試時(shí)間比OvO少。缺點(diǎn)是，類別很多時(shí)，訓(xùn)練時(shí)間長。

三、多對多（MvM）

MvM是每次將若干個(gè)類作為正類，若干個(gè)其他類作為反類。顯然，OvO和OvR是MvM的特例。MvM的正、反類構(gòu)造必須有特殊的設(shè)計(jì)，不能隨意選取。這里我們介紹一種最常用的MvM技術(shù)"糾錯(cuò)輸出碼" (Error Correcting Output Codes，簡稱 ECOC)

ECOC是將編碼的思想引入類別拆分，并盡可能在解碼過程中具有容錯(cuò)性。

ECOC工作過程主要分為兩步:

編碼：對N個(gè)類別做M次劃分，每次劃分將一部分類別劃為正類，一部分劃為反類，從而形成一個(gè)二分類訓(xùn)練集。這樣一共產(chǎn)生M個(gè)訓(xùn)練集，可訓(xùn)練出M個(gè)分類器。

解碼：M 個(gè)分類器分別對測試樣本進(jìn)行預(yù)測，這些預(yù)測標(biāo)記組成一個(gè)編碼。將這個(gè)預(yù)測編碼與每個(gè)類別各自的編碼進(jìn)行比較，返回其中距離最小的類別作為最終預(yù)測結(jié)果。

類別劃分通過"編碼矩陣"指定。編碼矩陣有多種形式，常見的主要有二元碼和三元碼。前者將每個(gè)類別分別指定為正類和反類，后者在正、反類之外，還可指定"停用類"。圖3.5給出了一個(gè)示意圖，在圖 3.5(a) 中，分類器f2將Cl類和C3類的樣例作為正例，C2類和C4類的樣例作為反例；在圖3.5(b)中，分類器f4將C1類和C4類的樣例作為正例，C3 類的樣例作為反例。在解碼階段，各分類器的預(yù)測結(jié)果聯(lián)合起來形成了測試示例的編碼，該編碼與各類所對應(yīng)的編碼進(jìn)行比較，將距離最小的編碼所對應(yīng)的類別作為預(yù)測結(jié)果。

例如在圖 3.5(a) 中，若基于歐式距離，預(yù)測結(jié)果將是 C3。也就是一個(gè)測試樣本，經(jīng)過分類器f1,f2,f3,f4,f5分別預(yù)測成了(-1，-1，+1，-1，+1)，與C1相比較，海明距離為0+1+1+1+0=3，歐式距離為，對C2,C3,C4都進(jìn)行比較即可。

為什么稱為"糾錯(cuò)輸出碼"呢?

這是因?yàn)樵跍y試階段，ECOC編碼對分類器的錯(cuò)誤有一定的容忍和修正能力。例如圖3.5(a) 中對測試示例的正確預(yù)測編碼是(-1，+1，+1，-1，+1)，假設(shè)在預(yù)測時(shí)某個(gè)分類器出錯(cuò)了，例如 h 出錯(cuò)從而導(dǎo)致了錯(cuò)誤編碼(-1，-1，+1，-1，+1)，但基于這個(gè)編碼仍能產(chǎn)生正確的最終分類結(jié)果C3。一般來說，對同一個(gè)學(xué)習(xí)任務(wù)，ECOC編碼越長，糾錯(cuò)能力越強(qiáng)。

EOCO編碼長度越長，糾錯(cuò)能力越強(qiáng)，那長度越長越好嗎？

NO！編碼越長，意味著所需訓(xùn)練的分類器越多，計(jì)算、存儲開銷都會增大；另一方面，對有限類別數(shù)，可能的組合數(shù)目是有限的，碼長超過一定范圍后就失去了意義。

對同等長度的編碼，理論上來說，任意兩個(gè)類別之間的編碼距離越遠(yuǎn)，則糾錯(cuò)能力越強(qiáng)。因此，在碼長較小時(shí)可根據(jù)這個(gè)原則計(jì)算出理論最優(yōu)編碼。然而，碼長稍大一些就難以有效地確定最優(yōu)編碼，事實(shí)上這是 NP 難問題。不過，通常我們并不需獲得理論最優(yōu)編碼，因?yàn)榉亲顑?yōu)編碼在實(shí)踐中往往己能產(chǎn)生足夠好的分類器。另一方面，并不是編碼的理論性質(zhì)越好，分類性能就越好，因?yàn)?a href="http://www.makelele.cn/v/tag/557/" target="_blank">機(jī)器學(xué)習(xí)問題涉及很多因素，例如將多個(gè)類拆解為兩個(gè)“類別子集”，不同拆解方式所形成的兩個(gè)類別子集的區(qū)分難度往往不同，即其導(dǎo)致的二分類問題的難度不同。于是一個(gè)理論糾錯(cuò)性質(zhì)很好、但導(dǎo)致的二分類問題較難的編碼，與另一個(gè)理論糾錯(cuò)性質(zhì)差一些、但導(dǎo)致的二分類問題較簡單的編碼，最終產(chǎn)生的模型性能孰強(qiáng)孰弱很難說。

審核編輯：黃飛

?