不均衡データの学習 ~imblanced-learnを例に~

ちゃお・・・† まいおり・・・†

不均衡データとは？

不均衡データとはクラスに属するサンプルサイズに偏りがある不均衡なデータのことです。 例えば、ネット広告のCTR (Click Through Rate; クリック率) のデータは正例 (クリックした数) が少なく、負例 (クリックしなかったケース) がほとんどです。

そこでなんとかデータを均衡にしていこうという試みがあります。対処法は大きく分けて2つあります。algorithm-level approaches (正例を誤答したときにペナルティを重くする方法) とdata-level approaches (正例と負例のサンプル数を調整する方法) です。この記事では後者について扱います。 以前に不均衡データに強いと謳っていたNegationNaiveBayesやその仲間について紹介しましたが、今回はimblanced-learnで採用されている手法を紹介していきます。

※結果的にほとんどimblanced-learnのドキュメントを日本語訳しただけの記事になってしまったので、imblanced-learn知ってるよ！って方はお手数ですが回れ右してください・・・†

Over sampling

Over samplingとはサンプルが少ないクラスのサンプルを増やして均衡にしていくことです。

Naive random over-sampling (RandomOverSampler)

この問題を解決する1つの方法は、サンプルの少ないクラスで新しいサンプルを生成することです。 最も単純な手法は、利用可能なサンプルをランダムにサンプリングして新しいサンプルを生成することです。ただし、それでは過学習を引き起こしやすいことに注意です。

SMOTE and ADASYN

置換を伴う無作為抽出とは別に、(i) Synthetic Minority Oversampling Technique (SMOTE) と (ii) Adaptive Synthetic (ADASYN) サンプリング法といった2つの一般的な手法があります。

前述のRandomOverSamplerは少数派クラスの元のサンプルの一部を複製することによってオーバーサンプリングしますが、SMOTEとADASYNは補間によって新しいサンプルを生成します。 しかし、新しい合成サンプルを補間/生成するために使用されるサンプルは異なります。 ADASYNは、k-NN (k-nearest neighbor) 分類器を使用して間違って分類された元のサンプルの隣にサンプルを生成することに焦点を当てていますが、SMOTEのベーシックな実装では学習中に検出される決定関数はアルゴリズム間で異なります。

SMOTEはinlierとoutlier (外れ値) を接続することがありますが、ADASYNはどちらの場合も準最適な決定機能につながる外れ値のみに焦点を当てることがあります。 これに関して、SMOTEはサンプルを生成するための3つの追加オプションを提供しています。 これらの方法は、最適な決定関数の境界付近のサンプルに焦点を合わせ、最近傍クラスの反対方向にサンプルを生成します。

SMOTEとADASYNは新しいサンプルを生成するのに同じアルゴリズムを使います。xi$x_i$x​i​​を考えるとき、kNNによって新しいサンプルxnew$x_{new}$ は生成されます。これらの最近傍xzi$x_{zi}$が選ばれ、サンプルが以下のように生成されます。

xnew=xi+λ×(xzi−xi)$x_{new}=x_i+\lambda \times (x_{zi}-x_i)$

各SMOTEとADASYNは、新しいサンプルを生成する前にサンプルxi$x_i$x​i​​を選択することによってお互いに異なります。

通常のSMOTEアルゴリズム

ルールを課すことなく、利用可能なすべてのxi$x_i$x​i​​をランダムに取得します。

Borderline SMOTE

各サンプルxi$x_i$を（i）ノイズ (全ての最近傍がxi$x_i$x​i​​のものとは異なるクラスである) 、(ii) 全ての最近傍は、xi$x_i$とは異なるクラスからのものである、または (iii) 安全である (全ての最近傍がxi$x_i$x​i​​と同じクラスからのものである） Borderline-1 SMOTEでは、xzi$x_{zi}$はサンプルxi$x_i$と異なるクラスに属しますが、Borderline-2 SMOTEはxzi$x_{zi}$を考慮します。

SVM SMOTE

SVM (Support Vector Machine) 分類器を使用してサポートベクトルを見つけ、それを考慮したサンプルを生成します。 SVM分類器のCパラメータは、より多くのまたはより少ないサポートベクトルを選択することを可能にします。

ADASYN

ADASYNは通常のSMOTEと同様に動作します。しかし、各xi$x_i$x​i​​に対して生成されるサンプルの数は、所与の近傍におけるxi$x_i$x​i​​と同じクラスにないサンプルの数に比例します。したがって、最近傍ルールが尊重されない領域では、より多くのサンプルが生成されます。

Under sampling

Under samplingとはサンプルが多すぎるクラス (majority class) のサンプルを減らして均衡にしていくことです。 Random under samplingでは有益なデータを削除してしまう可能性があります。一方で、クラスターベースの手法なら各クラスdistinctなデータ群となるため、一部の有益なデータのみを消す事はありません。

ClusterCentroids

クラスタリング手法を使ってcentroidによってアンダーサンプリングしていく方法です。 ここではクラスターのmajority sampleをKMeansアルゴリズムのクラスタの重心に置き換えることでmajority classをサンプルします。このアルゴリズムはNクラスタとKMeansアルゴリズムをmajority classにフィットさせたり、Nクラスタのcentroidの調和を使うことでN majority sampleをキープします。

CondensedNearestNeighbour

この手法では、最近傍ルールを使ってサンプルを消すべきかどうかを繰り返し決めます。

1. セットCから全てのminority sampleを得る
2. Cの中の対象となるクラス(under-samplingされるクラス)と、このクラスの他のすべてのサンプルをセットSに追加
3. セットSを調べて最近傍ルールを使って各サンプルを分類
4. もしサンプルが誤分類だったらCに加える。そうでなければ何もしない
5. 追加するサンプルがなくなるまでSを繰り返す

OneSidedSelection

逆に、この手法はTomekLinksを使用してノイズの多いサンプルを除去します。 さらに、最近傍ルールがすべてのサンプルに適用され、誤分類されたルールがセットCに追加されます。セットSの反復は行われません。

Tomek links

1. class Aのインスタンスxとclass Bのインスタンスyがあります
2. d(x, y)はx, y間の距離を示します
3. もしもあるインスタンスzが d(x,y)<d(x,z)$d(x, y) < d(x, z)$d(x,y)<d(x,z) あるいは d(x,y)<d(y,z)$d(x, y)< d( y, z)$d(x,y)<d(y,z) のとき (x, y) はTomek linksであるといえます
4. もしもある2インスタンスがTomek linksだったら、そのうちの一つはノイズであるか、両方ともクラスの境界にあるので消します

NeighbourhoodCleaningRule

この手法は、データを圧縮するよりもデータのクリーニングに重点を置いています。 したがって、EditedNearestNeighbours と3つの最近傍の識別器間で拒絶されるサンプルの和集合を使用します。

Combination of over- and under-sampling

オーバーサンプリングとアンダーサンプリングを組み合わせた手法です。

SMOTEENN

SMOTEとEdited Nearest Neighboursを組み合わせてover- and under-samplingします。

SMOTETomek

SMOTEとTomek linksを組み合わせてover- and under-samplingします。

参考

• imblanced-learn
• 不均衡データにおけるsampling - Qiita
• 不均衡データのクラス分類