Clasificadores de aprendizaje automático big-O o complejidad

Question

Para evaluar el rendimiento de un nuevo algoritmo clasificador, intento comparar la precisión y la complejidad (big-O en entrenamiento y clasificación). En Aprendizaje automático: una revisión Obtengo una lista completa de clasificadores supervisados, también una tabla de precisión entre los algoritmos, y 44 problemas de prueba de Depósito de datos de la UCI . Sin embargo, no puedo encontrar una revisión, documento o sitio web con la gran-O para clasificadores comunes como:

• C4.5
• RIPPER (Creo que esto podría no ser posible, pero quién sabe)
• RNA con retropropagación
• Bayesiano ingenuo
• K-NN
• SVM

Si alguien tiene alguna expresión para estos clasificadores, será muy útil, gracias.

Answer 1

Sea $N$ = número de ejemplos de entrenamiento, $d$ = dimensionalidad de las características y $c$ = número de clases.

Luego la formación tiene complejidades:

1. Naive Bayes es $O(Nd)$ todo lo que tiene que hacer es calcular la frecuencia de cada valor de característica $d_i$ para cada clase.
2. $k$ -NN está en $\mathcal{O}(1)$ (algunos incluso dicen que es inexistente, pero la complejidad espacial de la formación es $\mathcal{O}(Nd)$ ya que hay que almacenar los datos, lo que también lleva tiempo).
3. La SVM no lineal no aproximada es $O(N^2)$ o $O(N^3)$ dependiendo del núcleo. Puede obtener un $O(N^3)$ hasta $O(N^{2.3})$ con algunos trucos.
4. La SVM aproximada es $O(NR)$ donde R es el número de iteraciones.

Complejidad de las pruebas:

1. Naive Bayes está en $\mathcal{O}(cd)$ ya que tiene que recuperar $d$ valores de las características de cada $c$ clases.
2. $k$ -NN está en $\mathcal{O}(Nd)$ ya que tiene que comparar el punto de prueba con cada punto de datos de su base de datos.

Fuente: "Core Vector Machines: Entrenamiento rápido de SVM en conjuntos de datos muy grandes" - http://machinelearning.wustl.edu/mlpapers/paper_files/TsangKC05.pdf

Lo siento, no sé nada de los demás.