Algorithme rapide pour calculer les centiles pour éliminer les valeurs aberrantes

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

  •  04-10-2019
  •  | 
  •  

Question

I possède un programme qui a besoin de calculer de manière répétée le percentile approximative (statistique d'ordre) d'un ensemble de données afin d'éliminer les valeurs aberrantes avant un traitement ultérieur. Je fais actuellement en groupant le tableau de valeurs et choisir l'élément approprié; ce qui est faisable, mais il est un blip sur les profils noticable en dépit d'être une partie relativement mineure du programme.

Plus d'infos:

  • L'ensemble de données contient de l'ordre de jusqu'à 100000 nombres à virgule flottante, et supposé être « raisonnablement » distribué - il est peu probable que des doublons ni des hausses importantes densité proche de valeurs particulières; et si pour une raison étrange, la distribution est étrange, il est OK pour une approximation d'être moins précis puisque les données sont probablement foiré en tout cas et le traitement à douteux. Cependant, les données ne sont pas nécessairement distribution uniforme ou normale; il est juste très peu de chances d'être dégénéré.
  • Une solution approximative serait bien, mais je besoin de comprendre comment l'erreur d'approximation de lance pour vous assurer qu'il est valide.
  • Étant donné que le but est d'éliminer les valeurs aberrantes, je calcule deux centiles sur les mêmes données en tout temps: par exemple une à 95% et l'autre à 5%.
  • L'application est en C # avec des morceaux de levage lourds en C ++; ou pseudo-code une bibliothèque pré-existante dans les deux seraient très bien.
  • Un tout autre moyen d'éliminer les valeurs aberrantes serait bien aussi, aussi longtemps qu'il est raisonnable.
  • Mise à jour: Il semble que je suis à la recherche d'une approximation algorithme de sélection .

Bien que cela est fait dans une boucle, les données sont (légèrement) différent à chaque fois, il est donc difficile de réutiliser une structure de données comme cela a été fait pour cette question.

Mise en œuvre Solution

En utilisant l'algorithme de sélection de wikipedia comme suggéré par Gronim réduit cette partie de la période de temps d'un facteur 20.

Depuis que je ne pouvais pas trouver une application C #, voici ce que je suis venu avec. Il est plus rapide, même pour les petites entrées que Array.Sort; et à 1000 éléments, il est 25 fois plus rapide. 

public static double QuickSelect(double[] list, int k) {
    return QuickSelect(list, k, 0, list.Length);
}
public static double QuickSelect(double[] list, int k, int startI, int endI) {
    while (true) {
        // Assume startI <= k < endI
        int pivotI = (startI + endI) / 2; //arbitrary, but good if sorted
        int splitI = partition(list, startI, endI, pivotI);
        if (k < splitI)
            endI = splitI;
        else if (k > splitI)
            startI = splitI + 1;
        else //if (k == splitI)
            return list[k];
    }
    //when this returns, all elements of list[i] <= list[k] iif i <= k
}
static int partition(double[] list, int startI, int endI, int pivotI) {
    double pivotValue = list[pivotI];
    list[pivotI] = list[startI];
    list[startI] = pivotValue;

    int storeI = startI + 1;//no need to store @ pivot item, it's good already.
    //Invariant: startI < storeI <= endI
    while (storeI < endI && list[storeI] <= pivotValue) ++storeI; //fast if sorted
    //now storeI == endI || list[storeI] > pivotValue
    //so elem @storeI is either irrelevant or too large.
    for (int i = storeI + 1; i < endI; ++i)
        if (list[i] <= pivotValue) {
            list.swap_elems(i, storeI);
            ++storeI;
        }
    int newPivotI = storeI - 1;
    list[startI] = list[newPivotI];
    list[newPivotI] = pivotValue;
    //now [startI, newPivotI] are <= to pivotValue && list[newPivotI] == pivotValue.
    return newPivotI;
}
static void swap_elems(this double[] list, int i, int j) {
    double tmp = list[i];
    list[i] = list[j];
    list[j] = tmp;
}

Performance graphique

Merci, Gronim, pour moi pointant dans la bonne direction!

Était-ce utile?

La solution

La solution de l'histogramme de Henrik fonctionnera. Vous pouvez également utiliser un algorithme de sélection pour trouver efficacement les k plus grand ou plus petit élément dans un tableau de n éléments en O (n). Pour l'utiliser pour le 95e percentile ensemble k = 0,05 N et trouver les k plus grands éléments.

Référence:

http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements

Autres conseils

Selon son créateur a SoftHeap peut être utilisé pour:

  

Compute exactes ou approximatives valeurs médianes   et centiles de manière optimale . C'est aussi   utile pour le tri approximatif ...

Vous pourriez estimer votre centiles de seulement une partie de votre ensemble de données, comme les premiers milliers de points.

Le théorème Glivenko-Cantelli assure que ce serait assez bonne estimation, si vous pouvez supposer vos points de données à être indépendants.

I utilisé pour identifier des valeurs aberrantes en calculant l'écart-type . Tout avec une distance plus que 2 (ou 3) fois l'écart type de la avarage est une valeur aberrante. 2 fois = environ 95%.

Depuis votre calculez le avarage, elle est aussi très facile de calculer l'écart-type est très rapide.

Vous pouvez également utiliser un sous-ensemble de vos données pour calculer les chiffres.

Diviser l'intervalle entre minimum et maximum de données en 1000 (par exemple) des bacs et calculer un histogramme. Ensuite, construire des sommes partielles et voir où ils dépassent d'abord 5000 ou 95000.

Il y a des approches de base couple je peux penser. La première est de calculer la plage (en trouvant les valeurs minimales et maximales), chaque élément du projet à un percentile. ((X - min) / plage) et jeter tout qui évaluent à une valeur inférieure ou supérieure à .05 .95

La seconde consiste à calculer la moyenne et l'écart-type. Une durée de 2 écarts-types de la moyenne (dans les deux sens) renfermera 95% d'un espace normalement distribué échantillon, ce qui signifie vos valeurs aberrantes serait dans le <2,5 et> 97,5 percentiles. Le calcul de la moyenne d'une série est linéaire, comme cela est le dev standard (racine carrée de la somme de la différence de chaque élément et la moyenne). Ensuite, soustraire 2 sigmas de la moyenne, et ajouter 2 sigmas à la moyenne, et vous avez vos limites de valeurs aberrantes.

Ces deux calculera en temps à peu près linéaire; le premier nécessite deux passes, la seconde prend trois (une fois que vous avez vos limites vous devez toujours éliminer les valeurs aberrantes). Je ne pense pas que depuis cette opération est basée sur la liste, vous trouverez quelque chose avec la complexité logarithmique ou constante; d'autres gains de rendement, il faudrait soit l'optimisation de l'itération et le calcul, ou l'introduction d'erreur en effectuant les calculs sur un sous-échantillon (tel que chaque troisième élément).

Une bonne réponse générale à votre problème semble être RANSAC . Compte tenu d'un modèle, et quelques données bruitées, l'algorithme récupère efficacement les paramètres du modèle.
Vous devrez choisir un modèle simple qui permet de cartographier vos données. Tout ce que lisse devrait être bien. Disons un mélange de quelques gaussiennes. RANSAC définira les paramètres de votre modèle et estimer un ensemble d'habillages en même temps. Ensuite, jeter tout ce qui ne correspond pas au modèle correctement.

Vous pouvez filtrer sur 2 ou 3 écart-type, même si les données ne sont pas normalement distribués; au moins, il se fera d'une manière cohérente, qui devrait être important.

Comme vous supprimez les valeurs aberrantes, le dev std va changer, vous pouvez le faire dans une boucle jusqu'à ce que le changement de std dev est minime. Si oui ou non vous voulez faire cela dépend de la raison pour laquelle vous manipuler les données de cette façon. Il y a des réserves importantes par certains statisticiens à l'élimination des valeurs aberrantes. Mais certains supprimer les valeurs aberrantes pour prouver que les données sont assez normalement distribué.

pas un expert, mais ma mémoire suggère:

  • pour déterminer les points percentile exactement ce que vous devez trier et nombre
  • prélever un échantillon à partir des données et le calcul des valeurs percentile sons comme un bon plan pour l'approximation correcte si vous pouvez obtenir un bon échantillon
  • sinon, comme suggéré par Henrik, vous pouvez éviter le genre complet si vous faites les seaux et les compter

Un ensemble de données de 100k éléments prend presque pas de temps de trier, donc je suppose que vous avez à faire à plusieurs reprises. Si l'ensemble de données est le même ensemble légèrement mis à jour, vous êtes mieux construire un arbre (O(N log N)), puis la suppression et l'ajout de nouveaux points comme ils viennent dans (O(K log N) où K est le nombre de points changé). Dans le cas contraire, la plus grande kth solution d'éléments déjà mentionné vous donne O(N) pour chaque jeu de données.

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