Algoritmos “on-line” (iterador) para estimar mediana estatística, modo, assimetria, curtose?

Existe um algoritmo para estimar a mediana, modo, assimetria e / ou curtose do conjunto de valores, mas isso NÃO requer armazenar todos os valores na memory de uma só vez?

Eu gostaria de calcular as statistics básicas:

  • média: média aritmética
  • variância: média dos desvios quadrados da média
  • desvio padrão: raiz quadrada da variância
  • mediana: valor que separa a metade maior dos números da metade menor
  • modo: valor mais frequente encontrado no conjunto
  • assimetria: tl; dr
  • curtose: tl; dr

As fórmulas básicas para calcular qualquer uma dessas são a aritmética do ensino fundamental, e eu as conheço. Existem muitas bibliotecas de statistics que as implementam também.

Meu problema é o grande número (bilhões) de valores nos conjuntos que estou manipulando: Trabalhando em Python, não posso simplesmente criar uma lista ou um hash com bilhões de elementos. Mesmo se eu escrevesse isso em C, os arrays de bilhões de elementos não seriam muito práticos.

Os dados não estão classificados. É produzido aleatoriamente, on-the-fly, por outros processos. O tamanho de cada conjunto é altamente variável e os tamanhos não serão conhecidos antecipadamente.

Eu já descobri como lidar com a média e variância muito bem, iterando através de cada valor no conjunto em qualquer ordem. (Na verdade, no meu caso, eu os tomo na ordem em que são gerados.) Aqui está o algoritmo que estou usando, cortesia http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm :

  • Inicialize três variables: count, sum e sum_of_squares
  • Para cada valor:
    • Contagem de incremento.
    • Adicione o valor à sum.
    • Adicione o quadrado do valor a sum_of_squares.
  • Divide a sum por contagem, armazenando como a média da variável.
  • Divida sum_of_squares por count, armazenando como a variável mean_of_squares.
  • Média quadrada, armazenando como square_of_mean.
  • Subtraia square_of_mean de mean_of_squares, armazenando como variance.
  • Média e variação de saída.

Esse algoritmo “on-line” possui pontos fracos (por exemplo, problemas de precisão como sum_of_squares crescem rapidamente maiores do que a faixa de números inteiros ou precisão de float), mas basicamente me dá o que preciso, sem ter que armazenar todos os valores em cada conjunto.

Mas não sei se existem técnicas semelhantes para estimar as statistics adicionais (mediana, modo, assimetria, curtose). Eu poderia viver com um estimador tendencioso, ou mesmo um método que comprometa a precisão até certo ponto, desde que a memory necessária para processar N valores seja substancialmente menor que O (N).

Apontar-me para uma biblioteca de statistics existente também ajudará se a biblioteca tiver funções para calcular uma ou mais dessas operações “on-line”.

Assimetria e Curtose

Para os algoritmos on-line para Skewness e Kurtosis (ao longo das linhas da variância), veja na mesma página wiki os algoritmos paralelos para statistics de momentos mais altos.

Mediana

A mediana é difícil sem dados ordenados. Se você sabe quantos pontos de dados você tem, em teoria você só tem que ordenar parcialmente, por exemplo, usando um algoritmo de seleção . No entanto, isso não ajuda muito com bilhões de valores. Eu sugeriria usar contagens de freqüência, veja a próxima seção.

Mediana e modo com contagens de frequência

Se são números inteiros, eu contaria freqüências , provavelmente cortando os valores mais altos e mais baixos além de algum valor, onde tenho certeza de que não é mais relevante. Para floats (ou muitos inteiros), provavelmente criaria intervalos / intervalos e, em seguida, usaria a mesma abordagem que para inteiros. (Aproximado) modo e cálculo mediano do que fica fácil, com base na tabela de frequências.

Variáveis ​​Aleatórias Normalmente Distribuídas

Se for normalmente distribuído, usaria a média , variância , assimetria e curtose da amostra da população como estimadores de máxima verossimilhança para um pequeno subconjunto. Os algoritmos (on-line) para calcular esses, você já tem. Por exemplo, leia em algumas centenas de milhares de milhões de pontos de dados, até que o seu erro de estimativa seja pequeno o suficiente. Apenas certifique-se de escolher aleatoriamente do seu set (por exemplo, se você não introduzir um viés escolhendo os primeiros 100.000 valores). A mesma abordagem também pode ser usada para estimar o modo e a mediana para o caso normal (para ambos, a média da amostra é um estimador).

Comentários adicionais

Todos os algoritmos acima podem ser executados em paralelo (incluindo muitos algoritmos de ordenação e seleção, por exemplo, QuickSort e QuickSelect), se isso ajudar.

Eu sempre assumi (com a exceção da seção sobre a distribuição normal) que nós falamos sobre momentos de amostra, mediana e modo, não estimadores para momentos teóricos dada uma distribuição conhecida.

Em geral, amostrar os dados (ou seja, observar apenas um subconjunto) deve ser bem-sucedido, dada a quantidade de dados, desde que todas as observações sejam realizações da mesma variável aleatória (tenha as mesmas distribuições) e os momentos, modo e mediana realmente existe para esta distribuição. A última ressalva não é inócua. Por exemplo, a média (e todos os momentos mais altos) da Distribuição de Cauchy não existe. Neste caso, a média da amostra de um subconjunto “pequeno” pode estar massivamente fora da média da amostra de toda a amostra.

Eu uso esses estimadores médios e medianos incrementais / recursivos, que usam armazenamento constante:

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

onde eta é um parâmetro de pequena taxa de aprendizado (por exemplo, 0,001) e sgn () é a function de signum que retorna um de {-1, 0, 1}. (Use uma constante eta se os dados forem não-estacionários e você quiser acompanhar as mudanças ao longo do tempo; caso contrário, para fonts estacionárias você pode usar algo como eta = 1 / n para o estimador médio, onde n é o número de amostras agora … infelizmente, isso não parece funcionar para o estimador mediano.)

Esse tipo de estimador de média incremental parece ser usado em todo o lugar, por exemplo, em regras de aprendizado de redes neurais não supervisionadas, mas a versão mediana parece muito menos comum, apesar de seus benefícios (robustez para outliers). Parece que a versão mediana poderia ser usada como um substituto para o estimador médio em muitas aplicações.

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

ATUALIZAR

Acabei de modificar o estimador mediano incremental para estimar quantis arbitrários. Em geral, uma function quantil ( http://en.wikipedia.org/wiki/Quantile_function ) informa o valor que divide os dados em duas frações: p e 1-p. As seguintes estimativas deste valor incrementalmente:

 quantile += eta * (sgn(sample - quantile) + 2.0 * p - 1.0) 

O valor p deve estar dentro de [0,1]. Isso essencialmente desloca a saída simétrica {-1,0,1} da function sgn () para se inclinar em direção a um lado, particionando as amostras de dados em dois escaninhos de tamanhos desiguais (as frações p e 1-p dos dados são menores que / maiores que a estimativa quantílica, respectivamente). Note que para p = 0,5, isso reduz para o estimador mediano.

Eu implementei o Algoritmo P-Square para o cálculo dynamic de quantis e histogramas sem armazenar observações em um módulo puro do Python que escrevi chamado LiveStats . Deve resolver o seu problema de forma bastante eficaz. A biblioteca suporta todas as statistics mencionadas, exceto o modo. Ainda não encontrei uma solução satisfatória para estimativa de modo.

Ryan, temo que você não esteja fazendo a média e a variância certas … Isso surgiu algumas semanas atrás aqui . E um dos pontos fortes da versão online (que na verdade é chamada de método de Welford) é o fato de ser especialmente precisa e estável, veja a discussão aqui . Um dos pontos fortes é o fato de que você não precisa armazenar a sum total ou a sum total de quadrados …

Não consigo pensar em nenhuma abordagem on-line para o modo e mediana, o que parece exigir a consideração de toda a lista de uma só vez. Mas pode muito bem ser que uma abordagem semelhante à da variância e da média funcione também para a assimetria e a curtose …

O artigo da Wikipedia citado na pergunta contém as fórmulas para a assimetria de calibração e curtose on-line.

Para o modo – eu acredito – não há como fazer isso on-line. Por quê? Suponha que todos os valores da sua input sejam diferentes, além do último que duplica um anterior. Neste caso você tem que lembrar todos os valores já vistos na input para detectar que o último valor duplica um valor visto antes e o torna o mais frequente.

Por mediana, é quase o mesmo – até a última input você não sabe qual valor se tornará a mediana se todos os valores de input forem diferentes, porque poderia ser antes ou depois da mediana atual. Se você souber a duração da input, você pode encontrar a mediana sem armazenar todos os valores na memory, mas ainda terá que armazenar muitos deles (acho que em torno da metade) porque uma sequência de input ruim poderia alterar a mediana segunda metade, possivelmente, fazendo qualquer valor a partir do primeiro semestre a mediana.

(Observe que estou me referindo apenas ao cálculo exato.)

Se você tem bilhões de pontos de dados, não é provável que você precise de respostas exatas, ao contrário de respostas próximas. Geralmente, se você tiver bilhões de pontos de dados, o processo subjacente que os gera provavelmente obedecerá a algum tipo de propriedade estatística de estacionariedade / ergodicidade / mistura. Também pode ser importante se você espera que as distribuições sejam razoavelmente contínuas ou não.

Nessas circunstâncias, existem algoritmos para memory baixa, on-line, estimativa de quantis (a mediana é um caso especial de quantil 0,5), assim como modos, caso você não precise de respostas exatas. Este é um campo ativo de statistics.

exemplo de estimativa quantílica: http://www.computer.org/portal/web/csdl/doi/10.1109/WSC.2006.323014

Exemplo de estimativa de modo: Bickel DR. Estimadores robustos do modo e skewness de dados contínuos. Estatística computacional e análise de dados. 2002; 39: 153-163. doi: 10.1016 / S0167-9473 (01) 00057-3.

Estes são campos ativos de statistics computacionais. Você está entrando nos campos onde não existe um algoritmo único e melhor, mas uma diversidade deles (estimadores estatísticos, na verdade), que têm propriedades, suposições e desempenho diferentes. É matemática experimental. Existem provavelmente centenas a milhares de artigos sobre o assunto.

A questão final é se você realmente precisa de assimetria e curtose por si só, ou mais provavelmente alguns outros parâmetros que podem ser mais confiáveis ​​na caracterização da distribuição de probabilidade (supondo que você tenha uma distribuição de probabilidade!). Você está esperando um gaussiano?

Você tem maneiras de limpar / pré-processar os dados para torná-lo principalmente Gaussianish? (por exemplo, quantias de transactions financeiras são geralmente um pouco gaussianas depois de tomar logaritmos). Você espera desvios padrão finitos? Você espera caudas gordas? São as quantidades que você se preocupa nas caudas ou no volume?

Todo mundo continua dizendo que você não pode fazer o modo de forma on-line, mas isso simplesmente não é verdade. Aqui está um artigo descrevendo um algoritmo para fazer exatamente este mesmo problema inventado em 1982 por Michael E. Fischer e Steven L. Salzberg da Universidade de Yale. Do artigo:

O algoritmo de localização majoritária usa um de seus registros para armazenamento temporário de um único item do stream; este item é o candidato atual para o elemento majoritário. O segundo registrador é um contador inicializado em 0. Para cada elemento do stream, solicitamos ao algoritmo que execute a seguinte rotina. Se o contador ler 0, instale o elemento de stream atual como o novo candidato majoritário (deslocando qualquer outro elemento que já esteja no registrador). Então, se o elemento atual corresponder ao candidato majoritário, incremente o contador; caso contrário, diminua o contador. Neste ponto do ciclo, se a parte do stream vista até agora tem um elemento majoritário, esse elemento está no registrador candidato e o contador contém um valor maior que 0. E se não houver um elemento majoritário? Sem fazer uma segunda passagem pelos dados – o que não é possível em um ambiente de stream – o algoritmo nem sempre pode fornecer uma resposta inequívoca nessa circunstância. Apenas promete identificar corretamente o elemento majoritário se houver um.

Ele também pode ser estendido para encontrar o N superior com mais memory, mas isso deve resolvê-lo para o modo.

Em última análise, se você não tem um conhecimento paramétrico a priori da distribuição, acho que você tem que armazenar todos os valores.

Dito isso, a menos que você esteja lidando com algum tipo de situação patológica, o remédio (Rousseuw e Bassett, 1990) pode ser bom o suficiente para seus propósitos.

Muito simplesmente, envolve o cálculo da mediana de lotes de medianas.

mediana e modo não podem ser calculados on-line usando apenas o espaço constante disponível. No entanto, como a mediana e o modo são, de qualquer forma, mais “descritivos” do que “quantitativos”, você pode estimá-los, por exemplo, amostrando o dataset.

Se os dados forem distribuídos normalmente a longo prazo, você poderá usar sua média para estimar a mediana.

Você também pode estimar a mediana usando a seguinte técnica: estabelecer uma estimativa mediana M [i] para cada, digamos, 1.000.000 inputs no stream de dados, de modo que M [0] seja a mediana do primeiro milhão de inputs, M [1] mediana do segundo um milhão de inputs etc. Em seguida, use a mediana de M [0] … M [k] como o estimador mediano. Isso, claro, economiza espaço, e você pode controlar quanto quer usar espaço “ajustando” o parâmetro 1.000.000. Isso também pode ser generalizado recursivamente.

OK cara tente estes:

para c ++:

 double skew(double* v, unsigned long n){ double sigma = pow(svar(v, n), 0.5); double mu = avg(v, n); double* t; t = new double[n]; for(unsigned long i = 0; i < n; ++i){ t[i] = pow((v[i] - mu)/sigma, 3); } double ret = avg(t, n); delete [] t; return ret; } double kurt(double* v, double n){ double sigma = pow(svar(v, n), 0.5); double mu = avg(v, n); double* t; t = new double[n]; for(unsigned long i = 0; i < n; ++i){ t[i] = pow( ((v[i] - mu[i]) / sigma) , 4) - 3; } double ret = avg(t, n); delete [] t; return ret; } 

onde você diz que já pode calcular a variância da amostra (svar) e a média (avg) você aponta para as suas funções para fazer isso.

Além disso, dê uma olhada na coisa de aproximação de Pearson. em um dataset tão grande seria bem parecido. 3 (média - mediana) / desvio padrão você tem mediana como max - min / 2

para o modo floats não tem significado. um normalmente os colocaria em checkboxs de tamanho considerável (como 1/100 * (max - min)).

Eu costumava usar baldes, que poderiam ser adaptativos. O tamanho do balde deve ser a precisão que você precisa. Em seguida, à medida que cada ponto de dados chega, você adiciona um à contagem do intervalo relevante. Estes devem dar-lhe aproximações simples de mediana e curtose, contando cada balde como seu valor ponderado pela sua contagem.

O único problema pode ser a perda de resolução em ponto flutuante após bilhões de operações, ou seja, adicionar um não altera mais o valor! Para contornar isso, se o tamanho máximo do intervalo exceder algum limite, você poderá retirar um grande número de todas as contas.

 for j in range (1,M): y=np.zeros(M) # build the vector y y[0]=y0 #generate the white noise eps=npr.randn(M-1)*np.sqrt(var) #increment the y vector for k in range(1,T): y[k]=corr*y[k-1]+eps[k-1] yy[j]=y list.append(y)