Como calcular ou aproximar a mediana de uma lista sem armazenar a lista

Question

Eu estou tentando calcular a média de um conjunto de valores, mas eu não quero para armazenar todos os valores como que poderia explodir os requisitos de memória. Existe uma maneira de calcular ou aproximar a mediana sem armazenar e classificar todos os valores individuais?

Idealmente, eu gostaria de escrever meu código um pouco parecido com o seguinte

var medianCalculator = new MedianCalculator();
foreach (var value in SourceData)
{
  medianCalculator.Add(value);
}
Console.WriteLine("The median is: {0}", medianCalculator.Median);

Tudo que eu preciso é o código MedianCalculator real!

Update: Algumas pessoas têm perguntado se os valores que eu estou tentando calcular a mediana para ter propriedades conhecidas. A resposta é sim. Um valor é em incrementos de 0,5 a partir de cerca de -25 a -0,5. O outro também é em incrementos de 0,5 a partir de -120 a -60 ° C. Acho que isso significa que eu posso usar alguma forma de histograma para cada valor.

Graças

Nick

Answer 1

Se os valores são discretos e o número de valores distintos não é muito alta, você só poderia acumular o número de vezes que cada valor ocorre em um histograma, em seguida, encontrar a mediana das contagens de histograma (apenas somar as contagens do parte superior e inferior do histograma até chegar ao meio). Ou se eles são valores contínuos, você pode distribuí-los em caixas - que não iria dizer-lhe a mediana exata, mas que lhe daria um intervalo, e se você precisa saber mais precisamente você pode iterar sobre a lista novamente, examinando única os elementos no bin central.

Answer 2

Não é a estatística 'remedian'. Ele funciona por primeira criação matrizes k de comprimento, cada b. Os valores de dados são alimentados para a primeira matriz e, quando esta estiver cheia, a mediana é calculado e armazenado nos primeiros pos da seguinte matriz, após o que a primeira matriz é re-utilizado. Quando a segunda matriz é cheio a mediana dos seus valores são armazenados nos primeiros pos da terceira série, etc. etc. Você começa a idéia:)

É simples e bastante robusto. A referência é aqui ...

http://web.ipac.caltech.edu/ pessoal / fmasci / home / astro_refs / Remedian.pdf

Espero que isso ajude

Michael

Answer 3

Eu uso esses estimadores de média e mediana incrementais / recursivo, que tanto o armazenamento uso constante:

mean += eta * (sample - mean)
median += eta * sgn(sample - median)

onde eta é um parâmetro pequena taxa de aprendizagem (por exemplo, de 0,001), e sgn () é a função de signum que retorna um de {-1, 0, 1}.

Este tipo de estimador de média incrementais parece ser usado em todo o lugar, por exemplo, em regras sem supervisão de aprendizagem da rede neural, mas a versão mediana parece muito menos comum, apesar de seus benefícios (robustez a outliers). Parece que a versão mediana poderia ser usado como um substituto para o estimador de média em muitas aplicações.

Eu adoraria ver um estimador modo incremental de uma forma semelhante ...

(Nota: Eu também postei isso a um tópico semelhante aqui: " on-line"(iterador) algoritmos para a estimativa mediana de estatísticas, modo, assimetria, curtose? )

Answer 4

Aqui está uma abordagem louca que você pode tentar. Este é um problema clássico em streaming de algoritmos. As regras são

1. Você tem memória limitada, digamos O(log n) onde n é o número de itens que você deseja
2. Você pode olhar para cada item uma vez e tomar uma decisão e então aí o que fazer com ele, se você armazená-lo, custa memória, se você jogá-lo fora é ido para sempre.

A idéia para a encontrar uma mediana é simples. elementos O(1 / a^2 * log(1 / p)) * log(n) amostra da lista de forma aleatória, você pode fazer isso via reservatório de amostragem (veja a anterior pergunta ). Agora, basta voltar a mediana dos seus elementos amostrados, usando um método clássico.

A garantia é que o índice do item retornado será (1 +/- a) / 2 com probabilidade pelo menos 1-p. Portanto, há uma probabilidade p de falhar, você pode escolhê-lo por amostragem mais elementos. E ele não vai voltar a mediana ou garantia de que o valor do item devolvido é em qualquer lugar perto da mediana, só que quando você classificar a lista o item devolvido será perto da metade da lista.

Este algoritmo utiliza O(log n) espaço adicional e é executado em tempo linear.

Answer 5

Esta é complicado de acertar em geral, especialmente para lidar com séries degenerados que já estão classificados, ou tem um monte de valores para o "start" da lista, mas o fim da lista tem valores em um intervalo diferente.

A idéia básica de fazer um histograma é mais promissora. Isso permite que você acumular informações distribuição e consultas de resposta (como mediana) a partir dele. A mediana será aproximado desde que, obviamente, não armazenar todos os valores. O espaço de armazenamento é fixo para que ele irá trabalhar com qualquer seqüência de comprimento que você tem.

Mas você não pode simplesmente construir um histograma de dizer os primeiros 100 valores e usar isso histograma continuamente .. os dados de mudança pode fazer essa inválido histograma. Então você precisa de um histograma dinâmico que pode mudar a sua gama e caixas na mosca.

Faça uma estrutura que tem caixas N. Poderá armazenar o valor X de cada transição ranhura (N + 1 valores totais) assim como a população de lixo.

Córrego em seus dados. Registam-se os primeiros valores de N + 1. Se as extremidades fluxo antes disso, grande, você tem todos os valores carregados e você pode encontrar a mediana exata e devolvê-lo. Então usar os valores para definir o seu primeiro histograma. Apenas uma espécie os valores e utilizá-las como definições de lixo, cada bin ter uma população de 1. É aprovado tem dupes (0 caixas de largura).

Agora transmitir novos valores. Para cada um, a pesquisa binária para encontrar o bin que pertence. No caso comum, você apenas incrementar a população de que Bin e continuar. Se a sua amostra está além das bordas do histograma (maior ou menor), basta aumentar o alcance da bin fim de incluí-lo. Quando o fluxo é feito, você encontrar o valor mediano da amostra por encontrar o bin que tem população igual em ambos os lados da mesma, e linearmente interpolando a bin de largura restante.

Mas isso não é o suficiente .. você ainda necessidade de adaptar o histograma para os dados como ele está sendo transmitido. Quando uma bin fica mais cheio, você está perdendo informações sobre a distribuição sub desse bin. Você pode corrigir isso através da adaptação baseada em alguma heurística ... o mais fácil e mais robusto é se um bin atinge alguns determinada população limiar (algo como 10 * v / N, onde v = # de valores visto até agora na corrente, e N é o número de caixas), você dividir esse bin overfull. Adicione um novo valor no ponto médio da caixa, dar a cada lado metade da população bin originais. Mas agora você tem muitas caixas, então você precisa para apagar um bin. Uma boa heurística para isso é encontrar o bin com o menor produto da população e largura. Apagá-lo e fundi-lo com o seu vizinho esquerda ou à direita (o que um dos vizinhos em si tem o menor produto da largura e da população.). Feito! Note-se que a fusão ou divisão caixas perde informações, mas isso é inevitável .. você só tem de armazenamento fixo.

Este algoritmo é bom na medida em que vai lidar com todas tipos de fluxos de entrada e dar bons resultados. Se você tem o luxo de escolher a ordem da amostra, uma amostra aleatória é melhor, uma vez que minimiza cisões e fusões.

O algoritmo também permite consultar qualquer percentil, não apenas mediano, desde que você tem uma estimativa de distribuição completa.

Eu uso este método no meu próprio código em muitos lugares, principalmente para depuração de registros .. onde algumas estatísticas que você está gravando tem distribuição desconhecida. Com este algoritmo você não precisa adivinhar antes do tempo.

A desvantagem é o desigual meios larguras bin você tem que fazer uma pesquisa binária para cada amostra, para que o seu algoritmo de líquido é O (n log n).

Answer 6

Eu não acho que é possível fazer sem ter a lista na memória. Você pode, obviamente, aproximar com

• média se você sabe que os dados são distribuídos simetricamente
• ou calcular uma média adequada de um pequeno subconjunto de dados (que pode guardar na memória) - se você sabe que seus dados tem a mesma distribuição em toda a amostra (por exemplo, que o primeiro item tem a mesma distribuição como o último)

Answer 7

A sugestão de David parece ser a abordagem mais sensata para aproximar a mediana.

A correr média para o mesmo problema é muito mais fácil de calcular:

H _n = M _n-1 + ((V _n - H _n-1 ) / n)

Quando M _n é a média de n valores, H _n-1 é a média anterior, e V _n é o novo valor .

Em outras palavras, a nova média é a média existente mais a diferença entre o novo valor ea média, dividida pelo número de valores.

No código esta seria algo parecido com:

new_mean = prev_mean + ((value - prev_mean) / count)

embora, obviamente, você pode querer considerar o material específico do idioma como ponto flutuante arredondamento erros etc.

Answer 8

Encontre Min e Max da lista que contém itens N através de pesquisa linear e nomeá-los como de alto valor e reduzido valor Deixe MedianIndex = (N + 1) / 2

1ª ordem binária Pesquisa:

Repita as seguintes 4 passos até reduzido valor

1. Obter aproximadamente MedianValue = (+ alto valor reduzido valor) / 2

2. Get NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

3. é K = MedianIndex, em seguida, retornar MedianValue

4. é K> MedianIndex? em seguida, de alto valor = MedianValue Else reduzido valor = MedianValue

Será mais rápido sem consumir memória

2ª ordem binária Pesquisa:

LowIndex = 1 HighIndex = N

Repetir Após 5 etapas até (LowIndex

1. Obter DistrbutionPerUnit aproximado = (de alto valor-reduzido valor) / (HighIndex-LowIndex)

2. Obter aproximado MedianValue = reduzido valor + (MedianIndex-LowIndex) * DistributionPerUnit

3. Get NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

4. é (K = MedianIndex)? retorno MedianValue

5. é (K> MedianIndex)? em seguida, HighIndex = K e de alto valor = MedianValue LowIndex Else = K e reduzido valor = MedianValue

Será mais rápido do que 1ª ordem sem consumir memória

Nós também podemos pensar em ajuste de alto valor, reduzido valor e MedianValue com HighIndex, LowIndex e MedianIndex para uma parábola, e pode obter ThirdOrder binário Pesquisa que será mais rápido do que 2 fim sem consumir memória e assim por diante ...

Answer 9

Normalmente, se a entrada está dentro de um determinado intervalo, digamos 1 para 1 milhão, é fácil criar uma matriz de contagens: ler o código para "quantil" e "ibucket" aqui: http://code.google.com/p/ea-utils/source/ Navegar / trunk / clipper / sam-stats.cpp

Esta solução pode ser generalizado como uma aproximação por coagir a entrada em um número inteiro dentro de alguns gama usando uma função que lhe então inverter na saída: IE: foo.push ((int) de entrada / 1000000) e quantil (foo ) * 1.000.000.

Se a sua entrada é um número de precisão dupla arbitrária, então você tem que autoscale seu histograma como valores vêm em que estão fora da faixa (veja acima).

Ou você pode usar o método mediana-trigêmeos descrito neste artigo: http: / /web.cs.wpi.edu/~hofri/medsel.pdf

Answer 10

Eu peguei a idéia de cálculo quantil iterativo. É importante ter um bom valor para o ponto e eta partida, estes podem vir de média e sigma. Então eu programei esta:

Função QuantileIterative (Var x: Array de duas vezes; n: Integer; p, média, sigma: Duplo): Double;
eta Var, quantil, q1, dq: Double;
i: Integer;
comece
quantil: = média + 1,25 * * Sigma (P-0,5);
Q1: = quantil;
eta: = 0,2 * sigma / xy (1 + N, 0,75); // não deve ser muito grande! define precisão
Para i: = 1 a n Do quantil: = quantil + eta * (signum_smooth (x [i] - quantil, eta) + 2 * p - 1);
dq: = abs (Q1-quantil);
Se dq> eta
Em seguida, começar
Se dq <3 * eta seguida eta: = eta / 4;
Para i: = 1 a n Do quantil: = quantil + eta * (signum_smooth (x [i] - quantil, eta) + 2 * p - 1);
end;
QuantileIterative: = quantil
end;

Como a mediana para dois elementos seria a média, eu usei uma função alisada signum, e xy () é x ^ y. Existem idéias para torná-lo melhor? É claro que se tivermos um pouco mais a priori conhecimento que pode adicionar código usando mínimo e máximo da matriz, inclinação, etc. Para dados grandes que você não iria usar uma matriz talvez, mas para testá-lo é mais fácil.