DTW와 퓨전기법을 이용한 비유사도 기반 분류법의 최적화

김상운(Sang-Woon Kim),김승환(Seunghwan Kim) 大韓電子工學會 2010 電子工學會論文誌-CI (Computer and Information) Vol.47 No.2

본 논문에서는 동적시간교정법(dynamic time warping: DTW)과 다중퓨전기법(multiple fusion strategy: MFS)을 연속 적용하여 비유사도기반 분류법(dissimilarity-based classification: DBC)을 최적화시키는 방법의 실험결과를 보고한다. DBC란 샘플 패턴을 분류하기 위하여 샘플의 특징 값을 이용하는 대신에 샘플들 사이의 비유사도를 측정하여 분류기를 설계하는 방법이다. DTW에서는 다음과 같이 두 단계로 나누어 비유사도를 측정한다. 먼저 상관계수를 이용하여 객체 샘플들을 대응시키기 위한 최적의 대응경로를 찾을 수 있도록 샘플들을 조정한다. 그리고 기존의 거리측정법으로 조정된 샘플들 사이의 비유사도를 측정 한다. MFS에서는 분류기결합 뿐만 아니라 비유사도 행렬생성에서도 퓨전기법을 적용한다. 즉, DTW 기법으로 작성한 다수의 비유사도 행렬들을 결합하여 새로운 비유사도 행렬을 생성한 다음, 이 행렬공간에서 여러 개의 베이스 분류기를 학습하여 다시 결합한다. 본 논문에서 제안한 방법을 벤취마크 영상 데이터베이스를 대상으로 실험한 결과, 기존의 방법과 비교하여 분류 성능을 향상시킬 수 있음을 확인하였다. 이와 같은 실험결과로 볼 때, 제안 방법을 멀티미디어 정보검색 등과 같은 다른 고차원 응용에도 활용할 수 있을 것으로 사료된다. This paper reports an experimental result on optimizing dissimilarity-based classification(DBC) by simultaneously using a dynamic time warping(DTW) and a multiple fusion strategy(MFS). DBC is a way of defining classifiers among classes; they are not based on the feature measurements of individual samples, but rather on a suitable dissimilarity measure among the samples. In DTW, the dissimilarity is measured in two steps: first, we adjust the object samples by finding the best warping path with a correlation coefficient-based DTW technique. We then compute the dissimilarity distance between the adjusted objects with conventional measures. In MFS, fusion strategies are repeatedly used in generating dissimilarity matrices as well as in designing classifiers: we first combine the dissimilarity matrices obtained with the DTW technique to a new matrix. After training some base classifiers in the new matrix, we again combine the results of the base classifiers. Our experimental results for well-known benchmark databases demonstrate that the proposed mechanism achieves further improved results in terms of classification accuracy compared with the previous approaches. From this consideration, the method could also be applied to other high-dimensional tasks, such as multimedia information retrieval.

면적속도 기반 DTW를 이용한 이탈 항적 탐지

박지훈(Ji Hun Park),문성일(Seong Il Mun),고영호(Young Ho Ko),박헌진(Heon Jin Park) 한국자료분석학회 2023 Journal of the Korean Data Analysis Society Vol.25 No.2

항공 안전 분야에서 데이터를 분석하여 항공 사고 전조 징후를 탐지하는 연구가 이루어지고 있다. 정상적인 궤도로부터 벗어나는 항공기의 궤적을 뜻하는 이탈 항적은 항공로 구간에서 발생하는 항공 사고의 전조 징후 중 하나이다. 항공로 구간은 출발 절차를 마친 이후부터 착륙 절차를 시작하기 전 구간을 의미한다. 항적 데이터는 시간에 따른 위치 정보를 의미하는 궤적 데이터이다. 항적 데이터와 같이 궤적을 이루는 샘플 포인트 개수가 상이한 궤적 데이터의 비유사도를 산출하는 일반적인 방법은 DTW(dynamic time warping)이다. 그러나 이탈 항적 탐지에는 거리 기반의 비유사도보다 정상 항적으로부터 면적 기반의 비유사도가 더 유용하다. 이에 본 연구에서는 면적에 상응하는 값을 산출하는 ‘면적 속도 기반 DTW(이하 ADTW)'를 개발하였다. ADS-B(automatic dependent surveillance-broadcast) 항적 자료를 이용해 DTW와 ADTW 방법으로 각각 비유사도를 산출한 후 클러스터링 기반 이상치 탐지 기술을 이용하여 이탈 항적을 판단하였다. 클러스터링은 k-medoids 방법인 PAM(partitioning around medoids)을 이용하였다. Average silhouette 산출 결과 2개의 클러스터로 분류되었으며 각 클러스터의 대표 항적으로부터 비유사도를 이용해 이탈 항적을 탐지하였다. 이탈 항적 탐지 기준은 분위수를 이용해 구축하였다. 클러스터의 평균 실루엣 너비를 이용해 평가하였을 때 ADTW가 DTW보다 높은 성적을 나타냈다. In the field of aviation safety, data analysis research is being conducted to detect the precursors of aviation accidents. A deviation trajectory, which means the trajectory of an aircraft deviating from its normal trajectory, is one of the precursor signs of an aviation accident that occurs in an en-route section. The en-route section means segment of flight from the termination point of a departure procedure to the origination point of an arrival procedure. trajectory data is track data meaning positional information according to time. A general method for calculating the dissimilarity of trajectory data having different numbers of sample points constituting the trajectory is dynamic time wrapping (DTW). However, area-based dissimilarity from normal tracks is more useful than distance-based dissimilarity for deviation trajectory detection. Therefore, in this study, ‘area velocity-based DTW (hereafter referred to as ADTW)' was developed to calculate the value corresponding to the area. Dissimilarity was calculated by DTW and ADTW methods using ADS-B (automatic dependent surveillance-broadcast) trajectory data, and then deviation tracks were determined using clustering-based outlier detection technology. For clustering, the k-medoids method, PAM (partitioning around medoids), was used. As a result of calculating the average silhouette, it was classified into two clusters, and the deviation track was detected using the dissimilarity from the representative track of each cluster. Detection criteria were constructed using quantiles. When evaluated using the average silhouette width of clusters, ADTW performed better than DTW.

거리 행렬 연산 구조 최적화를 위한 확산 동적 시간 왜곡(Diffusive DTW) 알고리즘

김영탁(Young-tak Kim),진교홍(Kyo-hong Jin) 한국정보통신학회 2022 한국정보통신학회 종합학술대회 논문집 Vol.26 No.2

DTW는 길이가 서로 다른 시퀀스 사이의 간격을 제거하고 패턴의 유사성을 알아낼 수 있지만, 시공간 복잡성 때문에 대규모 데이터셋에서 많은 계산 비용이 필요로 한다. 본 논문에서는 계산 비용을 줄일 뿐만 아니라 결괏값의 오차도 없는 DDTW 알고리즘을 제안한다. 그리고 시퀀스의 길이에 따른 연산 시간을 측정하여 DTW와 DDTW의 알고리즘 복잡도를 비교한다. 시뮬레이션 결과 DTW에 비해 DDTW에서 연산 시간이 눈에 띄게 줄어듦을 확인하였다. DTW can eliminate gaps between sequences of different lengths and find out the similarity of patterns, but due to the time and space complexity, it requires a high computational cost on large datasets. In this paper, we propose a DDTW algorithm that not only reduces computational costs but also has no error in the results. In addition, the algorithm complexity of DTW and DDTW is compared by measuring the computational time according to the length of the sequence. Simulation results show a noticeable reduction in computational time in DDTW compared to DTW.

어.음식별중DTW개진산법적연구

왕홍려,최영일 한국어정보학회 2009 한국어정보학 Vol.11 No.2

인간 컴퓨터 상호작용 : Dynamic Time Warping 기반의 특징 강조형 제스처 인식 모델

권혁태 ( Hyuck Tae Kwon ),이석균 ( Suk Kyoon Lee ) 한국정보처리학회 2015 정보처리학회논문지. 소프트웨어 및 데이터 공학 Vol.4 No.3

스마트 디바이스가 보편화되면서 이에 내장된 가속도 센서를 사용한 제스처의 인식에 관한 연구가 주목받고 있다. 최근 가속도 센서 데이터 시컨스를 통한 제스처 인식에 Dynamic Time Warping(DTW) 기법이 사용되는데, 본 논문에서는 DTW 사용 시 제스처의 인식률을 높이기 위한 특징 강조형 제스처 인식(FsGr) 모델을 제안한다. FsGr 모델은 잘못 인식될 가능성이 높은 유사 제스처들의 집합에 대해 특징이 강조되는 데이터 시컨스의 부분들을 정의하고 이들에 대해 추가적인 DTW를 실행하여 인식률을 높인다. FsGr 모델의 훈련 과정에서는 유사 제스처들의 집합들을 정의하고 유사 제스처들의 특징들을 분석한다. 인식 과정에서는 DTW를 사용한 1차 인식 시도의 결과 제스처가 유사 제스처 집합에 속한 경우, 특징 분석 결과를 기반으로 한 추가적인 인식을 시도하여 인식률을 높인다. 알파베트 소문자에 대한 인식 실험을 통해 FsGr 모델의 성능 평가 결과를 보인다. As smart devices get popular, research on gesture recognition using their embedded-accelerometer draw attention. As Dynamic Time Warping(DTW), recently, has been used to perform gesture recognition on data sequence from accelerometer, in this paper we propose Feature-Strengthened Gesture Recognition(FsGr) Model which can improve the recognition success rate when DTW is used. FsGr model defines feature-strengthened parts of data sequences to similar gestures which might produce unsuccessful recognition, and performs additional DTW on them to improve the recognition rate. In training phase, FsGr model identifies sets of similar gestures, and analyze features of gestures per each set. During recognition phase, it makes additional recognition attempt based on the result of feature analysis to improve the recognition success rate, when the result of first recognition attempt belongs to a set of similar gestures. We present the performance result of FsGr model, by experimenting the recognition of lower case alphabets.

DTW를 이용한 SVM 기반 이진트리 구조 설계

강윤정(Youn Joung Kang),이재일(Jaeil Lee),배진호(Jinho Bae),이승우(Seung Woo Lee),이종현(Chong Hyun Lee) 대한전자공학회 2014 전자공학회논문지 Vol.51 No.6

본 논문은 DTW 결과를 이용하여 분류기 구조를 설계하는 알고리즘을 제안한다. 제안된 알고리즘은 다수 클래스의 데이터를 분류하기 위한 SVM 기반 이진트리 구조를 설계하는데 있어 DTW 결과를 이용한다. 각 클래스에 대한 데이터를 DTW의 입력으로 하여 얻어진 결과행렬의 열의 합을 이용하여 계산된 임계치를 기준으로 SVM 기반 이진트리 구조(SVM-BTA)를 설계한다. 제안된 알고리즘의 성능 비교를 위해 데이터베이스와 k-means 알고리즘을 이용한 이진트리 구조의 분류 결과를 비교한다. 분류에 사용된 데이터는 수중과도소음 데이터베이스의 18개 클래스 333개의 데이터이다. 제안된 분류기는 데이터베이스의 체계를 이용한 분류기에 비해 분류성능이 향상되었고, k-means 알고리즘을 이용한 분류기에 비해 비 생물소음의 검출 확률이 향상되었다. 제안된 SVM-BTA는 생물 소음(BO) 68.77%, 기계 소음인 체인(CHAN) 92.86%, 그 외의 기계 소음 및 음향학적 소음, 기타소음의 6종은 100%로 분류한다. In this paper, we propose the classifier structure design algorithm using DTW. Proposed algorithm uses DTW result to design the binary tree architecture based on the SVM which classify the multi-class data. Design the binary tree architecture for Support Vector Machine(SVM-BTA) using the threshold criterion calculated by the sum columns in square matrix which components are the reference data from each class. For comparison the performance of the proposed algorithm, compare the results of classifiers which binary tree structure are designed based on database and k-means algorithm. The data used for classification is 333 signals from 18 classes of underwater transient noise. The proposed classifier has been improved classification performance compared with classifier designed by database system, and probability of detection for non-biological transient signal has improved compare with classifiers using k-means algorithm. The proposed SVM-BTA classified 68.77% of biological sound(BO), 92.86% chain(CHAN) the mechanical sound, and 100% of the 6 kinds of the other classes.

2차 미분 연산자를 이용한 효과적인 Dynamic Time Warping

김세훈(Se-Hoon Kim),최형일(Hyung-Il Choi),이양원(Yang-Won Rhee),장석우(Seok-Woo Jang) 한국컴퓨터정보학회 2011 韓國컴퓨터情報學會論文誌 Vol.16 No.2

동적계획법이 기반인 Dynamic Time Warping은 두 패턴의 유사도를 비교하기 위해 널리 사용되는 방법이다. DTW알고리즘에는 2가지 알려진 문제점이 있다. 첫 번째 문제는 DTW알고리즘은 2개의 패턴의 대응경로를 계산하면서 특이점이 발생하는 문제가 발생하게 된다. 두 번째 문제는 동적패턴의 대응경로가 올바른지 알 수 없다는 문제가 있다. 이에 본 논문에서는 DTW알고리즘의 문제에 대한 효과적인 해결을 위하여, 2차 미분 연산자를 적용한 DTW알고리즘을 제안 한다. 2차 미분 연산자의 하나인 "라플라시안오브가우시안" 연산자를 적용하여, 효과적으로 특이점에 대한 문제를 해결하고, 올바른 대응경로를 가질 수 있는 방법에 대하여 제안하고, 실험의 결과로 제안하는 알고리즘의 우수성을 증명한다. Dynamic Time Warping based on Dynamic Programming is the one of the most widely been used to compare the similarity of two patterns. DTW algorithm has two known problems. The one is singularities. And the another problem is the accuracy of the warping path with patterns. Therefore, this paper suggest the solution for DTW algorithm to use a 2nd derivative operator. Laplacian of Gaussian is a kind of a 2nd derivative operator. Consequently, our suggestion method to apply to this operator, more efficient to solve the singularities problems and to secure a accuracy of the warping path. And the result shows a superior ability of this suggested method.

잡음환경에서의 Noise Cancel DTW를 이용한 음성인식에 관한 연구

안종영,김성수,김수훈,고시영,허강인 한국인터넷방송통신학회 2011 한국인터넷방송통신학회 논문지 Vol.11 No.4

본 논문에서는 잡음 환경에서의 음성인식 개선에 관한 내용으로 기존의 DTW에서 일종의 특징보상기법을 적용한 방식으로 예측잡음이 아닌 실생활에서의 음성잡음 데이터를 적용하여 인식모델을 잡음상황에 맞도록 적응시키는 방법으로 제안하는 Noise Cancel DTW를 사용하였다. 음성인식 시 주변노이즈를 고려한 참조패턴을 생성하여 특징 보상으로 인식률을 향상 시키는 방법으로 잡음 환경에서 음성 인식률을 향상 시켰다. In this paper, we propose the Noise Cancel DTW that to use a kind of feature compensation. This method is not to use estimated noise but we use real life environment noise data for Voice Recognition. And we applied this contaminated data for recognition reference model that suitable for noise environment. NCDTW is combined with surround noise when generating reference patten. We improved voice recognition rate at mobile environment to use NCDTW.

DTW를 이용한 보행 분석 시 warping path 특성

이현섭 대한체육학회 2020 대한스포츠융합학회지 (jcses) Vol.18 No.1

The purpose of this study was to investigate the characteristics of the warping path on gait patterns using the DTW algorithm. Participants in this study were consist of 20’s age of 10males and 10 females. Gait data obtained by a 3D motion analysis system analyzed using the DTW program made by Matlab’s functions. The analysis was performed 120 times including normal walking and abnormal walking. The length of the warping path relative to the reference sequences, and deviations was analyzed for the warping path calculated by the DTW program. The statistical method used in this study was a correlation, independent t-test, one-way ANOVA, and regression. The statistical significance level was  =.05. In this study, the correlation coefficient of Pearson was =.816 between the warping path length and the deviation, and this relationship was verified by regression analysis. The statistically significant difference between normal walking and abnormal walking appeared in the warping path length and in the deviation. The analysis according to walking phases showed a statistically significant defference between the support phase and the swing phase. In conclusion, if the length of the warping path is greater than about 127% compared to the diagonal length between two sequences, normal walking can be suspected, and if the mean of the warping path length deviations is greater than about 5.8, normal walking can be suspected also.

저비율 샘플링 음향 센서네트워크에서 DTW-Cosine 알고리즘을 이용한 목표물 식별기법

김영수(Youngsoo Kim),강종구(Jonggu Kang),김대영(Daeyoung Kim) 한국정보과학회 2008 정보과학회 컴퓨팅의 실제 논문지 Vol.14 No.2

센서네트워크에서 목표물 탐지하는데 있어 높은 샘플링이 수반되어야 하는 주파수 분석을 피하기 위하여, 낮은 샘플링 데이타를 이용하더라도 목표물 식별이 가능한 시계열(Time-series) 분석 기법으로서 시간 정합 유사도측정 알고리즘을 소개하고 그 중에 가장 우수한 DTW-Cosine 알고리즘을 제안한다. 시계열 분석 기법을 이용하여 패턴을 비교하기 위해서는 지역 시간 이동 문제와 공간 신호 변이 문제를 극복해야 하는데 DTW-Cosine 알고리즘은 이를 효과적으로 극복함과 동시에 Smoothing 기법을 통하여 다른 시간 정합 유사도 측정 알고리즘들에 비해 전체적으로 최소 10.31% 이상의 우수한 성능을 보였다. In this paper, to avoid the frequency analysis requiring a high sampling rate, time-warped similarity measure algorithms, which are able to classify objects even with a low-rate sampling rate as time-series methods, are presented and proposed the DTW-Cosine algorithm, as the best classifier among them in wireless sensor networks. Two problems, local time shifting and spatial signal variation, should be solved to apply the time-warped similarity measure algorithms to wireless sensor networks. We find that our proposed algorithm can overcome those problems very efficiently and outperforms the other algorithms by at least 10.31 % accuracy.