تشخیص داده پرت در دادگان با ابعاد بالا با استفاده از انتخاب زیرفضای مرتبط محلی مبتنی بر آنتروپی
محورهای موضوعی : مهندسی برق و کامپیوترمحبوبه ریاحی مدوار 1 , احمد اکبری 2 * , بابک ناصرشريف 3
1 - دانشگاه علم و صنعت،دانشکده مهندسی کامپیوتر
2 - دانشگاه علم و صنعت ایران،دانشکده مهندسی کامپیوتر
3 - دانشگاه صنعتی خواجه نصیرالدین طوسی،دانشکده مهندسی کامپیوتر
کلید واژه: تشخیص داده پرت, داده‌های با ابعاد بالا, انتخاب زیرفضای مرتبط محلی, آنتروپی محلی,
چکیده مقاله :
یکی از چالش‌های مسئله تشخیص داده پرت با ابعاد بالا، طلسم بعد است که در آن برخی ابعاد (ویژگی‌ها) منجر به پنهان‌شدن داده‌های پرت می‌گردند. برای حل این مسئله، ابعادی که حاوی اطلاعات ارزشمندی در دادگان با ابعاد بالا جهت تشخیص داده پرت هستند، جستجو می‌شوند تا با نگاشت دادگان به زیرفضای متشکل از این ابعاد مرتبط، داده‌های پرت برجسته‌تر و قابل شناسایی شوند. این مقاله با معرفی یک روش جدید انتخاب زیرفضای مرتبط محلی و توسعه یک رویکرد امتیازدهی داده پرت مبتنی بر چگالی محلی، امکان تشخیص داده پرت در دادگان با ابعاد بالا را فراهم می‌نماید. در ابتدا، یک الگوریتم برای انتخاب زیرفضای مرتبط محلی بر اساس آنتروپی محلی ارائه می‌شود تا بتواند برای هر نقطه داده با توجه به داده‌های همسایه‌اش یک زیرفضای مرتبط انتخاب کند. سپس هر نقطه داده در زیرفضای انتخابی متناظرش با یک روش امتیازدهی پرت محلی مبتنی بر چگالی امتیازدهی می‌شود، به طوری که با در نظر گرفتن یک پهنای باند تطبیقی جهت تخمین چگالی هسته سعی می‌شود که اختلاف جزئی بین چگالی یک نقطه داده نرمال با همسایه‌هایش از بین رفته و به اشتباه به عنوان داده پرت تشخیص داده نشود و در عین حال، تخمین کمتر از مقدار واقعی چگالی در نقاط داده پرت، منجر به برجسته‌شدن این نقاط داده گردد. در پایان با آزمایش‌های تجربی روی چندین دادگان دنیای واقعی، الگوریتم پیشنهادی تشخیص داده پرت زیرفضای مبتنی بر آنتروپی محلی با چند تکنیک تشخیص داده پرت بر حسب دقت تشخیص مقایسه شده است. نتایج تجربی نشان می‌دهد که الگوریتم پیشنهادی مبتنی بر معیار آنتروپی محلی و روش پیشنهادی امتیازدهی داده پرت توانسته است به دقت بالایی جهت تشخیص داده پرت دست یابند.
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.