Klasifikasi pembelajaran mesin big-O atau kompleksitas

Untuk mengevaluasi kinerja algoritma klasifikasi baru, saya mencoba untuk membandingkan akurasi dan kompleksitas (big-O dalam pelatihan dan klasifikasi). Dari Machine Learning: ulasan saya mendapatkan daftar pengklasifikasi lengkap yang diawasi, juga tabel akurasi antara algoritma, dan 44 masalah pengujian dari repositoy data UCI . Namun, saya tidak dapat menemukan ulasan, kertas, atau situs web dengan big-O untuk pengklasifikasi umum seperti:

• C4.5
• RIPPER (Saya pikir ini mungkin tidak mungkin, tetapi siapa yang tahu)
• JST dengan Propagasi Balik
• Bayesian yang naif
• K-NN
• SVM

Jika ada yang punya ekspresi untuk pengklasifikasi ini, itu akan sangat berguna, terima kasih.

Misalkan = jumlah contoh pelatihan, d = dimensi fitur dan$N$$d$ = jumlah kelas.$c$

Kemudian pelatihan memiliki kompleksitas:

1. Naif Bayes adalah , yang perlu dilakukan hanyalah menghitung frekuensi setiap nilai fitur d $O(Nd)$$d_i$ untuk masing-masing kelas.
2. -NN ada di O ( 1 ) (beberapa orang bahkan mengatakan itu tidak ada, tetapi kompleksitas ruang pelatihan adalah O ( N d $k$$\mathcal{O}(1)$$\mathcal{O}(Nd)$ karena Anda perlu menyimpan data yang juga membutuhkan waktu).
3. $O(N^2)$$O(N^3)$$O(N^3)$$O(N^{2.3})$ dengan beberapa trik.
4. $O(NR)$ mana R adalah jumlah iterasi.

Kompleksitas pengujian:

1. $\mathcal{O}(cd)$$d$$c$ kelas .
2. $k$$\mathcal{O}(Nd)$ karena Anda harus membandingkan titik uji dengan setiap titik data di basis data Anda.

Sumber: "Mesin Vektor Inti: Pelatihan SVM Cepat tentang Kumpulan Data Sangat Besar" - http://machinelearning.wustl.edu/mlpapers/paper_files/TsangKC05.pdf

Maaf saya tidak tahu tentang yang lain.