migrado de math.stackexchange .
Estou processando um longo fluxo de números inteiros e estou pensando em rastrear alguns momentos para poder calcular aproximadamente vários percentis para o fluxo sem armazenar muitos dados. Qual é a maneira mais simples de calcular percentis a partir de alguns momentos. Existe uma abordagem melhor que envolva apenas o armazenamento de uma pequena quantidade de dados?
algorithms
mathematical-statistics
moments
jonderry
fonte
fonte
Respostas:
Você não declara isso explicitamente, mas, a partir da descrição do problema, parece provável que você esteja buscando um conjunto de quantis com alto viés (por exemplo, percentis 50, 90, 95 e 99).
Se for esse o caso, tive muito sucesso com o método descrito em "Computação eficaz de modais enviesados sobre fluxos de dados", de Cormode et al. É um algoritmo rápido que requer pouca memória e é fácil de implementar.
O método é baseado em um algoritmo anterior de Greenwald e Khanna que mantém uma pequena amostra do fluxo de entrada junto com os limites superior e inferior na classificação dos valores na amostra. Requer mais espaço do que uma coleção de poucos momentos, mas será muito melhor para descrever com precisão a região interessante da cauda da distribuição.
fonte
Existe um algoritmo mais recente e muito mais simples para isso, que fornece estimativas muito boas dos quantis extremos.
A idéia básica é que compartimentos menores sejam usados nos extremos de uma maneira que limite o tamanho da estrutura de dados e garanta maior precisão para pequeno ou grande . O algoritmo está disponível em vários idiomas e em muitos pacotes. A versão MergingDigest não requer alocação dinâmica ... uma vez que o MergingDigest é instanciado, nenhuma alocação de heap adicional é necessária.q
Consulte https://github.com/tdunning/t-digest
fonte