Studying data
[이상치 탐색] 2. ML을 통한 Outlier Detection - (4) Mahalanobis Distance (with scikit-learn) 본문
[이상치 탐색] 2. ML을 통한 Outlier Detection - (4) Mahalanobis Distance (with scikit-learn)
halloweenie 2023. 5. 21. 21:29Mahalanobis Distance
마할라노비스 거리(Mahalanobis distance)는 다변량 공간에서 두 점 사이의 거리를 의미한다. 단, 유클리디안 거리와의 차이점은 두 점 사이의 분포, 즉 두 변수간의 상관관계를 고려해서 측정한 거리라는 것이다.
두 벡터 \(\vec{x}\)와 \(\vec{y}\) 사이의 유클리디안 거리는 다음과 같이 벡터의 차와 내적을 이용해 계산할 수 있다.
$$d_E = \sqrt{(\vec{x}-\vec{y})(\vec{x}-\vec{y})^T}$$
하지만 두 점 사이의 거리는 두 점 사이에 위치한 데이터들의 분포에 의해 상대적인 의미를 가지게 될 수 있다.
예를 들어 위 그림(a)의 \(\vec{x}\)와 \(\vec{y}\)는 중앙의 파란색 데이터들에서 멀리 떨어져 있고, 그림(b)의 \(\vec{x}\)와 \(\vec{y}\)는 비교적 파란색 데이터들에 가까이 위치해있다. 두 점 사이 파란색 분포를 고려하면 그림(a)의 두 점은 그림 (b)의 두 점보다 상대적으로 더 멀리 떨어져있다고 볼 수 있다. 그렇다면 두 점 사이의 거리를 데이터의 분포, 즉 표준편차를 고려하여 계산해야 하는 것인데 이는 "표준편차의 정규화"를 통해 가능하다.
아래 왼쪽 그림에서 데이터의 분포를 고려하면 두 주황색 점보다 두 노란색 점 사이의 거리가 더 멀다고 판단해야 한다. 그런데 데이터의 분포를 고려하여 두 노란색 점 사이의 유클리드 거리를 계산하는 것은 매우 복잡한 일이다. 따라서 표준편차를 정규화하게 되는데, 오른쪽 그림처럼 표준편차가 정규화된 상태에서 유클리드 거리만 계산해도 두 노란색 점들 간의 거리가 더 멀다. 정규화한 상태에서 유클리드 거리를 구하면 결국 데이터의 분포(표준편차)를 고려한 거리가 되는 것이다. 이는 정규화 과정에서 이미 데이터의 분포(표준편차)를 고려하여 데이터(벡터) 공간을 변형시켰기 때문이다. - 마할라노비스 거리
이처럼 주어진 데이터의 분포에서 표준편차를 조사한 후, 이를 정규화하여 유클리드 거리를 계산한 것이 마할라노비스 거리이다. 데이터의 표준편차는 공분산 행렬(Covariance matrix, \(\Sigma\))과 관련이 있고, 그것을 다시 돌려 놓기 위한 행렬은(표준편차의 정규화) 공분산 행렬의 역행렬(\(\Sigma^{-1}\))로 표현할 수 있다. 따라서 두 점 \(u\)와 \(v\) 사이 마할라노비스 거리 공식은 다음과 같아진다.
(공분산 행렬과 그 역행렬의 수식적 의미에 대해서는 이 글을 쓰는데 참고한 다음 페이지에서 더 자세히 다루고 있다. 마할라노비스 거리)
$$d(u, v) = \sqrt{(u-v)\Sigma^{-1}(u-v)^T}$$
보통 마할라노비스 거리 공식에서 \(u\)는 각 데이터 포인트, \(v\)는 평균 포인트를 의미한다. 즉, 마할라노비스 거리는 각 데이터 샘플과 데이터의 평균 포인트 사이의 거리를 구하게 되는 것이다. 예를 들어, 특성(feature)이 키와 몸무게로 두 개인 데이터에서 \(u\)는 [키, 몸무게] (e.g. [178, 70]), \(v\)는 [키 평균, 몸무게 평균]이 될 수 있겠다. (10000개의 샘플이 있으면 10000개의 마할라노비스 거리가 나옴) 만약 모든 변수들이 독립이고(e.g. 키와 몸무게가 독립), 분산이 1로 정규화되어 있다면 \(\Sigma\) = \(I\)가 되어 마할라노비스 거리는 유클리드 거리와 같아진다.
( \(d(u, v) = \sqrt{(u-v)I^{-1}(u-v)^T} = \sqrt{(u-v)(u-v)} = \sqrt{(u_1-v_1)^2+...+(u_p-v_p)^2}\) )
(마할라노비스 거리를 계산할 때 MCD 공분산 행렬을 사용하는지, MLE 공분산 행렬을 사용하는지에 따라 MCD 기반, MLE기반 마할라노비스 거리로 나뉜다.)
실제로 위 마할라노비스 거리 등고선을 나타낸 그림에서 x1과 x2는 평균 포인트(분홍색 점)로부터 비슷한 거리에 있지만, 등고선을 보면 x2를 더 멀리 있는 점으로 보고 있음을 확인할 수 있다. MLE 기반 마할라노비스 거리 등고선에서 x1은 두번째 등고선 안에, x2는 네번째 등고선 안에 위치하고 있다. MCD 기반 마할라노비스 거리 등고선에서 x1은 첫번째 등고선 안에, x2는 다섯번째 등고선 안에 위치하고 있다. 이렇게 마할라노비스 거리는 데이터의 분포를 고려하여 두 점이 먼지, 가까운지를 판단한다.
scipy 공식문서
Minimum Covariance Determinant (MCD)
마할라노비스 거리를 계산하려면 공분산 행렬(Covariance matrix, \(\Sigma\))이 필요하다. 이때 empirical covariance(i.e. standard covariance, maximum likelihood covariance estimator), 즉 Maximum Likelihood Estimate(MLE)은 이상치에 매우 민감하기 때문에 결과적으로 MLE 기반 마할라노비스 거리도 이상치에 취약해지게 된다. 몇 개의 극단적 이상치들이 공분산 행렬을 망칠 수 있고, 합리적이지 않은 마할라노비스 거리가 측정될 수 있는 것이다. 따라서 이상치에 강한 공분산 측정법이 필요해 나온 개념이 바로 Minimum Covariance Determinant(MCD)이다. 즉, robust covariance estimate이라고 보면 되며 이상치에 강하기 때문에 결과적으로 MCD 기반 마할라노비스 거리는 데이터의 구조를 정확하게 반영하게 된다. MCD를 이용하면 소수의 이상치에 영향을 받지 않고 covariance, 더 나아가 마할라노비스 거리를 계산할 수 있다.
MCD는 이상치가 매우 많은 highly contaminated 데이터에서 공분산 행렬을 구하는데에 쓰일 수 있다(단, 이상치의 개수가 \(n_{samples} - n_{features} - 1 \over 2\) 개 이하일 때). MCD는 데이터의 가장 밀집된 부분을 기반으로 공분산을 계산하는 방법이라고 보면 되는데, 주어진 \(n_{samples}\)\(\times\)\(n_{features}\) 데이터에서 *공분산 행렬의 determinant(행렬식)를 최소로 만드는 \(n_{samples} + n_{features} + 1 \over 2\) 개의 데이터를 추출해 그것들만 이용하여 공분산을 계산하게 된다. 즉, empirical covariance matrix의 determinant를 최소로 만드는 샘플들을 추출해서 만든 pure한 subset으로 위치(location)와 공분산을 계산하는 것이다.
(*아래에서 설명할 scikit-learn의 EllipticEnvelope은 MCD 기반 마할라노비스 거리로 이상치를 탐색하는데, support_fraction 하이퍼파라미터를 통해 MCD 계산에 사용할 데이터의 비율을 설정할 수 있다. None으로 설정하면 위에서 말한것처럼 \(n_{samples} + n_{features} + 1 \over 2\) 개를 사용하게 된다.)
정확한 MCD 계산을 위해서는 전체 \(n_{samples}\) (n)개의 데이터 중 \(n_{samples} + n_{features} + 1 \over 2\) (h)개의 데이터를 반복해서 뽑아 공분산 행렬을 구하고, determinant를 계산해야 하므로 \(_{n}\mathrm{C}_{h}\) 번의 버거운 계산 작업이 필요하다. 이를 완화하고자 나온 방법이 **Fast MCD라고 한다.
(**scikit-learn EllipticEnvelope의 assume_centered 하이퍼파라미터를 False로 설정하면 FastMCD 알고리즘을 사용한다.)
그럼 이제 실제 데이터로 그린 MLE와 MCD 기반 마할라노비스 거리를 확인해보자.
위 그림은 MLE와 MCD 기반 마할라노비스 거리가 각각 이상치에 얼마나 영향을 받는지를 보여준다. MCD 기반 마할라노비스 거리는 정상치인 검은 점들에 더 잘 들어맞는 것이 보이며, MLE 기반 마할라노비스 거리의 경우 이상치인 빨간 점들에 더 영향을 받고 있음이 보인다.
위 그림에서도 MCD 기반 마할라노비스 거리를 사용했을 때 정상치 분포로부터 이상치 분포가 더 잘 분리되어 있음을 확인할 수 있다. 정리하자면 MLE 기반 마할라노비스 거리를 사용하면 오염된 분포(contaminating distribution)에서 추출된 샘플들을 가우시안 분포에서 추출된 샘플들로부터 구별하는 것이 어려워지는 반면, MCD 기반 마할라노비스 거리를 사용하면 두 그룹은 구별이 가능해진다는 것이다.
아래는 오염된 가우시안 분포 데이터셋에서 위치와 공분산을 측정했을 때, 각 측정 방법에서의 측정 오류를 나타낸 것이다.
- The mean and the empirical covariance of the full dataset, which break down as soon as there are outliers in the data set (Full data set)
- The robust MCD, that has a low error provided \(n_{samples}\) > \(5n_{features}\) (MCD robust estimator)
- The mean and the empirical covariance of the observations that are known to be good ones. This can be considered as a “perfect” MCD estimation, so one can trust our implementation by comparing to this case. (Pure data set)
scikit-learn EllipticEnvelope
이상치를 탐색하는 보편적인 방법 중 하나는 규칙적인 데이터가 명확한 분포에서 왔다고 가정하는 것이다(e.g. 정규분포를 이루는 데이터). 이러한 가정으로부터 우리는 데이터가 어떤 특정한 모양, 형태를 이루고 있다고 보려하며, 이 모양에서 멀리 벗어나있는 관측치를 이상치로 판단하게 된다.
예를 들어 두 개의 특성이 있는 데이터셋에서 두 특성 모두 가우시안 분포를 따른다면 특성공간은 "다차원 가우시안 분포"를 띠며, 이 분포에 대한 정보로 분포로부터 멀리 떨어져있는 값(이상치)을 구분해낼 수 있다. 이 접근 방식은 정상치 범위를 다루는 타원체를 정의하고, 그 타원체 밖에 위치한 값들을 이상치로 판별함으로써 실현할 수 있다. 이러한 방식으로 다변량 데이터에서 이상치를 찾아내도록 한 것이 바로 MCD라고 할 수 있다.
- "The Minimum Covariance Determinant (MCD) method is a highly robust estimator of multivariate location and scatter, for which a fast algorithm is available. […] It also serves as a convenient and efficient tool for outlier detection". Minimum Covariance Determinant and Extensions, 2017
이 MCD method를 구현해놓은 것이 scikit-learn의 covariance.EllipticEnvelope인데 이는 가우시안 분포 데이터에서 이상치를 탐색하는 데에 쓰인다. 때문에 데이터가 unimodal하지 않은 경우에는 성능이 저하될 수 있다. EllipticEnvelope은 MCD를 데이터에 fit시켜 MCD 기반 마할라노비스 거리 타원(ellipse)을 데이터 중앙의 포인트들에 맞춘다. MCD 타원을 중앙 포인트들에 맞추는 과정에서 중앙에서 멀리 떨어진 포인트(이상치)들은 무시된다. 즉, EllipticEnvelope은 MCD를 사용해 정상치들의 위치와 공분산, 결과적으로 마할라노비스 거리를 이상치의 영향을 받지 않고 robust하게 측정하는 것이다. 이렇게 계산한 마할라노비스 거리는 outlyingness의 기준을 정하는데 쓰이게 된다. - 2.7.3.1. Fitting an elliptic envelope
- covariance.EllipticEnvelope assumes the data is Gaussian and learns an ellipse. It thus degrades when the data is not unimodal.
공분산 측정을 통한 이상치 탐색은 고차원 데이터셋에서 잘 작동하지 않을 수 있다고 한다. 공식문서에 따르면 \(n_{samples} > {n_{features}}^2\) 인 경우에만 사용가능한 것 같다.
Outlier detection from covariance estimation may break or not perform well in high-dimensional settings. In particular, one will always take care to work with n_samples > n_features ** 2. sklearn.covariance.EllipticEnvelope
아래는 scikit-learn의 이상치 탐색 알고리즘들을 비교한 그림이다. 맨 왼쪽 Robust covariance가 EllipticEnvelope을 사용한 이상치 탐색 결과이다. MCD 기반 마할라노비스 거리 타원 안에 정상치들이 구분되어 있는 것이 보인다.
Scikit-learn 공식문서
- 2.7. Novelty and Outlier Detection - 2.7.3.1. Fitting an elliptic envelope
- sklearn.covariance.EllipticEnvelope
- Robust covariance estimation and Mahalanobis distances relevance
- Robust vs Empirical covariance estimate
- 2.6. Covariance estimation
- Comparing anomaly detection algorithms for outlier detection on toy datasets
Reference
3. 4 Automatic Outlier Detection Algorithms in Python
5. [데이터분석 정리] Mahalanobis 거리와 MCD 개인적 정리
