Python: Target Encoding のやり方について

データ分析コンペでは Target Encoding という特徴量抽出の手法が用いられることがある。 Target Encoding では、一般的に説明変数に含まれるカテゴリ変数と目的変数を元にして特徴量を作り出す。データによっては強力な反面、目的変数をエンコードに用いるためリークも生じやすく扱いが難しい。

今回は、そんな Target Encoding のやり方にもいくつか種類があることを知ったので紹介してみる。元ネタは CatBoost の論文から。

CatBoost: unbiased boosting with categorical features (PDF)

使った環境は次の通り。

$ sw_vers
ProductName:    Mac OS X
ProductVersion: 10.14.6
BuildVersion:   18G103
$ python -V            
Python 3.7.4

Target Encoding の基本的な考え方

問題を単純にするため、このエントリでは二値分類問題に限定して考える。二値分類問題における Target Encoding では、一般的に説明変数に含まれるカテゴリ変数ごとの、目的変数の平均値を特徴量として用いる。カテゴリ変数は、複数の組み合わせになることもある。また、平均値を用いる手法は、より限定的に Target Mean Encoding と呼称することもある。 Target Encoding 自体は目的変数を用いた特徴量抽出の手法全般に対する呼称と理解してるけど、一般的には Target Mean Encoding を指すことが多い気がする。

Target Encoding の手法について

前述した CatBoost の論文には、Targe Encoding の手法として以下の 4 つが紹介されている。手法の名前に共通で含まれる TS は Target Statistics の略となっている。

Greedy TS
Leave-one-out TS
Holdout TS
Ordered TS

上記の中で、Greedy TS と Leave-one-out TS はリークが生じるため使うべきではない。そのため、一般的には Holdout TS が用いられている。 Ordered TS は CatBoost の論文の中で提案されている手法で、リークが生じにくいとされている。

下準備

ここからは実際に Python のコードを使って Target Encoding の手法について見ていく。

その前に、下準備として必要なパッケージをインストールしておく。

$ pip install pandas

Python のインタプリタを起動する。

$ python

サンプル用のデータフレームを用意する。色々なフルーツと、それが美味しいかを示しているとでも考えてもらえれば。

>>> import pandas as pd
>>> 
>>> data = {
...     'category': ['apple', 'apple',
...                  'banana', 'banana', 'banana',
...                  'cherry', 'cherry', 'cherry', 'cherry',
...                  'durian'],
...     'label': [0, 1,
...               0, 0, 1,
...               0, 1, 1, 1,
...               1],
... }

>>> df = pd.DataFrame(data=data)
>>> df
  category  label
0    apple      0
1    apple      1
2   banana      0
3   banana      0
4   banana      1
5   cherry      0
6   cherry      1
7   cherry      1
8   cherry      1
9   durian      1

上記を見ると、なんとなく cherry は美味しい割合が高そうで banana は低そうと感じるはず。この、ラベルの割合が高そう低そう、というのが実は正に Target Encoding の考え方になる。

Greedy TS (使っちゃダメ)

まず最初に示すのは Greedy TS から。最初に断っておくと、この手法はリークを起こすため使ってはいけない。

Greedy TS では、データ全体で計算したカテゴリ変数ごとの目的変数の平均値がそのまま特徴量になる。つまり、以下のようにカテゴリごとに集計した平均値となる。

>>> ts = df.groupby('category', as_index=False).agg({'label': 'mean'})
>>> ts
  category     label
0    apple  0.500000
1   banana  0.333333
2   cherry  0.750000
3   durian  1.000000

元のデータに特徴量を追加する場合、次のようになる。基本的に、同じカテゴリは同じ特徴量になる。

>>> pd.merge(df, ts, on='category', right_index=True)
  category  label_x   label_y
0    apple        0  0.500000
1    apple        1  0.500000
2   banana        0  0.333333
3   banana        0  0.333333
4   banana        1  0.333333
5   cherry        0  0.750000
6   cherry        1  0.750000
7   cherry        1  0.750000
8   cherry        1  0.750000
9   durian        1  1.000000

上記の Greedy TS は特徴量を付与するデータ自体も集計対象としている。そのため、本来は使えない目的変数の情報が説明変数に漏れてしまっている。結果として、Local CV で性能を高く見積もってしまうことになる。

Leave-one-out TS (使っちゃダメ)

続いては Leave-one-out TS という手法。一見すると上手くいきそうだけど、このやり方もリークが生じるため使ってはいけない。

まず、Leave-one-out TS の基本的な考え方は、特徴量を付与する対象となるデータをピンポイントで除いて集計するというもの。計算方法にはいくつかやり方があるけど、ここではあらかじめ集計した値から付与対象のデータを取り除く方法を取る。

まずはカテゴリ変数ごとの目的変数の合計とカウントを計算しておく。

>>> agg_df = df.groupby('category').agg({'label': ['sum', 'count']})

上記の集計から、付与する対象のデータだけを除外して計算した平均値を計算する関数を定義する。

>>> def loo_ts(row):
...     # 処理対象の集計を取り出す
...     group_ts = agg_df.loc[row.category]
...     # 集計した合計値から自身の目的変数を除く
...     loo_sum = group_ts.loc[('label', 'sum')] - row.label
...     # 集計したカウントから自身の存在を除く
...     loo_count = group_ts.loc[('label', 'count')] - 1
...     # 合計をカウントで割って平均を取り出す
...     return loo_sum / loo_count
...

上記の関数を各行に適用して得られる結果が次の通り。これが Leave-one-out TS の特徴量となる。先ほどの結果と違って同じカテゴリの中でも特徴量の値が異なっていることがわかる。

>>> ts = df.apply(loo_ts, axis=1)
__main__:9: RuntimeWarning: invalid value encountered in long_scalars
>>> ts
0    1.000000
1    0.000000
2    0.500000
3    0.500000
4    0.000000
5    1.000000
6    0.666667
7    0.666667
8    0.666667
9         NaN
dtype: float64

このやり方のまずさは元の説明変数と結合してみるとわかる。以下で、例えば apple のカテゴリの結果は目的変数を反転させた結果となっていることがわかる。もちろん、これは極端なパターンだけど、これでは目的変数をそのまま説明変数に埋め込んでいるのと変わりがない。

>>> ts.name = 'loo_ts'
>>> df.join(ts)
  category  label    loo_ts
0    apple      0  1.000000
1    apple      1  0.000000
2   banana      0  0.500000
3   banana      0  0.500000
4   banana      1  0.000000
5   cherry      0  1.000000
6   cherry      1  0.666667
7   cherry      1  0.666667
8   cherry      1  0.666667
9   durian      1       NaN

ちなみに durian の NaN は Leave-one-out しようにも、同じカテゴリのデータがないために生じている。これを回避するには、分母 (と場合によっては分子にも) に定数を加える Smoothing をした方が良い。以下では分かりやすさのために足して引いてしている。

>>> def loo_ts(row):
...     # 処理対象の集計を取り出す
...     group_ts = agg_df.loc[row.category]
...     # 集計した合計値から自身の目的変数を除く
...     loo_sum = group_ts.loc[('label', 'sum')] - row.label
...     # 集計したカウントから自身の存在を除く
...     loo_count = group_ts.loc[('label', 'count')] - 1
...     # 合計をカウントで割って平均を取り出す
...     return loo_sum / (loo_count + 1)  # smoothing
... 
>>> df.apply(loo_ts, axis=1)
0    0.500000
1    0.000000
2    0.333333
3    0.333333
4    0.000000
5    0.750000
6    0.500000
7    0.500000
8    0.500000
9    0.000000
dtype: float64

今度は NaN が登場しない。

Holdout TS

続いて紹介するのが、現在一般的な Target Encoding として用いられている Holdout TS という手法。より厳密には Holdout TS を交差させて全データに適用したもの。 Holdout TS は、前述した 2 つの手法よりもリークが起こりにくいとされる (起こらないわけではない)。

Holdout TS では、Leave-one-out TS ではひとつだけだった除外データを増やす。つまり、特定の割合でデータを学習用とホールドアウトに分割することになる。その上で、学習用のデータを用いて計算した平均値をホールドアウトの特徴量として使う。これを全データに対して k-Fold CV の要領で適用すれば良い。

計算方法は、Leave-one-out TS と同じようにあらかじめ集計した値から除外対象を引くやり方にしてみる。まずは単純に合計とカウントを集計する。

>>> agg_df = df.groupby('category').agg({'label': ['sum', 'count']})

データを分割するための KFold オブジェクトを用意する。

>>> from sklearn.model_selection import StratifiedKFold
>>> 
>>> folds = StratifiedKFold(n_splits=3,
...                         shuffle=True,
...                         random_state=42)

生成した特徴量を入れる Series オブジェクトを用意しておく。

>>> import numpy as np
>>> ts = pd.Series(np.empty(df.shape[0]), index=df.index)

そして、次のようにしてホールドアウト分を全体から除外した上で平均値を計算する。

>>> for _, holdout_idx in folds.split(df, df.label):
...     # ホールドアウトする行を取り出す
...     holdout_df = df.iloc[holdout_idx]
...     # ホールドアウトしたデータで合計とカウントを計算する
...     holdout_agg_df = holdout_df.groupby('category').agg({'label': ['sum', 'count']})
...     # 全体の集計からホールドアウトした分を引く
...     train_agg_df = agg_df - holdout_agg_df
...     # ホールドアウトしたデータの平均値を計算していく
...     oof_ts = holdout_df.apply(lambda row: train_agg_df.loc[row.category][('label', 'sum')] \
...                                           / train_agg_df.loc[row.category][('label', 'count')], axis=1)
...     # 生成した特徴量を記録する
...     ts[oof_ts.index] = oof_ts
... 
__main__:10: RuntimeWarning: invalid value encountered in double_scalars

生成された特徴量は次の通り。先ほどの Leave-one-out TS とは違って目的変数を単純に反転したものとはなっていない。

>>> ts.name = 'holdout_ts'
>>> df.join(ts)
  category  label  holdout_ts
0    apple      0         NaN
1    apple      1         NaN
2   banana      0         0.0
3   banana      0         0.5
4   banana      1         0.0
5   cherry      0         1.0
6   cherry      1         0.5
7   cherry      1         1.0
8   cherry      1         0.5
9   durian      1         NaN

しかし、上記では NaN となっている値が多いことに気づく。これは、データの分割方法によっては学習データが少なくなって平均値が計算できなくなってしまうため。

Holdout TS でも、やはり Smoothing はした方が良さそう。

>>> for _, holdout_idx in folds.split(df, df.label):
...     # ホールドアウトする行を取り出す
...     holdout_df = df.iloc[holdout_idx]
...     # ホールドアウトしたデータで合計とカウントを計算する
...     holdout_agg_df = holdout_df.groupby('category').agg({'label': ['sum', 'count']})
...     # 全体の集計からホールドアウトした分を引く
...     train_agg_df = agg_df - holdout_agg_df
...     # ホールドアウトしたデータの平均値を計算していく
...     oof_ts = holdout_df.apply(lambda row: train_agg_df.loc[row.category][('label', 'sum')] \
...                                           / (train_agg_df.loc[row.category][('label', 'count')] + 1), axis=1)
...     # 生成した特徴量を記録する
...     ts[oof_ts.index] = oof_ts
... 
>>> ts.name = 'holdout_ts'
>>> df.join(ts)
  category  label  holdout_ts
0    apple      0    0.000000
1    apple      1    0.000000
2   banana      0    0.000000
3   banana      0    0.333333
4   banana      1    0.000000
5   cherry      0    0.666667
6   cherry      1    0.333333
7   cherry      1    0.666667
8   cherry      1    0.333333
9   durian      1    0.000000

Ordered TS

最後に紹介するのが CatBoost の論文で提案されている Ordered TS というやり方。このやり方は Holdout TS よりも、さらにリークを起こしにくいらしい。

Ordered TS の基本的な考え方はオンライン学習に着想を得たもの。ある行の特徴量として平均値を計算するのに、その時点で過去に登場したデータの集計を用いる。ようするにストリーミング的にデータが次々と到着する場面で、到着したデータには過去の平均値を付与していくのをイメージすると良い。データが到着する毎に、過去のデータ (History) も増えて平均値も更新されていく。

しかし、上記の考え方はデータに時系列の要素が含まれないことも多い点が問題となる。そこで、Ordered TS では artificial "time" (人工的な時間) という概念を持ち込む。これは、ようするにデータが登場する順番を人工的に定義したもの。典型的には、データのインデックス番号をランダムにシャッフルして使えば良い。

説明が長くなってもあれなのでコードに移る。まずはデータフレームのインデックスを元に artificial "time" を定義する。

>>> np.random.seed(42)
>>> artificial_time = np.random.permutation(df.index)
>>> artificial_time
array([8, 1, 5, 0, 7, 2, 9, 4, 3, 6])

続いて、グループ化するのに使うカラムとターゲットのカラム、Smoothing の有無について変数を用意しておく。

>>> group_col = 'category'
>>> target_col = 'label'
>>> smooth = False

ここではターゲットの値が NaN になっているものはテストデータ (ターゲットの値を推論したいデータ) と仮定する。そのまま単純に平均値を計算すると NaN になってしまう。そこで、ターゲットの積算値と件数を学習データのみで構成するためにカラムを用意する。

>>> counter_name = 'Train'
>>> assert counter_name not in df.columns, f'Oops! need to rename {counter_name} column'
>>> df[counter_name] = ~df[target_col].isnull()

次に、出現時間のカラムを使ってソートしてデータをひとつずつずらす。これは、計算対象のデータに、自身のターゲットの値を計算に含めるとリークしてしまうため。また、シフトするとグループ化に使ったカラムが消えてしまうため埋め直す。

>>> sorted_indices = np.argsort(artificial_time)
>>> df_shifted = df.iloc[sorted_indices].groupby(group_col).shift(1)
>>> df_shifted[group_col] = df.iloc[sorted_indices][group_col]

シフトすると最初のデータが NaN になるので値を埋めておく。これがないと後続の cumsum が計算できない。

>>> df_shifted[target_col].fillna(value=0, inplace=True)
>>> df_shifted[counter_name].fillna(value=False, inplace=True)

あとはターゲットの積算値と、学習データの件数から尤度を計算するだけ。

>>> gdf = df_shifted.groupby(group_col)
>>> agg_df = gdf.agg({target_col: 'cumsum', counter_name: 'cumsum'})
>>> ordered_ts = agg_df[target_col] / (agg_df[counter_name] + int(smooth))

この値は artificial "time" 順に並んでいるため、元に戻すとこうなる。その時点での過去 (History) の平均値が入っている。

>>> ordered_ts[df.index]
0    1.000000
1         NaN
2    0.000000
3         NaN
4    0.000000
5         NaN
6    0.666667
7    0.500000
8    0.000000
9         NaN
dtype: float64

元のデータを結合してみよう。

>>> df.join(ordered_ts[df.index].rename('ordered-ts'))
  category  label  Train  ordered-ts
0    apple      0   True    1.000000
1    apple      1   True         NaN
2   banana      0   True    0.000000
3   banana      0   True         NaN
4   banana      1   True    0.000000
5   cherry      0   True         NaN
6   cherry      1   True    0.666667
7   cherry      1   True    0.500000
8   cherry      1   True    0.000000
9   durian      1   True         NaN