manière incrémentale de comptage quantiles pour un grand ensemble de données

StackOverflow https://stackoverflow.com/questions/2837311

Question

Je dois compter les quantiles pour un grand ensemble de données.

Supposons que nous pouvons obtenir les données que par certaines parties (à savoir une rangée d'une grande matrice). Pour compter le Q3 quantile un besoin d'obtenir toutes les parties des données et les stocker quelque part, puis trier et compter le quantile: 

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];

Je souhaite trouver un moyen d'obtention de la quantile sans mémoriser les données dans une variable intermédiaire. La meilleure solution serait de compter certains paramètres de milieu des résultats pour la première ligne, puis régler étape par étape pour les lignes suivantes.

Note:

  • Ces ensembles de données sont vraiment grands (ca 5000 éléments de chaque ligne)
  • Le Q3 peut être estimée, il ne doit pas être une valeur exacte.
  • j'appelle les portions de données « lignes », mais ils peuvent avoir des leghts! Habituellement, il ne varie pas tellement (+/- quelques centaines d'échantillons), mais il varie!

Cette question est similaire à « On-line » algorithmes (iterator) pour estimer la médiane statistique, le mode, dissymétrie, kurtosis , mais je dois compter quantiles.

Alsó il y a quelques articles dans ce sujet, i.e. .:

Avant d'essayer de mettre en œuvre ces approches, je me demandais s'il y a peut-être d'autres, plus rapide façons de compter les 0,25 / 0,75 quantiles?

Était-ce utile?

La solution 5

Inspiré par cette réponse Je créé une méthode qui permet d'estimer les quantiles assez bon. Il est assez approximation rapprochée pour mes besoins.

L'idée suit: le 0,75 quantile est en fait une médiane de toutes les valeurs qui se situe au-dessus de la médiane globale. Et respectivement, 0,25 quantile est une médiane de toutes les valeurs inférieures à la médiane globale.

Donc, si l'on peut rapprocher la médiane, on peut dans la même manière approximative les quantiles. 

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);
}

Remarques:

  • Si la distribution de vos données est étrange, vous aurez besoin d'avoir plus eta afin de s'adapter aux données étranges. Mais la précision sera pire.
  • Si la distribution est étrange, mais vous savez la taille totale de votre collection (à savoir N) vous pouvez régler le paramètre eta de cette manière: au beggining fixé le eta être presque égale à une valeur élevée (à savoir 0,2). Comme la boucle passe, plus la valeur de eta donc lorsque vous atteignez presque la fin de la collecte, la eta sera presque égale à 0 (par exemple, dans le calcul de la boucle comme ça: eta = 0.2 - 0.2*(i/N);

Autres conseils

Je seconde l'idée d'utiliser des seaux. Ne vous limitez pas à 100 seaux - pourrait tout aussi bien utiliser 1 million. La partie la plus délicate est de choisir vos gammes de seau afin que tout ne se termine pas dans un seul seau. Probablement la meilleure façon d'évaluer vos gammes de godet est de prendre un échantillon aléatoire raisonnable de vos données, calculer les 10% et 90% quantiles en utilisant l'algorithme de tri simple, puis générer des seaux de taille égale pour remplir cette gamme. Il est pas parfait, mais si vos données ne provient pas d'une distribution de super-bizarre, cela devrait fonctionner.

Si vous ne pouvez pas faire des échantillons aléatoires, vous êtes plus d'ennuis. Vous pouvez choisir une estimation initiale de héliporté en fonction de votre distribution de données attendue, tout en travaillant à travers vos données si un seau (généralement le premier ou le dernier seau) obtient overfull, recommencer à nouveau avec une nouvelle gamme de godets.

Il y a un algorithme plus récent et beaucoup plus simple pour ce qui fournit de très bonnes estimations des quantiles extrêmes.

L'idée de base est que les petits bacs sont utilisés aux extrémités d'une manière qui les deux bornes de la taille de la structure des données et garantit une plus grande précision pour les petites ou grandes q. L'algorithme est disponible en plusieurs langues et de nombreux forfaits. La version MergingDigest nécessite pas d'allocation dynamique ... une fois que la MergingDigest est instancié, aucune autre allocation de tas est nécessaire.

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

  1. Ne récupérer que les données que vous avez vraiment besoin -. À savoir, quelle que soit la valeur (s) est / sont utilisés comme la clé pour le tri, pas tout le reste associé
  2. Vous pouvez probablement utiliser l'algorithme Select Tony Hoare pour trouver votre quantile plus rapidement que le tri de toutes les données.

Si vos données ont une distribution gaussienne, vous pouvez estimer les quantiles de l'écart-type. Je suppose que vos données ne sont pas une distribution gaussienne ou que vous souhaitez simplement utiliser la SD de toute façon.

Si vous pouvez passer à travers vos données deux fois, je fais ce qui suit:

  • Première passe, calculer le max, min, SD et moyenne.
  • Deuxième passage, diviser l'intervalle [min, max] dans un certain nombre de compartiments (par exemple 100); faire la même chose pour (moyenne - 2 * SD, moyenne + 2 * SD) (avec des seaux supplémentaires pour les valeurs aberrantes). Ensuite, exécutez à travers les données à nouveau, les numéros de jeter dans ces seaux.
  • Nombre de seaux jusqu'à ce que vous êtes à 25% et 75% des données. Si vous souhaitez obtenir-fantaisie supplémentaire, vous pouvez interpoler entre les valeurs du godet. (À savoir si vous avez besoin de 10% d'un seau pour frapper votre 25 quantile, supposons que la valeur est de 10% de la distance entre la borne inférieure à la borne supérieure.)

Cela devrait vous donner un très bon algorithme en temps linéaire qui fonctionne bien pour la plupart des ensembles de données non entièrement perverse.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top