Como medir a classificação

34

Gostaria de saber se existe uma maneira padrão de medir a "ordenação" de uma matriz? Uma matriz com o número médio de inversões possíveis seria considerada maximamente sem classificação? Com isso, quero dizer que é basicamente o mais longe possível de ser classificado ou reverso.

Robert S. Barnes
fonte

Respostas:

31

Não, isso depende da sua aplicação. As medidas de ordenação são freqüentemente chamadas de medidas de desordem , que são funções de a , onde é a coleção de todas as seqüências finitas de números inteiros não negativos distintos. A pesquisa de Estivill-Castro e Wood [1] lista e discute 11 medidas diferentes de desordem no contexto de algoritmos de classificação adaptativa. R N < NN<NRN<N

O número de inversões pode funcionar em alguns casos, mas às vezes é insuficiente. Um exemplo dado em [1] é a sequência

n/2+1,n/2+2,,n,1,,n/2

que possui um número quadrático de inversões, mas consiste apenas em duas execuções ascendentes. Está quase classificado, mas isso não é capturado por inversões.


[1] Estivill-Castro, Vladmir e Derick Wood. "Uma pesquisa de algoritmos de classificação adaptativa". Pesquisas ACM Computing (CSUR) 24.4 (1992): 441-476.

Juho
fonte
2
O contexto está tentando entender por que o quicksort tem desempenho relativamente fraco em permutações aleatórias de n elementos em que o número de inversões é próximo da mediana.
Robert S. Barnes
1
Ótimo exemplo, essa é exatamente a informação que eu estava procurando.
Robert S. Barnes
1
Estivill-Castro e madeira é A referência para este, com certeza.
Pedro Dusso
10

Mannila [1] axiomatiza a pré-classificação (com foco em algoritmos baseados em comparação) da seguinte maneira (parafraseando).

Vamos um conjunto totalmente ordenado. Então, um mapeamento de (as seqüências de elementos distintos de ) para os naturais é uma medida de pré - ordenação, se satisfizer abaixo das condições.m Σ ΣΣmΣΣ

  1. Se estiver classificado, então . m ( X ) = 0XΣm(X)=0

  2. Se com , e para todos os , então .X,YΣX=x1xnY=y1ynxi<xiyi<yji,j[1..n]m(X)=m(Y)

  3. Se é uma subsequência de Y Σ , então m ( X ) m ( Y ) .XYΣm(X)m(Y)

  4. Se para todos os i [ 1 .. | X | ] e j [ 1 .. | Y | ] para alguns X , Y Σ , então m ( X Y ) m ( X ) + m ( Y ) .xEu<yjEu[1 ..|X|]j[1 ..|Y|]X,YΣm(XY)m(X)+m(Y)

  5. para todos os X Σ e um E X .m(umaX)|X|+m(X)XΣumaEX

Exemplos de tais medidas são os

  • número de inversões,
  • número de swaps,
  • o número de elementos que não são máximos da esquerda para a direita e
  • o comprimento de uma subsequência crescente mais longa (subtraída do comprimento de entrada).

Observe que foram definidas distribuições aleatórias usando essas medidas, ou seja, que tornam as seqüências mais / menos ordenadas mais ou menos prováveis. Estes são chamados de distribuições do tipo Ewens [2, cap. 4-5; 3, exemplo 12; 4], cujo caso especial é a chamada distribuição de Mallows . Os pesos são paramétricos em uma constante e cumpremθ>0 0

.Pr(X)=θm(X)YΣΣ|X|θm(Y)

Observe como define a distribuição uniforme (para todos os m ).θ=1m

Como é possível amostrar permutações através dessas medidas de forma eficiente, esse corpo de trabalho pode ser útil na prática ao comparar os algoritmos de classificação.


  1. Medidas de Pré-Sortimento e Algoritmos de Classificação Ótima por H. Mannila (1985)
  2. Estruturas combinatórias logarítmicas: uma abordagem probabilística por R. Arratia, AD Barbour e S. Tavaré (2003)
  3. Ao adicionar uma lista de números (e outros processos determinantes dependentes de um) por A. Borodin, P. Diaconis e J. Fulman (2010)
  4. Distribuições do tipo Ewens e Análise de Algoritmos por N. Auger et al. (2016)
Rafael
fonte
3

Eu tenho minha própria definição de "ordenação" de uma sequência.

Dada qualquer sequência [a, b, c,…], a comparamos com a sequência classificada que contém os mesmos elementos, contamos o número de correspondências e a dividimos pelo número de elementos na sequência.

Por exemplo, dada sequência [5,1,2,3,4], procedemos da seguinte forma:

1) classifique a sequência: [1,2,3,4,5]

2) compare a sequência classificada com a original movendo-a uma posição de cada vez e contando o número máximo de correspondências:

        [5,1,2,3,4]
[1,2,3,4,5]                            one match

        [5,1,2,3,4]
  [1,2,3,4,5]                          no matches

        [5,1,2,3,4]
    [1,2,3,4,5]                        no matches

        [5,1,2,3,4]
      [1,2,3,4,5]                      no matches

        [5,1,2,3,4]
        [1,2,3,4,5]                    no matches

        [5,1,2,3,4]
          [1,2,3,4,5]                  4 matches

        [5,1,2,3,4]
            [1,2,3,4,5]                no matches

                ...

         [5,1,2,3,4]
                 [1,2,3,4,5]            no matches

3) O número máximo de correspondências é 4, podemos calcular a "classificação" como 4/5 = 0,8.

A classificação de uma sequência classificada seria 1 e a classificação de uma sequência com elementos colocados em ordem inversa seria 1 / n.

A idéia por trás dessa definição é estimar a quantidade mínima de trabalho que precisaríamos fazer para converter qualquer sequência na sequência classificada. No exemplo acima, precisamos mover apenas um elemento, o 5 (existem várias maneiras, mas mover 5 é o mais eficiente). Quando os elementos seriam colocados em ordem inversa, precisaríamos mover 4 elementos. E quando a sequência foi classificada, nenhum trabalho é necessário.

Espero que minha definição faça sentido.

Andrushenko Alexander
fonte
Boa ideia. Uma definição semelhante é Exc, a terceira definição de desordem no trabalho mencionado na resposta de Juho . Exc é o número de operações necessárias para reorganizar uma sequência na ordem classificada.
Apass.Jack 13/01
Bem, pode ser, acabei de aplicar meu entendimento de entropia e desordem à sequência de elementos :-)
Andrushenko Alexander 14/01
-2

Se você precisar de algo rápido e sujo (os sinais de soma me assustam), escrevi uma função de desordem super fácil em C ++ para uma classe chamada Array, que gera matrizes int preenchidas com números gerados aleatoriamente:

void Array::disorder() {
    double disorderValue = 0;
    int counter = this->arraySize;
    for (int n = 0; n < this->arraySize; n++) {
        disorderValue += abs(((n + 1) - array[n]));
//      cout << "disorderValue variable test value = " << disorderValue << endl;
        counter++;
    }
    cout << "Disorder Value = " << (disorderValue / this->arraySize) / (this->arraySize / 2) << "\n" << endl;
}

A função simplesmente compara o valor em cada elemento com o índice do elemento + 1, de modo que uma matriz na ordem inversa tenha um valor de desordem igual a 1 e uma matriz classificada com um valor de desordem igual a 0. Não sofisticado, mas funcional.

Michael

Michael Sneberger
fonte
Este não é um site de programação. Seria suficiente definir a noção de desordem e mencionar que ela pode ser calculada em tempo linear.
Yuval Filmus