RANSAC (RANdom SAmple Consensus)

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

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