Algoritmo para avaliar a monotonicidade de uma matriz (ou seja,julgando a “classificação” de um array)

Question

---

EDITAR:Uau, muitas ótimas respostas.Sim, estou usando isso como uma função de aptidão para julgar a qualidade de uma classificação realizada por um algoritmo genético.Portanto, o custo da avaliação é importante (ou seja, tem que ser rápido, de preferência O(n).)

---

Como parte de um aplicativo de IA com o qual estou brincando, gostaria de poder avaliar uma matriz candidata de números inteiros com base em sua monotonicidade, também conhecida como sua "classificação".No momento, estou usando uma heurística que calcula a execução classificada mais longa e depois divide pelo comprimento da 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 é um bom começo, mas não leva em conta a possibilidade de haver "aglomerados" de subsequências classificadas.Por exemplo.:

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

Esta matriz é particionada em três subsequências classificadas.Meu algoritmo irá classificá-lo como apenas 40% classificado, mas intuitivamente, deve obter uma pontuação mais alta do que essa.Existe um algoritmo padrão para esse tipo de coisa?

Answer 1

Espero que a escolha da função a ser usada dependa muito fortemente do que você pretende usá -lo. Com base na sua pergunta, eu acho que você está usando um sistema genético para criar um programa de classificação, e essa deve ser a função de classificação. Se for esse o caso, a velocidade de execução é crucial. Com base nisso, aposto que o seu algoritmo de subseqüência mais antigo funcionaria muito bem. Parece que deve definir muito bem a aptidão.

Answer 2

Isso parece um bom candidato para Levenshtein Damerau - Levenshtein Distância - o número de swaps necessários para classificar a matriz. Isso deve ser proporcional a quão longe cada item está de onde deve estar em uma matriz classificada.

Aqui está um algoritmo de rubi simples que resume os quadrados das distâncias. Parece uma boa medida de classificação-o resultado fica menor toda vez que dois elementos fora de ordem são trocados.

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

Algo como estes? http://en.wikipedia.org/wiki/Rank_Correlation

Answer 4

Aqui está um que acabei de inventar.

Para cada par de valores adjacentes, calcule a diferença numérica entre eles. Se o segundo for maior ou igual ao primeiro, adicione isso ao sorted Total, de outra forma, adicione ao unsorted total. Quando terminar, tome a proporção dos dois.

Answer 5

Calcule os lenghts de todas as sub-seqüências classificadas, depois os coloque e adicione-os. Se você deseja calibrar a quantidade de enphasis que você coloca na maior, use uma potência diferente de 2.

Não tenho certeza de qual é a melhor maneira de normalizar isso por comprimento, talvez dividi -lo por comprimento ao quadrado?

Answer 6

O que você provavelmente está procurando é Kendall Tau. É uma função individual da distância de classificação da bolha entre duas matrizes. Para testar se uma matriz é "quase classificada", calcule seu Kendall Tau contra uma matriz classificada.

Answer 7

Eu sugeriria olhar para o Problema da panqueca e a distância de reversão das permutações.Esses algoritmos são frequentemente usados ​​para encontrar a distância entre duas permutações (a identidade e a string permutada).Esta medida de distância deve levar em consideração mais grupos de valores ordenados, bem como reversões (diminuindo monotonicamente em vez de subsequências crescentes).Há também aproximações que são tempo polinomial[PDF].

Na verdade, tudo depende do que o número significa e se essa função de distância faz sentido no seu contexto.

Answer 8

Eu tenho o mesmo problema (pontuação de monotonicidade) e sugiro que você tente Subseqüência crescente mais longa. O algoritmo mais eficiente é executado O(n log n), não é tão ruim.

Exemplo da pergunta, a sequência mais crescente de {4, 5, 6, 0, 1, 2, 3, 7, 8, 9} é {0, 1, 2, 3, 7, 8, 9} (comprimento de 7). Talvez ele avalie melhor (70%) do que o seu algoritmo de punção mais longo.

Answer 9

Depende muito do que você pretende usar a medida, mas uma maneira fácil de fazer isso é alimentar a matriz em um algoritmo de classificação padrão e medir quantas operações (swaps e/ou comparações) precisam ser feitas para classificar para classificar a matriz.

Answer 10

Algumas experiências com um modificador 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

Então, meio que faz o que precisa. Não tenho muita certeza de como provar isso.

Answer 11

Que tal contar o número de etapas com o aumento do valor versus o número do total de etapas. Isso é O(n).