Outlier Detection in Discrete Sequences - Position & Combination Outliers

Outlier Detection in Discrete Sequences - Position & Combination Outliers

 

10.1 Introduction

• Each time stamp가 discrete-valued( i.e., categorical) 에서 individual elements를 가지는 discrete time-series를 sequence라 합니다.
• discrete-valued temporal scenarios 는 intrusion detection,system diagnosis , biological applications에서 많이 이용합니다.

 

Temporal ordering and physical ordering

• intrusion detection과 system diagnosis 와 같은 domain에서 discrete sequences 는 temporal ordering에 의해 생성합니다.
• 반면 biological data 와 같은 domain에서는 the discrete sequences는 physical ordering에 의해 생성됩니다.
• 둘의 주요 차이는 temporal data는 특정한 방향( i.e., forward in time)이 있지만 placement relationships 기반인 physical data는 특정한 방향이 존재하지 않는 것입니다.
• 그러나 logical level에서 두 경우에 대한 problem definitions의 차이는 상대적으로 적어서 cross-applicability 지닙니다.

Example of applications that generate discrete data sequences

• Systems diagnosis : 많은 automated systems 은 system state에 대한 끊임없는 데이터 생산. 다음의 예가 있습니다.
  • UNIX system calls
  • aircraft system states
  • mechanical systems
  • host-based intrusion detection systems. - 가장 흔하고 그 자체로 중요한 연구 주제
• Biological data : Biological data는 일반적으로 아미노산에 대한 sequences가 포함되어있는데 anomalous subsequences는 unusual genome sequences 에 대한 information 과 genetic conditions의 다른 종류에 대한 impact에 대해 information 제공 가능합니다.
• User-action sequences : different application domains에 따른 user actions 에 의해 sequences 생성됩니다.
  • Web logs : 은 개인의 web sites 방문에 대한 long sequencs 지닙니다.
  • Customer transactions : 구매 행동에 대한 sequences 가집니다. symbols는 팔린 품목의 식별자에 해당될 수 있습니다. 비정상적인 temporal patterns 는 구매 패턴에 대한 변화에 해당합니다.
  • User actions on web sites : web logs와 비슷하지만 web sites에서의 logs가 더 디테일 한 것이 다릅니다. action에 대한 anomalous subsequences는 unusual activity에 대해 insights 제공 가능합니다.

 

Notation

• A sequence는 symbol set $\Sigma = { \sigma_1,...\sigma_{|\Sigma|} }$ 에서 추출한 symbols $a_1a_2...a_r$ 에 대한 ordered set 으로 정의합니다.
• 가장 general form 에서 a sequence는 ordered set of sets $S_1S_2...S_r$ 으로 정의합니다. ( each $S_i$ 는 $\Sigma$의 subset )
• 이 챕터에서는 각 element $a_i$ 가 $\Sigma$ 로 부터 directly 추출한 전자 이용합니다. the more complex case인 set-based sequences 인 후자는 briefly 하게 examined.

 

Position outliers and Combination outliers

• 거리 관점에서 alphabet $\Sigma$ 로 부터의 서로 다른 symbols에 대해 거리를 직접적으로 비교할 수 있어 continous time series와 다릅니다. ⇒ regression modeling을 쉽게 일반화 할 수 없습니다.
• 그래도 이런 경우에 outliers는 specific time stamps에서 예측되는 값에서의 deviation이나 unusual successive combinations of sequence values 관점에 따라 정의될 수 있습니다.
• specific positions을 기준으로 하는 outlier와 combinations of symbols을 기준으로 하는 두 가지 outlier types 존재합니다.

 

• Position outliers
  • position based outliers 에서 특정 위치의 값은 모델에 의해 예측됩니다. 이 예측은 모델로부터의 deviation 측정하기 위해 사용됩니다.
  • 일반적으로 Markovian methods 가 predictive outlier detection에 이용됩니다.
  • continuous time series에서의 regression models와 비슷합니다.
  • regression과 다르게 Markovian models 는 discrete data에 더 적절하며 이는 contextual outliers 에 해당됩니다.
• Combination outliers
  • combination outliers에서 entire set sequence는 그 sequence에 해당하는 combination때문에 비정상적인 것으로 간주합니다. 이는 이 combination은 (frequency-based) sequence database에서 매우 드물거나 비슷한 size의 다른 많은 subsequences 과 distance가 멀거나 similarity가 낮기 때문입니다.
  • hidden Markov models와 같은 복잡한 모델은 generative probabilities 관점에서 presence에 대한 frequency 모델하는데 이용될 수 있습니다.
  • a longer test sequence에 대해서는 smaller subsequences가 testing을 위해서 추출되고 이후 entire subsequences에 대한 outlier score가 these values들에 대한 조합으로 예측됩니다. ⇒ time series data의 unusual shapes determination과 비슷합니다. 이는 collective outliers 에 해당합니다.

 

특정 모델의 선택에 따라 다른 방식으로 정의되는 combination of values의 rarity

• Distance-based
  • 한 subsequence 에서 다른 base data에 있는 candidate subsequence 에 대한 the nearest-neighbor distance 계산하여 해당 sequence의 outlier score로 사용합니다.
  • a longer sequence의 score는 its smaller subsequences의 outlier scores의 combination으로 계산합니다.
  • shorter sequences 경우 clustering 이 outlier analysis process에 이용될 수 있고 이러한 방법들은 multidimensional data에서 사용한 distance-based 방식과 비슷합니다.
• Frequency-based
  • different subsequences 의 values 에 대한 occurrence 의 frequency 는 base training data와 test instance 사이에서 비교합니다.
  • test 와 training sequence 사이의 subsequences frequency distributions 의 unusual differences 를 보이는 sequences는 outliers로 가정합니다.
  • 이 방법은 alphabet size가 작고 subsequence가 상대적으로 작을 때 유용. 이런 경우 한정된 distinct values에 대한 subsequences 가 존재하고 이는 frequencies 관점에서 meaningful.
  • distance-based models 처럼 smaller subsequences 는 meaningful frequency comparisons를 위해 extracted.
• Model-based
  • subsequeces 를 생성하는 probabilistic generative model 이 constructed. (i.e., hidden Markov model )
  • model 에 의해 생성된 낮은 확률을 가진 subsequences 는 outliers로 predicted 되며 이는 multidimensional data의 expectation-maximization algorithm 과 비슷합니다.
  • discrete case에서의 이러한 모델의 장점은 well-designed generative Markov model은 sequence에 대한 user understanding을 encoding가능하고 현재 데이터에서 명백하게 드러나지 않는 가능성 높은 sequences도 capture 가능합니다.
• Transformation-based
  • the sequences들은 kernel methods의 사용을 통해 new space로 transformed.
  • A pairwise object-to-object similarity matrix is constructed.
  • kernel-PCA 나 one-class support vector machines 와 같은 방법들이 resulting similarity matrix와 conjuction되어 이용 가능합니다.

 

* 이 글은 Charu C. Aggarwal 의 Outlier Analysis Second Edition을 정리한 글입니다.