Classificateurs d'apprentissage automatique Big-O ou complexité

Pour évaluer les performances d'un nouvel algorithme de classificateur, j'essaie de comparer la précision et la complexité (big-O dans la formation et la classification). De Machine Learning: un examen, j'obtiens une liste complète des classificateurs supervisés, ainsi qu'un tableau de précision entre les algorithmes et 44 problèmes de test du référentiel de données UCI . Cependant, je ne trouve pas de critique, de papier ou de site Web avec le big-O pour les classificateurs courants comme:

C4.5
RIPPER (je pense que ce n'est peut-être pas possible, mais qui sait)
ANN avec propagation arrière
Bayésien naïf
K-NN
SVM

Si quelqu'un a une expression pour ces classificateurs, ce sera très utile, merci.

machine-learning classification multiple-comparisons algorithms time-complexity Dinl
la source

Vous pouvez être intéressé par l'article suivant: thekerneltrip.com/machine/learning/… Avertissement complet, c'est mon blog :)

RUser4512

Souciez-vous de retracer les endroits où les liens maintenant morts de la question pointaient?

mat

@ RUser4512 délibération de blog vraiment super! avez-vous également envisagé d'ajouter de la complexité à l'espace?

mat

@matt Merci :) oui, mais probablement dans un autre article, il y a aussi beaucoup de choses à dire à ce sujet!

RUser4512

Réponses:

Soit = nombre d'exemples de formation, = dimensionnalité des caractéristiques et = nombre de classes. $N$ $d$ $c$

La formation a alors des complexités:

Naive Bayes est , il suffit de calculer la fréquence de chaque valeur de caractéristique pour chaque classe. $O(Nd)$ $d_i$
-NN est dans (certaines personnes disent même qu'il n'existe pas, mais la complexité spatiale de la formation est car vous devez stocker les données, ce qui prend également du temps). $k$ $\mathcal{O}(1)$ $\mathcal{O}(Nd)$
Le SVM non linéaire non approximatif est ou selon le noyau. Vous pouvez obtenir un jusqu'à $O(N^2)$ $O(N^3)$ $O(N^3)$ $O(N^{2.3})$ avec quelques astuces.
SVM approximatif est $O(NR)$

Tester les complexités:

$\mathcal{O}(cd)$ $d$ $c$
$k$ $\mathcal{O}(Nd)$

Source: "Core Vector Machines: Fast SVM Training on Very Large Data Sets" - http://machinelearning.wustl.edu/mlpapers/paper_files/TsangKC05.pdf

Désolé je ne sais pas pour les autres.

samthebest
la source

O (n^{2})

$O(n^2)$

O (n^{3})

$O(n^3)$

@MarcClaesen Le lien ne fonctionne plus et il n'est pas sur la machine de retour. S'agit-il du même article: leon.bottou.org/publications/pdf/lin-2006.pdf ?

wordsforthewise