Paper
Abstract
$OutRank$는 observation마다 여러개의 relevant subspace를 찾아 outlier score를 계산하는 (local) subspace outlier mining 방법입니다. $OutRank$는 relevant subspace search 방법으로 기존 subspace clustering 테크닉을 차용합니다. Subspace clustering을 통해 얻은 set of relevant subspace 중 $o$가 clustered 되어있는 subspace에 대해서만 outlier score를 계산하고 이를 combination하여 최종 Outlier score를 도출합니다. 이 때, subspace clustering을 통해 얻은 set of relevant subspace에 대한 outlier score 계산시 발생할 수 있는 문제를 극복하기위해 subspace와 cluster의 simliarity를 고려하는 outlier scoring function 세가지를 제안합니다. $OutRank$는 특정 subspace clustering 방법을 이용하는 것이 아닌 subspace clustering을 Outlier detection에 사용할 수 있는 전반적인 framework을 제공합니다.
Introduction
Outlier detection의 기본 아이디어는 전체 데이터셋에 어울리지 않는, 다른 매커니즘을 통해 발생한 것으로 추측되는, object들을 발견하는 것입니다. 따라서 대부분의 outlier detection 방법론은 object가 다른 (local) objects와 떨어진 거리 혹은 density를 이용하여 outlierness함을 나타내는 outlier score를 계산합니다. 그런데 이전 글 [Outlier Detection] Feature Bagging 리뷰 에서 살펴본 것과 같이 High-dimensional 데이터에선 두가지 문제점이 발생했습니다. 첫째, 'Data sparsity'. 둘째, 'Local feature relevance' 입니다. (자세한 설명은 이전 글을 참고바랍니다).
Basci Idea
(1) Relevant subspace search
$OutRank$는 subspace clustering 테크닉을 이용해 $o$의 set of relevant subspace를 찾습니다. Subspace clustering은 전체 데이터셋에 대하여 cluster가 발생하는 모든 가능한 subspace를 탐지합니다. $OutRank$는 이 중 $o$가 속해있는 cluster에 해당하는 subspace들을 $o$의 set of relevant subspace로 채택합니다. Subspace clustering을 이용해 set of relevant subspace를 찾는 아이디어는 다음과 같습니다. 어떤 object가 속해있는 cluster가 많고 그 cluster에서의 밀집도를 나타내는 regularity가 높은 경우 정상 object인 경향이 높고 속한 cluster가 적고 regularity가 낮은 object는 outlier일 경향이 높을 것이라는 직관에 기반합니다. 따라서 $OutRank$는 $o$의 regularity를 기반으로 outlier score를 계산합니다. Subspace clustering을 통해 얻어지는 일반적인 결과인 SCR은 다음과 같이 나타낼 수 있습니다.
$$ \begin{align*} SCR = {(C_{1}, S_{1}),\cdots, (C_{k}, S_{K})} \end{align*} $$
-
이 때, $C_{i}$는 해당 subspace $S_{i}$에서의 set of clusters를 나타냅니다.
이를 이용해 각 observation 마다의 relevant subspace는 $\{(C,S)\in SCR | o\in C\}$로 표현할 수 있습니다.
(2) Outlier scoring functions
$OutRank$의 outlier scoring function을 포괄적으로 나타내면 다음과 같습니다.
$$score(o) = \sum_{\{(C,S)\in SCR | o\in C\}} evidence(o, (C, S), SCR)$$
이 때, $evidence$는 $o$의 regularity를 나타냅니다. $score(o)$는 $o$의 모든 set of relevant subspace에 대한 regularity를 combination하여 얻은 최종 regularity score입니다. Outlier score는 1 - $score(o)$를 통해 얻어집니다.
Outlier score 계산시 주의하여야할 사항은 "redundacy of subspaces"입니다. Subspace cluster는 종종 overlap 하는 경향이 있습니다. 즉, 어떤 subspace cluster $(C_{i}, S_{i})$와 다른 subspace cluster $(C_{j}, S_{j})$가 공통된 objects를 포함하는 경우를 뜻합니다. 이렇게 overlap된 subspace cluster가 많은 경우 regularity (outlier score)의 bias가 발생할 수 있습니다. 이러한 overlap 현상은 subspace cluster가 많은 수의 공통된 변수를 공유할 때 발생하는 경향이 높습니다. 극단적인 경우 다음과 같은 monotonicity property를 보이기도 합니다.
$$ (C, S) \in SCR \Rightarrow (C, T) \in SCR \forall T \subseteq S $$
$OutRank$는 이러한 redundancy of subspaces를 방지하기 위해 outlier scoring function에서 subspace와 cluster의 similarity를 고려합니다. Outlier scoring function은 위의 similarity를 고려하는 정도에 따라 세가지가 제안됩니다. 첫째, subspace의 차원 크기만 고려하는 Individual Weighting (IW). 둘째, subspace의 similarity를 고려하는 Subspace Similarity (SS). 셋째, subspace와 cluster의 similarity를 모두 고려하는 Cluster Coverage (CC).
-
Basline scoring (IW): subspace의 차원 크기만 고려
-
Subspace Similarity Scoring (SS): subspace의 similarity 고려
-
Cluster Coverage Scoring (CC): subspace similarity와 cluster similarity 고려
위으 outlier scoring function에 대한 자세한 설명은 [1]을 참고하시기 바랍니다.
(3) Underlying Subspace Methods
$OutRank$는 subspace cluster 테크닉 중 하나를 특정하지 않고 일반적인 framework을 제시합니다. 따라서 상황에 어떤 subspace clustering 방법을 사용해야할지가 중요한 문제가 됩니다. $OutRank$는 subspace clustering 기법을 4가지 범주로 분류하여 각 상황별로 어떤 subspace clustering 방법을 사용해야할지 제시합니다. (1) subspace clustering [3], [4], (2) projected clustering [5], [6], (3) non-redundant subspace clustering [7], [8], [9], (4) multiple projected clusters [10]. 위의 4가지 subspace clustering 방법 선택의 기준으로 모든 observation의 cluster 개수의 평균을 제안합니다.
$$ClusterCount(o, SCR) = |\{(C, S)\in SCR | o \in (C,S)\}|$$
$$avgCC(SCR) = \sum_{o\in DB}ClusterCount(o, SCR) / |DB|$$
-
$avgCC(SCR) \leq 2^{g}$
-
with $g = min{|S| | (C,S)\in SCR}$
-
For all redundant subspace clustering results(i.e., (1),(2),(4))
-
-
$avgCC(SCR)\geq 1$
-
For all paritional result sets (i.e., (2))
-
-
$avgCC(SCR)=c$
-
with a constant $c$ that can be controlled by the user
-
For all non-redundant clustering algorithms (i.e., (3))
-
-
$avgCC(SCR) = c$
-
with $c$ the number of $PROCLUS$ runs
-
For the multiple non-deterministic $PROCLUST$ runs that are comined in one results set (i.e., (4))
-
Discussion
$OutRank$의 outlier detection 성능은 [1]에서 확인하실 수 있습니다.
$OutRank$의 장점
- 비교적 연구가 많이된 subspace clustering을 직접적으로 이용할 수 있다.
- $o$의 outlierness를 여러개의 relevant subspaces를 통해 측정할 수 있다.
- Outlier scoring function에서 subspace의 similarity를 고려함으로써 score의 bias를 줄일 수 있다.
Reference
[1] Müller, Emmanuel, Ira Assent, Patricia Iglesias, Yvonne Mülle, and Klemens Böhm. "Outlier ranking via subspace analysis in multiple views of the data." In 2012 IEEE 12th international conference on data mining, pp. 529-538. IEEE, 2012.
[2] Lazarevic, Aleksandar, and Vipin Kumar. "Feature bagging for outlier detection." In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pp. 157-166. 2005.
[3] Sequeira, Karlton, and Mohammed Zaki. "SCHISM: a new approach to interesting subspace mining." International Journal of Business Intelligence and Data Mining 1, no. 2 (2005): 137-160.
[4] Kriegel, H-P., Peer Kroger, Matthias Renz, and Sebastian Wurst. "A generic framework for efficient subspace clustering of high-dimensional data." In fifth IEEE international conference on data mining (ICDM'05), pp. 8-pp. IEEE, 2005.
[5] Assent, Ira, Ralph Krieger, Emmanuel Müller, and Thomas Seidl. "INSCY: Indexing subspace clusters with in-process-removal of redundancy." In 2008 Eighth IEEE International Conference on Data Mining, pp. 719-724. IEEE, 2008.
[6] Moise, Gabriela, and Jörg Sander. "Finding non-redundant, statistically significant regions in high dimensional data: a novel approach to projected and subspace clustering." In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 533-541. 2008.
[7] Müller, Emmanuel, Ira Assent, Stephan Günnemann, Ralph Krieger, and Thomas Seidl. "Relevant subspace clustering: Mining the most interesting non-redundant concepts in high dimensional data." In 2009 Ninth IEEE International Conference on Data Mining, pp. 377-386. IEEE, 2009.
[8] Aggarwal, Charu C., Joel L. Wolf, Philip S. Yu, Cecilia Procopiuc, and Jong Soo Park. "Fast algorithms for projected clustering." ACM SIGMoD Record 28, no. 2 (1999): 61-72.
