ある面接で、雇用主からの質問に遭遇しました。彼は、たとえば文字認識や顔認識において、KNN 分類器が決定木よりもはるかに高速なのはなぜですか?と尋ねました。
当時の私にはまったくわかりませんでした。では、速度性能の 2 つの分類方法をどの点で比較すればよいか知りたいですか? ありがとう。
2241 次
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 に答える