Klasyfikatory uczenia maszynowego duże O lub złożoność

Aby ocenić wydajność nowego algorytmu klasyfikatora, próbuję porównać dokładność i złożoność (duże O w treningu i klasyfikacji). Z uczenia maszynowego: recenzja Otrzymuję pełną listę nadzorowanych klasyfikatorów, tabelę dokładności między algorytmami i 44 problemy testowe z repozytorium danych UCI . Nie mogę jednak znaleźć recenzji, artykułu papierowego ani strony internetowej z dużym O dla popularnych klasyfikatorów, takich jak:

• C4.5
• RIPPER (Myślę, że to może nie być możliwe, ale kto wie)
• ANN z propagacją wsteczną
• Naiwny Bayesian
• K-NN
• SVM

Jeśli ktoś ma jakieś zdanie na temat tych klasyfikatorów, będzie to bardzo przydatne, dziękuję.

Niech = liczba przykładów szkoleniowych, d = wymiarowość cech ic = liczba klas.$N$$d$$c$

Zatem szkolenie ma złożoność:

1. Naiwny Bayes to , wystarczy tylko obliczyć częstotliwość każdej wartości cechy d i dla każdej klasy.$O(Nd)$$d_i$
2. -NN znajduje się w O ( 1 ) (niektórzy twierdzą nawet, że nie istnieje, ale złożoność treningu w przestrzeni to O ( N d ), ponieważ trzeba przechowywać dane, co również wymaga czasu).$k$$\mathcal{O}(1)$$\mathcal{O}(Nd)$
3. $O(N^2)$$O(N^3)$$O(N^3)$$O(N^{2.3})$
4. $O(NR)$

Testowanie złożoności:

1. $\mathcal{O}(cd)$$d$$c$
2. $k$$\mathcal{O}(Nd)$ ponieważ musisz porównać punkt testowy z każdym punktem danych w bazie danych.

Źródło: „Podstawowe maszyny wektorowe: Szybkie szkolenie SVM na bardzo dużych zestawach danych” - http://machinelearning.wustl.edu/mlpapers/paper_files/TsangKC05.pdf

Przepraszam, nie wiem o innych.