اجماع نمونه تصادفی کیست؟ توضیح بده.
اجماع نمونه تصادفی یک روش تکرار شونده () است برای تخمین پارامترهای یک مدل ریاضی روی یک مجموعه داده که شامل داده‌های پرت است، به طوری که داده‌های پرت تأثیری روی تخمینی که زده می‌شود نداشته باشند. با این تعریف، از این روش می‌توان به عنوان یک روش برای تشخیص داده پرت نیز یاد کرد. RANSAC در حقیقت یک الگوریتم غیرقطعی است، بدین معنا که تنها به یک احتمال مشخصی جواب مطلوب می‌دهد که این احتمال با افزایش تعداد دفعات اجرای الگوریتم بیشتر می‌شود. این الگوریتم در ابتدا توسط Fischler و Bolles در اس‌آرآی اینترنشنال در سال ۱۹۸۱ منتشر شد. آنها از RANSAC برای حل مسئله تعیین موقعیت (به انگلیسی: Location Determination Problem) استفاده کردند. در این مسئله هدف تعیین نقاطی در فضا است که نگاشت آنها روی یک تصویر بر روی مجموعه مشخصی از نقاط می‌افتد.RANSAC از استفاده می‌کند. یکی از فرض‌های پایه‌ای الگوریتم این است که داده‌ها شامل داده درونی و داده‌های پرت هستند. منظور از داده‌های درونی، داده‌هایی هستند که توزیع آن‌ها قابل بیان توسط مجموعه‌ای از پارامترهای یک مدل است و البته می‌توانند شامل مقداری نویز باشند. داده‌های پرت هم داده‌هایی هستند که با مدل مدنظر سازگار نیستند. منشأ داده‌های پرت می‌تواند مقادیر خیلی زیاد نویز، یا اندازه‌گیری‌های خطادار (هنگام جمع‌آوری داده) یا فرض اشتباه در مورد داده‌ها باشد. RANSAC همچنین این فرض را دارد که با داشتن مجموعه‌ای (معمولا کوچک) از داده‌های درونی، فرایندی وجود دارد که با استفاده از آن می‌تواند پارامترهای مدلی که به صورت بهینه توزیع داده‌ها را بیان می‌کند و با داده‌ها سازگار است، برآورد کرد.مثال.یک مثال ساده، برازش یک خط در دو بعد به یک مجموعه از مشاهدات است. با فرض اینکه این مجموعه هم شامل داده‌های درونی است، یعنی داده‌هایی که به‌طور تقریبی می‌توانند به یک خط برازش شوند، و هم داده‌های پرت، داده‌هایی که به این خط نمی‌توانند برازش شوند، استفاده از روش کمترین مربعات معمولی باعث می‌شود خطی بدست آید که به خوبی به این مجموعه داده برازش نشود. چرا که سعی شده‌است که این خط به همه نقاط برازش شود، که شامل داده‌های پرت نیز هستند. RANSAC اما سعی می‌کند داده‌های پرت را جزو داده‌های مورد استفاده هنگام برازش در نظر نگیرد و مدلی خطیای بیابد که هنگام برازش شدن تنها از داده‌های درونی استفاده می‌کند. این کار با برازش کردن مدل خطی به چندین زیرمجموعه از داده‌ها که تصادفی انتخاب شده‌اند و انتخاب مدلی که بهترین برازش را به زیرمجموعه ای از داده‌ها داشته‌است، انجام می‌شود. از آنجا که داده‌های درونی نسبت به مخلوطی تصادفی از داده‌های درونی و داده‌های پرت، بیشتر به صورت خطی به هم مرتبط هستند، زیرمجموعه تصادفی ای که به صورت کامل از داده‌های درونی تشکیل شده باشد، بهترین برازش مدل خطی را حاصل می‌شود. در عمل، هیچ تضمینی وجود ندارد که زیرمجموعه‌ای انتخاب شود که تنها شامل داده‌های درونی باشد و احتمال موفقیت الگوریتم به نسبت داده‌های درونی به کل داده‌ها و انتخاب پارامترهای الگوریتم بستگی دارد.بررسی اجمالی.الگوریتم RANSAC یک الگوریتم یادگیری برای تخمین پارامترهای یک مدل با نمونه‌گیری تصادفی از داده‌های مشاهده شده‌است. RANSAC با یک روش رای‌گیری، سعی می‌کند تا برازش بهینه را بر روی مجموعه داده‌ای که هم شامل داده‌های درونی و هم داده‌های پرت است، بیابد. هر یک از نمونه‌های موجود در مجموعه داده برای رای‌گیری برای یک یا چند مدل استفاده می‌شوند. پیاده‌سازی این رای‌گیری بر ۲ فرض استوار است: اینکه داده‌های پرت زیاد نیستند تا همواره تأثیر منفی روی رای‌گیری بگذارند و اینکه داده‌های درونی به قدری کافی هستند که بتوان مدل خوبی یافت تا توزیع داده‌های درونی را به خوبی بیان کند یا به به عبارتی دیگر، داده‌های از دست رفته زیاد نیستند. الگوریتم RANSAC شامل دو مرحله است که مکرراً اجرا می‌شوند:مجموعه داده‌های درونی بدست آمده برای مدل برازش شونده مجموعه اجماع نام می‌گیرد. الگوریتم RANSAC این دو مرحله را آنقدر تکرار می‌کند تا مجموعه اجماع به دست آمده اندازه مطلوب را داشته باشد.ورودی الگوریتم شامل یک مجموعه داده، روشی برای برازش کردن یک مدل به مشاهدات و تعدادی پارامترهای اطمینان است. روند الگوریتم به صورت دقیق تر در زیر آورده شده‌است:این روند تعداد مشخصی بار اجرا می‌شود و هر بار یا مدل به دلیل سازگاری با تعداد کمی از اعضای مجموعه داده رد می‌شود، یا یک مدل بهبود یافته بهمراه مجموعه اجماع متناظر با آن بدست می‌آید. در حالت دوم، مدل را به عنوان مدل بهینه تا اینجای کار در نظر می‌گیریم اگر اندازه مجموعه اجماع آن از اندازه مجموعه اجماع متناظر مدل بهینه قبلی بزرگتر باشد.الگوریتم.شبه کد الگوریتم RANSAC در زیر آورده شده‌است:&lt;syntaxhighlight&gt;Given: data – A set of observations. model – A model to explain observed data points. n – Minimum number of data points required to estimate model parameters. k – Maximum number of iterations allowed in the algorithm. t – Threshold value to determine data points that are fit well by model. d – Number of close data points required to assert that a model fits well to data.Return: bestFit – model parameters which best fit the data (or null if no good model is found)iterations = 0bestFit = nullbestErr = something really largewhile iterations &lt; k do maybeInliers := n randomly selected values from data maybeModel := model parameters fitted to maybeInliers alsoInliers := empty set for every point in data not in maybeInliers do if point fits maybeModel with an error smaller than t add point to alsoInliers end if end for if the number of elements in alsoInliers is &gt; d then // This implies that we may have found a good model // now test how good it is. betterModel := model parameters fitted to all points in maybeInliers and alsoInliers thisErr := a measure of how well betterModel fits these points if thisErr &lt; bestErr then bestFit := betterModel bestErr := thisErr end if end if increment iterationsend whilereturn bestFit&lt;/syntaxhighlight&gt;کد نمونه.در این قطعه علاوه بر پیاده‌سازی شبه کد، کد یک codice_1 بر پایه کمترین مربعات تعریف شده‌است. همچنین الگوریتم codice_2 بر روی یک مسئله رگرسیون دوبعدی اعمال می‌شود و نتایج به تصویر کشیده شده‌اند:from copy import copyimport numpy as npfrom numpy.random import default_rngrng = default_rng()class RANSAC: def __init__(self, n=10, k=100, t=0.05, d=10, model=None, loss=None, metric=None): self.n = n # `n`: Minimum number of data points to estimate parameters self.k = k # `k`: Maximum iterations allowed self.t = t # `t`: Threshold value to determine if points are fit well self.d = d # `d`: Number of close data points required to assert model fits well self.model = model # `model`: class implementing `fit` and `predict` self.loss = loss # `loss`: function of `y_true` and `y_pred` that returns a vector self.metric = metric # `metric`: function of `y_true` and `y_pred` and returns a float self.best_fit = None self.best_error = np.inf def fit(self, X, y): for _ in range(self.k): ids = rng.permutation(X.shape[0]) maybe_inliers = ids[: self.n] maybe_model = copy(self.model).fit(X[maybe_inliers], y[maybe_inliers]) thresholded = ( self.loss(y[ids][self.n :], maybe_model.predict(X[ids][self.n :])) &lt; self.t inlier_ids = ids[self.n :][np.flatnonzero(thresholded).flatten()] if inlier_ids.size &gt; self.d: inlier_points = np.hstack([maybe_inliers, inlier_ids]) better_model = copy(self.model).fit(X[inlier_points], y[inlier_points]) this_error = self.metric( y[inlier_points], better_model.predict(X[inlier_points]) if this_error &lt; self.best_error: self.best_error = this_error self.best_fit = maybe_model return self def predict(self, X): return self.best_fit.predict(X)def square_error_loss(y_true, y_pred): return (y_true - y_pred) ** 2def mean_square_error(y_true, y_pred): return np.sum(square_error_loss(y_true, y_pred)) / y_true.shape[0]class LinearRegressor: def __init__(self): self.params = None def fit(self, X: np.ndarray, y: np.ndarray): r, _ = X.shape X = np.hstack([np.ones((r, 1)), X]) self.params = np.linalg.inv(X.T @ X) @ X.T @ y return self def predict(self, X: np.ndarray): r, _ = X.shape X = np.hstack([np.ones((r, 1)), X]) return X @ self.paramsif __name__ == "__main__": regressor = RANSAC(model=LinearRegressor(), loss=square_error_loss, metric=mean_square_error) X = np.array([-0.848,-0.800,-0.704,-0.632,-0.488,-0.472,-0.368,-0.336,-0.280,-0.200,-0.00800,-0.0840,0.0240,0.100,0.124,0.148,0.232,0.236,0.324,0.356,0.368,0.440,0.512,0.548,0.660,0.640,0.712,0.752,0.776,0.880,0.920,0.944,-0.108,-0.168,-0.720,-0.784,-0.224,-0.604,-0.740,-0.0440,0.388,-0.0200,0.752,0.416,-0.0800,-0.348,0.988,0.776,0.680,0.880,-0.816,-0.424,-0.932,0.272,-0.556,-0.568,-0.600,-0.716,-0.796,-0.880,-0.972,-0.916,0.816,0.892,0.956,0.980,0.988,0.992,0.00400]).reshape(-1,1) y = np.array([-0.917,-0.833,-0.801,-0.665,-0.605,-0.545,-0.509,-0.433,-0.397,-0.281,-0.205,-0.169,-0.0531,-0.0651,0.0349,0.0829,0.0589,0.175,0.179,0.191,0.259,0.287,0.359,0.395,0.483,0.539,0.543,0.603,0.667,0.679,0.751,0.803,-0.265,-0.341,0.111,-0.113,0.547,0.791,0.551,0.347,0.975,0.943,-0.249,-0.769,-0.625,-0.861,-0.749,-0.945,-0.493,0.163,-0.469,0.0669,0.891,0.623,-0.609,-0.677,-0.721,-0.745,-0.885,-0.897,-0.969,-0.949,0.707,0.783,0.859,0.979,0.811,0.891,-0.137]).reshape(-1,1) regressor.fit(X, y) import matplotlib.pyplot as plt plt.style.use("seaborn-darkgrid") fig, ax = plt.subplots(1, 1) ax.set_box_aspect(1) plt.scatter(X, y) line = np.linspace(-1, 1, num=100).reshape(-1, 1) plt.plot(line, regressor.predict(line), c="peru") plt.show()