تشخیص داده پرت در دادگان با ابعاد بالا با استفاده از انتخاب زیرفضای مرتبط محلی مبتنی بر آنتروپی
محورهای موضوعی : مهندسی برق و کامپیوتر
محبوبه ریاحی مدوار
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.
نشریه مهندسی برق و مهندسی كامپیوتر ایران، ب- مهندسی کامپیوتر، سال 19، شماره 4، زمستان 1400 1
مقاله پژوهشی
تشخیص داده پرت در دادگان با ابعاد بالا با استفاده
از انتخاب زیرفضای مرتبط محلی مبتنی بر آنتروپی
محبوبه ریاحی مدوار، احمد اکبری ازیرانی و بابک ناصرشریف
چكیده: یکی از چالش‌های مسئله تشخیص داده پرت با ابعاد بالا، طلسم بعد است که در آن برخی ابعاد (ویژگی‌ها) منجر به پنهان‌شدن داده‌های پرت می‌گردند. برای حل این مسئله، ابعادی که حاوی اطلاعات ارزشمندی در دادگان با ابعاد بالا جهت تشخیص داده پرت هستند، جستجو می‌شوند تا با نگاشت دادگان به زیرفضای متشکل از این ابعاد مرتبط، داده‌های پرت برجسته‌تر و قابل شناسایی شوند. این مقاله با معرفی یک روش جدید انتخاب زیرفضای مرتبط محلی و توسعه یک رویکرد امتیازدهی داده پرت مبتنی بر چگالی محلی، امکان تشخیص داده پرت در دادگان با ابعاد بالا را فراهم می‌نماید. در ابتدا، یک الگوریتم برای انتخاب زیرفضای مرتبط محلی بر اساس آنتروپی محلی ارائه می‌شود تا بتواند برای هر نقطه داده با توجه به داده‌های همسایه‌اش یک زیرفضای مرتبط انتخاب کند. سپس هر نقطه داده در زیرفضای انتخابی متناظرش با یک روش امتیازدهی پرت محلی مبتنی بر چگالی امتیازدهی می‌شود، به طوری که با در نظر گرفتن یک پهنای باند تطبیقی جهت تخمین چگالی هسته سعی می‌شود که اختلاف جزئی بین چگالی یک نقطه داده نرمال با همسایه‌هایش از بین رفته و به اشتباه به عنوان داده پرت تشخیص داده نشود و در عین حال، تخمین کمتر از مقدار واقعی چگالی در نقاط داده پرت، منجر به برجسته‌شدن این نقاط داده گردد. در پایان با آزمایش‌های تجربی روی چندین دادگان دنیای واقعی، الگوریتم پیشنهادی تشخیص داده پرت زیرفضای مبتنی بر آنتروپی محلی با چند تکنیک تشخیص داده پرت بر حسب دقت تشخیص مقایسه شده است. نتایج تجربی نشان می‌دهد که الگوریتم پیشنهادی مبتنی بر معیار آنتروپی محلی و روش پیشنهادی امتیازدهی داده پرت توانسته است به دقت بالایی جهت تشخیص داده پرت دست یابند.
کلیدواژه: تشخیص داده پرت، داده‌های با ابعاد بالا، انتخاب زیرفضای مرتبط محلی، آنتروپی محلی.
1- مقدمه
تشخیص داده پرت یکی از مهم‌ترین و چالش‌برانگیزترین وظایف داده‌کاوی است که اشاره به مسئله یافتن نقاط داده‌ای دارد که مشخصات آنها با اکثریت داده‌ها به طور قابل توجهی متفاوت است. تشخیص داده پرت، کاربردهای گسترده‌ای در زمینه‌های تشخیص تقلب2، تشخیص خطا3، تشخیص نفوذ4، تجزیه و تحلیل بیولوژیکی5 و بازاریابی6 [1] دارد. در کاربردهای دنیای واقعی، ماهیت مسئله تشخیص داده پرت، یادگیری بدون نظارت است، زیرا داده‌های پرت به ندرت رخ می‌دهند و هزینه برچسب‌گذاری آنها سنگین است.
تشخیص داده پرت در زمینه‌های پژوهشی زیادی مورد توجه قرار گرفته است اما بسیاری از تکنیک‌های تشخیص داده پرت موجود، روی داده‌های با ابعاد بالا با توجه به مسئله طلسم بعد7، چالش‌های قابل توجهی دارند. برخی پژوهش‌های اخیر، روش‌هایی مبتنی بر زیرفضا ارائه کرده‌اند تا با انتخاب زیرفضایی با ابعاد کمتر بتوانند داده‌های پرتی را که مخفی شدند شناسایی کنند [2] و [3]. به دلیل ماهیت پیچیده داده‌های پرت، ممکن است یک داده در یک زیرفضا قابل تشخیص باشد، اما داده پرت دیگر در آن زیرفضا قابل تشخیص نباشد. بنابراین هیچ زیرفضایی وجود ندارد که به طور کامل مشخصات تمام نقاط داده پرت را در بر داشته باشد. بنابراین در روش‌هایی که با دیدگاه سراسری، تنها یک زیرفضای مرتبط برای تشخیص داده پرت انتخاب می‌شود، ممکن است تمام داده‌های پرت در آن زیرفضا قابل تشخیص نباشند.
در این مقاله برای مقابله با مشکلات بالا یک روش تشخیص داده پرت زیرفضای مبتنی بر آنتروپی محلی 8(LESOD) پیشنهاد داده می‌شود که شامل دو گام مجزای انتخاب زیرفضای مرتبط و سپس، امتیازدهی و تشخیص داده‌های پرت است. این جداسازی این امکان را فراهم می‌کند که بتوان به طور مجزا روی هر یک از این دو حوزه تحقیق کرد. در این مقاله، ابتدا با پیشنهاد یک روش جدید انتخاب زیرفضای مرتبط مبتنی بر آنتروپی و سپس، توسعه یک روش امتیازدهی داده پرت، سعی بر بهبود دقت تشخیص داده پرت می‌شود. انگیزه روش پیشنهادی انتخاب زیرفضای مرتبط محلی، انتخاب یک زیرفضای مرتبط برای هر نقطه داده است. هدف از انتخاب زیرفضای مرتبط برای یک نقطه داده، حذف ویژگی‌های بی‌ربط است به طوری که نقطه داده مفروض در راستای این ویژگی‌های بی‌ربط دارای اطلاعات کمی است. بنابراین با حذف ویژگی‌های بی‌ربط برای هر نقطه داده و تنها نگه‌داشتن ویژگی‌های مرتبط که حاوی اطلاعات بالایی جهت تشخیص داده پرت هستند، می‌توان با کارایی بالایی، نقاط داده پرت را در دادگان با ابعاد بالا شناسایی کرد. برای رتبه‌بندی نقاط داده پرت، یک روش جدید امتیازدهی مبتنی
بر چگالی تطبیقی با الهام از روش [4] پیشنهاد داده می‌شود که برای
هر نقطه داده، یک امتیاز پرت با مقایسه چگالی‌اش با چگالی نقاط همسایگی‌اش در زیرفضای انتخابی متناظر با نقطه داده مفروض تخصیص می‌دهد.
به طور کلی، نوآوری‌های اصلی این مقاله می‌توانند به صورت زیر خلاصه‌سازی شوند:
1) به کارگیری مفهوم آنتروپی محلی به همراه مفهوم اطلاعات برای تعیین باربط/ بی‌ربط‌بودن یک ویژگی که منجر به افزایش دقت تشخیص داده پرت می‌گردد.
2) یک پهنای باند تطبیقی برای تخمین چگالی هسته پیشنهاد داده می‌شود. هنگام محاسبه و مقایسه چگالی یک نقطه داده با همسایه‌هایش، یک پهنای باند تطبیقی برای نقطه داده مفروض، محاسبه و از این همین پهنای باند برای تخمین چگالی نقاط داده همسایگی استفاده می‌شود. بدین ترتیب انتظار می‌رود که در یک ناحیه چگال، با در نظر گرفتن یک پهنای باند یکسان برای تخمین چگالی نقاط همسایگی، اختلاف‌های ناچیز بین مقادیر چگالی از بین رفته و نرخ مثبت کاذب کاهش یابد.
ساختار مقاله به صورت زیر است: ابتدا یک مرور خلاصه‌ای از کارهای مرتبط در بخش 2 معرفی شده است. بخش 3، روش پیشنهادی تشخیص داده پرت زیرفضا، شامل دو الگوریتم جدید انتخاب زیرفضای مرتبط مبتنی بر آنتروپی و امتیازدهی داده پرت مبتنی بر چگالی را تشریح می‌کند. آزمایش‌های تجربی و تحلیل نتایج آنها در بخش 4 بیان شده و بخش 5، این مقاله را با چند نتیجه‌گیری و کارهای آتی خاتمه می‌دهد.
2- پژوهش‌های مرتبط
روش‌های تشخیص داده پرت را می‌توان با توجه به معیار‌های مختلف، تقسیم‌بندی کرد:
با توجه به موجودبودن برچسب داده‌ها، تکنیک‌های تشخیص داده پرت را می‌توان به سه طبقه بانظارت، نیمه‌نظارتی و بدون نظارت تقسیم‌بندی کرد [5]. در روش‌های بانظارت، برچسب داده‌ها به صورت نرمال و پرت وجود دارند و در روش‌های نیمه‌نظارتی، تمام نمونه‌ها متعلق به کلاس نرمال هستند. در تکنیک‌های بدون نظارت، هیچ داده پرچسب‌داری موجود نیست. در این تکنیک‌ها فرض می‌شود که نمونه‌های پرت از سایر نمونه‌ها دور هستند. تکنیک‌های بدون نظارت در مسئله تشخیص داده پرت عملی‌تر هستند، زیرا جمع‌آوری یک مجموعه داده برچسب‌دار که کل رفتار نمونه‌های پرت را پوشش دهد دشوار است.
با توجه به تعداد ابعاد مورد استفاده در تشخیص داده پرت، الگوریتم‌های تشخیص داده پرت به دو دسته فضای کامل9 و زیرفضا تقسیم می‌گردند. روش‌های بدون نظارت تشخیص داده پرت فضای کامل را بر اساس تکنیک‌های به کار گرفته شده می‌توان به روش‌های مبتنی بر خوشه‌بندی، مبتنی بر مدل‌های آماری و مبتنی بر نزدیک‌ترین همسایهها تقسیم‌بندی کرد. تکنیک‌های مبتنی بر خوشه‌بندی، داده‌هایی را که متعلق به هیچ خوشه‌ای نیستند یا متعلق به خوشه‌های بسیار کوچک هستند، به عنوان داده پرت در نظر می‌گیرند. تکنیک‌های مبتنی بر مدل‌های آماری [6] فرض می‌کنند که توزیع داده‌ها از یک مدل آماری پیروی می‌کند و سپس یک تست آماری برای تعیین نقاط داده‌ای که با مدل مفروض، سازگار نیستند به کار گرفته می‌شود. در روش‌های مبتنی بر نزدیک‌ترین همسایهها، هر نقطه داده با توجه به همسایگی محلی‌اش تحلیل می‌شود. این روش‌ها با توجه به این که داده‌های پرت بر اساس چه معیاری با نزدیک‌ترین همسایهها مقایسه و شناسایی می‌شوند، به دو دسته روش‌های مبتنی بر فاصله [7] تا [9] و مبتنی بر چگالی [10] تقسیم می‌گردند. در روش‌های مبتنی بر فاصله، زمانی که چگالی نواحی مختلف داده متفاوت باشند، تکنیک‌های مبتنی بر فاصله، ضعیف عمل می‌کنند. روش‌های مبتنی بر چگالی نه تنها چگالی هر نقطه، بلکه چگالی نقاط همسایگی را نیز محاسبه می‌کنند. اگر چگالی یک نقطه داده نسبت به همسایگانش بسیار کمتر باشد، به عنوان داده پرت شناسایی می‌شود. همچنین در دسته‌بندی دیگری بر اساس اندازه مجموعه مرجع (کل/ بخشی از نقاط دادگان) برای محاسبه امتیاز پرت یک نقطه، روش‌های تشخیص داده پرت را می