Una volta in un'intervista, ho incontrato una domanda dal datore di lavoro. Mi ha chiesto perché il classificatore KNN è molto più veloce dell'albero delle decisioni, ad esempio nel riconoscimento di lettere o nel riconoscimento facciale?Perché KNN è molto più veloce dell'albero decisionale?
All'epoca non avevo assolutamente idea. Quindi voglio sapere in che termini dovrei confrontare i due metodi di classificazione nelle prestazioni di velocità? Grazie.
Considerare il seguente set di dati: N campioni, ognuno ha k attributi. In generale:
1. naive KNN: O (1) [tempo di allenamento] + O (NK) [tempo di interrogazione] = O (NK)
2. albero di decisione ingenuo: O (N^2 * K * log (N)) [tempo di allenamento] + O (log (N)) [tempo di interrogazione] = O (N^2 * K) - Anche per il tempo di interrogazione, assumiamo che l'albero sia bilanciato.
Per calcolare le complessità, ho considerato l'implementazione molto semplice di ciascun classificatore. Ci sono già alcuni miglioramenti per l'implementazione di KNN e Decision Tree.
ci sono un paio di paragoni bel linea – Dreamwalker