k-NN Feature Extraction を試す

機械学習について色々と調べていたら特徴量エンジニアリングの 1 つとして k-NN Feature Extraction という手法がある事を知ったので試してみた。考え方としては Python: k-NN Feature Extraction について が分かり易く説明してくれていたので参考にさせてもらった。

簡易版の実装は https://github.com/you1025/knn_feature_extraction/blob/master/knn_feature_extraction.R で参照できるとして、以下ではいくつかのサンプルデータに対して当該処理で作成される特徴量がどのようなものとなるのかを確認していく。

サンプル 1: 4 つの正方形(2 クラス)

例としてネットによく挙がってるデータで試してみる。
元データは線形分離が出来ない典型的なデータであり、何らかの非線形変換なしには線形分離は不可能である。そこで k-NN Feature Extraction を実施して新しい特徴量で分布を可視化してみる。

library(tidyverse)

# データの定義
N <- 500
df.data <- tibble(
  x = runif(N, min = -1, max = 1),
  y = runif(N, min = -1, max = 1),
  class = dplyr::if_else(x * y > 0, "a", "b") %>% factor()
)

# 可視化(変換前)
df.data %>%
  ggplot(aes(x, y)) +
    geom_point(aes(colour = class), show.legend = F)

# 特徴量の追加
df.data.knn_d <- df.data %>%
  add_knn_d_columns(col_class = class, k = 1)

# 可視化(変換後)
df.data.knn_d %>%
  ggplot(aes(class_a_1, class_b_1)) +
    geom_point(aes(colour = class), show.legend = F)

変換前

変換後

かなり良い感じに分離できそうなデータに変換されている事が分かる。

サンプル 2: 単位円(2 クラス)

単位円盤上に分布する　π / 3 ごとに 2 つのクラスが切り替わるデータで試してみる。
こちらも単純な直線では分離できないデータである。

library(tidyverse)

# データの定義
N <- 500
df.data <- tibble(
  r = runif(N, 0, 1),
  theta = runif(N, 0, 2 * pi),
  x = r * cos(theta),
  y = r * sin(theta),
  class = cut(theta, breaks = seq(0, 2 * pi, length.out = 7), labels = rep(letters[1:2], 3))
) %>%
  dplyr::select(x, y, class)

# 可視化(変換前)
df.data %>%
  ggplot(aes(x, y)) +
    geom_point(aes(colour = class), show.legend = F)

# 特徴量の追加
df.data.knn_d <- df.data %>%
  add_knn_d_columns(class)

# 可視化(変換後)
df.data.knn_d %>%
  ggplot(aes(class_a_1, class_b_1)) +
  geom_point(aes(colour = class), show.legend = F)

変換前

変換後

こちらもサンプル 1 と同様にかなりきれいに分離可能なデータに変換された。

サンプル 3: 単位円(3 クラス)

単位円盤上に分布する π / 3 ごとに 3 つのクラスが切り替わるデータで試してみる。
こちらはサンプル 2 のデータの 3 クラス版となる。

library(tidyverse)

# データの定義
N <- 500
df.data <- tibble(
  r = runif(N, 0, 1),
  theta = runif(N, 0, 2 * pi),
  x = r * cos(theta),
  y = r * sin(theta),
  class = cut(theta, breaks = seq(0, 2 * pi, length.out = 7), labels = rep(letters[1:3], 2))
) %>%
  dplyr::select(x, y, class)

# 可視化(変換前)
df.data %>%
  ggplot(aes(x, y)) +
  geom_point(aes(colour = class), show.legend = F)

# 特徴量の追加
df.data.knn_d <- df.data %>%
  add_knn_d_columns(col_class = class)

# 可視化(変換後)
df.data.knn_d %>%
  ggplot(aes(class_a_1, class_b_1)) +
  geom_point(aes(colour = class), show.legend = F)

変換前

変換後

クラス a までの距離およびクラス b までの距離の 2 次元で表示したところ、クラス c が平面全体に散らばってしまいクラス a と b の分離には良さそうだがクラス c を含めた線形分離は厳しい事が分かる。そこで 3 次元でのマッピングを試してみる。

plotly::plot_ly(
  x = df.data.knn_d$class_a_1,
  y = df.data.knn_d$class_b_1,
  z = df.data.knn_d$class_c_1,
  type = "scatter3d",
  mode = "markers",
  color = df.data.knn_d$class,
  size = 0
)

画像だと少し分かりづらいかもしれないがクラス a / b / c の各点がそれぞれ y-z 平面 / z-x 平面 / x-y 平面 の上に張り付いており、線形分離が可能な分布となっている。

サンプル 4: 長方形(2 クラス)

比率が 1:1000 の長方形で試してみる。
こちらはサンプル 1 と類似しているデータだが x と y のスケールが 大きく異なっており、この事がどのように影響するのかを確認していく。

library(tidyverse)

# データの定義
N <- 500
df.data <- tibble(
  x = runif(N, -1, 1),
  y = runif(N, -1000, 1000),
  class = dplyr::if_else(x * y > 0, "a", "b") %>% factor()
)

# 可視化(変換前)
df.data %>%
  ggplot(aes(x, y)) +
    geom_point(aes(colour = class), show.legend = F) +
    scale_y_continuous(labels = scales::comma)

# 特徴量の追加
df.data.knn_d <- df.data %>%
  add_knn_d_columns(class)

# 可視化(変換後)
df.data.knn_d %>%
  ggplot(aes(class_a_1, class_b_1)) +
    geom_point(aes(colour = class), show.legend = F)

変換前

変換後

上記は全く分離できそうな雰囲気が無い。
k-means などのユークリッド距離(L2距離)を用いるアルゴリズムと同様に、あまりにもスケールの異なるデータでは数値の大きいデータに引っ張られてまともに処理が出来ない事が原因だと思われる。
仮にサンプル 1 において x, y が共に m(メートル) 単位のデータでありサンプル 4 においては y の単位を cm(センチメートル) に変更したと考えてみると、本質的に同じデータであっても採用する単位によって簡単に結果がおかしくなってしまう事が分かる。この例からも実際の分析に用いる際にはスケーリングが必須となる事が伺える。

まとめ

試してみて実装も比較的容易で使い勝手の良さそうな手法だと感じられる。
問題は処理時間であり、サンプルに用いた 500 件程度のデータでも 10 秒ほどの処理時間が必要となった。データ数 N に対し O(N^2) のアルゴリズムとなるはずなのでこれだとまともなサイズのデータ(万オーダー)には使えない可能性が高い。この点の解消のためには 特徴量エンジニアリング〜fastknn〜 を参考に高速なアルゴリズムへの置き換えが必要だと思われる。