Memory-efficient real-time data stream mining: discovering recently frequent Items and estimating local triangles

Abstract

어떻게 제한된 메모리만을 이용해 데이터 스트림에서 패턴을 찾을 수 있을까? 이 문제는 데이터 마이닝, 데이터베이스, 기계 학습 등 다양한 분야의 핵심적인 과제이다. 데이터 스트림은 각각의 데이터가 시간이 지남에 따라 하나씩 주어지는 데이터 모델이다. 많은 실세계 데이터들이 스트림 형태를 띄는데, 예를 들면, 센서에서 생성되는 데이터, 소셜 네트워크 서비스에서 발생하는 메시지, 네트워크 트래픽, 통화 기록, 금융 거래 내역 등이 있다. 이러한 데이터들의 가장 중요한 특징 중 하나는 꾸준히, 무한히 그리고 빠른 속도로 생성된다는 것이다. 그 결과, 데이터를 모두 수집한 후 이루어지는 일괄 분석(batch analysis)은 적합하지 않고, 온라인 분석이 필수적이다. 또한, 무한히 생성된다는 것은 주어진 데이터를 모두 저장할 수 없다는 것을 의미한다. 따라서, 데이터 스트림 마이닝에서는 효율적으로 메모리 공간을 활용하면서 분석 결과를 항상 최신으로 유지하는 것이 핵심이 된다. 본 학위 논문에서는 데이터 스트림에 대한 두 가지 중요한 문제를 다룬다. 첫 번째 문제는 데이터 스트림에서 최신 빈발 아이템을 탐지하는 것으로써, 이는 데이터 스트림 마이닝에서 가장 기본적이면서도 핵심적인 문제이다. 구체적으로, 본 논문에서는 $O(k)$의 메모리 공간만을 사용해 상위 $k$개의 최신 빈발 아이템을 추적하는 알고리즘을 제안한다. 먼저, 아이템 샘플링을 이용한 확률적 알고리즘인 TwSample을 제안한다. 이는 기대값으로 정확도를 보장한다. 이의 결정론적 변형을 통해 본 논문에서는 최종적으로 TwMinSwap을 제안한다. 본 논문의 실험 결과에 따르면 TwMinSwap은 기존의 기법들에 비해 메모리는 적게 쓰면서 더 좋은 정확도를 보여 준다. 또한 TwMinSwap을 실세계 데이터 스트림에 적용해 흥미로운 패턴을 발견할 수 있음을 보인다. 두 번째 문제는 그래프 스트림에서 모든 정점들에 대해 로컬 삼각형 개수를 추정하는 것이다. 이는 이상 현상 탐지, 웹 마이닝 등 실세계에서 다양한 응용을 갖는다. 이 문제를 해결하기 위해 본 논문에서는 공간 효율적이면서도 정확성을 갖는 로컬 삼각형 추정 기법인 MASCOT를 제안한다. MASCOT를 제안하기에 앞서, 간선 샘플링을 이용한 기본적인 로컬 삼각형 추정 알고리즘인 MASCOT-C와 MASCOT-A를 설명한다. MASCOT-C와 비교해서 MASCOT-A는 낮은 분산을 갖는 반면 더 많은 메모리 공간을 요구한다. MASCOT는 두 기본적인 기법의 장점을 모두 갖는다. MASCOT-C 만큼의 메모리 공간을 사용하면서, MASCOT-A와 같은 분산 상한을 갖는다. 실험을 통해 본 논문에서는 MASCOT가 두 기본 기법들뿐만 아니라 기존 기법과 비교해서도 더 좋은 정확도를 갖음을 보인다. 또한 MASCOT를 실세계 그래프 스트림에 적용하여 발견한 몇 가지 이상 패턴에 대해서도 논의한다.