[Dcase Task2] A hybrid novelty score and its use in keystroke dynamics-based user authentication (2009) 리뷰

거리 기반 이상탐지 알고리즘인 KNN Detector에 대해 소개하겠습니다. KNN Detector는 벡터를 저장해 학습하는 KNN의 원리를 따라서 정상 데이터의 Emebdding Vector를 저장해서 이후 들어오는 Test 데이터들에 대해 Training Data와 거리가 멀다면 이상 거리가 멀지 않다면 정상으로 판단하는 알고리즘입니다. 이때 거리를 판단하는 종류에도 여러가지가 있는데 이를 살펴보겠습니다.

 

본격적으로 들어가기 전에 KNN에 대해 간략하게 훑고 가겠습니다. 

 

KNN(K-Nearest-Neighborhoods)

KNN의 학습과정은 라벨링이 된 데이터들의 벡터를 저장하는 것입니다. 새로운 벡터를 classification할 때 새로운 데이터의 벡터 주변에 분포한 K개의 벡터 들 중 다수를 이루는 Class로 라벨을 예측하게 됩니다.

 

KNN Detector

KNN Detector는  벡터를 저장하여 학습한다는 점은 같지만 저장된 벡터들로부터 새로운 데이터 포인트의 거리를 측정하여 분류를 하는 것이 아니라 거리가 일정 수준 이상 넘으면 Abnormal 넘지 않으면 Normal로 판단하는 거리 기반 이상탐지가 목적이라는 점이 다릅니다. 새로운 데이터와 학습된 데이터의 거리를 기준으로 이상치를 판단한다는 것은 Abnormal Data라면 Normal Data와 거리가 멀 것이라는 가정하에 진행되는 것이고 또 학습 때 Normal Data만을 사용한다는 것이 전제가 됩니다.  결국 Normal Data의 분포를 학습시켜 분포로부터의 거리로 이상치인지 아닌지 판단하겠다는 것입니다.

 

 

Conventional Distance

KNN Detector는 거리를 기반으로 이상탐지를 하는 알고리즘입니다. 새로운 데이터 포인트 한 개에 대해 K 개의 저장된 벡터로부터의 거리를 구하는 방법에는 Max-Distance, Avg-Distance, Mean-Distance 3가지가 있었습니다.

 

Max-Distance

K개의 거리 중 가장 먼 거리를 선택하는

단점: 한 가지의 Data Point와의 거리만을 고려하다 보니 밀집도를 고려하지 못하게 됨.

 

Avg-Distance

K 개의 Data Point들 과의 거리의 평균을 사용하는 Distance

Data Point의 밀집도를 고려할 수 있음.

 

Mean-Distance

K개의 Data Point들의 평균 벡터와의 거리를 이용하는 Distance

Data Point 들의 밀집도 뿐만 아니라 Data Point 들의 중심점과 상대적인 거리를 고려

 

 

그림은 각각의 상황에서 Conventional Distance 3가지가 각각의 상황에서 새로운 데이터 포인트 x, y 거리를 어떻게 탐지하는 지 나타낸 것입니다.

먼저 a의 오른 쪽 상황은 왼쪽 상황에 비해 학습된 데이터 포인트 a,b,c,d,e 가 새로운 데이터 포인트 y에 대해 더 밀집된 것을 볼 수 있습니다. 이때 Max-Distance는 가장 먼 데이터 포인트만을 고려하므로 왼 쪽 오른 쪽 목두 Novelty Score(Distance)가 5라고 판단하는데 Avg-Distance는 5개의 거리의 평균을 사용하므로 4.2에서 2.8로 Novelty Score(Distance)에 밀집도가 잘 반영된 것을 볼 수 있습니다.

b를 보면 x는 a,b,c,d,e 를 이어서 만들 수 있는 바운더리 밖에 있는 반면 y는 a, b, c, d, e의 바운더리 내에 있는 것을 볼 수있습니다. Avg-Distance는 모두 4.4로 동일한 것을 볼 수 있지만 Mean-Distance는 3.3에서 2.1로 데이터의 바운더리를 잘 고려한 것을 알 수 있습니다.

a,b 로부터는 데이터의 포인트의 밀집도와 바운더리가 Novelty Score에서 꽤 중요한 역할을 한다는 것을 알 수 있습니다.

 

 

다음은 저자가 예시로 들은 Conventional Distance가 위와 같이 Data Point간 거리를 잘 판단해내지 못하는 상황입니다.

 

 

네모는 학습된 데이터 포인트 들이고 Δ와 Ο는 모두 거리를 출력해야할 새로운 데이터 포인트들입니다. 

제시된 상횡 a에서 Δ는 Ο보다 학습된 데이터 포인트 들에 더 가까이 있는 것을 볼 수 있고 b에서 Δ는 학습된 데이터 포인트 들의 바운더리 내에 있으므로 a,와 b 모두에서 Δ의 Novelty Score는 Ο보다 작아야할 것입니다. 

 

하지만 실제 거리 측정 결과는 이렇습니다.

a) Ο  : d max=1.58, d avg = 1.14, d mean = 0.50

     Δ  : d max=1.64, d avg = 1.07, d mean = 0.94

avg distance를 제외하면 모두 Δ가 더 높은 Novelty Score를 가지게 되는 것을 볼 수 있습니다. 

 

b) Ο  :  d max=1.56, d avg = 1.08, d mean = 0.80

      Δ   : d max=1.86, d avg = 1.09, d mean = 0.88

b에서는 모두 Δ가 더 높은 Novelty Score를 갖게 되네요.

 

저자는 Conventional Distance들이 위와 같이 특수한 상황에서 낮은 성능을 보이는 이유를 거리가 멀다면 무조건 Novelty Score가 높아지기 때문이라고 합니다. 이를 방지하기 위해서 저자가 세운 가정은 데이터 포인트를 이은 모형 안에 새로운 데이터 포인트가 존재하게 된다면 Novelty Score가 0에 가깝거나 낮아져야 하고 또 밖에 존재하더라고 데이터 포인트를 이은 간선(Convex Hull)과 상대적으로 가깝다면 Novelty Score가 작아야한다고 합니다.

 

b는 새로운 데이터 포인트가 Boundary 안과 밖에 있는 상황, fig3은 모두 Boundary 밖에 있지만 Convex Hull로부터 상대적인 거리가 다름을 나타냅니다.

 학습된 데이터 포인트들 과의 거리만을 고려하는 게 아니라 Boundary에 대해 보다 더 정밀하게 고려하여 데이터 포인트와의 거리는 상대적으로 더 가깝더라도 Convex Hull과의 거리가 멀다면 Novely Score가 역전이 되는 새로운 Novelty Score가 필요한 것입니다.

 

Hybrid Novelty Score

 

 

저자가 제시한 Hybrid Novelty Score입니다. 전체적으로 살펴보면 avg-distance와 convex-hull distance가 혼합된 형태임을 볼 수 있습니다. Convex Hull로부터 거리가 0에 가깝다면 hybrid distance는 avg-distance와 같은 값을 갖게 될 것이고 Convex-Hull로부터 거리가 멀어 아주 큰 값을 갖게 된다면 점점 avg-distance의 두 배에 가까운 값을 갖게 될 것입니다. Convex-Hull로 부터의 거리를 가중치로 둬서  데이터 포인트 들과의 거리, Convex-Hull 로부터의 거리 모두를 고려할 수 있게된 것입니다.

 

avg-distance는 앞에서 살펴봤으니 convex-hull distance에 대해 살펴보겠습니다. 

 

k개의 학습된 데이터 포인트들로부터 새로운 데이터 포인트 xq 를 재구성 하는 목적함수를 나타냅니다. 이때 wi의 합이 1이 되어야 하고 또 각각이 0보다 크거나 같아야 한다는 조건이 있습니다. 합이 1이되는 가중치가 k개의 데이터 포인트에 곱해져 더해진 다는 것은 내분점을 의미하고 xq가 데이터 포인트들의 경계 내부에 들어간 다면 내분점 중 하나로 표현이 될 것이니 Convex Hull Distance는 0이될 것 입니다.

반대로 Convex-Hull 로부터 거리가 멀다면 내분점 만으로는 표현이 어려워 지므로 k 개의 data point로 reconstructiom할 때 Error가 커지게 될 것입니다.

 

 

Convex-Hull Distance가 0이라면 기존의 avg distance로 Convex Hull이 0이 아니라면 avg-distance에 가중치가 곱해져서 결과적으로 더 큰 값을 갖게 될 것 입니다. 이에 대해 더 큰 Thresh Hold를 줘서 Abnormal Data를 탐지할 수 있습니다.

 

 

위 그림은 Distance마다의 Boundary를 그림으로 나타낸 것입니다. 이번 포스트에서 살펴본 distance들 위주로 살펴보겠습니다. 먼저 c, max-distance의 경계면은 부드럽지 않은 것을 알 수 있고 avg distance는 바운 더리 중간 중간 빈 부분과 우측 상단 부분의 군집은 연결이 잘록하게 되어 있는 것을 볼 수 있습니다. k개 데이터 포인트의 거리의 평균을 사용하다 보니 군집이 존재하더라도 몰려 있지 않은 부분은 이상치의 바운더리로 보는 것입니다. e는 Mean distance인데 평균 vector의 바운더리를 사용하니 군집 중간에 추가적인 바운더리가 생기는 것입니다. 실제 군집의 바운더리 밖에 존재하더라도 정상데이터로 판단할 수 있는 것입니다. 마지막으로 f, hybrid novelty score가 만든 바운더리는 매끄럽고 빈 부분이 없으면 군집의 바운더리를 잘 반영하고 있음을 알 수 있습니다.