تشخیص داده پرت در دادگان با ابعاد بالا با استفاده از انتخاب زیرفضای مرتبط محلی مبتنی بر آنتروپی
محورهای موضوعی : مهندسی برق و کامپیوترمحبوبه ریاحی مدوار 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.
نشریه مهندسی برق و مهندسی كامپیوتر ایران، ب- مهندسی کامپیوتر، سال 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] تقسیم میگردند. در روشهای مبتنی بر فاصله، زمانی که چگالی نواحی مختلف داده متفاوت باشند، تکنیکهای مبتنی بر فاصله، ضعیف عمل میکنند. روشهای مبتنی بر چگالی نه تنها چگالی هر نقطه، بلکه چگالی نقاط همسایگی را نیز محاسبه میکنند. اگر چگالی یک نقطه داده نسبت به همسایگانش بسیار کمتر باشد، به عنوان داده پرت شناسایی میشود. همچنین در دستهبندی دیگری بر اساس اندازه مجموعه مرجع (کل/ بخشی از نقاط دادگان) برای محاسبه امتیاز پرت یک نقطه، روشهای تشخیص داده پرت را میتوان به دو دسته محلی و سراسری تقسیم کرد. الگوریتم شناختهشده عامل پرت محلی 10(LOF) [10]، اولین روش محلی مبتنی بر چگالی است که به هر نقطه داده، یک امتیاز پرت محلی تخصیص میدهد. امتیاز LOF برای هر نقطه داده با توجه به نرخ میانگین چگالی محلی نزدیکترین همسایهاش 11(kNN) و چگالی محلی آن نقطه داده تعیین میشود. در روش تشخیص ناهنجاری مبتنی بر چگالی تطبیقی 12(Adaptive-KD) [4]، یک روش امتیازدهی پیشنهاد شده که برای بهبود قدرت تفکیک بین دادههای نرمال و پرت، یک پهنای باند تطبیقی به کار گرفتند: در مناطق با چگالی بالا، پهنای باند عریض برای برطرفنمودن اختلاف چگالی بین نمونههای نرمال و در نواحی با چگالی پایین، از پهنای باند باریک برای تشدید ناهنجاری نمونههای پرت بالقوه استفاده میکنند.
اکثر روشهای رایج تشخیص داده پرت، کل فضای ویژگی را برای یافتن دادههای پرت استفاده میکنند. در دادههای با ابعاد بالا به دلیل مشکل طلسم بعد، حضور تعداد بالای ابعاد بیربط در دادگان منجر به پنهانشدن اطلاعات مرتبط میگردد. در نتیجه، در روشهای مبتنی بر کل ابعاد، داده پرت به راحتی مخفی میشود [11]. روشهای مبتنی بر زیرفضا برای کاهش اثر طلسم بعد، دادههای پرت را در یک/ چند زیرفضا با ابعاد کمتر جستجو میکنند. در این روشها، یافتن یک/ چند زیرفضا با ابعاد کمتر که بتواند دادههای پرت را از سایر دادهها تفکیک نماید، به دلیل اندازهگیری میزان ارتباط یک ویژگی با مسئله بدون نظارت تشخیص داده پرت، چالشبرانگیز است. همچنین این روشها به دلیل نیاز به جستجوی زیرفضاهایی در فضای داده با ابعاد بالا، پیچیدگی محاسباتی بالایی دارند. روشهای مبتنی بر زیرفضا در دو نوع روشهای زیرفضای تنک [12] تا [14] و روشهای زیرفضای مرتبط [15] تا [19] توسعه داده شدند:
1) روشهای تشخیص داده پرت مبتنی بر زیرفضای تنک، دادههای پرت را در زیرفضاهایی با ابعاد پایینتر جستجو میکنند. در این روشها، تمام نقاط دادگان به زیرفضای با ابعاد پایینتر، نگاشت میشوند و نمونههایی که در زیرفضای تنک دارای چگالی کمتر از میانگین هستند به عنوان نمونه پرت شناسایی میشوند. آگاروال در اولین روش تشخیص داده پرت زیرفضا [12]، از نمایش گرید برای محاسبه ضرایب تنکی زیرفضاهای مختلف استفاده کرده و با بهرهگیری از الگوریتم ژنتیک برای جستجوی کاراتر زیرفضاهای تنک، توانست عملکرد جستجو را بهبود دهد. اما کارایی الگوریتم ژنتیک، وابسته به پارامترهای مختلفی از قبیل جمعیت اولیه، تابع برازش و ... است و بنابراین الگوریتم ژنتیک نمیتواند کاملبودن نتایج جستجو را تضمین کند. در یک الگوریتم تشخیص داده پرت دیگر [13] با بهرهگیری از شبکه مفهومی13 به عنوان ابزاری برای نمایش زیرفضاها و با معرفی مفهوم چگالی، کاملبودن نتایج جستجو تضمین شده است. اما ساخت شبکه مفهومی از زیرفضاها، پیچیده است و منجر به کارایی پایین میگردد. برخلاف روشهای قبلی [12]، [13] و [20] که زیرفضای تنک را با توجه به کل دادگان جستجو میکردند، یک الگوریتم تشخیص داده پرت محلی 14(LOMA) [14] مبتنی بر تحلیل ارتباط ویژگی با نمونههای پرت پیشنهاد داده است که ابعاد و نقاط داده بیربط در دادگان را با به کارگیری تحلیل ارتباط ویژگی همراه با یک آستانه عامل تنکی هرس میکند. LOMA با به کارگیری روش بهینهسازی ازدحام ذرات15 روی دادگان کاهشیافته، زیرفضای تنک را جستجو میکند. روش LOMA نقاط داده بیربط را هرس میکند و تعداد ویژگیها را کاهش میدهد. بنابراین در دادگان با ابعاد بالا کارامدتر است اما توسط دقت تشخیص محدود میشود.
2) روشهای تشخیص داده پرت مبتنی بر زیرفضای مرتبط، یک/ چند زیرفضا را شامل تعدادی بعد معنادار که دادههای پرت را برجسته مینمایند انتخاب میکنند. در روش تشخیص داده پرت زیرفضا 16(SOD) [15]، برای هر نقطه داده، یک مجموعه مرجع با استفاده از نزدیکترین همسایه مشترک17 میگردد. زیرفضای مرتبط با توجه به ابعادی تعیین میشود که در نقاط مجموعه مرجع دارای واریانس پایینی هستند. درجه پرت زیرفضا برای یک نقطه داده با توجه
به فاصلهاش تا صفحهای شامل ابعاد مرتبط، تعریف میشود.
روش SOD در موارد بسیاری به دلیل نادیدهگرفتن تعامل بین
ابعاد، دچار مشکل میشود [21]. در روش رتبهبندی داده پرت زیرفضا 18(OUTRES) [16]، مجموعه زیرفضاهای مرتبط شامل زیرفضاهایی که دارای توزیع غیر یکنواخت هستند با استفاده از جستجوی پایین به بالا19 شناسایی میشوند. در ارزیابی یکنواختی توزیع یک زیرفضا از تست آماری کولموگروف- اسمیرنف20 استفاده میشود. روش OUTRES [16] برای محاسبه امتیاز پرت، نیاز به تعداد زیادی دادگان محلی دارد و همچنین دارای پیچیدگی محاسباتی نمایی بر حسب تعداد ابعاد میباشد. بدین ترتیب روش OUTRES [16] روی دادگان با ابعاد بالا و حجیم، دارای مقیاسپذیری ضعیفی میباشد. روش احتمال پرت همبستگی 21(COP) [19]، از تحلیل مؤلفه اصلی22 در دادگان محلی برای جستجوی زیرفضاهای جهتدار دلخواه با کمترین واریانس استفاده میکند و دادههای پرت را بر اساس میزان انحراف از توزیع دادگان محلی تعیین مینماید. بنابراین، این روش برای بازتاب مشخصات توزیع دادگان و نهایتاً تعیین میزان انحراف، به دادگان محلی به اندازه کافی بزرگ نیاز دارد. در روش زیرفضاهای با کنتراست بالا برای رتبهبندی داده پرت مبتنی بر چگالی 23(HiCS) [17]، با فرض استقلال ویژگیها، کنتراست یک زیرفضا را با میزان همبستگی
بین ویژگیهای آن زیرفضا، اندازهگیری میکنند و زیرفضاهای با کنتراست بالا جستجو میشوند. معیار کنتراست زیرفضا با استفاده از محاسبه اطلاعات متقابل به صورت تخمین مونتکارلو اندازهگیری میشود. سپس میزان پرتبودن نقاط داده بر اساس نگاشت نقاط دادگان محلی به زیرفضای مرتبط، اندازهگیری میشوند. در HiCS برای محاسبه اطلاعات متقابل، اختلاف بین توزیع شرطی و حاشیهای در یک بعد تصادفی از زیرفضای مورد نظر اندازهگیری میشود و بدین ترتیب با این انتخاب تصادفی، ممکن است برخی زیرفضاهای مرتبط از دست بروند [22]. همچنین فرض استقلال ویژگیها و انتخاب یک زیرمجموعه از ویژگیهای وابسته ممکن است معتبر نباشد، زیرا برخی ویژگیها ممکن است با تشخیص داده پرت قویاً مرتبط باشند اما هیچ وابستگی با سایر ویژگیها نداشته باشند. تعیین زیرفضای مرتبط در HiCS مبتنی بر یک رویکرد سراسری است، در حالی که در الگوریتم تشخیص داده پرت ضمنی در زیرفضای مرتبط دلخواه 24(COAS) [18]، یک الگوریتم محلی برای تشخیص داده پرت ضمنی مبتنی بر زیرفضای مرتبط روی دادگان حجیم و با ابعاد بالا پیشنهاد داده شده است. زیرفضای مرتبط در COAS با استفاده از ابعادی که تنکی محلی از یک حد آستانه بزرگتر باشد، ساخته میشود. سپس با تعریف یک فرمول محاسبه عامل پرت محلی احتمالی25 در زیرفضای مرتبط، درجه پرتبودن نقاط دادهای که از توزیع دادگان محلی پیروی نمیکنند محاسبه میگردد. اخیراً یک روش تشخیص داده پرت زیرفضای مبتنی بر چگالی [2] با معرفی یک نمایش مبتنی بر چگالی، امکان ارائه دو معیار جدید مبتنی بر چگالی برای انتخاب زیرفضای مرتبط فراهم شده است. در معیار اول، ماکسیمم- ارتباط- با- چگالی26 با استفاده از اطلاعات متقابل ویژگیهایی که بیشترین ارتباط با چگالی دادهها را دارند محاسبه میشود. در معیار دوم، مینیمم- افزونگی- ماکسیمم- ارتباط- با- چگالی27 با به کارگیری مفهوم افزونگی بین ویژگیها سعی میشود یک زیرفضای فشرده شامل ویژگیهایی که ماکسیمم ارتباط با چگالی و در عین حال، کمترین افزونگی بین آنهاست انتخاب گردد. نقاط داده پرت در زیرفضای انتخابی با استفاده از الگوریتم امتیازدهی داده پرت LOF امتیازدهی و شناسایی میشوند. این روش [2] تنها یک زیرفضا برای تشخیص دادههای پرت در کل دادگان انتخاب میکند و این در حالی است که در برخی دادگان ممکن است یک زیرفضا نتواند تمام دادههای پرت را نمایش دهد.
به طور خلاصه، مطالعه کارهای پیشین تشخیص داده پرت بیان میکند که یک روش دقیق و کارامد تشخیص داده پرت در دادگان با ابعاد
[1] این مقاله در تاریخ 13 اردیبهشت ماه 1400 دریافت و در تاریخ 28 شهریور ماه 1400 بازنگری شد.
محبوبه ریاحی مدوار، دانشکده مهندسی کامپیوتر، دانشگاه علم و صنعت ایران، تهران، ایران، (email: m_riahi@comp.iust.ac.ir).
احمد اکبری ازیرانی (نویسنده مسئول)، دانشكده مهندسي كامپيوتر، دانشگاه علم و صنعت ايران، تهران، ایران، (email: akbari@iust.ac.ir).
بابک ناصرشریف، دانشکده مهندسی کامپیوتر، دانشگاه صنعتی خواجه نصیرالدین طوسی، تهران، ایران، (email: bnasersharif@kntu.ac.ir).
[2] . Fraud Detection
[3] . Fault Detection
[4] . Intrusion Detection
[5] . Biological Analysis
[6] . Marketing
[7] . Curse of Dimensionality
[8] . Local Entropy-Based Subspace Outlier Detection
[9] . Full-Dimensional
[10] . Local Outlier Factor
[11] . k-Nearest Neighbors
[12] . Adaptive Kernel Density-Based Anomaly Detection
[13] . Concept Lattice
[14] . Local Outlier Mining Algorithm
[15] . Particle Swarm Optimization
[16] . Subspace Outlier Detection
[17] . Shared Nearest Neighbors
[18] . Subspace Outlier Ranking
[19] . Bottom-up
[20] . Kolmogorov-Smirnov
[21] . Correlation Outlier Probability
[22] . Principal Component Analysis
[23] . High Contrast Subspaces for Density-Based Outlier Ranking
[24] . Contextual Outlier Detection in Arbitrarily Relevant Subspaces
[25] . Probability Local Outlier Factor
[26] . Maximum-Relevance-to-Density
[27] . Minimum-Redundancy-Maximum-Relevance-to-Density
بالا، باید دارای مزایای زیر باشد: انتخاب ابعاد مرتبط بدون در نظر گرفتن هیچ گونه فرضی روی ابعاد و توزیع دادهها، امکان تشخیص چندین نوع داده پرت با انتخاب زیرفضاهای مرتبط به صورت محلی، بهبود قدرت تفکیک معیار امتیازدهی پرت محلی با استفاده از پهنای تطبیقی و در عین حال، کاهش اختلافهای ناچیز بین چگالی یک نقطه و همسایگانش به منظور کاهش تعداد دادههای نرمالی که به اشتباه به عنوان داده پرت، تشخیص داده میشوند.
3- روش پیشنهادی
دستیافتن به دقت و کارایی بالا در مسئله تشخیص دادههای پرت روی دادگان با ابعاد بالا، یک چالش است. اکثر روشهای موجود در تشخیص دادههای پرت با ابعاد بالا ناکارامد هستند. در این بخش، یک روش انتخاب زیرفضای مرتبط محلی برای کاهش تعداد ابعاد پیشنهاد داده میشود که بر اساس میزان اطلاعات یک نقطه داده در راستای ابعاد مختلف، ویژگیهای مرتبط برای تعیین پرتبودن آن نقطه داده شناسایی میشوند. سپس با نگاشت کل دادگان به زیرفضای به دست آمده برای نقطه داده مفروض، درجه پرتبودن آن نقطه داده محاسبه میگردد.
برای توصیف روش پیشنهادی، ابتدا برخی نمادگذاریهای مورد استفاده معرفی میشود. فرض کنید که دادگانی شامل نقطه داده در فضای ویژگی بعدی میباشد که مجموعه ویژگیها به صورت است.
روند کلی الگوریتم پیشنهادی در شکل 1 آمده است. ابتدا نرمالسازی دادهها (یا مقیاسبندی ویژگیها) ضروری است، زیرا ویژگیهای با مقادیر بزرگتر در محاسبه فاصله و همچنین در ساختار همسایگی بر سایر ویژگیها تسلط دارند. معمولاً در تشخیص دادههای پرت، روش نرمالسازی حداقل- حداکثر 1(min-max) که هر ویژگی را به بازه نرمالسازی میکند استفاده میشود [23]. نرمالسازی min-max، تبدیل خطی زیر را روی مقادیر ویژگی انجام میدهد
(1)
که و به ترتیب برابر مقادیر مینیمم و ماکسیمم ویژگی هستند و بدین ترتیب با نرمالسازی تمام ویژگیها (ستونها)، ماتریس داده تبدیل به میشود.
در این مقاله مشابه با HiCS [17] و گروهبندی ویژگی2 [24]، گام انتخاب زیرفضای مرتبط و امتیازدهی پرت به صورت مسئلههای مجزا جداسازی شده که با این جداسازی میتوان به طور عمیق روی هر یک از این مسئلهها پژوهش کرد. گامهای روش پیشنهادی آمده در شکل 1، به طور کامل در زیربخشهای بعدی شرح داده میشوند.
3-1 تخمین چگالی هسته تطبیقی برای تشخیص داده پرت
تخمین چگالی هسته 3(KDE) یک روش غیر پارامتری برای تخمین تابع چگالی احتمال متغیرهای تصادفی است. پهنای باند نقش مهمی در کیفیت KDE دارد. روش تخمین چگالی هسته نزدیکترین همسایگی 4(kNN-KDE)، گونه مهمی از روش تخمین چگالی هسته میباشد که در آن پهنای باند به صورت محلی انتخاب میگردد. در مسئله تشخیص داده پرت، استفاده از روش تخمین چگالی kNN-KDE دارای مزیتهای امکان به کارگیری یک پهنای باند هسته تطبیقی، کاهش پیچیدگی محاسباتی و از دست نرفتن اختلافهای محلی در چگالی به دلیل استفاده از نزدیکترین همسایگی به جای کل نقاط دادگان میباشد.
در این مقاله از روش kNN-KDE برای تخمین چگالی محلی استفاده میشود. در این تخمینگر چگالی هسته، مقدار چگالی برای نقطه داده با توجه به نزدیکترین همسایهاش به صورت زیر تعریف میگردد
(2)
که پارامتر پهنای باند، تعداد ابعاد نقاط داده، تابع هسته و فاصله اقلیدسی بین نقاط داده و میباشد. چگالی نقطه داده با استفاده از میانگین تخمین چگالی با توجه به کل نقاط همسایگیاش تخمین زده میشود.
در دادههای نااریب5، توزیع نقاط داده در بخشهای مختلف، متفاوت است و به کارگیری پهنای باند ثابت در تشخیص داده پرت در دادگانی شامل چندین خوشه با چگالیهای متفاوت، منجر به عملکرد مناسبی نمیگردد. بنابراین منطقی نیست که یک پهنای باند ثابت برای کل نقاط دادگان به کار گرفته شود. یک روش رایج برای تعیین پهنای تطبیقی در مسایل تخمین چگالی و تشخیص داده پرت [25]، به کارگیری مقادیر کوچک پهنای باند در نواحی با چگالی بالا و مقادیر بزگ در نواحی با چگالی پایین است. اما در مسئله تشخیص داده پرت، نواحی با چگالی بالا مورد توجه نیستند، بنابراین با در نظر گرفتن یک پهنای باند بزرگ میتوان چگالی را هموار6 تخمین زد و بدین ترتیب واریانس امتیاز پرت بین نقاط نرمال را کاهش داد. در نواحی با چگالی پایین، پهنای باند باریک منجر به تخمین چگالیهای کوچکتر میشود که این میتواند باعث برجستهنمودن نقاط داده پرت گردد. بنابراین در مسئله تشخیص داده پرت بر عکس مسئله تخمین چگالی، انتخاب یک پهنای باند بزرگ در نواحی
با چگالی بالا و یک پهنای باند کوچک در نواحی با چگالی پایین ترجیح داده میشود.
در این مقاله از یک پهنای باند متفاوت برای هر نقطه داده
استفاده خواهد شد. فرض کنید که برای امین نقطه داده، برابر با میانگین فاصله تا نزدیکترین همسایهاش یعنی است و و برابر کوچکترین و بزرگترین مقادیر در مجموعه باشند. با الهام از پهنای باند تطبیقی ارائهشده در روش Adaptive-KD [4]، از به عنوان پهنای باند نقطه داده ام استفاده میشود که عامل مقیاسبندی برای کنترل اثر هموارسازی سراسری و یک مقدار مثبت بسیار کوچک (برای مثال، ) برای اطمینان از غیر صفر شدن پهنای باند میباشد. در روش Adaptive-KD [4]، برای هر نقطه داده به صورت تطبیقی یک پهنای باند محاسبه و بر اساس آن، چگالی نقطه داده مفروض تعیین میشود. در حالی که روش پیشنهادی پس از محاسبه پهنای باند یک نقطه داده بر اساس فاصله تا نزدیکترین همسایگی و تعداد ابعاد زیرفضا، از این پهنای باند برای محاسبه چگالی نقاط همسایگی نیز استفاده میکند تا اختلافهای جزئی بین چگالی نقاط داده نرمال را کاهش دهد.
در اینجا تابع هسته گاوسی به کار گرفته شده است. بدین ترتیب مدل KDE مورد استفاده در این مقاله به صورت زیر میباشد
(3)
که است.
در گام انتخاب ابعاد مرتبط، نیاز به محاسبه چگالی در راستای یک ویژگی است. همچنین در مرحله امتیازدهی به منظور محاسبه امتیاز پرت نقاط داده مختلف در زیرفضاهای محلی متناظر با تعداد ابعاد متفاوت،
نیاز به محاسبه چگالی در این زیرفضاها است. فرض کنید که زیرفضای مد نظر (ویژگی ام یا زیرفضای انتخابی متناظر با نقطه داده ام) با نمایش داده شود. مدل KDE در (3) برای محاسبه چگالی در زیرفضای به صورت زیر درمیآید
(4)
که نگاشت نقطه داده ام به زیرفضای ، تعداد ابعاد زیرفضای ، شامل نزدیکترین همسایه نقطه داده در زیرفضای و برابر پهنای باند نقطه داده ام در زیرفضای میباشد. نحوه محاسبه پارامتر جهت تخمین چگالی نقطه داده ام در زیرفضای در گامهای انتخاب ابعاد و امتیازدهی داده پرت، در زیربخشهای 3-2 و 3-3 آورده شده است.
3-2 انتخاب زیرفضای مرتبط مبتنی بر آنتروپی
در تئوری اطلاعات، آنتروپی توسعهیافته توسط شانون یک معیار مؤثر برای اندازهگیری اطلاعات یا عدم قطعیت برای یک متغیر است [26]. مفهوم آنتروپی برای تشخیص داده پرت بسیار شهودی است زیرا حضور داده پرت، آنتروپی دادگان را افزایش میدهد. همچنین نقطه داده پرت در مقایسه با همسایههایش دارای چگالی کمتر و اطلاعات بیشتری است.
فرض کنید که یک متغیر تصادفی و برابر مجموعه مقادیری که متغیر میتواند اختیار کند، باشد و تابع احتمال متغیر تصادفی را نمایش دهد. آنتروپی میتواند به صورت (5) تعریف گردد
(5)
در این مقاله، پیرو تعریف شانون از آنتروپی، آنتروپی محلی7 تعریف و
به منظور انتخاب زیرفضای مرتبط به کار گرفته میشود. هدف از انتخاب زیرفضای مرتبط، هرسکردن ابعاد بیربط از طریق شناسایی ابعادی است که حاوی اطلاعات کمی هستند.
برای اندازهگیری میزان اطلاعات محلی نقطه داده در راستای ویژگی ام ، ابتدا یک دادگان محلی به صورت kNN در راستای امین ویژگی تعریف میشود که آنتروپیاش به عنوان آنتروپی محلی اشاره میشود. همچنین بر اساس این همسایگی، مقدار اطلاعات محلی نقطه داده در راستای ویژگی ام به صورت زیر محاسبه میگردد
(6)
که احتمال نقطه داده در راستای ویژگی است. برای محاسبه مقدار احتمال ، لازم است مقدار چگالی نقطه داده و نقاط همسایگیاش در راستای ویژگی محاسبه و سپس نرمالسازی گردد. مقادیر چگالی هر یک از نقاط در راستای ویژگی ام با استفاده از محاسبه پهنای باند طبق (7) و سپس با جایگذاری در (4) تعیین میشوند
(7)
که برابر میانگین فاصله تا نزدیکترین همسایهاش
در راستای ویژگی ام و و به ترتیب برابر کوچکترین و بزرگترین مقادیر در مجموعه هستند. بنابراین با نرمالسازی چگالی نسبت به مجموع چگالی نقاط همسایگیاش، احتمال به نقطه داده تخصیص داده میشود
(8)
آنتروپی محلی نقطه داده در راستای ویژگی میتواند به صورت زیر تعریف گردد
(9)
که بیانگر نزدیکترین همسایه به نقطه داده در راستای امین ویژگی است.
بر طبق این شهود که نقطه داده پرت در مقایسه با همسایههایش دارای مقدار احتمال کوچکتر و حاوی اطلاعات بیشتری است، میتوان ابعاد مرتبط را انتخاب کرد. ویژگی برای تشخیص پرتبودن/ نبودن نقطه داده مرتبط است، اگر مقدار اطلاعات نقطه داده نسبت به مقدار میانگین اطلاعات نقاط همسایگیاش (آنتروپی محلی) در راستای ویژگی بیشتر باشد
(10)
بعد از محاسبه مقدار اطلاعات و آنتروپی محلی در طول تمام ویژگیها، میتوان زیرفضای مرتبط با تشخیص داده پرت در این نقطه داده را به صورت زیر انتخاب کرد
(11)
در الگوریتم 1، فرایند انتخاب زیرفضای مرتبط مبتنی بر آنتروپی آورده شده است (شکل 2).
3-3 نگاشت دادهها و امتیازدهی دادههای پرت
در دادههای با ابعاد بالا ممکن است با توجه به تعداد زیاد ویژگیهای بیربط، برخی دادههای پرت گم شوند. در این مقاله با پیشنهاد یک روش انتخاب زیرفضای مرتبط محلی برای تشخیص دادههای پرت سعی شده که اکثر دادههای پرت شناسایی شوند. پس از این که برای هر نقطه داده، یک زیرفضای مرتبط استخراج شد، لازم است که کارایی این زیرفضاهای محلی در تشخیص دادههای پرت ارزیابی گردد.
برای امتیازدهی دادههای پرت، هر نقطه داده در فضای اولیه با ابعاد بالا به زیرفضای مرتبط متناظرش با ابعاد پایینتر نگاشت میشود . با به کارگیری تعریف ویژگی مرتبط در (10)، میتوان نقاط دادهای را که در راستای کل ابعاد، حاوی اطلاعات کمتری در مقایسه با همسایهها هستند (یعنی در طول هیچ یک از ویژگیها در ناحیه تنک قرار ندارند) نرمال در نظر گرفت و امتیاز پرت صفر به آنها تخصیص داد. در اینجا برای تعیین میزان پرتبودن نقاط دادگان ، یک معیار نسبی به کار گرفته میشود تا میزان انحراف چگالی نقطه داده از نقاط همسایگیاش در زیرفضای را اندازهگیری کند. برای تعیین نقاط همسایگی در زیرفضای مرتبط متناظرش لازم است کل دادگان اولیه به زیرفضای نگاشت شود تا نقاط همسایگی در فضای نگاشتیافته تعیین گردند.
وابستگی شدیدی بین چگالی یک نقطه داده و تعداد ابعاد زیرفضای مرتبط محلیاش وجود دارد. با افزایش تعداد ابعاد زیرفضای مرتبط، چگالی نقاط داده کاهش مییابند و یک پهنای باند هسته تطبیقی پیشنهاد داده میشود که تعداد ابعاد زیرفضا را نیز در نظر میگیرد. همچنین به منظور کاهش واریانس چگالی نقاط داده نرمال و در نتیجه، کاهش نرخ مثبت کاذب، در مرحله امتیازدهی نقطه داده ام در زیرفضای از پهنای باند تطبیقی استفاده شده است. بدین صورت که پهنای باند نقطه داده ام به صورت تطبیقی بر حسب فاصله تا نقاط همسایگیاش و تعداد ابعاد زیرفضای با توجه به نسخه چندبعدی قانون اسکات8 [27] تعیین میگردد. سپس از همین پهنای باند برای محاسبه چگالی نقاط همسایگی استفاده میشود. با در نظر گرفتن یک پهنای باند یکسان برای نقاط همسایگی، انتظار میرود اختلافهای جزئی بین مقدار چگالی نقطه و چگالی نقاط همسایگیاش از بین رود. بنابراین چگالی نقطه داده و نقاط داده همسایگیاش در زیرفضای با استفاده از پهنای باند تطبیقی به دست آمده از (12) و سپس با جایگذاری در (4)، محاسبه میشوند
(12)
که تعداد ابعاد زیرفضای مرتبط ، برابر میانگین فاصله نقطه داده تا نزدیکترین همسایهاش در زیرفضای و و به ترتیب برابر کوچکترین و بزرگترین مقادیر در مجموعه میباشند.
با فرض این که اندازه دادگان ثابت باشد، پهنای باند تطبیقی تابعی افزایشی بر حسب تعداد ابعاد است. بدین ترتیب با افزایش تعداد ابعاد، پهنای باند نیز افزایش مییابد و چگالی نقاط در زیرفضاهای با ابعاد مختلف قابل مقایسه خواهند بود.
پس از تخمین چگالی نقطه داده و همسایگانش در زیرفضای
[1] . Minimum-Maximum
[2] . Feature Bagging
[3] . Kernel Density Estimation
[4] . k-Nearest Neighbor Kernel Density Estimation
[5] . Skewed Data
[6] . Smooth
[7] . Local Entropy
[8] . Scott's Rule
Algorithm 1: Local Entropy-based Subspace Selection for Outlier Detection(LESS)
Input:
Output:
_________________________________________________________________________________________________________________________
Initialization: Set
for each in :
· column of dataset matrix
for each in :
· = Compute for data point in
· =Compute the average Euclidean distance to its nearest neighbors
end
· Compute and from all the quantities
end
for each in :
for each in :
· = column of dataset matrix
· Compute the kernel width of the ith data point:
· Compute the local density of the ith data point:
· Compute the sum of local density for nearest neighbors of the ith data point using the kernel width of the ith data point:
· Compute the probability of the ith data point and its on feature by means of the normalization of their local density:
· Compute the information provided by the ith data on feature :
· Compute the local entropy of the ith data point on feature :
if :
· Add to :
end
end
end
شكل 2: الگوریتم 1.
، معیار عامل پرت مبتنی بر چگالی نسبی نقطه داده ام به صورت زیر تعریف میشود
(13)
که برابر نرخ میانگین چگالی نقاط همسایگی به چگالی نقطه داده است. اگر بزرگتر از 1 باشد، آن گاه نقطه داده خارج از یک ناحیه چگال قرار دارد و بنابراین یک داده پرت میباشد. اگر کوچکتر یا مساوی با 1 باشد، آن گاه نقطه داده توسط یک ناحیه همسایگی با چگالی یکسان یا توسط ناحیه تنکتر احاطه شده که یک داده پرت نیست. الگوریتم نگاشت و امتیازدهی دادههای پرت در الگوریتم 2 توصیف شده است (شکل 3).
در زیربخشهای بالا، گامهای الگوریتم با تمرکز بر انتخاب زیرفضای مرتبط و امتیازدهی داده پرت شرح داده شد. حال در الگوریتم 3، این مراحل در کنار هم قرار گرفته و شبهکد کلی روش پیشنهادی برای تشخیص دادههای پرت با ابعاد بالا آورده شده است (شکل 4).
سرانجام به طور خلاصه روی پیچیدگی محاسباتی روش پیشنهادی بحث میشود. در الگوریتم پیشنهادی، زیرفضای مرتبط نقطه داده بر اساس آنتروپی و اطلاعات محلی محاسبه شده و سپس میزان پرتبودن این نقطه داده در زیرفضای مرتبط بر اساس مقایسه چگالی محلیاش با چگالی نقاط داده همسایگیاش تعیین میگردد. در الگوریتم 1 بر اساس نقاط داده یکبعدی در راستای یک ویژگی، مرتبطبودن آن ویژگی به نقاط داده مختلف بررسی میگردد که محاسبات عمده در الگوریتم 1 مربوط به تعیین نقاط داده همسایگی است، به طوری که پیچیدگی محاسباتی یافتن kNN برای یک نقطه داده در راستای یک ویژگی برابر
Algorithm 2: Local Density-based Outlier Scoring (LDOS)
Input:
Output:
___________________________________________________________________________________________________
for each in :
· =project data matrix into
· =compute for data point in the subspace
· Compute the local density of the data point and its neighbors as follows:
where and
· Compute the Relative Density-based Outlier Factor(RDOF) for data point :
if :
else
, where
end
end
شكل 3: الگوریتم 2.
Algorithm 3: Local Entropy-based Subspace Outlier Detection (LESOD)
Input:
Output: Outlier data points
___________________________________________________________
· = Applying feature normalization/scaling on
· =Select the local relevant subspaces for outlier detection using
Algorithm 1 :
· =Compute outlier scores for all data points in using Algorithm 2:
Detect outlier data points given as score values in the previous step
شكل 4: الگوریتم 3.
است، البته با استفاده از ساختار درختی میتواند برای کل نقاط دادگان به کاهش یابد. بدین ترتیب پیچیدگی زمانی الگوریتم 1، است. در الگوریتم 2 برای امتیازدهی یک نقطه داده، نیاز به نگاشت دادگان به زیرفضای مرتبط متناظر با آن نقطه داده، یافتن نقاط همسایگیاش و سپس امتیازدهی نقطه داده مفروض است که پیچیدگی محاسباتی این عملیات از مرتبه است. بنابراین پیچیدگی محاسباتی کلی روش تشخیص داده پرت آمده در الگوریتم 3 برابر است. پیچیدگی محاسباتی روش پیشنهادی با برخی تکنیکهای محلی تشخیص داده پرت با ابعاد بالا SOD [15]، COP [19] و OUTRES [16] با پیچیدگی به ترتیب برابر با ، و قابل مقایسه است. پیچیدگی محاسباتی روش پیشنهادی بر حسب تعداد ابعاد، خطی است در حالی که پیچیدگی الگوریتمهای COP و OUTRES به ترتیب چندجملهای و نمایی است.
4- ارزیابی روش پیشنهادی
در این بخش، عملکرد روش پیشنهادی از طریق آزمایشهایی روی
جدول 1: مشخصات دادگان مورد استفاده از مخزن UCI.
دادگان | تعداد نمونهها | تعداد | تعداد ویژگیها |
Arrhythmia | 420 | 18 | 129 |
Ionosphere | 351 | 126 | 32 |
Breast_diagnostic | 569 | 212 | 30 |
Diabetes | 768 | 268 | 8 |
Glass | 214 | 9 | 7 |
چندین دادگان واقعی مخزن یادگیری ماشین UCI [28] ارزیابی و با روشهای LOF [10]، HiCS [17]، COP [19] و Adaptive-KD [4] مقایسه میشود.
4-1 روش راهاندازی
الگوریتم پیشنهادی تشخیص داده پرت در دادههای با ابعاد بالا به زبان پایتون روی سیستمی با مشخصات CPU 7Intel® Core™ i و حافظه
GB 8 پیادهسازی شده است.
دادگان: آزمایشها روی چندین دادگان واقعی متعلق به مخزن یادگیری ماشین UCI [28] شامل دادگان Arrhythmia، Breast_diagnostic، Ionosphere، Diabetes و Glass که مشخصات آنها در جدول 1 آمده، انجام شده است.
معیار ارزیابی: سطح زیر منحنی ROC 1(AUC) یک معیار شناختهشده برای ارزیابی عملکرد روشهای تشخیص داده پرت است. نمودار ROC نرخ مثبت صحیح 2 در مقابل نرخ مثبت کاذب
[1] . Area Under Curve
[2] . True Positive Rate
جدول 2: مقایسه AUC (بر حسب %) روی دادگان واقعی UCI.
دادگان/ الگوریتم | LOF | HiCS | COP | Adaptive-KD | LESOD |
Arrhythmia | 98/64 | 35/60 | 49/60 | 06/66 | 53/72 |
Ionosphere | 43/86 | 99/69 | 26/76 | 04/91 | 03/93 |
Breast_diagnostic | 19/53 | 03/64 | 61/50 | 8/61 | 4/70 |
Diabetes | 95/61 | 69/58 | 16/54 | 81/61 | 09/67 |
Glass | 61/81 | 95/83 | 33/75 | 5/86 | 96/87 |
1 با در نظر گرفتن حد آستانههای مختلف، ترسیم میگردد که و به صورت زیر محاسبه میشوند
(14)
که ، ، و به ترتیب بیانگر تعداد نقاط دادهای که به درستی پرت تشخیص داده شدهاند، تعداد کل نقاط داده پرت موجود در دادگان، تعداد نقاط دادهای که به اشتباه پرت تشخیص داده شدهاند و تعداد کل نقاط نرمال در دادگان است. برای محاسبه سطح زیر منحنی ROC روشهای ذوزنقهای خطی2، ذوزنقهای لگاریتمی3 و ذوزنقهای خطی- لگاریتمی4 وجود دارد. روش ذوزنقهای خطی از درونیابی خطی5 بین دو نقطه نمودار ROC برای محاسبه AUC استفاده میکند. برای یک بازه زمانی مشخص ، AUC میتواند به صورت زیر محاسبه گردد
(15)
که در آن و به ترتیب برابر مقادیر منحنی ROC در زمانهای و هستند.
در آزمایشها، روش پیشنهادی با چهار الگوریتم شناختهشده تشخیص داده پرت LOF [10]، HiCS [17]، COP [19] و Adaptive-KD [4] با استفاده از AUC مقایسه گردیده است.
4-2 نتایج
پارامترهای روش HiCS مطابق پیشنهاد نویسندگان [17] به صورت ، و تنظیم شده است. پارامتر تعداد نزدیکترین همسایه در هر سه روش LOF، HiCS و Adaptive-KD مشابه با برخی کارهای تشخیص داده پرت قبلی [14] و [18] برابر تنظیم شده است. در COP، پارامتر باید به اندازه کافی بزرگ و مقدارش از تعداد ابعاد دادگان بزرگتر باشد تا قادر به تخمین ساختار کواریانس محلی باشد. بنابراین از روی تمام دادگان استفاده شده است، به جز دادگان Arrhythmia که برابر 200 تنظیم گردیده است. نتایج این سه روش روی هر یک از دادگان آمده در جدول 1 بر حسب مقدار AUC در جدول 2 گزارش شده است. در این مقاله، از پیادهسازیهای انجامشده الگوریتمهای LOF [10]، HiCS [17] و COP [19] در چارچوب ELKI [29] استفاده گردیده و الگوریتم Adaptive-KD [4] به زبان پایتون پیادهسازی شده است.
در این آزمایشها از هسته گاوسی استفاده شده که برای تعیین پهنای باند تطبیقی، نیاز به تنظیم سه پارامتر ، و دارد. پارامترهای و به ترتیب برابر با 5/0 و 5-10 و پارامتر تعداد نزدیکترین همسایه برای هر دو گام تعیین انتخاب زیرفضای مرتبط و امتیازدهی داده پرت برابر تنظیم شده است. با تنظیم این پارامترها، مقادیر AUC به دست آمده از روش پیشنهادی روی هر یک از دادگان آمده در جدول 1 در جدول 2 آورده شده و همچنین بهترین مقدار AUC در بین الگوریتمهای LOF، HiCS، COP، Adaptive-KD و روش پیشنهادی روی هر یک از دادگان، برجسته شده است.
همان طور که در جدول 2 پیداست، روش پیشنهادی LESOD روی تمام دادگان آمده در جدول 1، توانسته بهترین نتایج را در بین الگوریتم پیشنهادی، LOF [10]، HiCS [17]، COP [19] و Adaptive-KD [4] به دست آورد. روشهای LOF و Adaptive-KD، نقاط داده پرت را در فضای کل ابعاد جستجو میکنند و بنابراین به دلیل مسئله طلسم بعد ممکن است برخی دادههای پرت مخفی شوند و تشخیص داده نشوند.
در جدول 2 مشاهده میشود که دقت الگوریتم پیشنهادی LESOD بالاتر از الگوریتم COP است. زیرفضای مرتبط در الگوریتم COP با استفاده از همبستگی خطی پیرسون به دست میآید و این روش همبستگی تنها مشخصات توزیع خطی دادگان محلی را منعکس میکند. بدین ترتیب، زیرفضای مرتبط در COP، تنها میتواند دادههای پرتی که از توزیع خطی منحرف هستند را شناسایی کند. بنابراین توزیع دادگان و طلسم بعد روی دقت تشخیص روش COP تأثیرگذار است. این در حالی است که روش پیشنهادی ما برای تعیین زیرفضای مرتبط تفاوت بین ابعاد با مشخصات مختلف را بر حسب آنتروپی محلی و بدون در نظر گرفتن هیچ فرضی روی توزیع دادهها محاسبه میکند و در نتیجه، توزیع دادهها تأثیر کمتری روی دقت تشخیص داده پرت در روش پیشنهادی میگذارد. در روش HiCS [17] بر اساس یک روش سراسری، چندین زیرفضای مرتبط انتخاب میگردد. همچنین زیرفضاهای مرتبط از طریق یک الگوریتم Apriori-like جستجو میشوند که ممکن است زیرفضاهای مرتبط انتخابشده توسط این الگوریتم جستجو، ناقص باشند. علاوه بر این، روش HiCS [17] با فرض استقلال بین ویژگیها، کنتراست یک زیرفضا را با اندازهگیری همبستگی بین ابعادش اندازهگیری کرده است. در کل، فرض استقلال بین ابعاد صحیح نیست یعنی ممکن است انتخاب زیرفضایی با ابعاد وابسته، بیانگر ماهیت واقعی دادههای پرت در هر دادگانی نباشد. با توجه به دلایل اشارهشده، روش ما با به کارگیری یک رویکرد انتخاب محلی ابعاد مرتبط و بدون در نظر گرفتن هیچ فرضی روی ویژگیها و توزیع دادهها میتواند ویژگیهای مرتبط برای تشخیص پرتبودن هر یک از نقاط داده را تعیین کند و نسبت به روش HiCS [17] بهبود چشمگیری داشته باشد. البته قابل اشاره است که پهنای باند تطبیقی پیشنهادی نیز بر روی عملکرد مناسب الگوریتم امتیازدهی داده پرت و نهایتاً روی بهبود دقت الگوریتم تشخیص داده پرت پیشنهادی تأثیرگذار است.
5- نتیجهگیری و کارهای آتی
تشخیص داده پرت در فضای داده با ابعاد بالا، چالشبرانگیز و هزینهبر است. در این خصوص، انتخاب زیرفضای مرتبط نقش مهمی در دقت و کارایی مسئله تشخیص داده پرت بازی میکند. در این مطالعه، یک روش بدون نظارت تشخیص داده پرت محلی مبتنی بر زیرفضا در دادههای با ابعاد بالا پیشنهاد شده است. در الگوریتم پیشنهادی، زیرفضای مرتبط برای هر نقطه داده، بر اساس آنتروپی محلی و مقدار اطلاعات آن نقطه داده در دادگان محلی که با استفاده از تخمین چگالی تطبیقی محاسبه شدهاند، تعریف میگردد. زیرفضای مرتبط محلی یک نقطه داده، متشکل از ابعادی است که مقدار اطلاعات آن نقطه داده در راستای آن ابعاد بزرگتر از آنتروپی محلی باشد و بر این اساس، از تأثیر ویژگیهای بیربط روی تشخیص داده پرت میتواند به طور مؤثری جلوگیری کند و منجر به تشخیص دادههای پرت پنهانشده در زیرفضاهای با ابعاد پایینتر گردد. همچنین در این مقاله یک روش امتیازدهی داده پرت مبتنی بر تخمین چگالی هسته پیشنهاد داده شده که برای کاهش اختلاف امتیاز پرت بین نقاط داده نرمال و برجستهنمودن نقاط داده پرت، از یک پهنای باند تطبیقی که رابطه معکوس با فاصله تا نزدیکترین همسایگی دارد استفاده میکند. باید اشاره کرد که پهنای باند تطبیقی محاسبهشده برای یک نقطه داده، جهت تخمین چگالی نقاط داده همسایگی نیز استفاده میشود تا اختلافهای جزئی بین مقدار چگالی و امتیاز پرت نقاط داده نرمال از بین رود. با استفاده از دادگان واقعی، نتایج تجربی تأیید میکنند که روش پیشنهادی ما برای تشخیص داده پرت در دادگان با ابعاد بالا کارامد است.
در الگوریتم پیشنهادی برای انتخاب ابعاد مرتبط از معیار کلی آنتروپی استفاده شده که در کارهای آتی میتوان از فاصله کولبک- لیبلر6 برای اندازهگیری اختلاف توزیع دادههای پرت با توزیع دادههای نرمال استفاده کرد. در الگوریتم ما، زیرفضای مرتبط برای یک نقطه داده بر اساس مشخصات توزیع دادگان محلیاش تعیین میشود و بنابراین انتخاب مناسب نقاط داده در دادگان محلی روی کارایی انتخاب زیرفضای مرتبط تأثیرگذار است. در پژوهشهای آتی میتوان به تحلیل همزمان دو زیرمسئله انتخاب دادگان محلی و انتخاب زیرفضای مرتبط پرداخت. به علاوه، با توجه به رشد روزافزون دادهها میتوان الگوریتم پیشنهادی تشخیص داده پرت در زیرفضای مرتبط را در محیطهای محاسباتی توزیعشده و موازی بسط داد تا امکان به کارگیری این روش روی دادههای عظیم و با ابعاد بالا فراهم گردد.
مراجع
[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.
محبوبه ریاحی مدوار تحصیلات خود را در مقطع کارشناسی مهندسی کامپیوتر در سال 1390 از دانشگاه صنعتی شریف و کارشناسی ارشد مهندسی کامپیوتر گرایش هوش مصنوعی در سال 1392 از دانشگاه صنعتی امیرکبیر به پایان رسانده است. از سال 1392 تا 1394 نامبرده در دانشگاه شهید باهنر کرمان و ولیعصر (عج) رفسنجان مشغول تدریس بود. پس از آن، در سال 1394 به دوره دکتری مهندسی کامپیوتر گرایش هوش مصنوعی در دانشگاه علم و صنعت ایران وارد گردید و هماکنون نیز در حال تحصیل است. زمینههای علمی مورد علاقه ایشان عبارتند از: دادهکاوی، بازشناسی الگو، تشخیص دادههای پرت، دادههای با ابعاد بالا.
احمد اکبری ازیرانی دانشیار دانشکده مهندسی کامپیوتر دانشگاه علم و صنعت ایران هستند. ایشان 25 سال سابقه تدریس و پژوهش در زمینه های مختلف رشته مهندسی کامپیوتر را در این دانشکده را دارند و دبیر قطب علمی شبکههای ارتباطی و اطلاعاتی نسل جدید میباشند و بیش از 50 مقاله در ژورنال های معتبر بین المللی انتشار دادهاند. ایشان مسئولیتهای علمی و اجرایی مختلفی از جمله ریاست دانشکده به مدت 7 سال و عضویت در هیات مدیره انجمن کامپیوتر ایران به مدت 16 سال را در کارنامه خود دارند. زمینههای پژوهشی مورد علاقه ایشان پردازش دادهها، شبکههای کامپیوتری و امنیت شبکه است.
بابك ناصر شريف درجه كارشناسي را در رشته مهندسي كامپيوتر گرايش سختافزار از دانشگاه صنعتي اميركبير در سال 1376 دريافت نمود و موفق به اخذ درجه كارشناسي ارشد و دكتري در رشته مهندسي كامپيوتر گرايش هوش مصنوعي از دانشگاه علم و صنعت ايران بهترتیب در سالهاي 1379 و 1386 گرديد. نامبرده از سال 1386 تا 1390 عضو هيأت علمي گروه مهندسي كامپيوتر در دانشكده فني گيلان و ازسال1390 تاكنون عضو هيأت علمي دانشكده مهندسي كامپيوتر در دانشگاه صنعتي خواجه نصير طوسي است. زمينه تحقيقاتي ايشان پردازش گفتار، یادگیری عمیق برای پردازش گفتار و بازشناسي الگو است.
[1] . False Positive Rate
[2] . Linear Trapezoidal Method
[3] . Logarithmic Trapezoidal Method
[4] . Linear-Log Trapezoidal Method
[5] . Linear Interpolation
[6] . Kullback-Leibler