不均衡データはundersampling+baggingしろ、という話
まとめ
不均衡なデータの分類器を学習するときはundersampling+baggingすべし。 特に以下の場合に、コストを調整する手法やoversampling(SMOTEなど)に対して優れている。
- 次元数が多い
- 少数クラスのデータ数(の比率)が少ない
- 学習データの規模が小さい
きっかけ
不均衡なデータを扱う問題に遭遇したので、先人たちの工夫について調べていたところ、以下のツイートを発見した。
imbalanced data に対する対処を勉強していたのだけど,[Wallace et al. ICDM'11] https://t.co/ltQ942lKPm … で「undersampling + bagging をせよ」という結論が出ていた.
— ™ (@tmaehara) 2017年7月29日
ここで紹介されている論文、およびその解説記事などを読み漁った。本記事ではそれらをつまみ食いした知見をまとめる。
論文
Byron C Wallace, Kevin Small, Carla E Brodley and Thomas A Trikalinos, "Class imbalance, redux," Proc. Int'l Conf. Data Mining (ICDM), pp. 754–763. 2011.
不均衡データによって生じる分類器のバイアス
まず、不均衡データによって分類器にバイアスが生じる様子を示す。
簡単のため線形分類器で2値分類をする場合を考える。正規分布のような山は、それぞれ正例と負例の真の分布を表す(左側が正例、右側が負例である)。これらの分布から取り出されたサンプルを、バツ印(正例)と四角(負例)で表している。図から明らかなように、正例がminority classである。さらに、識別境界を と表し、その左側の領域を , 右側の領域を と記す。
ここで、理想的な境界は、真の分布から とわかる。しかしながら、サンプルから(例えばマージン最大化で)学習された境界は、点線で示された のようにバイアスがかかってしまう。
バイアスが発生する条件
次に、このようなバイアスが発生する条件を考える。
データセットに含まれる正例の集合を , 負例の集合を とする。データセット で学習したときの経験損失 は、偽陰性と偽陽性のコスト(ペナルティ)をそれぞれ とすると、
となる。要は、偽陰性の数×コストと、偽陽性の数×コストの和である。このとき、バイアスが生じる必要十分条件は、次のように書ける。
すなわち、理想的な境界 の右側にあるすべてのどんな境界よりも、経験損失を小さくする境界が左側に存在するとき、バイアスが生じると言っている。
このようにバイアスが発生する、すなわち が存在する条件を考える。正例と負例の真の分布をそれぞれ とし、prevalence(母集団における正例の割合)を とすると、
のとき、 が存在しうる。
バイアスを低減するためのアンダーサンプリング、およびbagging
上式を成立しにくくするためには、とすればよい。すなわち、majority classをアンダーサンプリングし、クラス間のデータ数を揃えればよい。
アンダーサンプリングはバイアスを低減できる一方で、モデルのvarianceは増えてしまう(学習される識別境界が、ランダムサンプリングによってばらつくことを言っている)。このvarianceを抑えるために、baggingするのがよい。
コストの調整やオーバーサンプリング
コストの調整
不均衡データに対する対処法として、偽陰性や偽陽性のコストに重みをつける手法が知られている。しかしながら、このような重み付きコストが効果を発揮しにくい場合がある。
いま、 (同じ重み)として、ある境界 が学習できたとする。ここで、 を 倍することを考える。このコスト増加によって境界 が動くのは、 が1つ以上の偽陰性をもたらす場合だけである。このような偽陰性のデータが無いとき、 にかかわらず、 は既に損失関数を最小化している。なお、 を動かすような偽陰性が観測される確率は次のように書ける。
上式より、以下のような場合に の増加が を動かす、すなわちバイアスの低減に寄与しにくいことがわかる。
- prevalence が低い場合(正例の割合が小さい場合)
- データセットの規模が小さい場合(データ数 が少ない場合)
また、 も寄与を左右する。具体的には、理想的な境界 の周辺で が密である場合に、コストの調整はバイアス低減に寄与しやすい。
オーバーサンプリング (SMOTE)
重み付きコストの他に、SMOTEのようなオーバーサンプリングに基づく手法も知られている。SMOTEでは、minority classのデータ同士で近いものの間に新しいデータを内挿することで、データ数を増やす。したがって、SMOTEで新たに生成されるデータは、既に存在するminorityなデータの凸包 (convex hull) の外側に現れることはない。これより、SMOTEがバイアスの低減に効果を発揮するのは、コストを調整する手法が効果を発揮する場合と同様である。SMOTEによって新しく生成されたデータが境界 を動かすには、このデータが偽陰性とならなければいけない。
実験
論文ではシミュレーションデータや実際のデータセットで実験し、ここまで述べた理論の裏付けをしている。内容は省略。
関連トピック
予測確率のバイアス
アンダーサンプリングによって、分類器の予測確率にバイアスが生じてしまう。アプリケーションにて予測確率が重要な場合は、キャリブレーションすべきとのこと。
参考:ダウンサンプリングによる予測確率のバイアス - sola
DNN (Deep Neural Network) への適用
モデルがDNNの場合は、訓練や推論の時間的にもモデルの容量的にもbaggingを単純に適用するのは難しいことが多い。これに対して、ミニバッチ内でアンダーサンプリングを行うことで、似たような効果があるようだ。
参考:不均衡データ分類問題をDNNで解くときの under sampling + bagging 的なアプローチ - BASEプロダクトチームブログ
参考文献
- メモ Class Imbalance, Redux - Coda
- 冒頭の論文を非常に簡潔かつわかりやすくまとめている。
- 論文読んだ「Class Imbalance, Redux」 - Speaker Deck
- こちらもよくまとまっている。
- Class Imbalance, Redux
- 論文著者による発表または講義のためのスライドにようだ。これも図が多めでわかりやすい。
- 不均衡データをundersampling + baggingで補正すると汎化性能も確保できて良さそう - 渋谷駅前で働くデータサイエンティストのブログ
- Rによる実験コードおよび結果。