How can we find interesting patterns in data streams with limited memory spaces? This question has arisen in various fields including data mining, database, machine learning, etc. A data steam is a model where each data is given one by one over time. For example, many real world data such as data generated by sensors, SNS messages, network traffic, phone call history, and financial transactions are given in the stream fashion. One of the most important characteristics is that those data are generated constantly and infinitely even at a high speed. Consequently, batch analysis, which is done after gathering data, is not suitable, and online analysis is necessarily required. Moreover, the infiniteness implies that storing all of the given data is impossible. Thus, efficiently using limited spaces and maintaining analysis results up-to-date are crucial in stream mining.
In this dissertation, we tackle two important problems on data streams. The first problem is to discover recently frequent items in data streams, which is a fundamental problem in stream mining. More precisely, we propose an algorithm for tracking top-$k$ recently frequent items in data streams with $O(k)$ memory spaces. We first explain a motivating algorithm TwSample based on exhaustive item sampling which theoretically guarantees accuracy in expectation. Then, we propose the main algorithm TwMinSwap which is a deterministic variation of TwSample. Our experimental results show that TwMinSwap outperforms other competing methods in accuracy and memory usage with fast running time. Also applying TwMinSwap to real data streams, we discover several interesting patterns.
The second problem is to estimate the number of local triangles for every node in a graph stream, which has many applications like anomaly detection, web mining, etc. For this problem, we propose MASCOT, a memory-efficient and accurate algorithm for local triangle estimation in graph streams. To develop MASCOT, we first give two naive local triangle counting algorithms based on edge sampling: MASCOT-C and MASCOT-A. Compared with MASCOT-C, MASCOT-A has lower variance while it may use undesirably many memory spaces. MASCOT achieves the advantages of memory usage and accuracy of MASCOT-C and MASCOT-A, respectively. Through experiments, we demonstrate that MASCOT provides the best performance in accuracy compared with not only the two naive algorithms but also the existing method. Also we report several anomalous patterns discovered by applying MASCOT to real graph streams.
어떻게 제한된 메모리만을 이용해 데이터 스트림에서 패턴을 찾을 수 있을까? 이 문제는 데이터 마이닝, 데이터베이스, 기계 학습 등 다양한 분야의 핵심적인 과제이다. 데이터 스트림은 각각의 데이터가 시간이 지남에 따라 하나씩 주어지는 데이터 모델이다. 많은 실세계 데이터들이 스트림 형태를 띄는데, 예를 들면, 센서에서 생성되는 데이터, 소셜 네트워크 서비스에서 발생하는 메시지, 네트워크 트래픽, 통화 기록, 금융 거래 내역 등이 있다. 이러한 데이터들의 가장 중요한 특징 중 하나는 꾸준히, 무한히 그리고 빠른 속도로 생성된다는 것이다. 그 결과, 데이터를 모두 수집한 후 이루어지는 일괄 분석(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를 실세계 그래프 스트림에 적용하여 발견한 몇 가지 이상 패턴에 대해서도 논의한다.