اجماع نمونه تصادفی
اجماع نمونه تصادفی (به انگلیسی: Random sample consensus) یک روش تکرار شونده (iterative method) است برای تخمین پارامترهای یک مدل ریاضی روی یک مجموعه داده که شامل دادههای پرت است، به طوری که دادههای پرت تأثیری روی تخمینی که زده میشود نداشته باشند. با این تعریف، از این روش میتوان به عنوان یک روش برای تشخیص داده پرت نیز یاد کرد.[۱] RANSAC در حقیقت یک الگوریتم غیرقطعی است، بدین معنا که تنها به یک احتمال مشخصی جواب مطلوب میدهد که این احتمال با افزایش تعداد دفعات اجرای الگوریتم بیشتر میشود. این الگوریتم در ابتدا توسط Fischler و Bolles در اسآرآی اینترنشنال در سال ۱۹۸۱ منتشر شد. آنها از RANSAC برای حل مسئله تعیین موقعیت (به انگلیسی: Location Determination Problem) استفاده کردند. در این مسئله هدف تعیین نقاطی در فضا است که نگاشت آنها روی یک تصویر بر روی مجموعه مشخصی از نقاط میافتد.
RANSAC از نمونهگیری تصادفی فرعی[۲] استفاده میکند. یکی از فرضهای پایهای الگوریتم این است که دادهها شامل داده درونی و دادههای پرت هستند. منظور از دادههای درونی، دادههایی هستند که توزیع آنها قابل بیان توسط مجموعهای از پارامترهای یک مدل است و البته میتوانند شامل مقداری نویز باشند. دادههای پرت هم دادههایی هستند که با مدل مدنظر سازگار نیستند. منشأ دادههای پرت میتواند مقادیر خیلی زیاد نویز، یا اندازهگیریهای خطادار (هنگام جمعآوری داده) یا فرض اشتباه در مورد دادهها باشد. RANSAC همچنین این فرض را دارد که با داشتن مجموعهای (معمولا کوچک) از دادههای درونی، فرایندی وجود دارد که با استفاده از آن میتواند پارامترهای مدلی که به صورت بهینه توزیع دادهها را بیان میکند و با دادهها سازگار است، برآورد کرد.
مثال[ویرایش]
یک مثال ساده، برازش یک خط در دو بعد به یک مجموعه از مشاهدات است. با فرض اینکه این مجموعه هم شامل دادههای درونی است، یعنی دادههایی که بهطور تقریبی میتوانند به یک خط برازش شوند، و هم دادههای پرت، دادههایی که به این خط نمیتوانند برازش شوند، استفاده از روش کمترین مربعات معمولی باعث میشود خطی بدست آید که به خوبی به این مجموعه داده برازش نشود. چرا که سعی شدهاست که این خط به همه نقاط برازش شود، که شامل دادههای پرت نیز هستند. RANSAC اما سعی میکند دادههای پرت را جزو دادههای مورد استفاده هنگام برازش در نظر نگیرد و مدلی خطیای بیابد که هنگام برازش شدن تنها از دادههای درونی استفاده میکند. این کار با برازش کردن مدل خطی به چندین زیرمجموعه از دادهها که تصادفی انتخاب شدهاند و انتخاب مدلی که بهترین برازش را به زیرمجموعه ای از دادهها داشتهاست، انجام میشود. از آنجا که دادههای درونی نسبت به مخلوطی تصادفی از دادههای درونی و دادههای پرت، بیشتر به صورت خطی به هم مرتبط هستند، زیرمجموعه تصادفی ای که به صورت کامل از دادههای درونی تشکیل شده باشد، بهترین برازش مدل خطی را حاصل میشود. در عمل، هیچ تضمینی وجود ندارد که زیرمجموعهای انتخاب شود که تنها شامل دادههای درونی باشد و احتمال موفقیت الگوریتم به نسبت دادههای درونی به کل دادهها و انتخاب پارامترهای الگوریتم بستگی دارد.
-
مجموعه دادهای که شامل تعداد زیادی دادهپرت است و باید خطی به به این مجموعه داده برازش شود
-
خط برازش شده با استفاده از الگوریتم RANSAC؛ دادههای پرت تاثیری روی نتیجه ندارند
بررسی اجمالی[ویرایش]
الگوریتم RANSAC یک الگوریتم یادگیری برای تخمین پارامترهای یک مدل با نمونهگیری تصادفی از دادههای مشاهده شدهاست. RANSAC با یک روش رایگیری، سعی میکند تا برازش بهینه را بر روی مجموعه دادهای که هم شامل دادههای درونی و هم دادههای پرت است، بیابد. هر یک از نمونههای موجود در مجموعه داده برای رایگیری برای یک یا چند مدل استفاده میشوند. پیادهسازی این رایگیری بر ۲ فرض استوار است: اینکه دادههای پرت زیاد نیستند تا همواره تأثیر منفی روی رایگیری بگذارند و اینکه دادههای درونی به قدری کافی هستند که بتوان مدل خوبی یافت تا توزیع دادههای درونی را به خوبی بیان کند یا به به عبارتی دیگر، دادههای از دست رفته زیاد نیستند. الگوریتم RANSAC شامل دو مرحله است که مکرراً اجرا میشوند:
- در مرحله اول، یک زیرمجموعه نمونه به صورت تصادفی از مجموعه داده ورودی انتخاب میشود. یک مدل برازش شده و پارامترهای آن با استفاده از اعضای این زیرمجموعه به دست میآیند. اندازه زیرمجموعه به کوچکترین مقداری است که برای تعیین پارامترهای مدل کافی باشد.
- در مرحله دوم، الگوریتم بررسی میکند که کدام اعضای کل مجموعه داده با مدل به دست آمده از بخش قبل سازگار هستند. یک عضو از مجموعه داده به عنوان داده پرت شناخته میشود اگر میزان ناسازگاری آن با مدل از یک حد مشخص بیشتر باشد. در واقع این حد بیانگر بیشترین میزان انحراف قابل انتساب به تأثیرات نویز است.
مجموعه دادههای درونی بدست آمده برای مدل برازش شونده مجموعه اجماع نام میگیرد. الگوریتم RANSAC این دو مرحله را آنقدر تکرار میکند تا مجموعه اجماع به دست آمده اندازه مطلوب را داشته باشد.
ورودی الگوریتم شامل یک مجموعه داده، روشی برای برازش کردن یک مدل به مشاهدات و تعدادی پارامترهای اطمینان است. روند الگوریتم به صورت دقیق تر در زیر آورده شدهاست:
- انتخاب یک زیرمجموعه تصادفی از دادههای اصلی. این زیرمجموعه دادههای درونی فرضی نام دارد.
- یک مدل به مجموعهٔ دادههای درونی فرضی برازش میشود.
- سپس کل دادههای مجموعه داده بر روی مدل برازش شده تست میشوند. نمونههایی که با توجه به یک تابع هزینه با مدل سازگار هستند، در مجموعه اجماع قرار میگیرند.
- مدل بدست آمده خوب تلقی میشود اگر تعداد نمونههایی که در مجموعه اجماع قرار میگیرند کافی باشد.
- سپس، مدل میتواند با برآورد دوباره پارامترها، اما این بار روی مجموعه اجماع، بهتر شود.
این روند تعداد مشخصی بار اجرا میشود و هر بار یا مدل به دلیل سازگاری با تعداد کمی از اعضای مجموعه داده رد میشود، یا یک مدل بهبود یافته بهمراه مجموعه اجماع متناظر با آن بدست میآید. در حالت دوم، مدل را به عنوان مدل بهینه تا اینجای کار در نظر میگیریم اگر اندازه مجموعه اجماع آن از اندازه مجموعه اجماع متناظر مدل بهینه قبلی بزرگتر باشد.
الگوریتم[ویرایش]
شبه کد الگوریتم RANSAC در زیر آورده شدهاست:
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 = 0
bestFit = null
bestErr = something really large
while iterations < 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 > 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 < bestErr then
bestFit := betterModel
bestErr := thisErr
end if
end if
increment iterations
end while
return bestFit
کد نمونه[ویرایش]
در این قطعه علاوه بر پیادهسازی شبه کد، کد یک LinearRegressor
بر پایه کمترین مربعات تعریف شدهاست. همچنین الگوریتم RANSAC
بر روی یک مسئله رگرسیون دوبعدی اعمال میشود و نتایج به تصویر کشیده شدهاند:
from copy import copy
import numpy as np
from numpy.random import default_rng
rng = 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 :]))
< self.t
)
inlier_ids = ids[self.n :][np.flatnonzero(thresholded).flatten()]
if inlier_ids.size > 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 < 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) ** 2
def 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.params
if __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()
متد های مرتبط[ویرایش]
- MLESAC (برآورد درست نمایی بیشینه، به انگلیسی: Maximum Likelihood Estimate Sample Consensus): میزان درست نمایی اینکه داده از مدلی که به نمونهها برازش شده است تولید شده است، را بیشینه میکند؛ مثل یک مدل مخلوطی از دادههای درونی و بیرونی.
- MAPSAC (اجماع نمونه بیشینه احتمال پسین، به انگلیسی: Maximum A Posterior Sample Consensus): متد قبلی را گسترش میدهد و یک توزیع پیشین از پارامتر ها را در فرایند میگنجاند تا برازش شود و احتمال پسین را بیشینه میکند.
- KALMANSAC: استنباط علیت وضعیت یک سامانه پویا
- نمونهسازی مجدد (آمار)
- Hop-Diffusion Monte Carlo در هر مرحله از RANSAC، از نمونه گیری تصادفی که شامل پرش های سراسری و انتشار محلی است، برای برآورد هندسه فراقطبی میان تصاویر با اشتراک پایه ای زیاد استفاده میکند.[۳]
منابع[ویرایش]
- ↑ Data Fitting and Uncertainty, T. Strutz, Springer Vieweg (2nd edition, 2016)
- ↑ Cantzler, H. "Random sample consensus (ransac)." Institute for Perception, Action and Behaviour, Division of Informatics, University of Edinburgh (1981). http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.3035&rep=rep1&type=pdf
- ↑ Brahmachari, Aveek S.; Sarkar, Sudeep (March 2013). "Hop-Diffusion Monte Carlo for Epipolar Geometry Estimation between Very Wide-Baseline Images". IEEE Transactions on Pattern Analysis and Machine Intelligence. 35 (3): 755–762. doi:10.1109/TPAMI.2012.227. PMID 26353140. S2CID 2524656.