![RでNN実行してみた
install.packages("class")
library("class")
data(iris)
#irisデータを学習データとテストデータに分ける
train = rbind(iris[1:25,1:4], iris[51:75,1:4], iris[101:125,1:4])
test = rbind(iris[26:50,1:4], iris[76:100,1:4], iris[126:150,1:4])
c = factor(c(iris[1:25,5], iris[51:75,5], iris[101:125,5]))
levels(c) = c("se", "ve", "vi")
knn1(train, test, c) #学習と予測がセット
実行結果](https://image.slidesharecdn.com/5kknn-130913070116-phpapp01/85/5-k-k_nn-91-320.jpg)
![RでkNN実行してみた
install.packages("class")
library("class")
data(iris)
train = rbind(iris[1:25,1:4], iris[51:75,1:4], iris[101:125,1:4])
test = rbind(iris[26:50,1:4], iris[76:100,1:4], iris[126:150,1:4])
c = factor(c(iris[1:25,5], iris[51:75,5], iris[101:125,5]))
levels(c) = c("se", "ve", "vi")
knn(train, test, c, k = 3, prob=TRUE) #kNNの実行
attributes(.Last.value) #詳細の表示
実行結果
knn.cv関数でクロスバ
リデーションも一緒に
できるようだけど、挙
動が謎だった???](https://image.slidesharecdn.com/5kknn-130913070116-phpapp01/85/5-k-k_nn-92-320.jpg)
More Related Content
What's hot (20)
Similar to はし?めてのハ?ターン認識 第5章 k最近傍法(k_nn法) (13)
More from Motoya Wakiyama (7)
![[Rec sys2013勉強会]using maximum coverage to optimize recommendation systems in ...](https://cdn.slidesharecdn.com/ss_thumbnails/recsys2013usingmaximumcoveragetooptimizerecommendationsystemsine-commerce-131215222200-phpapp01-thumbnail.jpg?width=560&fit=bounds)
![[Rec sys2013勉強会]orthogonal query recommendation](https://cdn.slidesharecdn.com/ss_thumbnails/recsys2013orthogonalqueryrecommendation-131215221938-phpapp02-thumbnail.jpg?width=560&fit=bounds)
はし?めてのハ?ターン認識 第5章 k最近傍法(k_nn法)
- 4. 最近傍法って何だ
- 6. どうやって近さを求めるの？ 一般的には 「ユークリッド距離」を使う あるデータxと、クラスiのj番目の データxj (i)のユークリッド距離 d(x,xj (i)) = |x-xj (i)| ? 原理的には他の距離でもいい けど、ユークリッド距離を使 うのが一般的らしい コインのサイズ コインの重量 真 偽 この距離
- 7. 最近傍法の識別規則は？ ? ? ? ? ? ? ? ? ? other txxd reject xxd i j i j i の時 識別クラス )()( ,min,minarg コインのサイズ コインの重量 真 偽 距離が一番小さいデータ が属するクラス 一番近い鋳型との 距離がtより大きい 時はreject !
- 11. 最近傍法での判別 ボロノイ境界 ? ? ? ?3,...,1 ?? NxxS N ボロノイ境界 学習データxiとxjのボロノイ境界B(xi, xj) B(xi, xj) = {x|d(xi, x) = d(xj, x)} ?xiとxiから等距離のxの集合 1と3の境界だと この辺も境界…？
- 12. 最近傍法での判別 データ1と データ3の 超平面 ボロノイ境界（を作る超平面） ベクトルを使って表現するとこうなる 上式を満たすxが表す超平面がボロノイ領域を作る ? ? ? ? ? ?jiji T xxnxxxnxx ?????? ,2/,0 n x
- 13. 最近傍法での判別 ? ? ? ? ? ?jiji T xxnxxxnxx ?????? ,2/,0 半空間（超平面のあっち側とこっち側） 超平面は、 xiを含む半空間D(xi, xj) = {x|d(xi, x) < d(xj, x)}と xjを含む半空間D(xj, xi)に 二分割する 半空間 D(1, 3) 半空間 D(3, 1) 超平面
- 17. データ1とデータ2から 作ったデータ1の半空間 データ1とデータ3から 作ったデータ1の半空間 重複箇所がボロノイ領域 ? ? ? ?? ijSx jii j xxDSxVR ?? ? , ,, ただし、上式は 開集合だから境 界は含まないら しい。 境界を含める閉 包の場合は以下 で表現 ? ?SxVR i ,
- 18. ボロノイ図またの名をボロノイモザイク ?さっきの閉包を全部くっつけたのがボロノイ図 ? ? ? ?jiSxx ji ji SxVRSxVRSV ?? ? ,, ),(),( これは境界を表す
- 20. 办狈狈法って何だ？
- 21. kNN法(k最近傍法)って何？ 大ざっぱに言うと、 近傍k個のデータから識別する 2クラス識別の例で考える 右図は、ユークリッド距離で マッピングしたものと思ってくれ クラス1鋳型 クラス2鋳型
- 31. 最適なkはいくつ？ 汎化誤差が最少となるkを求めればいい ?CrossValidationなどを使ってk毎の汎化誤差を求める ? 汎化誤差の計測は2.2節を参照 ? 本の例だとホールドアウト法と、一つ抜き法を使っている ? kが増えた時のホールドアウト法の誤り率が高いのは、次元の呪いの せいらしい こういう時にkを大きく し過ぎると、▲のクラス と識別してしまうから？
- 32. kNN法の弱点 ?処理が重い ? 鋳型（学習データ）を全探索するから当たり前 ? 手法の改善 ? 誤り削除型kNN ? 圧縮型kNN ? 分枝限定法 ? 近似最近傍探索 ?次元の呪いの影響を受ける ? ベイズ誤り率から分かるみたい
- 33. 办狈狈法の改善手法
- 41. 分枝限定法 ?分枝法と限定法を用いて、近傍の探索を効率化させる ? 分枝法：クラスタリングによって木構造のように組織化する ? 限定法：分枝法で作成した木構造をもとに近傍の探索を行う 限定法 一番上の階層のクラスタの平 均ベクトルmi との距離を算出 し、最も近いクラスタを探す 対象データとm1、m2、m3との 距離を算出すると、m1が最も 近い(S1が最も近い) S1 S2 S3 m1 m3 m2
- 42. 分枝限定法 ?分枝法と限定法を用いて、近傍の探索を効率化させる ? 分枝法：クラスタリングによって木構造のように組織化する ? 限定法：分枝法で作成した木構造をもとに近傍の探索を行う 限定法 S1の中のクラスタの平均ベク トルmi との距離を算出し、最 も近いクラスタを探す 対象データとm4、m5との距離 を算出すると、 m4が最も近 い(S4が最も近い) S1 S2 S3 S4 m4 S5 m5
- 45. 分枝限定法 ?分枝法と限定法を用いて、近傍の探索を効率化させる ? 分枝法：クラスタリングによって木構造のように組織化する ? 限定法：分枝法で作成した木構造をもとに近傍の探索を行う 限定法 S4以外のクラスタのデータが、 x38より近くないか判断する。 まずはS5のデータで判断。 d(x,m5) > d(x, x38) + d5 なら、 S5の全データはx38より遠い ↓ S5を探索する必要はない 探索するデータが減らせる！ S1 S2 S3 S4 x38 S5d5
- 46. 分枝限定法 ?分枝法と限定法を用いて、近傍の探索を効率化させる ? 分枝法：クラスタリングによって木構造のように組織化する ? 限定法：分枝法で作成した木構造をもとに近傍の探索を行う 限定法 S4以外のクラスタのデータが、 x38より近くないか判断する。 まずはS5のデータで判断。 d(x,m5) > d(x, x38) + d5 なら、 S5の全データはx38より遠い S1 S2 S3 S4 x38 S5d5 一旦位置関係は忘れて、S5のデータが取り得 る範囲を考える。
- 47. 分枝限定法 ?分枝法と限定法を用いて、近傍の探索を効率化させる ? 分枝法：クラスタリングによって木構造のように組織化する ? 限定法：分枝法で作成した木構造をもとに近傍の探索を行う 限定法 S4以外のクラスタのデータが、 x38より近くないか判断する。 まずはS5のデータで判断。 d(x,m5) > d(x, x38) + d5 なら、 S5の全データはx38より遠い S1 S2 S3 S4 x38 S5d5 一旦位置関係は忘れて、S5のデータが取り得 る範囲を考える。 d(x,m5) > d(x, x38) + d5なら、S5とx38の間に隙 間ができる ? S5のデータはx38のより遠い m5 d5 x38 x d(x, x38) d(x, m5) S5のデータが 取り得る範囲
- 48. 分枝限定法 ?分枝法と限定法を用いて、近傍の探索を効率化させる ? 分枝法：クラスタリングによって木構造のように組織化する ? 限定法：分枝法で作成した木構造をもとに近傍の探索を行う 限定法 S4以外のクラスタのデータが、 x38より近くないか判断する。 まずはS5のデータで判断。 d(x,m5) > d(x, x38) + d5 なら、 S5の全データはx38より遠い S1 S2 S3 S4 x38 S5d5 逆に、d(x,m5) ≦ d(x, x38) + d5だったら？ ?S5がx38よりxに近い可能性がある。 （絶対近いとは言えないけど、 S5を調べる 必要がでてくる） m5 d5 x38 x d(x, x38) d(x, m5)S5のデータが 取り得る範囲
- 49. 分枝限定法 ?分枝法と限定法を用いて、近傍の探索を効率化させる ? 分枝法：クラスタリングによって木構造のように組織化する ? 限定法：分枝法で作成した木構造をもとに近傍の探索を行う 限定法 d(x,m5) > d(x, x38) + d5 ↓ d(x,m2) > d(x, x38) + d2 ↓ d(x,m3) > d(x, x38) + d3 という条件を満たせば、 x38が最近傍！ S1 S2 S3 S4 x38 S5d5
- 56. 近似最近傍探索 最良優良探索 Step.1：2分木を作成 （作成方法は11章担当者が説明してくれるはず！） xA xB xC xD xE q (A,B,C,D,E) (A,C) (A) (C) (B,D,E) (B) (D,E) (D) (E) A B C D E
- 58. 近似最近傍探索 最良優良探索 Step.1：2分木を作成 Step.2：入力データと同じ領域内のデータxDとの距離d(q,xD)を算出 Step.3：次に近い領域Aとの距離d(q,A)を算出し、とd(q,xD)比較 xA xB xC xD xE q A B C D E d(q,A) ? ? ? ? ? ? ? ? ? ? ? ? ? ? 次に進む が近似解DD x Aqd xqd ),( 1 ),( ?
- 60. 近似最近傍探索 最良優良探索 Step.1：2分木を作成 Step.2：入力データと同じ領域内のデータxDとの距離d(q,xD)を算出 Step.3：次に近い領域Aとの距離d(q,A)を算出し、とd(q,xD)比較 Step.4：領域AのデータxAとの距離d(q,xA)を算出し、d(q,xD)も含めて 距離が短い方を保存（ここではd(q,xD)の方が短いとする） Step.5：次に近い領域Bとの距離d(q,B)を算 出し、とd(q,xD)比較 xA xB xC xD xE q A B C D E d(q,B) ? ? ? ? ? ? ? ? ? ? ? ? ? ? 次に進む が近似解DD x Bqd xqd ),( 1 ),( ? ※比較対象がxDなのは、今回はxDがxAよりが 近いから
- 63. 近似最近傍探索 最良優良探索 Step.1：2分木を作成 Step.2：入力データと同じ領域内のデータxDとの距離d(q,xD)を算出 Step.3：次に近い領域Aとの距離d(q,A)を算出し、とd(q,xD)比較 Step.4：領域AのデータxAとの距離d(q,xA)を算出し、d(q,xD)も含めて 距離が短い方を保存（ここではd(q,xD)の方が短いとする） Step.5：次に近い領域Bとの距離d(q,B)を算 出し、とd(q,xD)比較 Step.6：距離d(q,xB)を算出し、d(q,xD)と比 較して短い方を保存 xA xB xC xD xE q A B C D E 次に近い領域Dに対して同じ処 理を実施 ?以下の条件を満たさないので、 xB を近似解として終了 d(q,E) ? ? ? ? ? ? ? ? ? ? ? ? ? ? 次に進む が近似解BB x Eqd xqd ),( 1 ),( ? これが近似解！
- 64. 近似最近傍探索 なんで を満たすと、近似解と言えるのか？ xA xB xC xD xE q A B C D E ),( 1 ),( Eqd xqd B ? ??
- 65. 近似最近傍探索 なんで を満たすと、近似解と言えるのか？ (1+ε)r = d(q, xB) として円を描く r < d(q,E) < d(q, xE) (1+ε)r < (1+ε)d(q,E) < (1+ε)d(q, xE) d(q, xB) < (1+ε)d(q,E) < (1+ε)d(q, xE) xA xB xC xD xE q A B C D E ),( 1 ),( Eqd xqd B ? ?? (1+ε)r r d(q,E) 発表の時は図がおかしかったので修正しました。 バランスが悪いので、できれば本の方の図を見てください 本だとr’ 本だと d(q, xE)
- 66. 近似最近傍探索 なんで を満たすと、近似解と言えるのか？ (1+ε)r = d(q, xB) として円を描く r < d(q,E) < d(q, xE) (1+ε)r < (1+ε)d(q,E) < (1+ε)d(q, xE) d(q, xB) < (1+ε)d(q,E) < (1+ε)d(q, xE) ),( 1 ),( Eqd xqd B ? ?? 近似解が、厳密解の1+ε倍以内 xA xB xC xD xE q A B C D E (1+ε)r r d(q,E)
- 67. 近似最近傍探索 なんで を満たすと、近似解と言えるのか？ (1+ε)r = d(q, xB) として円を描く r < d(q,E) < d(q, xE) (1+ε)r < (1+ε)d(q,E) < (1+ε)d(q, xE) d(q, xB) < (1+ε)d(q,E) < (1+ε)d(q, xE) ),( 1 ),( Eqd xqd B ? ?? 探索の 判定と同じ ),( 1 ),( Eqd xqd B ? ? ? ? ? ? ? ? ?? xA xB xC xD xE q A B C D E (1+ε)r r d(q,E)
- 68. 办狈狈法における次元の呪い
- 72. 次元の呪い 漸近過程って？ ?鋳型の数が∞に近づけば、入力xと一致する鋳型が存在し そうなので、何となくこんなもんだと思う ? ? 0,lim 1 ?? ?? NNN N xxdT ? ? の距離と、最近傍鋳型 入力 個の鋳型の集合 鋳型の数 NNNN N xxxxd NT N 11 :, : :
- 73. 次元の呪い 漸近過程が成り立つと？ ベイズ誤り率の期待値ε*が、kNNの誤り率εkNNとの関係と 上限、下限が決まる ? 証明は5.3.1節を見てください！ ? 資料作るのがめんどくさかった。すいません。質問で対応します。 ? 多クラスの場合も成り立つみたいだけど、証明は確認してない… *2** 2 1 NN1NN3NN4NN2 ??????? ???????? ??
- 74. 次元の呪い 補足をちょっとだけ ?これはリジェクト時は誤りとカウントされないから ?k=偶数の方が、リジェクトが良く生じる という理解だけど、間違ってたらご指摘ください！ *2** 2 1 NN1NN3NN4NN2 ??????? ???????? ?? k=偶数だと誤り率が低く k=奇数だと誤り率が高い
- 76. 次元の呪い 次元が大きくなると、 漸近過程は成り立たない？ ?単位超球の中に鋳型が一様分布しているとする 1 ? ? 0,lim 1 ?? ?? NNN N xxdT 鋳型の数Nが∞になれば、 d(x, x1NN)は0になりそう (漸近過程が成り立ちそう)
- 80. 次元の呪い 次元が大きくなると、 漸近過程は成り立たない？ ?殻の厚さε=0.1として、殻部分の鋳型の部分を計算して みる 11 0.9 d = 2（2次元）だと？ 1－(1 － 0.1)2 = 0.19 単位超球内の鋳型の19%が殻の中にある
- 81. 次元の呪い 次元が大きくなると、 漸近過程は成り立たない？ ?殻の厚さε=0.1として、殻部分の鋳型の部分を計算して みる 11 0.9 d = 5（5次元）だと？ 1－(1 － 0.1)5 = 0.41 単位超球内の鋳型の41%が殻の中にある
- 82. 次元の呪い 次元が大きくなると、 漸近過程は成り立たない？ ?殻の厚さε=0.1として、殻部分の鋳型の部分を計算して みる 11 0.9 d = 10（10次元）だと？ 1－(1 － 0.1)10 = 0.65 単位超球内の鋳型の65%が殻の中にある
- 83. 次元の呪い 次元が大きくなると、 漸近過程は成り立たない？ ?殻の厚さε=0.1として、殻部分の鋳型の部分を計算して みる 11 0.9 d = 50（50次元）だと？ 1－(1 － 0.1)50 = 0.99 単位超球内の鋳型の99%が殻の中にある！
- 84. どういうこっちゃ？
- 85. 次元の呪い 次元が大きくなると、 漸近過程は成り立たない？ 11 0.9 なんとなく分かるのは、 d = 50（50次元）だと、単位超球内の鋳型 の99%が殻の中にある。 これだと、漸近過程は成り立たない??? ? ? 0,lim 1 ?? ?? NNN N xxdT
- 86. 次元の呪い ? ? 0,lim 1 ?? ?? NNN N xxdT *2** 2 1 NN1NN3NN4NN2 ??????? ???????? ?? 漸近過程がなりたつと、 ベイズ誤り率の上限と下限が決まる
- 87. 次元の呪い ? ? 0,lim 1 ?? ?? NNN N xxdT *2** 2 1 NN1NN3NN4NN2 ??????? ???????? ?? 漸近過程がなりたつと、 ベイズ誤り率の上限と下限が決まる 次元が大きいと漸近過程が 成り立たない！ ということで、データの 次元は小さい方がいい。
- 90. Rでボロノイ図書いてみた #パッケージのインストール install.packages("tripack") library(tripack) data(iris) iris.vm = voronoi.mosaic(as.vector(iris$Sepal.Length), as.vector(iris$Sepal.Width), duplicate="remove") plot(iris$Sepal.Length, iris$Sepal.Width, pch=16) plot.voronoi(iris.vm, add=T)
- 91. RでNN実行してみた install.packages("class") library("class") data(iris) #irisデータを学習データとテストデータに分ける train = rbind(iris[1:25,1:4], iris[51:75,1:4], iris[101:125,1:4]) test = rbind(iris[26:50,1:4], iris[76:100,1:4], iris[126:150,1:4]) c = factor(c(iris[1:25,5], iris[51:75,5], iris[101:125,5])) levels(c) = c("se", "ve", "vi") knn1(train, test, c) #学習と予測がセット 実行結果
- 92. RでkNN実行してみた install.packages("class") library("class") data(iris) train = rbind(iris[1:25,1:4], iris[51:75,1:4], iris[101:125,1:4]) test = rbind(iris[26:50,1:4], iris[76:100,1:4], iris[126:150,1:4]) c = factor(c(iris[1:25,5], iris[51:75,5], iris[101:125,5])) levels(c) = c("se", "ve", "vi") knn(train, test, c, k = 3, prob=TRUE) #kNNの実行 attributes(.Last.value) #詳細の表示 実行結果 knn.cv関数でクロスバ リデーションも一緒に できるようだけど、挙 動が謎だった???