موضوع مقاله: الگوریتم محاسبه واریانس | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم محاسبه واریانس | مقدمه: چون Sum_sqr و (Sum*Sum)/n می‌توانند مقدار بسیار نزدیکی داشته باشند، تقریب زدن می‌تواند منجر شود که دقت نتیجه بسیار کمتر از دقت ذاتی موجود در محاسبات ممیز شناور شود. | ## بخش 1: الگوریتم محاسبه واریانس | این موضوع بخصوص در مواردی که انحراف معیار نسبت به میانگین بسیار کوچک است، تشدید می‌شود. نتایج هر دو الگوریتم می‌تواند بی اندازه، به ترتیب داده ها وابسته باشد و می‌تواند نتایج ضعیفی برای مجموعه داده‌های بسیار بزرگ (بخاطر تکرر خطای گرد کردن) داشته باشد. تکنیکهایی همچون مجموعِ جبران شده می‌تواند تا درجه‌ای برای از بین بردن این خطا مورد استفاده قرار گیرند. برای چنین الگوریتم برخطی، رابطه رخداد مجدد بین کمیتهایی مورد استفاده در محاسبات، مورد نیاز می‌باشد تا محاسبات ما به صورت به روشی سازگار انجام شود. فرمول‌های زیر برای به روزرسانی میانگین و واریانس(تخمینی) داده‌ها، در زمان افزودن عنصر جدید استفاده می‌شود. در اینجا، n نشان دهنده میانگین n نمونهٔ اول (x1, ..., xn) و s2n واریانس نمونه و σ2N واریانس جامعهٔ آماری آنهاست. همچنین می‌توان نشان داد که کمیت مناسبتر برای به روزرسانی مجموع مربعات فاصله از میانگین کنونی ، با عنوان دراینجا نشان داده شده‌است: یک الگوریتم عددی سازگار به صورت زیر داده شده‌است، که البته میانگین را نیز محاسبه می نماید. برای الگوریتم عظیمتر دومرحله‌ای برای محاسبه واریانس، بهتر است ابتدا تخمینی از میانگین را محاسبه کنیم و سپس در ادامه از این الگوریتم استفاده نماییم. الگوریتم موازی که در ادامه خواهد آمد، نشان می‌دهد که چگونه چندین مجموعه آماری را که به صورت برخط محاسبه می‌شوند، ادغام نمود. الگوریتم افزایشی وزن دار این الگوریتم می‌تواند برای کنترل نمونه‌های دارای وزن تعمیم یابد، بدین صورت که می‌توان شمارنده n را برای مجموع وزنهایی مشاهده شده تاکنون استفاده کرد. می‌گوید که سومین الگوریتم برخط فوق، نمونه‌ای خاص از الگوریتم است که برای هر تقسیم‌بندی از نمونه به مجموعه‌های , درست عمل می‌کند: . | ## بخش 2: الگوریتم محاسبه واریانس | این موضوع می‌تواند زمانی مفید باشد که برای مثال، چندین واحد پرداش برای قسمت‌های مختلف از ورودی در نظر گرفته شده باشد. شیوه Chan روشی برای تخمین میانگین، زمانی که و هر دو بسیار بزرگ باشند، از لحاظ عددی نامطمئن است، چراکه خطای عددی موجود در متناسب با زمانی نیست که . براساس این نمونه، میانگین تخمینی جامعه برابر با 10 است و واریانس تخمینی بدون پیشقدرِ جامعه برابر با 30 است. سپس نمونه { 108 + 4, 108 + 7, 108 + 13, 108 + 16 } را در نظر بگیرید، که مقدار واریانسی برابر با نمونهٔ قبلی به ما می‌دهد. الگوریتم دوم این واریانس تخمینی را به درستی محاسبه می‌کند، اما الگوریتم اول مقدار 29.33333333 را به جای 30 برمی‌گرداند. اگرچه این کمبود دقت قابل تحمل است و به عنوان نقص کوچکی در الگوریتم اول مشاهده می‌شود، اما به سادگی داده‌هایی یافت که نقص اساسی در الگوریتم naive را آشکار میسازد: نمونهٔ { 109 + 4, 109 + 7, 109 + 13, 109 + 16 } را در نظر بگیرید. دوباره واریانس تخمینی برابر با 30 می‌باشد که توسط الگوریتم دوم به سادگی قابل محاسبه است، اما این دفعه الگوریتم naive مقدار −170.66666666666666 را به عنوان جواب برمی‌گرداند. این یک مشکل اساسی در الگوریتم اول می‌باشد و بخاطر تقریب زدن فاجعه آمیزی رخ داده است که در مرحله آخر الگوریتم، هنگام تفریق دو عدد مشابه صورت گرفته‌است. برای مثال برای تخمین چولگی و کشیدگی مورد نیاز است: اینجا برابر با توان‌های فاصله با میانه است که نتیجه می‌دهد: چولگی: کشیدگی: برای نسخه افزایشی (مثلاً )، به صورت زیر ساده می‌شود: با نگهداشتن مقدار ، فقط یک عمل تقسیم مورد نیاز است و آمار رده بالاتر می‌تواند بنابراین برای هزینه افزایشی محاسبه شود. روش اول، برای محاسبه گشتاورهای آماری، با جداسازی داده‌ها، گشتاورها را از رابطه هندسیِ هیستوگرامِ به دست آمده محاسبه می‌کند، که به صورت بهینه‌ای تبدیل به یک الگوریتم یک مرحله‌ای برای گشتاورهای بالاتر می‌شود. یکی از مزایای کار این است که محاسبات گشتاورهای آماری می‌تواند با دقت اختیاری محاسبه شود، پس می‌توان این دقت را با دقت فرمت انبار داده ویا سخت افزار اندازه‌گیری اصلی، منطبق کرد. | ## بخش 3: الگوریتم محاسبه واریانس | هیستوگرام نسبی از یک متغیر تصادفی می‌تواند یک در این راه قراردادی ساخته شود: محدوده مقادیر بالقوه به بازه‌هایی تقسیم می‌شود و تعداد رخدادها در هر بازه شمارش و به گونه‌ای کشیده می‌شود که مساحت هر مستطیل برابر با سهم رخدادهای آن بازه شود: که و نشاندهندهٔ میزان فرکانس و فرکانس نسبی در بازهٔ است و مجموع تمام نواحی هیستوگرام است. بعد از نرمال سازی، گشتاور خام و گشتاورهای مرکزیِ می‌تواند از هیستوگرام نسبی محاسبه شود: که توان نشان دهنده گشتاورهایی است که از هیستوگرام محاسبه شده‌است. برای بازهٔ با ضخامت ثابت این دو عبارت می‌تواند با استفاده از ساده شود: دومین روش Choi و Sweetman یک متدولوژی تحلیلی برای ترکیب گشتاورهای آماری از بخش‌های مجزا از یک بازهٔ زمانی است که گشتاورهای کلی بدست آمده، همان گشتاورهای بازهٔ زمانی کامل است. این متدولوژی می‌تواند برای محاسبه موازی گشتاورهای آماری با کمک ترکیب گشتاورهای پس آیند(بعدی) ویا ترکیب گشتاورهای آماری محاسبه شده در زمان‌های پشت سرهم، استفاده شود. اگر تعداد مجموعه از گشتاورهای آماری به این صورت نمایش داده شوند: که در آن است، سپس هر می‌تواند براساس گشتاور اولیه معادل نمایش داده شود: که به صورت کلی در طول بازهٔ زمانی بدست آمده‌است یا تعداد نقاطی که ثابت است. مزیت نمایش گشتاورهای آماری براساس این است که مجموعه می‌توانند با عمل جمع ترکیب شوند و محدودیتی در مقدار نیست. این مقادیر ترکیب شده از می‌تواند سپس به صورت معکوس به گشتاورهای خام که تمام بازهٔ ترکیبی را نشان می‌دهند، تبدیل شوند: روابط مشاهده شده بین گشتاورهای خام و گشتاورهای مرکزی ، سپس برای محاسبه گشتاورهای مرکزیِ ترکیبِ بازه زمانی مورد استفاده قرار می‌گیرد. در پایان، گشتاورهای آماری بازهٔ ترکیبی از گشتاورهای مرکزی محاسبه می‌شوند: کوواریانس الگوریتم‌های کاملاً مشابهی هم می‌تواند برای محاسبه کوواریانس به کار برده شود. یک الگوریتم تک مرحله‌ای مطمئنی، مشابه با مورد بالا، وجود دارد، که گشتاورهای مشترک را محاسبه می‌کند: عدم تقارن آشکار در تساوی آخر بخاطر این است که ، پس هر دو عبارت به روزرسانی برابرند با: . با محاسبهٔ میانگین‌ها می‌توان به دقت بالاتری دست یافت، سپس بااستفاده از الگوریتم تک مرحله‌ای مطمئن بر روی بقیه استفاده کرد. | ## جمع‌بندی | بنابراین ما می‌توانیم کوواریانس را به این صورت به دست آوریم: به همین ترتیب، فرمولی برای ترکیب کوواریانس دو مجموعه برای موازی‌سازی محاسبات وجود دارد: .