【k-近傍法】scikit.learnのBallTreeを使ってみた！

# 【k-近傍法】scikit.learnのBallTreeを使ってみた！

＜目次＞
1.はじめに
2.k-近傍法とは
3.BallTreeの特徴
4.実装
5.参考にしたサイト・書籍

## 1.はじめに

kaggleの「Foursquare - Location Matching」という大会に取り組んでいく中で，k-近傍法のパッケージであるscikit.learnのBallTreeを使う機会があったため，学んだことや実装する場面・方法をご紹介していきたいと思います！

## 2.k-近傍法(kNN法)とは
<font color="MidnightBlue">
対象とするデータに最も近いデータをk個取ってきて，それらが最も多く所属するクラスに識別する方法．
</font>

![kNN法.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2627906/7b15f8cf-d447-7b8f-6b0a-f16aa15c4dd8.png)
　　　　　　　　　　　　　　　　　　　　図１

図１の場合だと，k=3の場合は対象のデータはクラス１に分類され，k=5の場合はクラス２に分類される．

※名前が似ているK-平均法(K-means)とは別物なので注意．
(K-平均法は,データの平均値を使ってK個のクラスタを作るクラスタリングの手法．)

## 3.BallTreeの特徴
<font color="MidnightBlue">
BallTreeとはあるデータ点の近傍を探すのに適したデータ構造のこと</font>

以下ではBallTreeの簡単な概観を図を用いて説明する．

図2ように平面上にデータが与えられた時を考える．
![スクリーンショット 2022-06-10 15.31.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2627906/aa05410d-cfca-87a9-ad1a-fd2a8969ce55.png)
　　　　　　　　　　　　　　　　　　　　図２

まずデータをaとbという円領域に分割する．(分割方法については[論文１](https://doi.org/10.48550/arXiv.1511.00628)を参照)
![スクリーンショット 2022-06-10 15.31.32.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2627906/5962da4c-a000-7ba7-e374-cac2565d9161.png)
　　　　　　　　　　　　　　　　　　　　図３

それを各円領域a,bでも繰り返していく．
![スクリーンショット 2022-06-10 15.31.42.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2627906/934ac9e6-7f62-1616-36ad-c5622a7bc889.png)
　　　　　　　　　　　　　　　　　　　　図４

分割し終わったものが図５のようになる．
![スクリーンショット 2022-06-10 15.31.58.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2627906/693e5673-180f-4528-9ad2-f813b187e47b.png)
　　　　　　　　　　　　　　　　　　　　図５

そして，図５からは図６のような木が得られることとなる．
![スクリーンショット 2022-06-10 15.32.12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2627906/06dd4853-1be4-d468-43be-e7fe24abc11f.png)
　　　　　　　　　　　　　　　　　　　　図６
このように円領域(Ball)をもとに木(Tree)を作るようなデータ構造であるため，BallTreeという名称になっている．
こうして得られた木と対象のデータqと円領域との距離を用いて，効率良く最近傍探索(最も近いデータを見つけること)や範囲探索(ある範囲内のデータを探すこと)を行うことができる．



## 4.実装
**目的**：以下のテストデータから，同じ場所を指しているid同士をmatchさせること
![スクリーンショット 2022-06-10 17.02.37.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2627906/e4a84ee8-d7dd-d571-f0de-855e4ff52e0c.png)

**指針**：BallTreeを用いたk-近傍法により各idと最も近い2点を出力し，その距離が基準以下であればidを出力する．(ここでは「name」「categories」「latitude」「longitude」という4つの特徴量を用いる)

```python
import numpy as np
import pandas as pd 
from sklearn.neighbors import BallTree
from tqdm import tqdm
```
```python
tree=BallTree(np.deg2rad(test_0[["latitude","longitude"]].values),metric='haversine')

#test_0はテストデータを指す
#np.deg2radで緯度と経度をまとめてラジアンに直している
#'haversine'は球面上の距離を求める方法
```
```python
#結果を格納するリスト
pois_out=[] 

#近傍数
n=min(20,len(test_0)) 

#マッチさせるidの最大数
max_poi=2

#最大距離
max_dist_cat = 0.00018
max_dist_name = 0.0018
max_dist = max(max_dist_cat, max_dist_name)

for i, row in tqdm(test_0.iterrows()):
    #2点の最近傍データをdist,indに出力
    dist, ind = tree.query(np.deg2rad(np.c_[row['latitude'], row['longitude']]), k = n)
    poi = []
    for d, j in zip(dist[0], ind[0]):
        if d <= max_dist_cat and row['categories'] != '__NAN__' and (row['categories'] in test_0.categories.iloc[j] or test_0.categories.iloc[j] in row['categories']):
            poi.append(test_0.id.iloc[j])
        elif d <= max_dist_name and row['name'] != '__NAN__' and (row['name'].lower() == test_0.name.iloc[j].lower()):
            poi.append(test_0.id.iloc[j])
        if d > max_dist or len(poi) >= max_poi:
            break

    if len(poi) == 0:
        pois_out.append(row['id'])
    else:
        pois_out.append(' '.join(poi))
```
得られたデータをtestデータに格納すると以下のようになった．
![スクリーンショット 2022-06-10 17.02.44.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2627906/205ac32e-4f41-3d7c-8315-2273a814641e.png)

与えられていたサンプルのデータと同じ結果になってしまいました．．．

今後はこれをどのように応用するかを考えていきたいと思います！

## 5.参考文献
- [はじめてのパターン認識](https://www.amazon.co.jp/%E3%81%AF%E3%81%98%E3%82%81%E3%81%A6%E3%81%AE%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3%E8%AA%8D%E8%AD%98-%E5%B9%B3%E4%BA%95-%E6%9C%89%E4%B8%89/dp/4627849710/ref=as_li_ss_tl?adgrpid=53626124112&dchild=1&gclid=Cj0KCQjwyPbzBRDsARIsAFh15Ja5-49w0azyD6rnjYYV57Xr4RUdGXuJG_EurJY39QzIi-OAkCne-kUaAlb1EALw_wcB&hvadid=338568184520&hvdev=c&hvlocphy=1009214&hvnetw=g&hvqmt=e&hvrand=7165555007750497788&hvtargid=kwd-335484816958&hydadcr=27264_11561110&jp-ad-ap=0&keywords=%E3%81%AF%E3%81%98%E3%82%81%E3%81%A6%E3%81%AE%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3%E8%AA%8D%E8%AD%98&qid=1585316375&sr=8-1&linkCode=sl1&tag=yoheifukuha06-22&linkId=df8a79b68021b143fdf4a661d1abc7dd&language=ja_JP)
- [Ball*-tree: Efficient spatial indexing for constrained nearest-neighbor search in metric spaces](https://doi.org/10.48550/arXiv.1511.00628)
- [sklearn.neighbors.BallTree](https://runebook.dev/ja/docs/scikit_learn/modules/generated/sklearn.neighbors.balltree)