PAA 기반 SAX 변환을 통한 Time Series 차원 축소 및 Lower Bound 거리 측정 구현

Review: A Symbolic Representation of Time Series, with Implications for Streaming Algorithms

Alex Towell2026년 6월 7일9분advanced

AI 요약

Context

고차원 Real-valued Time Series 데이터의 방대한 차원으로 인한 $\mathcal{O}(cn)$ 복잡도의 연산 병목 발생. 기존 Symbolic Representation 방식은 차원 축소가 불가능하며, 원본 데이터와의 거리 측정 시 Lower Bound를 보장하지 못해 데이터 마이닝 활용도가 낮음.

Technical Solution

PAA(Piecewise Aggregate Approximation)를 중간 단계로 도입하여 원본 데이터의 차원을 효과적으로 축소
정규 분포 특성을 활용한 등확률 구간 분할 기반의 Nominalization 과정으로 PAA 계수를 문자열로 변환
SAX $\rightarrow$ PAA $\rightarrow$ Original Time Series로 이어지는 전이적 관계로 원본 데이터 거리의 Lower Bound를 수학적으로 증명
$\text{MIN_DIST}$ 함수와 Lookup Table을 결합하여 Euclidean Distance 계산 비용을 상수로 최적화
Run-length Encoding 적용이 가능한 Symbolic Sequence 구조 설계를 통한 메모리 사용량 최적화

실천 포인트

- 고차원 시계열 데이터의 유사도 검색 시, 전수 조사 전 Lower Bound를 보장하는 요약 표현식(SAX)을 통한 후보군 필터링 적용 검토 - 데이터의 분포 특성(예: Normal Distribution)을 활용한 구간 최적화로 데이터 손실 최소화 및 표현력 극대화 - 복잡한 거리 연산을 Pre-computed Lookup Table로 대체하여 런타임 CPU 오버헤드 제거

태그

#Dimensionality Reduction #Time Series #SAX #Lower Bound #PAA

원문 읽기