次元の呪いについて

ETL1とビマ・インディアンデータ

ビマ・インディアンデータ次元数が7と少ない. 一方でETLは16×16の256次元？

次元数が少ないと、kを増加させた際に誤り率が低下し、knnが有効となる

例題5.1

定義より、$(\bar{\boldsymbol{x}}-\boldsymbol{x})\boldsymbol{n}=0$となる$\boldsymbol{x}=(x,y)$がボロノイ境界となる.
$\bar{\boldsymbol{x}}=(\frac{1}{2},\frac{1}{2})^T$, $\boldsymbol{n}=(1,-1)$より, 上式に当てはめて
$(\frac{1}{2}-x)-(\frac{1}{2}-y)=0$

よって$-x+y=0$

knnと次元の呪い

引用：https://qiita.com/oirom/items/49009c8903ece81fd7cf

引用；https://qiita.com/FukuharaYohei/items/0314f73cebb471deb515

knn誤り率とベイズ誤り率の関係について

漸近仮定

章末問題

例題5.1

・|・|・|・|・|・|・|・|・|・|・

↑こんなかんじになる（・が鋳型、|がボロノイ境界）

例題5.2

(1)
水平線$y=y_0$と鋳型(x_1,y_1)までの距離が等しくなる$\boldsymbol{x}=(x,y)$を求める。
$y-y_0=\sqrt{((x_1-x)^2+(y_1-y)^2)}$
$y^2-2yy_0+{y_0}^2=(x_1-x)^2+(y_1-y)^2)$
...
$y=\frac{1}{2(y_1-y_0)}(x-x_1)^2+\frac{1}{2}(y_1+y_0)$

(2)
p204の解図を参照。実線がp1, 点線がp2の軌跡を表す。
これらの交点は、p1, p2からの距離が等しい点となる

例題5.3

knnの計算量削減手法について

こちらがよくまとまっている
https://www.slideshare.net/slideshow/5-kknn/26165132#57