이번 포스팅에서는 이상치 탐지 (Anomaly Detection) 영역의 알고리즘인 Local Outlier Factor (LOF)에 대해서 살펴보겠습니다. 먼저 간단하게 Anomaly Detection이 무엇이며, 왜 필요한지 살펴보고, 국소(local)영역에서 이상치를 탐지하는 LOF 알고리즘 순으로 이어가겠습니다.
Anomaly Detection?
Anomaly Detection이란 Machine Learning의 Unsupervised Learning의 영역으로 주어진 데이터로 하여금 이상치 (Outlier)를 탐지하는 방법들의 집합으로 정의할 수 있습니다. 여기에서 Outlier란 데이터의 평균적인 패턴과 극단적으로 다른 모습을 보이거나, 또는 그러한 데이터의 중심부에서 멀리 떨어져 있는 데이터를 의미합니다.
Anomaly Detection은 다양한 목적으로 필요할 수 있습니다. 본 포스팅에서는 Fraud Detection을 예로 들려고합니다.
Motivation - Fraud Detection
정상/사기(또는 스팸메일 등)에 대한 이진 분류를 생각해보곘습니다. 이 문제를 풀때 두 가지 challenge를 직면할 수 있습니다. 첫 번째는 정상의 경우보다 사기가 극단적으로 적은 상황, 두 번째는 '사기'라는 event 자체를 정의하기 어려운 상황입니다.
첫 번째 상황에서 classification문제를 풀기 위해서 Machine Learning (ML)의 Supervised Learning (SL) 알고리즘을 이용할 수 있습니다. 하지만 SL은 결국 주어진 데이터에서 패턴을 찾고, 이에 대한 예측결과를 제공하다보니, 데이터가 적은 영역에서 성능이 떨어지게 됩니다.
두 번째 상황은 사실 첫 번째 상황보다 더 본질적으로, 어떤 경우를 사기/스팸 등으로 정의를 내려야 되는데, 쉬운일이 아닙니다. 가령 판촉 광고를 문자/메일/전화 등로 받았을 경우 때로는 Spam보다는 Ham일 수 도 있기 때문입니다.
위와 같은 상황에서 Anomaly Detection을 적용하는 것이 도움이 될 수 있습니다. 첫 번째 상황에서는 단순히 일반적인 패턴이 아닌 데이터를 분류하면 되는 문제로 바꾸어 해결할 수 있고, 두 번째 상황에서는 Anomaly Detection은 라벨을 정의할 필요가 없고, 데이터 패턴이 특이한 것을 사기/스팸으로 바꾸어 생각할 수 있습니다.
Local Outlier Factor (LOF)
Local Outlier Factor?
Local Outlier Factor (LOF)란 Outlier의 정도 나타내되, 어떤 데이터의 Neiborhood를 고려하여 outlier factor를 계산해주는 방법입니다. 직관적인 예시를 살펴보겠습니다.
위 fig1의 좌측 그림을 살펴보면 빨간색 원으로 표기된 부분은 outlier인 것 처럼 보입니다. 그런데 사실은 2개의 bivariate normal distribution으로 부터 랜덤 샘플링한 결과로, 우측에 표기된 것 처럼 빨간색 분포와 초록색 분포는 각 분포내에서 지극히 정상적인 데이터입니다. 이렇듯 현실에서 마주하는 데이터는 여러분포가 섞여있을 수 있습니다. LOF는 데이터의 국소적인 분포를 고려하여 outlier의 정도를 나타내주는 방법입니다.
LOF를 정의하고, 이해하기 위해선 몇 가지 간단한 내용을 알고 있어야 되는데, Reachabilityh Distance와 Local Reachability Density입니다. 아래에서 순서대로 살펴보겠습니다.
Reachability Distance
Reachability Distance는 주어진 데이터로부터 k-neiborhood의 데이터내에 있을 경우 거리를 같게 아닌 경우는 실제 거리를 측도하는 방법입니다. $$\text{RD}\left(x_{i},x_{j}\right)=max\left[\text{k-distance}\left(x_{j}\right), dist.\left(x_{i},x_{j}\right)\right]$$여기에서 $\text{k-distance}(x_{j})$는 $x_{j}$와 $k$번째 가까운 데이터와의 거리를 의미하며, distance는 세간의 어떤 distance라도 적용할 수 있습니다. Euclidean Distance를 가정해보면 아래와 같은 직관적인 상황을 생각해 볼 수 있습니다. ($k=3$을 가정합니다.)
$RD(x_{a}, x_{j})$는 $k=3$ 근방에 있고 $\text{k-distance}(x_{j})$가 2라서, 거리가 2이 됩니다. 반면에 $RD(x_{b}, x_{j})$는 $k=3$보다 멀리있고, 그 거리가 5임으로 5가 된다는 의미입니다. 이렇게 거리를 설정하면 주어진 데이터로부터 근방에 있는 데이터가 같은 분포에 속해 있음을 표현할 수 있게 됩니다.
Local Reachability Density
Local Reachability Density (LRD)는 기준 데이터 근방 $k$개의 데이터와의 밀집 정도를 측도한 것 입니다. $$LRD\left(Y\right)=\frac{1}{\frac{1}{\|N_{k}(Y)\|}\sum_{X_{j}\in N_{k}(Y)}RD\left(Y, X_{j}\right)}=\left[\frac{1}{\|N_{k}(Y)\|}\sum_{X_{j}\in N_{k}(Y)}RD\left(Y, X_{j}\right)\right]^{-1}$$ 위 식에서 $N_{k}(Y)$는 데이터 $Y$ 근방의 $k$개의 데이터라는 의미입니다. $\|N_{k}(Y)\|$의 경우 $k$보다 크거나 같은 값을 가질 수 있습니다. 예를 들어 $k=2$이고 어떤 점으로부터 가까운 거리의 점이 1, 2, 2, 2, 2 순이라고 한다면, 그 값은 5가 됩니다.
수식을 자세히 살펴보겠습니다. RD를 산출하는 부분을 살펴보면, 기준 데이터 $Y$ 근방에 있는 어떤 데이터 $X_{j}$를 산출하되 기준점이 $X_{j}$입니다. 즉 $Y$는 $Y$와 가까운 $X_{j}$들 사이에서 얼마나 떨어져 있는지를 측도하는 것 입니다. 그리고 얼마나 떨어져 있는지에 대한 평균을 구하고, 이에 대한 역수를 취합니다. 따라서 $Y$가 $Y$ 근방에 있는 데이터들의 공간에서 동떨어져 있을 수록 분모의 크기가 커져 LRD는 작은 값을 얻습니다.
위 예시로 살펴보면 좀 더 와닿을 거라고 생각합니다. $k=4$를 기준으로 했을 때, Case1의 경우에는 밝은 보라색인 이웃점들의 근방과의 거리 대비 가까운 반면, Case 2경우는 상대적으로 거리가 멉니다. 따라서 Case 1의 LRD가 Case 2대비 큰 값을 갖게 됩니다.
Local Outlier Factor
RD와 LRD를 정의하고 나면 비로소 Local Outlier Factor (LOF)를 정의할 수 있습니다. LOF는 측도하고자하는 데이터 $Y$대비 $k$근방 데이터들의 LRD가 얼마나 작은가를 측도합니다. $$LOF_{k}\left(Y\right)=\frac{\frac{1}{\|N_{k}(Y)\|}\sum_{X_{j}\in N_{k}(Y)}LRD_{k}(X_{j})}{LRD_{k}(Y)}$$ LRD는 주변 데이터에서 많이 떨어져있을 수록 값이 작도록 정의되어, LOF 값이 크다는 것은 주변 데이터들이 흩어짐 정도 보다 훨씬 많이 떨어져 있음을 의미합니다. 즉 LOF 크기가 클 수록 Outlier임을 의미합니다. 보통 LOF는 1을 기준으로 1보다 값이 큰 값을 아웃라이어로 분류하며, 값이 클 수록 아웃라이어 정도가 심함을 의미합니다.
Summary + Limitation
이번 포스팅에서는 데이터의 국소 영역의 분포를 고려하여 outlier 정도를 측도하는 방법인 Local Outlier Factor에 대해서 살펴봤습니다. LOF는 간단한 구조로 효과적으로 outlier를 탐지할 수 있는 방법입니다. 반면에 $k$ 근방의 데이터를 찾아내는 과정에서 data-wisely 거리를 계산하게 되고, 따라서 크기가 큰 데이터에서는 계산량이 많아 사용하기 어렵다는 단점이 존재합니다. 이상으로 이번 포스팅을 마치겠습니다.
긴글 끝까지 읽어주셔서 감사합니다 :)
Reference
Breunig, Markus M., et al. "LOF: identifying density-based local outliers."
Proceedings of the 2000 ACM SIGMOD international conference on Management of data
. 2000.
댓글