Algoritmo para monitorar dinamicamente quantis

Eu quero estimar o quantil de alguns dados. Os dados são tão grandes que não podem ser acomodados na memória. E os dados não são estáticos, novos dados continuam chegando. Alguém conhece algum algoritmo para monitorar os quantis dos dados observados até agora com memória e computação muito limitadas? Acho o algoritmo P2 útil, mas não funciona muito bem para meus dados, que são extremamente distribuídos de cauda pesada.

O algoritmo P2 é uma boa descoberta. Ele funciona fazendo várias estimativas do quantil, atualizando-as periodicamente e usando interpolação quadrática (não linear, não cúbica) para estimar o quantil. Os autores afirmam que a interpolação quadrática funciona melhor nas caudas do que a interpolação linear e cúbica seria muito exigente e difícil.

Você não indica exatamente como essa abordagem falha nos dados "de cauda pesada", mas é fácil adivinhar: as estimativas de quantis extremos para distribuições de cauda pesada serão instáveis ​​até que uma grande quantidade de dados seja coletada. Mas isso será um problema (em menor grau), mesmo que você armazene todos os dados, portanto, não espere milagres!

De qualquer forma, por que não definir marcadores auxiliares - vamos chamá-los de e nos quais você tem certeza absoluta de que o quantil estará e armazenar todos os dados que estão entre e ? Quando o seu buffer for preenchido, você precisará atualizar esses marcadores, mantendo sempre . Um algoritmo simples para fazer isso pode ser planejado a partir de uma combinação de (a) a estimativa P2 atual do quantil e (b) contagens armazenadas do número de dados menor que e do número de dados maior que . Dessa forma, você pode, com alta certeza, estimar o quantil da mesma maneira que se tivesse todo o conjunto de dados sempre disponível, mas você só precisa de um buffer relativamente pequeno.x 6 x 0 x 6 x 0 ≤ x 6 x 0 x $x_0$$x_6$$x_0$$x_6$$x_0 \le x_6$$x_0$$x_6$

Especificamente, estou propondo uma estrutura de dados para manter informações parciais sobre uma sequência de valores de dados . Aqui, é uma lista vinculadan x 1 , x 2 , … , x n $(k, \mathbf{y}, n)$$n$$x_1, x_2, \ldots, x_n$$\mathbf{y}$

Nesta notação denota o menor dos valores lidos até agora. é uma constante, o tamanho do buffer . i th n x m $x^{(n)}_{[i]}$$i^\text{th}$$n$ $x$$m$$\mathbf{y}$

O algoritmo começa preenchendo com os primeiros dados encontrados e colocando-os na ordem classificada, do menor para o maior. Seja o quantil a ser estimado; por exemplo, = 0,99. Ao ler existem três ações possíveis: m q q x n + $\mathbf{y}$$m$$q$$q$$x_{n+1}$

• Se , aumente .$x_{n+1} \lt x^{(n)}_{[k+1]}$$k$

• Se , não faça nada.$x_{n+1} \gt x^{(n)}_{[k+m]}$

• Caso contrário, insira em .$x_{n+1}$$\mathbf{y}$

De qualquer forma, incremente .$n$

O procedimento de inserção coloca em na ordem classificada e, em seguida, elimina um dos valores extremos em : y $x_{n+1}$$\mathbf{y}$$\mathbf{y}$

• Se , remova de e aumente ;x ( n ) [ k + 1 ] y$k + m/2 \lt n q$$x^{(n)}_{[k+1]}$$\mathbf{y}$$k$

• Caso contrário, remova de .$x^{(n)}_{[k+m]}$$\mathbf{y}$

Desde que seja suficientemente grande, esse procedimento agrupará o verdadeiro quantil da distribuição com alta probabilidade. Em qualquer etapa pode ser estimado da forma habitual em termos de e , que provavelmente estará em . (Acredito que só precise ser dimensionado como a raiz quadrada da quantidade máxima de dados ( ), mas não realizei uma análise rigorosa para provar isso.) De qualquer forma, o algoritmo detectará se foi bem-sucedido (por comparando e a ).n x ( n ) [ ⌊ q n ⌋ ] x ( n ) [ ⌈ q n ⌉ ] y m N k / n ( k + m ) / n $m$$n$$x^{(n)}_{[\lfloor{q n}\rfloor]}$$x^{(n)}_{[\lceil{q n}\rceil]}$$\mathbf{y}$$m$$N$$k/n$$(k+m)/n$$q$

Testar com até 100.000 valores, usando e (o caso mais difícil) indica que esse algoritmo tem uma taxa de sucesso de 99,5% na obtenção do valor correto de . Para um fluxo de valores, isso exigiria um buffer de apenas dois milhões (mas três ou quatro milhões seriam uma escolha melhor). O uso de uma lista duplamente vinculada classificada para o buffer requer um esforço de = ao identificar e excluir as operações máximas ou mínimas de . A inserção relativamente cara normalmente precisa ser feita apenas q=0,5x ( n ) [ ⌊ q n ⌋ ] N=10 12 O(log($m = 2\sqrt{N}$$q=.5$$x^{(n)}_{[\lfloor{q n}\rfloor]}$$N=10^{12}$O(log(N))O(1)O($O(\log(\sqrt{N}))$$O(\log(N))$$O(1)$O(N+$O(\sqrt{N})$vezes. Portanto, os custos computacionais desse algoritmo são no tempo e no armazenamento.O($O(N + \sqrt{N} \log(N)) = O(N)$$O(\sqrt{N})$

Eu acho que a sugestão do whuber é ótima e eu tentaria isso primeiro. No entanto, se você achar que realmente não pode acomodar o armazenamento ou não funcionar por algum outro motivo, aqui está uma idéia para uma generalização diferente de P2. Não é tão detalhado quanto o sugerido pelo whuber - mais como uma ideia de pesquisa do que como uma solução.$O(\sqrt N)$

Em vez de rastrear os quantis em , p / 2 , p , ( 1 + p ) / 2 e 1 , como sugere o algoritmo P2 original, você pode simplesmente acompanhar mais quantis (mas ainda assim um número constante). Parece que o algoritmo permite isso de uma maneira muito direta; tudo o que você precisa fazer é calcular o "intervalo" correto para os pontos recebidos e a maneira correta de atualizar os quantis (quadraticamente usando números adjacentes).$0$$p/2$$p$$(1+p)/2$$1$

Digamos que você acompanhe pontos. Você poderia tentar rastrear o quantil a 0 , p / 12 , ... , p ⋅ 11 / 12 , p , p + ( 1 - p ) / 12 , ... , p + 11 ⋅ ( 1 - p ) / 12 , 1 (picking os pontos de forma equidistante em entre 0 e p , e entre os $25$$0$$p/12$$\dotsc$$p \cdot 11/12$$p$$p + (1-p)/12$$\dotsc$$p + 11\cdot(1-p)/12$$1$$0$$p$$p$e ), ou mesmo usando 22 nós Chebyshev da forma p / 2 ⋅ ( 1 + cos ( 2 i - 1 ) $1$$22$ eP+(1-P)/2⋅(1+cos(2i-1)$p/2 \cdot (1 + \cos \frac{(2 i - 1)\pi}{22})$. Sepestiver próximo de0ou1, tente colocar menos pontos no lado em que há menos massa de probabilidade e mais no outro lado.$p + (1 - p)/2 \cdot (1 + \cos \frac{(2i-1)\pi}{22})$$p$$0$$1$

Se você decidir prosseguir com isso, eu (e possivelmente outros neste site) estaria interessado em saber se funciona ...

Press et al., Numerical Recipes 8.5.2 "Estimativa de passagem única de quantis arbitrários" p. 435, forneça uma classe c ++ IQAgent que atualize um cdf aproximado linear por partes.

Isso pode ser adaptado a partir de algoritmos que determinam a mediana de um conjunto de dados online. Para obter mais informações, consulte esta postagem do stackoverflow - /programming/1387497/find-median-value-from-a-growing-set

Eu olhava para a regressão quantílica. Você pode usá-lo para determinar uma estimativa paramétrica de quaisquer quantis que você deseja examinar. Ele não assume nenhuma premissa em relação à normalidade, por isso lida muito bem com a heterocedasticidade e pode ser usado como janela de rolagem. É basicamente uma regressão penalizada pela norma L1, por isso não é muito numericamente intensa e há um pacote R, SAS e SPSS bastante completo, além de algumas implementações de matlab por aí. Aqui estão as wikis principais e do pacote R para obter mais informações.

Editado:

Verifique a ligação cruzada de troca de pilhas matemáticas: alguém colocou alguns papéis que essencialmente expõem a idéia muito simples de usar apenas uma janela rolante de estatísticas de pedidos para estimar quantis. Literalmente, tudo o que você precisa fazer é classificar os valores do menor para o maior, selecionar qual quantil você deseja e selecionar o valor mais alto dentro desse quantil. Obviamente, você pode dar mais peso às observações mais recentes se acreditar que elas são mais representativas das condições atuais reais. Isso provavelmente fornecerá estimativas aproximadas, mas é bastante simples de fazer e você não precisa passar pelos movimentos do levantamento quantitativo de cargas pesadas. Apenas um pensamento.

É possível estimar (e rastrear) quantis on-line (o mesmo se aplica aos parâmetros de uma regressão quantil). Em essência, isso se resume à descida do gradiente estocástico na função de verificação e perda que define a regressão quantílica (quantis sendo representados por um modelo contendo apenas uma interceptação), por exemplo, atualizando os parâmetros desconhecidos à medida que as observações chegam.

Consulte o artigo da Bell Labs "Estimativa incremental de quantis para rastreamento maciço" ( ftp://ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/kdd/p516-chen.pdf )

Outro algoritmo importante é M. Greenwald e S. Khanna 2004 - Computação on-line com espaço eficiente de resumos de quantis.