Je recherche un bon algorithme (calcul minimal, exigences de stockage minimales) pour estimer la médiane d'un ensemble de données trop volumineux pour être stocké, de telle sorte que chaque valeur ne puisse être lue qu'une fois (à moins que vous stockiez explicitement cette valeur). Aucune donnée sur les données ne peut être supposée.
Les approximations sont correctes, à condition que la précision soit connue.
Des pointeurs?
algorithms
median
large-data
PeterR
la source
la source
Réponses:
Pourriez-vous regrouper l'ensemble de données dans des ensembles de données beaucoup plus petits (par exemple, 100, 1 000 ou 10 000 points de données) si vous avez ensuite calculé la médiane de chacun des groupes. Si vous le faisiez avec suffisamment d'ensembles de données, vous pourriez tracer quelque chose comme la moyenne des résultats de chacun des ensembles les plus petits et ce, en exécutant suffisamment d'ensembles de données plus petits qui convergent vers une solution «moyenne».
la source
Que diriez-vous de quelque chose comme une procédure de binning? Supposons (à titre d'illustration) que vous savez que les valeurs sont comprises entre 1 et 1 million. Mettre en place N bacs, de taille S. Donc, si S = 10000, vous auriez 100 bacs, correspondant aux valeurs [1: 10000, 10001: 20000, ..., 990001: 1000000]
Puis, parcourez les valeurs. Au lieu de stocker chaque valeur, incrémentez simplement le compteur dans le bac approprié. En utilisant le point médian de chaque case comme estimation, vous pouvez obtenir une approximation raisonnable de la médiane. Vous pouvez adapter cette résolution à une résolution aussi fine ou grossière que vous le souhaitez en modifiant la taille des bacs. Vous n'êtes limité que par la quantité de mémoire dont vous disposez.
Puisque vous ne savez pas quelle taille peuvent prendre vos valeurs, il vous suffit de choisir une taille de corbeille suffisamment grande pour ne pas manquer de mémoire, à l'aide de calculs rapides de retour en arrière. Vous pouvez également stocker les bacs de manière éparse, de sorte que vous n’ajoutez un bac que s’il contient une valeur.
Modifier:
Le lien ryfm en donne un exemple, avec l'étape supplémentaire consistant à utiliser les pourcentages cumulés pour estimer plus précisément le point dans la tranche médiane, au lieu d'utiliser uniquement les points centraux. C'est une belle amélioration.
la source
la source
L' algorithme Rivest-Tarjan-Selection (parfois aussi appelé algorithme de la médiane des médianes) vous permettra de calculer l'élément médian en temps linéaire, sans aucun tri. Pour les grands ensembles de données, cela peut être un peu plus rapide que le tri log-linéaire. Cependant, cela ne résoudra pas votre problème de stockage de mémoire.
la source
J'ai implémenté l' algorithme P-square pour le calcul dynamique de quantiles et d'histogrammes sans stockage d'observations dans un module Python soigné que j'ai écrit, appelé LiveStats . Cela devrait résoudre votre problème assez efficacement.
la source
Je n'ai jamais eu à faire cela, alors ce n'est qu'une suggestion.
Je vois deux (autres) possibilités.
Demi-données
Distribution d'échantillonnage
L'autre option consiste à utiliser une approximation impliquant la distribution d'échantillonnage. Si vos données sont normales, l’erreur standard pour n modéré est la suivante:
1,253 * sd / sqrt (n)
Pour déterminer la taille de n qui vous conviendrait le mieux, j’ai exécuté une simulation rapide de Monte-Carlo dans R
Pour n = 10 000, 15% des estimations de la médiane uniforme étaient en dehors de l'IC.
la source
Vous pouvez essayer de trouver une médiane basée sur la distribution de fréquence groupée, voici quelques détails
la source
Voici une réponse à la question posée sur stackoverflow: https://stackoverflow.com/questions/1058813/on-line-iterator-algorithms-for-estimating-statistical-median-mode-skewness/2144754#2144754
La mise à jour itérative médiane + = eta * sgn (échantillon - médiane) semble être une solution.
la source
L' algorithme Remedian (PDF) fournit une estimation médiane en un seul passage avec de faibles exigences de stockage et une précision bien définie.
la source
Si les valeurs que vous utilisez sont comprises dans une certaine plage, par exemple, entre 1 et 100 000, vous pouvez calculer efficacement la médiane sur un très grand nombre de valeurs (disons, des milliards d'entrées), avec un compartiment entier (ce code tiré d'une licence sous licence BSD). -utils / sam-stats.cpp)
la source