Anar al contingut

Algoritmes per a calcular la variància

De L'Enciclopèdia, la wikipedia en valencià

Els algoritmes per a calcular la variància juguen un paper important en l'estadística informàtica. Una dificultat clau en el disseny de bons algoritmes per a este problema és que les fòrmules de la variància poden incloure sumes de quadrats, lo que pot dur a problemes d'inestabilitat numèrica aixina com a rebosamiento quan es tracta de valors grans.

Algoritme "ingenu"

Una fòrmula per a calcular la variància d'una població completa de tamany N és:

σ2=(x2)‾−x¯2=∑i=1Nxi2−(∑i=1Nxi)2/NN.

Usant la correcció de Bessel per a calcular una estimació no biaixada de la variància poblacional d'una mostra finita d'observacions n, la fòrmula és:

s2=(∑i=1nxi2n−(∑i=1nxin)2)⋅nn−1.

Per lo tant, un algoritme "ingenu" per a calcular la variància estimada ve dau pel procediment:

Plantilla:Framebox

  • Let n ← 0, Sum ← 0, SumSq ← 0
  • For each datum x:
    • n ← n + 1
    • Sum ← Sum + x
    • SumSq ← SumSq + x × x
  • Var = (SumSq − (Sum × Sum) / n) / (n − 1)

Plantilla:Frame-footer

Este algoritme es pot adaptar fàcilment per a calcular la variància d'una població finita: simplement, n'hi ha prou en dividr entre N en lloc d'entre n - 1 en l'última llínea.

Com SumSq i (Sum×Sum)/n poden ser números molt similars, cancelació dels restants pot dur a que la precisió del resultat siga molt menor que la precisió inherent de moma flotant utilisada per a realisar el càlcul. Per lo tant, s'ha propost este algoritme no deu utilisar-se en la pràctica.[1][2] i varis algoritmes alternatius, numèricament estables.[3] Açò és particularment mal si la desviació estàndar és chicoteta en relació en la mija. No obstant, l'algoritme pot millorar-se adoptant el método de la mija falsa.

Càlcul de senyes desplaçades

Podem usar una propietat de la variància per a evitar la cancelació catastròfica en esta fòrmula, a saber, la variància és invariante sobre els canvis respecte a un paràmetro de localisació

Var⁡(X−K)=Var⁡(X).

Sent K una constant qualsevol, s'obté la nova fòrmula:

s2=∑i=1n(xi−K)2−(∑i=1n(xi−K))2/nn−1.

Quant més prop estiga K del valor mig, més precís serà el resultat, pero simplement elegint un valor dins del ranc de mostres es garantisarà l'estabilitat desijada. Si els valors (xi−K) són menuts, llavors no hi ha problemes en la suma dels seus quadrats, pel contrari, si són grans, necessàriament significa que la variància també és gran. En qualsevol cas, el segon terme en la fòrmula és sempre més chicotet que el primer, per lo que no pot produir-se cap cancelació.[2]

Si es pren solament la primera mostra com K, l'algoritme es pot escriure en el llenguage de programació Python com

def shifted_data_variance(data):
   if len(data) < 2:
      return 0.0
   K = data[0]
   n = Ex = Ex2 = 0.0
   for x in data:
      n = n + 1
      Ex += x - K
      Ex2 += (x - K) * (x - K)

variance = (Ex2 - (Ex * Ex)/n)/(n - 1)
   # use n instead of (n-1) if want to compute the exact variance of the given data
   # use (n-1) if data llaure samples of a larger population
   return variance

esta fòrmula facilita també el càlcul incremental, que pot expressar-se com

K = n = Ex = Ex2 = 0.0

def add_variable (x):
     si (n ==0):
       K = x
     n = n + 1
     Ex + = x - K
     Ex2 + = (x - K) * (x - K)

def remove_variable (x):
     n = n - 1
     Ex - = (x - K)
     Ex2 - = (x - K) * (x - K)

def get_meanvalue ():
     tornar K + Ex / n

def get_variance ():
     tornada (Ex2 - (Ex * Ex) / n) / (n-1)

Algoritme de dos passos

Una aproximació alternativa, usant una fòrmula diferent per a la variància, computa primer la mija de la mostra,

x¯=∑j=1nxjn,

i despuix computa la suma dels quadrats de les diferències en la mija,

sample variance=s2=∑i=1n(xi−x¯)2n−1,

a on s és la desviació estàndar. Este plantejament ve dau pel següent pseudocódigo:

def two_pass_variance(data):
    n = sum1 = sum2 = 0

    for x in data:
        n += 1
        sum1 += x

    pixen = sum1 / n

    for x in data:
        sum2 += (x - pixen)*(x - pixen)

    variance = sum2 / (n - 1)
    return variance

Este algoritme és numèricament estable si n és menut.[1][4] No obstant, els resultats d'estos dos algoritmes simples ("ingenu" i "de dos passos") poden dependre excessivament de l'orde de les senyes i poden donar resultats deficients per a conjunts de senyes molt grans, per repetits errors de grosseig en l'acumulació de les sumes. Tècniques com la suma compensada es poden usar per a combatre este error fins a cert punt.

Vore també

Referències

  1. ↑ 1,0 1,1 Einarsson, Bo (1 d'agost de 2005). Accuracy and Reliability in Scientific Computing, SIAM, p. 47. ISBN 978-0-89871-584-2. Consultat el 17 de febrer de 2013.
  2. ↑ 2,0 2,1 Chan, Tony F.; Golub, Gene H.; LeVeque, Randall J.(1983).«Algorithms for computing the sample variance: Analysis and recommendations».The American Statistician.37(3): 242–247.
  3. ↑ Schubert, Erich; Gertz, Michael(9 de juliol de 2018).«Numerically stable parallel computation of (co-)variance».ACM.: 10.doi:10.1145/3221269.3223036.
  4. ↑ Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2 ed) (Problem 1.10), SIAM.