RANSAC

RANdom SAmple Consensus, 랜덤으로 샘플 데이터를 뽑아 모델을 예측하는 알고리즘이다. 노이즈가 큰 상황에서도 이상적인 모델을 추출할 수 있어서 사용한다.

알고리즘

1. Hypothesis - 가설
   전체 데이터에서 N개의 샘플을 랜덤으로 선택하여 모델을 예측한다.
2. Verification - 검증
   전체 데이터셋에서 예측한 모델과 일치하는 데이터의 수를 센다.

1~2과정을 N회 반복하여 검증 단계에서 가장 많은 데이터와 일치하는 모델을 최종 선택하는 알고리즘이다.

inlier, outlier

모델과 일치하는 데이터인지 판단하는 기준으로 임계치가 있다. 모델과 관측 데이터의 값이 100% 일치하는 기대하기는 어렵기 때문이다. 즉, 모델과 임계치 이하의 차이를 보이면 모델의 경향성을 따른다고 보고 inlier로 판단하는 것이다. 그 임계치를 넘어가는 차이가 있다면 outlier이다. 당연히 이 임계치를 어떻게 설정하는지에 따라 정확도는 크게 영향을 받는데, 일반적으로 inlier들의 분산(s)을 구해 2s~3s 정도로 설정한다.

반복하는 횟수(N)는 목표 정확도(P)를 통해 구하게 되는데,

P = 1 - (1 - a**m)**N

여기서 a는 inlier의 비율, m은 가설 과정에서 추출하는 데이터의 수이다.
일반적으로 99% 이상으로 설정한다.

특징

• Non-determistic: 가설 단계에서 값을 랜덤으로 추출하기 때문에, 항상 같은 결과를 보장하지 않는다.
• 마찬가지로 값을 랜덤 추출하므로 노이즈에 강하다. 그러나, 노이즈가 어떤 모델을 이루고 있는 경우에는 해당 모델이 추출될 수 있다.
• 임계값 이하의 차이의 경우 그 값을 반영하지 않기 때문에 밀집되어 있는 데이터에 약하다.