Qual é um bom algoritmo para estimar a mediana de um enorme conjunto de dados de leitura única?

48

Estou procurando um bom algoritmo (que significa computação mínima, requisitos mínimos de armazenamento) para estimar a mediana de um conjunto de dados muito grande para armazenar, de modo que cada valor possa ser lido apenas uma vez (a menos que você armazene explicitamente esse valor). Não há limites nos dados que podem ser assumidos.

As aproximações são boas, desde que a precisão seja conhecida.

Alguma dica?

PeterR
fonte
4
Talvez, perguntando no Stackoverflow possa obter melhores respostas.
2
@Srikant:> é uma área bastante ativa de pesquisa em estatística :) A solução mais próxima dos limites teóricos mais baixos em termos de armazenamento também envolve algumas construções de probabilidade bastante inteligentes. No geral, fiquei surpreso quando olhei pela primeira vez há alguns meses; há mais estatísticas aqui do que aparenta.
usar o seguinte comando

Respostas:

6

Você poderia agrupar o conjunto de dados em conjuntos de dados muito menores (digamos 100, 1000 ou 10.000 pontos de dados)? Se você calculou a mediana de cada um dos grupos. Se você fizesse isso com conjuntos de dados suficientes, poderia plotar algo como a média dos resultados de cada um dos conjuntos menores e esse problema, executando conjuntos de dados menores o suficiente para convergir para uma solução "média".

Ian Turner
fonte
Isso é interessante, e onde alguns conselhos estatísticos podem surgir! Suponha no total que eu tenho (digamos) 500.000 pontos de identificação e olho para grupos de (digamos) 1.000 deles, e calculo a mediana de cada grupo. Agora eu tenho 500 medianas. Existe uma teoria que me permita calcular um intervalo de confiança para a mediana geral com base nessas 500 medianas?
precisa saber é o seguinte
4
Portanto, de acordo com um colega perdido há muito tempo, a melhor abordagem parece ser Chiranjeeb Buragohain e Subhash Suri. Quantiles em córregos. cs.ucsb.edu/~suri/psdir/ency.pdf Também gosto da abordagem de Ian, pois essas medianas de conjuntos de dados menores convergem para uma distribuição normal e, assim, posso formar intervalos de conf para as medianas.
PeterR
10

Que tal algo como um procedimento de binning? Suponha (para fins ilustrativos) que você saiba que os valores estão entre 1 e 1 milhão. Configure N compartimentos, do tamanho S. Portanto, se S = 10000, você terá 100 compartimentos, correspondentes aos valores [1: 10000, 10001: 20000, ..., 990001: 1000000]

Em seguida, percorra os valores. Em vez de armazenar cada valor, basta incrementar o contador na bandeja apropriada. Usando o ponto médio de cada compartimento como uma estimativa, é possível fazer uma aproximação razoável da mediana. Você pode dimensioná-lo para uma resolução tão fina ou grossa quanto desejar, alterando o tamanho dos compartimentos. Você é limitado apenas pela quantidade de memória que possui.

Como você não sabe o tamanho dos seus valores, basta escolher um tamanho de compartimento grande o suficiente para que não fique sem memória, usando alguns cálculos rápidos do verso do envelope. Você também pode armazenar as caixas escassamente, de forma que você adicione uma bandeja apenas se ela contiver um valor.

Editar:

O link ryfm fornece um exemplo de como fazer isso, com a etapa adicional de usar as porcentagens acumuladas para estimar com mais precisão o ponto na bandeja mediana, em vez de apenas usar pontos médios. Esta é uma boa melhoria.

chrisamiller
fonte
O problema com a abordagem de binning é que não temos um bom limite superior para os dados e, portanto, o ponto médio do maior bin teria que ser enorme. Portanto, precisaríamos de um grande número de compartimentos (memória insuficiente para isso) ou ter compartimentos bastante amplos (o que levaria a uma resposta bastante imprecisa.) E os dados não são muito escassos.
precisa saber é o seguinte
Como você está interessado apenas na mediana, por que não conseguiu ampliar os compartimentos com valores mais altos de sua variável?
russellpierce
drknexus - porque não sabemos qual deve ser o maior compartimento.
PeterR
Você tem alguma intuição sobre qual será o alcance? Se você tiver certeza de que mais da metade das respostas estará abaixo do número N, poderá aumentar o tamanho da sua última lixeira. Talvez seu último bin seja todos os números maiores que 1 trilhão - isso seria alto o suficiente? Com a quantidade de memória nos sistemas modernos, você pode armazenar MUITAS caixas e obter uma resolução bastante alta. Em termos de estruturas de dados, não estamos falando de nada sofisticado e com muita memória aqui.
Chrisamiller
Alguma intuição? sim. E sua abordagem pode funcionar em geral. No entanto, neste caso, não podemos ter muita memória / computação. Está em um aplicativo de rede em que o dispositivo pode ver dezenas de milhares de itens por segundo e resta MUITO pouco processamento para esse fim. Não é o cenário ideal / típico, eu sei, mas é isso que o torna interessante!
PeterR
9

Eu o redireciono para minha resposta a uma pergunta semelhante . Em poucas palavras, é um algoritmo de leitura única, 'on the fly' com pior caso de complexidade para calcular a mediana (exata).O(n)

user603
fonte
8

O algoritmo Rivest-Tarjan-Selection (às vezes também chamado de algoritmo mediana-de-medianas) permitirá calcular o elemento mediano em tempo linear, sem classificação. Para conjuntos de dados grandes, isso pode ser um pouco mais rápido que a classificação linear de log. No entanto, isso não resolverá seu problema de armazenamento de memória.

Robby McKilliam
fonte
2

Eu nunca tive que fazer isso, então isso é apenas uma sugestão.

Eu vejo duas (outras) possibilidades.

Metade dos dados

  1. Carregue metade dos dados e classifique
  2. Em seguida, leia os valores restantes e compare com a lista classificada.
    1. Se o novo valor for maior, descarte-o.
    2. caso contrário, coloque o valor na lista classificada e remova o maior valor dessa lista.

Distribuição de amostras

A outra opção é usar uma aproximação envolvendo a distribuição amostral. Se seus dados forem normais, o erro padrão para n moderado é:

1,253 * sd / sqrt (n)

Para determinar o tamanho de n com o qual você ficaria feliz, executei uma rápida simulação de Monte-Carlo em R

n = 10000
outside.ci.uni = 0
outside.ci.nor = 0
N=1000
for(i in 1:N){
  #Theoretical median is 0
  uni = runif(n, -10, 10)
  nor  = rnorm(n, 0, 10)

  if(abs(median(uni)) > 1.96*1.253*sd(uni)/sqrt(n))
    outside.ci.uni = outside.ci.uni + 1

  if(abs(median(nor)) > 1.96*1.253*sd(nor)/sqrt(n))
    outside.ci.nor = outside.ci.nor + 1
}

outside.ci.uni/N
outside.ci.nor/N

Para n = 10000, 15% das estimativas medianas uniformes estavam fora do IC.

csgillespie
fonte
3
O conjunto de dados é potencialmente grande demais para ser lido na metade ... está em um contexto de rede em que o dispositivo que está processando pode ver dezenas de milhares de itens por segundo e provavelmente possui memória suficiente para armazenar apenas algumas centenas. Além disso, os dados definitivamente não são gaussianos. De fato, ele não se encaixa bem em nenhuma das distribuições comuns.
precisa saber é o seguinte
1

Você pode tentar encontrar uma mediana baseada na distribuição de frequências agrupada, eis alguns detalhes

ryfm
fonte
1

Aqui está uma resposta para a pergunta feita no stackoverflow: https://stackoverflow.com/questions/1058813/on-line-iterator-algorithms-for-estimating-statistical-median-mian-mode-skewness/2144754#2144754

A mediana da atualização iterativa + = eta * sgn (amostra - mediana) parece ser um caminho a percorrer.

Comunidade
fonte
1
mas então como escolher eta, e o que isso significa estatisticamente? ou seja, como formar intervalos de confiança para a mediana desse resultado?
PeterR
@ PeterR, ei, qual é a solução final que você usou?
Aakash Goel
1

O Algoritmo Remediano (PDF) fornece uma estimativa mediana de uma passagem com baixos requisitos de armazenamento e precisão bem definida.

O remédio com base b prossegue calculando medianas de grupos de observações b e, em seguida, medianas dessas medianas, até restar apenas uma estimativa. Este método apenas precisa de k matrizes de tamanho b (onde n = b ^ k) ...

sapatilha
fonte
1

Se os valores que você estiver usando estiverem dentro de um determinado intervalo, digamos 1 a 100000, você poderá calcular eficientemente a mediana em um número extremamente grande de valores (digamos, trilhões de entradas), com um intervalo inteiro (esse código obtido da EA licenciada pela BSD -utils / sam-stats.cpp)

class ibucket {
public:
    int tot;
    vector<int> dat;
    ibucket(int max) {dat.resize(max+1);tot=0;}
    int size() const {return tot;};

    int operator[] (int n) const {
        assert(n < size());
        int i;
        for (i=0;i<dat.size();++i) {
            if (n < dat[i]) {
                return i;
            }
            n-=dat[i];
        }
    }

    void push(int v) {
        assert(v<dat.size());
        ++dat[v];
        ++tot;
    }
};


template <class vtype>
double quantile(const vtype &vec, double p) {
        int l = vec.size();
        if (!l) return 0;
        double t = ((double)l-1)*p;
        int it = (int) t;
        int v=vec[it];
        if (t > (double)it) {
                return (v + (t-it) * (vec[it+1] - v));
        } else {
                return v;
        }
}
Erik Aronesty
fonte
Além disso, este pode ser estendido ao uso de um número finito de lixo para medianas em tempo real, etc.
Erik Aronesty