Varyans hesaplanması için algoritmalar - Algorithms for calculating variance


Vikipedi, özgür ansiklopedi

Varyansı hesaplamak için algoritmalar önemli bir rol oynamaktadır hesaplamalı istatistik . İyi tasarımında önemli bir zorluk algoritmaları bu sorun için formülleri olmasıdır varyans yol açabilir kareleri toplamı, kapsayabilir sayısal dengesizlik yanı sıra aritmetik taşma büyük değerler söz konusu olduğunda.

naif algoritması

Bütün bir varyansı hesaplamak için formül nüfus boyutu K olduğu:

Kullanılması Bessel düzeltme bir hesaplamak için tarafsız bir sonlu popülasyon varyansının tahminini numunenin ait n gözlemleri, formüldür:

Bu nedenle, tahmin edilen varyansı hesaplamak için naif algoritma aşağıda verilmektedir:

  • Let n ← 0, Sum ← 0, SUMSQ ← 0
  • Her bir veri için x :
    • Nn + 1
    • Toplam ← Sum + x
    • SUMSQ ← SUMSQ + x x x
  • Var = (SUMSQ - (Toplam x toplamı) / n) / (n - 1)

Bu algoritma, kolayca sonlu nüfusun değişikliği hesaplamak için adapte edilebilir: sadece bölün N yerine n  - son satırında 1.

Çünkü SUMSQ ve (Sum × Sum) / n çok benzer sayılar olabilir, iptal yol açabilir hassas doğal hassasiyet çok daha az olması sonucun kayan nokta aritmetik hesaplama yapmak için kullandı. Böylece bu algoritma pratikte kullanılmamalıdır ve birkaç alternatif, sayısal olarak kararlı, algoritmalar önerilmiştir. Standart sapma göre küçük olduğu, bu özellikle kötü. Ancak, algoritma yöntemi benimseyerek geliştirilebilir kabul ortalama .

Bilgisayar verilerini kaymıştır

Bu formülde felaket periyot kaybını engellemek için varyans özelliğini, yani varyans değişmez bir değişim ile ilgili konum parametresi

ile yeni formül yol açan herhangi bir sabit,

daha yakın , daha doğru bir sonucu olacaktır ortalama değere, ancak örnekler istenilen kararlılığı garanti edecek aralığı içinde yalnızca bir değer seçme. Değerleri ise küçük daha sonra karelerinin toplamı ile herhangi bir sorun vardır onlar büyükse, tam tersine, bu mutlaka varyans da büyüktür demektir. Herhangi bir durumda, formül içindeki ikinci terim, ilk dolayısıyla iptal oluşabilir daima daha küçüktür.

Biz sadece ilk örneği alırsak olarak algoritma yazılabilir Python programlama dili olarak

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 are samples of a larger population
   return variance

Bu formül de şu şekilde ifade edilebilir artan hesaplama, kolaylaştırır

K = n = Ex = Ex2 = 0.0

def add_variable(x):
    if (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():
    return K + Ex / n

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

İki geçiş algoritması

Alternatif bir yaklaşım, varyans için farklı bir formül kullanılarak, ilk olarak, örnek ortalaması hesaplar

,

ve sonra ortalamadan farklarının karelerinin toplamını hesaplar,

,

burada s standart sapmadır. Bu aşağıdaki pseudocode ile verilir:

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

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

    mean = sum1 / n

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

    variance = sum2 / (n - 1)
    return variance

Bu algoritma, eğer sayısal olarak kararlıdır , n küçüktür. Ancak bu basit algoritmalar hem sonuçları ( "Naif" ve "İki-pass") verileri sıralama üzerinde haddinden bağlı olabilir ve toplanması nedeniyle tekrarlanan roundoff hata çok büyük veri kümeleri için kötü sonuçlar verebilir toplamlar. Gibi teknikler telafi toplamı bir dereceye kadar bu hatayı mücadele etmek için de kullanılabilir.

Welford Çevrimiçi algoritması

Her bir değer, kontrol ederken, bir tek geçişte değişikliği hesaplamak mümkün genellikle yararlı olduğu sadece bir kez; örneğin, veri yeterli depolama olmadan toplanır zaman tüm değerleri tutmak veya bellek erişimi maliyetleri hesaplama olanlar hakim ne zaman. Böyle bir için çevrimiçi bir algoritma , bir yineleme ilişki gerekli istatistik sayısal olarak kararlı bir şekilde hesaplanabilir olan miktarlarda arasında gereklidir.

Aşağıdaki formüller güncellemek için kullanılabilir ortalama bir ek eleman ve dizinin (tahmin edilen) varyans, X , n . Burada, X, n, ilk örnek ortalaması anlamına gelir , n numuneleri ( X 1 , ..., x , n ), s 2 , n örneklem varyans ve σ 2 N nüfus varyans.

Tekrar tekrar ölçeklenir büyük sayıda küçük bir sayı gibi bu formüller, sayısal kararsızlık n . Güncellenmesi için daha iyi bir miktar akım ortalamadan farklarının karelerinin toplamı, burada gösterilen :

Bu algoritma Welford tarafından bulundu ve iyice analiz edilmiştir. Ayrıca belirtmek için yaygındır ve .

Welford algoritması için bir örnek Python uygulaması aşağıda verilmiştir.

# for a new value newValue, compute the new count, new mean, the new M2.
# mean accumulates the mean of the entire dataset
# M2 aggregates the squared distance from the mean
# count aggregates the number of samples seen so far
def update(existingAggregate, newValue):
    (count, mean, M2) = existingAggregate
    count += 1 
    delta = newValue - mean
    mean += delta / count
    delta2 = newValue - mean
    M2 += delta * delta2

    return (count, mean, M2)

# retrieve the mean, variance and sample variance from an aggregate
def finalize(existingAggregate):
    (count, mean, M2) = existingAggregate
    (mean, variance, sampleVariance) = (mean, M2/count, M2/(count - 1)) 
    if count < 2:
        return float('nan')
    else:
        return (mean, variance, sampleVariance)

Bu algoritma nedeniyle hassasiyet kaybına daha az eğilimli feci iptal , fakat döngü içine Bölme işleminin olabildiğince verimli olmayabilir. Varyans hesaplanması için özellikle sağlam bir iki geçişli algoritması için, bir birinci hesaplama ve ortalama bir tahminini çıkarma ve artıklar ile ilgili bu algoritma kullanabilir.

Paralel algoritma aşağıda çevrimiçi hesaplanan istatistiklerin birden setleri birleştirme nasıl göstermektedir.

Ağırlıklı artan algoritması

Algoritması basit sayacı değiştirmeden, eşit olmayan örnek ağırlıkları işlemek için uzatılabilir n kadar görülen ağırlıklarının toplamı. (1979) Batı bu önerir artan algoritmayı :

def weighted_incremental_variance(dataWeightPairs):
    wSum = wSum2 = mean = S = 0

    for x, w in dataWeightPairs:  # Alternatively "for x, w in zip(data, weights):"
        wSum = wSum + w
        wSum2 = wSum2 + w*w
        meanOld = mean
        mean = meanOld + (w / wSum) * (x - meanOld)
        S = S + w * (x - meanOld) * (x - mean)

    population_variance = S / wSum
    # Bessel's correction for weighted samples
    # Frequency weights
    sample_frequency_variance = S / (wSum - 1)
    # Reliability weights
    sample_reliability_variance = S / (wSum - wSum2/wSum)

Paralel algoritma

Chan ve diğ. Yukarıdaki "On-line" algoritma numunesinin herhangi bölümü için çalışan bir algoritma özel bir durum olduğuna dikkat kümeler halinde , :

.

Örneğin, birden fazla işlem birimi girdi ayrık parça atanabilir zaman, yararlı olabilir.

Zaman ortalamasını tahmin etmek için Chan'in yöntemi sayısal istikrarsız hem büyük ve sayısal hata nedeniyle, içinde bulunduğu bu şekilde küçültülmüş edilmez durumda. Bu gibi durumlarda, tercih .

def parallel_variance(avg_a, count_a, var_a, avg_b, count_b, var_b):
    delta = avg_b - avg_a
    m_a = var_a * (count_a - 1)
    m_b = var_b * (count_b - 1)
    M2 = m_a + m_b + delta ** 2 * count_a * count_b / (count_a + count_b)
    return M2 / (count_a + count_b - 1)

Örnek

Tüm kayan nokta işlemi standart kullanan varsayın IEEE 754 çift kesinlikli aritmetik. Sonsuz popülasyondan örnek (4, 7, 13, 16) göz önünde bulundurun. Bu örnek göre, tahmin edilen popülasyon ortalama 10 ve nüfus varyans tarafsız tahmini 30 saf algoritma her ikisi ve iki-geçiş algoritması doğru bu değerleri hesaplamak olup.

Sonraki örnek (dikkate 10 8  + 4 , 10 8  + 7 , 10 8  + 13 , 10 8  + 16 , ilk örnekle aynı tahmini varyansa neden olur). İki geçiş algoritması doğru bu varyans tahminini hesaplayan, ancak saf algoritma 29,333333333333332 yerine 30 döndürür.

Bu kesinlik kaybı tolere edilebilir ve daha ileri ofset hatası felaket yapar artan naif algoritmasının bir küçük kusur olarak görülüyor olsa da. Örnek düşünün ( 10 9  + 4 , 10 9  + 7 , 10 9  + 13 , 10 9  + 16 ). Yine 30 tahmini nüfus varyans iki geçişli algoritması tarafından doğru hesaplanır fakat naif algoritma şimdi -170.66666666666666 olarak hesaplar. Bu naif algoritma ile ciddi bir sorundur ve kaynaklanmaktadır katastrofik iptal algoritmasının son aşamada iki benzer sayıların çıkarma içinde.

Yüksek mertebeden istatistikler

Terriberry üçüncü ve dördüncü hesaplama için Chan formülleri uzanan merkezi anları tahmin edilirken, örneğin gerekli çarpıklık ve basıklığını :

İşte yine ortalamadan farkların güçlerin toplamından oluşmasıdır , veren

çarpıklık:
Basıklık:

Artışlı durum için (yani ), buna kolaylaştırır:

Değeri koruyarak , tek bir bölme işlemi gereklidir ve daha yüksek dereceden istatistikleri, böylece küçük artımlı maliyet için hesaplanabilir.

olduğu açıklandığı gibi uygulanan basıklıklarıyla için çevrimiçi algoritma örneği:

def online_kurtosis(data):
    n = mean = M2 = M3 = M4 = 0

    for x in data:
        n1 = n
        n = n + 1
        delta = x - mean
        delta_n = delta / n
        delta_n2 = delta_n * delta_n
        term1 = delta * delta_n * n1
        mean = mean + delta_n
        M4 = M4 + term1 * delta_n2 * (n*n - 3*n + 3) + 6 * delta_n2 * M2 - 4 * delta_n * M3
        M3 = M3 + term1 * delta_n * (n - 2) - 3 * delta_n * M2
        M2 = M2 + term1

    kurtosis = (n*M4) / (M2*M2) - 3
    return kurtosis

Pébaÿ ayrıca keyfi mertebeden bu sonuçları uzanır merkez anlar artan ve İkili durumlarda ve sonradan Pébaÿ ark. ağırlıklı ve bileşik anlar için. Bir de orada benzer formüller bulabilirsiniz kovaryans .

Choi ve Sweetman belli uygulamalarda önemli bilgisayar bellek gereksinimlerini ve CPU zamandan tasarruf edebilirsiniz her biri çarpıklığını ve basıklığını hesaplamak için iki alternatif yöntemler sunuyoruz. Birinci yaklaşım, depo veri ayrılması ve daha sonra etkili bir şekilde olur elde edilen histogram, geometrisi anları hesaplanmasıyla istatistiksel anlar hesaplamak için tek geçişli bir algoritma daha anlar için. Bir yarar istatistiksel momenti hesaplamaları hesaplamaları hassasiyeti, örneğin, veri saklama biçimi ya da orijinal ölçüm donanımına ayarlanmış olabilir, öyle ki rasgele doğrulukta gerçekleştirilebilir olmasıdır. Bir rastgele değişkenin bir nispi histogramı geleneksel şekilde inşa edilebilir: potansiyel değerler aralığı içine bölünmüş ve her bin içindeki geçiş sayısı sayılmış ve her bir dikdörtgen alanı örnek değerler kısmını eşit şekilde çizilmiştir o çöp kutusu içinde:

burada ve sıklığı ve depo göreceli sıklığını temsil ve histogram toplam alanıdır. Bu normalleştirmenin ardından bir ham anlar ve momentler göreceli histogram hesaplanabilir:

Üst simge burada işaret anlar histogram hesaplanır. Sabit bin genişliği için bu iki ifade kullanarak basitleştirilmiş edilebilir :

Choi ve Sweetman ikinci yaklaşım, sonuçtaki toplam anlar tam zaman aralığına ait olanlardır, örneğin bir zaman aralığına ait bireysel segmentler istatistiksel anları birleştirmek için analitik bir yöntemdir. Bu metodoloji, o anların ya da ardışık zamanlarda hesaplanan istatistiksel anlar kombinasyonu için daha sonraki bir kombinasyonu ile istatistiksel anları paralel hesaplama kullanılabilir.

Eğer istatistik anları takımları bilinmektedir: için , daha sonra her bir eşdeğer cinsinden ifade edilebilir ham anlar:

burada genel süresi olarak alınır ise zaman aralığına veya noktalarının sayısı sabittir.

Açısından istatistiksel anlar ifade yararı olmasıdır setleri ilavesiyle kombine edilebilir, ve değerine ilişkin herhangi bir üst sınır yoktur .

nerede indis birleştirilmiş zaman geçmişi veya kombine temsil . Bu birleştirilmiş değerleri kutu sonra ters tam sıralı zaman geçmişi temsil ham anlar dönüştürülecektir

Ham anlar (arasında bilinen ilişkiler ) ve merkezi anlar ( ) daha sonra birleştirilmiş zaman tarihin merkez anları hesaplamak için kullanılır. Son olarak, birleştirilmiş tarihinin istatistiksel anlar merkez anlar hesaplanır:

Kovaryans

Çok benzer algoritmalar hesaplamak için kullanılabilir kovaryansını .

naif algoritması

naif algoritma şudur:

Yukarıdaki algoritma, bir aşağıdaki Python kodu kullanabilirsiniz:

def naive_covariance(data1, data2):
    n = len(data1)
    sum12 = 0
    sum1 = sum(data1)
    sum2 = sum(data2)

    for i1, i2 in zip(data1, data2):
        sum12 += i1*i2

    covariance = (sum12 - sum1*sum2 / n) / n
    return covariance

ortalama tahmini ile

Varyans için olduğu gibi, iki rasgele değişken kovaryans da öteleme ile değişmez, böylece bir, iki sabit değerleri verilmiştir ve bu yazılabilir:

ve yine felaket iptaline formül stabilize olarak büyük miktarlarda bir karşı daha sağlam hale getirecek değerler aralığı içinde bir değeri seçmek. her bir veri setinin ilk değer alarak, algoritma şu şekilde yazılabilir:

def shifted_data_covariance(dataX, dataY):
   n = len(dataX)
   if (n < 2):
     return 0
   kx = dataX[0]
   ky = dataY[0]
   Ex = Ey = Exy = 0
   for ix, iy in zip(dataX, dataY):
      Ex += ix - kx
      Ey += iy - ky
      Exy += (ix - kx) * (iy - ky)
   return (Exy - Ex * Ey / n) / n

İki geçişli

İki geçiş algoritması birinci numune araçları ve kovaryans hesaplar:

İki geçiş algoritması aşağıdaki gibi yazılabilir:

def two_pass_covariance(data1, data2):
    n = len(data1)

    mean1 = sum(data1) / n
    mean2 = sum(data2) / n

    covariance = 0

    for i1, i2 in zip(data1, data2):
        a = i1 - mean1
        b = i2 - mean2
        covariance += a*b / n
    return covariance

Biraz daha doğru telafi versiyonu artıkların tam naif algoritmasını gerçekleştirir. Nihai toplamları ve gereken sıfır olabilir, ancak ikinci geçiş herhangi küçük bir hata telafi eder.

İnternet üzerinden

Stabil bir Tek-geçiş algoritması, ko-an hesaplar varyansı, işlem için çevrimiçi algoritmasına benzer var :

Bu son denklemde belirgin asimetri olduğu gerçeği nedeniyle her iki güncelleme terimleri eşittir, . Daha büyük doğruluk ilk önce artıklar ile ilgili sabit bir geçişli algoritması kullanılarak, hesaplama araçları aracılığıyla elde edilebilir.

Böylece olarak kovaryansını hesaplayabilir

def online_covariance(data1, data2):
    meanx = meany = C = n = 0
    for x, y in zip(data1, data2):
        n += 1
        dx = x - meanx
        meanx += dx / n
        meany += (y - meany) / n
        C += dx * (y - meany)

    population_covar = C / n
    # Bessel's correction for sample variance
    sample_covar = C / (n - 1)

Biz de ağırlıklı kovaryansını hesaplamak için küçük bir değişiklik yapabilirsiniz:

def online_weighted_covariance(data1, data2, data3):
    meanx = meany = 0
    wsum = wsum2 = 0
    C = 0
    for x, y, w in zip(data1, data2, data3):
        wsum += w
        wsum2 += w*w
        dx = x - meanx
        meanx += (w / wsum) * dx
        meany += (w / wsum) * (y - meany)
        C += w * dx * (y - meany)

    population_covar = C / wsum
    # Bessel's correction for sample variance
    # Frequency weights
    sample_frequency_covar = C / (wsum - 1)
    # Reliability weights
    sample_reliability_covar = C / (wsum - wsum2 / wsum)

Benzer şekilde, hesaplama paralelleştirme kullanılabilecek iki set kovaryansın birleştirmek için bir formül olduğu:

Ağırlıklı olarak Toplu versiyonu

Varlığından da güncellendi batched gelmez ağırlıklı çevrimiçi algoritmasının bir versiyonu: let ağırlıkları göstermek, biz yazabiliriz

Kovaryans daha sonra aşağıdaki gibi hesaplanabilir:

Ayrıca bakınız

Referanslar

  1. ^ A b Bo Einarsson (1 Ağustos 2005). Bilimsel Bilgi İşlemde Doğruluk ve Güvenilirlik . SIAM. s. 47. ISBN  978-0-89871-584-2 . Alındı Şubat 17 2013 .
  2. ^ Bir B T.F.Chan GH Golub ve RJ LeVeque (1983). " " Örnek varyansını hesaplamak için Algoritmalar: Analiz ve öneriler", Amerikan İstatistikçi, 37" (PDF) : 242-247.
  3. ^ Bir B Schubert, Erich; Gertz, Michael (2018/07/09). "(Yardımcı) varyans Sayısal stabil paralel hesaplama" . ACM: 10. doi : 10,1145 / 3.221.269,3223036 . ISBN  9781450365055 .
  4. ^ Higham Nicholas (2002). Doğruluk ve sayısal Algoritma (2 ed) (Problem 1.10) Stabilitesi . SIAM.
  5. ^ BP Welford (1962). "Kare ve ürünlerin düzeltilmiş miktarda hesaplanması için bir usul ile ilgili not" . Technometrics 4 (3): 419-420.
  6. ^ Donald E. Knuth (1998). Bilgisayar Programlama Sanatı :, hacim 2 Seminumerical Algoritmalar ., 3üncü baskı, s. 232. Boston: Addison-Wesley.
  7. ^ Chan, Tony F .; Golub, Gene, H .; LeVeque Randall, J. (1983). Numune Varyans hesaplanıyor için Algoritmalar: Analiz ve Öneriler. Amerikan İstatistikçi 37, 242-247. https://www.jstor.org/stable/2683386
  8. ^ Ling, Robert F. (1974). Bilgisayar Numune Means ve Varyanslar için çeşitli Algoritmaların Karşılaştırılması. Amerikan İstatistik Derneği Dergisi, Cilt. 69, No. 348, 859-866. doi : 10,2307 / 2286154
  9. ^ http://www.johndcook.com/standard_deviation.html
  10. ^ DHD Batı (1979). ACM İletişim : 22, 9, 532-535 güncellenmesi ortalama ve varyans tahmin: geliştirilmiş bir yöntem
  11. ^ Chan Tony F ; Golub, Gene H. ; LeVeque Randall, J. (1979), "güncelleme Formüller ve Örnek varyanslar hesaplanması için bir İkili Algoritması." (PDF) , Teknik Rapor STAN-CS-79-773 , Bilgisayar Bilimleri Bölümü, Stanford Üniversitesi.
  12. ^ Terriberry Timothy B. (2007), Bilgisayar Yüksek mertebeden Anlar Çevrimiçi
  13. ^ Pébaÿ Philippe (2008), "kovaryanslar ve Keyfi-al İstatistiksel Anlarının Sağlam, Tek Geçiş Paralel Hesaplama için formüller" (PDF) , Teknik Rapor SAND2008-6212 , Sandia Ulusal Laboratuvarları
  14. ^ Pébaÿ Philippe; Terriberry Timothy; Kolla, Hemanth; Bennett, Janine (2016), "Keyfi Ağırlıklar Yüksek Dereceden değişkenli Merkez Anlar Paralel ve Online Hesaplama için Sayısal Kararlı, Ölçeklenebilir Formüller" , bilgisayar istatistikleri , Springer
  15. ^ Bir B Choi Myoungkeun; Sweetman Bert (2010), "Yapısal Sağlık İzleme için İstatistik Anlar Etkin Hesaplama" , Yapısal Sağlık İzleme Dergisi , 9 (1)

Dış bağlantılar