본문 바로가기

Enginius/Machine Learning

Interpolation

출처: http://blog.jidolstar.com/59
 관측 또는 실험에서 얻은 데이타는 몇개의 (x,y)값으로 되어있을 것이다. 이 데이타를 이용하여 원하는 결과를 도출하기 위해 자주 사용되는 것 중에 하나가 보간법(補間法, Interpolation)이다.  이 보간법이라는 것은 주어진 데이타를 가지고 어떤 다항식과 같은 형태로 표준화 시키는 작업 중에 하나로 관측이나 실험을 통해서 얻어지지 않은 점을 추정할 때 유용하게 사용된다. 보간법은 반드시 원본데이타를 포함하기 때문에  내삽법(內揷法)이라고 한다.(참고: 외삽법)

보간법에는 상당히 많은 종류가 있다. 너무 많기 때문에 여기에서 다 설명하지 않고 간단하게 보간법에 대해 이해할 수 있도록 하고자 한다. 보간법을 이용해 실제적으로 계산하는 방법에 대해서는 여기서 다루지 않겠다.

이 자료는 wikipedia.org에 올라온 자료를 참고하여 쓴 글이다. 상업적 용도로 쓰여질 수 없다는 점을 미리 언급한다. 

작성자 : 지돌스타(http://blog.jidolstar.com/59 ), 천문노트(http://astronote.org/

정의


순차적이고 분리된  xk  에 대응하는 yk값 이 있을때 함수 f가 다음과 같이 정의된다.

사용자 삽입 이미지

xk  ,y)값을 데이타 점(data point)라 하고 f를 이 데이타 점을 이으는 보간함수(interpolant)라고 부른다.
y가 함수 f에 의해 주어질 때  y를 fk.로 쓰여지기도 한다.


예제

사용자 삽입 이미지

왼쪽 테이블에서 주어진 각 점을 plot한 모습이다.


예를 들어 알려지지 않은 함수 f의 값이 아래의 테이블 값처럼 주어졌다고 가정하자.
xf(x)
0 0
1 0 . 8415
2 0 . 9093
3 0 . 1411
4 −0 . 7568
5 −0 . 9589
6 −0 . 2794

x=2.5일때 값은 무엇일까? 
보간법은 이런 문제를 풀 수 있는 실마리가 된다.

보간법은 그 종류가 다앙하다. 아래는 몇가지 보간법의 간단한 예제만 소개한다. 보간법을 선택할 때는 원하는 결과의 정확성, 비용등을 잘 생각할 필요가 있다. 이 문제는 실험자 당사자가 해결해야 할 문제이다.

선형보간법(linear Interpolation)

사용자 삽입 이미지

선형보간법을 이용하여 연결한 모습이다.

참고글 : http://en.wikipedia.org/wiki/Linear_interpolation

선형보간법은 보간법중 가장 간단한 방법중에 하나이다. 
단순히 알려진 데이타 점들을 오른쪽 그래프와 같이 선형으로 이어주기만 하면 된다. 이를 근거로 위에 언급한  f(2.5)의 값을 결정해보도록 하자. 알려진값 2와 3에 대하여 f(2)=0.9093, f(3)=0.1411 이므로 f(2.5)는 0.5252가 된다.

일반적으로 선형보간법은 두 데이타 점들인  (xa,ya) 와 (xb,yb)가 주어졌을때 그 사이의 (x,y)점에 대한 보간함수는 다음과 같이 주어진다.

사용자 삽입 이미지




선형보간법은 쉽고 빠르다. 하지만 그리 정확한 방법은 아니다. 게다가 각 데이타 점부분(xk)에서 미분이 가능하지 않다. 

다항식 보간법(Polynomial interpolation)

참고글 : http://en.wikipedia.org/wiki/Polynomial_interpolation

사용자 삽입 이미지

다항식 보간법을 적용하여 데이타를 plot함


다항식 보간법은 선형보간법을 일반화 시킨 것과 같다. 선형보간법은 1차 다항식인 반면 다항식 보간법은 2차 이상의 다항식을 가진다.  

선형 보간법에서 언급한 예제를 생각해보자. 7개의 점을 전부 통과하는 다항식은 아래와 같은 6차 다항식이어야 한다. 

f(x) = − 0.0001521x6 − 0.003130x5 + 0.07321x4 − 0.3577x3 + 0.2255x2 + 0.9038x. 

x=2.5를 대입하면 f(2.5)=0.5965 이다. 

일반적으로 n개의 데이타가 있는 경우 다항식의 차수는 n-1차가 된다. 왜냐하면 이 n개의 데이타를 전부 통과해야 하는 곡선을 선택해야하기 때문이다. 다항식 보간법은 선형보간법과 달리 데이타 점에서 미분이 가능하다. 

하지만 다항식 보간법은 몇가지 단점이 있다. 데이타 점이 많을 수록 다항식의 차수가 높아지므로 계산 복잡성(computational complexity)이 커진다. 게다가 Runge 현상(Runge's phenomenon)이 일어난다. 이 현상은 데이타 점(보간점)에 따라서 다항식 자체가 많이 바뀌므로 제대로된 보간을 기대하기 어렵다. 이러한 단점때문에 아래에서 설명한 스플라인 보간법(spline interpolation)을 이용한다.

스플라인 보간법(Spline Interpolation)

참고글 : http://en.wikipedia.org/wiki/Spline_interpolation

사용자 삽입 이미지

스플라인 보간법에 의해 데이타를 Plot한 결과



선형 보간법이 [xk,xk+1] 구간에서 선형함수를 사용했다는 것을 위에서 설명했다. 스플라인 보간법은 각 구간에서 낮은 차원(low-degree)의 다항식을 사용한다. 이 다항식은 전후구간의 다항식들과 자연스럽게 연결될 수 있는 것으로 선택한다. 이렇게 각 구간마다 선택된 함수들을 스플라인(spline)이라고 한다. 

각 구간에서 스플라인 함수를 선택할때 각 점에서 전후 스플라인 함수가 미분이 가능해야 하고 곡률도 같아야 한다. 이렇게 해서 각 구간별 정해진 다항식은 다음과 같다.
사용자 삽입 이미지

이 경우에 f(2.5)=0.597262 가 된다.

다항식 보간법와 같이 스플라인 보간법이 선형보간법보다 작은 오차를 낸다. 그리고 보간식도 자연스럽게 연결된다. 그러나 다항식 보간법보다 계산하기 훨씬 간단하다. 앞에서 언급한 Runge현상이 다항식 보간법에 비해 크게 개선이 되긴 했지만 스플라인 보간법만 가지고는 아직 충분하지는 않다. Runge현상을 줄이기 위해 y값이 급격하게 변하는 구간에서 보간점(데이타 점)을 잘 선택하는 것이 중요하다. 스플라인 보간법의 또 한가지 단점은 각 구간별로 곡선식을 가지므로 하나의 함수식으로 표현이 불가능하다. 

참고사항

  1. 보간법은 Curve Fitting(곡선적합)법의 하나이다. 즉, 데이타를 표현하는 함수를 유추해내기 위한 방법인데 곡선적합법은 보간법과 최소면적법(least squares method)등이 있다.
    적절한 함수를 도출해내기 위해서 스플라인보간법을 이용하여 fitting한 후, 이 데이터를 입력데이터로 사용하여 새로운 curve를 생성후 최소면적법을 이용하여 한개의 곡선식을 얻는 방법도 있다.
    사이트 : http://www.mathpad.com/kr/public/htmls/main/left/fit/CurveFitInfo.html
  2. 보간법을 내삽법이라고 했다. 내삽법이라는 것은 이미 설명했듯이 실험데이터를 포함하는 함수를 구하는 것을 뜻한다. 또, 내삽법 외에 외삽법(外揷法, extrapolation)이라는 것이 있는데, 외삽법은 실험데이타를 포함하지 않지만 그 데이타를 적절해 표현할 만한 근사함수를 구하는데 목적이 있다. 

참고사이트

http://en.wikipedia.org/wiki/Interpolation 

'Enginius > Machine Learning' 카테고리의 다른 글

Papers studied in Pattern Recognition Class  (0) 2011.12.06
MCMC  (0) 2011.11.15
Gmail Priority Inbox 알고리즘에서 배우는 실전 기계학습  (0) 2011.11.01
Least Squres  (2) 2011.10.26
퍼셉트론 패턴인식 데모  (0) 2011.10.25