【kNN】R で k 近傍法

K近傍法

k近傍法 (k-nearest neighbor algorithm) は, 特徴空間上で最も近い距離にある訓練データに基づいて分類/回帰を行う手法であり, 直感的にもわかりやすいパターン認識手法です。

最短近傍法は与えられた未知データに対して一番近い訓練データのクラスに属しているだろうというのが基本的な考えで, 特徴空間で距離が近い順から k 個選択し多数決でクラスを推定するのが kNN法 です。一般的にはユークリッド距離が使われます。

一方, 訓練データにノイズが多かったり k を小さくした場合に精度が下がりやすい特徴があります。特徴空間が高次元になるとデータ間の距離が遠くなるため, 予め有用な特徴の見当がつく場合は特徴選択を行う方が良いです。また, 基本的に特徴空間全てを保持するためメモリ負荷が高くなります。

kNN in R

{class} パッケージを使います。kNN() は以下です。

knn(train, test, cl, k = 1, l = 0, prob = FALSE, use.all = TRUE)

Wineデータセットを使います。
Wine データセットは3つの異なる品種のワインを化学的な分析により, 13の特徴量で線形分離されたサンプルサイズ 178 のデータセットです。
3つの各クラスの前半 30 個を訓練データに使用し, 残りを評価に使います。

library(class)
library(dplyr)

# wine <- data(wine)
wine <- read.csv("data/wine.data", header = FALSE)
colnames(wine) <- c("class", "Alcohol", "Malic Acid", "Ash", "Alcalinity of Ash",
                    "Magnesium", "Total Phenols", "Flavanoids", "Nonflavanoid Phenols",
                    "Proanthocyanins", "Color Intensity", "Hue", 
                    "0D280/OD315 of Diluted Wines", "Proline")

wine$class <- as.factor(wine$class)

c1 <- wine %>%
  filter(class == 1)

c2 <- wine %>%
  filter(class == 2)

c3 <- wine %>%
  filter(class == 3)

t_size <- 30
train_X <- rbind(c1[1:t_size,-1], c2[1:t_size,-1], c3[1:t_size,-1])
train_y <- c(c1$class[1:t_size], c2$class[1:t_size], c3$class[1:t_size])
test_X <- rbind(c1[(t_size+1):nrow(c1),-1], c2[(t_size+1):nrow(c2),-1], c3[(t_size+1):nrow(c3),-1])
test_y <- c(c1$class[(t_size+1):nrow(c1)], c2$class[(t_size+1):nrow(c2)], c3$class[(t_size+1):nrow(c3)])

# knn
res <- knn(train_X, test = test_X, cl = train_y, k = 3, prob = TRUE)

table(res)
# res
#  1  2  3
# 28 43 17

table(test_y)
# test_y
#  1  2  3
# 29 41 18

# accuracy
sum(res == test_y)/length(test_y)
# [1] 0.7045455

k = 3 で正解率は 0.705 でした。

Visualization

{ElemStatLearn} パッケージの mixture.example データセットを使い kNN の分離平面を可視化してみます。mixture.example データセットは 2 クラスで各 100 サンプルを含んでいます

df <- ElemStatLearn::mixture.example

train_X <- df$x
train_y <- df$y
test_X <- df$xnew

# kNN
mod5 <- knn(train_X, test = test_X, cl = train_y , k = 5, prob = TRUE)

prob <- attr(mod5, "prob")
prob5 <- matrix(ifelse(mod5 == "1", prob, 1 - prob),
                length(df$px1),
                length(df$px2))

# plot
col_y <- ifelse(train_y == 1, "coral", "cornflowerblue")
col_pred <- ifelse(prob5 > 0.5, "coral", "cornflowerblue")

par(mar = rep(2,4))
contour(df$px1, df$px2, prob5,
        levels = 0.5, labels = "",
        xlab = "", ylab = "", main = "5-nearest neighbour",
        axes = FALSE)
points(train_X, col = col_y)
gd <- expand.grid(x = df$px1, y = df$px2)
points(gd,pch = ".", cex = 1.2, col = col_pred)
box()

参考書籍は『はじめてのパターン認識』です。


[1] はじめてのパターン認識 第5章 k最近傍法(k_nn法)
[2] kNNによるデータ分類
[3] Using the k-Nearest Neighbors Algorithm in R