内容を他人に説明する機会があったので，そのときに自分なりにまとめたものをここに記しておく。
近傍法の発想
近傍法の根本は「近いデータどうしは同じクラスに属する」という発想だろう。第5章の内容は，この発想に照らし合わせることですっきり理解できた。
kの値の適切さ
kNN法ではkの値を適切に決める必要がある。具体的な最適値は汎化誤差を比べないとわからないようだが，適切さの基準を定性的に述べるなら，「近くの情報が適切に拾えるかどうか」ということになるだろう。kが小さすぎると外れ値などの局所的なばらつきの情報が強く表れるので，誤った分類をしやすくなる。ばらつきの影響はたくさんの鋳型を見て判断すれば小さくなるけど，kが大きすぎると今度は識別に関係しない遠くの情報まで拾ってしまうことになる。どちらにしても近傍の情報が正しく拾えないので，近傍法はうまくはたらかない。
漸近仮定の意味
漸近仮定とは「鋳型が十分に多ければ，入力データに十分近い鋳型がある」とする仮定だ。近傍法の基本思想は近いデータどうしが同じクラスに属することだから，入力データから好きなだけ近いところに鋳型があると言えるのは近傍法にとって理想的な条件である。誤り率についての議論が漸近仮定の下で進められているのは，それがkNN法を一番理想的に扱える状態だからだろう。次元の呪い
逆に『次元の呪い』は近傍法にとって一番不利な条件である。次元の呪いは第2章でも出てきたが，今回の呪いは「次元が大きいと超球の体積のほとんどを球殻が占めるようになる」というものだ。超球の体積とその球殻（厚さε）の体積とを比べると，εが小さくても次元が大きければ体積比が1に漸近してしまう。近傍法でいうと，入力データの近くに鋳型がない上に，周りの鋳型はほとんど同じ距離（球殻上）に存在するということになる。これは漸近仮定が成り立っているときとは真逆の状態で，近傍法にとっては致命的である。
計算量を減らすための方針
素朴なkNN法は鋳型全部との距離を計算するので，鋳型が多いと計算量も多くなる。5.4節では計算量を低減する方法が紹介されている。計算量低減の方針は大きく分けて①いらない鋳型を削除する②遠くの鋳型は計算しない，の2つがある。①の方針をとるなら，どんな鋳型を不要と判断するかが問題になる。「誤り削除型」では，間違ったクラス領域にある鋳型を不要として取り除いている。「圧縮型」では，識別境界に影響しないデータを不要として取り除いている。
②の方針をとるなら，具体的に距離を計算しなくても大まかな遠近を把握できる仕組みが必要になる。この仕組みは，あらかじめ鋳型どうしの距離関係を反映したデータ構造を定義しておくことで実現できる。「分枝限定法（分岐ではない）」では，鋳型の部分集合を節，集合の包含関係を枝とした木構造を使って，節の要素全体を囲む領域との距離を計算することで大まかな距離を把握している。「近似最近傍探索」では，特徴空間を区切った矩形領域を鋳型に割り当てておいて，その矩形領域との距離を計算することで近似解かどうかを判断している。
まとめ
- 近傍法は「近いデータどうしが同じクラスに属する」という発想に基づく
- kの値は近傍の情報が拾える大きさにする
- 近傍法にとっては入力データの近くに鋳型があることが理想的
- 鋳型どうしの距離構造を反映したデータ構造が用意されていると計算を省ける
