u++の備忘録

KaggleのWinner solutionにもなった「K近傍を用いた特徴量抽出」のPython実装

今回は、KaggleのWinner solutionにもなった「K近傍を用いた特徴量抽出」を紹介します。

Rでの実装は公開されていますが、Pythonでの実装は確認できなかったので、自前のPython実装も公開しています。

github.com

アルゴリズムの概要

近傍数を k、分類するクラス数を cとした場合に、アルゴリズム k \times c個の特徴量を生成します。生成される特徴量は下記のように、観測値と各クラス内の k最近傍点との間の距離から計算されます。

  1. とあるクラスに属する訓練データの中の第1近傍までの距離を1つ目の特徴量とする
  2. とあるクラスに属する訓練データの中の第2近傍までの距離の和を2つ目の特徴量とする
  3. とあるクラスに属する訓練データの中の第3近傍までの距離の和を3つ目の特徴量とする
  4. 以上を kに関して繰り返す

上記の手順を全てのクラスについて繰り返すことで、 k \times c個の特徴量が生成されます。実際は過学習を避けるため、n-foldで分割して特徴量を生成しています。

Pythonでの例

Notebook version can be seen [here](https://github.com/upura/knnFeat/blob/master/demo.ipynb).

可視化のためのパッケージ読み込み
import numpy as np
%matplotlib inline
import matplotlib.pyplot as plt
サンプルデータの生成
x0 = np.random.rand(500) - 0.5
x1 = np.random.rand(500) - 0.5
X = np.array(list(zip(x0, x1)))
y = np.array([1 if i0 * i1 > 0 else 0 for (i0, i1)  in list(zip(x0, x1))])
可視化

f:id:upura:20180623164523p:plain

K近傍を用いた特徴量抽出
from knnFeat import knnExtract
newX = knnExtract(X, y, k = 1, holds = 5)
可視化

f:id:upura:20180624233211p:plain

ほぼ線形分離可能な特徴量が抽出できています。

iris での例

定番のiris データセットでも、うまく分離できています(irisは3クラス分類なので特徴は3つ得られていますが、うち2つだけでプロットしています)。

from sklearn import datasets
iris = datasets.load_iris()
y = iris.target
X = iris.data

f:id:upura:20180623184422p:plain
f:id:upura:20180624233235p:plain

追記20180624

実装の修正

初回公開時、n-foldで分割においてX_testではなくX_trainから特徴量を抽出する実装となっていました。ご指摘いただき、ありがとうございます。