0. Abstract
- 스트리밍 데이터의 이상 탐지는 전통적인 방법들로는 처리하기 어려운 복잡성을 가지고 있음
- 스트리밍 데이터의 주요 도전 과제에 대응하기 위해 8개의 최신 알고리즘을 테스트하고 평가
- 연구 결과는 알고리즘 선택에 있어 데이터의 지역성, 상대성, 개념 변화와 같은 특성이 중요한 영향을 미친다는 것을 보여줌
- locality
- 이상치가 지역적 맥락에 상대적인지 여부)
- relativeness
- 과거 데이터가 이상치를 정의하는지 여부
- concept drift
- 그 강도와 빈도
- locality
- 실제 환경에서 스트리밍 데이터의 이상 탐지를 위한 중요한 발견을 제공
1. Introduction
[1] 데이터 스트림 vs 다변량 시계열 데이터
데이터 스트림은 다변량 시계열 데이터와 밀접한 관련이 있지만,
다변량 시계열 데이터는 일반적으로 더 강한 시간 의존성을 보이며 반드시 실시간으로 처리될 필요는 없습니다.
[2] 스트리밍 데이터에서의 이상 탐지의 중요성
- 스트리밍 데이터에서 이상 탐지의 중요성
- 사물인터넷의 기기 간 증가하는 상호연결에 따라 센서 데이터의 순차적 처리가 결정적
- ex. 의료, 네트워킹 또는 환경 모니터링
- 이상 현상에 대한 명확한 정의의 중요성
- 특정 애플리케이션에서 예상되는 이상 현상에 대한 명확한 정의가 좋은 탐지 성능을 위해 필요
- '이상치' = '이상 현상'은 흔히 동의어로 사용됨
- 전통적인 이상치의 정의
- 다른 관측치와 매우 다르게 벗어나서 다른 메커니즘에 의해 생성되었다는 의심을 불러일으키는 관측치"(Hawkins, 1980)
- '이상치'가 특정 통계적 속성 때문에 다른 데이터와 눈에 띄어야 함을 제안
- 시간에 따라 변하는 환경에서의 불확실성과 밀접한 관련
- ex. 스트림 내의 이상치는 고립된 데이터 포인트일 수도 있고, 시간 패턴을 깨는 데이터 포인트일 수도 있지만, 고립된 작은 클러스터나 갑자기 폭발하여 나중에 사라지는 큰 클러스터일 수도 있음
- 이상 현상의 정의
- 보통 애플리케이션 맥락에 의해 정의됨
[3] 스트리밍 데이터 분석에서의 이상 탐지 알고리즘 지침 3가지
- 이전 연구들
- unsupervised classification의 성능이 데이터와 분석 목표에 따라 달라질 수 있다고 강조
- 일부 방법들이 명확한 이점을 보일 수 있지만, 일반적인 '최고의 알고리즘'을 설정하는 것은 거의 불가능
- unsupervised classification의 성능이 데이터와 분석 목표에 따라 달라질 수 있다고 강조
- 스트리밍 데이터 분석에서의 이상 탐지 알고리즘 지침 3가지
- 1) 특정 데이터 특성이 알고리즘 정확도에 어떤 영향을 미치는가?
- 우리는 다양한 이상치 비율, 공간 및 시간 밀도, 정상 형태 간의 변화하는 거리, 그리고 다양한 유형의 개념 변화를 고려
- 2) 알고리즘이 이전 지식을 어떻게 활용하여 스트리밍 조건에 적합하게 하는가?
- unsupervised 학습 알고리즘은 종종 구체적인 애플리케이션에서 추상화되어 설계되므로 잠재적 사전 지식을 무시함
- (하이퍼파라미터 자동화 필요성) 실제로, 모델을 훈련시키고 하이퍼파라미터를 조정하기 위해 사전 지식이 필요하며, 이러한 과정은 이상적으로 자동화될 수 있어야 함
- 데이터가 진화함에 따라 구성이 최적이 아닌 상태가 되는지 평가하는 것이 중요
- 알고리즘의 메모리 범위(예: 슬라이딩 윈도우 크기)는 탐지 성능에 영향을 미치지만, 메모리 요구 사항과 계산 비용에도 영향O
2. Outlier detection in streaming data
[1] 다차원 스트리밍 데이터에서의 이상 탐지 연구 필요성
- 스트리밍 데이터 분석: concept drift, 즉 예상치 못한 방식으로 모델링된 현상의 통계적 속성이 시간이 지남에 따라 어떻게 변하는지를 다뤄야 합니다
- 스트림 클러스터링에서 가장 인기 있는 설문조사 중 하나인 알고리즘에서 다루어야 할 주요 누락된 측면으로도 발견됩니다
[2] 스트리밍 데이터에서 이상 탐지의 가장 관련성 있는 비교
- 스트리밍 데이터에서 이상 탐지의 가장 관련성 있는 비교; Tran, Fan, 및 Shahabi(2016)의 작업
- k-NN 기반 알고리즘에 초점을 맞추고 CPU 시간과 최대 메모리 소비 측면에서 비교
- 정확도 대신 실행 시간과 메모리에 초점을 맞춤
- 각 방법이 이상함의 다른 해석을 어떻게 적용하고 그 함의가 무엇인지를 연구
- 메모리 범위를 증가시킬 때 확장성에 대한 통찰력을 얻기 위해 실행 시간을 평가
2.1. Methods under study
[1] 방법론들 소개
- unsupervised + streaming data
- 방법론들
- SWKNN (슬라이딩 윈도우 K-최근접 이웃): Ramaswamy, Rastogi, Shim (2000)이 제안한 k-NN 알고리즘을 슬라이딩 윈도우 내에서 구현한 방법입니다. 스트리밍 데이터에서 이상 탐지를 위한 가장 인기 있는 접근법 중 하나로, 계산 부하를 줄이는 방법(예: Approx-STORM에서의 샘플링 또는 MCOD에서의 마이크로 클러스터 사용)에서 기술적 차이가 있습니다. 이 방법은 단순히 이진 라벨을 얻는 대신, 𝑘번째 이웃까지의 거리를 기반으로 점수를 구성하여 다른 방법과 공정하게 비교할 수 있습니다.
- SWLOF (슬라이딩 윈도우 로컬 이상치 팩터): Breunig, Kriegel, Ng, Sander (2000)가 제안한 인기 있는 LOF 알고리즘을 슬라이딩 윈도우와 함께 구현한 방법입니다. LOF는 일반적인 목적의 이상 탐지 기술로 여전히 가장 신뢰할 수 있는 옵션 중 하나지만, 스트리밍 데이터에는 계산 비용이 많이 듭니다. 이 방법은 실행 시간을 줄이기 위한 다른 색인 기술을 사용합니다.
- RRCT (Robust Random Cut Forest): AWS Kinesis Analytics에서 사용 가능한 동적 데이터 스트림의 이상 탐지를 위한 모델 기반 접근 방법입니다. 트리 그래프의 앙상블을 사용하며, 숲 구조에 대한 차별적 효과를 바탕으로 새로운 점의 이상치 정도를 설정합니다.
- RSHash: Sathe와 Aggarwal (2016)에 의해 개발된 무작위 해싱을 기반으로 하는 간단한 알고리즘입니다. 해시된 데이터 표현, 약한 감지기의 앙상블, 데이터 샘플을 사용하여 훈련 모델을 생성합니다. 방법의 복잡성은 데이터 크기에 선형적이며, 공간 요구 사항은 일정하며 좋은 정확도 성능을 달성합니다.
- LODA: Pevný (2016)에 의해 제안된 스트리밍 데이터를 위한 이상 탐지기로, 낮은 시간 및 공간 복잡성을 가진 약한 학습자 집합을 결합합니다. 이 방법은 분석 공간을 일련의 주요 일차원 히스토그램을 통해 단순화합니다.
- SDO 및 SDOstream: SDO는 모델 기반의 이상 탐지 기술이며, SDOstream은 그것의 스트리밍 데이터 확장입니다. SDO는 본질적으로 정적이지만, 내부 모델을 업데이트하지 않고도 점진적으로 작동할 수 있습니다. SDOstream은 모델 노화를 설정하는 하이퍼파라미터 𝑇를 추가합니다.
- xStream: 특징 공간이 변할 수 있는 스트리밍 데이터 시나리오를 다루는 최근의 접근 방법입니다. 고차원 데이터를 저차원 부공간으로 투영하고 반공간 체인을 사용하여 이상치 점수를 계산합니다.
3. Defining anomalies
- 전통적인 이상 탐지
- 주로 unsupervised 방식
- 시간, 공간 상에서 가까운 다른 데이터 포인트들과의 위치 평가
- 집단적 이상현상(이상 cluster) 탐지에 부적합
- 최근 이상 탐지
- 이전 정상 데이터 포인트로 정의된 것과 다른 것을 이상치로 정의
- semi supervised방식에 가까움, 일종의 classification으로 언급됨
- 이상 정의 방식 주요 카테고리
- Local vs. global
- 로컬 접근 방식: 가장 가까운 이웃에서 이상을 평가하는 데 초점
- 글로벌 방법: 이상치를 극단적인 값과 강하게 고립된 데이터로 간주
- Strict vs. relative
- 상대적 접근 방식: 과거 데이터를 사용하여 시간이 지남에 따라 모델이나 매개변수에서 유지되는 정상성을 정의
- 엄격한 방법: 사전 지식에 덜 의존하는 이상함의 정의를 사용
- Local vs. global
4. Data scenarios and challenges
4.1. Synthetic data
- MDCstream
- 다차원 공간에서 다양한 유형의 개념 변화를 생성할 수 있는 스트리밍 데이터 생성기
- 전반적인 구성에 따라 노이즈, 근접한 점, 극단값 또는 문맥적 이상으로 이상치를 추가하지만, 항상 독립적인 데이터 포인트로 추가 (작은 클러스터가 나중에 이상치로 재분류되지 않는 한).
4.2. Real-application data and memory span
- 대부분의 스트림 분석 알고리즘
- 과거 데이터를 얼마나 오랫동안 기억할지를 결정하는 하나 이상의 하이퍼파라미터를 가짐
- = 슬라이딩 윈도우와 같은 형태로 구현
- 특정 시나리오의 동적인 특성에 맞추어 조정
- 언제 과거 데이터를 잊어야 하는지는 전문가의 주관적인 판단에 달려있음
- ⇒ 자동화 어려운 주관적 측면
- 가능한 한 긴 기억력을 유지하는 것이 바람직⇒일부 알고리즘에서는 시간 관련 하이퍼파라미터의 변경이 다른 하이퍼파라미터의 조정에 영향을 미칠 수도 있음
- ⇒ 긴 기억력은 concept drift를 다루는 데 있어서 역효과
- ⇒ 계산 비용으로 인해 실제로는 이를 유지하기 어려움
- 실제 데이터 사용 중요
- 다양한 시간 관련 하이퍼파라미터가 방법론의 정확성과 실행 시간 성능에 미치는 영향을 테스트하기 위해
- 비지도 알고리즘이 사전 지식을 최대한 활용하여 모델, 파라미터, 이상치의 정의를 조정하는 방법.
- 데이터셋
- 네트워크 침입 감지를 위한 CICIDS2017
- 우주 셔틀의 하위 시스템 진단에 관한 셔틀 데이터셋,
- 태양 광구 벡터 자기도에서 추출된 Swan-SF
- 레이블이 지정된 이상을 포함하는 실시간 및 합성 시계열 데이터인 Yahoo-TSA
5. Evaluation methodology
- 시간에 따라 변화하는 다차원 수치 특성 공간 다룸
- 동시성이 생략되고 두 연속적인 데이터 포인트 사이의 시간적 거리가
- 하나의 단위로 고정된 방식으로 데이터를 순차적으로 처리하는 비지도 알고리즘을 테스트
- 단변량 시계열 이상탐지
- 혼합데이터에서의 이상탐지
- 증분 지도학습 이상탐지
- 스트리밍 데이터에서의 이상 패턴 탐지
5.1. Parameter adjustment
5.2. Experimental steps
6. Results and discussion
6.1. Streaming data challenges
6.1.1. Accuracy
- SWKNN, SDOstream
- 둘다 최상의 결과
- SWKNN: 관측 window에서 가장 가까운 점을 사용
- 관측 창이 비교적 적은 데이터 포인트만을 취하고 이러한 차이를 덜 명확하게 만드는 문제는 SWKNN이 적절한 𝑘 하이퍼파라미터를 조정함으로써 일반적으로 극복
- SDOstream: 모델 내에서 가장 가까운 점(즉, 관찰자)을 사용
- concept drift에 안좋게 적응됨(즉, 비정상, 순차적, 이동하는 경우).
- 고정된 학습 모델을 사용하기 때문에 주요 개념 변화 후에 모델이 구식이 되기 때문
- RSHash
- 뛰어난 정확도를 보이지만, SWKNN과 SDOstream에 비해 클러스터 관련 공간적 문제(즉, 밀도 차이, 근접한 클러스터, 클러스터 중첩)에 더 크게 영향
- SWLOF, LODA, RRCT
- 앞서 언급된 방법들보다는 일반적으로 낮지만 여전히 만족스러움
- 클러스터가 서로 너무 가까운 타이트한 공간에서 SWLOF가 오도되는 것을 가장 잘 피함
- RRCT
- LODA
- xStream
6.1.2. Challenges
7. Conclusions
- 개념 변화와 데이터 기하학: 대부분의 연구된 방법들은 개념 변화와 변동하는 이상치 비율을 적절히 처리하지만, 정상 데이터가 중첩되거나 다른 밀도를 보이는 근접한 형태로 이루어진 축소된 공간에 직면했을 때 어려움을 겪습니다. SWKNN, RSHash, SDOstream은 최상의 성능을 보여주며, 경쟁자들보다 작은 데이터 포인트 집합을 더 잘 처리하는 것 같습니다.
- 사전 지식의 사용: 알고리즘은 훈련 데이터를 사용하여 파라미터와 모델을 적절하게 조정할 수 있습니다. 전통적인 방법들(SWKNN, SWLOF)은 이상치에 대한 엄격한 정의를 최대한 활용하는 반면, 현대적인 제안들(RSHash, RRCT, LODA, SDO, xStream)은 응용 프로그램에 의해 부과된 정상성을 더욱 고려하는 더 유연한 정의를 구축합니다. 중간 접근법은 비이진 점수를 가진 SWKNN 버전과 SDOstream입니다.
- 메모리 범위: 메모리 범위는 SWLOF에서 중요한 제약 조건으로, 심각하게 단시안을 만듭니다. LODA에서도 덜 하지만 여전히 제한적인 요소입니다. 다른 방법들(SWKNN, SDO, SDOstream, RSHash, RRCT, xStream)은 응용 프로그램의 요구 사항을 우선시하면서 메모리를 조정할 수 있으며, 계산 비용에 의해 덜 제한됩니다. 그러나 실제로, 메모리 범위는 응용 프로그램의 역동성뿐만 아니라 모델을 생성하고 하이퍼파라미터를 조정하는 데 사용되는 사전 지식에도 의존합니다.
- 각 방법론의 특성 요약
- SDO: 개념 변화를 무시할 수 있고 정상성이 과거 데이터에 의해 잘 정의될 때 가장 신뢰할 수 있습니다.
- SWLOF: 응용 목표가 강하게 지역적인 접근을 요구하는 과밀하고 좁은 공간에 가장 적합합니다.
- RRCT: 정확도를 잃는 대신에 가장 적응력이 뛰어납니다.
- xStream: 고차원성을 해결하고 응용 단계 중에 추가되는 새로운 차원을 다룰 수 있는 능력을 얻기 위해 정확도와 적응성을 희생합니다.
- LODA: 상대적인 글로벌 방법으로, 정상 데이터의 집중을 더 잘 강조할 수 있으며, 따라서 이상치가 많은 소음 배경 내에서 클러스터를 구분하는 데 가장 좋은 방법입니다.
- SWKNN, RSHash, SDOstream: 일반적으로 가장 정확하며, 이러한 정확도를 달성하기 위해 더 적은 데이터를 요구합니다. 이 세 가지 옵션 사이의 결정은 궁극적으로 지역성과 상대성을 얼마나 중요시하느냐에 달려 있습니다: SWKNN은 가장 지역적이고 엄격하며, RSHash는 가장 글로벌하고 상대적이고, SDOstream은 그 중간에 위치합니다.
- 이상치의 해석을 지역적, 글로벌, 엄격 또는 상대적으로 구분하는 것 외에도, 방법 선택을 위해 다른 특성들도 신중하게 고려되고 연구되어야 합니다; 예를 들어, 하이퍼파라미터의 견고성과 조정 용이성뿐만 아니라 데이터 컨텍스트의 변화에 직면했을 때 파라미터와 학습된 모델의 관성 등입니다.