Algoritmo para la calificación de la monotonía de una matriz (es decir, juzgar la "sortedness" de una matriz)

Question

---

EDITAR: Wow, muchas grandes respuestas. Sí, estoy usando esto como una función de aptitud para juzgar la calidad de un tipo realizado por un algoritmo genético. Por lo tanto el costo de la evaluación es importante (es decir, tiene que ser rápido, preferiblemente O(n).)

---

Como parte de la solicitud AI estoy jugando con, me gustaría ser capaz de evaluar un candidato una matriz de enteros basada en su monotonicidad, también conocida como "ordenada". Por el momento, estoy usando una heurística que calcula la pista más larga ordenados, y luego divide el resultado por la longitud de la matriz:

public double monotonicity(int[] array) { 
    if (array.length == 0) return 1d; 

    int longestRun = longestSortedRun(array); 
    return (double) longestRun/(double) array.length; 
} 

public int longestSortedRun(int[] array) { 

    if (array.length == 0) return 0; 

    int longestRun = 1; 
    int currentRun = 1; 

    for (int i = 1; i < array.length; i++) { 
     if (array[i] >= array[i - 1]) { 
      currentRun++; 
     } else { 
      currentRun = 1; 
     } 

     if (currentRun > longestRun) longestRun = currentRun; 
    } 

    return longestRun; 
} 

Este es un buen comienzo, pero no tiene en cuenta la posibilidad que puede haber "grupos" de subsecuencias clasificadas. Por ejemplo:

{ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9} 

Esta matriz está dividida en tres subsecuencias ordenadas. Mi algoritmo lo calificará como solo el 40% ordenado, pero intuitivamente, debería obtener una puntuación más alta que eso. ¿Hay un algoritmo estándar para este tipo de cosas?

Answer 1

Espero que la elección de la función que se va a utilizar dependa en gran medida de la intención de su uso. Según su pregunta, supongo que está utilizando un sistema genético para crear un programa de clasificación, y esta es la función de clasificación. Si ese es el caso, entonces la velocidad de ejecución es crucial. Basado en eso, apuesto a que su algoritmo de subsecuencia ordenada más larga funcionaría bastante bien. Eso suena como que debería definir la aptitud bastante bien.

Answer 2

Este parece ser un buen candidato para Levenshtein Damerau–Levenshtein distancia - el número de permutas necesarias para ordenar la matriz. Esto debería ser proporcional a qué tan lejos está cada elemento de donde debería estar en una matriz ordenada.

Aquí hay un algoritmo simple de ruby ​​que suma los cuadrados de las distancias. Parece una buena medida de clasificación: el resultado se reduce cada vez que se intercambian dos elementos fuera de servicio.

ap = a.sort 
sum = 0 
a.each_index{|i| j = ap.index(a[i])-i 
    sum += (j*j) 
} 
dist = sum/(a.size*a.size) 

Answer 3

¿Te gustan estos? http://en.wikipedia.org/wiki/Rank_correlation

Answer 4

Sugeriría mirar el Pancake Problem y la distancia de inversión de las permutaciones. Estos algoritmos se usan a menudo para encontrar la distancia entre dos permutaciones (la Identidad y la cadena permutada). Esta medida de distancia debería tener en cuenta más grupos de valores de orden, así como reversiones (disminuyendo monótonamente en lugar de subsecuencias crecientes). También hay approximations that are polynomial time[PDF].

Realmente todo depende de lo que signifique el número y si esta función de distancia tiene sentido en su contexto.

Answer 5

Depende en gran medida de lo que pretenda usar la medida, pero una manera fácil de hacerlo es alimentar la matriz en un algoritmo de clasificación estándar y medir cuántas operaciones (intercambios y/o comparaciones) necesitan hacerse para ordenar la matriz.

Answer 6

Aquí hay una que acabo de inventar.

Para cada par de valores adyacentes, calcule la diferencia numérica entre ellos.Si el segundo es mayor o igual que el primero, agréguelo al total de sorted, de lo contrario, agréguelo al total de unsorted. Cuando termine, tome la proporción de los dos.

Answer 7

Calcule las longitudes de todas las subsecuencias ordenadas, luego cuadre y añádalas. Si desea calibrar cuánto énfasis pone en el más grande, use una potencia diferente a 2.

No estoy seguro de cuál es la mejor manera de normalizar esto por la longitud, tal vez dividirla por la longitud al cuadrado?

Answer 8

Algunos experimentos con un modificador de Ratcliff & Obershelp

>>> from difflib import SequenceMatcher as sm 
>>> a = [ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9 ] 
>>> c = [ 0, 1, 9, 2, 8, 3, 6, 4, 7, 5 ] 
>>> b = [ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9 ] 
>>> b.sort() 
>>> s = sm(None, a, b) 
>>> s.ratio() 
0.69999999999999996 
>>> s2 = sm(None, c, b) 
>>> s2.ratio() 
0.29999999999999999 

Así que tipo de hace lo que tiene a. Sin embargo, no estoy muy seguro de cómo demostrarlo.

Answer 9

Lo que probablemente esté buscando es Kendall Tau. Es una función uno a uno de la distancia de ordenación de burbuja entre dos matrices. Para probar si una matriz está "casi ordenada", calcule su Kendall Tau contra una matriz ordenada.

Answer 10

Tengo el mismo problema (puntuación de monotonicidad), y le sugiero que pruebe Longest Increasing Subsequence. El algoritmo más eficiente ejecutado en O(n log n), no está tan mal.

Tomando el ejemplo de la pregunta, la secuencia que aumenta más tiempo de {4, 5, 6, 0, 1, 2, 3, 7, 8, 9} es {0, 1, 2, 3, 7, 8, 9} (longitud de 7). Tal vez califique mejor (70%) que su algoritmo de ejecución ordenada más larga.

Answer 11

¿Qué le parece contar el número de pasos con el aumento del valor frente al número total de pasos? Eso es O(n).