algorithm - algoritmos de clasificacion machine learning

¿Qué algoritmo de clasificación funciona mejor en la mayoría de los datos ordenados? (20)

¿Qué algoritmo de clasificación funciona mejor en la mayoría de los datos ordenados?

timsort

Timsort es "un mergesort adaptable, estable y natural" con " rendimiento sobrenatural en muchos tipos de matrices parcialmente ordenadas (menos de lg (N!) Comparaciones necesarias, y tan solo N-1)". La sort() incorporada de Python sort() ha usado este algoritmo por algún tiempo, aparentemente con buenos resultados. Está específicamente diseñado para detectar y aprovechar subsecuencias parcialmente ordenadas en la entrada, que a menudo ocurren en conjuntos de datos reales. En el mundo real, a menudo ocurre que las comparaciones son mucho más costosas que el intercambio de elementos en una lista, ya que uno simplemente intercambia punteros, lo que a menudo hace que el timsort sea una excelente opción. Sin embargo, si usted sabe que sus comparaciones son siempre muy económicas (por ejemplo, escribir un programa de juguete para clasificar enteros de 32 bits), existen otros algoritmos que probablemente tengan un mejor rendimiento. La forma más fácil de tomar ventaja de timsort es, por supuesto, usar Python, pero dado que Python es de código abierto, también es posible que pueda tomar prestado el código. Alternativamente, la descripción anterior contiene detalles más que suficientes para escribir su propia implementación.

Basado en el método altamente científico de ver gifs animados , diría que los tipos de Inserción y Burbuja son buenos candidatos.

Como todos dijeron, tenga cuidado con Quicksort ingenuo, que puede tener un rendimiento O (N ^ 2) en datos clasificados o casi ordenados. Sin embargo, con un algoritmo apropiado para la elección del pivote (ya sea al azar o en la mediana de tres, consulte Elección de un pivote para Quicksort ), Quicksort seguirá funcionando correctamente.

En general, la dificultad de elegir algoritmos como insertar ordenado es decidir cuándo los datos están lo suficientemente fuera de servicio que Quicksort realmente sería más rápido.

El smoothsort de Dijkstra es excelente para los datos ya ordenados. Es una variante heatsort que se ejecuta en O (n lg n) en el peor de los casos y O (n) en el mejor de los casos. Escribí un análisis del algoritmo, en caso de que tenga curiosidad sobre cómo funciona.

Natural mergesort es otro muy bueno para esto: es una variante de mergesort bottom-up que funciona tratando la entrada como la concatenación de múltiples rangos ordenados diferentes, y luego usando el algoritmo de combinación para unirlos. Repita este proceso hasta que todo el rango de entrada esté ordenado. Esto se ejecuta en O (n) tiempo si los datos ya están ordenados y O (n lg n) en el peor de los casos. Es muy elegante, aunque en la práctica no es tan bueno como otros tipos adaptativos como Timsort o smoothsort.

El tipo de burbuja (o, más seguro, tipo de burbuja bidireccional) es ideal para las listas ordenadas en su mayoría, aunque apuesto a que un tipo de peine ajustado (con un tamaño de hueco inicial mucho más bajo) sería un poco más rápido cuando la lista no fuera Es tan perfectamente ordenado. Comb sort se degrada a bubble-sort.

El tipo de burbuja es definitivamente el ganador El siguiente en el radar sería el tipo de inserción.

El tipo de inserción es el mejor de los casos O (n) en la entrada ordenada. Y está muy cerca de la entrada principalmente ordenada (mejor que la clasificación rápida).

Esta bonita colección de algoritmos de clasificación para este propósito en las respuestas parece carecer de Gnome Sort , que también sería adecuada y probablemente requiera el menor esfuerzo de implementación.

La ordenación por inserción lleva tiempo O (n + el número de inversiones).

Una inversión es un par (i, j) tal que i < j && a[i] > a[j] . Es decir, un par fuera de servicio.

Una medida de estar "casi ordenado" es el número de inversiones, uno podría tomar "datos casi ordenados" para significar datos con pocas inversiones. Si uno sabe que el número de inversiones es lineal (por ejemplo, acaba de agregar O (1) elementos a una lista ordenada), la ordenación por inserción toma O (n) la hora.

Manténgase alejado de QuickSort: es muy ineficiente para los datos previamente ordenados. El tipo de inserción maneja bien los datos casi ordenados moviendo la menor cantidad de valores posible.

No voy a pretender tener todas las respuestas aquí, porque creo que obtener las respuestas reales puede requerir la codificación de los algoritmos y su perfil contra muestras de datos representativos. Pero he estado pensando en esta pregunta toda la noche, y esto es lo que se me ocurrió hasta ahora, y algunas conjeturas sobre qué funciona mejor dónde.

Deje N ser el número total de elementos, M sea el número fuera de orden.

La clasificación de burbujas tendrá que hacer que algo como 2 * M + 1 pase por todos los N elementos. Si M es muy pequeño (0, 1, 2?), Creo que será muy difícil de superar.

Si M es pequeño (digamos menos que log N), la ordenación de inserción tendrá un gran rendimiento promedio. Sin embargo, a menos que haya un truco que no estoy viendo, tendrá muy mal desempeño en el peor de los casos. (¿Verdad? Si el último elemento del pedido es lo primero, entonces tienes que insertar cada elemento, por lo que puedo ver, lo que matará el rendimiento.) Supongo que hay un algoritmo de clasificación más confiable para este caso, pero no sé lo que es

Si M es más grande (digamos igual o mayor que log N), el tipo introspectivo es casi seguro el mejor.

Excepción a todo eso: si realmente sabe con anticipación qué elementos no están clasificados, entonces la mejor opción será sacar esos elementos, clasificarlos usando clasificación introspectiva y combinar las dos listas ordenadas en una lista ordenada. Si pudieras descubrir rápidamente qué elementos están desordenados, esta también sería una buena solución general, pero no he podido encontrar una forma sencilla de hacerlo.

Otros pensamientos (durante la noche): si M + 1 <N / M, entonces puede escanear la lista buscando una corrida de N / M en una fila que esté ordenada, y luego expandir esa carrera en cualquier dirección para encontrar la salida -encargar artículos. Eso tomará como máximo 2N comparaciones. Luego puede ordenar los elementos sin clasificar y hacer una combinación ordenada en las dos listas. Las comparaciones totales deberían ser inferiores a algo así como 4N + M log2 (M), que va a superar cualquier rutina de clasificación no especializada, creo. (Aún más pensado: esto es más complicado de lo que pensaba, pero todavía creo que es razonablemente posible).

Otra interpretación de la pregunta es que puede haber muchos artículos fuera de orden, pero están muy cerca de donde deberían estar en la lista. (Imagínese comenzar con una lista ordenada e intercambiar cada otro artículo con el que viene después). En ese caso, creo que el tipo de burbuja funciona muy bien. Creo que el número de pases será proporcional al más alejado de un elemento. es. La ordenación por inserción funcionará mal, porque cada elemento fuera de servicio activará una inserción. Sospecho que tipo introspectivo o algo así también funcionará bien.

Prueba el tipo introspectivo. http://en.wikipedia.org/wiki/Introsort

Está basado en la oferta rápida, pero evita el peor comportamiento de caso que tiene la vía rápida para listas casi ordenadas.

El truco es que este algoritmo de clasificación detecta los casos en los que la vía rápida entra en el modo del peor de los casos y cambia a la ordenación por acumulación o fusión. Las particiones casi ordenadas se detectan mediante un método de partición no ingenuo y las particiones pequeñas se manejan mediante la ordenación por inserción.

Obtienes lo mejor de todos los principales algoritmos de clasificación por el costo de un código y una complejidad mayores. Y puede estar seguro de que nunca se encontrará con el peor comportamiento posible, sin importar el aspecto de sus datos.

Si usted es un programador de C ++ verifique su algoritmo std :: sort. Puede que ya use el tipo introspectivo internamente.

Si los elementos ya están ordenados o si solo hay unos pocos elementos, sería un caso de uso perfecto para Insertion Sort!

Si necesita una implementación específica para clasificar algoritmos, estructuras de datos o cualquier otra cosa que tenga un enlace al anterior, ¿podría recomendarle el excelente proyecto de "Estructuras de datos y algoritmos" en CodePlex?

Tendrá todo lo que necesita sin reinventar la rueda.

Solo mi pequeño grano de sal.

Solo unos pocos elementos => INSERTION SORT

Los artículos ya están ordenados en su mayoría => INSERTION SORT

Preocupado por los peores escenarios => HEAP SORT

Interesado en un buen resultado promedio de caso => QUICKSORT

Los elementos se extraen de un universo denso => BUCKET SORT

Deseo escribir el menor código posible => INSERTION SORT

Tipo de inserción con el siguiente comportamiento:

Para cada elemento k en las ranuras 1..n , primero compruebe si el[k] >= el[k-1] . Si es así, ve al siguiente elemento. (Obviamente omita el primer elemento).
De lo contrario, utilice la búsqueda binaria en los elementos 1..k-1 para determinar la ubicación de inserción y luego deslice los elementos hacia arriba. (Puede hacer esto solo si k>T donde T es algún valor de umbral, con k pequeña esto es excesivo).

Este método hace el menor número de comparaciones.

bien, depende del caso de uso. Si sabes qué elementos se cambian, eliminar e insertar será el mejor caso en lo que a mí respecta.

inserción o tipo de concha!

Splaysort es un método de clasificación oscuro basado en árboles de cobertura , un tipo de árbol binario adaptativo. Splaysort es bueno no solo para los datos parcialmente ordenados, sino también para los datos parcialmente revertidos o, de hecho, para cualquier información que tenga algún tipo de orden preexistente. Es O (nlogn) en el caso general, y O (n) en el caso en que los datos se ordenan de alguna manera (avance, retroceso, organodubo, etc.).

Su gran ventaja sobre el ordenamiento de inserción es que no revierte al comportamiento O (n ^ 2) cuando los datos no están ordenados del todo, por lo que no es necesario estar absolutamente seguro de que los datos estén parcialmente ordenados antes de usarlo. .

Su desventaja es la sobrecarga de espacio adicional de la estructura de árbol desplegable que necesita, así como también el tiempo requerido para construir y destruir el árbol desplegable. Pero dependiendo del tamaño de los datos y la cantidad de preordenada que espere, la sobrecarga puede valer la pena por el aumento de la velocidad.

Se publicó un documento sobre splaysort en Software - Practice & Experience.

reflexiona Prueba Heap. Creo que es el más consistente de los tipos O (n lg n).