Recently, the advancement of network technologies for cloud computing, Internet of Things, and the 5G mobile communication is combined with the advancement of hardware technologies for semiconductors and sensors, and they together facilitate the collection, management, and processing of data streams generated in real time. As a result, there has been growing needs for technologies for rapid acquisition of valuable information from real-time data streams in various industries. Particularly, outlier detection techniques for finding abnormal data points that deviate significantly from normal data points are widely used in many applications, such as finance, manufacturing, healthcare, etc. This dissertation research aims to detect various types of outliers with high accuracy and low latency, mainly by preventing redundant updates incurred by the existing algorithms. There are two representative outlier detection approaches, similarity-based and model-based; the former approach measures the similarity between data points, whereas the latter approach learns parameters to explain the properties of data points. This dissertation addresses two main challenges in these outlier detection approaches with sliding windows: immediacy and complexity. The immediacy refers to the need for fast detection of outlier while continuously updating similarities between data points in sliding windows or updating a model to reflect the properties of data points. The complexity refers to differing types and related accuracy criteria of outliers, such as global, local, and high-dimensional; these each pose different constraints and objectives of outlier detection performance. Based on similarity measures and models suitable for each type of outlier, this dissertation presents four different studies of efficient updates of the similarities and models. The first study proposes an algorithm NETS, which implements a set-based update of distance-based similarity to reduce redundant computations; it detected global outliers 17 times faster on average than state-of-the-art algorithms. The second study proposes an algorithm MDUAL, which processes multiple and dynamic distance-based outlier detection queries by exploiting the duality of data grouping and query grouping; it detected global outliers 217 times faster on average than state-of-the-art algorithms. The third study proposes an algorithm STARE, which uses density-based similarity to detect local outliers efficiently by employing stationary region skipping; it detected local outliers 11 times faster on average than state-of-the-art algorithms. The fourth study proposes a deep learning model-based outlier detection framework ARCUS, which uses a model pooling approach to detect high-dimensional outliers that cannot be easily identified by comparing similarities; it demonstrated higher accuracy and efficiency than state-of-the-art algorithms. This dissertation is expected to bring great values to many real-world applications by resolving the immediacy and complexity challenges of outlier detection in a data stream.
최근 클라우드 컴퓨팅, 사물 인터넷, 5세대 이동통신과 같은 네트워크 기술의 발전과 반도체 및 센서와 같은 하드웨어 기술의 발전이 함께 맞물리며 실시간으로 발생하는 데이터 스트림을 손쉽게 수집, 관리, 처리할 수 있는 기술이 널리 보급되고 있다. 이로 인해 다양한 산업 분야에서 실시간 데이터 스트림으로부터 가치 있는 정보를 신속하게 얻어낼 수 있는 기술에 대한 수요가 커지고 있다. 특히 정상 데이터의 범위에서 벗어나는 데이터를 찾아내는 이상치 탐지 기술은 금융, 제조, 의료 등 여러 응용 분야에서 널리 활용되고 있다. 본 연구에서는 기존 이상치 탐지 방법들이 불필요하게 수행하는 갱신 연산을 방지함으로써 보다 빠르고 정확하게 다양한 종류의 이상치 탐지를 가능케 하고자 한다. 대표적인 이상치 탐지 방법으로 데이터 간의 유사 정도를 판단하는 유사도 기반 탐지 방법과 정상 데이터를 표현하는 매개변수를 학습하는 모델 기반 탐지 방법이 존재한다. 본 연구에서는 슬라이딩 윈도우에서 유사도 및 모델 기반 이상치 탐지를 수행하는데 존재하는 두 가지 중요 도전 과제를 해결하고자 한다. 첫째는 이상치 탐지의 실시간성으로 윈도우 내 데이터들의 유사도를 지속해서 갱신하거나 그 데이터들의 특성을 잘 반영하는 모델을 지속적으로 갱신하며 이상치를 빠르게 탐지할 수 있어야 한다. 둘째는 이상치 탐지의 복잡성으로 전역 이상치, 지역 이상치, 그리고 고차원 이상치 등 각기 다른 특성과 정확도 기준을 지니는 이상치를 정확하게 탐지하기 위해 그에 맞는 이상치 탐지 조건들과 성능 목적을 만족하여야 한다. 본 연구에서는 각 이상치 특성에 맞는 유사도 또는 모델 기반 이상치 탐지 방법을 기본으로 하여, 데이터 스트림의 특성을 고려한 효율적인 유사도 및 모델 갱신 방법 네 가지를 제안한다. 첫 번째 연구에서는 거리 기반 유사도를 집합 기반으로 갱신하는 방법 NETS를 제안하여 기존 최첨단 방법에 비해 평균 17배 빠른 속도로 정확하게 전역 이상치를 탐지한다. 두 번째 연구에서는 거리 기반 유사도를 정의하는 이상치 탐지 질의들이 복수개가 존재하며 동적으로 변화하는 상황에서 데이터 그룹화와 질의 그룹화의 이중성을 활용한 방법 MDUAL을 제안하여 기존 최첨단 방법 대비 평균 218배 빠른 속도로 정확하게 전역 이상치를 탐지한다. 세 번째 연구에서는 밀도 기반 유사도를 이용하여 국소 지역상에서만 구분이 가능한 지역 이상치를 탐지하는 방법 STARE를 제안하며, 이때 불변 지역 생략 기법을 통해 기존 최첨단 방법 대비 평균 11배가량 빠른 속도로 정확하게 지역 이상치를 탐지한다. 마지막 네 번째 연구에서는 유사도 기반으로 탐지가 어려운 고차원 이상치를 잘 구분하기 위해 딥러닝 모델 기반의 이상치 탐지 프레임워크 ARCUS를 제안하며, 모델 풀링 기법을 통해 기존 최첨단 방법 대비 높은 효율성 및 정확도를 얻는다. 본 연구를 통해 데이터 스트림에서의 이상치 탐지의 도전과제들인 실시간성과 복잡성을 효과적으로 해결하여 여러 실세계 응용 분야에 더욱 큰 가치를 가져다줄 수 있을 것으로 기대한다.
