8

ある面接で、雇用主からの質問に遭遇しました。彼は、たとえば文字認識や顔認識において、KNN 分類器が決定木よりもはるかに高速なのはなぜですか?と尋ねました。

当時の私にはまったくわかりませんでした。では、速度性能の 2 つの分類方法をどの点で比較すればよいか知りたいですか? ありがとう。

4

1 に答える 1

6

次のデータセットについて考えてみます。N個のサンプル。それぞれにk個の属性があります。一般的に:
1。ナイーブKNN:O(1)[トレーニング時間] + O(NK)[クエリ時間] = O(NK)
2.ナイーブ決定木:O(N ^ 2 * K * log(N))[トレーニング時間]+O(log(N))[クエリ時間] = O(N ^ 2 * K)-クエリ時間についても、ツリーのバランスが取れていると仮定します。
複雑さを計算するために、私は各分類器の非常に単純な実装を検討しました。KNNとディシジョンツリーを実装するための改善点はすでにいくつかあります。

于 2013-03-15T09:35:45.790 に答える