Fast Fourier Transform for Data Mining: Theory and Algorithms = 데이터 마이닝을 위한 고속 푸리에 변환: 이론과 알고리즘|RISS 상세보기

다국어 초록 (Multilingual Abstract)

Fast Fourier transform (FFT) is a foundational primitive in data mining, supporting a broad range of pipelines for feature extraction, filtering, compression, and large-scale learning.
However, modern workloads, including high-dimensional signals, large-scale tensors, and continuously arriving observations, often exhibit strong frequency-domain structure in which only a small, structured portion of the spectrum is informative.
In such settings, conventional practice still relies on full transforms followed by discarding most coefficients, and in streaming scenarios it frequently resorts to full or frequent retraining, incurring unnecessary computational cost and limiting responsiveness as data grow.

This thesis develops FFT-centric theory and algorithms that explicitly exploit frequency-domain structure to scale data mining across both offline and online regimes.
The proposed partial-spectrum computation directly evaluates task-relevant Fourier components with provable, user-controlled approximation error, eliminating the overhead of computing unused coefficients.
We further enable rapid, automatic accuracy-speed reconfiguration in multidimensional settings through an efficient optimization formulation, making partial Fourier computation practical under changing data shapes and requirements.
Beyond spectral access, this thesis develops frequency-informed learning mechanisms for data mining: lightweight, invertible frequency-domain transformations are learned to align multi-way data and reduce the effective rank for downstream tensor factorization, and an online coupled factorization framework is presented to support real-time updates via frequency regularization and adaptive forgetting rather than full retraining.

Experiments on diverse real and synthetic datasets demonstrate consistent and substantial acceleration, achieving up to 19x speedup while preserving accuracy and improving reconstruction quality, compression efficiency, and anomaly detection performance under practical budgets.
Collectively, the results show that FFT can serve not only as a fast transform, but as a scalable design principle for approximation, representation, and continuous learning in data mining systems.

번역하기

국문 초록 (Abstract)

고속 푸리에 변환(FFT)은 데이터 마이닝의 핵심적 기반 연산으로서, 특징 추출, 필터링, 압축, 대규모 학습 등 다양한 파이프라인을 뒷받침한다. 그러나 고차원 신호, 대규모 텐서, 연속적으로 유입되는 관측치를 포함하는 현대의 워크로드는 주파수 영역에서 특징적인 구조를 보이는 경우가 많으며, 이때 정보가 담긴 스펙트럼은 전체 중 일부의 작고 구조화된 구간에만 집중되는 경향이 있다. 그럼에도 기존 관행은 여전히 전체 푸리에 변환을 수행한 뒤 대부분의 계수를 폐기하는 방식에 의존하며, 특히 스트리밍 환경에서는 빈번한 재학습에 의존하는 경우가 많아 불필요한 계산 비용을 초래하고 데이터 규모 증가에 따라 대응성을 저하시킨다.

본 학위 논문에서는 오프라인과 온라인 두 환경을 아우르는 확장 가능한 데이터 마이닝을 위해, 주파수 분석을 핵심 목표로 삼는 FFT 중심의 이론과 알고리즘을 제시한다. 먼저, 사용되지 않는 계수를 계산하는 비용을 피하기 위해 과업에 필요한 푸리에 성분만을 직접 평가하는 원리적 계산 기법을 개발하고, 사용자가 제어 가능한 근사 오차에 대한 엄밀한 보장을 제공한다. 또한 온라인 환경에서 데이터의 형태와 요구 조건이 변화하더라도 부분 푸리에 계산을 실용적으로 적용할 수 있도록, 효율적인 최적화 알고리즘을 통해 정확도-속도 간 설정을 빠르고 자동적으로 재구성하는 방법을 제안한다. 더 나아가 스펙트럼 접근을 넘어, 데이터 마이닝을 위한 주파수 기반 학습 메커니즘을 발전시킨다. 구체적으로, 경량이면서 가역적인 주파수 영역 변환을 학습하여 다중 모드 데이터의 정렬을 유도하고, 이후 텐서 분해를 위한 유효 랭크를 감소시키는 기법을 제시한다. 또한 전체 재학습 대신 주파수 정규화와 적응형 망각에 기반한 실시간 업데이트를 지원하는 온라인 결합 분해 프레임워크를 제안한다.

다양한 실제 및 합성 데이터셋에 대한 실험 결과, 제안 방법은 정확도를 유지하면서도 일관되고 유의미한 속도 향상을 달성하였으며, 동일 정확도 기준 최대 19배의 가속을 확인하였다. 또한 현실적인 자원 제약 하에서 재구성 품질, 압축 효율, 이상 탐지 성능을 개선함을 확인하였다. 종합하면, FFT는 단지 빠른 변환 연산에 그치지 않고, 데이터 마이닝 시스템에서 근사, 표현, 연속 학습을 위한 확장 가능한 설계 원리로 기능할 수 있음을 보여준다.

번역하기

고속 푸리에 변환(FFT)은 데이터 마이닝의 핵심적 기반 연산으로서, 특징 추출, 필터링, 압축, 대규모 학습 등 다양한 파이프라인을 뒷받침한다. 그러나 고차원 신호, 대규모 텐서, 연속적으로...

목차 (Table of Contents)