विचरण की गणना के लिए एल्गोरिदम

विचरण की गणना के लिए कलन विधि कम्प्यूटेशनल सांख्यिकी में एक प्रमुख भूमिका निभाते हैं। इस समस्या के लिए अच्छे एल्गोरिदम के डिजाइन में एक महत्वपूर्ण कठिनाई यह है कि विचरण के सूत्रों में वर्गों का योग शामिल हो सकता है, जिससे बड़े मूल्यों से निपटने के दौरान संख्यात्मक अस्थिरता के साथ-साथ अंकगणितीय अतिप्रवाह भी हो सकता है।

भोला एल्गोरिथ्म

आकार N की संपूर्ण सांख्यिकीय जनसंख्या के विचरण की गणना के लिए एक सूत्र है:

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

एन अवलोकनों के एक सीमित सांख्यिकीय नमूने से जनसंख्या भिन्नता के अनुमानक पूर्वाग्रह अनुमान की गणना करने के लिए बेसेल के सुधार का उपयोग करते हुए, सूत्र है:

$s^{2}=\left({\frac {\sum _{i=1}^{n}x_{i}^{2}}{n}}-\left({\frac {\sum _{i=1}^{n}x_{i}}{n}}\right)^{2}\right)\cdot {\frac {n}{n-1}}.$

इसलिए, अनुमानित विचरण की गणना करने के लिए एक सरल एल्गोरिदम निम्नलिखित द्वारा दिया गया है:

• होने देना n ← 0, Sum ← 0, SumSq ← 0
• प्रत्येक डेटाम के लिए x:
  • n ← n + 1
  • Sum ← Sum + x
  • SumSq ← SumSq + x × x
• Var = (SumSq − (Sum × Sum) / n) / (n − 1)

इस एल्गोरिदम को एक सीमित जनसंख्या के विचरण की गणना करने के लिए आसानी से अनुकूलित किया जा सकता है: बस अंतिम पंक्ति पर n − 1 के बजाय n से विभाजित करें।

क्योंकि SumSq और (Sum×Sum)/n बहुत समान संख्याएं हो सकती हैं, कैटास्ट्रॉफिक रद्दीकरण के कारण परिणाम की सटीकता (अंकगणित) गणना करने के लिए उपयोग किए जाने वाले फ़्लोटिंग-पॉइंट अंकगणित की अंतर्निहित सटीकता से बहुत कम हो सकती है। इस प्रकार इस एल्गोरिथम का प्रयोग व्यवहार में नहीं किया जाना चाहिए, और कई वैकल्पिक, संख्यात्मक रूप से स्थिर, एल्गोरिदम प्रस्तावित किए गए हैं। यह विशेष रूप से बुरा है यदि मानक विचलन माध्य के सापेक्ष छोटा है।

स्थानांतरित डेटा की कंप्यूटिंग

स्थान पैरामीटर में परिवर्तन के संबंध में भिन्नता अपरिवर्तनीय (गणित) है, एक संपत्ति जिसका उपयोग इस सूत्र में विनाशकारी रद्दीकरण से बचने के लिए किया जा सकता है।

$\operatorname {Var} (X-K)=\operatorname {Var} (X).$

साथ $K$ कोई भी स्थिरांक, जो नए सूत्र की ओर ले जाता है

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

करीब $K$ औसत मान जितना अधिक सटीक होगा परिणाम उतना ही सटीक होगा, लेकिन केवल इसके अंदर एक मान चुनना होगा नमूनों की रेंज वांछित स्थिरता की गारंटी देगी। यदि मान $(x_{i}-K)$ छोटे हैं तो इसके वर्गों के योग में कोई समस्या नहीं है, इसके विपरीत, यदि वे बड़े हैं तो इसका मतलब यह है कि भिन्नता भी बड़ी है। किसी भी स्थिति में सूत्र में दूसरा पद हमेशा पहले से छोटा होता है इसलिए कोई रद्दीकरण नहीं हो सकता है।

यदि केवल पहला नमूना ही लिया जाए $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 += 1
        Ex += x - K
        Ex2 += (x - K) ** 2
    variance = (Ex2 - Ex**2 / 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

यह सूत्र वृद्धिशील गणना को भी सुविधाजनक बनाता है जिसे इस प्रकार व्यक्त किया जा सकता है

K = Ex = Ex2 = 0.0
n = 0


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

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

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

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

दो-पास एल्गोरिथ्म

एक वैकल्पिक दृष्टिकोण, विचरण के लिए एक अलग सूत्र का उपयोग करते हुए, पहले नमूना माध्य की गणना करता है,

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

और फिर माध्य से अंतर के वर्गों के योग की गणना करता है,

${\text{sample variance}}=s^{2}={\dfrac {\sum _{i=1}^{n}(x_{i}-{\bar {x}})^{2}}{n-1}},$

जहां s मानक विचलन है. यह निम्नलिखित कोड द्वारा दिया गया है:

def two_pass_variance(data):
    n = len(data)
    mean = sum(data) / n
    variance = sum([(x - mean) ** 2 for x in data]) / (n - 1)
    return variance

यदि n छोटा है तो यह एल्गोरिदम संख्यात्मक रूप से स्थिर है। हालाँकि, इन दोनों सरल एल्गोरिदम (भोले और दो-पास) के परिणाम डेटा के क्रम पर अत्यधिक निर्भर हो सकते हैं और रकम के संचय में बार-बार राउंडऑफ त्रुटि के कारण बहुत बड़े डेटा सेट के लिए खराब परिणाम दे सकते हैं। इस त्रुटि से कुछ हद तक निपटने के लिए क्षतिपूर्ति योग जैसी तकनीकों का उपयोग किया जा सकता है।

वेलफ़ोर्ड का ऑनलाइन एल्गोरिथम

प्रत्येक मान का निरीक्षण करते हुए, एक-पास एल्गोरिथ्म में भिन्नता की गणना करने में सक्षम होना अक्सर उपयोगी होता है $x_{i}$ केवल एकबार; उदाहरण के लिए, जब सभी मूल्यों को रखने के लिए पर्याप्त भंडारण के बिना डेटा एकत्र किया जा रहा हो, या जब मेमोरी एक्सेस की लागत गणना पर हावी हो। ऐसे ऑनलाइन एल्गोरिदम के लिए, मात्राओं के बीच एक पुनरावृत्ति संबंध की आवश्यकता होती है जिससे आवश्यक आंकड़ों की गणना संख्यात्मक रूप से स्थिर तरीके से की जा सकती है।

अतिरिक्त तत्व x के लिए अनुक्रम के माध्य और (अनुमानित) विचरण को अद्यतन करने के लिए निम्नलिखित सूत्रों का उपयोग किया जा सकता है_n. यहाँ, ${\textstyle {\overline {x}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}x_{i}}$ पहले n नमूनों के नमूना माध्य को दर्शाता है $(x_{1},\dots ,x_{n})$, ${\textstyle \sigma _{n}^{2}={\frac {1}{n}}\sum _{i=1}^{n}\left(x_{i}-{\overline {x}}_{n}\right)^{2}}$ उनका वेरिएंस#बायस्ड_सैंपल_वेरिएंस, और ${\textstyle s_{n}^{2}={\frac {1}{n-1}}\sum _{i=1}^{n}\left(x_{i}-{\overline {x}}_{n}\right)^{2}}$ उनका भिन्नता#निष्पक्ष_नमूना_भिन्नता।

${\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}}$

$\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}}.$

$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$

ये सूत्र संख्यात्मक अस्थिरता से ग्रस्त हैं, क्योंकि वे बार-बार एक बड़ी संख्या से एक छोटी संख्या घटाते हैं जो n के साथ मापी जाती है। अद्यतन करने के लिए एक बेहतर मात्रा वर्तमान माध्य से अंतर के वर्गों का योग है, ${\textstyle \sum _{i=1}^{n}(x_{i}-{\bar {x}}_{n})^{2}}$, यहाँ दर्शाया गया है $M_{2,n}$:

${\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{aligned}}$

यह एल्गोरिथम वेलफ़ोर्ड द्वारा पाया गया था, और इसका गहन विश्लेषण किया गया है। निरूपित करना भी आम बात है $M_{k}={\bar {x}}_{k}$ और $S_{k}=M_{2,k}$. वेलफ़ोर्ड के एल्गोरिदम के लिए पायथन कार्यान्वयन का एक उदाहरण नीचे दिया गया है।

# 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)

इस एल्गोरिदम में विनाशकारी रद्दीकरण के कारण परिशुद्धता के नुकसान की बहुत कम संभावना है, लेकिन लूप के अंदर विभाजन ऑपरेशन के कारण यह उतना कुशल नहीं हो सकता है। विचरण की गणना के लिए विशेष रूप से मजबूत दो-पास एल्गोरिदम के लिए, कोई पहले माध्य के अनुमान की गणना और घटा सकता है, और फिर अवशेषों पर इस एल्गोरिदम का उपयोग कर सकता है।

नीचे दिया गया #समानांतर एल्गोरिदम दर्शाता है कि ऑनलाइन गणना किए गए आँकड़ों के कई सेटों को कैसे मर्ज किया जाए।

भारित वृद्धिशील एल्गोरिथ्म

असमान नमूना वजन को संभालने के लिए एल्गोरिदम को बढ़ाया जा सकता है, सरल काउंटर एन को अब तक देखे गए वजन के योग के साथ बदल दिया जा सकता है। पश्चिम (1979) इस वृद्धिशील कंप्यूटिंग का सुझाव देता है:

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**2
        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)

Further information: Weighted arithmetic mean § Weighted sample variance

समानांतर एल्गोरिदम

चान एट अल. ध्यान दें कि ऊपर वर्णित वेलफ़ोर्ड का ऑनलाइन एल्गोरिदम एक एल्गोरिदम का एक विशेष मामला है जो मनमाने सेटों के संयोजन के लिए काम करता है $A$ और $B$:

${\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{aligned}}$.

यह तब उपयोगी हो सकता है जब, उदाहरण के लिए, कई प्रसंस्करण इकाइयों को इनपुट के अलग-अलग हिस्सों को सौंपा जा सकता है।

माध्य का अनुमान लगाने की चैन की विधि संख्यात्मक रूप से अस्थिर होती है $n_{A}\approx n_{B}$ और दोनों बड़े हैं, क्योंकि इसमें संख्यात्मक त्रुटि है $\delta ={\bar {x}}_{B}-{\bar {x}}_{A}$ उस तरह से कम नहीं किया गया है जैसा कि इसमें है $n_{B}=1$ मामला। ऐसे मामलों में, प्राथमिकता दें ${\textstyle {\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

इसे उन्नत वेक्टर एक्सटेंशन, ग्राफ़िक्स प्रोसेसिंग युनिट और कंप्यूटर क्लस्टर और सहप्रसरण के साथ समानांतरीकरण की अनुमति देने के लिए सामान्यीकृत किया जा सकता है।

उदाहरण

मान लें कि सभी फ़्लोटिंग पॉइंट ऑपरेशन मानक IEEE 754#डबल-प्रिसिजन 64 बिट|IEEE 754 डबल-प्रिसिजन अंकगणित का उपयोग करते हैं। अनंत जनसंख्या से नमूने (4, 7, 13, 16) पर विचार करें। इस नमूने के आधार पर, अनुमानित जनसंख्या माध्य 10 है, और जनसंख्या भिन्नता का निष्पक्ष अनुमान 30 है। भोले एल्गोरिदम और दो-पास एल्गोरिदम दोनों इन मूल्यों की सही गणना करते हैं।

आगे नमूने पर विचार करें (10⁸ + 4, 10⁸ + 7, 10⁸ + 13, 10⁸ + 16), जो पहले नमूने के समान अनुमानित भिन्नता को जन्म देता है। दो-पास एल्गोरिथ्म इस विचरण अनुमान की सही गणना करता है, लेकिन भोला एल्गोरिथ्म 30 के बजाय 29.33333333333332 लौटाता है।

हालाँकि परिशुद्धता की यह हानि सहनीय हो सकती है और इसे भोले-भाले एल्गोरिदम की एक छोटी सी खामी के रूप में देखा जा सकता है, लेकिन ऑफसेट को और बढ़ाने से त्रुटि भयावह हो जाती है। नमूने पर विचार करें (10⁹ + 4, 10⁹ + 7, 10⁹ + 13, 10⁹ + 16). फिर से 30 की अनुमानित जनसंख्या भिन्नता की गणना दो-पास एल्गोरिदम द्वारा सही ढंग से की जाती है, लेकिन भोला एल्गोरिदम अब इसे −170.666666666666666 के रूप में गणना करता है। यह भोले-भाले एल्गोरिथम के साथ एक गंभीर समस्या है और एल्गोरिथम के अंतिम चरण में दो समान संख्याओं के घटाव में भयावह रद्दीकरण के कारण है।

उच्च-क्रम आँकड़े

टेरीबेरी तीसरे और चौथे केंद्रीय क्षणों की गणना के लिए चान के सूत्रों का विस्तार करता है, उदाहरण के लिए तिरछापन और कुकुदता का अनुमान लगाते समय आवश्यक:

${\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}\right)}{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{aligned}}$

यहां ही $M_{k}$ फिर से माध्य से अंतर की शक्तियों का योग है ${\textstyle \sum (x-{\overline {x}})^{k}}$, देना

${\begin{aligned}&{\text{skewness}}=g_{1}={\frac {{\sqrt {n}}M_{3}}{M_{2}^{3/2}}},\\[4pt]&{\text{kurtosis}}=g_{2}={\frac {nM_{4}}{M_{2}^{2}}}-3.\end{aligned}}$

वृद्धिशील मामले के लिए (अर्थात्, $B=\{x\}$), इससे यह सरल हो जाता है:

${\begin{aligned}\delta &=x-m\\[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{aligned}}$

मूल्य को संरक्षित करके $\delta /n$, केवल एक डिवीजन ऑपरेशन की आवश्यकता है और उच्च-क्रम के आँकड़ों की गणना थोड़ी वृद्धिशील लागत के लिए की जा सकती है।

जैसा कि वर्णित है, कर्टोसिस के लिए लागू ऑनलाइन एल्गोरिदम का एक उदाहरण है:

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**2
        term1 = delta * delta_n * n1
        mean = mean + delta_n
        M4 = M4 + term1 * delta_n2 * (n**2 - 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**2) - 3
    return kurtosis

पेबे वृद्धिशील और जोड़ीदार मामलों के लिए, और बाद में पेबाओ एट अल के लिए, इन परिणामों को मनमाने ढंग से क्रम वाले केंद्रीय क्षणों तक विस्तारित करता है। भारित और मिश्रित क्षणों के लिए. वहाँ सहप्रसरण के समान सूत्र भी मिल सकते हैं।

चोई और स्वीटमैन तिरछापन और कुर्टोसिस की गणना करने के लिए दो वैकल्पिक तरीकों की पेशकश करें, जिनमें से प्रत्येक कुछ अनुप्रयोगों में पर्याप्त कंप्यूटर मेमोरी आवश्यकताओं और सीपीयू समय को बचा सकता है। पहला दृष्टिकोण डेटा को डिब्बे में अलग करके सांख्यिकीय क्षणों की गणना करना है और फिर परिणामी हिस्टोग्राम की ज्यामिति से क्षणों की गणना करना है, जो प्रभावी रूप से उच्च क्षणों के लिए एक-पास एल्गोरिदम बन जाता है। एक लाभ यह है कि सांख्यिकीय क्षण की गणना मनमानी सटीकता के साथ की जा सकती है, जैसे कि गणना को सटीकता के साथ ट्यून किया जा सकता है, उदाहरण के लिए, डेटा भंडारण प्रारूप या मूल माप हार्डवेयर। एक यादृच्छिक चर का एक सापेक्ष हिस्टोग्राम पारंपरिक तरीके से बनाया जा सकता है: संभावित मूल्यों की सीमा को डिब्बे में विभाजित किया जाता है और प्रत्येक बिन के भीतर घटनाओं की संख्या को गिना और प्लॉट किया जाता है ताकि प्रत्येक आयत का क्षेत्र उस बिन के भीतर नमूना मूल्यों के हिस्से के बराबर हो:

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

कहाँ $h(x_{k})$ और $H(x_{k})$ बिन पर आवृत्ति और सापेक्ष आवृत्ति का प्रतिनिधित्व करें $x_{k}$ और ${\textstyle A=\sum _{k=1}^{K}h(x_{k})\,\Delta x_{k}}$ हिस्टोग्राम का कुल क्षेत्रफल है. इस सामान्यीकरण के बाद, $n$ कच्चे क्षण और केंद्रीय क्षण $x(t)$ सापेक्ष हिस्टोग्राम से गणना की जा सकती है:

$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}$

$\theta _{n}^{(h)}=\sum _{k=1}^{K}{\Big (}x_{k}-m_{1}^{(h)}{\Big )}^{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}$

जहां सुपरस्क्रिप्ट $^{(h)}$ इंगित करता है कि क्षणों की गणना हिस्टोग्राम से की जाती है। निरंतर बिन चौड़ाई के लिए $\Delta x_{k}=\Delta x$ इन दो अभिव्यक्तियों का उपयोग करके सरल बनाया जा सकता है $I=A/\Delta x$:

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

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

चोई और स्वीटमैन का दूसरा दृष्टिकोणसमय-इतिहास के अलग-अलग खंडों से सांख्यिकीय क्षणों को संयोजित करने की एक विश्लेषणात्मक पद्धति है, ताकि परिणामी समग्र क्षण संपूर्ण समय-इतिहास के हों। इस पद्धति का उपयोग उन क्षणों के बाद के संयोजन के साथ सांख्यिकीय क्षणों की समानांतर गणना के लिए, या अनुक्रमिक समय पर गणना किए गए सांख्यिकीय क्षणों के संयोजन के लिए किया जा सकता है।

अगर $Q$ सांख्यिकीय क्षणों के सेट ज्ञात हैं: $(\gamma _{0,q},\mu _{q},\sigma _{q}^{2},\alpha _{3,q},\alpha _{4,q})\quad$ के लिए $q=1,2,\ldots ,Q$, फिर प्रत्येक $\gamma _{n}$ कर सकना समकक्ष के रूप में व्यक्त किया जाए $n$ कच्चे क्षण:

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

कहाँ $\gamma _{0,q}$ आम तौर पर की अवधि के रूप में लिया जाता है $q^{th}$ समय-इतिहास, या अंकों की संख्या यदि $\Delta t$ स्थिर है.

सांख्यिकीय क्षणों को के रूप में व्यक्त करने का लाभ $\gamma$ है कि $Q$ सेट को जोड़कर जोड़ा जा सकता है, और इसके मूल्य पर कोई ऊपरी सीमा नहीं है $Q$.

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

जहां सबस्क्रिप्ट $_{c}$ संघटित समय-इतिहास या संयुक्त का प्रतिनिधित्व करता है $\gamma$. ये संयुक्त मूल्य हैं $\gamma$ फिर इसे पूर्ण रूप से संयोजित समय-इतिहास का प्रतिनिधित्व करने वाले कच्चे क्षणों में उलटा रूपांतरित किया जा सकता है

$m_{n,c}={\frac {\gamma _{n,c}}{\gamma _{0,c}}}\quad {\text{for }}n=1,2,3,4$

कच्चे क्षणों के बीच ज्ञात संबंध ($m_{n}$) और केंद्रीय क्षण ($\theta _{n}=\operatorname {E} [(x-\mu )^{n}])$) फिर संघटित समय-इतिहास के केंद्रीय क्षणों की गणना करने के लिए उपयोग किया जाता है। अंत में, संक्षिप्त इतिहास के सांख्यिकीय क्षणों की गणना केंद्रीय क्षणों से की जाती है:

$\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$

सहप्रसरण

सहप्रसरण की गणना के लिए बहुत समान एल्गोरिदम का उपयोग किया जा सकता है।

भोला एल्गोरिथ्म

भोला एल्गोरिथ्म है

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

उपरोक्त एल्गोरिदम के लिए, कोई निम्नलिखित पायथन कोड का उपयोग कर सकता है:

def naive_covariance(data1, data2):
    n = len(data1)
    sum1 = sum(data1)
    sum2 = sum(data2)
    sum12 = sum([i1 * i2 for i1, i2 in zip(data1, data2)])

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

माध्य के अनुमान के साथ

विचरण के लिए, दो यादृच्छिक चर का सहप्रसरण भी शिफ्ट-अपरिवर्तनीय है, इसलिए कोई भी दो स्थिर मान दिए गए हैं $k_{x}$ और $k_{y},$ इसे लिखा जा सकता है:

$\operatorname {Cov} (X,Y)=\operatorname {Cov} (X-k_{x},Y-k_{y})={\dfrac {\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}}.$

और फिर से मूल्यों की सीमा के अंदर एक मूल्य चुनने से भयावह रद्दीकरण के खिलाफ फॉर्मूला स्थिर हो जाएगा और साथ ही बड़ी रकम के खिलाफ यह अधिक मजबूत हो जाएगा। प्रत्येक डेटा सेट का पहला मान लेते हुए, एल्गोरिदम को इस प्रकार लिखा जा सकता है:

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

दो-पास

दो-पास एल्गोरिथ्म पहले नमूना माध्य की गणना करता है, और फिर सहप्रसरण की:

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

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

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

दो-पास एल्गोरिथ्म को इस प्रकार लिखा जा सकता है:

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

थोड़ा अधिक सटीक मुआवजा संस्करण अवशेषों पर पूर्ण अनुभवहीन एल्गोरिदम निष्पादित करता है। अंतिम रकम ${\textstyle \sum _{i}x_{i}}$ और ${\textstyle \sum _{i}y_{i}}$ शून्य होना चाहिए, लेकिन दूसरा पास किसी भी छोटी त्रुटि की भरपाई करता है।

ऑनलाइन

एक स्थिर वन-पास एल्गोरिदम मौजूद है, जो विचरण की गणना के लिए ऑनलाइन एल्गोरिदम के समान है, जो सह-पल की गणना करता है ${\textstyle C_{n}=\sum _{i=1}^{n}(x_{i}-{\bar {x}}_{n})(y_{i}-{\bar {y}}_{n})}$:

${\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}}$

उस अंतिम समीकरण में स्पष्ट विषमता इस तथ्य के कारण है ${\textstyle (x_{n}-{\bar {x}}_{n})={\frac {n-1}{n}}(x_{n}-{\bar {x}}_{n-1})}$, इसलिए दोनों अद्यतन शर्तें समान हैं ${\textstyle {\frac {n-1}{n}}(x_{n}-{\bar {x}}_{n-1})(y_{n}-{\bar {y}}_{n-1})}$. पहले साधनों की गणना करके, फिर अवशेषों पर स्थिर वन-पास एल्गोरिदम का उपयोग करके और भी अधिक सटीकता प्राप्त की जा सकती है।

इस प्रकार सहप्रसरण की गणना इस प्रकार की जा सकती है

${\begin{aligned}\operatorname {Cov} _{N}(X,Y)={\frac {C_{N}}{N}}&={\frac {\operatorname {Cov} _{N-1}(X,Y)\cdot (N-1)+(x_{n}-{\bar {x}}_{n})(y_{n}-{\bar {y}}_{n-1})}{N}}\\&={\frac {\operatorname {Cov} _{N-1}(X,Y)\cdot (N-1)+(x_{n}-{\bar {x}}_{n-1})(y_{n}-{\bar {y}}_{n})}{N}}\\&={\frac {\operatorname {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 {\operatorname {Cov} _{N-1}(X,Y)\cdot (N-1)+{\frac {N}{N-1}}(x_{n}-{\bar {x}}_{n})(y_{n}-{\bar {y}}_{n})}{N}}.\end{aligned}}$

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)

भारित सहप्रसरण की गणना के लिए एक छोटा संशोधन भी किया जा सकता है:

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)

इसी तरह, दो सेटों के सहप्रसरणों को संयोजित करने का एक सूत्र है जिसका उपयोग गणना को समानांतर करने के लिए किया जा सकता है:

$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}}}.$

भारित बैच संस्करण

भारित ऑनलाइन एल्गोरिथम का एक संस्करण जो बैच अद्यतन करता है वह भी मौजूद है: चलो $w_{1},\dots w_{N}$ वज़न दर्शाएं और लिखें

${\begin{alignedat}{2}{\bar {x}}_{n+k}&={\bar {x}}_{n}&\,+\,&{\frac {\sum _{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}}$

इसके बाद सहप्रसरण की गणना इस प्रकार की जा सकती है

$\operatorname {Cov} _{N}(X,Y)={\frac {C_{N}}{\sum _{i=1}^{N}w_{i}}}$

यह भी देखें

• कहान योग एल्गोरिथ्म
• माध्य से वर्ग विचलन
• यामार्टिनो विधि

बाहरी संबंध

• Weisstein, Eric W. "Sample Variance Computation". MathWorld.