1.
해외 블로거인Systematic Investor의 글을 읽는데 Dynamic Time Warping을 소개하더군요. 참고 논문이라고 해서 연결한 논문이 아래입니다.
그런데 유심히 보니까 저자들이 한국 사람입니다. 그래서 관련한 논문을 다시 검색했습니다. 한국데이터정보과학회가 발행하는 Journal of the Korean Data & Information Science Society 2011년 v.22 no.2에 실린 논문이었습니다. 공동저자인 오경주 연세대 정보산업공학과 교수가 쓴 논문도 많아서 검색을 해보니 대학원을 졸업하고 잠시 현대증권 리서치센터 금융공학팀에서 근무를 하셨더군요.
DTW는 처음 음성인식에서 나온 방법으로 패턴 인식에서 이용되는 방법입니다. 시퀀스를 시간의 길이를 고려하지 않고 인식할 수 있는 방법이고 말 그대로 Time을 Warping하기 때문에 특정한 동작을 느리게 하게 되면 시간을 느리게 변화시키는 방법이라고 합니다. 그림으로 표현하면 아래와 같습니다. 기본적인 설명은 Wikipedia를 보시길 바랍니다.
DTW을 구현한 방법은 다양합니다. 최근 각광을 받고 있는 R과 Python의 경우 무척 많습니다. Dynamic Time Warping for Sequence Comparison은 Python으로 DTW를 찬찬히 설명하고 있습니다. Dynamic Time Warping using rpy and Python은 R과 Pyhon을 이용하고 있습니다. pyML을 보면 Coursera 강의중 Andrew Ng의 기계학습 알고리즘을 구현한 프로젝트입니다. 이중 DTW방법을 포함하고 있습니다. Time Series Analysis and Mining with R나 Python으로 설명한 Time Series Classification and Clustering을 보면 데이타분석을 통해 데이타의 유사성을 밝혀 예측을 할 때 DTW방법이 의미를 가진 듯 합니다.
R이나 Python 이외에 FastDTW나 lbimproved와 같이 Java와 C++로 구현한 라이브러리도 유명합니다. 그런데 C는 별로 없네요. Speech Processing에 포함된 소스를 참고로 올립니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 |
/* Design Document : Comparision of two Speech Signals by DTW algorithm : Step 1 : Generate a text file ( Like signal1.txt, signal2.txt ) of each speech signal by some softare or program. Step 2 : Generate frames (Each frame contain a set of cepstral coefficients) by splitting the voiced region from that text file and save these frames in order in a text file( Like input1.txt, input2.txt ). where each row represent a frame and contains frame's set of coefficients as column elements. Step 3 : Apply this program "dtw.c" only after doing step1 and step2 to find similerities and differences between signal1 and signal2. It take two text files as input ( Like "input1.txt" and "input2.txt" ) and give Optimal Warping Path and Cost as output. */ /* Input format :- input.txt : 9 frames of speech signal and each frame has 12 cepstral coefficient 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 */ // Assumption : All cepstral coefficients are integer type. #include<stdio.h> int distance_measure(int ct[12], int cr[12]) //return Tohkura Distance(A Weighted Cepstral Distance) between the set of cepstral coefficients "ct" and "cr" { int i,w[12] = {1,3,7,13,23,33,45,64,80,96,110,130}; int D = 0 ; for(i=0; i<12; i++) D = w[i]*(ct[i]-cr[i])*(ct[i]-cr[i]) ; return D; } int min( int x, int y, int z ) // return minimum among integer x, y and z { if( ( x <= y ) && ( x <= z ) ) return x; if( ( y <= x ) && ( y <= z ) ) return y; if( ( z <= x ) && ( z <= y ) ) return z; } int main() { int i,k; printf("\n------------------------------------------ input1 -----------------------------\n"); int n; printf("First Input Text File => No. of Rows : "); scanf("%d",&n); int ceps1[n][12]; char filename1[256]; printf("First Input Text File Name : "); scanf("%s",filename1); printf("\n"); FILE *file1; file1 = fopen(filename1,"r"); if(file1==NULL) printf("file not found!"); for(i=0; i<n; i++) { for(k=0; k<12; k++) { fscanf(file1,"%d",&ceps1[i][k]); printf("%d ",ceps1[i][k]); }printf("\n"); } fclose(file1); printf("\n------------------------------------------ input2 -----------------------------\n"); int m; printf("First Input Text File => No. of Rows : "); scanf("%d",&m); int ceps2[m][12]; char filename2[256]; printf("Second Input Text File Name : "); scanf("%s",filename2); printf("\n"); FILE *file2; file2 = fopen(filename2,"r"); if(file2==NULL) printf("file not found!"); for(i=0; i<m; i++) { for(k=0; k<12; k++) { fscanf(file2,"%d",&ceps2[i][k]); printf("%d ",ceps2[i][k]); }printf("\n"); } fclose(file2); printf("\n----------------------------- Local Distance Matrix ---------------------------\n\n"); int local_distance[n][m]; for(i=0; i<n; i++) { for(k=0; k<m; k++) { local_distance[i][k] = distance_measure(ceps1[i],ceps2[k]); printf("%d\t ",local_distance[i][k]); } printf("\n"); } printf("-------------------------------------------------------------------------------\n\n"); printf("----------------------------- Global Distance Matrix --------------------------\n\n"); int global_distance[n][m]; global_distance[0][0] = local_distance[0][0]; printf("%d\t ",global_distance[0][0]); for(i=1; i<n; i++) // generating first row element of global_distance matrix global_distance[i][0] = local_distance[i][0] + global_distance[i-1][0]; for(k=1; k<m; k++) // generating first column element of global_distance matrix { global_distance[0][k] = local_distance[0][k] + global_distance[0][k-1]; printf("%d\t ",global_distance[0][k]); } printf("\n"); for(i=1; i<n; i++) { printf("%d\t ",global_distance[i][0]); for(k=1; k<m; k++) { global_distance[i][k] = local_distance[i][k] + min(global_distance[i-1][k],global_distance[i-1][k-1],global_distance[i][k-1]); printf("%d\t ",global_distance[i][k]); } printf("\n"); } printf("-------------------------------------------------------------------------------\n\n"); printf("Optimal Warping Path : (0,0) "); i=0; k=0; while((i!=n-1)||(k!=m-1)) { if(i==n-1) // if you reached to the last row (n-1) then go only one step forward in last row k=k+1; else if(k==m-1) //if you have reached to the last column (m-1) then go only one step upward in last column i=i+1; else { int global_minm = min(global_distance[i+1][k],global_distance[i+1][k+1],global_distance[i][k+1]); if(global_distance[i+1][k] == global_minm) { i=i+1; } else if(global_distance[i+1][k+1] == global_minm) { i=i+1; k=k+1; } else//(global_distance[i][k+1] == global_minm) { k=k+1; } } printf("(%d,%d) ",i,k); } printf("\nOptimal Warping Path Cost : %d\n", global_distance[n-1][m-1]); printf("\n-------------------------------------------------------------------------------\n\n"); return 0; } |
2.
다시 처음으로 돌아갑니다. 위의 논문을 찾아보니 한국데이타정보과학회지에 실린 글이더군요. 그렇지만 색인에 나오지 않았습니다. 여러번 확인끝에 선물시장의 시스템트레이딩에서 동적시간와핑 알고리즘을 이용한 최적매매빈도의 탐색 및 거래전략의 개발에서 찾을 수 있었습니다.
DTW가 더 궁금하시면 2차 미분 연산자를 이용한 효과적인 Dynamic Time Warping을 읽어보세요. 영어가 아니라 한글입니다.
그러면 DTW방법을 이용한 선물거래시스템 구현은 다음편에서.
