본 문서에서는 CIKM 2018에서 발표된 "Zoom-SVD: Fast and Memory Efficient Method for Extracting Key Patterns in an Arbitrary Time Range" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
- Title: Zoom-SVD: Fast and Memory Efficient Method for Extracting Key Patterns in an Arbitrary Time Range
- Authors: Jun-Gi Jang, Dongjin Choi, Jinhong Jung, and U Kang
- Conference: 27th ACM International Conference on Information and Knowledge Management (CIKM 2018)
Singular Value Decomposition
센서 데이터, 기상 데이터 등과 같이 여러 시계열 데이터 (multiple time series data)는 행이 시간 축, 열이 속성 (예를 들어, 센서 타입) 축인 행렬들로 표현 될 수 있습니다. Singular Value Decomposition (SVD)는 행렬로 표현된 실세계 데이터를 분석하는 가장 유명한 도구 중 하나입니다. SVD는 차원 축소, 클러스터링, 주성분 분석 등 데이터 마이닝 응용에서 많이 활용되고 있습니다. 아래 그림은 SVD 방식에 대한 예제를 나타냅니다.
그림 1. Singular Value Decomposition (SVD) - 출처[link]
SVD는 주어진 행렬 A를 세 개의 행렬들 U, 𝝨, V로 분해합니다. 행렬 U와 V는 직교행렬이며, 𝝨는 대각행렬이고, 대각의 값은 내림차순으로 정렬되어 있습니다. 실세계 데이터는 중복이 많으며, 저차원 구조를 가지고 있으므로 작은 행렬들로 입력 데이터 행렬 A를 표현할 수 있습니다.
Problem Definition
해당 논문의 목표는 임의의 시간 범위에서 얻은 여러 시계열 데이터를 분석하고자 합니다.
해당 논문에서 풀고자하는 공식적인 문제 정의는 다음과 같습니다.
- Given: a time range, and multiple time series data represented by a matrix A.
- Find: the SVD result of the sub-matrix of A in the time range quickly, without storing all of A. The SVD result includes left singular vectors, singular values, and right singular vectors.
SVD로 인해 분해된 결과를 이용하여 주어진 시간 범위에 대한 분석을 수행할 수 있습니다. 예를 들어, 행렬 U를 이용하여 주요 시간 패턴들을 분석할 수 있으며, V를 이용하여 속성들 간의 클러스터링을 수행할 수 있습니다.
Limitations of Existing Methods
임의의 시간 범위에 대해 분석할 수 있는 기존 방법들은 기본 SVD (Standard SVD)와 증분 SVD (Incremental SVD)가 있습니다. 하지만, 두 가지 접근 방법 모두 임의로 주어지는 시간 범위에 대하여 분석하기에는 실용적이지 않습니다.
기본 SVD는 임의의 시간 범위에서 얻은 데이터를 가져와 행렬로 나타내고, 이 행렬에 대해서 SVD를 수행합니다. 해당 방식을 사용하기 위해서는 시간에 따라 들어오는 모든 데이터를 저장해놓아야 합니다. 또한, 시간 범위 쿼리가 주어졌을 때 쿼리에 포함되는 값들을 행렬로 표현하고 SVD를 주어진 행렬로부터 계산을 해야하기 때문에, 시간 및 공간적으로 매우 비효율적입니다.
또한, 증분 SVD는 이름에서와 같이 시간에 따라 새로 들어온 데이터를 이전 시간에 계산된 결과들에 업데이트를 하는 방식입니다. 해당 방식은 새로 들어온 데이터에 대해서만 업데이트를 하는 방식이므로, 임의의 시간 범위에 대처해야하는 현재 문제 정의에는 적절하지 않습니다.
어떻게 해야 임의의 시간 범위에 대한 분석을 효율적으로 할 수 있을까요?
Proposed Method
그림 2. Zoom-SVD 개요.
본 논문에서는 주어진 임의의 시간 범위에 대한 SVD를 빠르고 메모리 효율적으로 계산하는 Zoom-SVD 방법을 제안합니다. Zoom-SVD는 시간에 따라 들어오는 데이터를 효율적으로 압축 저장하며, 임의의 시간 범위 쿼리가 주어지면 압축 저장된 결과들을 이용하여 효율적으로 쿼리를 처리합니다. 그림 2에서와 같이 Zoom-SVD는 Storage phase와 Query phase 두 단계로 구성되어 있습니다.
- 저장 단계 (Storage Phase): 시간에 따라 들어오는 데이터를 블록 단위로 압축 저장하는 단계. 블록 단위로 처리함으로써 새로 들어온 데이터를 빠르게 업데이트할 수 있음. 또한, Query phase에서 짧은 시간 범위와 긴 시간 범위 쿼리 모두를 효율적으로 처리할 수 있음.
- 쿼리 단계 (Query Phase): 주어진 임의의 시간 쿼리에 대해서 저장 단계에서 저장된 결과들을 이용하여 효율적으로 쿼리를 처리함. 저장 단계에서 얻은 압축된 결과를 입력 행렬 형태로 복원시키지 않고, 블록 단위로 저장된 결과들을 잘 꿰어 연결함으로써 임의의 시간 범위 쿼리를 시간 및 공간 효율적으로 처리함.
본 문서에서는 Zoom-SVD에 대한 핵심적인 내용만 다루며, 구체적인 수식 및 내용은 논문을 참고하시면 됩니다.
Storage Phase
저장단계에서는 시간에 따라 새로 들어오는 데이터를 시간 블록 단위로 효율적으로 압축 저장합니다. 시간마다 압축 저장하며, 입력 데이터는 버림으로써 공간 효율성을 증대시킵니다. 간단한 방법은 증분 SVD (Incremental SVD)를 사용하는 것이나, 새로 들어온 데이터를 하나의 큰 SVD 결과에 업데이트해야하고 이는 임의의 시간 범위를 처리하는 현 문제에서는 매우 비효율적입니다. 그 이유로는, 시간이 지남에 따라 업데이트 비용이 늘어나고, 다양한 길이의 쿼리를 처리하기 어렵기 때문입니다. 그러므로 Zoom-SVD는 그림2 왼쪽에서와 같이 저장단계에서 1) 새로 들어오는 데이터를 업데이트하고, 2) 처리한 데이터가 주어진 블록 크기를 만족하면 해당 블록을 저장하고 새로운 블록을 생성, 업데이트합니다. 각 블록들은 입력 데이터에 비해 크기가 작으며, 입력 데이터는 업데이트 후 버림으로써 저장 효율성을 확보합니다.
Query Phase
쿼리 단계에서는 주어진 시간 범위에 대해 저장단계에서 압축된 결과를 활용하여 효율적으로 SVD를 계산합니다. 간단한 방법은 주어진 쿼리에 대해서 저장된 결과를 하나의 큰 행렬 형태로 복구하고, 행렬에 대해서 SVD를 수행할 수 있습니다. 그러나, 이러한 접근방법은 큰 행렬을 다뤄야 하기 때문에 매우 비효율적입니다. 그래서, 쿼리 단계에서는 Partial-SVD와 Stitch-SVD 두가지 부분 모듈을 사용하여 쿼리를 효율적으로 처리합니다.
Partial-SVD. 해당 부분 모듈은 시작 시간이 포함되는 블록과 끝 시간이 포함되는 블록에서 주어진 시간 범위에 포함되는 부분의 SVD 결과들을 추출합니다. 그림 3은 Partial-SVD를 나타냅니다. 시작 시간과 끝 시간은 블록의 중간에 위치할 수 있으며, 시간 범위에 포함되지 않는 부분을 제거하고 남은 부분에 대해서 SVD 형태로 변환시킵니다. 이 때, 입력 행렬 형태로 복구시키지 않고 SVD 형태로 변환시키기 때문에 계산 효율성이 높습니다.
그림 3. Partial-SVD.
Stitch-SVD. 해당 부분 모듈은 그림 2의 오른쪽 그림에서와 같이 시간 범위에 포함되어 있는 블록들의 SVD 결과를 이용하여 하나의 큰 SVD 결과로 만듭니다. Stitch-SVD는 모든 블록 결과들이 SVD 형태인 것과 각각의 U, V가 직교행렬인 특성을 활용합니다. 이 특성들을 활용하면 하나의 입력 행렬 형태로 복구하지 않은 채 SVD 결과를 얻을 수 있기 때문에 빠르고 메모리 효율적으로 임의의 시간 범위에 대한 SVD 결과를 얻을 수 있습니다.
Experimental Results
아래 실험 결과들은 제안하는 방법인 Zoom-SVD가 주어진 임의의 시간 범위에 대해 빠르고 메모리 효율적으로 계산하는 것을 보여줍니다.
그림 4. 계산 시간 비교
그림 4는 세가지 여러 시계열 데이터에 대해서 제안하는 방법인 Zoom-SVD와 경쟁 방법들 간의 계산 시간을 비교합니다. 10,000에서 400,000까지 다양한 쿼리 길이에 대해 실험을 진행하였습니다. 그림4에서 보시는 것과 같이 제안하는 방법인 Zoom-SVD가 경쟁 방법들에 비해 최소 9.6배에서 최대 15배 빠르게 쿼리를 처리하였습니다. 또한, 모든 쿼리 길이에 대해서 Zoom-SVD가 가장 빠르게 처리하는 것을 볼 수가 있습니다.
그림 5. 공간 비용 비교
그림 5는 세가지 여러 시계열 데이터에 대해서 Zoom-SVD의 공간 비용을 보여줍니다. Zoom-SVD는 기존 데이터를 사용할 때보다 최대 15배이상 적은 양의 메모리를 사용하여 쿼리를 처리할 수 있음을 보여주고 있습니다.
Conclusion
본 문서에서는 CIKM 2018에서 발표된 "Zoom-SVD: Fast and Memory Efficient Method for Extracting Key Patterns in an Arbitrary Time Range" 논문을 소개하였습니다. 해당 논문은 임의의 시간 범위에 대한 패턴을 효율적으로 찾는 방법인 Zoom-SVD를 제안하였습니다. 실험 결과를 통해서 제안하는 방법이 기존 방법들보다 효율적임을 보였습니다. Zoom-SVD 기법은 특정 시간 범위에서 발생하는 이벤트를 분석하거나, 주기적인 패턴을 비교 분석할 때 효율적으로 사용할 수 있습니다. 예를 들어, 기상 데이터에서 월별 패턴을 분석하거나, 이상 기온과 같은 이벤트가 발생했을 때 이벤트 전후 패턴을 분석해 볼 수 있습니다. 제안한 Zoom-SVD를 통해 사용자마다 원하는 시간 범위를 매우 효율적으로 분석할 수 있음에 따라, 다양한 여러 시계열 데이터에서 미처 알지 못했던 독특한 시간 범위나 특정 시간 범위내에만 존재하는 숨겨진 정보들을 찾아낼 수 있을 것이라 기대합니다. 자세한 내용은 해당 링크에서 확인하실 수 있습니다.