今回はk近傍法 (k-nearest neighbor algorithm; kNN)を使った分類を紹介します。今回も前回と同様、なるべく外部パッケージを使わずkNNを実装してみたいと思います1

仮想データの作成

今回も仮想データの作成から始めましょう。やはり楽しいのは実際のデータをいじるのですが、既知のデータ生成過程から作成したデータセットは「正解」が分かっているので、シミュレーションなどに向いています。

今回も結果変数が(0, 1)の二値であるとし、以下のデータ生成過程にしたがうとします。

\[\begin{eqnarray} Y & = & \begin{cases} 1, & \text{if $y^* \geq 30$}, \\ 0, & \textrm{otherwise}, \end{cases}\\ y^* & \sim & 1 - 0.8 X1 + 2 X1^2 - 3 X2 + 0.2 X2^2 + \varepsilon, \nonumber \\ \varepsilon & \sim & \textrm{Normal}(0, 10) \nonumber \\ X1, X2 & \sim & \textrm{Uniform}(-5, 5) \nonumber \end{eqnarray}\]

それでは早速データセットを作成し、dfと名付けましょう。

set.seed(19861008)
x1 <- runif(100, -5, 5)
x2 <- runif(100, -5, 5)
e  <- rnorm(100, 0, 10)
ya <- 1 - (0.8 * x1) + (2 * x1^2) - 3 * x2 + (0.2 * x2^2) + e
y  <- ifelse(ya >= 30, 1, 0)

df <- data.frame(x1 = x1, x2 = x2, y = y)

rm(x1, x2, e, ya, y)

それでは、説明変数 (\(X1\)\(X2\))と結果変数 (\(Y\))の関係を確認しましょう。

前回の例のように一本の線で2つを分けるのはなかなか難しいようです。

kNN法について

前回のロジスティック回帰は予め関数型が決められており、数個のパラメーター2だけを推定するだけで済みましたよね。このようなモデルをパラメトリック・モデル (parametric model)と呼びます。今回のkNNはノンパラメトリック・モデル (nonparametric model)の代表的なモデルです。推定するパラメーターの数も指定せず、パラメトリック・モデルに比べ計算量が多いです。しかし、回帰分析のような線形を前提としていないため、非線形の関係などにも柔軟に対応できるというメリットがあります。

kNN法ある地点がどのカテゴリーに属するかを決めるアルゴリズムです。どのカテゴリーに属するかは、ある点を中心にした最も近いk個の点を用いて多数決で決めます。ちなみに、距離はユークリッド距離を用います。たとえば、\(k = 3\)にした場合、(-3.5, -0.75)の点はどのカテゴリーに属するでしょうか。

ある点、(-3.5, -0.75)の近傍にある5つの点は赤 (1)が2つ、青 (0)が1つです。つまり、(-3.5, -0.75)は\(Y = 1\)の領域であることを意味します。このような作業をプロット全体に対して行います。プロット内の感覚を細かく刻めば刻むほど、より正確に計算できるようになります。

もし、\(k = 5\)ならどうでしょうか。