深入理解RANSAC算法：应对异常值的高效方法

深入理解RANSAC算法：应对异常值的高效方法

引用

CSDN

1.

https://m.blog.csdn.net/qq_22841387/article/details/143029154

在机器学习和数据拟合中，异常值的存在是一个常见的挑战。传统的最小二乘法容易受到异常值的影响，导致拟合结果偏差很大。为了解决这个问题，RANSAC（随机抽样一致性）算法应运而生。本文将详细介绍RANSAC算法的基本原理、实现步骤及其参数选择方法。

异常值对数据拟合的影响

在机器学习和数据拟合中，一个常见的问题就是异常值（outliers）的存在。异常值是那些远离大多数数据点的点。如果我们尝试使用传统的最小二乘法（如线性回归）直接对数据进行拟合，异常值会对模型产生极大的干扰，导致拟合结果偏差很大。

举个简单例子：

假设我们试图拟合一条直线，而我们的数据集中有一些异常值。如果我们选择了一个异常值作为基础来计算拟合直线，那么这条直线很可能只会通过异常点及其附近的几个点，而无法很好地通过数据集中大多数的其他点。因此，基于这个异常值拟合出来的直线不会得到大部分点的支持。

直觉告诉我们：如果我们选择了异常点来计算模型，那么结果模型的支持点（内点）数量会非常少。这个思路也就是 RANSAC 的基本出发点——为了避免异常点对拟合模型的影响，我们通过一种随机采样的方式，去尝试找到能够得到大部分数据点支持的模型。

RANSAC 详细实现步骤

下面，我们就按照这个思路，一步步拆解 RANSAC 的实现过程：

1. 随机选择种子点：

• 假设我们的数据是二维的，需要拟合一条直线。
• RANSAC 的第一个步骤就是从数据集中随机选择两个点，这两个点称为“种子点”。
  为什么是两个点？
  在二维平面中，确定一条直线只需要两个点。同样，如果是在三维中拟合平面，则需要选择三个点。
  直觉分析：如果选到的种子点是异常值，比如数据中的极端值，那么我们用这两个异常点拟合出来的直线，肯定不会得到大多数数据点的支持，内点数量会很少。
  

2. 基于种子点计算模型：

• 接下来，我们使用这两个种子点来计算模型的参数。具体来说，在二维情况下，我们可以根据这两个点的坐标计算出直线的方程。
• 比如，如果两个点的坐标是( x 1 , y 1 ) (x_1, y_1)(x1 ,y1 )和( x 2 , y 2 ) (x_2, y_2)(x2 ,y2 )，那么我们可以用直线方程y = m x + b y = mx + by=mx+b进行计算，其中m mm是斜率，b bb是截距。

3. 计算内点：

• 现在我们有了一个模型（直线方程），下一步是计算有多少数据点符合这个模型。我们通过计算每个点到直线的距离，判断这些点是否在允许的误差范围内（这个范围被称为阈值）。
• 如果某个点到直线的距离小于设定的阈值，那么我们称这个点为“内点”。否则，它就被视为异常点。
  
  重要概念：阈值
  阈值定义了一个点被认为是“内点”的条件。这个阈值的大小直接影响内点的数量。设置太大，可能包括很多离直线较远的点；设置太小，可能排除一些本应算作内点的数据。

4. 迭代多次选择种子点：

• RANSAC 的核心在于其迭代过程。算法不会只随机选择一组种子点，而是会重复这个过程多次。假设我们设定迭代次数 (k)，RANSAC 会重复以下步骤：
  1. 随机选择一组种子点；
  2. 根据种子点计算模型；
  3. 评估内点数量；
  4. 如果当前的内点数量大于之前记录的内点数量，就更新最优模型。
     直觉：通过这种不断随机选择种子点的方式，RANSAC 能够避免由于一次选到异常值而导致的错误拟合。随着迭代次数的增加，模型最终会趋于稳定，找到那些能得到最多数据点支持的模型。

5. 保留内点最多的模型并重新计算：

• 在迭代完成后，RANSAC 会保留内点最多的模型。但这还不是最后一步。
  为什么要重新计算？
  最初的模型是基于随机选择的种子点拟合的，可能并不是最精确的。所以，RANSAC 会使用所有符合模型的“内点”来重新计算一次模型参数。这样做可以确保最终的模型是基于大量支持点的，而不是基于最初的随机选择。
  例如：假设我们在某次迭代中找到了 50 个内点，而之前每次只有不到 10 个。我们会使用这 50 个内点，重新拟合一条直线，以确保这条线能更好地代表数据。

小结

RANSAC 通过随机采样、计算模型、筛选内点、迭代选择等步骤，有效避免了异常值对模型的干扰。最终，它选择内点最多的模型，并重新拟合出更准确的模型。

RANSAC 的优点：

• 能够有效应对含有大量噪声和异常值的数据；
• 通过多次迭代，找到最符合大部分数据的模型。

需要注意的问题：

• 迭代次数k kk需要合理设定，次数过少可能导致没找到最优模型，次数过多则增加计算开销；
• 阈值的设定非常关键，它直接影响到内点的判断标准。

迭代次数k kk的选定

在RANSAC算法中，迭代次数k kk是一个非常关键的参数。它决定了算法重复随机采样并拟合模型的次数。选择合适的k kk值能够在确保找到最优模型的同时，减少不必要的计算。接下来我们将详细解释如何根据内点比例、模型的自由度和期望的成功概率来确定合理的k kk值。

背景

假设在一个数据集中，数据点分为两类：

1. 内点（Inliers）：符合我们想拟合的模型的数据点。
2. 外点（Outliers）：不符合模型的异常点或噪声数据。

RANSAC的目标是通过多次随机选择数据点，找到包含最多内点的模型。为了确保一定几率选中全部内点的组合，我们需要确定迭代次数k kk。

公式解释

为了确定k kk的值，我们引入以下参数：

• w ww：数据点中内点的比例。例如，如果80%的数据是内点，那么w = 0.8 w = 0.8w=0.8。
• n nn：拟合模型所需的最小样本数量，等于模型的自由度。例如，在二维平面上拟合一条直线，我们需要至少两个点来唯一确定直线，因此n = 2 n = 2n=2。
• p pp：期望至少一次选中全部内点的概率。通常我们设定p = 0.99 p = 0.99p=0.99，即希望有99%的概率能够选中正确的内点。

RANSAC算法中的每次随机采样有w n w^nwn的概率选择到全部内点。这里的w n w^nwn代表的是所有选中的点都是内点的概率。如果我们希望通过多次采样来提高选中全部内点的概率，我们需要计算迭代次数k kk。

k kk的公式为：
k = log ⁡ ( 1 − p ) log ⁡ ( 1 − w n ) k = \frac{\log(1 - p)}{\log(1 - w^n)}k=log(1−wn)log(1−p)

这个公式的意义在于：我们希望通过k kk次迭代，确保至少有一次成功采样出全部内点的组合。公式中的每个部分解释如下：

• p pp：成功采样到全部内点的概率。例如，如果我们希望有99%的概率能够成功采样出内点，p = 0.99 p = 0.99p=0.99。
• w n w^nwn：每次采样成功选中全部内点的概率。w ww是内点在数据中的比例，n nn是拟合模型所需的点数。因此，w n w^nwn是每次采样选中所有点都是内点的概率。如果w ww较小，即内点的比例较低，那么w n w^nwn也会非常小，意味着我们很难通过一次采样就选中正确的内点。

公式推导过程

1. 首先，假设每次随机选择n nn个点，选择到全部内点的概率为w n w^nwn。
2. 失败的概率是1 − w n 1 - w^n1−wn，即没有选中全部内点的概率。
3. 经过k kk次采样后，仍然没有选中全部内点的概率为( 1 − w n ) k (1 - w^n)^k(1−wn)k。
4. 成功选中全部内点的概率为1 − ( 1 − w n ) k 1 - (1 - w^n)^k1−(1−wn)k，我们希望这个概率1 − ( 1 − w n ) k 1 - (1 - w^n)^k1−(1−wn)k大于p pp，即有p pp的信心我们能成功选中全部内点。
5. 由此，我们可以推导出：
   1 − ( 1 − w n ) k ≥ p 1 - (1 - w^n)^k \geq p1−(1−wn)k≥p
6. 进一步化简得出：
   ( 1 − w n ) k ≤ 1 − p (1 - w^n)^k \leq 1 - p(1−wn)k≤1−p
7. 对两边取对数，得到：
   k ≥ log ⁡ ( 1 − p ) log ⁡ ( 1 − w n ) k \geq \frac{\log(1 - p)}{\log(1 - w^n)}k≥log(1−wn)log(1−p)

最终，我们得到了确定迭代次数k kk的公式。

如何使用公式

• 如果数据中内点的比例w ww较高（例如80%的点都是内点），则每次随机选择内点的概率w n w^nwn较大，所需的迭代次数k kk会较少。
• 如果内点的比例w ww较低，尤其当数据中存在较多的异常值时，k kk会显著增加。这是因为每次随机选择到内点的机会很小，需要更多的迭代来确保成功。
• p pp越接近1，意味着我们希望有越高的成功概率（例如p = 0.99 p = 0.99p=0.99表示99%的成功概率）。这也会导致所需的迭代次数k kk增加。

示例解释

我们可以看到不同情况下k kk的大小：

这个表格展示了不同异常值比例（5%-50%）以及不同样本数（n nn）下所需的迭代次数k kk。

• 样本数n = 2 n = 2n=2：如果我们拟合的是二维直线，且异常值比例为50%，则 ( k = 17 )。这意味着为了确保有99%的把握至少一次选中全部内点，我们需要进行17次采样。
• 样本数n = 5 n = 5n=5：如果拟合的是更复杂的模型（比如三维中的平面或更高维度），且异常值比例为50%，则需要146次迭代。
  可以看到，随着异常值比例的增加或拟合模型的复杂性增加，所需的迭代次数k kk也显著增加。

两个相关问题：

1. 可以扩展到三维吗？
   可以。在三维空间中，RANSAC 也适用。拟合一个平面时，我们只需要随机选择三个点，而不是两个点。用这三个点计算平面的方程，并通过类似的方式评估其他点到平面的距离，判断是否为内点。因此，RANSAC 的思想不仅限于二维场景，实际上可以扩展到任意维度的空间。

2. 阈值会不会影响结果？
   是的，阈值的大小对结果有着直接影响。阈值定义了一个点被认为是内点的标准。如果阈值设置过小，很多点可能被排除在外，即便它们距离模型较近；如果阈值设置过大，可能会错误地将异常值也算作内点。因此，选择合适的阈值需要根据数据的噪声水平以及模型的需求进行调试和调整。