機器學習:如何在多類別分類問題上使用用二元分類器進行分類(Multiclass Strategy for Binary classifier)

在二元分類器最常遇到的問題就是要怎麼應用到多類別的分類問題上。通常二元分類器會用到的多類別分類策略會有兩種，分別為one-against-all (OAA) 和 one-against-one(OAO)，概念和做法都很簡單。

Note: 這篇文章OAA會假設二元分類器都是分+1和-1兩類 (跟SVM呼應)。

one-against-all(OAA)

有的時候這個方法也會被稱為one-against-rest、one-versus-all、one-versus-rest，中文翻譯「一對全部」或是「一對剩下」，從名稱來看非常直覺。

OAA運作方式是先拿其中一類當作+1類，剩下的類別當作-1類，然後用二元分類器學習一次得到一個分類器/decision hyperplane；然後第二次繼續拿下一類當作+1類，剩下的類別當作-1類，學習一個分類器/decision hyperplane；直到所以的類別都有當作+1類為止，最後看decision value哪個比較大，資料就判給哪一類。

假設有L類的分類問題，OAA總共就會訓練L個二元分類器。

文字看沒有感覺，用圖片來體驗感覺會比較好。
下圖為一個三分類的問題。

上圖我舉了三類分類的問題，有紅色(類別1)、綠色(類別2)，藍色(類別3)。OAA總共會訓練三個分類器，分別為

第1次，把紅色(類別1)視為+1類，綠色和藍色(類別2和3)視為-1類，然後訓練一個訓練二元分類器得到decision hyperplance (class1) 。

第2次，把綠色(類別2)視為+1類，紅色和藍色(類別1和3)視為-1類，然後訓練一個訓練二元分類器得到decision hyperplance (class2)。

第3次，把藍色(類別1)視為+1類，紅色和綠色(類別1和2)視為-1類，然後訓練一個訓練二元分類器得到decision hyperplance (class3)。

所以經由上述步驟，可以得到decision hyperplance (class1)、decision hyperplance (class2)和decision hyperplance (class3)。

所以當我們有新的樣本(x_new)要進來分類時，將這個樣本丟進去這三個hyperplance去算decision value，這個樣本就會判給有最大decision value那類。

DV1(x_new)=Decision hyperplance(class1, x_new)
DV2(x_new)=Decision hyperplance(class2, x_new)
DV3(x_new)=Decision hyperplance(class3, x_new)
argmax({DVi, i=1,2,3})

從圖例來看，OAA為什麼是取最大的decision value?

Case 1: 新的資料就是直接落在紅色區域，這時候這個資料帶到decision hyperplance (class1)得到的值會大於0，這個資料帶到decision hyperplance (class2)和decision hyperplance (class3)都會小於0，所以這個資料是判給紅色(類別1)。

Case 2: 新的資料就是直接落在紅色(類別1)區域和藍色(類別3)區域，這時候這個資料帶到decision hyperplance (class1)得到的值會大於0，這個資料帶到decision hyperplance (class3)得到的值也會大於0，但這個資料帶到decision hyperplance (class3)會小於0。
但這個資料帶到decision hyperplance (class1)「離紅色線較遠」又是在「值是正值」的區域，所以這個值會遠大於0。但這個資料帶到decision hyperplance (class3)離藍色線雖然在「值是正值」的區域，但這個資料很接近「藍色線」，所以這個值很接近0。所以DV1(x_new)> DV3(x_new)，所以這個資料是判給紅色(類別1)。

Case 3: 新的資料就是直接落在混淆區(confusion area)，這個時候這筆資料帶到哪個decision hyperplane 都會小於0，「值都會在負值區」。因此這個時候會希望資料判給「越接近哪條線」(decision value最大)的那類。此例新資料較接近綠色的線(類別2)，所以這個資料是判給綠色(類別2)。

這樣的介紹應該讓人很清楚OAA在幹什麼吧。

one-against-one(OAO)

這個方法中文翻譯「一對一」，從名稱來看跟OAA一樣非常直覺。

OAO策略:

先拿第1類和第2類用二元分類器學習一次得到一個分類器/decision hyperplane，然後再用第1類和第3類用二元分類器學習一次得到一個分類器/decision hyperplane，直到第1類都和其他類作過二元分類器學習。
然後換第2類和第3類用二元分類器學習一次得到一個分類器/decision hyperplane，然後再用第2類和第4類用二元分類器學習一次得到一個分類器/decision hyperplane，直到第2類都和其他類作過二元分類器學習。
一直重複到，所有類別都彼此分類學習過為止。

判別類別方式為看此樣本被判斷哪一類的次數最多，這個樣本就判給哪一類。

假設有L類的分類問題，OAO總共就會訓練(C L取2)個二元分類器。

OAO用圖例說明，延續剛剛的三分類的問題，有紅色(類別1)、綠色(類別2)，藍色(類別3)，OAO剛好也是訓練三個分類器。

第1次，把紅色(類別1)和綠色(類別2)進行二元分類器訓練(decision hyperplance (class1 vs class2))。

第2次，把紅色(類別1)和藍色(類別3)進行二元分類器訓練(decision hyperplance (class1 vs class3))。

第3次，把綠色(類別2)和藍色(類別3)進行二元分類器訓練(decision hyperplance (class2 vs class3))。

所以經由上述步驟，可以得到三個二元分類器
1. Decision hyperplance (class1 vs class2)
2. Decision hyperplance (class1 vs class3)
3. Decision hyperplance (class2 vs class3))

所以當我們有新的樣本(x_new)要進來分類時，將這個樣本丟進去這三個hyperplance去被這三個分類器分到的類別次數，最後用Majority vote的方式進行投票，新的樣本會被判別到得到最多票的那類，如下圖範例為判給第1類。

但有沒有可能有好死不死，剛好每一類都只得到一票，或是剛好有兩類的票數一樣? 答案是肯定一定有。

Majority vote只是Multi-classification system或是ensemble learning內最基本decision fusion的一種方式。

Majority vote是初階版的decision fusion的方法，所以就一定有進階版的。
進階版就是將每一個分類器的output做sum、weight sum或是其他奇奇怪怪的fusion technique(以前還做過fuzzy fusion)，去得到最後的結果，這時候就不太會有不知道判哪一類的情況拉。

看完了這篇文章，對OAA和OAO怎麼對二元分類器怎麼進行多類別分類問題，應該有比較深的認識。通常這個方法都是跟著SVM一起去介紹的，因為SVM是一個標準且很強大的二元分類器，所以SVM的多類別分類的方法通常會接著一起介紹。
但OAO和OAA各有千秋，沒有說哪種方式可以得到較好得結果，但根據我得經驗，如果是用SVM，OAO對於類別樣本數大小差距懸殊的分類問題可以得到較好的結果，OAA在這種問題上比較不好，最大原因是樣本數少的那類在training過程中可能會因為樣本數大的類別比重較重，在訓練過程中被犧牲掉了。

當然樣本數大小差距懸殊的問題或是小樣本的問題可以用oversampling的方式解決，這邊就不在介紹這個問題了。