موضوع مقاله: اجماع نمونه تصادفی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # اجماع نمونه تصادفی | مقدمه: اجماع نمونه تصادفی یک روش تکرار شونده (iterative method) است برای تخمین پارامترهای یک مدل ریاضی روی یک مجموعه داده که شامل داده‌های پرت است، به طوری که داده‌های پرت تأثیری روی تخمینی که زده می‌شود نداشته باشند. | ## بخش 1: اجماع نمونه تصادفی | در این مسئله هدف تعیین نقاطی در فضا است که نگاشت آنها روی یک تصویر بر روی مجموعه مشخصی از نقاط می‌افتد. یکی از فرض‌های پایه‌ای الگوریتم این است که داده‌ها شامل داده درونی و داده‌های پرت هستند. منظور از داده‌های درونی، داده‌هایی هستند که توزیع آن‌ها قابل بیان توسط مجموعه‌ای از پارامترهای یک مدل است و البته می‌توانند شامل مقداری نویز باشند. منشأ داده‌های پرت می‌تواند مقادیر خیلی زیاد نویز، یا اندازه‌گیری‌های خطادار (هنگام جمع‌آوری داده) یا فرض اشتباه در مورد داده‌ها باشد. RANSAC همچنین این فرض را دارد که با داشتن مجموعه‌ای (معمولا کوچک) از داده‌های درونی، فرایندی وجود دارد که با استفاده از آن می‌تواند پارامترهای مدلی که به صورت بهینه توزیع داده‌ها را بیان می‌کند و با داده‌ها سازگار است، برآورد کرد. با فرض اینکه این مجموعه هم شامل داده‌های درونی است، یعنی داده‌هایی که به‌طور تقریبی می‌توانند به یک خط برازش شوند، و هم داده‌های پرت، داده‌هایی که به این خط نمی‌توانند برازش شوند، استفاده از روش کمترین مربعات معمولی باعث می‌شود خطی بدست آید که به خوبی به این مجموعه داده برازش نشود. چرا که سعی شده‌است که این خط به همه نقاط برازش شود، که شامل داده‌های پرت نیز هستند. RANSAC اما سعی می‌کند داده‌های پرت را جزو داده‌های مورد استفاده هنگام برازش در نظر نگیرد و مدلی خطیای بیابد که هنگام برازش شدن تنها از داده‌های درونی استفاده می‌کند. این کار با برازش کردن مدل خطی به چندین زیرمجموعه از داده‌ها که تصادفی انتخاب شده‌اند و انتخاب مدلی که بهترین برازش را به زیرمجموعه ای از داده‌ها داشته‌است، انجام می‌شود. از آنجا که داده‌های درونی نسبت به مخلوطی تصادفی از داده‌های درونی و داده‌های پرت، بیشتر به صورت خطی به هم مرتبط هستند، زیرمجموعه تصادفی ای که به صورت کامل از داده‌های درونی تشکیل شده باشد، بهترین برازش مدل خطی را حاصل می‌شود. | ## بخش 2: اجماع نمونه تصادفی | در عمل، هیچ تضمینی وجود ندارد که زیرمجموعه‌ای انتخاب شود که تنها شامل داده‌های درونی باشد و احتمال موفقیت الگوریتم به نسبت داده‌های درونی به کل داده‌ها و انتخاب پارامترهای الگوریتم بستگی دارد. بررسی اجمالی الگوریتم RANSAC یک الگوریتم یادگیری برای تخمین پارامترهای یک مدل با نمونه‌گیری تصادفی از داده‌های مشاهده شده‌است. RANSAC با یک روش رای‌گیری، سعی می‌کند تا برازش بهینه را بر روی مجموعه داده‌ای که هم شامل داده‌های درونی و هم داده‌های پرت است، بیابد. هر یک از نمونه‌های موجود در مجموعه داده برای رای‌گیری برای یک یا چند مدل استفاده می‌شوند. پیاده‌سازی این رای‌گیری بر ۲ فرض استوار است: اینکه داده‌های پرت زیاد نیستند تا همواره تأثیر منفی روی رای‌گیری بگذارند و اینکه داده‌های درونی به قدری کافی هستند که بتوان مدل خوبی یافت تا توزیع داده‌های درونی را به خوبی بیان کند یا به به عبارتی دیگر، داده‌های از دست رفته زیاد نیستند. الگوریتم RANSAC شامل دو مرحله است که مکرراً اجرا می‌شوند: در مرحله اول، یک زیرمجموعه نمونه به صورت تصادفی از مجموعه داده ورودی انتخاب می‌شود. یک مدل برازش شده و پارامترهای آن با استفاده از اعضای این زیرمجموعه به دست می‌آیند. اندازه زیرمجموعه به کوچک‌ترین مقداری است که برای تعیین پارامترهای مدل کافی باشد. در مرحله دوم، الگوریتم بررسی می‌کند که کدام اعضای کل مجموعه داده با مدل به دست آمده از بخش قبل سازگار هستند. یک عضو از مجموعه داده به عنوان داده پرت شناخته می‌شود اگر میزان ناسازگاری آن با مدل از یک حد مشخص بیشتر باشد. | ## بخش 3: اجماع نمونه تصادفی | الگوریتم RANSAC این دو مرحله را آنقدر تکرار می‌کند تا مجموعه اجماع به دست آمده اندازه مطلوب را داشته باشد. ورودی الگوریتم شامل یک مجموعه داده، روشی برای برازش کردن یک مدل به مشاهدات و تعدادی پارامترهای اطمینان است. روند الگوریتم به صورت دقیق تر در زیر آورده شده‌است: انتخاب یک زیرمجموعه تصادفی از داده‌های اصلی. نمونه‌هایی که با توجه به یک تابع هزینه با مدل سازگار هستند، در مجموعه اجماع قرار می‌گیرند. مدل بدست آمده خوب تلقی می‌شود اگر تعداد نمونه‌هایی که در مجموعه اجماع قرار می‌گیرند کافی باشد. سپس، مدل می‌تواند با برآورد دوباره پارامترها، اما این بار روی مجموعه اجماع، بهتر شود. این روند تعداد مشخصی بار اجرا می‌شود و هر بار یا مدل به دلیل سازگاری با تعداد کمی از اعضای مجموعه داده رد می‌شود، یا یک مدل بهبود یافته بهمراه مجموعه اجماع متناظر با آن بدست می‌آید. در حالت دوم، مدل را به عنوان مدل بهینه تا اینجای کار در نظر می‌گیریم اگر اندازه مجموعه اجماع آن از اندازه مجموعه اجماع متناظر مدل بهینه قبلی بزرگتر باشد. | ## جمع‌بندی | خط نارنجی بیانگر پارامترهای کمترین مربعات است که به صورت موفقیت‌آمیز توانسته‌است از نقاط پرت چشم‌پوشی کند.