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?
algorithms
median
large-data
PeterR
fonte
fonte
Respostas:
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".
fonte
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.
fonte
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)
fonte
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.
fonte
Eu implementei o algoritmo P-Square para cálculo dinâmico de quantiles e histogramas sem armazenar observações em um puro módulo Python que escrevi chamado LiveStats . Isso deve resolver seu problema com bastante eficiência.
fonte
Eu nunca tive que fazer isso, então isso é apenas uma sugestão.
Eu vejo duas (outras) possibilidades.
Metade dos dados
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
Para n = 10000, 15% das estimativas medianas uniformes estavam fora do IC.
fonte
Você pode tentar encontrar uma mediana baseada na distribuição de frequências agrupada, eis alguns detalhes
fonte
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.
fonte
O Algoritmo Remediano (PDF) fornece uma estimativa mediana de uma passagem com baixos requisitos de armazenamento e precisão bem definida.
fonte
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)
fonte