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

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

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

github.com

アルゴリズムの概要
Pythonでの例
iris での例
追記20180624
- 実装の修正
- はてなホットエントリ入り

アルゴリズムの概要

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

とあるクラスに属する訓練データの中の第1近傍までの距離を1つ目の特徴量とする
とあるクラスに属する訓練データの中の第2近傍までの距離の和を2つ目の特徴量とする
とあるクラスに属する訓練データの中の第3近傍までの距離の和を3つ目の特徴量とする
以上を $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, folds = 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から特徴量を抽出する実装となっていました。ご指摘いただき、ありがとうございます。