Algoritmo para monitorar dinamicamente quantis

24

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.

sinoTrinity
fonte
Para algumas idéias (no contexto da estimativa de medianas), consulte o tópico em stats.stackexchange.com/q/346/919 .
whuber
3
Esta pergunta é cruzada em math.SE.
cardeal

Respostas:

16

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 0x 6 x 0 x 6x0x6x0x6x0x6x0x6

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 y(k,y,n)nx1 1,x2,...,xny

y=(x[k+1 1](n)x[k+2](n)x[k+m](n)).

Nesta notação denota o menor dos valores lidos até agora. é uma constante, o tamanho do buffer . i th n x m yx[Eu](n)Euºn xmy

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 + 1ymqqxn+1 1

  • Se , aumente .xn+1 1<x[k+1 1](n)k

  • Se , não faça nada.xn+1 1>x[k+m](n)

  • Caso contrário, insira em . anoxn+1 1y

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 yxn+1 1yy

  • Se , remova de e aumente ;x ( n ) [ k + 1 ] y kk+m/2<nqx[k+1 1](n)yk

  • Caso contrário, remova de . yx[k+m](n)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 qmnx[qn](n)x[qn](n)ymNk/n(k+m)/nq

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=2Nq=.5x[qn](n)N=1012O(log(N))O(1)O(O(registro(N))O(registro(N))O(1 1)O(N+O(N)vezes. Portanto, os custos computacionais desse algoritmo são no tempo e no armazenamento.O(O(N+Nregistro(N))=O(N)O(N)

whuber
fonte
Este é um trabalho estendido do algoritmo P2. [link] sim.sagepub.com/content/49/4/159.abstract . O armazenamento ainda é demais para o meu aplicativo, que roda em pequenos sensores com um total de 10K RAM. Posso consumir algumas centenas de bytes, no máximo, apenas para estimativa quantil.
precisa saber é o seguinte
@whuber Na verdade, eu implemento o P2 estendido e o testo com amostras geradas de várias distribuições, como uniforme e exponencial, onde funciona muito bem. Mas quando eu o aplico aos dados do meu aplicativo, cuja distribuição é desconhecida, às vezes falha em convergir e gera um erro relativo (abs (estimativa - real) / real) em até 300%.
precisa saber é o seguinte
2
@sino A qualidade do algoritmo em comparação com o uso de todos os dados não deve depender do peso das caudas. Uma maneira mais justa de medir o erro é esta: seja o cdf empírico. Para uma estimativa do percentil , qual é a diferença entre e ? Se for da ordem de você está indo muito bem. Em outras palavras, qual percentual o algoritmo P2 está retornando para seus dados? q q F ( Q ) F ( q ) 1 / nFq^qF(q^)F(q)1 1/n
whuber
Você está certo. Acabei de medir F (qˆ) e F (q) no caso mencionado com erro relativo de até 300%. Para q de 0,7, qˆ é quase 0,7, resultando em erro desprezível. No entanto, para q de 0,9, qˆ parece estar em torno de 0,95. Acho que é por isso que tenho um erro enorme de até 300%. Alguma idéia de por que é 0,95, não 0,9? BTW, posso postar uma figura aqui e como posso postar uma fórmula matemática como você fez?
precisa saber é o seguinte
2
@whuber Estou bastante confiante de que minha implementação está em conformidade com o P2 estendido. 0,9 ainda vai para 0,95 ou até maior quando eu estimar simultaneamente quantis 0,8, 0,85, 0,9, 0,95. No entanto, 0,9 chega muito perto de 0,9 se os quantis 0,8, 0,85, 0,9, 0,95 e 1,0 forem rastreados ao mesmo tempo.
precisa saber é o seguinte
5

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(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).0p/2p(1+p)/21

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 p250p/12p11/12pp+(1p)/12p+11(1p)/1210ppe ), ou mesmo usando 22 nós Chebyshev da forma p / 2 ( 1 + cos ( 2 i - 1 ) π122 eP+(1-P)/2(1+cos(2i-1)πp/2(1+cos(2i1)π22). Sepestiver próximo de0ou1, tente colocar menos pontos no lado em que há menos massa de probabilidade e mais no outro lado.p+(1p)/2(1+cos(2i1)π22)p01 1

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

Erik P.
fonte
+1 Acho que essa é uma ótima ideia, dadas as restrições do OP. Tudo o que se pode esperar é uma aproximação; portanto, o truque é escolher caixas com alta probabilidade de serem estreitas e conterem o quantil desejado.
whuber
3

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.

denis
fonte
books.google.com/… para uma versão que não requer Flash.
ZachB
2

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

Benhamner
fonte
Os recursos computacionais exigidos do algoritmo ao qual você vincula são desnecessariamente grandes e não atendem aos requisitos desta pergunta.
whuber
2

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.

Marc
fonte
1

É 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 )

Ludo
fonte