챠트 패턴 매칭을 위한 DTW

주가는 관성의 원리에 따라 추세를 지속하려는 속성이 있으며 파동과 사이클을 반복하려는 속성이 있다. 주가의 추세를 담고 있는 챠트는 그런 면에서 의미가 있다. 차트의 대표적인 유형으로는 상승 추세와 하강 그리고 횡보 추세 등 다양하게 존재한다. 이러한 점은 로봇 트레이딩에서 중요한 정보로 사용된다. 로봇 트레이딩에서 기계적으로 챠트 유형이나 패턴을 분석하고자 할 때 DTW(Dynamic Time Warping)이라는 알고리즘을 사용하기도 한다.  DTW 소개 자료를 찾다 유용한 자료를 찾아 내용을 정리해본다.(아래 참고자료에서 내용 발췌함을 표기함)

기본 DTW 알고리즘

DTW는 패턴간 유사도를 검색하기 위한 알고리즘이다. 찾고자 하는 패턴을 주어지면 DTW 알고리즘으로 가장 유사하게 생긴 주가 챠트를 찾을 수 있는 것이다.

dtw_intro

조금 수학적인 용어를 사용한다면 비교하고자 하는 패턴을 X, Y라고 하면 X := (x_1 , x_2, ..., x_N) 이고 Y := (y_1 , y_2 , ..., y_M)으로 표기 가능하다. 여기서 중요한 점은 X의 개수와 Y의 개수가 다를 수 있다는 점이다. X의 개수와 Y의 개수가 다르다면 패턴 매칭에 있어 고려해야할 사항이 많을 것이다.

DTW는 패턴 매칭에 있어 아래와 같은 조건을 만족해야 한다.

  • 끝점 제약의 조건(Boundary condition): 입력 패턴(X)과 참조 패턴(Y)의 시작점과 끝을 일치시킨 상태에서 패턴 비교
  • 단조 증가 제약 조건(Monotonicity condition): 최적 경로는 항상 단조로 증가해야 한다
  • 단계 증가 조건(Step size condition): 입력 패턴과 참조 패턴 비교 시 격자상의 한 노드에서 다른 노드에 도달하기 위해 필요한 단계 사이즈에 제한을 둠. 가령 스텝 사이즈가 1일 경우 (1, 1)과 비교를 하였다면 다음 격자는(1, 2) 또는 (2, 1), (2, 2) 등의 비교가 가능해짐

각 X와 Y 격자별 각각에 대하여 거리값(difference)를 구하면 가령 아래와 같은 매트릭스(matrix) 형태가 나올 것이다. (검은 색이 가깝고, 밝은 색이 거리값이 큼)

dtw_cost

DTW로 X, Y 패턴의 거리는 결국 거리값 매트릭스에서 가장 최저(최선)의 솔루션(경로)을 찾는 것이다. (아래 그림 참조)

dtw_find_path

다만 위와 같은 비용 매트릭스(cost matrix) 를 모든 영역에 대하여 산출하면 많은 연산을 해야 되기에 (1, 1)에서부터 누적 비용 매트릭스 (accumulated cost matrix)를 계산한다.  이로써 전체 비용 매트릭스가 아닌 누적해가며 최소가 되는 매트릭스 일부를 구하게 된다. 누적 비용 매트릭스를 수식화하면 아래 공식과 같다. c(x_n , y_m)x_n y_m간의 거리 비용을 의미한다.

D(n, m) = min {D(n-1, m-1), D(n-1, m), D(n, m-1)}+c(c_n , y_m)

누적 비용 매트릭스가 계산하고 나면 이제 x_n, y_m 부터 역으로 최저 패스를 찾아가는 방법으로 X, Y 패턴간 최소 거리를 찾는다.

찾고자 하는 패턴을 Y라고 하면, 종목별 각각의 챠트데이터를 가져와 DTW를 적용하고 나면 가장 가까운 X 패턴을 찾을 수 있을 것이다. 그러면 찾고자 하는 패턴(예로 상승패턴)에 가장 가까운 챠트에 대한 종목을 알 수 있게 된다.

DTW 확장 알고리즘

기본 DTW을 확장한 여러 알고리즘이 있다.

  • 단계 증가를 변경: 기존 DTW의 단계 증가는 0 또는 1인데 이를 2~3으로 증가시켜 변경하는 식으로 응용
  • 가중치 적용: 경로에 있어 가중치를 부여함. 가령 비용 매트릭스에서 x축, y축 보다는 대각선 방향 가중치를 높일 수 있음
  • 전역 경로 제약: 경로 생성에 있어 영역을 제한하는 방식(아래 그림)

dtw_global

  • 멀티스케일(Multiscale) DTW: 매칭시 큰 영역에서 작은 영역으로 하향(Top-down) 방식으로 경로를 찾아가는 방식
  • 부분 매칭 (subsequence) DTW: X, Y 전체가 아닌 X와 Y 일부만 매칭하는 방식

참조

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중