はじパタ第5章 k最近傍法（kNN法）

　平井有三先生の「はじめてのパターン認識」第5章を読んだ。
kNN自体はもちろん知っていたが、理論的な考察についてはほとんど知らなかったので勉強になった。

面白かったところ

• 式を使ったボロノイ図の定義
• kNNとベイズ誤り率の関係
• kNNにおける次元の呪いの話

理解度チェックリスト

• 最近傍法とは？
• k最近傍法とは？
• ボロノイ図とは？
• kNNを使うときに問題となる次元の呪いについて説明せよ。
• 予測データと学習データの距離はどうなる？
• kNNの計算量は？
• kNNの計算量を減らすための工夫をいくつか説明せよ。