One-vs-RestとOne-vs-Oneを実装してみた

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

今回は、2クラス分類器を多クラス分類器へと拡張する手法である、One-VS-Rest(一対他) とOne-VS-One(一対一)を実装して、
ロジスティック回帰に適用する実験を行ってみます。

### 多クラスへの拡張

モデルによっては、2値分類しか扱うことができないものがあります。

最小二乗回帰やSVM,ロジスティック回帰など、むしろオリジナルの分類器は2値分類であることの方が多いのかもしれません。

多クラス分類を行う手法として、直接多クラス分類を行うモデルを構築するのが一つの手です。
deep learningの出力層にsoftmaxをいれて、クロスエントロピーを目的関数に持ってくるとか、そんなかんじのがよくある例だと思います。

もう一つ、直接多クラスの分類モデルを構築するのではなく、2値分類を行う分類器をいくつか組み合わせることで多クラス分類を行う手法があります。

それが、今回扱うOne-VS-Rest(一対他) とOne-VS-One(一対一)です。
以下、$C$個のクラスがあるとします。

### One-VS-Rest(一対他)

One-VS-Rest(一対他)は、$C$個の2値分類器を学習します。

一つ目の分類器は、クラス1を正例、その他のクラスを負例とする分類器になるように学習します。
同様に、$i$番目の分類器はクラス$i$が正例に、その他のクラスを負例として学習します。

推論時は、$C$個の分類器全てに予測させて、一番正例である確信度が高いと予測されたクラスを最終的な予測結果とします。

確信度を用いるので、2値分類器には各クラスに属する予測確率(またはそれに比例するなんらかの数値)を出力できるモデルを用いる必要があります。

その他のクラスを負例とする、という部分がRestに対応していますね。

利点としては、クラスの個数だけ分類器を学習すればいいので次に紹介するOne-VS-One(一対一)よりは分類器の個数が少なくて済みます。

短所としては、各分類器の学習に用いるデータの正例負例の割合が偏ってしまうことが挙げられます。

### One-VS-One(一対一)

もう一つの手法であるOne-VS-One(一対一)は、$C(C-1)/2$個の分類器を学習します。

一対一という名前の通り、$C$個あるクラスから2つ選んできて、片方のクラスを正例、もう片方のクラスを負例として学習を行います。

推論時は、学習した$C(C-1)/2$個の分類器にそれぞれ予測させ、それぞれの分類器が予測したクラスに投票していきます。

一番投票数が多かったクラスが全体としての予測になります。

どれくらいの確信度で投票したかなどを考慮することもできそうですが、今回は確信度は考慮せず単純に分類された数が最大のクラスを選ぶようにしてみます。

分類器の個数はOne-VS-Rest(一対他)よりも多くなってしまいますが、各学習に用いるデータの偏りは小さくなります。

### 実装

pythonで実装してみました。
両方とも、`fit`と`predict_proba`をもつ2値分類modelであれば動作するように作ってあります。
基本的にはscikit learnに準拠したモデルを想定しています。

もちろん上の条件を満たせば自作の2値分類器を与えても動きます。

```python
class OneVsRestClassifier:
    """一対他分類器."""

def __init__(self, class_num, classifier, params=None):
        """binary classifierを受け取り、クラスの数分インスタンスを作成する."""
        self.class_num = class_num
        if params is None:
            self.classifiers = [classifier() for _ in range(class_num)]
        else:
            self.classifiers = [classifier(**params) for _ in range(class_num)]

def fit(self, X, y):
        for i in range(self.class_num):
            print(f"Training classifier{i}...")
            self.classifiers[i].fit(X, self.re_labaling(y, i))
        return self

def re_labaling(self, y, pos_label):
        """labelを受け取り、pos_labelに指定したカテゴリを+1、それ以外を-1にラベリングしなおしたデータを返す."""
        return np.where(y == pos_label, 1, -1)

def predict(self, X):
        scores = np.array([model.predict_proba(X)[:, 1]
                           for model in self.classifiers])
        return np.argmax(scores, axis=0)

def evaluate(self, X, y):
        pred = self.predict(X)
        return accuracy_score(y, pred)

```

```python
class OneVsOneClassifier:
    """一対一分類器."""

def __init__(self, class_num, classifier, params=None):
        """binary classifierを受け取り、c(c-1)/2個のインスタンスを作成する."""
        self.class_num = class_num
        self.perm = list(combinations(list(range(class_num)), 2))
        if params is None:
            self.classifiers = [classifier() for _ in range(len(self.perm))]
        else:
            self.classifiers = [classifier(**params)
                                for _ in range(len(self.perm))]

def fit(self, X, y):
        for i in range(len(self.classifiers)):
            X_i, y_i = self.extract_dataset(X, y, i)
            print(f"Training classifier{i}...")
            self.classifiers[i].fit(X_i, y_i)
        return self

def extract_dataset(self, X, y, i):
        pos = self.perm[i][0]
        neg = self.perm[i][1]
        X = X[(y == pos) | (y == neg)]
        y = y[(y == pos) | (y == neg)]
        y = np.where(y == pos, 1, -1)
        return X, y

def predict(self, X):
        votes = np.zeros((len(X), self.class_num))
        for i in range(len(self.classifiers)):
            prediction = self.classifiers[i].predict(X)
            voted = np.where(prediction == 1, self.perm[i][0], self.perm[i][1])
            for j in range(len(voted)):
                votes[j, voted[j]] += 1
        return np.argmax(votes, axis=1)

def evaluate(self, X, y):
        pred = self.predict(X)
        return accuracy_score(y, pred)

```

### 数値実験

簡単にirisデータセットで実験してみました。
3クラス分類問題です。

2値分類器にはロジスティック回帰を用いています。

One-VS-Rest(一対他) とOne-VS-One(一対一)のほかに、scikit learnにあるロジスティック回帰モデルも使います。

scikit learnにあるロジスティック回帰モデルはOne-VS-Restを用いて多クラスへ拡張した実装になっているとドキュメントにある(<a href="https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html">sklearn.linear_model.LogisticRegression</a>)ので、比較してみます。

#### 結果
テストデータのAccuracyです。
```
One-VS-Rest: 100%
One-VS-One: 96.67%
scikit learn: 100%
```

確かにscikit learn のモデルとOne-VS-Restが同じ結果です。

### まとめ

2値分類器を多クラス分類へ拡張する手法であるOne-VS-Rest(一対他) とOne-VS-One(一対一)を実装して、irisで実験しました。

One-VS-Rest(一対他) とOne-VS-One(一対一)のどちらがいいかは問題によるみたいです。
試しに他の手書き画像を分類してみると今度はOne-VS-Oneの方が性能が良かったりしたので、ほんとみたいです。

あと、少し気になった「One-VS-Oneの確信度を考慮して投票させる」というアイデアについても少し調べてみたいと思います。

ありがとうございました。

このブログを検索

ぐぐりらにっき

One-vs-RestとOne-vs-Oneを実装してみた

コメント

コメントを投稿

One-vs-RestとOne-vs-Oneを実装してみた

この記事をシェアする

コメント

コメントを投稿