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

Varyansı hesaplamak için kullanılan algoritmalar , hesaplama istatistiklerinde önemli bir rol oynar . Bu problem için iyi algoritmaların tasarımındaki önemli bir zorluk , varyans formüllerinin , büyük değerlerle uğraşırken aritmetik taşmanın yanı sıra sayısal kararsızlığa da yol açabilen karelerin toplamını içerebilmesidir .

Naif algoritma

N büyüklüğündeki bir popülasyonun tamamının varyansını hesaplamak için bir formül :

${\displaystyle \sigma ^{2}={\overline {(x^{2})}}-{\bar {x}}^{2}=\displaystyle {\frac {\sum _{i=1} ^{N}x_{i}^{2}-(\sum _{i=1}^{N}x_{i})^{2}/N}{N}}.\!}$

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:

${\displaystyle s^{2}=\left({\frac {\sum _{i=1}^{n}x_{i}^{2}}{n}}-\left({\frac {\ toplam _{i=1}^{n}x_{i}}{n}}\sağ)^{2}\sağ)\cdot {\frac {n}{n-1}}.\!}$

Bu nedenle, tahmin edilen varyansı hesaplamak için naif bir algoritma aşağıdaki şekilde verilir:

Bu algoritma, sonlu bir popülasyonun varyansını hesaplamak için kolayca uyarlanabilir:  son satırda n − 1 yerine basitçe N'ye bölün .

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

Kaydırılan verileri hesaplama

Varyans, bir konum parametresindeki değişikliklere göre değişmezdir , bu formülde feci iptali önlemek için kullanılabilecek bir özelliktir.

${\displaystyle \operatöradı {Var} (XK)=\operatöradı {Var} (X).}$

ile yeni formül yol açan herhangi bir sabit, ${\görüntüleme stili K}$

${\displaystyle \sigma ^{2}=\displaystyle {\frac {\sum _{i=1}^{n}(x_{i}-K)^{2}-(\sum _{i=1}) ^{n}(x_{i}-K))^{2}/n}{n-1}}.\!}$

ortalama değere ne kadar yakınsa , sonuç o kadar doğru olur, ancak sadece numune aralığı içinde bir değer seçmek istenen kararlılığı garanti edecektir. Değerler küçükse karelerinin toplamında sorun yoktur, aksine büyükse varyansın da büyük olduğu anlamına gelir. Her durumda, formüldeki ikinci terim her zaman birinciden daha küçüktür, bu nedenle iptal olmaz. ${\görüntüleme stili K}$${\görüntüleme stili (x_{i}-K)}$

İlk örnek olarak alınırsa algoritmada yazılabilir Python programlama dili olarak ${\görüntüleme stili K}$

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 aynı zamanda şu şekilde ifade edilebilen artımlı hesaplamayı da kolaylaştırır.

K = n = Ex = Ex2 = 0.0

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

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

def get_mean():
    global K, n, Ex
    return K + Ex / n

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

İki geçişli algoritma

Varyans için farklı bir formül kullanan alternatif bir yaklaşım, önce örnek ortalamasını hesaplar,

${\displaystyle {\bar {x}}={\frac {\sum _{j=1}^{n}x_{j}}{n}},}$

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

${\displaystyle {\text{örnek varyans}}=s^{2}=\displaystyle {\frac {\sum _{i=1}^{n}(x_{i}-{\bar {x}}) ^{2}}{n-1}},\!}$

burada s standart sapmadır. Bu, aşağıdaki kod tarafından 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, n küçükse sayısal olarak kararlıdır . Bununla birlikte, bu basit algoritmaların her ikisinin ("naif" ve "iki geçişli") sonuçları, verilerin sıralanmasına aşırı derecede bağlı olabilir ve çok büyük veri kümeleri için tekrarlanan yuvarlama hatası nedeniyle çok büyük veri kümeleri için kötü sonuçlar verebilir. toplamlar. Bu hatayla bir dereceye kadar mücadele etmek için telafi edilmiş toplama gibi teknikler kullanılabilir.

Welford'un çevrimiçi algoritması

Varyansı tek geçişte hesaplayabilmek ve her değeri yalnızca bir kez inceleyebilmek genellikle yararlıdır ; örneğin, veriler, tüm değerleri tutmak için yeterli depolama olmadan toplandığında veya bellek erişimi maliyetleri, hesaplama maliyetlerinin önüne geçtiğinde. Böyle bir çevrimiçi algoritma için , gerekli istatistiklerin sayısal olarak kararlı bir şekilde hesaplanabileceği miktarlar arasında bir tekrarlama ilişkisi gereklidir. ${\displaystyle x_{i}}$

Ek bir x _n öğesi için dizinin ortalamasını ve (tahmini) varyansını güncellemek için aşağıdaki formüller kullanılabilir . Burada, ilk örnek ortalamasını gösterir , n numuneleri , onların önyargılı örnek varyans ve onların tarafsız örnek varyansı . ${\displaystyle {\overline {x}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}x_{i}}$${\displaystyle (x_{1},\dots ,x_{n})}$${\displaystyle \sigma _{n}^{2}={\frac {1}{n}}\sum _{i=1}^{n}\left(x_{i}-{\overline {x} }_{n}\sağ)^{2}}$${\displaystyle s_{n}^{2}={\frac {1}{n-1}}\sum _{i=1}^{n}\left(x_{i}-{\overline {x} }_{n}\sağ)^{2}}$

${\displaystyle {\bar {x}}_{n}={\frac {(n-1)\,{\bar {x}}_{n-1}+x_{n}}{n}}= {\bar {x}}_{n-1}+{\frac {x_{n}-{\bar {x}}_{n-1}}{n}}\!}$

${\displaystyle \sigma _{n}^{2}={\frac {(n-1)\,\sigma _{n-1}^{2}+(x_{n}-{\bar {x}) }_{n-1})(x_{n}-{\bar {x}}_{n})}{n}}=\sigma _{n-1}^{2}+{\frac {( x_{n}-{\bar {x}}_{n-1})(x_{n}-{\bar {x}}_{n})-\sigma _{n-1}^{2} }{n}}.}$

${\displaystyle s_{n}^{2}={\frac {n-2}{n-1}}\,s_{n-1}^{2}+{\frac {(x_{n}-{) \bar {x}}_{n-1})^{2}}{n}}=s_{n-1}^{2}+{\frac {(x_{n}-{\bar {x}) }_{n-1})^{2}}{n}}-{\frac {s_{n-1}^{2}}{n-1}},\quad n>1}$

Bu formüller, n ile ölçeklenen büyük bir sayıdan art arda küçük bir sayıyı çıkardıkları için sayısal kararsızlıktan muzdariptir . Güncelleme için daha iyi bir miktar , burada belirtilen mevcut ortalamadan farklılıkların karelerinin toplamıdır, : ${\displaystyle \textstyle \sum _{i=1}^{n}(x_{i}-{\bar {x}}_{n})^{2}}$${\displaystyle M_{2,n}}$

${\displaystyle {\begin{aligned}M_{2,n}&=M_{2,n-1}+(x_{n}-{\bar {x}}_{n-1})(x_{n }-{\bar {x}}_{n})\\[4pt]\sigma _{n}^{2}&={\frac {M_{2,n}}{n}}\\[4pt ]s_{n}^{2}&={\frac {M_{2,n}}{n-1}}\end{hizalı}}}$

Bu algoritma Welford tarafından bulundu ve kapsamlı bir şekilde analiz edildi. Ayrıca belirtmek için yaygındır ve . ${\displaystyle M_{k}={\bar {x}}_{k}}$${\displaystyle S_{k}=M_{2,k}}$

Welford'un algoritması için örnek bir 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
    if count < 2:
        return float("nan")
    else:
        (mean, variance, sampleVariance) = (mean, M2 / count, M2 / (count - 1))
        return (mean, variance, sampleVariance)

Bu algoritma, yıkıcı iptal nedeniyle kesinlik kaybına çok daha az eğilimlidir , ancak döngü içindeki bölme işlemi nedeniyle o kadar verimli olmayabilir. Varyansı hesaplamak için özellikle sağlam bir iki geçişli algoritma için, önce ortalamanın bir tahmini hesaplanabilir ve çıkarılabilir ve daha sonra bu algoritma artıklar üzerinde kullanılabilir.

Aşağıdaki paralel algoritma , çevrimiçi olarak hesaplanan birden çok istatistik kümesinin nasıl birleştirileceğini gösterir.

Ağırlıklı artımlı algoritma

Algoritma, eşit olmayan numune ağırlıklarını işlemek için genişletilebilir, basit sayaç n şimdiye kadar görülen ağırlıkların toplamı ile değiştirilir . West (1979) bu artımlı algoritmayı önerir :

def weighted_incremental_variance(data_weight_pairs):
    w_sum = w_sum2 = mean = S = 0

    for x, w in data_weight_pairs:
        w_sum = w_sum + w
        w_sum2 = w_sum2 + w * w
        mean_old = mean
        mean = mean_old + (w / w_sum) * (x - mean_old)
        S = S + w * (x - mean_old) * (x - mean)

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

paralel algoritma

Chan ve ark. Welford'un yukarıda ayrıntıları verilen çevrimiçi algoritmasının, rastgele kümeleri birleştirmek için çalışan bir algoritmanın özel bir durumu olduğunu unutmayın ve : ${\görüntüleme stili A}$${\görüntüleme stili B}$

${\displaystyle {\begin{aligned}n_{AB}&=n_{A}+n_{B}\\\delta &={\bar {x}}_{B}-{\bar {x}}_ {A}\\{\bar {x}}_{AB}&={\bar {x}}_{A}+\delta \cdot {\frac {n_{B}}{n_{AB}}} \\M_{2,AB}&=M_{2,A}+M_{2,B}+\delta ^{2}\cdot {\frac {n_{A}n_{B}}{n_{AB} }}\\\end{hizalanmış}}}$.

Bu, örneğin, girdinin ayrı bölümlerine birden çok işlem birimi atanabildiğinde yararlı olabilir.

Chan'ın ortalamayı tahmin etme yöntemi, her ikisi de büyük olduğunda sayısal olarak kararsızdır , çünkü içindeki sayısal hata, durumda olduğu gibi küçültülmez . Bu gibi durumlarda tercih edin . ${\displaystyle n_{A}\yaklaşık n_{B}}$${\displaystyle \delta ={\bar {x}}_{B}-{\bar {x}}_{A}}$${\displaystyle n_{B}=1}$${\displaystyle {\bar {x}}_{AB}={\frac {n_{A}{\bar {x}}_{A}+n_{B}{\bar {x}}_{B} }{n_{AB}}}}$

def parallel_variance(n_a, avg_a, M2_a, n_b, avg_b, M2_b):
    n = n_a + n_b
    delta = avg_b - avg_a
    M2 = M2_a + M2_b + delta ** 2 * n_a * n_b / n
    var_ab = M2 / (n - 1)
    return var_ab

Bu, AVX ile GPU'lar ve bilgisayar kümeleri ile paralelleştirmeye ve kovaryansa izin verecek şekilde genelleştirilebilir .

Örnek

Tüm kayan nokta işlemlerinin standart IEEE 754 çift kesinlikli aritmetik kullandığını varsayın . Sonsuz bir popülasyondan örneği (4, 7, 13, 16) düşünün. Bu örneğe dayanarak, tahmini popülasyon ortalaması 10'dur ve popülasyon varyansının yansız tahmini 30'dur. Hem naif algoritma hem de iki geçişli algoritma bu değerleri doğru şekilde hesaplar.

Ardından , ilk örnekle aynı tahmini varyansa yol açan örneği ( 10 ⁸  + 4 , 10 ⁸  + 7 , 10 ⁸  + 13 , 10 ⁸  + 16 ) düşünün . İki geçişli algoritma bu varyans tahminini doğru bir şekilde hesaplar, ancak saf algoritma 30 yerine 29.33333333333332 döndürür.

Bu kesinlik kaybı tolere edilebilir ve naif algoritmanın küçük bir kusuru olarak görülse de, ofseti daha da artırmak hatayı felakete götürür. Örneği düşünün ( 10 ⁹  + 4 , 10 ⁹  + 7 , 10 ⁹  + 13 , 10 ⁹  + 16 ). Yine tahmini popülasyon varyansı 30, iki geçişli algoritma tarafından doğru bir şekilde hesaplanır, ancak saf algoritma şimdi bunu -170.6666666666666 olarak hesaplar. Bu, saf algoritma ile ilgili ciddi bir sorundur ve algoritmanın son aşamasında benzer iki sayının çıkarılmasındaki feci iptalden kaynaklanmaktadır .

Üst düzey istatistikler

Terriberry, Chan'ın formüllerini , örneğin çarpıklık ve basıklığı tahmin ederken gerekli olan üçüncü ve dördüncü merkezi momentleri hesaplamak için genişletir :

${\displaystyle {\begin{aligned}M_{3,X}=M_{3,A}+M_{3,B}&{}+\delta ^{3}{\frac {n_{A}n_{B }(n_{A}-n_{B})}{n_{X}^{2}}}+3\delta {\frac {n_{A}M_{2,B}-n_{B}M_{2 ,A}}{n_{X}}}\\[6pt]M_{4,X}=M_{4,A}+M_{4,B}&{}+\delta ^{4}{\frac { n_{A}n_{B}\left(n_{A}^{2}-n_{A}n_{B}+n_{B}^{2}\sağ)}{n_{X}^{3} }}\\[6pt]&{}+6\delta ^{2}{\frac {n_{A}^{2}M_{2,B}+n_{B}^{2}M_{2,A }}{n_{X}^{2}}}+4\delta {\frac {n_{A}M_{3,B}-n_{B}M_{3,A}}{n_{X}}} \end{hizalanmış}}}$

Burada yine ortalama farkları güçlerin toplamından oluşmasıdır , verme ${\ Displaystyle M_{k}}$${\displaystyle \sum (x-{\overline {x}})^{k}}$

${\displaystyle {\begin{hizalı}&{\text{çarpıklık}}=g_{1}={\frac {{\sqrt {n}}M_{3}}{M_{2}^{3/2} }},\\[4pt]&{\text{kurtosis}}=g_{2}={\frac {nM_{4}}{M_{2}^{2}}}-3.\end{hizalı} }}$

Artımlı durum (yani, ) için bu, şunları basitleştirir: ${\görüntüleme stili B=\{x\}}$

${\displaystyle {\begin{aligned}\delta &=xm\\[5pt]m'&=m+{\frac {\delta }{n}}\[5pt]M_{2}'&=M_{2 }+\delta ^{2}{\frac {n-1}{n}}\\[5pt]M_{3}'&=M_{3}+\delta ^{3}{\frac {(n- 1)(n-2)}{n^{2}}}-{\frac {3\delta M_{2}}{n}}\\[5pt]M_{4}'&=M_{4}+ {\frac {\delta ^{4}(n-1)(n^{2}-3n+3)}{n^{3}}}+{\frac {6\delta ^{2}M_{2 }}{n^{2}}}-{\frac {4\delta M_{3}}{n}}\end{hizalı}}}$

Değeri korunarak , yalnızca bir bölme işlemine ihtiyaç duyulur ve böylece daha yüksek mertebeden istatistikler, küçük bir artımlı maliyetle hesaplanabilir. ${\görüntüleme stili \delta /n}$

Açıklandığı gibi uygulanan basıklık için çevrimiçi algoritmanın bir ö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

    # Note, you may also calculate variance using M2, and skewness using M3
    # Caution: If all the inputs are the same, M2 will be 0, resulting in a division by 0.
    kurtosis = (n * M4) / (M2 * M2) - 3
    return kurtosis

Pébaÿ bu sonuçları , artımlı ve ikili durumlar için keyfi sıralı merkezi momentlere daha da genişletir ve ardından Pébaÿ ve diğerleri. ağırlıklı ve bileşik anlar için. Orada da kovaryans için benzer formüller bulunabilir .

Choi ve Sweetman, eğriliği ve basıklığı hesaplamak için, her biri belirli uygulamalarda önemli bilgisayar belleği gereksinimlerinden ve CPU zamanından tasarruf edebilen iki alternatif yöntem sunar. İlk yaklaşım, verileri kutulara ayırarak istatistiksel anları hesaplamak ve ardından daha yüksek anlar için etkin bir şekilde tek geçişli bir algoritma haline gelen histogramın geometrisinden anları hesaplamaktır . Bir fayda, istatistiksel moment hesaplamalarının, hesaplamaların, örneğin veri depolama formatının veya orijinal ölçüm donanımının kesinliğine ayarlanabilmesi için keyfi doğrulukta gerçekleştirilebilmesidir. Rastgele bir değişkenin göreli histogramı geleneksel yolla oluşturulabilir: potansiyel değerlerin aralığı kutulara bölünür ve her kutu içindeki oluşum sayısı sayılır ve her dikdörtgenin alanı örnek değerlerin kısmına eşit olacak şekilde çizilir. o kutunun içinde:

${\displaystyle H(x_{k})={\frac {h(x_{k})}{A}}}$

burada ve sıklığı ve depo göreceli sıklığını temsil ve histogram toplam alanıdır. Bu normalleştirmeden sonra, ham momentler ve merkezi momentler , bağıl histogramdan hesaplanabilir: ${\görüntüleme stili h(x_{k})}$${\ Displaystyle H(x_{k})}$${\displaystyle x_{k}}$${\displaystyle A=\sum _{k=1}^{K}h(x_{k})\,\Delta x_{k}}$${\görüntüleme stili n}$${\görüntüleme stili x(t)}$

${\displaystyle m_{n}^{(h)}=\sum _{k=1}^{K}x_{k}^{n}H(x_{k})\,\Delta x_{k}= {\frac {1}{A}}\sum _{k=1}^{K}x_{k}^{n}h(x_{k})\,\Delta x_{k}}$

${\displaystyle \theta _{n}^{(h)}=\sum _{k=1}^{K}{\Big (}x_{k}-m_{1}^{(h)}{\ Büyük )}^{n}\,H(x_{k})\,\Delta x_{k}={\frac {1}{A}}\sum _{k=1}^{K}{\Big (}x_{k}-m_{1}^{(h)}{\Big )}^{n}h(x_{k})\,\Delta x_{k}}$

burada üst simge , histogramdan hesaplanan momentleri gösterir. Sabit bölme genişliği için bu iki ifade aşağıdakiler kullanılarak basitleştirilebilir : ${\görüntüleme stili ^{(h)}}$${\displaystyle \Delta x_{k}=\Delta x}$${\displaystyle I=A/\Delta x}$

${\displaystyle m_{n}^{(h)}={\frac {1}{I}}\sum _{k=1}^{K}x_{k}^{n}\,h(x_{ k})}$

${\displaystyle \theta _{n}^{(h)}={\frac {1}{I}}\sum _{k=1}^{K}{\Big (}x_{k}-m_{) 1}^{(h)}{\Büyük )}^{n}h(x_{k})}$

Choi ve Sweetman'ın ikinci yaklaşımı, bir zaman-tarihinin bireysel bölümlerinden istatistiksel anları birleştirmek için analitik bir metodolojidir, öyle ki, sonuçta ortaya çıkan genel anlar, tam zaman-tarihininkilerdir. Bu metodoloji, bu anların müteakip kombinasyonları ile istatistiksel anların paralel hesaplanması için veya ardışık zamanlarda hesaplanan istatistiksel anların kombinasyonu için kullanılabilir.

Eğer istatistik anları takımları bilinmektedir: için , daha sonra her bir eşdeğer cinsinden ifade edilebilir ham anlar: ${\görüntüleme stili Q}$${\displaystyle (\gamma _{0,q},\mu _{q},\sigma _{q}^{2},\alpha _{3,q},\alpha _{4,q})\ dörtlü }$${\görüntüleme stili q=1,2,\ldots ,Q}$${\görüntüleme stili \gama _{n}}$${\görüntüleme stili n}$

${\displaystyle \gamma _{n,q}=m_{n,q}\gamma _{0,q}\qquad \quad {\textrm {for}}\quad n=1,2,3,4\quad {\text{ ve }}\quad q=1,2,\dots ,Q}$

burada genellikle zaman geçmişinin süresi veya sabit ise nokta sayısı olarak alınır. ${\görüntüleme stili \gama _{0,q}}$${\görüntüleme stili q^{th}}$${\görüntüleme stili\Delta t}$

İstatistiksel momentleri cinsinden ifade etmenin faydası , kümelerin toplama ile birleştirilebilmesi ve değerinde bir üst sınır olmamasıdır . ${\görüntüleme stili \gama }$${\görüntüleme stili Q}$${\görüntüleme stili Q}$

${\displaystyle \gamma _{n,c}=\sum _{q=1}^{Q}\gamma _{n,q}\quad \quad {\text{için }}n=0,1,2 ,3,4}$

burada alt simge , birleştirilmiş zaman geçmişini veya birleştirilmiş . Bu birleşik değerler daha sonra ters bir şekilde sıralı zaman-tarihinin tamamını temsil eden ham anlara dönüştürülebilir. ${\görüntüleme stili _{c}}$${\görüntüleme stili \gama }$${\görüntüleme stili \gama }$

${\displaystyle m_{n,c}={\frac {\gamma _{n,c}}{\gamma _{0,c}}}\quad {\text{için }}n=1,2,3 ,4}$

Ham momentler ( ) ve merkezi momentler ( ) arasındaki bilinen ilişkiler , daha sonra birleştirilmiş zaman tanım alanının merkezi anlarını hesaplamak için kullanılır. Son olarak, birleştirilmiş geçmişin istatistiksel anları, merkezi anlardan hesaplanır: ${\displaystyle m_{n}}$${\displaystyle \theta _{n}=\operatöradı {E} [(x-\mu )^{n}])}$

${\displaystyle \mu _{c}=m_{1,c}\qquad \sigma _{c}^{2}=\theta _{2,c}\qquad \alpha _{3,c}={\ frac {\theta _{3,c}}{\sigma _{c}^{3}}}\qquad \alpha _{4,c}={\frac {\theta _{4,c}}{\ sigma _{c}^{4}}}-3}$

kovaryans

Kovaryansı hesaplamak için çok benzer algoritmalar kullanılabilir .

Naif algoritma

Saf algoritma:

${\displaystyle \operatorname {Cov} (X,Y)=\displaystyle {\frac {\sum _{i=1}^{n}x_{i}y_{i}-(\sum _{i=1} ^{n}x_{i})(\sum _{i=1}^{n}y_{i})/n}{n}}.\!}$

Yukarıdaki algoritma için aşağıdaki Python kodu kullanılabilir:

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

Varyansa gelince, iki rastgele değişkenin kovaryansı da kaydırma ile değişmezdir, bu nedenle herhangi iki sabit değer verilir ve şu şekilde yazılabilir: ${\görüntüleme stili k_{x}}$${\görüntüleme stili k_{y},}$

${\displaystyle \operatöradı {Cov} (X,Y)=\operatöradı {Cov} (X-k_{x},Y-k_{y})=\displaystyle {\frac {\sum _{i=1}^ {n}(x_{i}-k_{x})(y_{i}-k_{y})-(\sum _{i=1}^{n}(x_{i}-k_{x}) )(\sum _{i=1}^{n}(y_{i}-k_{y}))/n}{n}}.\!}$

ve yine değerler aralığı içinde bir değer seçmek, formülü feci iptallere karşı stabilize edecek ve aynı zamanda büyük meblağlara karşı daha sağlam hale getirecektir. Her veri setinin ilk değeri alınarak algoritma şu şekilde yazılabilir:

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

iki geçiş

İki geçişli algoritma önce örnek ortalamayı ve ardından kovaryansı hesaplar:

${\displaystyle {\bar {x}}=\displaystyle \sum _{i=1}^{n}x_{i}/n}$

${\displaystyle {\bar {y}}=\displaystyle \sum _{i=1}^{n}y_{i}/n}$

${\displaystyle \operatorname {Cov} (X,Y)=\displaystyle {\frac {\sum _{i=1}^{n}(x_{i}-{\bar {x}})(y_{i }-{\bar {y}})}{n}}.\!}$

İki geçişli algoritma şu şekilde 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 bir telafi edilmiş sürüm, artıklar üzerinde tam saf algoritmayı gerçekleştirir. Son toplamlar ve sıfır olmalıdır , ancak ikinci geçiş herhangi bir küçük hatayı telafi eder. ${\displaystyle \textstyle \sum x_{i}}$${\displaystyle \textstyle \sum y_{i}}$

İnternet üzerinden

Varyansı hesaplamak için çevrimiçi algoritmaya benzer, eş momenti hesaplayan kararlı bir tek geçişli algoritma mevcuttur : ${\displaystyle \textstyle C_{n}=\sum _{i=1}^{n}(x_{i}-{\bar {x}}_{n})(y_{i}-{\bar { y}}_{n})}$

${\displaystyle {\begin{alignedat}{2}{\bar {x}}_{n}&={\bar {x}}_{n-1}&\,+\,&{\frac {x_ {n}-{\bar {x}}_{n-1}}{n}}\\[5pt]{\bar {y}}_{n}&={\bar {y}}_{n -1}&\,+\,&{\frac {y_{n}-{\bar {y}}_{n-1}}{n}}\\[5pt]C_{n}&=C_{ n-1}&\,+\,&(x_{n}-{\bar {x}}_{n})(y_{n}-{\bar {y}}_{n-1})\ \[5pt]&=C_{n-1}&\,+\,&(x_{n}-{\bar {x}}_{n-1})(y_{n}-{\bar {y }}_{n})\end{alignedat}}}$

Bu son denklemdeki bariz asimetri , her iki güncelleme teriminin de eşit olması gerçeğinden kaynaklanmaktadır . İlk önce ortalamaları hesaplayarak, ardından artıklar üzerinde kararlı tek geçişli algoritmayı kullanarak daha da büyük doğruluk elde edilebilir. ${\displaystyle \textstyle (x_{n}-{\bar {x}}_{n})={\frac {n-1}{n}}(x_{n}-{\bar {x}}_ {n-1})}$${\displaystyle \textstyle {\frac {n-1}{n}}(x_{n}-{\bar {x}}_{n-1})(y_{n}-{\bar {y}} _{n-1})}$

Böylece kovaryans şu şekilde hesaplanabilir:

${\displaystyle {\begin{hizalanmış}\operatöradı {Cov} _{N}(X,Y)={\frac {C_{N}}{N}}&={\frac {\operatöradı {Cov} _{ N-1}(X,Y)\cdot (N-1)+(x_{n}-{\bar {x}}_{n})(y_{n}-{\bar {y}}_{ n-1})}{N}}\\&={\frac {\operatör adı {Cov} _{N-1}(X,Y)\cdot (N-1)+(x_{n}-{\ bar {x}}_{n-1})(y_{n}-{\bar {y}}_{n})}{N}}\\&={\frac {\operatör adı {Cov} _{ N-1}(X,Y)\cdot (N-1)+{\frac {N-1}{N}}(x_{n}-{\bar {x}}_{n-1})( y_{n}-{\bar {y}}_{n-1})}{N}}\\&={\frac {\operatör adı {Cov} _{N-1}(X,Y)\cdot (N-1)+{\frac {N}{N-1}}(x_{n}-{\bar {x}}_{n})(y_{n}-{\bar {y}}_ {n})}{N}}.\end{hizalı}}}$

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)

Ağırlıklı kovaryansı hesaplamak için küçük bir değişiklik de yapılabilir:

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, hesaplamayı paralelleştirmek için kullanılabilecek iki kümenin kovaryanslarını birleştirmek için bir formül vardır:

${\displaystyle C_{X}=C_{A}+C_{B}+({\bar {x}}_{A}-{\bar {x}}_{B})({\bar {y} }_{A}-{\bar {y}}_{B})\cdot {\frac {n_{A}n_{B}}{n_{X}}}.}$

Ağırlıklı toplu sürüm

Toplu güncelleme yapan ağırlıklı çevrimiçi algoritmanın bir sürümü de mevcuttur: ağırlıkları belirtelim ve yazalım ${\displaystyle w_{1},\dots w_{N}}$

${\displaystyle {\begin{alignedat}{2}{\bar {x}}_{n+k}&={\bar {x}}_{n}&\,+\,&{\frac {\ toplam _{i=n+1}^{n+k}w_{i}(x_{i}-{\bar {x}}_{n})}{\sum _{i=1}^{n +k}w_{i}}}\\{\bar {y}}_{n+k}&={\bar {y}}_{n}&\,+\,&{\frac {\sum _{i=n+1}^{n+k}w_{i}(y_{i}-{\bar {y}}_{n})}{\sum _{i=1}^{n+ k}w_{i}}}\\C_{n+k}&=C_{n}&\,+\,&\sum _{i=n+1}^{n+k}w_{i}( x_{i}-{\bar {x}}_{n+k})(y_{i}-{\bar {y}}_{n})\\&=C_{n}&\,+\ ,&\sum _{i=n+1}^{n+k}w_{i}(x_{i}-{\bar {x}}_{n})(y_{i}-{\bar { y}}_{n+k})\\\end{alignedat}}}$

Kovaryans daha sonra şu şekilde hesaplanabilir:

${\displaystyle \operatöradı {Cov} _{N}(X,Y)={\frac {C_{N}}{\sum _{i=1}^{N}w_{i}}}}$

Ayrıca bakınız

• Kahan toplama algoritması
• Ortalamadan kare sapmalar
• Yamartino yöntemi

Referanslar

Dış bağlantılar

• Weisstein, Eric W. "Örnek Varyans Hesaplaması" . Matematik Dünyası .