Outlier Detection in High Dimensional Space
[Warning] 이 글은 공부 목적으로 계속 업데이트 되는 글임을 밝힙니다.
Motivation
어떤 Feature Extraction 알고리즘을 이용하여 어떤 Time Series Data(Constant Length)를 Dimension Reduction한 High-Dimensional Feature (N >= 10)로부터 out-lier를 제거하려고 한다.
Extracted Feature에 Clustering 알고리즘을 이용하여 유의미한 군을 찾아내는 작업을 해야되는데, outlier가 Clustering 결과에 악영향을 미칠것이 뻔하기 때문에 제거되는 데이터가 non-outlier라고 해도 제거하는 것이 성능향상을 위해서 맞는 선택일 것이다.
* Fluctuation(Noise)이 '상대적'으로 심한 Signal도 걸러내주는 효과가 있을 것이라고 예상하고 있다. 사실 이건, sampling한 time series들의 noise level이 모든 동일할 것이라고 가정했을 때
Out-lier Detection, Clustering 방법론을 나누는 기준은 Survey Article마다 기준이 달라서 몇개를 참조한 뒤에 적어보도록 하겠다.
PCA, ICA 알고리즘 같은 경우에는 Variance Percentage를 이용하여 Latent Vector Space의 Dimension size를 결정할 수 있는데, 비선형 계열의 알고리즘(t-SNE, AutoEncoder, KernelPCA)는 Reduction Hyperparameter를 어떻게 결정해야 할 지 의문이다.
(1) Domain-Expert의 도움을 받아서 Cluster개수를 정한다.
Pros
- 숨겨져 있는 클러스터를 찾지 못할 가능성이 크다.
Cons
- 특정한 병변, 조직에서 예상되는 클러스터 별 효과를 볼 수 있다.
(2) 어떤 특정한 Data-Specific Similarity Measure를 이용해서 (클러스터 내부 sample들 간의 similarity measure의 총합 / 클러스터 내부 sample의 개수) 가 최소가 되는 K를 찾는다.
- SUM(i = 0 to K)(클러스터 내부 sample K)
- silhouette index, adjusted mutual information(AMI) 등이 있을 수 있다.
silhouette index도 distance metric이 euclidean이나 mahalanobis일 경우에 concentration of distance현상 때문에 high dimensional data에서 제대로 동작하지 않을 가능성이 있어 보인다.
Unsupervised Clustering 의 Optimal Cluster Number 정하기.
[1]에서는 clustering validation metric을 centroid와 sample간의 거리로잡았는데, high dimensional feature일 경우에는 의미가 없어질 수 있을 것 같다.. 자세한 것은 더 읽어 봐야 될 듯.
[1] Optimized Cluster Validation Technique for Unsupervised Clustering Techniques(http://bit.ly/2us5V9e)
[2] https://stats.stackexchange.com/questions/21807/evaluation-measure-of-clustering-without-having-truth-labels
Assumption
Density, Distance based 알고리즘은 Concentration of Distances 현상 때문에 Feature의 개수가 조금만 많아져도 성능이 굉장히 떨어진다.
1. Angle-Based Detection
Concentration of Distances 현상이 sample간의 Angle High Dimension으로 갈 수록 Angle Based Method
2. Subspace Out-lier Detection
(1) CLIQUE
(2) PROCLUS
(3) ORCLUS
(4) DOC
3. Isolation-Based Detection
(1) Isolation Forest
[1] Aggarwal, Charu C., and Philip S. Yu. "Outlier detection for high dimensional data." ACM Sigmod Record. Vol. 30. No. 2. ACM, 2001.
(http://charuaggarwal.net/outl.pdf)
[2] Outlier Detection in High-Dimensional Data
Motivation
어떤 Feature Extraction 알고리즘을 이용하여 어떤 Time Series Data(Constant Length)를 Dimension Reduction한 High-Dimensional Feature (N >= 10)로부터 out-lier를 제거하려고 한다.
Extracted Feature에 Clustering 알고리즘을 이용하여 유의미한 군을 찾아내는 작업을 해야되는데, outlier가 Clustering 결과에 악영향을 미칠것이 뻔하기 때문에 제거되는 데이터가 non-outlier라고 해도 제거하는 것이 성능향상을 위해서 맞는 선택일 것이다.
* Fluctuation(Noise)이 '상대적'으로 심한 Signal도 걸러내주는 효과가 있을 것이라고 예상하고 있다. 사실 이건, sampling한 time series들의 noise level이 모든 동일할 것이라고 가정했을 때
Out-lier Detection, Clustering 방법론을 나누는 기준은 Survey Article마다 기준이 달라서 몇개를 참조한 뒤에 적어보도록 하겠다.
PCA, ICA 알고리즘 같은 경우에는 Variance Percentage를 이용하여 Latent Vector Space의 Dimension size를 결정할 수 있는데, 비선형 계열의 알고리즘(t-SNE, AutoEncoder, KernelPCA)는 Reduction Hyperparameter를 어떻게 결정해야 할 지 의문이다.
(1) Domain-Expert의 도움을 받아서 Cluster개수를 정한다.
Pros
- 숨겨져 있는 클러스터를 찾지 못할 가능성이 크다.
Cons
- 특정한 병변, 조직에서 예상되는 클러스터 별 효과를 볼 수 있다.
(2) 어떤 특정한 Data-Specific Similarity Measure를 이용해서 (클러스터 내부 sample들 간의 similarity measure의 총합 / 클러스터 내부 sample의 개수) 가 최소가 되는 K를 찾는다.
- SUM(i = 0 to K)(클러스터 내부 sample K)
- silhouette index, adjusted mutual information(AMI) 등이 있을 수 있다.
silhouette index도 distance metric이 euclidean이나 mahalanobis일 경우에 concentration of distance현상 때문에 high dimensional data에서 제대로 동작하지 않을 가능성이 있어 보인다.
Unsupervised Clustering 의 Optimal Cluster Number 정하기.
[1]에서는 clustering validation metric을 centroid와 sample간의 거리로잡았는데, high dimensional feature일 경우에는 의미가 없어질 수 있을 것 같다.. 자세한 것은 더 읽어 봐야 될 듯.
[1] Optimized Cluster Validation Technique for Unsupervised Clustering Techniques(http://bit.ly/2us5V9e)
[2] https://stats.stackexchange.com/questions/21807/evaluation-measure-of-clustering-without-having-truth-labels
Assumption
Density, Distance based 알고리즘은 Concentration of Distances 현상 때문에 Feature의 개수가 조금만 많아져도 성능이 굉장히 떨어진다.
[Figure 1] Concentration of Distances
1. Angle-Based Detection
Concentration of Distances 현상이 sample간의 Angle High Dimension으로 갈 수록 Angle Based Method
2. Subspace Out-lier Detection
(1) CLIQUE
(2) PROCLUS
(3) ORCLUS
(4) DOC
3. Isolation-Based Detection
(1) Isolation Forest
[1] Aggarwal, Charu C., and Philip S. Yu. "Outlier detection for high dimensional data." ACM Sigmod Record. Vol. 30. No. 2. ACM, 2001.
(http://charuaggarwal.net/outl.pdf)
[2] Outlier Detection in High-Dimensional Data
댓글
댓글 쓰기