اجماع نمونه تصادفی

اجماع نمونه تصادفی (به انگلیسی: Random sample consensus) یک روش تکرار شونده (iterative method) است برای تخمین پارامترهای یک مدل ریاضی روی یک مجموعه داده که شامل داده‌های پرت است، به طوری که داده‌های پرت تأثیری روی تخمینی که زده می‌شود نداشته باشند. با این تعریف، از این روش می‌توان به عنوان یک روش برای تشخیص داده پرت نیز یاد کرد. RANSAC در حقیقت یک الگوریتم غیرقطعی است، بدین معنا که تنها به یک احتمال مشخصی جواب مطلوب می‌دهد که این احتمال با افزایش تعداد دفعات اجرای الگوریتم بیشتر می‌شود. این الگوریتم در ابتدا توسط Fischler و Bolles در اس‌آرآی اینترنشنال در سال ۱۹۸۱ منتشر شد. آنها از RANSAC برای حل مسئله تعیین موقعیت (به انگلیسی: Location Determination Problem) استفاده کردند. در این مسئله هدف تعیین نقاطی در فضا است که نگاشت آنها روی یک تصویر بر روی مجموعه مشخصی از نقاط می‌افتد.

RANSAC از نمونه‌گیری تصادفی فرعی استفاده می‌کند. یکی از فرض‌های پایه‌ای الگوریتم این است که داده‌ها شامل داده درونی و داده‌های پرت هستند. منظور از داده‌های درونی، داده‌هایی هستند که توزیع آن‌ها قابل بیان توسط مجموعه‌ای از پارامترهای یک مدل است و البته می‌توانند شامل مقداری نویز باشند. داده‌های پرت هم داده‌هایی هستند که با مدل مدنظر سازگار نیستند. منشأ داده‌های پرت می‌تواند مقادیر خیلی زیاد نویز، یا اندازه‌گیری‌های خطادار (هنگام جمع‌آوری داده) یا فرض اشتباه در مورد داده‌ها باشد. RANSAC همچنین این فرض را دارد که با داشتن مجموعه‌ای (معمولا کوچک) از داده‌های درونی، فرایندی وجود دارد که با استفاده از آن می‌تواند پارامترهای مدلی که به صورت بهینه توزیع داده‌ها را بیان می‌کند و با داده‌ها سازگار است، برآورد کرد.

مثال

یک مثال ساده، برازش یک خط در دو بعد به یک مجموعه از مشاهدات است. با فرض اینکه این مجموعه هم شامل داده‌های درونی است، یعنی داده‌هایی که به‌طور تقریبی می‌توانند به یک خط برازش شوند، و هم داده‌های پرت، داده‌هایی که به این خط نمی‌توانند برازش شوند، استفاده از روش کمترین مربعات معمولی باعث می‌شود خطی بدست آید که به خوبی به این مجموعه داده برازش نشود. چرا که سعی شده‌است که این خط به همه نقاط برازش شود، که شامل داده‌های پرت نیز هستند. RANSAC اما سعی می‌کند داده‌های پرت را جزو داده‌های مورد استفاده هنگام برازش در نظر نگیرد و مدلی خطیای بیابد که هنگام برازش شدن تنها از داده‌های درونی استفاده می‌کند. این کار با برازش کردن مدل خطی به چندین زیرمجموعه از داده‌ها که تصادفی انتخاب شده‌اند و انتخاب مدلی که بهترین برازش را به زیرمجموعه ای از داده‌ها داشته‌است، انجام می‌شود. از آنجا که داده‌های درونی نسبت به مخلوطی تصادفی از داده‌های درونی و داده‌های پرت، بیشتر به صورت خطی به هم مرتبط هستند، زیرمجموعه تصادفی ای که به صورت کامل از داده‌های درونی تشکیل شده باشد، بهترین برازش مدل خطی را حاصل می‌شود. در عمل، هیچ تضمینی وجود ندارد که زیرمجموعه‌ای انتخاب شود که تنها شامل داده‌های درونی باشد و احتمال موفقیت الگوریتم به نسبت داده‌های درونی به کل داده‌ها و انتخاب پارامترهای الگوریتم بستگی دارد.

• 
  مجموعه داده‌ای که شامل تعداد زیادی داده‌پرت است و باید خطی به به این مجموعه داده برازش شود
• 
  خط برازش شده با استفاده از الگوریتم RANSAC؛ داده‌های پرت تاثیری روی نتیجه ندارند

بررسی اجمالی

الگوریتم RANSAC یک الگوریتم یادگیری برای تخمین پارامترهای یک مدل با نمونه‌گیری تصادفی از داده‌های مشاهده شده‌است. RANSAC با یک روش رای‌گیری، سعی می‌کند تا برازش بهینه را بر روی مجموعه داده‌ای که هم شامل داده‌های درونی و هم داده‌های پرت است، بیابد. هر یک از نمونه‌های موجود در مجموعه داده برای رای‌گیری برای یک یا چند مدل استفاده می‌شوند. پیاده‌سازی این رای‌گیری بر ۲ فرض استوار است: اینکه داده‌های پرت زیاد نیستند تا همواره تأثیر منفی روی رای‌گیری بگذارند و اینکه داده‌های درونی به قدری کافی هستند که بتوان مدل خوبی یافت تا توزیع داده‌های درونی را به خوبی بیان کند یا به به عبارتی دیگر، داده‌های از دست رفته زیاد نیستند. الگوریتم RANSAC شامل دو مرحله است که مکرراً اجرا می‌شوند:

1. در مرحله اول، یک زیرمجموعه نمونه به صورت تصادفی از مجموعه داده ورودی انتخاب می‌شود. یک مدل برازش شده و پارامترهای آن با استفاده از اعضای این زیرمجموعه به دست می‌آیند. اندازه زیرمجموعه به کوچک‌ترین مقداری است که برای تعیین پارامترهای مدل کافی باشد.
2. در مرحله دوم، الگوریتم بررسی می‌کند که کدام اعضای کل مجموعه داده با مدل به دست آمده از بخش قبل سازگار هستند. یک عضو از مجموعه داده به عنوان داده پرت شناخته می‌شود اگر میزان ناسازگاری آن با مدل از یک حد مشخص بیشتر باشد. در واقع این حد بیانگر بیشترین میزان انحراف قابل انتساب به تأثیرات نویز است.

مجموعه داده‌های درونی بدست آمده برای مدل برازش شونده مجموعه اجماع نام می‌گیرد. الگوریتم RANSAC این دو مرحله را آنقدر تکرار می‌کند تا مجموعه اجماع به دست آمده اندازه مطلوب را داشته باشد.

ورودی الگوریتم شامل یک مجموعه داده، روشی برای برازش کردن یک مدل به مشاهدات و تعدادی پارامترهای اطمینان است. روند الگوریتم به صورت دقیق تر در زیر آورده شده‌است:

1. انتخاب یک زیرمجموعه تصادفی از داده‌های اصلی. این زیرمجموعه داده‌های درونی فرضی نام دارد.
2. یک مدل به مجموعهٔ داده‌های درونی فرضی برازش می‌شود.
3. سپس کل داده‌های مجموعه داده بر روی مدل برازش شده تست می‌شوند. نمونه‌هایی که با توجه به یک تابع هزینه با مدل سازگار هستند، در مجموعه اجماع قرار می‌گیرند.
4. مدل بدست آمده خوب تلقی می‌شود اگر تعداد نمونه‌هایی که در مجموعه اجماع قرار می‌گیرند کافی باشد.
5. سپس، مدل می‌تواند با برآورد دوباره پارامترها، اما این بار روی مجموعه اجماع، بهتر شود.

این روند تعداد مشخصی بار اجرا می‌شود و هر بار یا مدل به دلیل سازگاری با تعداد کمی از اعضای مجموعه داده رد می‌شود، یا یک مدل بهبود یافته بهمراه مجموعه اجماع متناظر با آن بدست می‌آید. در حالت دوم، مدل را به عنوان مدل بهینه تا اینجای کار در نظر می‌گیریم اگر اندازه مجموعه اجماع آن از اندازه مجموعه اجماع متناظر مدل بهینه قبلی بزرگتر باشد.

الگوریتم

شبه کد الگوریتم 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()

نتایج حاصل از اجرای RANSAC که در کد پایتون پیاده‌سازی شده‌است. خط نارنجی بیانگر پارامترهای کمترین مربعات است که به صورت موفقیت‌آمیز توانسته‌است از نقاط پرت چشم‌پوشی کند.

متد های مرتبط

• MLESAC (برآورد درست نمایی بیشینه، به انگلیسی: Maximum Likelihood Estimate Sample Consensus): میزان درست نمایی اینکه داده از مدلی که به نمونه‌ها برازش شده است تولید شده است، را بیشینه می‌کند؛ مثل یک مدل مخلوطی از داده‌های درونی و بیرونی.
• MAPSAC (اجماع نمونه بیشینه احتمال پسین، به انگلیسی: Maximum A Posterior Sample Consensus): متد قبلی را گسترش می‌دهد و یک توزیع پیشین از پارامتر ها را در فرایند می‌گنجاند تا برازش شود و احتمال پسین را بیشینه می‌کند.
• KALMANSAC: استنباط علیت وضعیت یک سامانه پویا
• نمونه‌سازی مجدد (آمار)
• Hop-Diffusion Monte Carlo در هر مرحله از RANSAC، از نمونه گیری تصادفی که شامل پرش های سراسری و انتشار محلی است، برای برآورد هندسه فراقطبی میان تصاویر با اشتراک پایه ای زیاد استفاده می‌کند.