[ML] 'Robust Random Cut Forest for anomaly detection' 설명 및 library (Online Anomaly Detection)

 

 

Robust random cut trees

• Random: 우리가 가지고 있는 데이터들로부터 임의로 뽑아냄.
• Cut: 같은 수의 점들로 부분집합을 만들어서 tree를 구성.
• Forest: 만들어진 여러 트리들을 모두 고려해서 anomaly 여부를 결정.
  • binary tree이다.
• Stream data를 처리할 수 있으며, 고차원 데이터에도 적합.
• 이상치 점수를 매겨 통계적으로 이상치 판단.
• 포인트 셋에서 이상치(outlier)들을 탐지하는 데 사용할 수 있는 이분 탐색 트리이다. 루트에 가까운 점은 이상치일 가능성이 높다.

 

 

Amazon SageMaker의 Random Cut Forest(RCF) 알고리즘

• 트리 만들기:
  • 트리는 숫자 데이터를 순서대로 저장한다. (이진 트리)
• 이상치 판단: 데이터 'A'가 이상치인지 알아보자
  1. 기존 데이터에서 랜덤 샘플링해서 뽑은 데이터 몇 개와 A를 둔다.
  2. 데이터가 있는 공간을 랜덤 하게 2등분 한다.
  3. root는 (랜덤 샘플링한 데이터 + A)모든 데이터를 가지고 있는 노드이다. 여기에 [3]에서 나눈 데이터를 각각 자식 노드로 둔다.
  4. 나눠진 영역에 A만 남을 때까지 계속해서 랜덤 하게 분할하며 트리를 생성한다.
  5. 세분화한 횟수가 적을수록(A만 있는 노드의 depth가 낮을수록) A는 데이터 셋에 대한 anomaly일 가능성이 높다.
     • anomaly score: 이 확률(이상치일 확률)을 측정
     • anomaly socre가 높다는 것은 anomaly일 가능성이 높다는 것을 나타냄
  6. trees를 forest로 combine
     • [1~5] 과정을 통해 여러 개의 트리를 만들어 forest를 구성하고 전체적으로 반영한다.

 

• 통상 평균값에서 3 표준편차 범위를 넘을 경우 이상치로 간주(데이터가 정규분포를 따른다고 가정)
• Amazon SageMaker의 RCF 알고리즘
  1. 우선 학습 데이터에서 임의로 샘플을 추출하여 작업을 수행한다. 만약 학습 데이터가 지나치게 커서 머신 한 대에 올리기 어려운 경우, reservoir sampling 기법을 이용하여 데이터 스트림으로부터 샘플 데이터를 효율적으로 추출한다.
     • reservoir sampling 기법: 입력 데이터를 주어진 파일에 대해 오프셋 탐색을 이용하여 선택된 데이터만을 샘플로 선정해 메모리에 적재하므로 대용량 데이터에 대해 효과적으로 샘플링 가능.
  2. 이를 통해서 서브 샘플 데이터들이 Random Cut Forest를 구성하는 트리 각각에 분포하게 된다.
  3. 각각의 서브 샘플 데이터는 바운딩 박스를 랜덤하게 분할하는 식으로 만들어진 이진트리를 구성하게 되는데, 이러한 트리 구성은 각 리프 노드(즉, 터미널 노드)가 데이터를 하나만 담고 있는 바운딩 박스로 만들어질 때까지 계속 반복된다.
  4. 입력 데이터에 할당된 이상치 스코어는 포레스트를 구성하는 트리의 평균 깊이와 반비례한다.
• 더 자세한 내용 - 참고

 

 

전처리 방법: shingling

• 이상 탐지 알고리즘에서, shingling은 연속성을 지닌 데이터에서 길이 s만큼의 시퀀스를 s-차원의 벡터로 변환함으로써 1차원 데이터를 s-차원 데이터로 바꾸는 기술이다.
• 이렇게 하면 정기적으로 나타나는 변화를 탐지하기 좋고, 이상치 스코어의 원래 값에서 작은-규모의 노이즈를 필터링하는데 효과적이다.
• shingle 사이즈가 너무 작을 경우, Random Cut Forest 알고리즘이 데이터의 작은 변화에도 심하게 영향을 받을 수 있다. 반면에 사이즈가 너무 크면, 작은 크기의 이상치를 탐지하지 못할 수 있다.

 

 

 

Library 사용법

1. 설치

pip install rrcf

 

2. 빈 트리 생성

def create_forest(num_trees):

        forest = []
        for _ in range(num_trees):
            tree = rrcf.RCTree()
            forest.append(tree)

        return forest

 

3. 이상치 탐지

#check anomaly with RRCF
    def anomaly_detection(self, data):
        for tree in self.forest:
            if len(tree.leaves) > self.tree_size:
                tree.forget_point(self.idx-self.tree_size)
              
            tree.insert_point(data, index=self.idx)

            if not self.idx in self.avg_codisp:
                self.avg_codisp[self.idx] = 0
            self.avg_codisp[self.idx] += tree.codisp(self.idx) / self.num_trees
        # avg_codisp은 (각 tree 이 point를 anomaly로 생각하는 정도)의 평균
        mean = np.array(list(self.avg_codisp.values())).mean()
        std = np.array(list(self.avg_codisp.values())).std()

        z = (self.avg_codisp[self.idx] - mean)/std
        self.idx += 1
        if z > 3.0 or z < -3.0 :
            return self.previous_train_batch.mean()
            # if abs(z-score) is over 3.0
            # replace the value with the mean of whole data we met

        else :
            return data
        #if not over 3.0, then no need to replace the value

 

 

 

 

 

 

참고:

 

- Amazon SageMaker에서의 점진적 훈련:

https://docs.aws.amazon.com/ko_kr/sagemaker/latest/dg/incremental-training.html

 

- RCF 알고리즘 library:

https://github.com/kLabUM/rrcf

 

- AWS Sagemaker 설명:

https://freecontent.manning.com/the-randomcutforest-algorithm/