レコメンド指標でよく見るMAP@kとは


## 概要
- レコメンドでよく使われるメトリクスである**Mean Average Precision (MAP)**について解説する
- MAPについて説明する前にまず前提条件として**Precision@k (P@k)**、**Average Precision @k (AP@k)** についても説明する


## 問題設定
- 正解を予測して並べた5個 (k=5)のデータのうち何個正解できたかを考える
  - 例えば5個並べた商品のうち、実際にクリックされたのはどれだったか

- 以下の例だと1番目と4番目を正解したことになる
- これを評価するメトリクスを考えたい

<img width="180" alt="スクリーンショット 2022-02-17 0.27.56.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547532/9b0902cb-506e-809a-37ca-004723796111.png">

- 単純に5個中何個正解できたかを考えてみる (2/5)
- 　でも同じ「2個正解」でも「1、2番目が正解」と「4、5番目が正解」だったら前者のほうが良さそう
    - 　なぜならクリックされやすいものをできるだけ上位に出したいから

- 上位で正解するほど大きな値となるようなメトリクスを採用したい
- そこでよく用いられるのがMAP@kである   

## P@kとAP@k
- k番目までを見たときのprecisionをP@kと表現する
- 例えばP@1ならば1個中1個正解できているので1/1= 1
- P@4ならば4個中2個正解できているので2/4 = 0.5 といった感じ
- 先ほどの図に付け足してみる

<img width="300" alt="スクリーンショット 2022-02-17 14.28.35.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547532/fedfd947-e029-6fcb-0183-8873fddc18f7.png">

こんな感じ。
ここで正解 (=1)できた順位について、Pの平均を取ることを考える。
今回は1番目と4番目を考えるので、1+0.333.. = 1.333.. となる。
これを**Average Precision (AP)**という。

式で表すと以下のようになる。
ただし、APの計算においてはPは正解の場合のみ足し上げているのに注意。
上の図においてk=2,3,5のP=0と置くと考えればいい。

```math
\sum_{k=1}^K{P_{k}}
```

## MAP@k
- さて、全部でN個のデータがあるとする
- 上で計算したPやAPはそのうち一個のデータと考えることができる
- これをN個のデータで平均してあげたのが**MAP@k**になる

```math
\frac{1}{N} \sum_{i=1}^N \frac{1}{min(m_{i},K)}\sum_{k=1}^K{P_{i}(k)}
```
- この数式を見るとmin(m,k)で割っている箇所はなんだ？と思うだろう
- 上記の例だとk=5としていたが、kの数をどんどん増やしていけばMAPの値はどんどん大きくなってしまう
- なので、この効果を抑えるためにmin(m,k)で割っている
    - ここでmは正解の個数


### なぜminなのか
例えばm=1000だとする。
k=5, 10, 20...と増やしていくほどMAPの数は大きくなっていくだろう。
一方でm=3だとする。
この場合、正解は全部で3つしかないのでkの値をどんなに増やしていってもAPで計算される和はせいぜい3つだろう。
なのでこの二つのうちの小さい値であるmin(m,k)で割るというわけだ。

## Pythonで実装してみる

以下のような正解と予測があったとする。N=3, K=3である。

<img width="450" alt="スクリーンショット 2022-02-17 23.49.13.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547532/b5acc128-c58e-151f-6b61-dd6e4f035cf1.png">

実際にコードで挙動を確認してみよう。
コードは「Kaggleでかつデータ分析の技術」のgithubのものを参考にした。

- https://github.com/ghmagazine/kagglebook/blob/master/ch02/ch02-01-metrics.py

元のデータをListで定義。

```Python
import numpy as np
import pandas as pd

#クラスは4種類とする
K = 3
# 各レコードの真の値
y_true = [[1, 2], [4], [1, 2, 3, 4]]
# 各レコードに対する予測値 
# K=3なので、通常は各レコードにそれぞれ3個まで順位をつけて予測する
y_pred = [[1, 2, 4], [1, 4, 3], [1, 2, 3]]
```

AP@k、MAP@kをそれぞれapk(), mapk()で実装する。

```Python

# 各レコードごとのaverage precisionを計算する関数
# 1/min(m,K) * Σp
def apk(y_i_true, y_i_pred):
    # y_predがK以下の長さで、要素がすべて異なることが必要
    assert (len(y_i_pred) <= K)
    assert (len(np.unique(y_i_pred)) == len(y_i_pred))

    sum_precision = 0.0
    num_hits = 0.0

    for i, p in enumerate(y_i_pred):
        if p in y_i_true: # 正解の場合のみ足す
            num_hits += 1
            precision = num_hits / (i + 1)
            sum_precision += precision

    return sum_precision / min(len(y_i_true), K)


# MAP@K を計算する関数
def mapk(y_true, y_pred):
    return np.mean([apk(y_i_true, y_i_pred) for y_i_true, y_i_pred in zip(y_true, y_pred)])
```

出力してみる。
上の表と同じ値が出て来ればおっけー。

``` Python
# APの計算結果
print(apk(y_true[0], y_pred[0])) # 1.0
print(apk(y_true[1], y_pred[1])) # 0.5
print(apk(y_true[1], y_pred[1])) # 1.0

# MAP@K
print(mapk(y_true, y_pred))
# 0.833...
```

## まとめ
- MAP@kを使うことで、レコメンドなどの順番が重要な場合のメトリクスを計算できる。