Méthode rapide pour calculer l'uniformité ou la divergence de l'ensemble de nombres

Question

Bonjour Supposons que j'ai l'ensemble des nombres que je veux calculer rapidement une certaine mesure d'uniformité. Je sais que la variance est la réponse la plus évidente mais je crains que la complexité de l'algorithme naïf soit trop élevée Quelqu'un a des suggestions?

Answer 1

algorithmes « intuitifs » pour le calcul de la variance souffrent généralement d'une ou les deux suivants:

1. Utilisez deux boucles (un pour le calcul de la moyenne, l'autre pour la variance)
2. Ne sont pas numerically stable

Un bon algorithme, avec une seule boucle et numériquement stable est dû à D. Knuth (comme toujours).

From Wikipedia:

n = 0 
mean = 0 
M2 = 0 
def calculate_online_variance(x): 
    n = n + 1 
    delta = x - mean 
    mean = mean + delta/n 
    M2 = M2 + delta*(x - mean) # This expression uses the new value of mean 

    variance_n = M2/n 
    variance = M2/(n - 1) #note on the first pass with n=1 this will fail (should return Inf) 
    return variance 

Vous devriez appeler calculate_online_variance (x) pour chaque point, et il renvoie la variance calculée jusqu'à présent.

Answer 2

Je ne vois pas pourquoi le calcul de la variance devrait être un problème du tout. Comme la variance est juste la somme des carrés des distances à la moyenne divisée par le nombre d'éléments, pseudocode de base pour ce faire serait

1. Calculer mu, la moyenne de l'ensemble
2. Let s = 0
3. pour chaque élément x dans la liste, soit s = s + (x - mu) * (x-mu)
4. Calculer/n

Note que, parfois, il est préférable de s diviser par n-1 (plus précisément, lorsque vous vous inquiétez des estimateurs biaisés). Voir the Wikipedia article on Bessel's correction pour pourquoi.

Bien sûr, une variance plus faible indique une uniformité élevée. Notez qu'il n'est peut-être pas une mauvaise idée de diviser davantage votre variance par mu^2 pour obtenir une mesure absolue de l'uniformité (c'est-à-dire, que ".5 1 .5 1 .5 1" est considéré comme moins serré que "100 101 100 101 100 101", car les différences relatives sont beaucoup plus importantes dans le premier que dans le second).