Qu'est-ce qu'un bon algorithme pour estimer la médiane d'un énorme jeu de données en lecture unique?

48

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?

PeterR
la source
4
Peut-être que poser des questions sur Stackoverflow donnera de meilleures réponses.
2
@Srikant:> c'est un domaine de recherche statistique assez actif :) La solution la plus proche des limites théoriques inférieures en termes de stockage implique également des constructions de probabilité assez intelligentes. Dans l’ensemble, j’ai été surpris quand j’y ai regardé pour la première fois il ya deux mois; il y a plus de statistiques ici qu'il n'y paraît.
user603

Réponses:

6

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».

Ian Turner
la source
C'est intéressant, et où quelques conseils statistiques pourraient entrer! Supposons au total que j'ai (disons) 500 000 points d'id et que je regarde des groupes de (disons) 1 000, et calcule la médiane de chaque groupe. Maintenant, j'ai 500 médianes. Existe-t-il une théorie qui me permettrait de calculer un intervalle de confiance pour la médiane globale en fonction de ces 500 médianes?
PeterR
4
Ainsi, selon un collègue perdu depuis longtemps, Chiranjeeb Buragohain et Subhash Suri semblent être les meilleurs. Quantiles sur les flux. cs.ucsb.edu/~suri/psdir/ency.pdf J'aime aussi l'approche de Ian, car ces médianes d'ensembles de données plus petits convergeront vers une distribution normale et je pourrai ainsi former des intervalles de conf pour les médianes.
PeterR
10

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.

Chrisamiller
la source
Le problème avec la méthode de tri est que nous n’avons pas une bonne limite supérieure pour les données et que, par conséquent, le point médian de la plus grande corbeille devrait être énorme. Donc, nous aurions besoin d’un grand nombre de bacs (pas assez de mémoire pour cela), ou d’avoir des bacs assez larges (ce qui donnerait alors une réponse assez inexacte.) Et les données ne sont pas très rares.
PeterR
Puisque vous ne vous intéressez qu'à la médiane, pourquoi ne pourriez-vous pas élargir les classes lorsque les valeurs de votre variable sont plus élevées?
russellpierce
drknexus - parce que nous ne savons pas ce que devrait être le plus grand bac.
PeterR
Avez-vous une intuition quant à ce que sera la gamme? Si vous êtes à peu près sûr que plus de la moitié des réponses seront en dessous du nombre N, vous pouvez alors créer votre dernière corbeille aussi grande que vous le souhaitez. Peut-être que votre dernier groupe contient tous des chiffres supérieurs à 1 billion de dollars - cela serait-il suffisant? Avec la quantité de mémoire des systèmes modernes, vous pouvez stocker beaucoup de bacs et obtenir une résolution assez élevée. En termes de structures de données, nous ne parlons pas de fantaisie et de mémoire intensive.
chrisamiller
Une intuition? Oui. Et votre approche pourrait fonctionner en général. Cependant, dans ce cas, nous ne pouvons pas avoir beaucoup de mémoire / calcul. C’est dans une application réseau où l’appareil peut voir des dizaines de milliers d’éléments par seconde et TRES peu de traitement à cette fin. Ce n’est pas le scénario idéal / typique, je le sais, mais c’est ce qui le rend intéressant!
PeterR
8

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.

Robby McKilliam
la source
2

Je n'ai jamais eu à faire cela, alors ce n'est qu'une suggestion.

Je vois deux (autres) possibilités.

Demi-données

  1. Chargez en deux les données et triez
  2. Ensuite, lisez les valeurs restantes et comparez-les à la liste triée.
    1. Si la nouvelle valeur est plus grande, jetez-la.
    2. sinon mettez la valeur dans la liste triée et en supprimant la plus grande valeur de cette liste.

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

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

Pour n = 10 000, 15% des estimations de la médiane uniforme étaient en dehors de l'IC.

csgillespie
la source
3
L'ensemble de données est potentiellement trop volumineux pour être lu en deux parties ... c'est dans un contexte de réseau où le périphérique effectuant le traitement peut voir des dizaines de milliers d'éléments par seconde et dispose probablement de suffisamment de mémoire pour stocker quelques centaines. De plus, les données ne sont certainement pas gaussiennes. En fait, cela ne correspond à aucune des distributions courantes.
PeterR
1

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.

Communauté
la source
1
mais alors comment choisir eta et que veut-on dire statistiquement? comment former des intervalles de confiance pour la médiane à partir de ce résultat?
PeterR
@ Peter, hé, quelle est la solution finale que vous avez utilisée?
Aakash Goel
1

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.

Le remède de base b procède en calculant les médianes de groupes d'observations b, puis les médianes de ces médianes, jusqu'à ce qu'il ne reste qu'une seule estimation. Cette méthode a simplement besoin de k tableaux de taille b (où n = b ^ k) ...

cordonnier
la source
1

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)

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
la source
En outre, cela peut être étendu à l'utilisation d'un nombre fini de bacs pour les médianes en temps réel, etc.
Erik Aronesty