[논문]고차원 데이터에서 랜드마크를 이용한 거리 기반 이상치 탐지 방법

박정희

doi:10.9717/kmms.2021.24.9.1242

[국내논문] 고차원 데이터에서 랜드마크를 이용한 거리 기반 이상치 탐지 방법
A Distance-based Outlier Detection Method using Landmarks in High Dimensional Data 원문보기

멀티미디어학회논문지 = Journal of Korea Multimedia Society, v.24 no.9, 2021년, pp.1242 - 1250

박정희 (Division of Computer Convergence, Chungnam National University)

Abstract ▼ AI-Helper

Detection of outliers deviating normal data distribution in high dimensional data is an important technique in many application areas. In this paper, a distance-based outlier detection method using landmarks in high dimensional data is proposed. Given normal training data, the k-means clustering method is applied for the training data in order to extract the centers of the clusters as landmarks which represent normal data distribution. For a test data sample, the distance to the nearest landmark gives the outlier score. In the experiments using high dimensional data such as images and documents, it was shown that the proposed method based on the landmarks of one-tenth of training data can give the comparable outlier detection performance while reducing the time complexity greatly in the testing stage.

주제어

표/그림 (10)

그림 Fig. 1. Normalized Euclidean pairwise distance in the standard normal distribution. (a) with normal data (b) with normal and outlier data [17].
그림 Fig. 2. Discrimination of normal data and outliers by the distance to the nearest landmark.
그림 Fig. 3. The summarization of the proposed method.
표 Table 1. The description of experimental setting.
표 Table 2. Performance comparison for outlier detection by the average AUC.
표 Table 3. The result of hypothesis testing about the mean of the proposed method and the compared outlier detection methods by the paired t-test.
표 Table 4. The comparison of execution time in outlier detection methods (in seconds).
그림 Fig. 4. Performance comparison when various landmark sizes are used.
그림 Fig. 5. Performance comparison when the first and sec-ond nearest landmarks are used.
표 Table 5. The comparison of training time when the max-imum iteration in k-means clustering was set variously.

AI 본문요약
AI-Helper

문제 정의

정상 학습 데이터가 주어졌을 때 정상 데이터 분포를 대표할 수 있는 소수의 랜드마크들을 선택하고 가장 가까운 랜드마크까지의 거리를 이용하여 이상치를 탐지하는 방법을 제안하고, 탐지 성능과 시간 복잡도를 기존의 이상치 방법들과 비교한다. 또한, 고차원 데이터에서 거리 기반 방법이 효과적으로 사용될 수 있는 근거를 살펴본다.
특히, 고차원 데이터에서는 거리 계산이 데이터 차원에 비례해서 높아지게 된다. 본 논문에서는 KNN 기반 이상치 탐지 방법의 성능을 유지하면서 테스트단계에서의 계산 복잡도를 크게 낮출 수 있는 랜드마크를 이용한 거리 기반 이상치 탐지 방법을 제안하였다. 정상 학습 데이터가 주어졌을 때, k-means clustering 방법을 사용하여 클러스터들의 중심을 정상 데이터를 대표할 수 있는 랜드마크로 선택한다.
본 논문에서는 고차원 데이터에서 정상 데이터를 대표할 수 있는 소수의 데이터 샘플들인 랜드마크 (landmark)를 이용한 거리 기반 이상치 탐지 방법을 제안한다. 정상 학습 데이터가 주어졌을 때 정상 데이터 분포를 대표할 수 있는 소수의 랜드마크들을 선택하고 가장 가까운 랜드마크까지의 거리를 이용하여 이상치를 탐지하는 방법을 제안하고, 탐지 성능과 시간 복잡도를 기존의 이상치 방법들과 비교한다.
일반적으로 정상 상태를 나타내는 데이터는 수집이 용이하나 이상 상태를 나타내는 데이터는 얻기가 매우 어려운 현실적인 조건을 고려할 때, 정상 데이터로 구성된 학습 데이터를 이용해서 정상 데이터 분포를 모델링하고 이를 기반으로 테스트 데이터에서 이상치를 탐지하는 방법은 실제 응용 문제에서 적용이 용이하다는 장점을 가진다. 본 논문에서는 정상 데이터로 구성된 학습 데이터가 주어지는 환경에서 고차원 데이터에서 효과적으로 적용할 수 있는 이상치 탐지 방법을 제안한다.

제안 방법

정상 학습 데이터가 주어졌을 때, k-means clustering 방법을 사용하여 클러스터들의 중심을 정상 데이터를 대표할 수 있는 랜드마크로 선택한다. 각 테스트 데이터 샘플에서 가장 가까운 랜드마크까지의 거리를 이용해 이상치 지수를 계산한다. 학습 단계에서는 k-means clustering에 드는 시간이 커지게 되나, 테스트 단계에서는 전체 학습 데이터에서 이웃 탐색을 하는 대신에 매우 적은 수의 랜드마크에서 이웃 탐색을 하게 되므로 시간 복잡도를 크게 낮출 수 있게 된다.
본 논문에서는 고차원 데이터에서 정상 데이터를 대표할 수 있는 소수의 데이터 샘플들인 랜드마크 (landmark)를 이용한 거리 기반 이상치 탐지 방법을 제안한다. 정상 학습 데이터가 주어졌을 때 정상 데이터 분포를 대표할 수 있는 소수의 랜드마크들을 선택하고 가장 가까운 랜드마크까지의 거리를 이용하여 이상치를 탐지하는 방법을 제안하고, 탐지 성능과 시간 복잡도를 기존의 이상치 방법들과 비교한다. 또한, 고차원 데이터에서 거리 기반 방법이 효과적으로 사용될 수 있는 근거를 살펴본다.
본 논문에서는 KNN 기반 이상치 탐지 방법의 성능을 유지하면서 테스트단계에서의 계산 복잡도를 크게 낮출 수 있는 랜드마크를 이용한 거리 기반 이상치 탐지 방법을 제안하였다. 정상 학습 데이터가 주어졌을 때, k-means clustering 방법을 사용하여 클러스터들의 중심을 정상 데이터를 대표할 수 있는 랜드마크로 선택한다. 각 테스트 데이터 샘플에서 가장 가까운 랜드마크까지의 거리를 이용해 이상치 지수를 계산한다.
제안 방법은 정상 데이터로 구성된 학습 데이터가 주어질 때 적용할 수 있는 이상치 탐지방법이다. 일반적으로 이상 데이터는 정상 데이터에 비해 수집하기가 어려운 경우가 많으므로 이러한 제한 조건은 실제 문제에 대한 적용에 있어서 크게 문제가 되지 않을 수 있지만, 데이터 라벨이 알려지지 않은 무감독 학습 환경의 고차원 데이터에서도 효과적으로 적용할 수 있는 방법의 개발은 필요하다.

대상 데이터

실험에서는 각 데이터셑에서 한 개의 클래스를 이상치 클래스로 두고 나머지 클래스를 정상 데이터로 설정하였다. MNIST 데이터에서는 정상 데이터의 30%를 랜덤하게 추출하여 학습 데이터로 사용하고, 나머지 정상 데이터와 이상치 데이터를 테스트 데이터로 하였다. 두 개의 텍스트 데이터에서는 정상 데이터의 50%를 학습 데이터로 사용하고, 나머지 정상 데이터와 이상치 데이터를 테스트 데이터로 설정하였다.
MNIST 데이터에서는 정상 데이터의 30%를 랜덤하게 추출하여 학습 데이터로 사용하고, 나머지 정상 데이터와 이상치 데이터를 테스트 데이터로 하였다. 두 개의 텍스트 데이터에서는 정상 데이터의 50%를 학습 데이터로 사용하고, 나머지 정상 데이터와 이상치 데이터를 테스트 데이터로 설정하였다. 정상 학습 데이터로부터 이상치 탐지 모델을 학습하고, 테스트 데이터에 대해 이상치 지수를 계산하여 AUC(Area Under the Curve) 값을 구할 수 있다.

데이터처리

Fig. 4에서는 KNN_Land 방법에서 랜드마크 사이즈를 정상 학습 데이터의 10%, 20%, 30%로 선택하고, 가장 가까운 랜드마크까지의 거리를 이용해 이상치 지수를 계산할 때의 성능을 비교하였다. KNN_ Land(rand)는 랜드마크 사이즈가 커질수록 더 좋은 성능을 보인 반면, KNN_Land(clu)는 랜드마크 사이즈가 10%-30% 범위에서 비교적 안정적인 성능을 보였다.
Table 2에서 보여주는 평균 AUC에 의한 비교가 통계적으로 의미가 있는지를 검증하기 위해 Table 1의 각 행마다 10번씩 반복된 실험 결과에 대해 제안 방법인 KNN_Land(clu)과 다른 비교방법에 대해 쌍체표본 t-test를 수행하였다. 유의 수준 5%로 하여 양측검정을 수행하여 제안 방법과 다른 비교 방법들의 비교 결과를 win(제안 방법의 평균이 비교방법의 평균보다 높다), tie(평균이 같다), lose(제안 방법의 평균이 비교방법의 평균보다 낮다)의 빈도수로 Table 3에 나타내었다.
Table 4는 각 방법들의 실행시간을 비교한다. 모든 방법은 python 패키지인 Scikit-learn과 PyOD 함수들을 사용하여 구현되었고, 10번 반복하여 평균 시간을 초로 나타내었다. training time은 학습 데이터로 모델을 수립하는 fit() 함수 수행시간이며 test time은 테스트 데이터에 대해 이상치 지수를 계산하는 decision_function() 수행시간을 측정하였다.
Table 2와 Table 4의 평균 AUC와 실행시간 측정은 k-means clustering 알고리즘에서 최대 반복 회수를 100으로 제한하여 수행한 결과이다. 최대 반복 회수를 다르게 변화시켜 가면서 수행할 때 이상치 탐지 성능과 실행시간이 어떻게 달라지는지 비교하기 위해, Table 1에서 설명한 실험 셋팅에서 Mnist (outlier class: 4), Reuter(outlier class: 3), BBC(outlier class: 1)의 세 가지 경우에 대해 탐지 성능과 실행 시간을 비교하였다. Table 5에서 k-means clustering 알고리즘에서 최대 반복 회수를 50, 100, 200 으로 다르게 설정하면서 각 데이터에서 학습 데이터와 테스트 데이터로 랜덤하게 나누는 것을 10번 반복하여 실험을 수행했을 때 training time을 비교해서 보여준다.
정상 학습 데이터로부터 이상치 탐지 모델을 학습하고, 테스트 데이터에 대해 이상치 지수를 계산하여 AUC(Area Under the Curve) 값을 구할 수 있다. 학습 데이터와 테스트 데이터로 랜덤 선택을 통해 나누는 과정을 10번 반복하여 AUC 평균값을 성능평가 척도로 사용하였다. 또한 어떤 클래스를 이상치 클래스로 설정하느냐에 따라 성능이 달라질 수있으므로 이상치 클래스로 설정하는 클래스를 다르게 반복하여 수행하였다.

이론/모형

전체 정상 데이터를 대표할 수 있도록 랜드마크를 선택하기 위해 k-means clustering 방법을 사용할 수 있다. 선택하고자 하는 랜드마크 수만큼 클러스터를 구성한 후 각 클러스터의 센터를 랜드마크로 사용한다.

성능/효과

k번째 가까운 이웃과의 거리가 멀면 멀수록 이상 치일 가능성이 더 커지는 KNN 기반 이상치 탐지 방법은 개념이 단순하고 탐지 성능도 높으나 이웃 간의 거리를 계산하는데 걸리는 시간이 높다는 단점이 있다. 특히, 고차원 데이터에서는 거리 계산이 데이터 차원에 비례해서 높아지게 된다.
학습 단계에서는 k-means clustering에 드는 시간이 커지게 되나, 테스트 단계에서는 전체 학습 데이터에서 이웃 탐색을 하는 대신에 매우 적은 수의 랜드마크에서 이웃 탐색을 하게 되므로 시간 복잡도를 크게 낮출 수 있게 된다. 고차원 데이터를 이용한 실험에서 전체 학습 데이터의 10% 크기의 랜드마크를 선택할 때, 테스트 단계에서 전체 데이터를 이용할 때보다 수행 시간은 12%에서 15% 정도로 낮추면서 이상치 탐지성능은 유지하거나 더 향상될 수 있음을 보였다.
각 테스트 데이터 샘플에서 가장 가까운 랜드마크까지의 거리를 이용해 이상치 지수를 계산한다. 학습 단계에서는 k-means clustering에 드는 시간이 커지게 되나, 테스트 단계에서는 전체 학습 데이터에서 이웃 탐색을 하는 대신에 매우 적은 수의 랜드마크에서 이웃 탐색을 하게 되므로 시간 복잡도를 크게 낮출 수 있게 된다. 고차원 데이터를 이용한 실험에서 전체 학습 데이터의 10% 크기의 랜드마크를 선택할 때, 테스트 단계에서 전체 데이터를 이용할 때보다 수행 시간은 12%에서 15% 정도로 낮추면서 이상치 탐지성능은 유지하거나 더 향상될 수 있음을 보였다.

후속연구

일반적으로 이상 데이터는 정상 데이터에 비해 수집하기가 어려운 경우가 많으므로 이러한 제한 조건은 실제 문제에 대한 적용에 있어서 크게 문제가 되지 않을 수 있지만, 데이터 라벨이 알려지지 않은 무감독 학습 환경의 고차원 데이터에서도 효과적으로 적용할 수 있는 방법의 개발은 필요하다. k-means clustering에 의한 랜드마크 선택 과정에서 학습 데이터에 포함되어 있을지도 모르는 소수의 이상치 데이터가 랜드마크로 선택되지 않도록 하는 후처리 과정을 도입함으로써 제안방법을 무감독 학습에서도 적용할 수 있도록 향후 연구를 수행할 예정이다.
제안 방법은 정상 데이터로 구성된 학습 데이터가 주어질 때 적용할 수 있는 이상치 탐지방법이다. 일반적으로 이상 데이터는 정상 데이터에 비해 수집하기가 어려운 경우가 많으므로 이러한 제한 조건은 실제 문제에 대한 적용에 있어서 크게 문제가 되지 않을 수 있지만, 데이터 라벨이 알려지지 않은 무감독 학습 환경의 고차원 데이터에서도 효과적으로 적용할 수 있는 방법의 개발은 필요하다. k-means clustering에 의한 랜드마크 선택 과정에서 학습 데이터에 포함되어 있을지도 모르는 소수의 이상치 데이터가 랜드마크로 선택되지 않도록 하는 후처리 과정을 도입함으로써 제안방법을 무감독 학습에서도 적용할 수 있도록 향후 연구를 수행할 예정이다.

참고문헌 (20)

C. Aggarwal, Outlier Analysis, Springer, Switzerlnd, 2017.
C. Park. "Outlier and Anomaly Pattern Detection on Data Streams," The Journal of Supercomputing, Vol. 75, pp. 6118-6128, 2019.

상세보기
S. Damaswanny, R. Rastogi, and K. Shim, "Efficient Algorithms for Mining Outliers from Large Data Sets," Proceeding of ACM Sigmod International Conference on Management of Data, pp. 427-438, 2000.
T. Vries, S. Chawla, and M. Houle, "Finding Local Anomalies in Very High Dimensional Space," Proceeding of International Conference on Data Mining, pp 128-137, 2010.
H. Hoffmann, "Kernel PCA for Novelty Detection," Pattern Recognition, Vol. 40, pp. 863- 874, 2007.

상세보기
S. Choi and C. Park, "Emerging Topic Detection Using Text Embedding and Anomaly Pattern Detection in Text Streaming Data," Journal of Korea Multimedia Society, Vol. 23, No. 9, pp. 1181-1190, 2020.

원문보기 상세보기
S. Sathe and C. Aggarwal, "Subspace Histograms for Outlier Detection in Linear Time," Knowledge and Information Systems, Vol. 56, pp. 691-715, 2018.

상세보기
H. Kriegel, P. Kroger, E. Schubert, and A. Zimek, "Outlier Detection in Axis-parallel subspaces of High Dimensional Data," Proceeding of Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 831-838, 2009.
A. Lazarevic and V. Kumar, "Feature Bagging for Outlier Detection," Proceeding of ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 157-166, 2005.
F. Liu, K. Ting, and Z. Zhou, "Isolation Forest," Proceeding of International Conference on Data Mining, pp. 413-422, 2008.
A. Putina, M. Sozio, D. Rossi, and J. Navarro, "Random Histogram Forest for Unsupervised Anomaly Detection," Proceedings of International Conference on Data Mining, pp. 1226-1231, 2020.
E. Knorr and R. Ng, "Finding Intensional Knowledge of Distance-based Outliers," Proceeding of 25th International Conference on Very Large Databases, pp. 211-222, 1999.
M. Breunig, H. Kriegel, R. Ng, and J. Sander, "LOF: Identifying Density-based Local Outliers," Proceeding of the ACM Sigmod International Conference on Management of Data, pp. 93-104, 2000.
E. Marchi, F. Vesperini, F. Weninger, F. Eyben, S. Squartini, and B. Schuller, "Non-linear Prediction with LSTM Recurrent Neural Networks for Acoustic Novelty Detection," Proceeding of International Joint Conference on Neural Networks, 2015.
K. Wu, K. Zhang, W. Fan, A. Edwards, and P. Yu, "RS-Forest: A Rapid Density Estimator for Streaming Anomaly Detection," Proceeding of the 14th International Conference on Data Mining, pp. 600-609, 2014.
E. Knor and R. Ng, "Algorithms for Mining Distance-based Outliers in Large Datasets," Proceeding of International Conference on Very Large Databases, pp. 392-403, 1998.
A. Zimek, E. Schubert, and H. Kriegel, "A Survey on Unsupervised Outlier Detection in High-dimensional Numerical Data," Statistical Analysis and Data Mining, Vol. 5, pp. 363-387, 2012.

상세보기
The MNIST Database(1998), http://yann.lecun.com/exdb/mnist (Accessed February 20, 2019).
D. Greene and P. Cunningham, "Practical Solutions to the Problem of Diagonal Dominance in Kernel Document Clustering," Proceeding of International Conference on Machine Learning, pp. 377-384, 2006.
Y. Zhao, Z. Nasrullah and Z. Li, "PyOD: A Python Toolbox for Scalable Outlier Detection," Journal of Machine Learning Research, Vol. 20, pp. 1-7, 2019.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증