Paper
www.dbs.ifi.lmu.de/~zimek/publications/PAKDD2009/pakdd09-SOD.pdf
Introduction
SOD (Subspace Outlier Degree)는 High-dimensional 데이터에서 outlier detection의 문제를 극복하기 위해 각 observation에 대한 relevant subspace를 탐색하여 outlier score (degree)를 계산하는 방법을 제안합니다.
Outlier detection의 기본 아이디어는 전체 데이터셋에 어울리지 않는, 다른 매커니즘을 통해 발생한 것으로 추측되는, object들을 발견하는 것입니다. 따라서 대부분의 outlier detection 방법론은 object가 다른 (local) objects와 떨어진 거리 혹은 density를 이용하여 outlierness함을 나타내는 outlier score를 계산합니다. 그런데 이전 글 [Outlier Detection] Feature Bagging 리뷰 에서 살펴본 것과 같이 High-dimensional 데이터에선 두가지 문제점이 발생했습니다. 첫째, 'Data sparsity'. 둘째, 'Local feature relevance' (자세한 설명은 이전 글을 참고바랍니다).
SOD는 Feature Bagging과 달리 subspace를 random하게 찾지 않고 일정한 기준을 세워 relevant subspace를 select 하는 방법을 제안합니다. 이 때 제안된 relevant subspace는 observation 마다 오직 하나만 존재합니다 (singe subspace). relevant subspace는 observation의 상황에 따라 다르게 제공됩니다. 따라서 각 observation에 대한 outlier score 는 각기 다르게 제공된 relevant subspace에 대해 계산됩니다. Outlier score는 기존의 classical outlier detection 모형을 사용하지 않고 SOD의 독작적인 계산법에 의해 산출됩니다. 이렇게 각 observation의 상황을 고려하여 각기 다른 relevant subspace를 제공하는 방법을 (Local) Subspace Outlier Mining 이라고 부릅니다. (모든 observation에 대해 공통된 relevant subspace를 제공하는 방법은 (Global) Subspace Search 라고 불립니다.[2])
본문에선 SOD가 relevant subspace를 선택하는 기준과 outlier score를 계산하는 방식에 대해 설명드리도록 하겠습니다.
Basic Idea
이 섹션에선 SOD가 작동하는 방식을 직관적으로 설명합니다. 보다 구체적인 설명은 뒤의 Method 파트에서 다룰 것입니다.
(i) Relevant subspace selection
High-dimensional Outlier detection에서 relevant (or interesting) subspace는 어떠한 subspace에서 object들이 uniform 하게 distributed 되어있지 않고 소수의 object들이 다수의 object들과 극명한 차이를 보이는 subspace를 상정합니다. 즉, few and different한 경향이 잘 관측되는 subspace를 relevant subspace라고 생각합니다. SOD 또한 이러한 아이디어에 기반하여 relevant subspace를 찾습니다.
SOD는 relevant subspace 를 찾는 기준으로 이웃한 점 (neighborhoods)들을 1-dimensional space (하나의 변수)에 projection 내렸을 때의 '분산 (Variance)'을 이용합니다. 아래 Figure 1. 의 예를 보면, 점 $o$ 가 $\{A_{1},A_{2}\}$ 공간에선 이웃한 $x$ 점들과 떨어진 정도가 극명하지 않기 때문에 outlier로 탐지되지 않습니다. 하지만 이 object들을 $\{A_{1}\}$에 projection 내렸을 때 밀집하여 모여있는 점 $x$ 들과 이웃한 점들로 부터 떨어져 있는 점 $o$ 의 deviation (차이)가 뚜렷하게 관측되기 때문에 outlier로 탐지될 수 있습니다.
위의 $A_{1}$ 처럼 점 $o$ 의 이웃한 점들을 1차원 공간에 projection 내렸을 때의 퍼진 정도가 작은. 즉, 분산이 작은 변수를 relevant attribute로 채택합니다. 왜냐하면 Figure 1의 예제와 같이, 밀집한 와중에 떨어져있는 소수의 점이 있다면 그 점이 다른 점들과는 다른 매커니즘을 가지는 outlier일 경향이 높기 때문입니다. 반면, $A_{2}$의 경우와 같이 점 $o$ 의 이웃한 점들을 projection 내렸을 때 그 분산이 큰 변수는 해당 차원에서 object들이 uniformly distributed 되어있다고 생각하여 irrelevant attribute로 상정합니다. 왜냐하면 object들 간에 deviation이 명확하게 나타나지 않기 때문입니다. 그리하여 최종적으로 전체 attribute 중 irrelvant atrributes를 제외한 나머지 변수들 (relevant attributes)의 모임을 relevant subspace로 정의합니다.
(ii) Outlying degree computation
위 방법에 따러 얻은 relevant subspace때 outlying degree (outlir score) 계산은 다음과 같이 이루어집니다.
Figure 2 의 예를 통해 보면, 이 경우는 점 $o$ 의 relevant subspace로 전체 feature space $\{A_{1}, A_{2}, A_{3}\}$ 중 $\{A_{1}, A_{3}\}$가 채택된 상황입니다. 이 때, 사용된 object 들은 점 $o$ 의 이웃한 점들의 모임인 $R(o)$ 입니다. 점 $o$ 의 outlying degree는 $\{A_{1}$와 $A_{3}\}$ 변수 각각의 평균값인 $\mu^{R(o)}_{1}$, $\mu^{R(o)}_{3}$로 생성한 hyperplane $\mathcal{H}(R(o))$ 와 점 $o$ 간의 거리인 $dist(\mathcal{H}(R(o),p)$ 를 기반으로 계산됩니다.
즉, "점 $o$ 의 outlier score는 $o$ 의 이웃한 점들 $R(o)$를 이용해 계산한 분산값이 작은 relevant subspace들에 대해 산출된다. score 계산 방식은 relevant subspace에 해당하는 각 변수들의 평균값을 구성요소로 하는 hyperplane $\mathcal{H}(R(o))$와 점 $o$ 간의 거리 측정으로 도출된다. 거리가 멀수록 outlier score가 높고 outlierness 하다고 여긴다."라고 요약할 수 있습니다.
Method
(0) Notation
- $\mathcal{D}\subseteq \mathbb{R}^{d}$: a database of $n$ points in a $d$ -dimensional feature space
(i) Reference set
SOD는 점 $o$ 의 relevant subspace search와 outlier degree 계산 모두에 $o$ 와 이웃한 점들의 모임인 reference set $R(o)$ 만을 이용합니다. 이 섹션에선 $R(o)$ 구성 기준을 설명합니다.
Curse of dimensionality로 인해 high-dimensional 데이터에서 이웃한 점들간의 거리는 무의미해집니다 [3]. 그래서 일반적인 k-nearest neighbor 방법을 이용하기 어렵습니다. 이를 극복하기위해 SOD는 Shared Nearest Neighbor (SNN) 방법을 차용하여 이웃한 점들을 찾는데 적용합니다. SNN은 high-dimensional 데이터에서 이웃한 점들간의 '거리'는 의미가 없지만 '거리의 순위'는 여전히 의미있다는 점에 착안한 방법입니다.
-
$N_{k}(p) \subseteq \mathcal{D}$: the k-nearest neighbors of $p\in \mathcal{D}$ w.r.t. the distance function $dist$
-
$Card()$: computing cardinality of the input set
The shared nearest neighbor similarity between two points $p, q\in\mathcal{D}$:
$sim_{SNN}(p,q) = Card(N_{k}(p)\cap N_{k}(q))$
즉, 점 $p$왕 $q$의 k-nearest neighbors 중 중복되는 이웃한 점들의 개수를 $sim_{SNN}(p,q)$로 설정하는 것입니다. 이 때, reference set for object $p$인 $R(p)$는 $sim_{SNN}$을 user define parameter $\ell$만큼 그 개수를 제한하여 $\ell$개의 중복된 nearest neighbors 를 최종 이웃한 점으로 채택합니다.
-
$R(p)$: the set of $\ell$-nearest neighbors of $p$ using $sim_{SNN}$
-
$\ell$: specifies the size of the reference sets (an user define parameter)
(ii) Relevant subspace search
object $o$ 에 대한 relevant subspace search는 $R(o)$에 속한 objects 만을 이용해 full-dimension 에서의 분산 $VAR^{R(p)}$와 predefined coeeficient $\alpha$의 곱과 각 attribute에 projection 내렸을 때의 분산 $var^{(R(p)}_{i}$ 을 비교해 $var^{(R(p)}_{i}$ 값이 작은 attribute만을 relevatn subspace로 채택합니다.
아래는 위 설명을 수식으로 표현하기 위해 필요한 notation 입니다.
-
$S$: a subspace (subset of attributes)
-
$VAR^{S}\in \mathbb{R}$: The toal variance of $S$
-
$\mu^{S}$: The mean value of $S$
-
dist(p,q): the distance function between $p$ and $q$
-
Card(S): the cardinality of the set $S$
for any given Subspace $S$에 대한 분산을 다음과 같이 정의합니다.
$VAR^{S} = {\sum_{p\in S}dist(p,\mu^{s})^2 \over Card(S)}$
$S$를 for an attribute $i$에 projection 내렸을 때의 분산을 다음과 같이 정의합니다.
-
$var^{S}_{i}\in\mathbb{R}$: the variance along an attribute $i$
$var^{S}_{i}={\sum_{p\in S}(dist(p_{i},\mu^{s}_{i}))^2 \over Card(S)}$
$R(o)$에 대한 relevant subspace를 지칭하는 벡터를 $v^{R(p)}$로 정의합니다.
-
$v^{R(p)}\in\mathbb{R}^{d}$: the subspace defining vector of a reference set $R(p)$
$v^{R(p)}$의 i번째 component는 아래의 조건에 따라 결정됩니다.
$v^{R(p)}_{i} =$ $\begin{cases}1, \quad \text{if } var^{R(p)}_{i} < \alpha {VAR^{R(p)}\over d} \\ 0, \quad \text{else} \end{cases}$
즉, $var^{R(p)}_{i} < \alpha {VAR^{R(p)}\over d}$ 를 만족하는 attribute $i$만을 relevant subspace로 채택합니다.
(iii) Subspace outlier degree computation
이 섹션에선 위에서 얻은 reference set $R(o)$와 이에 해당하는 relevant subspace를 이용해 object $o$의 outlier degree 계산을 설명합니다.
점 $o$의 reference set $R(o)$에 대한 relevant subspace를 지칭하는 $v^{(R(o)}$와 $R(o)$에 대한 각 attribute에서의 평균값을 이용해 subspace hyperplane $\mathcal{H}(R(o))$를 정의합니다.
-
$\mathcal{H}(R(o))$: the subspace hyperplane
$\mathcal{H}(R(o)) = (\mu^{R(o)},v^{R(o)})$
object $o$와 subspace hyperplane $\mathcal{H}(R(o))$ 간의 떨어진 거리를 다음과 같이 정의합니다.
-
$dist(o,\mathcal{H}(S))$: the distance between object $o$ and the subspace hyperplane $\mathcal{H}(R(p))$
$dist(o,\mathcal{H}(S)) = \sqrt{\sum_{i=1}^{d}v^{S}_{i} \cdot (o_{i},\mu_{i}^{S})^2}$
위의 정의들을 이용하여 Subspace Outlier Degree of object $o$를 정의합니다.
Subspace Outlier Degree:
$SOD_{R(o)}(o):={dist(o,\mathcal{H}(R(o)))\over \|v^{R(o)}\|_{1}}$
*차원의 크기가 커짐에 따라 object간의 거리가 커지기 때문에 이를 방지하고자 relevant subspace의 차원 크기로 $o$와 $H(R(o))$의 거리를 scaling 해줍니다.
Discussion
SOD의 outlier detection 성능은 [1]에서 확인하실 수 있습니다.
* 인풋 파라미터
- $k$: the number of nearest neighbors that are considered to compute the shared nearest neighbor similarity
- 모형에 큰 영향을 주지 않는다. 적당히 큰 값을 설정해 사용하길 권장한다
- $\ell$: the size of the reference sets
- $k$보다 작은 값으로 설정해야 한다.
- 너무 작은 값으로 설정하지 않길 권장한다.
- $\alpha$: a threshold to decide about the significance of an attribute
- 저자는 $\alpha = 0.8$ 을 권장
SOD의 장점은 다음과 같습니다.
- observation 마다 relevant subspace를 제안해준다.
- 1-dimensional projection만 고려하기 때문에 계산량이 적다.
SOD의 단점은 다음과 같이 요약할 수 있습니다.
- 1-dimensional projection만 고려하기 때문에 변수들간의 interaction으로 발생하는 outlying behavior를 탐지할 수 없다.
Reference
[1] Kriegel, H. P., Kröger, P., Schubert, E., & Zimek, A. (2009, April). Outlier detection in axis-parallel subspaces of high dimensional data. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (pp. 831-838). Springer, Berlin, Heidelberg.
[2] Nguyen, H. V., Müller, E., Vreeken, J., Keller, F., & Böhm, K. (2013, May). CMI: An information-theoretic contrast measure for enhancing subspace cluster and outlier detection. In Proceedings of the 2013 SIAM International Conference on Data Mining (pp. 198-206). Society for Industrial and Applied Mathematics.
[3] 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.
