【西瓜書】周志華《機器學習》學習筆記與習題探討（三）③

01-25

【第3章線性模型】

〖一、知識點歸納〗

五、多分類學習

多分類學習有兩個思路。

一種是將二分類學習方法推廣到多分類，比如上一節講到的LDA。

另一種則是利用二分類的學習器來解決多分類問題。

下面主要討論第二種。

1、拆解法與拆分策略

拆解法：將多分類任務拆解成為若干個二分類任務求解。

拆解法步驟：

1.通過拆分策略對問題進行【拆分】；

2.為拆分出的每個二分類任務【訓練】一個分類器；

3.對各個分類器的結果進行【集成】，以獲得多分類結果。

（牢記這三個關鍵詞。）

最經典的拆分策略有三種，即「一對一（OvO）」、「一對其餘（OvR）」、「多對多（MvM）」。

多分類學習有 $N$ 個類別 $C_1,C_2,...,C_N$ ，給定數據集 $D={(oldsymbol x_1,y_1),(oldsymbol x_2,y_2),...,(oldsymbol x_m,y_m)},y_iin{C_1,C_2,...,C_n}$

1、OvO：

將 $N$ 個分類分別兩兩配對，從而【拆分】成 $N(N-1)/2$ 個二分類任務；【訓練】時為了區分 $C_i$ 和 $C_j$ 這兩個分類，這 $N(N-1)/2$ 個分類器中的一個將 $C_i$ 作為正例， $C_j$ 作為反例；測試時候將新樣本同時提交給所有分類器，將得到 $N(N-1)/2$ 個分類結果，【集成】的方法是通過投票在這些結果中選出最終結果。

2、OvR：

將 $N$ 個分類中的1個類拿出來作為一個分類器的正例，其餘均設置為反例，從而【拆分】成 $N$ 個分類任務；【訓練】得到 $N$ 個分類結果；【集成】的方法是考慮各被判為正例的分類器的置信度，選擇置信度大的類別標記作為分類的結果。（如只有一個，直接選擇）

OvO與OvR示意圖

3、MvM：

MvM是OvO和OvR的一般形式，反過來說，OvO和OvR是MvM的特例。

MvM每次將若干個類作為正類，若干個其他類作為反類。但其構造必須有特殊的設計，不能隨意選取。常用的一種MvM技術是「糾錯輸出碼」（ECOC）技術。

2、「糾錯輸出碼」（ECOC）技術

ECOC過程主要分兩步：

編碼：對 $N$ 個類進行 $M$ 次劃分，產生 $M$ 個分類器；

解碼： $M$ 個分類器對測試樣本進行預測，得到 $M$ 個預測標記，將其組成編碼；這個編碼與 $N$ 個類別各自的編碼進行比較，返回其中距離最小的類別作為最終預測的結果。

編碼形式又分為二元碼和三元碼，前者指定「正類」、「反類」，後者又多一個「停用類」。

以二元ECOC碼為例：如下圖，首先，將 $N$ （ $N=4$ ）個類通過設計構造成 $M$ （ $M=5$ ）個分類器（ $f_1,f_2,f_3,f_4,f_5$ ），每個分類器為每個類分配了一個標記結果（ $-1$ 或 $+1$ ），這樣一來，每一個類 $C_i,iin{1,N}$ 都獲得了一個 $M$ 位的編碼，這個編碼就是【各類所對應的編碼】。

當有一個測試例 $A$ 的時，先將 $A$ 依照次序放入 $M$ 個分類器中，得到了 $M$ 個分類標記結果（-1，-1，+1，-1，+1）；再將這 $M$ 個標記結果編成一個糾錯輸出碼（-1-1+1-1+1）；最後去和【各類所對應的編碼】進行比較海明距離或歐式距離，距離最短的對應編碼對應的分類就是結果。（圖中結果為 $C_3$ ）