18. 다중 클래스(Multi-Class) 분류를 위한 One vs Rest, One vs One 방법을 알아보자.

---

이진(Binary) 클래스에서는 잘 동작하는 분류기(모형)들이 다중 클래스(Multi-Class) 분류 문제로 확장하기가 어려운 경우가 있다. 이때에는 다중 클래스(Multi-Class) 분류 문제를 여러 개의 이진 분류 문제로 쪼개서 해결할 수 있다.

 

다중 클래스(Multi-Class)에서 한 클래스를 1 나머지를 0으로 코딩하여 이진 분류기를 여러개 생성하는 One vs Rest 방법이 있고 다중 클래스 문제를 서로 다른 모든 클래스의 쌍으로 쪼개서 푸는 One vs One 방법이 있다. 

 

이번 포스팅에서는 이 방법에 대한 내용을 소개한다.

 

- 목차 -

1. One vs Rest

2. One vs One

---

---

이곳은 꽁냥이가 머신러닝을 공부한 내용을 정리하는 곳입니다.

이 포스팅에서는 수식을 포함하고 있습니다. 티스토리 피드에서는 수식이 제대로 표시되지 않을 수 있으니 웹브라우저 또는 모바일 웹브라우저로 보시길 바랍니다.

---

---

   1. One vs Rest

- 정의 -

One vs Rest 방법은 다중 클래스 문제를 여러 개의 이진 분류 문제로 바꾸는데 이때 하나의 이진 분류기는 한 클래스를 1, 나머지 클래스를 0으로 취급하여 학습된다.

a. 과정

먼저 $K$개의 클라스가 있다고 하자. 그리고 데이터 $(x_i, c_i), i=1, \ldots, n$가 있다. 이때 $x_i$는 $p$차원 설명 변수 벡터이고 $c_i\in \{1, \ldots, K \}$이다.

 

이러한 상황에서 One vs Rest 방법은 총 $K$개의 이진(Binary) 분류기가 다음과 같이 만들어진다.

 

$k \in \{1, \ldots, K \}$에 대하여

(1) 만약 $c_i=k$라면 $z_i = c_i$, 아닌 경우 $z_i=0$으로 설정한다.

(2) 새롭게 만들어진 데이터 $(x_i, z_i), i=1, \ldots, n$에 대하여 이진 분류기를 학습한다.

b. 예측

새로운 데이터 $x$가 들어왔을 때 $z_i=k, k=1, \ldots, K$일 확률(또는 점수)을 나타내는 $f_k(x)$를 계산한다. 이런 식으로 $K$개의 확률(또는 점수)을 계산하고 이를 최대화하는 $k$를 최종 예측 라벨로 선정한다. 

$$\DeclareMathOperator*{\argmaxA}{arg\,max} \hat{c} = \argmaxA_{k}f_k(x)$$

 

만약 분류기가 확률을 계산할 수 없고(예: 서포트 벡터 머신) 라벨만을 예측하는 경우에는 가장 많이 나온 라벨을 예측 라벨로 한다.

- 예제 -

먼저 3개의 클래스가 있다고 하자. 각각 라벨은 1, 2, 3으로 하겠다. 그렇다면 아래와 같이 3개의 이진 분류기를 학습하고 각 클래스에 대한 확률(또는 점수)을 계산한다. 

 

one vs rest 설명

위 그림에서 라벨 1과 나머지(2, 3)에 대해서 이진 분류기를 학습하고 새로운 데이터 $x$에 대하여 라벨 1일 확률이 $f_1(x) = 0.2$으로 계산된 것이다. 라벨 2와 나머지 (1, 3)에 대해서도 이진 분류기를 학습하고 새로운 데이터 $x$에 대하여 라벨 2일 확률이 $f_2(x) = 0.8$로 계산 된 것이다.

 

그렇다면 새로운 데이터 $x$의 라벨은 어떻게 예측될까? $f_2(x)$의 값이 제일 크므로 예측 라벨은 2가 된다.

$$\DeclareMathOperator*{\argmaxA}{arg\,max} \begin{align} \argmaxA_{k\in\{1,2,3\}}\{f_1(x), f_2(x), f_3(x)\} &= \argmaxA_{k\in\{1,2,3\}}\{0.2, 0.8, 0.4\} \\ &= 2\end{align}$$

- 장단점 -

a. 장점

구현이 쉽다.

b. 단점

One vs Rest 방법은 $K$ 클래스인 경우 $K$개의 이진 분류기를 학습한다. 이때 각 분류기가 확률이 아닌 다른 점수(Score)를 계산한다면 이러한 점수들은 이진 분류기 별로 스케일 차이가 날 수 있다. 이는 이진 분류기들의 각 클래스에 대한 점수 비교를 어렵게 한다.

 

또한 원(Raw) 데이터 상으로 각 클래스별로 균형 잡힌(Balanced) 데이터인데 이를 한 클래스대 나머지로 설정해버리면 나머지 클래스 데이터가 일방적으로 많게 되어 불균형(Unbalanced) 데이터가 된다. 이는 각 이진 분류기가 학습이 잘 안 되는 결과를 초래할 수 있다.

---

   2. One vs One

- 정의 -

One vs One 방법은 다중 클래스(Multi-Class)를 가진 데이터를 서로 다른 두 개의 클래스를 갖는 데이터로 쪼개고 이를 이진 분류기로 학습하는 방법이다.

a. 과정

먼저 $K$개의 클래스가 있다고 하자. 그리고 데이터 $(x_i, c_i), i=1, \ldots, n$가 있다. 이때 $x_i$는 $p$차원 설명 변수 벡터이고 $c_i\in \{1, \ldots, K \}$이다.

 

그렇다면 $K$개 중에서 서로 다른 2개를 뽑는 조합의 수 $J = K(K-1)/2$만큼의 이진 분류기를 학습하게 되는데 과정은 다음과 같다.

 

$j \in \{1, \ldots, J \}$에 대하여

$j$번째 클래스 쌍을 $(m, n)$이라 하자. 즉, $1\leq n \leq K, 1\leq m \leq K$이다. 이때 전체 데이터 중에서 $c_i\in \{m, n\}$인 데이터를 추출한 뒤 이를 이용하여 이진 분류기를 학습한다.

b. 예측

새로운 데이터가 $x$ 들어왔을 때 $j$번째 이진 분류기에 확률(또는 점수) 값을 $f_j(x)$라 하자. 이때 $f_j(x)$를 최대화하는 $j$를 $J^*$ 다음과 같다고 해보자.

$$\DeclareMathOperator*{\argmaxA}{arg\,max} J^* = \argmaxA_{j\in\{1,\ldots, J\}}f_j(x)$$

 

새로운 데이터가 $x$ 들어왔을 때 예측 라벨은 다음과 같다.

$$f_{J^*}(x)\text{'s Label}$$

위 식은 예제를 보면 이해가 될 것이다.

 

만약 분류기가 확률을 계산할 수 없고(예: 서포트 벡터 머신) 라벨만을 예측하는 경우에는 가장 많이 나온 라벨을 예측 라벨로 한다.

- 예제 -

이번에도 라벨이 3개 있다고 하고 각 라벨은 1, 2, 3이다. 이 경우 아래와 같이 3(=(3x2)/2) 개의 이진 분류기를 학습하게 된다. 

새로운 $x$에 대하여 $j$번째 학습된 이진 분류기의 라벨이 $k$인 확률 $f_{jk}(x)$가 다음과 같이 계산되었다고 하자.

이 경우 예측 확률의 최대값은 $f_{12}(x)=0.8$이고 이에 대응하는 라벨인 2를 최종 예측 라벨로 선정하게 된다.

- 장단점 -

a. 장점

구현이 쉽다.

b. 단점

라벨 개수가 많아지면 학습해야 할 이진 분류기가 많아지게 된다. 그리고 확률이 아닌 점수와 같은 형태로 예측하게 된다면 One vs Rest에서의 단점과 같이 스케일이 문제가 될 수 있다.

---

이번 포스팅에서는 기존 이진 분류 모형이 다중 분류(Multi-Class) 문제로 확장하기 어려울 때 사용하는 방법들인 One vs One, One vs Rest를 알아보았다. 이는 다중 분류(Multi-Class) 서포트 벡터 머신에서 사용되기도 하므로 알아두면 이를 이해하는데 도움이 될 것이라 생각한다.

 

참고자료

Multi-Class - 위키백과

 

---