Kaggle Masterに学ぶ実践的機械学習[Kaggle TalkingData Competition編]

Kaggleでは世界トップクラスのデータサイエンティストが集まり，しのぎを削りながら賞金を狙って日々データを分析しています．
これは意外と知られていないのですが，Kaggleはただ単にみんなが競争しているだけでなく，かなり活発なフォーラムがあり，そこでcompetitionが終わった時に優れた結果を残したmasterたちが自分の手法を紹介することが通例となっています．
この記事では，先日終了した[Kaggle TalkingData Competition](https://www.kaggle.com/c/talkingdata-adtracking-fraud-detection)で3000以上の参加者の中で特に優れた結果を残した一部の参加者の用いた手法とそこから学べることについて分析・紹介していきます．

# Competitionの趣旨
[Kaggle TalkingData Competition](https://www.kaggle.com/c/talkingdata-adtracking-fraud-detection)は大量のクリックデータを元にアプリがダウンロードされるかどうかを予測するという趣旨のcompetitionでした．

### 用いる特徴
実際に使用されたデータがどのようなものだったかを理解するためにはtrain.csvをのぞいて見るのが最も手っ取り早いです．

<img width="634" alt="スクリーンショット 2018-05-14 15.07.42.png" src="https://qiita-image-store.s3.amazonaws.com/0/132104/f2689248-f328-8c4a-2d8e-9374b1693d1e.png">

予測対象は`is_attributed`（appがダウンロードされたかどうかを表す0か1かの二値）なので，入力は5つのカテゴリー型の変数とクリック時間のみです．ここまでシンプルなデータセットはなかなかありませんが，このシンプルさこそがこのcompetitionの難しさです．

### データセットの特徴
重要な統計量

| 量 | 値 |
| --- | --- |
| 学習データの行数 | 184,903,890 |
| テストデータの行数 | 18,790,469 |
| `is_attributed`== 1の割合 | 0.2% |


特徴量が少ない代わりにデータ量はかなり多く，データセットがかなりアンバランスなことがわかります．データセットについてもっと詳しく知りたい人は以下のEDA（探索的データ分析）Kernelを見てみると良いでしょう：
[TalkingData EDA and Class Imbalance](https://www.kaggle.com/kailex/talkingdata-eda-and-class-imbalance)
[TalkingData EDA plus time patterns](https://www.kaggle.com/yuliagm/talkingdata-eda-plus-time-patterns/code)

データの期間は
学習データ：2017/11/6 14:32:21 - 2017/11/9 16:00:00
テストデータ：2017/11/10 04:00:00 - 2017/11/10  15:00:00 
でした．

### 評価
評価は識別性能の指標であるAUCが用いられました．

# 上位のsubmission
ありがたいことに，このcompetitionでは上位のユーザー自身による手法の紹介が非常に充実しています．この記事では上位6件の手法についてまとめていきます．以下，元のdiscussionへのリンクです：

[1位(LB: 0.98432)](https://www.kaggle.com/c/talkingdata-adtracking-fraud-detection/discussion/56475)
[2位(LB: 0.98413)](https://www.kaggle.com/c/talkingdata-adtracking-fraud-detection/discussion/56328)
[3位(LB: 0.98408)](https://www.kaggle.com/c/talkingdata-adtracking-fraud-detection/discussion/56262)
[4位(LB: 0.98402)](https://www.kaggle.com/c/talkingdata-adtracking-fraud-detection/discussion/56243)
[5位(LB: 0.98402)](https://www.kaggle.com/c/talkingdata-adtracking-fraud-detection/discussion/56406)
[6位(LB: 0.98351)](https://www.kaggle.com/c/talkingdata-adtracking-fraud-detection/discussion/56283)

# 手法のまとめ

## データの扱い
#### Train, Validation
基本的に全ての上位のsubmissionについて共通しているのが，11/9のデータを検証用データに使い，それ以前のデータを学習に回している点です．これは時系列データを扱う際の基本で，評価対象のテストデータが学習データの未来のデータの場合，検証も同様に学習データの未来のデータを用いるべきです．人によってはテストデータと同じ時間帯のデータのみを使ったというユーザーもいました．

#### Subsampling

驚くべきことに，上位2つのsubmissionは学習時に**全データを学習に使っていません**．1位と2位のsubmissionは負例（`is_attributed`が0のデータ）が非常に多い点に着目し，**負例をサンプリング**した上で学習を行なっています．1位のsubmissionは負例と正例の数が一緒になるようにサンプリングしているので，学習する時になんと負例の99％以上を捨てています．ただ，そのまま全てのデータを捨てるのは勿体無いので，5つの異なるモデルを学習し，それぞれのモデルについて異なる負例のsubsetを使っています．さらに，1位のsubmissionは11/6以前のデータを使わず，11/7以降のデータのみでパラメーターのチューニングや学習を行なっています．
こうして一度に学習に使うデータを大幅に削減することで学習時間とメモリ消費量を抑え，より多くの実験を回すとともにより多くの特徴量を使えるようにしています．

ただし，1位のsubmissionは振り返って，ニューラルネットについてはより多くの負例を用いて学習するべきだったのではないかと考察しています．単純に負例をサンプリングすれば良いというわけではなく，学習器の特性に合わせてデータの使用法を考える必要があるようです．


## モデル
上位6つのsubmissionは全て[lightGBM](https://github.com/Microsoft/LightGBM)（以下lgbm)かニューラルネットのいずれかまたは両方を用いていました．どのsubmissionもいくつかのモデルを学習した上でensembleしています．4位のsubmissionはstacking（いくつかのモデルの出力をさらに機械学習のモデルにかけて最終的な予測値を出す手法）を用いていましたが，他の手法はそこまで凝ったモデルの組み合わせ方をしていませんでした．
第3位のsubmissionは色々とニューラルネットの構造を工夫しようと試みていましたが，3位以外のsubmissionは簡単な3層のニューラルネットを使っているものが多く，モデルのレベルでの工夫は他のsubmissionではほとんど記述されていませんでした．つまり，このcompetitionの鍵となったのはデータの扱いと特徴量エンジニアリングだったということです．


## 特徴量エンジニアリング

元データが非常に簡素な分全てのsubmissionでかなりの特徴量エンジニアリングが行われていました．

### 前処理
lgbmは欠損値もカテゴリー型の変数もそのまま入力として受け付け，特徴量のスケールに影響されないので前処理はほとんど必要ありません．
ニューラルネットを含む勾配を用いて学習するアルゴリズムではそうはいかないので，前処理として特徴量を正規化し，欠損値を補完しています．欠損値の補完は時間ベースの特徴以外は平均値を用いていました．時間ベースの特徴については後ほど詳しく述べます．

### Categories
多くのsubmissionはもともとあるcategoricalな特徴である，ip, os, app, channel, deviceをそのまま用いていました．特にアプリを表すappはかなり重要で，非常にダウンロード率が高いアプリも中にはあったため，全てのsubmissionで用いられていました．

### Aggregated Features
これはcompetitionの開催期間早々から行われていた特徴抽出法で，様々なカテゴリーでグループ化し，count,cumulative count, unique countなどの集計関数を使って特徴量を作成していました．例えば「同じip, os, deviceの総クリック数」が「各ipがクリックしたappの種類」などといった特徴量が作成されていました．どのようなグループに対してどのような特徴が用いられたかは基本的にsubmissionによってバラバラでした．
1位のsubmissionは様々なグループについて直近1~6時間の間のクリック数というのも特徴として用いていました．
なお，1位と2位のsubmissionはデータをサンプリングしたと書きましたが，このグループベースの特徴量を計算するときは全データを用いて計算されています．幸いこれらの特徴量は一度計算すれば良いので，全データで特徴量を作成してもサンプリングすれば学習時間は少なくて済みます．

### Time delta
ほとんどのsubmissionが様々なグループ毎の，直前・直後のクリックからの経過時間を特徴量として用いていました．
具体的には，例えば

| ip | os | click_time | 
| --- | --- | --- | 
| 1 | 13 |14:01|
| 2 | 13 |14:02|
| 1 | 15 |14:03|
| 1 | 13 |14:04|
| 1 | 15 |14:05|
| 2 | 13 |14:06|

というデータがあった場合，ipごとにグループ化して考えた場合直前のクリックからの経過時間は

| ip | os | click_time | time_delta |
| --- | --- | --- | --- |
| 1 | 13 |14:01| - |
| 2 | 13 |14:02| - |
| 1 | 15 |14:03| 2 |
| 1 | 13 |14:04| 1 |
| 1 | 15 |14:05| 1 |
| 2 | 13 |14:06| 4 |

となりますし，ip, osごとにグループ化して考えた場合は

| ip | os | click_time | time_delta |
| --- | --- | --- | --- |
| 1 | 13 |14:01| - |
| 2 | 13 |14:02| - |
| 1 | 15 |14:03| - |
| 1 | 13 |14:04| 3 |
| 1 | 15 |14:05| 2 |
| 2 | 13 |14:06| 4 |

となります．
5位のsubmissionは2個前，2個後のクリックからの経過時間も特徴として用いていました．

ちなみにあるカテゴリーの直前のエントリーを取得する処理は

```python
df.groupby(categories).shift(-1)
```

で行えます（ここで`df`は`Pandas.DataFrame`であることを想定）．


### Categorical Embedding
これは1位と6位が用いていた手法で，それぞれのカテゴリーを意味のある潜在空間内のベクトルに落とし込むものです．1位と6位が用いた手法は基本的にはかなり似ていて

①2つのカテゴリーを選び，それらのカテゴリー同士の共起回数（またはそのlog）を要素とする行列を計算する
（難しく聞こえますが，これは自然言語処理におけるterm document matrixの計算と何も変わりません）
②その行列をSVD・NMF・LDAで分解する

というものでした．ただし，6位の手法は3つのカテゴリーの組み合わせについてfactorization machineを使って特徴を計算するということも行なっています．


### Time Lagged Features
1位，5位，6位のsubmissionはカテゴリーごとの前日または以前までのアプリのダウンロード率（`is_attributed` = 1の割合）を特徴として用いていました．ダウンロード率などの情報をそのまま用いるのは一見邪道に見えますが，過去のデータを元に計算しているので何も問題はありません．


### Data Leakage
データリークとは，本来主催者が（おそらく）期待していない特徴が図らずも予測性能を持ってしまう現象のことです．例えば人工的にデータを作る際に誤ってipと出力値の間に相関をもたせてしまう，などといったことです．
[他の](https://www.kaggle.com/c/outbrain-click-prediction)[Competition](https://www.kaggle.com/c/quora-question-pairs)ほど大きなリークではないものの，このcompetitionでも若干のリークがありました．というのも，用いられたデータセット内で全く同じ`ip`, `os`, `device`, `app`, `channel`, `click_time`にも関わらず`is_attributed`の値が異なるデータがあり，このデータの扱いによって（わずかではあるものの）性能に差が生じてしまいました．
4位のsubmissionは`is_attributed` = 1のデータが最後になるようにソートした上で特徴抽出することで問題を解決していました．6位のユーザーはデータリークを学習できるように特徴を追加していました．
ちなみにこの問題に対する分析を[別のユーザー](https://www.kaggle.com/c/talkingdata-adtracking-fraud-detection/discussion/56268)がcompetition終了後にポストしているので，詳しく知りたい人は是非そこの議論も見て見てください．

### その他
5位のsubmissionはこれ以外にも様々な特徴量を作成しており，いくつか例をあげると
- `ip`毎のクリック数が多い`app`,`device`,などtop 5
- 同じ`time_delta`の値をもつデータのカウント（よく出現する`time_delta`の値があったことに対する対処）

などがありました（一部は説明が理解できなかったのでここでは述べません）．

# まとめ・学び
これほどシンプルなデータセットでも工夫次第でこれだけの特徴量を生み出し，ちゃんと他の人より高性能な学習器が作れるということに感心した，そんなcompetitionでした．
以下，特に汎用性が高そう・重要だと思った点についてまとめます：

### データ処理
- 時系列データでテストデータが未来にある場合は検証データも学習データの未来に取るべき
- lgbmのようなツリーベースの手法ではデータが単純に多ければ多いほどいいというわけではない（ただしニューラルネットの場合は基本的にはデータ量は多い方が良い，少なくともlgbmよりは多くのデータが必要）
- 実験回数をなるべく多くとれるように，データはsubsampleすると良い

### 特徴量エンジニアリング
- カテゴリー型の変数はグループ毎に特徴量を作成するのが基本
- グループ毎に作成できる特徴量の種類は膨大で，以下のようなものが挙げられる
    - count, unique count, cumulative count
    - 直前のデータからの経過時間
    - 過去の目的変数の平均値
- 行列分解を用いてカテゴリー型の変数のベクトル表現を得て，それを特徴として用いることができる