pythonで、不均衡データを識別が難しいサンプルを残してundersamplingしたいときは、imbalanced-learnのNearMissを使う

# intro

分類タスクなどで、クラスごとのサンプル数が極端に偏っていることがあります。  
そういった場合、一つの方法としてresamplingを行うことがあります。

どちらかといえばoversamplingを使うことのケースが多いかと思うのですが、
以下のようにundersamplingを使いたいケースがありました。  

- 全部を使ってトレーニングするには、データが多すぎる。  
- 偏りが非常に大きいため、Majority classを大幅に減らしたい
- 線形で分けにくいケースがある
- Majority classのうち明らかに識別できそうなものを除いて、識別が難しいサンプルを残したい

例えば、異常検知系だとこういったケースもあるかと思います。  

pythonでこういったケースに簡単に対処するには、どうすればいいか調べたのでシェアいたします。

（なおundersamplingしたいのはMajority classのほうが多いかと思うので、
この記事の中では対象をMajority classサンプルとしています。）

# 方法

[imabalanced-learn.under_samplingのNearMiss](http://contrib.scikit-learn.org/imbalanced-learn/stable/generated/imblearn.under_sampling.NearMiss.html#imblearn.under_sampling.NearMiss)を使います。  
[imbalanced-learnのUndersamplingにはTomek’s linksなどcleaningベースのmethodもあります](http://contrib.scikit-learn.org/imbalanced-learn/stable/api.html)。  
しかしノイズなるかもしれないsampleや境界付近のサンプルを取り除く手法で、  
目的にはそぐわないのでここでは選びません。  

（図はすべてimbaanced-learnの公式サイトから引用）

# アルゴリズム
以下の手順で残すMajority classに属するサンプルを選びます。  

Minority classのサンプルはすべて残します。 

1. 事前にk-nearest neighborsにより、それぞれのサンプルの近傍にあるサンプルを計算しておきます。
2. heuristicルールを使って残すサンプルを選ぶ。ルールには3タイプあります。<br><br>

- NearMiss-1  
       Minority classのサンプルのうち近くにあるkサンプルからの平均距離が小さいMajority classのサンプルを残します。
    ![sphx_glr_plot_illustration_nearmiss_0011.png](
    http://contrib.scikit-learn.org/imbalanced-learn/stable/_images/sphx_glr_plot_illustration_nearmiss_0011.png)  
       そのため理想的な状況なら、境界近くにあるサンプルが残りやすくなります。  
       ただしMajority Classの領域の中にノイズとしてMinority Classのサンプルが含まれていると、  
      それらの近くのサンプルを選びやすくなります。  
       逆にMinority Classの領域の中にMajority Classのサンプルが含まれていても、それらは残りやすくなります。<br><br>
- NearMiss-2  
        1.とは逆に遠いkサンプルからの平均距離がもっとも小さいMajority classのサンプルを選びます。  
　　　　![sphx_glr_plot_illustration_nearmiss_0021.png](http://contrib.scikit-learn.org/imbalanced-learn/stable/_images/sphx_glr_plot_illustration_nearmiss_0021.png)  
        残ったsampleは境界に集中することはありませんが、それでもある領域に集中しやすいです。
        こちらもminority classに大きな外れ値が複数あると、それに引っ張られて残る領域に偏りができてしまいます。 
        逆にMajority class領域内に存在するMinority Classのサンプルには影響を受けにくくなります。 <br><br>
- NearMiss-3  
       minority classのそれぞれのサンプルから、それぞれM番目までの近さにあるMajority Classのサンプルを残します。  
       
![sphx_glr_plot_illustration_nearmiss_0031.png](http://contrib.scikit-learn.org/imbalanced-learn/stable/_images/sphx_glr_plot_illustration_nearmiss_0031.png)
       その絞り込まれたMajority Classのサンプルから、さらに自身の近傍にあるN個のminorityのclassからの平均距離が一番遠いものを残します。 
       他の２つよりノイズの影響を受けにくいようです。  

# 単純な例での比較
![example][a]
[a]:http://contrib.scikit-learn.org/imbalanced-learn/stable/_images/sphx_glr_plot_nearmiss_001.png

![example2](http://contrib.scikit-learn.org/imbalanced-learn/stable/_images/sphx_glr_plot_comparison_under_sampling_0031.png)

NearMiss-1とNeaMiss-2により残ったサンプルがMajority領域の一部に集中している一方で、 
NearMiss-3はばらけて分布しているのが分かるかと思います。  
       
# 性能

原著の論文では、医学論文のアブストから関連するproteinの名前のtagをつける分類タスク(ただし文章中の単語を分類)で
性能を比較しています。  
性能劣化が一番抑えられたのは、NearMiss-2でした。
なお原著ではrandom samplingとそんなに変わらなかったともあります。

# まとめ

pythonで識別の難しいサンプルを残しながらundersamplingをするなら、  
imbalanced-learnのNearMissを使うといいということが分かりました。

ただし結局どこまでいってもベースとなるk-nearest neighborが、
うまく機能する特徴量を探す必要があります。  
場合によってはrandom samplingの方がいいかもしれません。  


# 参考文献

- I. Mani, I. Zhang. “kNN approach to unbalanced data distributions: a case study involving information extraction,” In Proceedings of workshop on learning from imbalanced datasets, 2003 (**原著**)
- [3. Under-sampling — imbalanced-learn 0.3.0 documentation](http://contrib.scikit-learn.org/imbalanced-learn/stable/under_sampling.html#controlled-under-sampling)
- [Nearmiss 1 & 2 & 3 — imbalanced-learn 0.3.0 documentation](http://contrib.scikit-learn.org/imbalanced-learn/stable/auto_examples/under-sampling/plot_nearmiss.html#sphx-glr-auto-examples-under-sampling-plot-nearmiss-py)