Sansan Tech Blog

Sansanのものづくりを支えるメンバーの技術やデザイン、プロダクトマネジメントの情報を発信

【ML Tech RPT. 】第4回 不均衡データ学習 (Learning from Imbalanced Data) を学ぶ(1)

f:id:ssatsuki040508:20181210005017p:plain
Sansan DSOC 研究員の吉村です。最近は憩いの場を求めて、休日に都内の図書館をまわるのが趣味になっています。先輩にこの話をしたところ、国会図書館をオススメされたので、近々行ってみようと思っている今日この頃です。

さて、今回は実データを分析する時に頻繁に出現し、予測が難しい 不均衡データ学習 (Learning from Imbalanced Data) 問題について調べました。下記では、不均衡データ学習の概要とその対処法についてまとめました。

不均衡データ (Imbalanced Data)

不均衡データ とは、目的変数の分布に大きな偏りがあるデータのことを指します。これだけでは分かり難いと思うので、簡単な二値分類における不均衡データの場合を例にとって説明します(以降、本記事においては特に断らない限り、二値分類における不均衡データ学習を想定して説明)。 細胞が癌化したか否かを予測するタスク (以降、癌化予測タスクと呼ぶ) を考えます。各細胞が癌化しているか否かをアノテーションをした結果、癌化している細胞の数 (つまり、正例 データ数) が232件、癌化していない細胞の数 (つまり、負例データ数) が9,768件だったとします。この時、正例が全体のたった2.3%程度しかない一方で、負例は全体の97.7%近くを占めます。このように、一方のラベルに対して、もう片方のラベルが極端に多い、または、少ないデータのことを不均衡データと呼びます。

不均衡データとなる場面

発生する可能性が極めて低い事象を予測の対象とする場合に、不均衡データが生じます。具体的には、滅多に発生しない疾患や悪性病変の発生を正例とする場合、クレジットの与信の判定をする場合、不適切なwebページや商品を正例とする場合などがそれに当たります。

不均衡データを扱う場合の注意点

上述した癌化予測タスクでは、非常に高い Accuracy を達成するはずです。なぜなら、同じ分布から生成されるテストデータセットに対して、全ての細胞を"癌化しない"と予測するだけで、およそ 0.9768 の Accuracy が達成できるからです。しかしながら、この場合は、癌化した細胞 (正例) を一つも癌化している (正例) と予測することはできていません。つまり、True Positive の件数は0件であるため、Recall は0です。おそらくこれでは本来の目的は達成できていないはずです。

不均衡データ学習で重要なことは、達成したい目標が何かを明確にすることです。つまり、 Accuracy を上げたいのであればこのままで良いですが、Recall を上げたいのであればこの分類法は全く意味を成しません。普通、不均衡データ学習では、Accuracy を高くすることが目標ではない場合が多いです。なぜなら、不均衡データ学習では、負例を誤って正例と予測してしまうこと(第一種の誤り) による影響と、正例を誤って負例と予測してしまうこと (第二種の誤り) による影響とが、多くの場合異なるためです。例えば、先ほどの癌化予測タスクの例では、癌化している細胞を癌化していないと予測した場合、癌細胞の発見が遅れてしまい、一大事になる可能性があります。しかし、癌化していない細胞を癌化していると予測した場合には、精密検査を行えば癌化していないことがわかり特に重大な影響はありません。つまり、不均衡データ学習では重要度の異なるこれら二種の誤りをどのように扱うのかを適切に理解することが重要となります。

不均衡データ学習に用いられるアプローチ

不均衡データ学習では、次の三つのアプローチがよく利用されます。
一つ目が、多い方のラベルのデータを減らしたり、少ない方のラベルのデータを増やしたりするデータレベル (Data-Level) のアプローチ、二つ目は、少ない方のラベルのデータを誤分類することに対して、より重いペナルティを課すように損失関数を定義する コスト考慮型学習 (Cost-sensitive Learning) のアプローチ、三つ目は、少ない方のラベルを異常値とみなすことで、異常検知 (Anomaly Detection) 手法を適用するアプローチです。
今回の記事ではこれらの三つの手法のうち、特にデータレベルのアプローチの詳細について見ていきます。残りのコスト考慮型学習のアプローチと異常検知手法を適用するアプローチは次回以降の記事でまとめます。

データレベルのアプローチ

不均衡データ学習では、各ラベルの数が不均衡であることが問題となるため、多い方のラベルのデータを減らすか、少ない方のラベルのデータを増やすことで、各ラベルの数を均衡にしようとするのは自然な発想と言えます。データレベルのアプローチでは、多い方のラベルのデータを減らす手法を Undersamping (/Downsampling) と言い、少ない方のラベルのデータを増やす手法を Oversampling (/Upsampling) と言います。

Undersampling

Undersampling は実施するのが非常に簡単です。特に、少ない方のラベルの数に合うように多い方のラベルの中からランダムサンプリングする方法は容易に実装できます。ただ、これだけではランダムサンプリング後のデータ分布に偏りが発生してしまう恐れがあるため、普通はクラスタ分析などを行なった後にサンプリングを実施します。一見して、 Undersampling は実装が簡単なだけでなく、不均衡さを取り除くことができ、更に、訓練データを小さくし学習コストを減らすことができるため非常に良い方法に思えます。

しかしながら、一般的な Undersampling では、学習に有用なデータをサンプリング時に捨てたり、全体のデータ数が不足したりするため、次の二つの問題を引き起こす原因になることに注意する必要があります。一つ目が、学習した分類器の分散が大きくなる問題です。これに対処するためには、UnderBagging [*1] のような平均化戦略を取るのが一般的です。UnderBaggingは、Undersampling を実施して k 通りの部分集合を作成し 、各部分集合ごとに分類器を学習し Bagging でアンサンブルする手法です。二つ目が、学習後に得られる事後分布が歪む問題です。これに対処するためには、テスト用のデータの事前分布を用いて事後分布を修正する必要があります。[*2] では、EMアルゴリズムに基づいて事前分布を推定しつつ、事後分布を修正する手法が提案されています。

[*3] では、これらの問題を踏まえた上で、どのような場合に Undersampling が有効に働くのかについての研究がなされています。この論文の中では、Undersampling が有効に働く条件が導出されており、人工データと実データを用いた実験を通して、確かにその条件を満たす場合に Undersampling が有効に働くことが確認されています。

Oversampling

データ不足の問題に陥らないデータレベルのアプローチ法として Oversampling があります。 Oversampling の代表的な手法として良く知られているのが SMOTE (Synthetic Minority Oversampling TEchnique) [*4] です。 SMOTE は、少ない方のラベルが付いた各データ点同士を線でつなぎ、その線分上の任意の点をランダムに人工データとして生成する手法です。SMOTE は不均衡データ学習における先駆的な存在であり、それ以前の時代で用いられていた、少ない方のデータを単に複製する方法では過学習してしまうことが知られていたため、データを増やすために人工データを生成するという発想が当時は画期的でした。

SMOTE が提案されて15年以上が経つ現在では、 SMOTE の拡張版が数多く提案されています。 [*5] によれば、SMOTEの拡張方針として次の7つの項目が挙げられています。

  1. Oversamplingするためのデータ点の初期選択: 基準となる少ない方のデータ点をどうやって決定するか。
  2. Undersampling との統合: Undersampling を Oversampling の前と後のどちらで実行するか。
  3. 補完手法の種類: 補完する範囲についての制限をどうやって決定するか。
  4. 次元変化を伴う操作: 人工データ生成を次元削減や次元拡張の前に実施するか、最中に実施するか。
  5. 人工データの適応的生成: 人工データ生成の際に、適応的な手法を用いるか否か。
  6. Relabeling: どのデータ点を再ラベル付けするか。
  7. ノイズがのっている生成データ点に対するフィルタリング: SMOTE を実施後にノイズ除去のためのフィルタリングステップを入れるか否か。

つまり、既存の SMOTE 拡張の多くが、上記の項目のいくつかを独自にアレンジしたものであるということになります。

SMOTEの拡張手法

SMOTE の拡張手法は [A. Fernandez et.al. 2018] によると、現在までで85種以上が提案されているようです。下記にその一部を示します。下記の一覧のうち、 * はその手法が [A. Fernandez et.al. 2018] で"非常によく知られた手法"として紹介されているものを表し、 \dagger は Python の不均衡データ学習用のライブラリである imbalanced-learn で実装されているものを表します。また、各手法の詳細を述べると非常に長くなるため今回は割愛します。気になる方は、 [A. Fernandez et.al. 2018] や imbalanced-learn で簡潔な説明がされているため、これらをご覧ください。

  • Borderline-SMOTE ^{*} [*6]
  • AHC ^{*} [*7]
  • ADASYN ^{*\dagger} [*8]
  • Safe-Level-SMOTE ^{*} [*9]
  • DBSMOTE ^{*} [*10]
  • ROSE ^{*} [*11]
  • MWMOTE ^{*} [*12]
  • MDO ^{*} [*13]
  • SMOTEENN ^{\dagger}, SMOTETomec ^{\dagger} [*14]
不均衡データ回帰 (Imbalanced Regression) における Oversampling

これまでは二値分類の場合の不均衡データ学習について述べてきましたが、当然、回帰問題でも不均衡データ学習となる場合があります。回帰問題における不均衡データ学習では、連続値をとる目的変数のうち、稀に生じる極値を正しく予測することが目標となります。この場合に用いられる手法としてよく知られているのが SMOTER [*15] であり、この手法では稀に発生する極大値と極小値をユーザが定義する閾値を基に定義します。 また、更に発展して、時系列データ (Time Series Data) に対応した SMOTER の拡張手法もあります。

まとめ

今回は不均衡データ学習の概要と、データレベルのアプローチについて説明しました。特にデータレベルのアプローチについては、 Undersamping を利用する際の課題と解決策、Oversampling 手法としての SMOTE の拡張手法に重点を置いて確認しました。今回は紹介できませんでしたが、SMOTE は特殊な問題設定に特化した拡張も多く提案されています。具体的には、ストリームデータ学習半教師あり学習能動学習マルチクラス分類マルチラベル分類マルチインスタンス分類などに対応したものです。そのため、特殊な問題設定における不均衡データを扱う場合には、より対象の問題設定に適応した手法を調べてみるのも一つの手かもしれません。

本文で述べたように、不均衡データ学習に対処するためのアプローチは他にもコスト考慮型学習のアプローチと異常検知を用いたアプローチがあるので、次回以降の記事で触れていきたいと思います。次回以降も引き続きお付き合いください。

*1:S. Wang, K. Tang, and X. Yao, "Diversity exploration and negative correlation learning on imbalanced data sets," in IJCNN, 2009.

*2:M. Saerens, P. Latinne, and C. Decaestecker, "Adjusting the outputs of a classifier to new a priori probabilities: a simple procedure," in NC, 2002.

*3:A. Dal Pozzolo, O. Caelen, and G. Bontempi, "When is undersampling effective in unbalanced classification tasks?," in ECML/PKDD, 2015.

*4:N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, "SMOTE: Synthetic minority over-sampling technique," in JAIR, 2002.

*5:A. Fernandez, S. Garcia, F. Herrera, and N. V. Chawla, "SMOTE for Learning from Imbalanced Data: Progress and Challenges, Marking the 15-year Anniversary," in JAIR, 2018.

*6:H. Han, W. Y. Wang, and B. H. Mao, "Borderline–SMOTE: A new over–sampling method in imbalanced data sets learning," in ICIC, 2005.

*7:G. Cohen, M. Hilario, H. Sax, S. Hugonnet, and A. Geissbuhler, "Learning from imbalanced data in surveillance of nosocomial infection," in AI in medicine, 2006.

*8:H. He, Y. Bai, E. A. Garcia, and S. Li,"ADASYN: Adaptive synthetic sampling approach for imbalanced learning," in IJCNN, 2008.

*9:C. Bunkhumpornpat, K. Sinapiromsaran, and C. Lursinsap, "Safe-level-SMOTE: Safe-level-synthetic minority over-sampling technique for handling the class imbalanced problem," in PAKDD, 2019.

*10:C. Bunkhumpornpat, K. Sinapiromsaran, and C. Lursinsap, "DBSMOTE: Density- based synthetic minority over-sampling TEchnique," in Applied Intelligence, 2012.

*11:G. Menardi, and N. Torelli, "Training and assessing classification rules with imbalanced data.," in DMKD, 2014.

*12:S. Barua, M. M. Islam, X. Yao, and K. Murase, "MWMOTE-Majority weighted minority oversampling technique for imbalanced data set learning," in TKDE, 2014.

*13:L. Abdi, and S. Hashemi, "To combat multi-class imbalanced problems by means of over-sampling techniques," in TKDE, 2016.

*14:G. E. A. P. A. Batista, R. C. Prati, and M. C. Monard, "A study of the behaviour of several methods for balancing machine learning training data, " in KDD Explorations, 2004.

*15:L. Torgo, P. Branco, R. P. Ribeiro, and B. Pfahringer, "Resampling strategies for regression," in ES, 2015.

© Sansan, Inc.