Chapter 02

k-近傍法(k-nearest neighbor)

k-近傍法

教師あり回帰問題、教師あり分類問題。入力xに対する出力yを予測する。

過去に観測されたことがある入出力のペアのうち、与えられた入力ともっとも距離が近い入力を持つk個のデータ点を抜き出し、そこに記録されている出力をそのまま、あるいは若干加工して出力するだけの方法。

誰でも思いつきそうな方法だが、データをたくさん集めるとけっこうワークするので案外侮れない。小難しい方法にチャレンジして、あとになって「k-近傍法のほうが性能がよかったです」と認めるときの屈辱はなかなかエゲツないので最初にサクッと試しておいてベースラインにするとよい。

本シリーズで用いる数式の表記一覧

本シリーズでは独自記号として、以下の「列挙(enumerate)」を使う。

\overset{n}{\underset{i=1}{\sf E}} x _ i = x _ 1, x _ 2, \ldots, x _ n

たとえばこれを用いて集合を定義することができる。

\Bigl\{ \overset{n}{\underset{i=1}{\sf E}} x _ i \Bigr\} = \{ x _ 1, x _ 2, \ldots, x _ n \}

モデル

入力空間\mathcal{X}における距離関数d \colon \mathcal{X} \times \mathcal{X} \to \mathbb{R}と、出力を加工するための関数\pi \colon \mathcal{Y} ^ k \to \mathcal{Y}を定義する必要がある。

学習

入力にもっとも近いデータを検索するだけなので学習と呼べるような操作は必要ない。

N個のデータを観測したデータセット\mathcal{D}が以下で与えられたとする。

\mathcal{D} = \Bigl\{ \overset{N}{\underset{i=1}{\sf E}} (x ^ {(i)}, y ^ {(i)}) \Bigr\}

新たに入力x \in \mathcal{X}が与えられたときに対応する出力y \in \mathcal{Y}を求めたい。このとき、入力xi番目のデータとの距離

d(x, x ^ {(i)})

を最小化するik個求めて、対応する出力の組(y ^ {(i _ 1)}, y ^ {(i _ 2)}, \ldots ,y ^ {(i _ k)})を加工するための関数\piにかけ、

\hat{y} = \pi(y ^ {(i _ 1)}, y ^ {(i _ 2)}, \ldots ,y ^ {(i _ k)})

を推定値とする。

距離関数

d \colon \mathcal{X} \times \mathcal{X} \to \mathbb{R}は距離としての性質を満たせば何を用いてもよい。距離の性質とは、任意の点x,y,zに対して

  1. 非負性:d(x,y) \geq 0
  2. 非退化性:d(x,y) = 0 \Leftrightarrow x = y
  3. 対称性:d(x,y) = d(y,x)
  4. 三角不等式:d(x,y) + d(y,z) \geq d(x,z)

の4つが成り立つことである。

出力を加工するための関数

\pi \colon \mathcal{Y} ^ k \to \mathcal{Y}は何でもよい。k=1であればそのまま出力するか、あるいはランダムなノイズを加えて出力してもよい。k > 1であれば候補の中からランダムにサンプリングしてもよいし、中心や重心を計算できるならばそれを出力してもよい。分類問題であれば多数決を取ってもよい。