How can we analyze large-scale real-world data with various attributes?
Many real-world data (e.g., network traffic logs, web data, social networks, knowledge bases, and sensor streams) with multiple attributes are represented as multi-dimensional arrays, called tensors.
For analyzing a tensor, tensor decompositions are widely used in many data mining applications: correlation analysis on sensor streams, latent semantic indexing on DBLP publication data, multi-aspect forensics on network data, network discovery on fMRI data, to name a few.
However, current tensor decomposition methods do not scale to large real-world tensors with millions of rows and columns and `fibers’.
In this thesis, we propose HaTen2, a distributed method for large-scale tensor decompositions that runs on the MapReduce framework.
Our careful design and implementation of HaTen2 dramatically reduce the size of intermediate data, and the number of jobs leading to achieving high scalability compared with the state-of-the-art method.
Thanks to HaTen2, we analyze big real-world tensors that can not be handled by the current state of the art, and discover hidden concepts.
네트워크 침입 로그 데이터(예: 출발지 IP, 목적지 IP, 포트번호, 시간)와 같이 다양한 특성을 지닌 대용량의 실제 세계 데이터에서 어떻게 유용한 패턴과 비정상 특성(예: 포트 스캐닝 공격, DDoS 공격 등)을 찾을 수 있을까? 텐서(tensor)는 2차원 배열(행렬)을 넘어선 다차원 배열로써, 실제 세계의 다차원의 데이터를 모델링하기 적합하기 때문에 소셜 네트워크 데이터, 웹 데이터, 네트워크 트래픽 데이터, 지식베이스 데이터 등과 같은 다양한 실제 세계의 데이터를 분석하는데 널리 활용되어왔다. 대표적인 텐서 분석 방법으로는, 텐서를 희소한 벡터들의 외적의 합으로 분해하여 데이터의 연관 관계를 살피는 텐서 분해 방법이 주로 사용된다. 그러나 기존의 텐서 분해 알고리즘은 확장성이 떨어지기 때문에 실제 세계의 대용량 텐서 데이터를 분석하기 어려웠다. 본 연구는 이러한 기존 방법의 문제점에서 출발하여, 실제 세계의 대용량 텐서 데이터를 분석하기 위한 맵리듀스 기반의 확장성이 높은 텐서 분해 알고리즘을 제안한다. 본 연구에서 제안한 HaTen2는 대용량 Tucker와 PARAFAC 텐서 분해 알고리즘 및 Tucker와 PARAFAC 기반의 비음 텐서 분해 알고리즘의 연산을 하나의 맵리듀스 기반의 프레임워크로 통합하였고, 효율적인 알고리즘 설계로 연산 시 중간 데이터의 크기와 실행시간을 최소화시켰다. 그리하여 제안한 HaTen2는 기존의 방법보다 최대 1000배 큰 크기의 텐서를 분해할 수 있을 뿐 아니라, 사용되는 머신의 수에 거의 선형적으로 비례하는 확장성을 갖추었다. 또한, 제안한 알고리즘을 지식 베이스 텐서와 네트워크 트래픽 로그, 통화 내역 등의 실제 데이터에 적용하여 숨겨진 개념 그룹과 비정상 공격 행위, 텔레마케터 등을 분석 해내었다.
