Paper
Abstract
OUTRES는 outlier detection in high-dimensional data에서의 문제를 해결하기 위해 observation 마다 relevant subspace를 찾는 (Local) Subspace Outlier Mining 방법론 입니다. 이 때, relevant subspace는 SOD와 다르게 변수 조합이 여러개인 multiple subspace가 제공됩니다. 이 때문에 다양한 관점 (multiple views)에서 object의 outlierness를 탐지할 수 있습니다. 그런데 multiple subspace의 차원 크기가 각기 달라 outlier score의 bias가 일어날 수 있기 때문에 OUTRES는 이를 adaptive 하게 조정하는 scoring 함수 및 combination 함수를 제안합니다. 본문에서 주요하게 다룰 내용은 (1) Relevant subspace search (2) Adaptive outlierness in subspaces 입니다.
Introduction
Outlier detection의 기본 아이디어는 전체 데이터셋에 어울리지 않는, 다른 매커니즘을 통해 발생한 것으로 추측되는, object들을 발견하는 것입니다. 따라서 대부분의 outlier detection 방법론은 object가 다른 (local) objects와 떨어진 거리 혹은 density를 이용하여 outlierness함을 나타내는 outlier score를 계산합니다. 그런데 이전 글 [Outlier Detection] Feature Bagging 리뷰 에서 살펴본 것과 같이 High-dimensional 데이터에선 두가지 문제점이 발생했습니다. 첫째, 'Data sparsity'. 둘째, 'Local feature relevance' 입니다. (자세한 설명은 이전 글을 참고바랍니다).
OUTRES는 위의 문제를 해결하는 방안으로 mulitple relevant subspace search for each observation을 제안합니다. 이 방법은 object $o$의 이웃한 점들을 이용해 일정한 기준을 만족하는 여러개의 relevant subspace를 찾습니다. 이렇게 구해진 multiple relevant subspace에 대해 outlier score를 계산합니다. score는 $o$의 이웃한 점들을 고려하여 추정한 local density와 이웃한 점들과 떨어진 정도인 local deviation의 비율에 기반하여 산출됩니다. 각 subspace에 대하여 $o$의 outlier score를 계산한 후 이 값들을 곱셈 (product)으로 combination 하여 최종 outlier score를 도출합니다.
이 방법은 점 $o$에 대한 relevant subspace가 여러개 제안되기 때문에 다양한 관점에서 $o$의 outlierness를 관측할 수 있다는 장점이 있습니다. 하지만 relevant subspace들의 차원이 각기 다르기 때문에 이를 고려하지 않고 outlier score를 계산할 경우 bias가 발생할 수 있습니다. 차원이 커질수록 object간의 거리가 멀어지므로[2] object의 density와 deviation을 기반으로 계산되는 outlier score가 고차원에서 과대계상 될 수 있기 때문입니다. OUTRES는 이 문제를 극복하기 위해 차원의 크기를 고려하는 adaptive outlierness in subspaces 방법을 제안합니다.
Basic Idea
(1) Relevant subspace search
(1-1) Relevant subspace test
OUTRES는 object $o$와 그 이웃한 점들을 distinguish 할 수 있는, 즉 대다수의 점들은 밀집되어 있고 소수의 object는 이들과 떨어져 있어 그 차이가 극명한 subspace를 $o$의 relevant subspace로 채택합니다. 반면 irrelevant subspace는 $o$와 그 이웃한 점들이 uniformly distributed 되어있는 subspace로 정의합니다. 왜냐하면 object들이 uniformly distributed 되어 있을 경우 object간의 거리가 모두 비슷해지기 때문에 outlying behavior를 관측할 수 없기 때문입니다.
아래 Figure 1을 통해 relevant subspace와 irrelevant subspace의 대략적인 양상을 확인할 수 있습니다. Subspace {1,2}, {3,4}의 경우 대다수의 object들이 밀집되어 있고 소수의 (하나의) object만 떨어져 있기 때문에 relevant subspace로 분류됩니다. 반면 {1,2,3}의 경우 모든 점들이 uniformly distributed 되어있기 때문에 irrelevant subspace로 분류합니다. ({1},{2}는 밀집되어 있지만 소수의 object가 떨어져있지 않기 때문에 relevant subspace에 포함되지 않습니다. 하지만 irrelevant subspace도 아니기 때문에 score 계산시에 제거하지 않습니다. 이에 관한 자세한 설명은 뒤의 "Adaptive outlierness in subspaces" 섹션에서 다룰 것입니다.)
OUTRES는 위의 {1,2,3}과 같이 uniformly distributed된 irrelevant subspace를 제거하는 걸 목적으로 합니다. 판단 방법으로 statistical significance test를 이용합니다. $o$의 이웃한 점들을 sample로 하는 subspace $S$에 대해 uniform 분포를 가정하고 유의수준 $\alpha$를 설정한 다음 Kolmogorov-Smirnov goodness of fit test[3]를 통해 해당 $S$가 uniform 분포인지 아닌지를 판단합니다. 이 test를 통해 uniform 분포가 아니라고 판단된 subspace들을 set of relevant subspace로 채택합니다.
(1-2) Subspace search algorithm
위 test를 모든 가능한 subspace에 대하여 시행할 수도 있지만, 전체 변수개수가 $D$일 때, 이는 $2^{|D|}-1$의 경우의 수 만큼의 계산이 필요하므로 상당한 computational cost가 요구됩니다. 따라서 OUTRES는 이를 극복하기 위해 approximative 한 subspace search 방법을 제안합니다.
OUTRES는 subspace search algorithm으로 Bottom-up based on pruning heuristic method를 차용합니다. Bottom-up method는1-dimensional subspace부터 차원을 하나씩 늘려가며 relevant subspace를 찾습니다. 현재 단계의 subspace들 중 relevant subspace test를 통과한 subspace에 대해서만 차원 (변수)을 추가하여 새로운 relevant subspace search를 진행합니다. 이 과정을 반복하며 차원을 늘려갑니다. 이에 대한 직관적인 설명을 돕는 그림을 Figure 2. 에서 확인할 수 있습니다.
그림에 X 로 표시된 overall dense subspaces는 uniformly distributed 되어있진 않지만 소수의 object가 떨어져 있지도 않은 그저 밀집된 subspace를 지칭합니다. 이러한 subspace는 최종 score 계산에 있어 영향을 주지 않기 때문에 (이는 "Adaptive outlierness in subspaces" 파트에서 설명될 것입니다) subspace serach 과정에서 제거하지 않고 set of relevant subspace에 포함합니다.
이러한 Apriori-like algorithm[4]이 가능한 이유는 차원이 늘어남에 따라 object간의 거리가 멀어져 scattered 되는 경향이 발생하기 때문입니다[2]. 따라서 더 낮은 차원에서 uniformly distributed 되어 있다면 차원이 추가되었을 때 역시 uniformly distributed 되어 있을 거란 직관에 의해 이러한 subspace search algorithm이 고안되었습니다.
(2) Adaptive outlierness in subspaces
위 방법을 통해 얻은 set of relevant subspace에 대해 outlier score를 계산합니다. Outlier score는 $o$의 local density와 local deviation의 비율에 기반하여 도출됩니다.
local density 는 kernel density estimator에 기반하여 계산되고 local deviation은 $o$의 이웃한 점들에 대해 계산한 local density를 이용해 $o$가 이웃한 점들의 density와 얼마나 차이가 나는지를 측정합니다.
이 때, subspace들의 차원이 각기 다름에 따라 score의 bias 문제가 발생할 수 있습니다. OUTRES는 이를 극복하기 위해 local density 계산시에 사용되는 이웃한 점들을 구성하는 기준 (neighborhood boundary)을 차원 크기에 따라 adaptive하게 조정하는 방법을 제안합니다. 이에 따라 boundary안에 존재할 것으로 기대되는 이웃한 점들의 개수가 차원크기가 변해도 일정하게 유지됩니다. (이에 대한 자세한 설명은 Methods 파트에서 다룹니다.)
Methods
(1) Relevant subspace search
Relevant subspace를 찾기 위해선 $o$의 이웃한 점에 대한 정의가 필요합니다. OUTRES는 주어진 subspace $S$의 차원 크기를 고려하는 "adaptive neihborhood $\mathcal{AN}(o,S)$"를 정의합니다.
$\mathcal{AN}(o,S) = \{p | dist_{S}(o,p) \leq \epsilon(|S|)\}$
$\epsilon(|S|)$ 함수는 뒤에 설명할 local density 계산에서의 개념을 차용합니다. (자세한 설명은 뒤의 "Adaptive outlierness in subspaces" 섹션에서 제공됩니다.) 이에 따라 subspace의 차원 크기가 커질 때, neighborhood boundary 역시 조정되어 기대되는 neighborhood의 개수가 일정하게 유지됩니다.
$\mathcal{AN}(o,S)$를 이용하여 relevant subspace test가 시행됩니다.
$H_{0}$: $S$ is distributed uniformly random in $\mathcal{N}(o,S)$
$H_{1}$: $S$ is distributed non-uniformly in $\mathcal{N}(o,S)$
statistcal test는 Kolmogorov-Smirnov goodness of fit test[3]에 기반하여 계산됩니다. 이 때, 1종 오류에 대한 유의수준 $\alpha$는 귀무가설을 기각할 확률을 낮추기 위해 작은 값으로 설정되길 권장합니다. (e.g., $\alpha = 0.01$)
Basic idea 섹션에서 살펴본 subspace search 알고리즘에 따라 각 subspace의 relevantness를 test하여 통과한 subspace들로 최종 set of relevant susbapces를 도출합니다.
$RS(o) = \{S \in \mathcal{P}(D) | S \text{passes } H_{1}\}$
(2) Adaptive outlierness in subspaces
Adaptive outlierness 계산을 위해 local density 와 local deviation을 정의합니다. $o$의 모든 relevant subspace에 대해 계산한 score를 곱셈 (product)으로 combination하여 최종 outlier score로 도출합니다.
Local density는 kernel density estimator를 이용하여 추정됩니다. kernel function으로는 Epanechnikov Kernel을 사용합니다.
$K_{e}(x) = (1-x)^{2}, \quad x<1$
이를 이용한 (local) density는 다음과 같습니다.
$den(o,S) = {1\over |DB|}\sum_{p\in DB}K_{e}\left({dist_{S}(o,p)\over h}\right)$
Epanechikov Kernel은 function argument $x$의 범위를 $x < 1$로 제한하여 density estimation에 사용되는 object가 전체 중 일부로 한정됩니다 (거리가 $h$보다 큰 $p$는 계산에서 제외됩니다). 따라서 object $o$의 이웃한 점들 (거리가 $h$보다 작은)에 대한 local density estimation 결과를 얻습니다. 이 때, 차원 크기에 따른 이웃한 점들의 범위 조정은 bandwidth $h$로 이루어집니다. $h$는 차원크기에 따라 optimal한 (Mean Integrated Squared Error가 최소인) 값이 자동으로 계산됩니다.
$h_{optimal}(d) = \left({8\cdot\Gamma(d/2 + 1)\over \pi^{d/2}}\cdot (d+4)\cdot (2\sqrt{\pi})^{d}\right)\cdot n^{-1\over d+4}$, where $n = |DB|$
* $h_{optimal}(d)$ 값을 이용해 $\epsilon(|S|)$ 을 정의합니다
$\epsilon(|S|) = \epsilon\cdot{h_{optimal}(|S|)\over h_{optimal}(2)}$
이 때, $\epsilon$ 값은 user define parameter로 상황에 맞게 설정하길 권장합니다. ($\epsilon$ = 15 is recommended)
Local object deviation은 $o$의 density와 이 density estimation에 사용된 이웃한 점들의 density와의 차이에 기반하여 계산됩니다.
- $\mu$: the average density in the neighborhood of object $o$
- $\sigma$: the standard deviation of $den(o,S)$ in the neighbor hood of object $o$
$dev(o,S) = {\mu-den(o,S)\over 2\cdot\sigma}$
이렇게 deviation을 구함으로써 $o$의 density가 이웃한 점들에 비해 얼마나 낮은 값을 갖는지 알 수 있습니다. 이를 이용해 score 계산에 사용할 $o$를 다음의 기준에 따라 제한합니다.
$den(o,S) < \mu-2\cdot\sigma \quad \iff dev(o,s)>1$
위 조건을 만족하는 $o$는 이웃한 점들의 density에 비해 현격히 낮은 density를 보이기 때문에 이웃한 나머지 objec들과 highly deviating 한다는 것을 알 수 있습니다. 따라서 위 조건을 만족하는 $o$만을 score계산에 고려합니다.
Adaptive Outlierness는 위의 local density와 local object deviation의 비율로 계산됩니다.
$score(o,S) = \begin{cases} {den(o,S)\over dev(o,S)}, \quad \text{if }dev(o,S)\geq 1\\ 1, \quad \text{else} \end{cases}$
이 score가 0에 가까울 수록 outlierness 함을 의미하며 반대로 1에 가까울수록 outlierness 하지 않음을 의미합니다.
최종 Outlier score는 위의 score를 $o$가 속한 모든 relevant subspace에 대해 계산한 후 곱하여 도출됩니다.
-
$RS(o)$: set of relevant subspace of $o$
$r(o) = \prod_{S\in RS(o)}score(o,S)$
score combination 방법으로 곱셈 (product)를 사용했기 때문에 score 값이 1일 경우 최종 score 계산에 어떠한 영향도 미치지 않습니다. 따라서 $dev(o,S)\geq 1$을 만족하지 않는 경우는 최종 score에 영향을 주지 않는 걸 알 수 있습니다.
이전 섹션 "Relevant subspace search"에서 확인한 overall dense subspace의 경우 모든 점들이 밀집되어 있기 때문에 $dev(o,S)$값이 낮아 최종 score 계산에 영향을 주지 않습니다. 이를 통해 해당 subspace를 set of relevant subspace에 포함시켜도 문제 없다는 걸 알 수 있습니다.
최종 알고리즘은 다음과 같습니다.
Discussion
OUTRES의 outlier detection 성능은 [1]에서 확인하실 수 있습니다.
* 인풋 파라미터
- $\epsilon$: neighborhood boundary parameter
- $\epsilon$ = 15 is recommended
- $\alpha$: relevant subspace test에서의 유의수준
- $\alpha$ = 0.01 is recommended
OUTRES의 장점은 다음과 같습니다.
- Mutiple relevant subspace를 찾기 때문에 다양한 관점에서 $o$의 outlierness를 관측할 수 있다.
- Relevant subspace test와 outlier score에 계산에 사용되는 $o$의 이웃한 점들을 차원크기에 따라 adaptive하게 조정하여 선정하기 때문에 차원크기에 따른 bias를 방지한다.
- 차원이 커짐에 따라 data가 sparse 해지는 특성을 이용해 Apriori-like algorithm을 적용할 수 있기 때문에 계산량이 비교적 적다.
Reference
[1] Müller, E., Schiffer, M., & Seidl, T. (2011, April). Statistical selection of relevant subspace projections for outlier ranking. In 2011 IEEE 27th international conference on data engineering (pp. 434-445). IEEE.
[2] Beyer, K., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999, January). When is “nearest neighbor” meaningful?. In International conference on database theory (pp. 217-235). Springer, Berlin, Heidelberg.
[3] Stephens, M. A. (1970). Use of the Kolmogorov–Smirnov, Cramer–Von Mises and related statistics without extensive tables. Journal of the Royal Statistical Society: Series B (Methodological), 32(1), 115-122.
[4] Agrawal, R., & Srikant, R. (1994, September). Fast algorithms for mining association rules. In Proc. 20th int. conf. very large data bases, VLDB (Vol. 1215, pp. 487-499).
