外れ値を含む回帰問題などに使用するアルゴリズム

通常の最小二乗法だと結果が外れ値に引っ張られてしまう

アルゴリズム

1. データから一部をランダムにサンプル抽出する

2. サンプルに対してモデルをフィットさせ、パラメーターを推定

3. 手順1で抽出されなかったデータ１つ１つに対して、モデルの当てはまりを確認

4. データ１つ１つに対してモデルの誤差が事前に設定した水準以内であれば、「このデータは外れ値ではない」と判断し、手順2の教師データに追加する

5. 手順4をサンプル以外の全データに行った結果、教師データの要素数が閾値を超えていれば、手順4のデータ追加後の教師データ全体に対してモデルをフィットさせ、当てはまりを確認

6. 手順1～手順5を規定の回数だけ繰り返し、手順5の当てはまりが最良のパラメーターを最終結果とする

プログラム

LidarVector<std::pair<int,LineSegment>> ransacs(const LidarVector<stm32_library::Vector2>& data)
    {
        using namespace stm32_library;
        LidarVector<LineSegment> ransac_lines;
        {
            LidarVector<Vector2> remaining_data = data;
            while(1){
                if(remaining_data.size() < LOOP_STOP_REMAINING_POINT_N){
                    break;
                }
                auto [line,unused_data] = ransac(remaining_data);
                if(!line){
                    break;
                }
                ransac_lines.push_back(line.value());
                remaining_data = unused_data;
            }
        }

        LidarVector<std::pair<int,LineSegment>> ret_lines;
        {
            for(int i = 0; i < ransac_lines.size(); i++){
                int count = 0;
                for(int j = 0; j < data.size(); j++){
                    if(ransac_lines[i].distance(data[j]) < NEAR_POINT_THRESHOLD){
                        count++;
                    }
                }
                if((count / ransac_lines[i].length()) > LINE_JUDGE_POINT_DENSITY){
                    ret_lines.push_back(std::make_pair(count,ransac_lines[i]));
                }
            }
        }

        return ret_lines;
    }

CHatGPTがはいたやつ

#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <Eigen/Dense>

using Point = Eigen::Vector2d;

// 点群から線を推定する関数
std::pair<Point, Point> fitLineRANSAC(const std::vector<Point>& points, double threshold, int max_iterations)
{
    // ランダム数生成器の初期化
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> distribution(0, points.size() - 1);

    std::pair<Point, Point> best_line;
    int best_inliers = 0;

    // RANSACアルゴリズムの繰り返し
    for (int i = 0; i < max_iterations; i++)
    {
        // ランダムに2点を選択して線を生成
        int idx1 = distribution(gen);
        int idx2 = distribution(gen);
        Point p1 = points[idx1];
        Point p2 = points[idx2];
        Point dir = (p2 - p1).normalized();
        Point normal(-dir.y(), dir.x());
        Point line_center = (p1 + p2) / 2.0;
        std::pair<Point, Point> line(line_center + normal, line_center - normal);

        // 線に対する誤差がthreshold以下の点をinliersに追加
        int inliers = 0;
        for (const auto& point : points)
        {
            double dist = (point - line.first).cross(line.second - line.first) / (line.second - line.first).norm();
            if (std::abs(dist) < threshold)
                inliers++;
        }

        // 最もinliersが多い線を更新
        if (inliers > best_inliers)
        {
            best_inliers = inliers;
            best_line = line;
        }
    }

    return best_line;
}

int main()
{
    // 例: 点群を作成
    std::vector<Point> points;
    points.push_back(Point(0, 0));
    points.push_back(Point(1, 1));
    points.push_back(Point(2, 2));
    points.push_back(Point(3, 3));
    points.push_back(Point(4, 4));
    points.push_back(Point(5, 5));
    points.push_back(Point(6, 6));
    points.push_back(Point(7, 7));
    points.push_back(Point(8, 8));
    points.push_back(Point(9, 9));

    // RANSACアルゴリズムによる線の推定
    double threshold = 0.1;
    int max_iterations = 100;
    auto line = fitLineRANSAC(points, threshold, max_iterations);

    // 結果を出力
    std::cout << "Line parameters: " << std::endl;
    std::cout << "Point 1: " << line.first.transpose() << std::endl;
    std::cout << "Point 2: " << line.second.transpose() << std::endl;

    return 0;