본 문서에서는 CIKM 2024 학회에 발표될 "Fast and Accurate PARAFAC2 Decomposition for Time Range Queries on Irregular Tensors" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
- Title : Fast and Accurate PARAFAC2 Decomposition for Time Range Queries on Irregular Tensors
- Authors: Jun-Gi Jang, Yong-chan Park, and U Kang
- Conference: ACM International Conference on Information and Knowledge Management (CIKM) 2024
Time Range Queries on Irregular Tensors
많은 실세계 데이터가 여러 축을 가지는 텐서로 표현될 수 있습니다. 특히, 최근 복잡한 환경에서 데이터가 생성됨에 따라 주식 데이터 및 교통량 데이터와 같은 많은 데이터들이 한 축이 불규칙한 불규칙 텐서로 표현될 수 있습니다. 주식 데이터를 예로 들면, 매일 (종목, 피처) 형태의 행렬을 얻어 (종목, 피처, 시간) 축을 가지는 3차원 텐서를 구성할 수 있습니다. 종목 축은 거래정지, 신규상장 등 다양한 이유로 인해 매일 그 수가 달라질 수 있으므로, 종목 축의 크기가 다른 불규칙 텐서로 표현됩니다.
불규칙 텐서는 행의 크기가 서로 다른 행렬들의 모음으로도 볼 수 있습니다. 시간 축을 가지는 매우 큰 불규칙 텐서가 주어질 때 다양한 시간 범위에 대한 분석을 수행하려는 요구가 증가하고 있으며, 이를 위해 불규칙 텐서 분해 방법인 PARAFAC2 분해 방법을 활용할 수 있습니다. PARAFAC2 분해는 불규칙성을 고려하여 텐서를 분해하는 방법으로, 분해 결과를 활용하여 이상 탐지, 클러스터링 등을 수행할 수 있습니다. 그림 1은 불규칙 텐서에 대한 시간 범위 쿼리 문제를 도식화한 것입니다.
그러나 기존 분해 방법은 주어진 텐서를 한 번 분해하는 것에 초점을 맞추고 있기 때문에, 다양한 시간 범위에 대해 효율적으로 분석하는 것에는 한계가 있습니다. 다시 말해, 시간 범위가 주어질 때마다 시간 범위에 속하는 부분 텐서를 PARAFAC2 분해를 통해 분해해야 합니다. 따라서, 기존 방법들은 여러 시간 범위를 분석함에 있어 매우 비효율적입니다.
 |
| 그림 1. 불규칙 텐서에 대한 시간 범위 쿼리 문제 개요. 시간 범위 쿼리와 불규칙 텐서가 주어지면 쿼리에 해당하는 하위 텐서에 대한 PARAFAC2 분해 결과를 찾고 이상 탐지 및 클러스터링을 포함한 실제 응용 프로그램에서 결과를 활용합니다. |
Proposed Method
본 논문이 제안하는 알고리즘 Repeat는 기존 PARAFAC2 분해 방법들과는 달리 효율적인 쿼리 응답을 위해, 쿼리가 주어지기 전 미리 주어진 텐서를 전처리하고, 쿼리가 주어질 때마다 전처리된 결과를 효과적으로 처리하여 PARAFAC2 결과를 효율적으로 얻습니다.
구체적으로, 본 논문은 전처리 단계와 쿼리 단계로 구성되어 있습니다. 전처리 단계에서는 쿼리가 주어지기 전 불규칙 텐서를 블록별로 나누고, 각 블록 텐서에 대해 PARAFAC2 분해를 수행하여 작은 요인 행렬들을 얻습니다. 그리고 쿼리 단계는 임의의 시간 범위 쿼리가 주어지면 시간 범위에 포함되는 전처리 결과들을 불러오고, 전처리 결과와 이를 효율적으로 다루는 계산식을 활용하여 최종 분해 결과를 얻습니다. 전처리 결과에 맞춘 새로운 계산식은 큰 중간 데이터의 생성을 피하면서도 빠르게 최종 결과를 계산합니다.
전처리 단계 (Preprocessing Phase)
먼저 전처리 단계에서는 그림 2와 같이 주어진 불규칙 텐서를 시간 축을 따라 블록별로 나누고, 각 블록 텐서에 대해 PARAFAC2 분해를 수행합니다. 예제에서는 4개의 행렬들의 모음인 불규칙 텐서를 시간 축을 따라 두 블록 텐서로 나누고, 각각의 블록 텐서에 대해 PARAFAC2 분해를 수행합니다. PARAFAC2 분해 결과는 입력 텐서보다 훨씬 작은 크기를 가지며, 시간 범위 쿼리들을 처리하기 전 한 번만 수행됩니다. 따라서, 전처리 결과들은 효율적인 쿼리 단계를 지원합니다.
 |
| 그림 2. 전처리 단계 |
쿼리 단계 (Query Phase)
쿼리 단계에서는 다양한 시간 범위에 대해 효율적으로 PARAFAC2 분해 결과를 계산합니다. 단순한 방법은 임의의 시간 범위가 주어지면, 해당 범위에 속하는 전처리 결과를 불러와 이를 텐서 형태로 복원하고, 복원된 불규칙 텐서를 PARAFAC2 분해 방법으로 분해합니다. 하지만, 복원된 불규칙 텐서는 기존 텐서와 크기가 동일하기 때문에 이 방법은 기존 PARAFAC2 방법들과 동일하게 매우 비효율적입니다. 본 논문은 그림 3과 같이 시간 범위에 대한 PARAFAC2 분해 결과를 효율적으로 계산하기 위해 텐서를 복원하는 계산을 피하고, 계산 순서를 신중히 정하고, 다양한 특성을 활용하여 전처리 결과들로부터 최종 결과를 효율적으로 계산합니다. 구체적으로, 열 단위 크로네커 곱(Kronecker Product)인 카트리-라오 곱(Khatri-Rao Product)과 행렬 곱셈으로 구성된 식을 재구성하는 혼합 곱셈 특성(Mixed Product Property)과 열 직교 행렬(Column Orthogonal Matrix)의 특성을 활용하여 효율적인 계산식을 유도합니다. 또한, 본 논문은 행의 크기는 크고 열의 크기는 작은 행렬들 간의 행렬 곱셈의 순서를 주의 깊게 정함으로써 큰 중간 데이터 생성 없이 효율적인 계산을 수행합니다
 |
| 그림 3. 쿼리 단계 |
Experiments
선행 기술과 비교하면, 본 논문이 제안하는 Repeat는 임의의 시간 범위에 대해 매우 효과적으로 PARAFAC2 분해 결과를 얻습니다. 여러 실세계 불규칙 텐서에서 시간 범위 쿼리에 대해 효율적으로 응답하는 것을 실험적으로 보였으며, 본 논문을 통해 다양한 실세계 응용을 수행할 수 있음도 보였습니다. 보다 자세한 실험 결과들은 논문에서 확인할 수 있습니다.
 |
| 그림 4. Repeat와 경쟁 기법의 속도 비교 실험 |
본 논문을 이용하면 다양한 실세계 데이터에 대한 특정 시간 범위 내의 분석을 진행할 수 있습니다. 아래 그림은 본 논문의 기법을 이용하여 각각 미국과 한국 주식 데이터의 연도 간 종가 유사도를 분석한 결과를 보여줍니다. 주식 데이터는 (종목, 피처, 시간) 축을 가지는 불규칙 텐서로 표현될 수 있습니다. 전처리 단계에서 이 불규칙 텐서를 전처리하고, 쿼리 단계에서는 2015년-2019년에 대응하는 시간 범위 쿼리들을 대해 효율적으로 PARAFAC2 분해 결과를 얻습니다. 그리고 각 연도별 종가에 대응하는 벡터들을 불러와 유사도를 계산하고 이를 분석할 수 있습니다. 이 외에도 분해 결과를 통해 다양한 응용을 수행할 수 있습니다.
 |
| 그림 5. 미국과 한국 주식 데이터에 대한 연도별 패턴 분석 |
Conclusion
본 문서에서는 CIKM 2024에 발표될 "Fast and Accurate PARAFAC2 Decomposition for Time Range Queries on Irregular Tensors" 논문을 소개하였습니다. 본 논문은 기존 PARAFAC2 분해 방법들과는 달리 효율적인 쿼리 응답을 위해, 쿼리가 주어지기 전 미리 주어진 텐서를 전처리하고, 쿼리가 주어질 때마다 전처리된 결과를 효과적으로 처리하여 PARAFAC2 결과를 효율적으로 얻습니다.
본 논문은 시간 축을 가지는 불규칙한 텐서가 주어질 때, 사용자가 관심을 가질만한 다양한 시간 범위에 대해 효율적인 분석을 가능하게 합니다. 임의의 시간 범위에 대해 불규칙 텐서 분해 결과를 얻고, 이 결과를 활용하여 해당 시간 범위에 대한 클러스터링, 이상 탐지 등 다양한 응용을 수행할 수 있습니다. 본 논문을 활용하여 교통량 데이터에 대한 월별 패턴 분석이나, 주별 패턴 분석을 수행할 수도 있고, 주식 데이터에서도 유사하게 특정 이벤트 범위에 대한 분석도 수행할 수 있습니다. 논문에 대한 자세한 정보는 [링크]에서 확인할 수 있습니다.
