RANSAC (RANdom SAmple Consensus)

Table of Contents

1 RANSAC

RANSAC(RANdom SAmple Consensus,随机抽样一致性算法)是一种迭代方法, 常用来排除异常数据点(outliers)对模型的影响。 它于1981年由Fischler和Bolles最先提出。

1.1 RANSAC效果演示

1 (摘自Robust linear model estimation using RANSAC)演示了使用和不使用RANSAC的区别,显然RANSAC(蓝线)没有受到异常点(黄色点)的影响,其结果更加稳定。

ransac_example.png

Figure 1: RANSAC Example

2 RANSAC算法

RANSAC算法描述:
1、从原始数据集中随机抽取一小部分(称为采样集),假设这部分数据都是正常的,用这部分数据训练模型。采样集的大小是能训练模型的最小样本数(这是个超参数,需要人为设置)。
2、用其他剩余样本测试上一步得到的模型。如果某个样本的损失小于某个阈值(这也是个超参数,需要人为设置),则认为它是和抽样出的样本是一致的,把它加入“一致集(Consensus Set)”中;若某个样本的损失大于阈值,则认为它是异常样本。
3、如果一致集的样本有足够多的样本,则认为该模型很好,拟合了大部分正常样本,如果一致集的样本较少,则丢弃这个模型。
4、然后,用一致集和采样集中的样本重新训练模型(如使用普通的最小二乘法),计算损失,如果整体损失比上次迭代小,则更新最佳拟合模型。
5、重复步骤1~4,直到一致集样本足够多或者达到最大的迭代次数,返回最佳拟合模型。

RANSAC算法的伪代码(摘自其 Wikipedia):

Given:
    data – a set of observed data points
    model – a model that can be fitted to data points
    n – minimum number of data points required to fit the model
    k – maximum number of iterations allowed in the algorithm
    t – threshold value to determine when a data point fits a 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 nul if no good model is found)

iterations = 0
bestfit = nul
besterr = something really large
while iterations < k {
    maybeinliers = n randomly selected values from data
    maybemodel = model parameters fitted to maybeinliers
    alsoinliers = empty set
    for every point in data not in maybeinliers {
        if point fits maybemodel with an error smaller than t
             add point to alsoinliers
    }
    if the number of elements in alsoinliers is > d {
        % 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 model fits these points
        if thiserr < besterr {
            bestfit = bettermodel
            besterr = thiserr
        }
    }
    increment iterations
}
return bestfit

2.1 RANSAC优缺点

RANSAC优点:它可排除异常点影响,使模型更加稳定。

RANSAC缺点:
1、有多个超参数需要根据具体问题来人为设置。
2、无时间上界,即不会自然收敛,只能靠最大迭代次数来限制。


Author: cig01

Created: <2015-12-06 Sun 00:00>

Last updated: <2017-12-16 Sat 19:07>

Creator: Emacs 25.3.1 (Org mode 9.1.4)