Algoritmos para calcular a mediana em execução?

18

Em tamanhos de janela menores, a n log nclassificação pode funcionar. Existem algoritmos melhores para conseguir isso?

miku
fonte
1
Acho que este é o primeiro candidato a ser movido para o estouro de pilha.
Possivelmente, mas precisaria de muito mais explicações sobre SO.
WalkyTalky
2
A maioria dos programadores sabe "mediana". (sort (array)) [length / 2] é uma dica grande o suficiente para quem esqueceu. Também na sua forma mais básica para cada novo ponto, você só precisa fazer uma bissecção / inserção em uma metade da matriz ... #
Paul
1
Reaberto
Rob Hyndman
2
Muito trivial para ser mais do que um comentário, mas o código para a mediana de 3s é apenas a + b + c - max (a, b, c) - min (a, b. C). Isso funciona bem mesmo se houver laços. Isso ficou óbvio para mim uma vez que eu pensei sobre isso no código de outra pessoa (por que ele (neste caso) está adicionando e subtraindo para obter uma mediana ???) e alguns outros podem ter a mesma reação. max () e min () são frequentemente implementados como funções super-rápidas. Infelizmente, não existe esse truque em geral.
Nick Cox

Respostas:

11

É uma má forma classificar uma matriz para calcular uma mediana. As medianas (e outros quantis) são tipicamente calculadas usando o algoritmo de seleção rápida, com complexidade .O(n)

Você também pode consultar minha resposta a uma pergunta relacionada recente aqui .

user603
fonte
7

Aqui está um artigo descrevendo um possível algoritmo. Código fonte incluído e uma aplicação bastante séria (detecção de ondas gravitacionais baseada em interferometria a laser), para que você possa esperar que seja bem testado.

Łukasz Lew
fonte
1
O link está quebrado e, sem as informações de título ou autor, é difícil encontrar o que ele se refere.
Kristopher Johnson
6

Se você deseja tolerar uma aproximação, existem outros métodos. Por exemplo, uma aproximação é um valor cuja classificação está a uma distância (especificada pelo usuário) da mediana verdadeira. Por exemplo, a mediana classificou (normalizou) 0,5 e, se você especificar um termo de erro de 10%, deseja uma resposta com classificação entre 0,45 e 0,55.

Se essa resposta for apropriada, existem muitas soluções que podem funcionar em janelas deslizantes de dados. A idéia básica é manter uma amostra dos dados de um determinado tamanho (aproximadamente 1 / termo de erro) e calcular a mediana nessa amostra. Pode-se mostrar que, com alta probabilidade, independentemente da natureza da entrada, a mediana resultante satisfaz as propriedades que mencionei acima.

Assim, a questão principal é como manter uma amostra contínua de dados de um determinado tamanho, e existem muitas abordagens para isso, incluindo a técnica conhecida como amostragem de reservatório. Por exemplo, este artigo: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7136

Suresh Venkatasubramanian
fonte
4

Se você mantiver uma janela de comprimento k de dados como uma lista duplamente vinculada classificada, por meio de uma pesquisa binária (para inserir cada novo elemento à medida que é deslocado para a janela) e uma matriz circular de ponteiros (para localizar imediatamente elementos que precisam ser excluídos), cada deslocamento da janela requer um esforço O (log (k)) para inserir um elemento, apenas um esforço O (1) para excluir o elemento deslocado para fora da janela e apenas um esforço O (1) para encontrar a mediana (porque toda vez que um elemento é inserido ou excluído da lista, você pode atualizar um ponteiro para a mediana no tempo O (1)). O esforço total para processar uma matriz de comprimento N, portanto, é O ((nk) log (k)) <= O (n log (k)). Isso é melhor do que qualquer outro método proposto até o momento e não é uma aproximação, é exato.

whuber
fonte
1
Você poderia elaborar como propõe fazer uma pesquisa binária em uma lista classificada duplamente vinculada?
NPE 28/11
um 'link' permite percorrer a lista em ordem de classificação; o outro permite percorrer na ordem em que os elementos aparecem. Não está claro como você faria isso com ponteiros, no entanto, como perguntas do @aix.
shabbychef
2
@aix Acho que sua sugestão está correta; Eu precisaria de uma lista de pulos indexáveis, não apenas de uma lista duplamente vinculada classificada. A idéia é ter uma estrutura de dados que permita a inserção de um elemento, a exclusão de um elemento e a localização da mediana no tempo esperado O (log (n)) (ou melhor).
whuber
3

Como você mencionou, a classificação seria O(n·log n)para uma janela de comprimento n. Fazer essa mudança adiciona outra que l=vectorlengthfaz o custo total O(l·n·log n).

A maneira mais simples de fazer isso é manter uma lista ordenada dos últimos n elementos na memória ao passar de uma janela para a seguinte. Como remover / inserir um elemento de / em uma lista ordenada, ambos O(n)resultariam em custos de O(l·n).

Pseudo-código:

l = length(input)
aidvector = sort(input(1:n))
output(i) = aid(n/2)
for i = n+1:l
    remove input(i-n) from aidvector
    sort aid(n) into aidvector
    output(i) = aid(n/2)
ymihere
fonte
2

Se você pode viver com uma estimativa em vez da mediana verdadeira, o Algoritmo Remediano (PDF) é uma passagem com baixos requisitos de armazenamento e precisão bem definida.

O remédio com base b prossegue calculando medianas de grupos de observações b e, em seguida, medianas dessas medianas, até que apenas uma única estimativa permaneça. Este método apenas precisa de k matrizes de tamanho b (onde n = b ^ k) ...

sapatilha
fonte
0

Eu usei esta biblioteca RunningStats C ++ em um aplicativo incorporado. É a biblioteca de estatísticas em execução mais simples que encontrei ainda.

No link:

O código é uma extensão do método de Knuth e Welford para calcular o desvio padrão em uma passagem pelos dados. Ele calcula assimetria e curtose, também com uma interface semelhante. Além de exigir apenas uma passagem pelos dados, o algoritmo é numericamente estável e preciso.

Chris K
fonte
Essa página diz algo sobre mediana?
Musiphil 20/11/2015