incremental forma de contagem de quantis para o grande conjunto de dados

Question

Eu preciso contar os quantis para um grande conjunto de dados.

Vamos supor que nós podemos obter os dados apenas através de algumas partes (i.e.uma linha de uma matriz de grandes dimensões).Para contar o Q3 gráfico quantil para todas as partes dos dados e armazená-lo em algum lugar, em seguida, classificar e contar o gráfico quantil:

List<double> allData = new List<double>();
// This is only an example; the portions of data are not really rows of some matrix
foreach(var row in matrix) 
{
    allData.AddRange(row);
}

allData.Sort();
double p = 0.75 * allData.Count;
int idQ3 = (int)Math.Ceiling(p) - 1;
double Q3 = allData[idQ3];

Eu gostaria de encontrar uma maneira de obter o gráfico quantil sem armazenar os dados em uma variável intermediária.A melhor solução seria a contagem de alguns parâmetros de meados de resultados para a primeira linha e, em seguida, ajustar o passo a passo para o próximo linhas.

Nota:

• Estes conjuntos de dados são realmente grandes (ac 5000 elementos em cada linha)
• O Q3 pode ser estimado, não tem de ser um valor exato.
• Eu chamo de porções de dados "linhas", mas eles podem ter diferentes leghts!Geralmente não varia muito (+/- algumas centenas de amostras), mas isso varia!

Esta questão é semelhante a "On-line" (iterator) algoritmos de estimativa estatística mediana, moda, assimetria, curtose, mas eu preciso contar quantis.

Também existem poucos artigos neste tópico, por exemplo:

• Um Algoritmo Eficiente para a Mediana Aproximada de Selecção Problema
• Incremental gráfico quantil-estimativa enorme de rastreamento

Antes de tentar implementar essas abordagens, gostaria de saber se há talvez qualquer outro, mais rápido, mais maneiras de contar a 0.25/0.75 quantis?

Answer 1

Inspirado por esta resposta Criei um método que estima os quantis bastante bons. É aproximação próxima o suficiente para meus propósitos.

A idéia está seguindo: o quantil 0,75 é de fato uma mediana de todos os valores que estão acima da mediana global. E respectivamente, 0,25 quantil é uma mediana de todos os valores abaixo da mediana global.

Portanto, se pudermos aproximar a mediana, podemos, de maneira semelhante, aproximar os quantis.

double median = 0;
double q1 = 0;
double q3 = 0;
double eta = 0.005;

foreach( var value in listOfValues) // or stream, or any other large set of data...
{
    median += eta * Math.Sign(p.Int - median);
}
// Second pass. We know the median, so we can count the quantiles.
foreach(var value in listOfValues)
{ 
    if(p.Int < median)
        q1 += eta*Math.Sign(p.Int - q1);
    else
        q3 += eta*Math.Sign(p.Int - q3);
}

Observações:

• Se a distribuição de seus dados for estranha, você precisará ter maior eta Para se encaixar nos dados estranhos. Mas a precisão será pior.
• Se a distribuição é estranha, mas você sabe o tamanho total da sua coleção (ou seja, você pode ajustar o eta parâmetro dessa maneira: no conjunto de mendicamentos, o eta para ser quase igual a algum valor grande (ou seja, 0,2). À medida que o loop passa, diminua o valor de eta Então, quando você chega a quase o final da coleção, o eta será quase igual 0 (por exemplo, em loop calculá -lo assim: eta = 0.2 - 0.2*(i/N);

Answer 2

Eu segundo a ideia de usar baldes. Não se limite a 100 baldes - pode muito bem usar 1 milhão. A parte complicada é escolher suas faixas de balde para que tudo não termine em um único balde. Provavelmente, a melhor maneira de estimar suas faixas de caçamba é tirar uma amostra aleatória razoável de seus dados, calcular os quantis de 10% e 90% usando o algoritmo simples de classificação e gerar baldes de tamanho igual para preencher esse intervalo. Não é perfeito, mas se seus dados não forem de uma distribuição super-tenda, ele deve funcionar.

Se você não pode fazer amostras aleatórias, está com mais problemas. Você pode escolher um palpite inicial com base na distribuição de dados esperada e, ao trabalhar com seus dados, se houver houver bucket (normalmente o primeiro ou o último balde) ficar muito cheio, comece novamente com uma nova faixa de balde.

Answer 3

Há mais recentes e muito mais simples do algoritmo para este, que fornece muito boas estimativas de quantis extremos.

A idéia básica é que pequenos contentores são utilizados nos extremos de uma forma que ambos os limites do tamanho da estrutura de dados e garante maior precisão para pequenos ou grandes q.O algoritmo está disponível em vários idiomas e muitos pacotes.O MergingDigest versão não requer a alocação dinâmica ...uma vez que o MergingDigest é instanciado, não mais de alocação de heap é necessária.

Ver https://github.com/tdunning/t-digest

Answer 4

1. Recupere apenas os dados de que você realmente precisa - ou seja, qualquer que seja o valor (s)/está sendo usado como a chave para classificar, nem tudo o mais associado a ele.
2. Você provavelmente pode usar o algoritmo selecionado de Tony Hoare para encontrar seu quantil mais rapidamente do que classificar todos os dados.

Answer 5

Se seus dados tiverem uma distribuição gaussiana, você poderá estimar os quantis a partir do desvio padrão. Suponho que seus dados não sejam distribuídos gaussianos ou você estaria usando o SD de qualquer maneira.

Se você puder passar seus dados duas vezes, eu faria o seguinte:

• Primeiro passe, calcule o máximo, min, SD e a média.
• Segunda passagem, divida o intervalo [min, max] em algum número de baldes (por exemplo, 100); Faça o mesmo para (média - 2*SD, média + 2*SD) (com baldes extras para outliers). Em seguida, execute os dados novamente, jogando números nesses baldes.
• Conte baldes até que você esteja em 25% e 75% dos dados. Se você deseja obter extra, poderá interpolar entre os valores do balde. (Ou seja, se você precisar de 10% de um balde para atingir seu 25º Quantil, suponha que o valor seja 10% do caminho do limite baixo até o limite superior.)

Isso deve fornecer um algoritmo de tempo linear muito bom que funcione bem para a maioria dos conjuntos de dados não-de-perversos.

Answer 6

O Q-Digest é um algoritmo online aproximado que permite calcular Quantil: http://www.cs.virginia.edu/~son/cs851/papers/ucsb.sensys04.pdf

Aqui está uma implementação:

https://github.com/airlift/airlift/blob/master/stats/src/main/java/io/airlift/stats/quantiledigest.java