OvA vs OvO

Random forest, Naïve Bayes classifier와 같은 일부 알고리즘들은 multinomial classification을 직접 처리할 수 있지만, SVM, linear classifier 등의 일반적인 알고리즘들은 기본적으로 binary classification만 할 수 있습니다.
그러나 binary classifier를 여러 개 사용하여 multinomial classifier를 구현하기 위해 OvA(OvR)과 OvO 전략을 사용할 수 있습니다.

Remarks

본 포스팅은 Hands-On Machine Learning with Scikit-Learn & TensorFlow (Auérlien Géron, 박해선(역), 한빛미디어) 를 기반으로 작성되었습니다.

OvA (One versus All, OvR, One versus Rest)

하나의 class와 그 외의 나머지 모든 class를 비교하는 classifier를 각각의 class마다 학습시키고, 생성된 모든 classifier 중 가장 큰 예측값을 가지는 class를 최종 예측값으로 선택하는 방법입니다. Scikit-learn에서 binary classification 알고리즘을 사용하여 multinomial classification을 하게되면 대부분 OvA 방식을 통해 작동하게 됩니다.

- Number of class: 10
- Number of train data: 1,000 for each class

# Train
for i in classes
  train i'th binary classifier (i or not) using full class data (10,000)

# Test
predict the class with the maximum probability value of classifier

OvO (One versus One)

하나의 class와 또다른 하나의 class를 비교하는 classifier를 각각의 class마다 학습시키고, classifier들의 예측값들을 비교하여 가장 많이 예측된 class를 최종 예측값으로 선택하는 방법입니다. SVM의 경우 기본적으로 LinearSVC(liblinear library 사용)를 제외하곤 OvO 방식으로 작동합니다. Quadratic programming 과정이 포함되어 한 번에 비교적 적은 수의 data를 사용하는 OvO 방식을 선호하는 것이라 생각됩니다.

- Number of class: 10
- Number of train data: 1,000 for each class

# Train
for i in classes
  for j in classes except i
    train ij'th binary classifier (i or j) using i'th and j'th class data (2 * 1,000)

# Test
predict the class voted the most among the classifiers

한편, Scikit-learn에서 OvO나 OvA를 사용하도록 강제할 수도 있습니다.

1
2
3
4
5
6
7
from sklearn.multiclass import OneVsOneClassifier, OneVsRestClassifier

ovo_clf = OneVsOneClassifier(SGDClassifier(max_iter=5, random_state=42))
ovo_clf.fit(X_train, y_train)
ovo_clf.predict(X_test)

len(ovo_clf.estimators_)  # 45

PREVIOUSEtc