시계열 데이터의 순열 엔트로피에 따른 순위패턴매칭 알고리즘 성능 비교
Performance Comparison of Order-preserving Pattern Matching Algorithms According to Permutation Entropy of Time Series Data
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
길이가 같은 두 문자열에서 같은 위치에 있는 문자의 상대적인 순위가 모든 위치에서 일치하면 두 문자열은 순위동형이라 한다. 순위패턴매칭문제는 대소 비교가 가능한 텍스트 와 패턴 가 주어졌을 때, 와 순위동형인 의 모든 부분문자열의 위치를 찾는 문제이며 시계열 데이터 분석에 활용될 수 있다. 본 논문에서는 다양한 시계열 데이터에 대한 순열 엔트로피를 계산하고, 각 데이터별로 순열 엔트로피 분포에 따른 순위패턴매칭 알고리즘들의 성능을 비교한다.
Abstract
Two strings of the same length are called order-isomorphic if the relative order of characters at the same position is identical for all positions. The order-preserving pattern matching problem is finding the positions of all substrings in text that are order-isomorphic to pattern . This problem can be applied in time series data analysis. In this paper, we compute the permutation entropy for various time series data and compare the performance of order-preserving pattern matching algorithms based on the permutation entropy distribution for each dataset.
참고문헌 (9)
- J. Kim, "Order-preserving matching", Theoretical Computer Science, 525, pp.68~79 (2014)
- M. Kubica, "A linear time algorithm for consecutive permutation pattern matching", Information Processing Letters, 113(12), pp.430~433 (2013)
- S. Cho, "A fast algorithm for order-preserving pattern matching", Information Processing Letters, 115(2), pp.397~402 (2015)
- T. Chhabra, "A filtration method for order-preserving matching", Information Processing Letters, 116(2), pp.71~74 (2016)
- Y. Kim, "An Order-Preserving Pattern Matching Algorithm based on the Horspool Algorithm using Binary Encoding", Proc. of the KIISE Korea Software Congress, pp.2112~2114 (2018)
- S. J. Lee, "A Method of Detecting Arrhythmia based on Order-preserving Pattern Matching using Periodicity Analysis of ECG Data", Proc. of the KIISE Korea Software Congress, pp.1224~1226 (2022)
- S. H. Lee, "Performance Comparison of Order-preserving Pattern Matching Algorithms by Permutation Entropy", Proc. of the KIISE Korea Software Congress, pp.1599~1601 (2020)
- C. Bandt, "Permutation entropy : a natural complexity measure for time series", Physical review letters, 88(17), pp.174102~ (2002)
- Julien Herzen, "Darts : User-Friendly Modern Machine Learning for Time Series", JMLR, 23(124), pp.1~6 (2022)