最大マージン kNN と SVM の関係: kNN も最近はがんばっています - 武蔵野日記

先日書いた機械学習における距離学習の続き。 kNN (k-nearest neighbour: k 近傍法)は Wikipedia のエントリにも書いてある通り、教師あり学習の一つで、あるインスタンスのラベルを周辺 k 個のラベルから推定する手法。memory-based learning と呼ばれることもある。単純に多数決を取る場合もあれば(同点を解決する必要があるが)、近いインスタンスの重みを大きくする場合もあるのだが、いずれにせよかなり実装は単純なので、他の機械学習との比較(ベースライン)として使われることも多い。 簡単なアルゴリズムではあるが、1-NN の場合このアルゴリズムの誤り率はベイズ誤り率(達成可能な最小誤り率)の2倍以下となることが示されたり、理論的にもそれなりにクリアになってきているのではないかと思う。また、多クラス分類がちょっと一手間な SVM (pairwise に

[gologo13]

kNNもなかなか良くなってるけど半決定的プログラミングという制約が大きくて，SVMの方に軍配が上がるという話

[ttpooh]

距離学習のLMNNとか高速なSVM実装(?)のCVM/BVMとか。うーん、全然フォローできてないなぁ・・・せめてKDDぐらいチェックせねば。

[suji_ski]

距離学習の話．SVMもちょっと出てきている．

[kana0355]

多クラス分類に強いというのは利点．

[y_yanbe]

Yahoo! Researchいいなぁ