Outlier Detection in High Dimensional Data Using Entropy-Based Locally Relevant Subspace Selection
Subject Areas : electrical and computer engineeringMahboobeh Riahi Madvar 1 , Ahmad Akbari 2 * , B. Nasersharif 3
1 -
2 -
3 - K.N. Toosi University of Technology
Keywords: Outlier detection, high dimensional data, locally relevant subspace selection, local entropy,
Abstract :
One of the challenges of high dimensional outlier detection problem is the curse of dimensionality which irrelevant dimensions (features) lead to hidden outliers. To solve this problem, some dimensions that contain valuable information to detect outliers are searched to make outliers more prominent and detectable by mapping the dataset into the subspace which is constituted of these relevant dimensions/features. This paper proposes an outlier detection method in high dimensional data by introducing a new locally relevant subspace selection and developing a local density-based outlier scoring. First, we present a locally relevant subspace selection method based on local entropy to select a relevant subspace for each data point due to its neighbors. Then, each data point is scored in its relevant subspace using a density-based local outlier scoring method. Our adaptive-bandwidth kernel density estimation method eliminates the slight difference between the density of a normal data point and its neighbors. Thus, normal data are not wrongly detected as outliers. At the same time, our method underestimates the actual density of outlier data points to make them more prominent. The experimental results on several real datasets show that our local entropy-based subspace selection algorithm and the proposed outlier scoring can achieve a high accuracy detection rate for the outlier data.
[1] C. C. Aggarwal and S. Y. Philip, "An effective and efficient algorithm for high-dimensional outlier detection," The VLDB J., vol. 14, no. 2, pp. 211-221, Apr. 2005.
[2] M. Riahi-Madvar, B. Nasersharif, and A. Akbari Azirani, "A new density-based subspace selection method using mutual information for high dimensional outlier detection," Knowledge-Based Systems, vol. 216, Article ID: 106733, 16 Mar. 2021.
[3] M. Riahi-Madvar, B. Nasershari, and A. Akbari Azirani, "Subspace outlier detection in high dimensional data using ensemble of PCA-based subspaces," in Proc. 26th Int. Computer Conf., Computer Society of Iran, CSICC'21, 5 pp., Tehran, Iran, 3-4 Mar. 2021.
[4] L. Zhang, J. Lin, and R. Karim, "Adaptive kernel density-based anomaly detection for nonlinear systems," Knowledge-Based Systems, vol. 139, pp. 50-63, 1 Jan. 2018.
[5] V. Chandola, A. Banerjee, and V. Kumar, "Outlier detection: a survey," ACM Computing Surveys, vol. 14, p. 15, Aug. 2007.
[6] V. Barnett and T. Lewis, Outliers in Statistical Data, 3rd Ed., Wiely, 1994.
[7] H. V. Nguyen, V. Gopalkrishnan, and I. Assent, "An unbiased distance-based outlier detection approach for high-dimensional data," in Proc. of the Int. Conf. on Database Systems for Advanced Applications, pp. 138-152, Taipei, Taiwan, 11-14 Apr. 2011.
[8] E. M. Knox and R. T. Ng, "Algorithms for mining distancebased outliers in large datasets," in Proc. of the Int. Conf. on Very Large Data Bases, pp. 392-403, New York, NY, USA, 24-27 Aug. 1998.
[9] F. Angiulli and C. Pizzuti, "Outlier mining in large high-dimensional data sets," IEEE Trans. on Knowledge and Data Engineering, vol. 17, no. 2, pp. 203-215, Jan. 2005.
[10] M. M. Breunig, et al., LOF: identifying density-based local outliers, ACM sigmod record, ACM, 2000.
[11] A. Zimek, E. Schubert, and H. P. Kriegel, "A survey on unsupervised outlier detection in high‐dimensional numerical data," Statistical Analysis and Data Mining: the ASA Data Science J., vol. 5, no. 5, pp. 363-387, Oct. 2012.
[12] C. C. Aggarwal and P. S. Yu, Outlier detection for high dimensional data, in ACM Sigmod Record, ACM, 2001.
[13] J. Zhang, et al., "A concept lattice based outlier mining method in low-dimensional subspaces," Pattern Recognition Letters, vol. 30, no. 15, pp. 1434-1439, Nov. 2009.
[14] X. Zhao, J. Zhang, and X. Qin, "LOMA: a local outlier mining algorithm based on attribute relevance analysis," Expert Systems with Applications, vol. 84, pp. 272-280, Oct. 2017.
[15] H. P. Kriegel, et al., "Outlier detection in axis-parallel subspaces of high dimensional data," in Proc. Pacific-Asia Conf. on Knowledge Discovery and Data Mining, pp. 831-838, Bangkok, Thailand, 27-30 Apr. 2009.
[16] E. Muller, M. Schiffer, and T. Seidl, "Statistical selection of relevant subspace projections for outlier ranking," in Proc. IEEE 27th Int. Conf. on Data Engineering, pp. 434-445, Hannover, Germany, 11-16 Apr. 2011.
[17] F. Keller, E. Muller, and K. Bohm, "HiCS: high contrast subspaces for density-based outlier ranking," in Proc. IEEE 28th Int. Conf. on Data Engineering, pp. 1037-1048, Arlington, VA, USA, 1-5 Apr. 2012.
[18] J. Zhang, et al., "A relevant subspace based contextual outlier mining algorithm," Knowledge-Based Systems, vol. 99, pp. 1-9, May 2016.
[19] H. P. Kriegel, et al., "Outlier detection in arbitrarily oriented subspaces," in Proc. IEEE 12th Int. Conf. on Data Mining, pp. 379-388, Brussels, Belgium, 10-13 Dec. 2012.
[20] F. Cheraghchi, A. Iranzad, and B. Raahemi, "Subspace selection in high-dimensional big data using genetic algorithm in apache spark," in Proc. of the 2nd Int. Conf. on Internet of Things, Data and Cloud Computing, ACM, Article ID: 54, 7 pp., Cambridge, United Kingdom, 22-23 Mar. 2017.
[21] C. C. Aggarwal, Outlier Analysis, in Data Mining, Springer, 2015.
[22] H. V. Nguyen, et al., "CMI: an information-theoretic contrast measure for enhancing subspace cluster and outlier detection," in Proc. of the SIAM Int. Conf. on Data Mining, 9 pp., Austin, TX,USA, 2-4 May 2013.
[23] S. Kandanaarachchi, et al., "On normalization and algorithm selection for unsupervised outlier detection," Data Mining and Knowledge Discovery, vol. 34, no. 2, pp. 309-354, Mar. 2020.
[24] A. Lazarevic and V. Kumar, "Feature bagging for outlier detection," in Proc. of the 11th ACM SIGKDD Int. Conf. on Knowledge Discovery in Data Mining, pp. 157-166, Chicago, IL, USA, 21-24 Aug. 2005.
[25] F. Liu, et al., "Scalable KDE-based top-n local outlier detection over large-scale data streams," Knowledge-Based Systems, vol. 204, Article ID: 106186, Sept. 2020.
[26] C. E. Shannon, "A mathematical theory of communication," the Bell System Technical J., vol. 27, no. 3, pp. 379-423, Jul. 1948.
[27] D. W. Scott, Multivariate Density Estimation: Theory, Practice, and Visualization, John Wiley & Sons, 2015.
[28] K. Bache and M. Lichman, UCI machine learning repository, 2013.
[29] E. Achtert, H. P. Kriegel, and A. Zimek, "ELKI: a software system for evaluation of subspace clustering algorithms," in Proc. Int. Conf. on Scientific and Statistical Database Management, pp. 580-585, Hong Kong, 9-11 Jul. 2008.