如何利用二分類學(xué)習(xí)器來(lái)解決多分類問(wèn)題

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

具體來(lái)說(shuō)，有以下三種策略：

一、一對(duì)一 （OvO)

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

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

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

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

二、一對(duì)其余 (OvR)

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

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

其實(shí)，有人會(huì)有疑問(wèn)，那么預(yù)測(cè)為負(fù)類的分類器就不用管了嗎？是的，因?yàn)轭A(yù)測(cè)為負(fù)類的時(shí)候有多種可能，無(wú)法確定，只有預(yù)測(cè)為正類的時(shí)候才能唯一確定屬于哪一類。比如對(duì)于分類器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的存儲(chǔ)開銷和測(cè)試時(shí)間開銷通常比OvR更大。但在訓(xùn)練時(shí)，OvR的每個(gè)分類器均使用全部訓(xùn)練樣例，而OvO的每個(gè)分類器僅用到兩個(gè)類的樣例，因此，在類別很多時(shí)，OvO的訓(xùn)練時(shí)間開銷通常比OvR更小。至于預(yù)測(cè)性能，則取決于具體的數(shù)據(jù)分布，在多數(shù)情形下兩者差不多。

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

三、多對(duì)多（MvM）

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

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

ECOC工作過(guò)程主要分為兩步:

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

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

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

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

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

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

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

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

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