유사 시퀀스 매칭에서는 고차원인 시퀀스를 저차원의 점으로 변환하기 위하여 저차원 변환을 사용한다. 그런데, 이러한 저차원 변환은 시계열 데이터의 종류에 따라 인덱싱 성능에 있어서 큰 차이를 나타낸다. 즉, 어떤 저차원 변환을 선택하느냐가 유사 시퀀스 매칭의 인덱싱 성능에 큰 영향을 주게 된다. 이 문제를 해결하기 위하여, 본 논문에서는 하나의 인덱스에서 두 개 이상의 저차원 변환을 통합하여 사용하는 하이브리드 접근법을 제안한다. 먼저, 하나의 시퀀스에 두 개 이상의 저차원 변환을 적용하는 하이브리드 저차원 변환의 개념을 제안하고, 변환된 시퀀스간의 거리를 계산하는 하이브리드 거리를 정의한다. 다음으로, 이러한 하이브리드 접근법 사용하면 유사 시퀀스 매칭을 정확하게 수행할 수 있음을 정형적으로 증명한다. 또한, 제안한 하이브리드 접근법을 사용하는 인덱스 구성 및 유사 시퀀스 매칭 알고리즘을 제시한다. 다양한 시계열 데이터에 대한 실험 결과, 제안한 하이브리드 접근법은 단일 저차원 변환을 사용하는 경우에 비해서 우수한 성능을 보이는 것으로 나타났다. 이 같은 결과를 볼 때, 제안한 하이브리드 접근법은 다양한 특성을 지닌 다양한 시계열 데이터에 두루 적용될 수 있는 우수한 방법이라 사료된다.
유사 시퀀스 매칭에서는 고차원인 시퀀스를 저차원의 점으로 변환하기 위하여 저차원 변환을 사용한다. 그런데, 이러한 저차원 변환은 시계열 데이터의 종류에 따라 인덱싱 성능에 있어서 큰 차이를 나타낸다. 즉, 어떤 저차원 변환을 선택하느냐가 유사 시퀀스 매칭의 인덱싱 성능에 큰 영향을 주게 된다. 이 문제를 해결하기 위하여, 본 논문에서는 하나의 인덱스에서 두 개 이상의 저차원 변환을 통합하여 사용하는 하이브리드 접근법을 제안한다. 먼저, 하나의 시퀀스에 두 개 이상의 저차원 변환을 적용하는 하이브리드 저차원 변환의 개념을 제안하고, 변환된 시퀀스간의 거리를 계산하는 하이브리드 거리를 정의한다. 다음으로, 이러한 하이브리드 접근법 사용하면 유사 시퀀스 매칭을 정확하게 수행할 수 있음을 정형적으로 증명한다. 또한, 제안한 하이브리드 접근법을 사용하는 인덱스 구성 및 유사 시퀀스 매칭 알고리즘을 제시한다. 다양한 시계열 데이터에 대한 실험 결과, 제안한 하이브리드 접근법은 단일 저차원 변환을 사용하는 경우에 비해서 우수한 성능을 보이는 것으로 나타났다. 이 같은 결과를 볼 때, 제안한 하이브리드 접근법은 다양한 특성을 지닌 다양한 시계열 데이터에 두루 적용될 수 있는 우수한 방법이라 사료된다.
We generally use lower-dimensional transformations to convert high-dimensional sequences into low-dimensional points in similar sequence matching. These traditional transformations, however, show different characteristics in indexing performance by the type of time-series data. It means that the sel...
We generally use lower-dimensional transformations to convert high-dimensional sequences into low-dimensional points in similar sequence matching. These traditional transformations, however, show different characteristics in indexing performance by the type of time-series data. It means that the selection of lower-dimensional transformations makes a significant influence on the indexing performance in similar sequence matching. To solve this problem, in this paper we propose a hybrid approach that integrates multiple transformations and uses them in a single multidimensional index. We first propose a new notion of hybrid lower-dimensional transformation that exploits different lower-dimensional transformations for a sequence. We next define the hybrid distance to compute the distance between the transformed sequences. We then formally prove that the hybrid approach performs the similar sequence matching correctly. We also present the index building and the similar sequence matching algorithms that use the hybrid approach. Experimental results for various time-series data sets show that our hybrid approach outperforms the single transformation-based approach. These results indicate that the hybrid approach can be widely used for various time-series data with different characteristics.
We generally use lower-dimensional transformations to convert high-dimensional sequences into low-dimensional points in similar sequence matching. These traditional transformations, however, show different characteristics in indexing performance by the type of time-series data. It means that the selection of lower-dimensional transformations makes a significant influence on the indexing performance in similar sequence matching. To solve this problem, in this paper we propose a hybrid approach that integrates multiple transformations and uses them in a single multidimensional index. We first propose a new notion of hybrid lower-dimensional transformation that exploits different lower-dimensional transformations for a sequence. We next define the hybrid distance to compute the distance between the transformed sequences. We then formally prove that the hybrid approach performs the similar sequence matching correctly. We also present the index building and the similar sequence matching algorithms that use the hybrid approach. Experimental results for various time-series data sets show that our hybrid approach outperforms the single transformation-based approach. These results indicate that the hybrid approach can be widely used for various time-series data with different characteristics.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
그리고, 이러한 하이브리드 변환을 유사 시퀀스 매칭에 사용하기 위해서, 하이브리드 변환된 두 시퀀스간의 거리를 계산하기 위한 하이브리드 거리(hybrid distance)를 정의한다. 다음으로, 이러한 하이브리드 변환과 하이브리드 거리를 사용하면 유사 시퀀스 매칭을 정확하게 수행할 수 있음을 정리로서 제시하고 증명한다. 또한, 제안한 하이브리드 변환과 하이브리드 거리를 사용한 인덱스 구성 알고리즘과 유사 시퀀스 매칭 알고리즘을 제시한다.
셋째, E-Index는 내부적으로 여러 인덱스가 구성되므로, 여러 인덱스 관리에 따른 오버헤드가 뒤따른다. 따라서, 본 논문에서는 하나의 인덱스에서 두 개 이상의 저차원 변환을 통합하여 사용하는 하이브리드 접근법을 제안한다. 제안하는 하이브리드 접근법은 각 시계열 데이터에 대해서 두 개 이상의 인덱스를 모두 사용하므로, 상기의 문제점이 발생하지 않는다.
본 논문에서는 DFT, DWT, PAA 등의 많은 저차원 변환이 대부분의 에너지를 소수의 특성에만 집중한다는 점에 착안하여 새로운 저차원 변환을 제안한다. 즉, 여러 저차원 변환의 결과인 여러 특성들을 하나로 통합하는 새로운 저차원 변환을 정의한다.
반면에, 서브시퀀스 매칭은 데이터 시퀀스에 포함된 서브시퀀스들 중에서 질의 시퀀스와 유사한 서브시퀀스를 찾는 문제로서, 사용자는 임의 길이의 시퀀스를 질의 시퀀스로 사용할 수 있다. 본 논문에서는 이러한 전체 매칭과 서브시퀀스 매칭 모두에 적용되는 저차원 변환(lower-dimensional transformation) 문제를 다룬다. 저차원 변환이란 고차원 공간의 점, 즉 고차원 시퀀스를 저차원 공간의 점으로 변환하는 기법으로, 많은 유사 시퀀스 매칭에서 사용되었다[1-10].
본 논문에서는 하나의 인덱스에서 두 개 이상의 저차원 변환을 통합하여 사용하는 하이브리드 접근법을 새로운 저차원 변환 기법으로 제안한다. 본 논문에서 “하이브리드”라는 용어를 사용한 이유는 제안한 접근법이 기존의 여러 저차원 변환을 통합하여 사용하기 때문이다.
본 논문에서는 하이브리드 저차원 변환의 개념을 제시하고, 이를 사용한 유사 시퀀스 매칭 방법을 제안하였다. 제안한 하이브리드 저차원 변환은 하나의 시계열 데이터에 여러 저차원 변환을 동시에 적용하는 방법으로서, 하나의 인덱스에서 두 개 이상의 저차원 변환들을 통합하여 사용하도록 하였다.
이와 같이 저차원 변환은 유사 시퀀스 매칭에서의 인덱스 사용을 가능하게 하였으며, 이러한 인덱스 사용의 효과를 극대화하기 위하여 보다 인덱싱 성능이 우수한 저차원 변환에 대한 많은 연구가 진행되었다[2, 6, 8-10, 15, 17]. 본 논문의 제3장 및 제4장에서 제안하는 하이브리드 접근법은 이러한 기존의 저차원 변환들의 장점을 취합하여, 보다 인덱싱 성능을 높이자는데 그 목적이 있다. 이와 같이 인덱싱 성능을 높일 수 있다면 궁극적으로 유사 시퀀스 매칭의 전체 성능을 크게 향상 시킬 수 있기 때문이다.
이와 같이 하이브리드 변환을 사용하는 이유는 각각의 저차원 변환이 서로 다른 특징을 가지므로[10], 하나의 인덱스에서 이들 여러 저차원 변환에 의해 추출한 특성들을 통합하여 사용하기 위해서이다. 즉, 하나의 시퀀스에 대해 여러 저차원 변환을 통해 다양한 특성들을 추출하여 통합하여 사용함으로써, 여러 저차원 변환의 장점을 고루 발휘하자는데 그 목적이 있다.
정의 2의 하이브리드 거리의 의미는 하이브리드 저차원 변환을 사용할 때, 여러 저차원 변환 중에서 변환된 두 시퀀스 간의 거리를 최대로 하는 저차원 변환을 선택함을 의미한다. 즉, 하이브리드 변환된 두 시퀀스를 비교할 때 가장 큰 거리 값을 인덱싱에 사용하자는데 그 목적이 있다. 이와 같이 가장 큰 거리 값을 하이브리드 거리로 사용하게 되면, 궁극적으로 유사 시퀀스 매칭에 있어서 보다 높은 인덱싱 성능을 나타낼 수 있기 때문이다[2, 3]
제안 방법
저차원 변환으로는 DFT[1, 2, 5]와 PAA[8, 16]의 두 변환만을 사용하였는데, 이는 DCT는 DFT와, DWT는 PAA와 각각 특징이 유사하기 때문이다. 그리고, 제안한 하이브리드 저차원 변환은 이들 두 변환을 통합하는 방식으로 구현하였으며, 특성은 DFT 및 PAA 변환 각각에서 네 개를 추출하여 사용하였다. 유사 시퀀스 매칭 방법으로는 서브시퀀스 매칭 방법 중의 하나인 DualMatch[3]를 사용하였다.
먼저, 인덱스 구성 알고리즘에서는 데이터 시퀀스를 나눈 슬라이딩 윈도우로 f-차원의 점으로 변환하여 다차원 인덱스에 저장한다. 다음으로, 질의 시퀀스를 나눈 디스조인트 윈도우를 f-차원의 점으로 변환하고, 이 점을 기준으로 범위 질의 혹은 k-NN 질의를 구성한다. 그리고, 다차원 인덱스를 검색하여 후보 시퀀스들을 찾아내고, 후처리 과정을 통하여 실제 유사 서브시퀀스만을 찾는다
다음으로, 이러한 하이브리드 변환과 하이브리드 거리를 사용하면 유사 시퀀스 매칭을 정확하게 수행할 수 있음을 정리로서 제시하고 증명한다. 또한, 제안한 하이브리드 변환과 하이브리드 거리를 사용한 인덱스 구성 알고리즘과 유사 시퀀스 매칭 알고리즘을 제시한다. 다양한 시계열 데이터에 대한 실험 결과, 제안한 하이브리드 접근법은 단일 저차원 변환을 사용하는 경우에 비해 우수한 성능을 보이는 것으로 나타났다.
즉, E-Index는 최적의 성능을 목적으로, 미리 분석/예측한 데이터를 바탕으로 최적의 저차원 변환을 선택하고 여러 다차원 인덱스를 사용하는 방법을 취하였다. 반면에, 제안한 접근법은 실제 사용자가 데이터에 대한 지식이나 분석/예측 없이도 실용적으로 사용할 수 있도록 하기 위하여, 여러 저차원 변환을 하나의 인덱스에서 통합하여 사용하는 방법을 취하였다. 이와 같이, 문제 해결의 목적이 다른 두 방법의 성능을 직접적으로 비교는 큰 의미가 없다고 판단하였기 때문이다.
둘째, 하이브리드 변환된 두 시퀀스간의 거리를 계산하기 위한 하이브리드 거리를 제시하고, 이를 사용하면 유사 시퀀스 매칭을 정확하게 수행할 수있음을 정리 1에서 정형적으로 증명하였다. 셋째, 제안한 하이브리드 저차원 변환과 하이브리드 거리를 사용하는 인덱스 구성 및 유사 시퀀스 매칭 알고리즘을 제시하였다. 넷째, 제안한 하이브리드 접근법이 단일 저차원 변환을 사용하는 경우에 비해서 우수한 성능을 보임을 실험을 통하여 확인하였다.
실험 결과로는 질의 시퀀스 길이를 256으로 고정(윈도우 크기를 128으로 고정)하고, 선택율(selectivity)[2, 3]을 1.0E-05, 1.0E-04, 1.0E-03으로 달리하면서 각 변환에 의한 서브시퀀스 매칭의 실행 시간을 측정하였다. 질의 시퀀스 길이를 256으로 고정한 이유는 실험 결과가 질의 시퀀스 길이 자체에는 큰 영향을 받지 않기 때문이다.
즉, 여러 저차원 변환을 사용하되, 각 저차원 변환 별로 적은 수의 특성만을 추출한 후 이를 통합하여 인덱싱을 수행하는 방법이다. 이를 위해, 본 논문에서는 우선 하이브리드 저차원 변환(hybrid lower-dimensional transformation)의 개념을 제안한다(혹은 간략히 하이브리드 변환이라 한다). 하이브리드 저차원 변환은 두 개 이상의 저차원 변환을 사용하여 하나의 시퀀스에서 서로 다른 특징을 지닌 여러 특성들을 추출하는 저차원 변환 방법이다.
따라서, 본 논문에서는 하나의 인덱스에서 두 개 이상의 저차원 변환을 통합하여 사용하는 하이브리드 접근법을 제안한다. 제안하는 하이브리드 접근법은 각 시계열 데이터에 대해서 두 개 이상의 인덱스를 모두 사용하므로, 상기의 문제점이 발생하지 않는다. 즉, 각 부분에 적합한 저차원 변환을 분석/예측할 필요가 없으며, 하나의 인덱스만을 구축하므로 인덱스 오버헤드도 발생하지 않는다
본 논문에서는 하이브리드 저차원 변환의 개념을 제시하고, 이를 사용한 유사 시퀀스 매칭 방법을 제안하였다. 제안한 하이브리드 저차원 변환은 하나의 시계열 데이터에 여러 저차원 변환을 동시에 적용하는 방법으로서, 하나의 인덱스에서 두 개 이상의 저차원 변환들을 통합하여 사용하도록 하였다. 이를 통하여 여러 저차원 변환의 특성을 동시에 발휘할 수 있고, 궁극적으로 유사 시퀀스 매칭의 성능을 향상 시킬 수 있다.
실험에서 E-Index와 비교 실험은 수행하지 않았는데, 이는 E-Index와 하이브리드 접근법은 문제 해결의 목적이 다르기 때문이다. 즉, E-Index는 최적의 성능을 목적으로, 미리 분석/예측한 데이터를 바탕으로 최적의 저차원 변환을 선택하고 여러 다차원 인덱스를 사용하는 방법을 취하였다. 반면에, 제안한 접근법은 실제 사용자가 데이터에 대한 지식이나 분석/예측 없이도 실용적으로 사용할 수 있도록 하기 위하여, 여러 저차원 변환을 하나의 인덱스에서 통합하여 사용하는 방법을 취하였다.
본 논문의 공헌은 다음과 같이 요약할 수 있다. 첫째, 여러 개의 저차원 변환을 사용하여 하나의 시퀀스에서 서로 다른 특징을 지닌 여러 특성들을 추출하는 하이브리드 저차원 변환 개념을 제안하였다. 둘째, 하이브리드 변환된 두 시퀀스간의 거리를 계산하기 위한 하이브리드 거리를 제시하고, 이를 사용하면 유사 시퀀스 매칭을 정확하게 수행할 수있음을 정리 1에서 정형적으로 증명하였다.
대상 데이터
첫 번째 데이터는 329,112개 엔트리로 구성된 실제 주식 데이터[2, 3]로서, 이를 STOCK-DATA라 한다. 두 번째 데이터는 주식 데이터와 유사한 특성을 갖는 100만개 엔트리의 랜덤 워크 데이터 (random walk data)[2, 3, 5]로서, 이 데이터를 WALK-DATA라 한다. 세 번째 데이터는 사인(sine) 함수를 사용하여 생성한 100만개의 스트리밍 시계열[15, 18]로서, 이를 SINE-DATA라 한다.
질의 시퀀스는 데이터 시퀀스의 랜덤 오프셋(random offset)을 시작 엔트리로 하는 서브시퀀스를 추출하여 사용하였으며, 노이즈를 피하기 위하여 같은 길이를 갖는 10개의 다른 질의 시퀀스에 대해서 실험한 후 평균을 취한 값을 실험 결과로 하였다. 실험을 수행한 하드웨어 플랫폼은 Intel Pentium IV 2.80GHz, 512MB RAM, 70.0GB 하드디스크를 장착한 PC이다. 그리고, 소프트웨어 플랫폼은 GNU/Linux Version 2.
0E-01에 가까워지면 대다수의 서브시퀀스가 후보로 선택되기 때문이다. 이에 따라, 본 논문에서는 선택율 범위가 낮은 1.0E-05, 1.0E-04, 1.0E-03의 세 가지를 실험에 사용하였다. 질의 시퀀스는 데이터 시퀀스의 랜덤 오프셋(random offset)을 시작 엔트리로 하는 서브시퀀스를 추출하여 사용하였으며, 노이즈를 피하기 위하여 같은 길이를 갖는 10개의 다른 질의 시퀀스에 대해서 실험한 후 평균을 취한 값을 실험 결과로 하였다.
제안한 하이브리드 저차원 변환이 여러 시계열 데이터에 잘 적용됨을 보이기 위하여, 본 논문에서는 특징이 다른 네가지 종류의 데이터를 실험에 사용하였다. 첫 번째 데이터는 329,112개 엔트리로 구성된 실제 주식 데이터[2, 3]로서, 이를 STOCK-DATA라 한다.
질의 시퀀스 길이를 256으로 고정한 이유는 실험 결과가 질의 시퀀스 길이 자체에는 큰 영향을 받지 않기 때문이다. 즉, 현재 길이인 256에서 4개 특성을 추출하였는데, 길이를 512로 변경할 경우 특성을 8개 추출하면 매우 유사한 결과를 얻을 수 있으므로, 질의 시퀀스 길이는 256으로 고정하고 실험을 수행하였다. 다음으로, 선택율 범위를 1.
데이터처리
0E-03의 세 가지를 실험에 사용하였다. 질의 시퀀스는 데이터 시퀀스의 랜덤 오프셋(random offset)을 시작 엔트리로 하는 서브시퀀스를 추출하여 사용하였으며, 노이즈를 피하기 위하여 같은 길이를 갖는 10개의 다른 질의 시퀀스에 대해서 실험한 후 평균을 취한 값을 실험 결과로 하였다. 실험을 수행한 하드웨어 플랫폼은 Intel Pentium IV 2.
이론/모형
고차원 시퀀스의 저차원 변환 방법으로는 DFT(Discrete Fourier Transform), DWT(Discrete Wavelet Transform), PAA(Piecewise Aggregate Approximation) 등 여러 가지 변환이 사용되었다. 우선, DFT는 참고문헌 [1, 2, 5, 7, 13, 14, 15] 등 많은 연구에서 가장 널리 사용되었다.
그리고, 제안한 하이브리드 저차원 변환은 이들 두 변환을 통합하는 방식으로 구현하였으며, 특성은 DFT 및 PAA 변환 각각에서 네 개를 추출하여 사용하였다. 유사 시퀀스 매칭 방법으로는 서브시퀀스 매칭 방법 중의 하나인 DualMatch[3]를 사용하였다. 성능평가는 하이브리드 저차원 변환과 DFT 혹은 PAA의 단일 저차원 변환을 비교하는 방식을 취하였다.
성능/효과
그림에서 가로축은 선택율을, 세로축은 하이브리드 저차원 변환에 대한 DFT와 PAA의 상대적 실행 시간 비율을 나타낸다. (그림 4)를 보면, DFT와 PAA는 거의 유사한 성능을 보인 반면에, 제안한 하이브리드 변환은 DFT 및 PAA에 비해 우수한 성능을 보임을 알 수 있다. 이는 하이브리드 변환이 시계열 데이터의 모든 구간에 대해서 DFT와 PAA를 통합하는 최적의 변환을 수행하기 때문이다.
이는 선택율이 높아질 수록 저차원 변환을 사용하는 인덱싱 과정보다는 실제 데이터 시퀀스를 액세스하는 후처리 과정이 성능에 큰 영향을 미치기 때문이다. (그림 4)의 STOCK- DATA 실험 결과를 요약하면, 제안한 하이브리드 저차원 변환은 DFT에 비해 최대 32.4%, PAA에 비해 최대 27.1%까지 성능을 향상시킨 것으로 나타났다.
반면에, 선택율이 높은 구간에서는 오히려 PAA가 DFT보다 우수한 것으로 나타났는데, 이는 선택율이 높아져 많은 유사한 시퀀스를 매칭 대상으로 할 경우, 각 구간별로 특성을 추출하는 PAA가 시퀀스 전체에서 특성을 추출하는 DFT에 비해 시퀀스 간 거리 구분 성능이 뛰어나기 때문이다. (그림 5)의 WALK-DATA의 실험 결과를 요약하면, 제안한 하이브리드 변환이 DFT에 비해 최대 28.9%, PAA에 비해 최대 34.5%까지 성능을 향상시킨 것으로 나타났다
이는 제안한 하이브리드 변환이 DFT와 PAA의 특징을 통합하여 발휘하기 때문이다. (그림 6)의 결과를 보면, 하이브리드 변환이 가장 우수한 반면에 DFT와 PAA는 성능 차이가 거의 없는 것으로 나타났다. 이는 SINE-DATA 가 이웃한 엔트리 변화가 적은 WALK-DATA를 모태로 생성된 반면에, 주기성을 가지므로 유사한 시퀀스가 반복하여 나타나는 특징 때문이다.
결과적으로, 제안한 하이브리드 변환은 데이터의 종류나 선택율의 범위에 관계없이 단일 저차원 변환보다 우수한 성능을 보인다고 말할수 있다. (그림 7)의 PERIOD-DATA의 실험 결과에서는 하이브리드 변환이 DFT에 비해 최대 45.6%, PAA에 비해 최대 79.7%까지 성능을 향상시킨 것으로 나타났다.
지금까지의 실험 결과를 종합하면, 하이브리드 저차원 변환은 시계열 데이터의 종류나 선택율 범위에 관계없이 단일 저차원 변환을 사용하는 경우보다 우수한 성능을 보인다고할 수 있다. 가장 좋은 결과를 보인 경우는 선택율 1.0E-05로 낮고 PERIOD-DATA를 사용한 경우로서, 이때 하이브리드 변환은 DFT 보다는 최대 45.6%까지, PAA 보다는 최대 79.7%까지 성능을 향상시키는 것으로 나타났다. 가장 좋지 않은 결과를 보인 경우는 선택율이 1.
7%까지 성능을 향상시키는 것으로 나타났다. 가장 좋지 않은 결과를 보인 경우는 선택율이 1.0E-03으로 높고 SINE-DATA를 사용한 경우인데, 이때 역시 하이브리드 변환은 DFT에 비해 최대 21.0%, PAA에 비해 최대 19.3%까지 성능을 나타낸 것으로 나타났다. 이 같은 결과를 종합하면, 데이터나 선택율에 따라 어떤 저차원 변환을 선택할 고민이 없이, 여러 저차원 변환을 통합하는 하이브리드 변환을 사용하면 유사 시퀀스 매칭에 있어서 보다 향상된 성능을 얻을 수 있음 의미한다.
그러나, DFT와 PAA의 특징을 통합한 하이브리드 저차원 변환은 이들 모든 구간에 있어서 가장 우수한 성능을 보이고 있다. 결과적으로, 제안한 하이브리드 변환은 데이터의 종류나 선택율의 범위에 관계없이 단일 저차원 변환보다 우수한 성능을 보인다고 말할수 있다. (그림 7)의 PERIOD-DATA의 실험 결과에서는 하이브리드 변환이 DFT에 비해 최대 45.
셋째, 제안한 하이브리드 저차원 변환과 하이브리드 거리를 사용하는 인덱스 구성 및 유사 시퀀스 매칭 알고리즘을 제시하였다. 넷째, 제안한 하이브리드 접근법이 단일 저차원 변환을 사용하는 경우에 비해서 우수한 성능을 보임을 실험을 통하여 확인하였다. 이 같은 결과를 볼 때, 제안한 하이브리드 접근법은 다양한 특성을 지닌 다양한 시계열 데이터에 두루 적용될수 있는 우수한 방법이라 사료된다.
또한, 제안한 하이브리드 변환과 하이브리드 거리를 사용한 인덱스 구성 알고리즘과 유사 시퀀스 매칭 알고리즘을 제시한다. 다양한 시계열 데이터에 대한 실험 결과, 제안한 하이브리드 접근법은 단일 저차원 변환을 사용하는 경우에 비해 우수한 성능을 보이는 것으로 나타났다. 특히, 하이브리드 저차원 변환은 시계열 데이터의 종류나 선택율 범위에 관계없이 단일 저차원 변환을 사용하는 경우보다 우수한 성능을 보이는 것으로 나타났다.
첫째, 여러 개의 저차원 변환을 사용하여 하나의 시퀀스에서 서로 다른 특징을 지닌 여러 특성들을 추출하는 하이브리드 저차원 변환 개념을 제안하였다. 둘째, 하이브리드 변환된 두 시퀀스간의 거리를 계산하기 위한 하이브리드 거리를 제시하고, 이를 사용하면 유사 시퀀스 매칭을 정확하게 수행할 수있음을 정리 1에서 정형적으로 증명하였다. 셋째, 제안한 하이브리드 저차원 변환과 하이브리드 거리를 사용하는 인덱스 구성 및 유사 시퀀스 매칭 알고리즘을 제시하였다.
둘째, 시계열 데이터의 각 부분에 대해서 최적의 저차원 변환을 선택하고, 이를 바탕으로 인덱스를 구성하는 작업을 일반적인 사용자에게 적용하기는 매우 어렵다. 셋째, E-Index는 내부적으로 여러 인덱스가 구성되므로, 여러 인덱스 관리에 따른 오버헤드가 뒤따른다. 따라서, 본 논문에서는 하나의 인덱스에서 두 개 이상의 저차원 변환을 통합하여 사용하는 하이브리드 접근법을 제안한다.
즉, 선택율이 낮은 구간에서는 엔트리 변화의 효과가 크게 발휘된 반면에, 선택 율이 높은 구간에서는 PERIOD-DATA의 특징인 유사 시퀀스의 반복 효과가 크게 발휘되기 때문이다. 엔트리 변화의 효과가 크게 발휘된 선택율이 낮은 구간에서는 DFT가 우수한 성능을 보이고, 유사 시퀀스의 반복 효과가 크게 발휘된 선택율이 높은 구간에서는 오히려 PAA가 우수한 성능을 보인 것이다. 이와 같이 선택율에 따라 최적의 인덱싱을 보이는 저차원 변환이 달라질 수 있다.
이 같은 결과를 종합하면, 데이터나 선택율에 따라 어떤 저차원 변환을 선택할 고민이 없이, 여러 저차원 변환을 통합하는 하이브리드 변환을 사용하면 유사 시퀀스 매칭에 있어서 보다 향상된 성능을 얻을 수 있음 의미한다. 이 같은 결과를 볼 때, 제안한 하이브리드 접근법은 다양한 특성을 지닌 다양한 시계열 데이터에 두루 적용될 수 있는 우수한 방법이라 사료된다.
이 같은 결과를 종합하면, 데이터나 선택율에 따라 어떤 저차원 변환을 선택할 고민이 없이, 여러 저차원 변환을 통합하는 하이브리드 변환을 사용하면 유사 시퀀스 매칭에 있어서 보다 향상된 성능을 얻을 수 있음 의미한다. 이 같은 결과를 볼 때, 제안한 하이브리드 접근법은 다양한 특성을 지닌 다양한 시계열 데이터에 두루 적용될 수 있는 우수한 방법이라 사료된다.
특히, 하이브리드 저차원 변환은 시계열 데이터의 종류나 선택율 범위에 관계없이 단일 저차원 변환을 사용하는 경우보다 우수한 성능을 보이는 것으로 나타났다. 이 같은 결과를 종합하면, 데이터나 선택율에 따라 어떤 저차원 변환을 선택할 고민이 없이, 여러 저차원 변환을 통합하는 하이브리드 변환을 사용하면 유사 시퀀스 매칭에 있어서 보다 향상된 성능을 얻을 수 있음 의미한다. 이 같은 결과를 볼 때, 제안한 하이브리드 접근법은 다양한 특성을 지닌 다양한 시계열 데이터에 두루 적용될 수 있는 우수한 방법이라 사료된다.
이는 하이브리드 변환이 시계열 데이터의 모든 구간에 대해서 DFT와 PAA를 통합하는 최적의 변환을 수행하기 때문이다. 즉, 각 부분 부분에서는 DFT나 PAA가 최적일 수 있으나, 시계열 전체 데이터 측면에서는 DFT와 PAA를 통합한 하이브리드 변환이 가장 좋은 성능을 나타냄을 의미한다. (그림 4)에서 PAA가 DFT보다 약간 우수한 결과를 보이는데, 이는 STOCKDATA의 경우 다른 데이터에 비해서 이웃한 엔트리들의 변화가 비교적 크고, 이는 PAA의 평균 방식이 DFT의 계수 방식 보다 유리하기 때문이다.
이는 SINE-DATA 가 이웃한 엔트리 변화가 적은 WALK-DATA를 모태로 생성된 반면에, 주기성을 가지므로 유사한 시퀀스가 반복하여 나타나는 특징 때문이다. 즉, 엔트리 변화가 작은 점은 DFT 에 유리하게 작용하나, 유사 시퀀스가 반복하여 나타나는 성질은 PAA에 유리하게 작용하여, 두 방법에 의한 차이가 거의 비슷하게 나타났다. (그림 6)의 SINE-DATA의 결과에서 하이브리드 변환은 DFT에 비해 최대 21.
지금까지의 실험 결과를 종합하면, 하이브리드 저차원 변환은 시계열 데이터의 종류나 선택율 범위에 관계없이 단일 저차원 변환을 사용하는 경우보다 우수한 성능을 보인다고할 수 있다. 가장 좋은 결과를 보인 경우는 선택율 1.
다양한 시계열 데이터에 대한 실험 결과, 제안한 하이브리드 접근법은 단일 저차원 변환을 사용하는 경우에 비해 우수한 성능을 보이는 것으로 나타났다. 특히, 하이브리드 저차원 변환은 시계열 데이터의 종류나 선택율 범위에 관계없이 단일 저차원 변환을 사용하는 경우보다 우수한 성능을 보이는 것으로 나타났다. 이 같은 결과를 종합하면, 데이터나 선택율에 따라 어떤 저차원 변환을 선택할 고민이 없이, 여러 저차원 변환을 통합하는 하이브리드 변환을 사용하면 유사 시퀀스 매칭에 있어서 보다 향상된 성능을 얻을 수 있음 의미한다.
후속연구
또한, 비록 하이브리드 변환이 기존 저차원 변환에 비해 뛰어난(몇 배 혹은 몇 십배) 성능 개선 효과를 거두지는 못하지만, 이들 여러 변환의 장점을 취할 수있는 우수한 접근법이라 할 수 있다. 즉, 새로운 저차원 변환이 개발되어 우수한 성능을 보인다면, 이를 본 논문의 하이브리드 접근법에 적용하면 보다 더 우수한 저차원 변환 개발이 가능한 프레임워크를 제공한다고 말할 수 있다.
질의응답
핵심어
질문
논문에서 추출한 답변
시계열 데이터란 어떤 값의 시퀀스인가요?
시계열 데이터(time-series data)란 각 시간별로 측정한 실수 값의 시퀀스로, 그 예로는 주식 데이터, 환율 데이터, 날씨 변동 데이터 등이 있다[1, 2, 3, 4]. 시계열 데이터베이스에 저장된 시계열 데이터를 데이터 시퀀스라 부르며, 사용자에 의해 주어진 시퀀스를 질의 시퀀스라 부른다.
유사 시퀀스 매칭은 어떻게 구분되나요?
유사 시퀀스 매칭은 크게 전체 매칭(whole matching)과서브시퀀스 매칭(subsequence matching)의 두 가지로 구분 한다[2]. 전체 매칭은 질의 시퀀스와 유사한 데이터 시퀀스를 찾는 문제로서, 질의 시퀀스와 데이터 시퀀스의 길이가동일한 특징을 갖는다[1].
유사 시퀀스 매칭에서 구분되는 전체 매칭은 어떤 문제로서, 어떤 특징을 갖나요?
유사 시퀀스 매칭은 크게 전체 매칭(whole matching)과서브시퀀스 매칭(subsequence matching)의 두 가지로 구분 한다[2]. 전체 매칭은 질의 시퀀스와 유사한 데이터 시퀀스를 찾는 문제로서, 질의 시퀀스와 데이터 시퀀스의 길이가동일한 특징을 갖는다[1]. 반면에, 서브시퀀스 매칭은 데이터 시퀀스에 포함된 서브시퀀스들 중에서 질의 시퀀스와 유사한 서브시퀀스를 찾는 문제로서, 사용자는 임의 길이의 시퀀스를 질의 시퀀스로 사용할 수 있다.
참고문헌 (18)
Agrawal, R., Faloutsos, C., and Swami, A., 'Efficient Similarity Search in Sequence Databases,' In Proc. the 4th Int'l Conf. on Foundations of Data Organization and Algorithms, Chicago, Illinois, pp.69-84, Oct., 1993
Faloutsos, C., Ranganathan, M., and Manolopoulos, Y., 'Fast Subsequence Matching in Time-Series Databases,' In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, Minneapolis, Minnesota, pp.419-429, May, 1994
Moon, Y.-S., Whang, K.-Y., and Loh, W.-K., 'Duality-Based Subsequence Matching in Time-Series Databases,' In Proc. the 17th Int'l Conf. on Data Engineering(ICDE), IEEE, Heidelberg, Germany, pp.263-272, April, 2001
Keogh, E. J. et al., 'LB_Keogh Supports Exact Indexing of Shapes under Rotation Invariance with Arbitrary Representations and Distance Measures,' In Proc. Int'l Conf. on Very Large Data Bases (VLDB), Seoul, Korea, pp.882-893, Sept., 2006
Moon, Y.-S., Whang, K.-Y., and Han, W.-S., 'General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows,' In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, Madison, Wisconsin, pp.382-393, June, 2002
Chan, K.-P., Fu, A. W.-C., and Yu, C. T., 'Haar Wavelets for Efficient Similarity Search of Time-Series: With and Without Time Warping,' IEEE Trans. on Knowledge and Data Engineering, Vol.15, No.3, pp.686-705, Jan./Feb., 2003
Loh, W.-K., Kim, S.-W., and Whang, K.-Y., 'A Subsequence Matching Algorithm that Supports Normalization Transform in Time-Series Databases,' Data Mining and Knowledge Discovery, Vol.9, No.1, pp.5-28, July, 2004
Keogh, J., Chakrabarti, K., Mehrotra, S., and Pazzani, M. J., 'Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases,' In Proc. of Int'l Conf. on Management of Data, ACM SIGMOD, Santa Barbara, CA, pp.151-162, May, 2001
Keogh, J., Chakrabarti, K., Pazzani, M. J., and Mehrotra, S., 'Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases,' Knowledge and Information Systems, Vol.3, No.3, pp.263-286, Aug., 2001
Keogh, E. J., Chu, S., and Pazzani, M. J., 'Ensemble-Index: A New Approach to Indexing Large Databases,' In Proc. of the 7th Int'l Conf. on Knowledge Discovery and Data Mining, ACM SIGKDD, San Francisco, CA, pp.117-125, Aug., 2001
Berchtold, S., Bohm, C., and Kriegel, H.-P., 'The Pyramid- Technique: Towards Breaking the Curse of Dimensionality,' In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, Seattle, Washington, pp.142-153, June, 1998
Beckmann, N., Kriegel, H.-P., Schneider, R., and Seeger, B., 'The R*-tree: An Efficient and Robust Access Method for Points and Rectangles,' In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, Atlantic City, New Jersey, pp.322-331, May, 1990
Lim, S.-H., Park, H.-J., and Kim, S.-W., 'Using Multiple Indexes for Efficient Subsequence Matching in Time-Series Databases,' In Proc. of the 11th Int'l Conf. on Database Systems for Advanced Applications (DASFAA 2006), Singapore, pp.65-79, Apr., 2006
Moon, Y.-S. and Kim, J., 'A Single Index Approach for Time-Series Subsequence Matching that Supports Moving Average Transform of Arbitrary Order,' In Proc. of the 10th Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD 2006), Singapore, pp.739-749, Apr., 2006
Moon, Y.-S., 'An MBR-Safe Transform for High-Dimensional MBRs in Similar Sequence Matching,' In Proc. of the 12th Int'l Conf. on Database Systems for Advanced Applications (DASFAA 2007), Bangkok, Thailand, pp.79-90, April, 2007
Yi, B.-K. and Faloutsos, C., 'Fast Time Sequence Indexing for Arbitrary Lp Norms,' In Proc. of the 26th Int'l Conf. on Very Large Data Bases, Cairo, Egypt, pp.385-394, Sept., 2000
Hsieh, M. J., Chen, M. S., and Yu, P. S., 'Integrating DCT and DWT for Approximating Cube Streams,' In Proc. of the 14th ACM Int'l Conf. on Information and Knowledge Management, Bremen, Germany, pp.179-186, Oct., 2005
Gao, L. and Wang, X. S., 'Continually Evaluating Similaritybased Pattern Queries on a Streaming Time Series,' In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, Madison, Wisconsin, pp.370-381, June, 2002
※ AI-Helper는 부적절한 답변을 할 수 있습니다.