データ科学特論

データ科学特論
その 8: k 近傍法
k 近傍 (k-nearest-neighbour, k-nn) 法
1
教科書に載っていないが，教師あり学習アルゴリズムである k 近傍法を紹介する。非常に
シンプルだが，大量の学習データがある場合に精度が上がる方法である。基準変数 Y につい
ては，カテゴリ変数の場合と連続変数の場合で処理が少し異なる。
1.1
距離
まず，2 データアイテム間の距離を定義する。
単なる実数 x1 , x2 , y1 , y2 を考えよう。平面上の 2 地点 (x1 , y1 ),(x2 , y2 ) 間の距離は，
p
(x1 − x2 )2 + (y1 − y2 )2
これを m 次元のデータ間の距離に一般化すると，
v
um
uX
t (x1k − x2k )2
k=1
つまり，データアイテム xi と xj の間の距離 dij は
v
um
uX
dij = t (xik − xjk )2
k=1
と定式化できる．このように定義される距離を，ユークリッド距離と呼ぶ。他にも，マン
ハッタン距離やマハラノビス距離など，いろいろな距離がある。以下ではベクトル a,b 間の
距離を
d(a, b)
と表記することにする．
1
1.2
学習と予測
k 近傍法においては，学習のフェーズではたいした計算は行わず，単に学習データを記憶し
ておくのみである．この意味で，k 近傍法は，記憶ベース推論とか，怠惰学習 (lazy learning)
の一種と呼ばれる。
では，予測の段階ではどのように計算を行うのであろうか。以下では基準変数 Y がカテゴ
リ変数の場合と連続変数の場合に分けて説明する。前提として，k は設計者が適当に決めて
おく必要がある。特に k = 1 の場合を，最近傍法と呼ぶ。
基準変数 Y がカテゴリ変数の場合
予測のためのデータ x ∈ X があると，それに距離が近い学習データ k 個を取り出す。その
k 個の学習データの中で最も多い基準変数 Y の値を予測値として採用する。
より正確には，以下のような手順となる。
1. 学習データを予測変数 X = {x1 , x2 , · · · , xh , · · · , xn }, 基準変数 Y = {y1 , y2 , · · · , xh , · · · , yn }
とする．説明の都合上，xh は多次元 (xh1 , · · · xhm ), yh は 1 次元であるとする。
2. 予測のためのデータ x が与えられたとする。これから以下のように予測値 y を求める。
3. X = {x1 , x2 , · · · , xh , · · · , xn } のうち d(x, xh ) が小さい物から k 個を取り出し，これを
X ′ と呼ぶ。
4. X ′ のとる値のうち，最も出現頻度が多い値を予測値 y とする．
基準変数 Y が連続変数の場合
距離が近い k 個のデータを取り出す 3 まではカテゴリ変数と同じであるが，その k 個の学
習データ X ′ に対応する基準変数 Y ′ の値の平均を予測値とする。
1.3
パラメータ k の決定方法
k の決定には試行錯誤が必要である。k が大きければ，基準変数 Y の個々の値 (クラスと
呼ぶことにする) に予測される空間が大きくなるので，その値に予測されることが多くなる
ため，分類にあたって漏れ (False Negative) が少なくなるが，クラス間の境界が明確になら
ない．k の決定には，交差検定などの経験的な手法を用いることが出来る。
2
2
R で k 近傍法
R には k 近傍法の実装はいくつかあるが，ここでは，アニメーションで例示する knn.ani
と，パッケージ caret の knn3 のヘルプにある例を紹介する。
knn.ani
knn.ani は二次元の予測変数 X に対する k 近傍法をアニメーションで例示する．以下の
ように example を実行できる。example 関数を使わずに，knn.an>の右側の文字列を手入力
しても良い。
> library(animation)
> example(knn.ani)
knn.an> ## a binary classification problem
knn.an> oopt = ani.options(interval = 2, nmax = 10)
まずはオプションを ani.options 関数で設定する．interval はアニメーションの時間間
隔, nmax はループの最大回数である。
knn.an> x = matrix(c(rnorm(80, mean = -1), rnorm(80, mean = 1)),
knn.an+
ncol = 2, byrow = TRUE)
上記では，変数 x に matrix で行列を設定している。その中身は，-1 を平均とする正規分
布に従う乱数 80 個と，1 を平均とする同様の乱数 80 個を行方向に並べていって，2 列で改
行した物である。後でプロットのときに，1 列目が水平軸，2 列目が垂直軸と見なされるの
で，座標 (-1,-1) を平均とする点の分布と，(1,1) を平均とする点の分布からなることになる．
knn.an> y = matrix(rnorm(20, mean = 0, sd = 1.2), ncol = 2)
今度は評価（予測）データを生成している．平均 0，標準偏差 1.2 の正規分布に従う乱数
を 20 個，生成して 2 列の行列としている。
knn.an> knn.ani(train = x, test = y, cl = rep(c("first class", "second class"),
knn.an+
each = 40), k = 30)
animation option ’nmax’ changed: 10 --> 40
3
knn.ani 関数で，学習データを x, 評価（予測）データを y として予測を行っている。引数
の cl はクラス，つまり基準変数 Y を指定している．ここでは，最初の 40 個が first class,
second class という 2 つのクラスになっている。引数 k で，パラメータ k を指定している。
アニメーションでは，判別結果が○や△で表示される。
ひとしきりアニメーションが表示されると，今度は別の例が始まる。今度は，3 クラスの
判別であり，それぞれ (-2,-2),(0,0),(2,2) という座標を平均とする分布を判別している。
knn.an> x = matrix(c(rnorm(30, mean = -2), rnorm(30, mean = 2),
knn.an+
rnorm(30, mean = 0)), ncol = 2, byrow = TRUE)
knn.an> y = matrix(rnorm(20, sd = 2), ncol = 2)
knn.an> knn.ani(train = x, test = y, cl = rep(c("first", "second", "third"),
knn.an+
each = 15), k = 25, cl.pch = c(2, 3, 19), dist.lty = 3)
判別結果は，アニメーションで●，+，△で表示される．2 つ以上のクラスの領域が重なっ
て判別できないときには，？が表示されるものと思われる．
その次には，実行されないが，テスト（評価）セットをマウスでクリックしたいときに行
う方法をコメントで表示している。
knn.an> ## Not run:
knn.an> ##D
knn.an> ##D # an interactive demo: choose the test set by mouse-clicking
knn.an> ##D ani.options(nmax = 5)
knn.an> ##D knn.ani(interact = TRUE)
knn.an> ##D
knn.an> ##D ani.options(ani.height = 500, ani.width = 600, nmax = 10,
knn.an> ##D
interval = 2, title = "Demonstration for kNN Classification",
knn.an> ##D
description = "For each row of the test set, the k nearest (in Euclidean
knn.an> ##D
distance) training set vectors are found, and the classification is
knn.an> ##D
decided by majority vote, with ties broken at random.")
knn.an> ##D ani.start()
knn.an> ##D par(mar = c(3, 3, 1, 0.5), mgp = c(1.5, 0.5, 0))
knn.an> ##D knn.ani()
knn.an> ##D ani.stop()
knn.an> ## End(Not run)
knn.an>
knn.an> ani.options(oopt)
animation option ’nmax’ changed: 40 --> 10
>
4
カテゴリ変数のための knn3
今度は caret パッケージにある knn3 関数を紹介する。example(knn3) で得られる例を基
にする．
> library(caret)
> irisFit1 <- knn3(Species ~ ., iris)
ここでは，iris というデータセットで学習をしている。iris の変数 Species を基準変数
Y として，学習をしている。第 1 引数の書き方は，決定木学習などで説明して物と同様。knn3
の文法は他にも，以下のように，予測変数 X と基準変数 Y を与える方法もある。以下は上
記と全く同じ意味である．
> irisFit2 <- knn3(as.matrix(iris[, -5]), iris[,5])
予測を行うには，predict.knn3 関数を使うが，predict のように省略可能である。
> pre <- predict(irisFit1,newdata=iris,type=’class’)
predict 関数の使い方は決定木の時と同様である。ここでは pre という変数に予測結果を
入れている。
カテゴリ変数の場合は，以下のように table 関数を使って個数を数えることが多い。（こ
の方法にはもうなれただろうか？）
> table(iris$Species, pre)
pre
setosa versicolor virginica
setosa
50
0
0
versicolor
0
47
3
virginica
0
2
48
連続変数のための knnreg
同様に caret パッケージの関数で，連続変数のための knnreg を紹介する。連続変数の場
合は，table 関数ではなく，回帰分析のように，散布図を書くことが多い。
以下も，example(knnreg) の結果を基に説明する。ここでは血液脳関門（Blood Brain
Barrier:血液と脳の組織液を交換する機構）のデータを扱う。（意味はよくわからないが。）
BloodBrain データを呼び出すと，bbbDescr と logBBB という 2 つのデータが得られる。こ
5
こでは前者を予測変数 X ，後者を基準変数 Y として，X から Y を予測するが，その際に，
学習データと評価データを分割するテクニックを使う。
そのテクニックとは，createDataPartition という関数を使う物である。この関数によ
り，データを一定の割合で分割し，その要素番号をベクトルで返す。
> data(BloodBrain)
> inTrain <- createDataPartition(logBBB, p = .8)[[1]]
これは logBBB データを 0.8 ％とそれ以外に分割するという意味である。その上で，
> trainX <- bbbDescr[inTrain,]
> trainY <- logBBB[inTrain]
とすると，分割したデータを要素番号で指定できる。逆にそれ以外のデータは，
> testX <- bbbDescr[-inTrain,]
> testY <- logBBB[-inTrain]
で得ることが出来る。
この上で学習をさせるには，
> fit <- knnreg(trainX, trainY, k = 3)
でよい．
次に予測とプロットを一気に行う。予測は同様に predict.knnreg を省略して predict で
可能である。
> plot(testY, predict(fit, testX))
この散布図から，統計的に傾きの当てはまりの良さなどを調べたり検定するには lm とい
う関数があるが，説明は省略する。
3
宿題
今回 R で行った内容を，自分の計算機環境で再現してください。
6

Download Report