• صفحه اصلی
  • تشخیص داده پرت در دادگان با ابعاد بالا با استفاده از انتخاب زیرفضای مرتبط محلی مبتنی بر آنتروپی

اشتراک گذاری

آدرس مقاله


کد مقاله : 14000213273286 بازدید : 6608 صفحه: 302 - 312

20.1001.1.16823745.1400.19.4.16.9

نوع مقاله: پژوهشی

تشخیص داده پرت در دادگان با ابعاد بالا با استفاده از انتخاب زیرفضای مرتبط محلی مبتنی بر آنتروپی

محورهای موضوعی : مهندسی برق و کامپیوتر

محبوبه ریاحی مدوار 1 , احمد اکبری 2 * , بابک ناصرشريف 3

1 - دانشگاه علم و صنعت،دانشکده مهندسی کامپیوتر
2 - دانشگاه علم و صنعت ایران،دانشکده مهندسی کامپیوتر
3 - دانشگاه صنعتی خواجه نصیرالدین طوسی،دانشکده مهندسی کامپیوتر

تاریخ دریافت : 1400/02/13 تاریخ پذیرش : 1400/09/22 تاریخ انتشار : 1400/12/14

کلید واژه: تشخیص داده پرت, داده‌های با ابعاد بالا, انتخاب زیرفضای مرتبط محلی, آنتروپی محلی,

چکیده مقاله :

یکی از چالش‌های مسئله تشخیص داده پرت با ابعاد بالا، طلسم بعد است که در آن برخی ابعاد (ویژگی‌ها) منجر به پنهان‌شدن داده‌های پرت می‌گردند. برای حل این مسئله، ابعادی که حاوی اطلاعات ارزشمندی در دادگان با ابعاد بالا جهت تشخیص داده پرت هستند، جستجو می‌شوند تا با نگاشت دادگان به زیرفضای متشکل از این ابعاد مرتبط، داده‌های پرت برجسته‌تر و قابل شناسایی شوند. این مقاله با معرفی یک روش جدید انتخاب زیرفضای مرتبط محلی و توسعه یک رویکرد امتیازدهی داده پرت مبتنی بر چگالی محلی، امکان تشخیص داده پرت در دادگان با ابعاد بالا را فراهم می‌نماید. در ابتدا، یک الگوریتم برای انتخاب زیرفضای مرتبط محلی بر اساس آنتروپی محلی ارائه می‌شود تا بتواند برای هر نقطه داده با توجه به داده‌های همسایه‌اش یک زیرفضای مرتبط انتخاب کند. سپس هر نقطه داده در زیرفضای انتخابی متناظرش با یک روش امتیازدهی پرت محلی مبتنی بر چگالی امتیازدهی می‌شود، به طوری که با در نظر گرفتن یک پهنای باند تطبیقی جهت تخمین چگالی هسته سعی می‌شود که اختلاف جزئی بین چگالی یک نقطه داده نرمال با همسایه‌هایش از بین رفته و به اشتباه به عنوان داده پرت تشخیص داده نشود و در عین حال، تخمین کمتر از مقدار واقعی چگالی در نقاط داده پرت، منجر به برجسته‌شدن این نقاط داده گردد. در پایان با آزمایش‌های تجربی روی چندین دادگان دنیای واقعی، الگوریتم پیشنهادی تشخیص داده پرت زیرفضای مبتنی بر آنتروپی محلی با چند تکنیک تشخیص داده پرت بر حسب دقت تشخیص مقایسه شده است. نتایج تجربی نشان می‌دهد که الگوریتم پیشنهادی مبتنی بر معیار آنتروپی محلی و روش پیشنهادی امتیازدهی داده پرت توانسته است به دقت بالایی جهت تشخیص داده پرت دست یابند.

چکیده انگلیسی:

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 

چكیده: یکی از چالش‌های مسئله تشخیص داده پرت با ابعاد بالا، طلسم بعد است که در آن برخی ابعاد (ویژگی‌ها) منجر به پنهان‌شدن داده‌های پرت می‌گردند. برای حل این مسئله، ابعادی که حاوی اطلاعات ارزشمندی در دادگان با ابعاد بالا جهت تشخیص داده پرت هستند، جستجو می‌شوند تا با نگاشت دادگان به زیرفضای متشکل از این ابعاد مرتبط، داده‌های پرت برجسته‌تر و قابل شناسایی شوند. این مقاله با معرفی یک روش جدید انتخاب زیرفضای مرتبط محلی و توسعه یک رویکرد امتیازدهی داده پرت مبتنی بر چگالی محلی، امکان تشخیص داده پرت در دادگان با ابعاد بالا را فراهم می‌نماید. در ابتدا، یک الگوریتم برای انتخاب زیرفضای مرتبط محلی بر اساس آنتروپی محلی ارائه می‌شود تا بتواند برای هر نقطه داده با توجه به داده‌های همسایه‌اش یک زیرفضای مرتبط انتخاب کند. سپس هر نقطه داده در زیرفضای انتخابی متناظرش با یک روش امتیازدهی پرت محلی مبتنی بر چگالی امتیازدهی می‌شود، به طوری که با در نظر گرفتن یک پهنای باند تطبیقی جهت تخمین چگالی هسته سعی می‌شود که اختلاف جزئی بین چگالی یک نقطه داده نرمال با همسایه‌هایش از بین رفته و به اشتباه به عنوان داده پرت تشخیص داده نشود و در عین حال، تخمین کمتر از مقدار واقعی چگالی در نقاط داده پرت، منجر به برجسته‌شدن این نقاط داده گردد. در پایان با آزمایش‌های تجربی روی چندین دادگان دنیای واقعی، الگوریتم پیشنهادی تشخیص داده پرت زیرفضای مبتنی بر آنتروپی محلی با چند تکنیک تشخیص داده پرت بر حسب دقت تشخیص مقایسه شده است. نتایج تجربی نشان می‌دهد که الگوریتم پیشنهادی مبتنی بر معیار آنتروپی محلی و روش پیشنهادی امتیازدهی داده پرت توانسته است به دقت بالایی جهت تشخیص داده پرت دست یابند.

 

کلیدواژه: تشخیص داده پرت، داده‌های با ابعاد بالا، انتخاب زیرفضای مرتبط محلی، آنتروپی محلی.

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 برای هر نقطه داده با توجه به نرخ میانگین چگالی محلی img0نزدیک‌ترین همسایه‌اش 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

img0 

شكل 1: روندنمای روش پیشنهادی تشخیص داده پرت زیرفضای مبتنی بر آنتروپی.

 

 

بالا، باید دارای مزایای زیر باشد: انتخاب ابعاد مرتبط بدون در نظر گرفتن هیچ گونه فرضی روی ابعاد و توزیع داده‌ها، امکان تشخیص چندین نوع داده پرت با انتخاب زیرفضاهای مرتبط به صورت محلی، بهبود قدرت تفکیک معیار امتیازدهی پرت محلی با استفاده از پهنای تطبیقی و در عین حال، کاهش اختلاف‌های ناچیز بین چگالی یک نقطه و همسایگانش به منظور کاهش تعداد داده‌های نرمالی که به اشتباه به عنوان داده پرت، تشخیص داده می‌شوند.

3-       روش پیشنهادی

دست‌یافتن به دقت و کارایی بالا در مسئله تشخیص داده‌های پرت روی دادگان با ابعاد بالا، یک چالش است. اکثر روش‌های موجود در تشخیص داده‌های پرت با ابعاد بالا ناکارامد هستند. در این بخش، یک روش انتخاب زیرفضای مرتبط محلی برای کاهش تعداد ابعاد پیشنهاد داده می‌شود که بر اساس میزان اطلاعات یک نقطه داده در راستای ابعاد مختلف، ویژگی‌های مرتبط برای تعیین پرت‌بودن آن نقطه داده شناسایی می‌شوند. سپس با نگاشت کل دادگان به زیرفضای به دست آمده برای نقطه داده مفروض، درجه پرت‌بودن آن نقطه داده محاسبه می‌گردد.

برای توصیف روش پیشنهادی، ابتدا برخی نمادگذاری‌های مورد استفاده معرفی می‌شود. فرض کنید که img0 دادگانی شامل img0 نقطه داده در فضای ویژگی img0بعدی می‌باشد که مجموعه ویژگی‌ها به صورت img0 است.

روند کلی الگوریتم پیشنهادی در شکل 1 آمده است. ابتدا نرمال‌سازی داده‌ها (یا مقیاس‌بندی ویژگی‌ها) ضروری است، زیرا ویژگی‌های با مقادیر بزرگ‌تر در محاسبه فاصله و همچنین در ساختار همسایگی بر سایر ویژگی‌ها تسلط دارند. معمولاً در تشخیص داده‌های پرت، روش نرمال‌سازی حداقل- حداکثر 1(min-max) که هر ویژگی را به بازه img0 نرمال‌سازی می‌کند استفاده می‌شود [23]. نرمال‌سازی min-max، تبدیل خطی زیر را روی مقادیر ویژگی img0 انجام می‌دهد

img0        (1)

که img0 و img0 به ترتیب برابر مقادیر مینیمم و ماکسیمم ویژگی img0 هستند و بدین ترتیب با نرمال‌سازی تمام ویژگی‌ها (ستون‌ها)، ماتریس داده img0 تبدیل به img0 می‌شود.

در این مقاله مشابه با HiCS [17] و گروه‌بندی ویژگی2 [24]، گام انتخاب زیرفضای مرتبط و امتیازدهی پرت به صورت مسئله‌های مجزا جداسازی شده که با این جداسازی می‌توان به طور عمیق روی هر یک از این مسئله‌ها پژوهش کرد. گام‌های روش پیشنهادی آمده در شکل 1، به طور کامل در زیربخش‌های بعدی شرح داده می‌شوند.

3-1 تخمین چگالی هسته تطبیقی برای تشخیص داده پرت

تخمین چگالی هسته 3(KDE) یک روش غیر پارامتری برای تخمین تابع چگالی احتمال متغیرهای تصادفی است. پهنای باند نقش مهمی در کیفیت KDE دارد. روش تخمین چگالی هسته img0نزدیک‌ترین همسایگی 4(kNN-KDE)، گونه مهمی از روش تخمین چگالی هسته می‌باشد که در آن پهنای باند به صورت محلی انتخاب می‌گردد. در مسئله تشخیص داده پرت، استفاده از روش تخمین چگالی kNN-KDE دارای مزیت‌های امکان به کارگیری یک پهنای باند هسته تطبیقی، کاهش پیچیدگی محاسباتی و از دست نرفتن اختلاف‌های محلی در چگالی به دلیل استفاده از img0نزدیک‌ترین همسایگی به جای کل نقاط دادگان می‌باشد.

در این مقاله از روش kNN-KDE برای تخمین چگالی محلی استفاده می‌شود. در این تخمین‌گر چگالی هسته، مقدار چگالی برای نقطه داده img0 با توجه به img0نزدیک‌ترین همسایه‌اش به صورت زیر تعریف می‌گردد

img0        (2)

که پارامتر img0 پهنای باند، img0 تعداد ابعاد نقاط داده، img0 تابع هسته و img0 فاصله اقلیدسی بین نقاط داده img0 و img0 می‌باشد. چگالی نقطه داده img0 با استفاده از میانگین تخمین چگالی با توجه به کل نقاط همسایگی‌اش تخمین زده می‌شود.

در داده‌های نااریب5، توزیع نقاط داده در بخش‌های مختلف، متفاوت است و به کارگیری پهنای باند ثابت در تشخیص داده پرت در دادگانی شامل چندین خوشه با چگالی‌های متفاوت، منجر به عملکرد مناسبی نمی‌گردد. بنابراین منطقی نیست که یک پهنای باند ثابت برای کل نقاط دادگان به کار گرفته شود. یک روش رایج برای تعیین پهنای تطبیقی در مسایل تخمین چگالی و تشخیص داده پرت [25]، به کارگیری مقادیر کوچک پهنای باند img0 در نواحی با چگالی بالا و مقادیر بزگ img0 در نواحی با چگالی پایین است. اما در مسئله تشخیص داده پرت، نواحی با چگالی بالا مورد توجه نیستند، بنابراین با در نظر گرفتن یک پهنای باند بزرگ می‌توان چگالی را هموار6 تخمین زد و بدین ترتیب واریانس امتیاز پرت بین نقاط نرمال را کاهش داد. در نواحی با چگالی پایین، پهنای باند باریک منجر به تخمین چگالی‌های کوچک‌تر می‌شود که این می‌تواند باعث برجسته‌نمودن نقاط داده پرت گردد. بنابراین در مسئله تشخیص داده پرت بر عکس مسئله تخمین چگالی، انتخاب یک پهنای باند بزرگ در نواحی 
با چگالی بالا و یک پهنای باند کوچک در نواحی با چگالی پایین ترجیح داده می‌شود.

در این مقاله از یک پهنای باند متفاوت برای هر نقطه داده 
img0 استفاده خواهد شد. فرض کنید که برای img0امین نقطه داده، img0 برابر با میانگین فاصله تا img0نزدیک‌ترین همسایه‌اش یعنی img0 است و img0 و img0 برابر کوچک‌ترین و بزرگ‌ترین مقادیر در مجموعه img0 باشند. با الهام از پهنای باند تطبیقی ارائه‌شده در روش Adaptive-KD [4]، از img0 به عنوان پهنای باند نقطه داده img0ام استفاده می‌شود که img0 عامل مقیاس‌بندی برای کنترل اثر هموارسازی سراسری و img0 یک مقدار مثبت بسیار کوچک (برای مثال، img0) برای اطمینان از غیر صفر شدن پهنای باند می‌باشد. در روش Adaptive-KD [4]، برای هر نقطه داده به صورت تطبیقی یک پهنای باند محاسبه و بر اساس آن، چگالی نقطه داده مفروض تعیین می‌شود. در حالی که روش پیشنهادی پس از محاسبه پهنای باند یک نقطه داده بر اساس فاصله تا img0نزدیک‌ترین همسایگی و تعداد ابعاد زیرفضا، از این پهنای باند برای محاسبه چگالی نقاط همسایگی نیز استفاده می‌کند تا اختلاف‌های جزئی بین چگالی نقاط داده نرمال را کاهش دهد.

در اینجا تابع هسته گاوسی به کار گرفته شده است. بدین ترتیب مدل KDE مورد استفاده در این مقاله به صورت زیر می‌باشد

img0        (3)

که img0 است.

در گام انتخاب ابعاد مرتبط، نیاز به محاسبه چگالی در راستای یک ویژگی است. همچنین در مرحله امتیازدهی به منظور محاسبه امتیاز پرت نقاط داده مختلف در زیرفضاهای محلی متناظر با تعداد ابعاد متفاوت، 
نیاز به محاسبه چگالی در این زیرفضاها است. فرض کنید که زیرفضای مد نظر (ویژگی img0ام یا زیرفضای انتخابی متناظر با نقطه داده img0ام) با img0 نمایش داده شود. مدل KDE در (3) برای محاسبه چگالی در زیرفضای img0 به صورت زیر درمی‌آید

img0        (4)

که img0 نگاشت نقطه داده img0ام به زیرفضای img0، img0 تعداد ابعاد زیرفضای img0، img0 شامل img0نزدیک‌ترین همسایه نقطه داده img0 در زیرفضای img0 و img0 برابر پهنای باند نقطه داده img0ام در زیرفضای img0 می‌باشد. نحوه محاسبه پارامتر img0 جهت تخمین چگالی نقطه داده img0ام در زیرفضای img0 در گام‌های انتخاب ابعاد و امتیازدهی داده پرت، در زیربخش‌های 3-2 و 3-3 آورده شده است.

3-2 انتخاب زیرفضای مرتبط مبتنی بر آنتروپی

در تئوری اطلاعات، آنتروپی توسعه‌یافته توسط شانون یک معیار مؤثر برای اندازه‌گیری اطلاعات یا عدم قطعیت برای یک متغیر است [26]. مفهوم آنتروپی برای تشخیص داده پرت بسیار شهودی است زیرا حضور داده پرت، آنتروپی دادگان را افزایش می‌دهد. همچنین نقطه داده پرت در مقایسه با همسایه‌هایش دارای چگالی کمتر و اطلاعات بیشتری است.

فرض کنید که img0 یک متغیر تصادفی و img0 برابر مجموعه مقادیری که متغیر img0 می‌تواند اختیار کند، باشد و img0 تابع احتمال متغیر تصادفی img0 را نمایش دهد. آنتروپی img0 می‌تواند به صورت (5) تعریف گردد

img0        (5)

در این مقاله، پیرو تعریف شانون از آنتروپی، آنتروپی محلی7 تعریف و 
به منظور انتخاب زیرفضای مرتبط به کار گرفته می‌شود. هدف از انتخاب زیرفضای مرتبط، هرس‌کردن ابعاد بی‌ربط از طریق شناسایی ابعادی است که حاوی اطلاعات کمی هستند.

برای اندازه‌گیری میزان اطلاعات محلی نقطه داده img0 در راستای ویژگی img0ام img0، ابتدا یک دادگان محلی به صورت kNN در راستای img0امین ویژگی تعریف می‌شود img0 که آنتروپی‌اش به عنوان آنتروپی محلی اشاره می‌شود. همچنین بر اساس این همسایگی، مقدار اطلاعات محلی نقطه داده img0 در راستای ویژگی img0ام به صورت زیر محاسبه می‌گردد

img0        (6)

که img0 احتمال نقطه داده img0 در راستای ویژگی img0 است. برای محاسبه مقدار احتمال img0، لازم است مقدار چگالی نقطه داده img0 و نقاط همسایگی‌اش در راستای ویژگی img0 محاسبه و سپس نرمال‌سازی گردد. مقادیر چگالی هر یک از نقاط img0 در راستای ویژگی img0ام با استفاده از محاسبه پهنای باند img0 طبق (7) و سپس با جایگذاری در (4) تعیین می‌شوند

img0        (7)

که img0 برابر میانگین فاصله img0 تا img0نزدیک‌ترین همسایه‌اش 
در راستای ویژگی img0ام و img0 و img0 به ترتیب برابر کوچک‌ترین و بزرگ‌ترین مقادیر در مجموعه img0 هستند. بنابراین با نرمال‌سازی چگالی img0 نسبت به مجموع چگالی نقاط همسایگی‌اش، احتمال img0 به نقطه داده img0 تخصیص داده می‌شود

img0        (8)

آنتروپی محلی نقطه داده img0 در راستای ویژگی img0 می‌تواند به صورت زیر تعریف گردد

img0        (9)

که img0 بیانگر img0نزدیک‌ترین همسایه به نقطه داده img0 در راستای img0امین ویژگی است.

بر طبق این شهود که نقطه داده پرت در مقایسه با همسایه‌هایش دارای مقدار احتمال کوچک‌تر و حاوی اطلاعات بیشتری است، می‌توان ابعاد مرتبط را انتخاب کرد. ویژگی img0 برای تشخیص پرت‌بودن/ نبودن نقطه داده img0 مرتبط است، اگر مقدار اطلاعات نقطه داده img0 نسبت به مقدار میانگین اطلاعات نقاط همسایگی‌اش (آنتروپی محلی) در راستای ویژگی ‌img0 بیشتر باشد

img0        (10)

بعد از محاسبه مقدار اطلاعات و آنتروپی محلی img0 در طول تمام ویژگی‌ها، می‌توان زیرفضای مرتبط با تشخیص داده پرت در این نقطه داده را به صورت زیر انتخاب کرد

img0        (11)

در الگوریتم 1، فرایند انتخاب زیرفضای مرتبط مبتنی بر آنتروپی آورده شده است (شکل 2).

3-3 نگاشت داده‌‌ها و امتیازدهی داده‌های پرت

در داده‌های با ابعاد بالا ممکن است با توجه به تعداد زیاد ویژگی‌های بی‌ربط، برخی داده‌های پرت گم شوند. در این مقاله با پیشنهاد یک روش انتخاب زیرفضای مرتبط محلی برای تشخیص داده‌های پرت سعی شده که اکثر داده‌های پرت شناسایی شوند. پس از این که برای هر نقطه داده، یک زیرفضای مرتبط استخراج شد، لازم است که کارایی این زیرفضاهای محلی در تشخیص داده‌های پرت ارزیابی گردد.

برای امتیازدهی داده‌های پرت، هر نقطه داده img0 در فضای اولیه با ابعاد بالا به زیرفضای مرتبط متناظرش با ابعاد پایین‌تر نگاشت می‌شود img0. با به کارگیری تعریف ویژگی مرتبط در (10)، می‌توان نقاط داده‌ای را که در راستای کل ابعاد، حاوی اطلاعات کمتری در مقایسه با همسایه‌ها هستند (یعنی در طول هیچ یک از ویژگی‌ها در ناحیه تنک قرار ندارند) نرمال در نظر گرفت و امتیاز پرت صفر به آنها تخصیص داد. در اینجا برای تعیین میزان پرت‌بودن نقاط دادگان img0، یک معیار نسبی به کار گرفته می‌شود تا میزان انحراف چگالی نقطه داده img0 از نقاط همسایگی‌اش در زیرفضای img0 را اندازه‌گیری کند. برای تعیین نقاط همسایگی img0 در زیرفضای مرتبط متناظرش img0 لازم است کل دادگان اولیه img0 به زیرفضای img0 نگاشت شود تا نقاط همسایگی img0 در فضای نگاشت‌یافته تعیین گردند.

وابستگی شدیدی بین چگالی یک نقطه داده و تعداد ابعاد زیرفضای مرتبط محلی‌اش وجود دارد. با افزایش تعداد ابعاد زیرفضای مرتبط، چگالی نقاط داده کاهش می‌یابند و یک پهنای باند هسته تطبیقی پیشنهاد داده می‌شود که تعداد ابعاد زیرفضا را نیز در نظر می‌گیرد. همچنین به منظور کاهش واریانس چگالی نقاط داده نرمال و در نتیجه، کاهش نرخ مثبت کاذب، در مرحله امتیازدهی نقطه داده img0ام در زیرفضای img0 از پهنای باند تطبیقی استفاده شده است. بدین صورت که پهنای باند نقطه داده img0ام img0 به صورت تطبیقی بر حسب فاصله تا نقاط همسایگی‌اش و تعداد ابعاد زیرفضای img0 با توجه به نسخه چندبعدی قانون اسکات8 [27] تعیین می‌گردد. سپس از همین پهنای باند img0 برای محاسبه چگالی نقاط همسایگی‌ استفاده می‌شود. با در نظر گرفتن یک پهنای باند یکسان برای نقاط همسایگی، انتظار می‌رود اختلاف‌های جزئی بین مقدار چگالی نقطه img0 و چگالی نقاط همسایگی‌اش از بین رود. بنابراین چگالی نقطه داده img0 و نقاط داده همسایگی‌اش در زیرفضای img0 img0 با استفاده از پهنای باند تطبیقی img0 به دست آمده از (12) و سپس با جایگذاری در (4)، محاسبه می‌شوند

img0        (12)

که img0 تعداد ابعاد زیرفضای مرتبط img0، img0 برابر میانگین فاصله نقطه داده img0 تا img0نزدیک‌ترین همسایه‌اش در زیرفضای img0 و img0 و img0 به ترتیب برابر کوچک‌ترین و بزرگ‌ترین مقادیر در مجموعه img0 می‌باشند.

با فرض این که اندازه دادگان img0 ثابت باشد، پهنای باند تطبیقی img0 تابعی افزایشی بر حسب تعداد ابعاد است. بدین ترتیب با افزایش تعداد ابعاد، پهنای باند نیز افزایش می‌یابد و چگالی نقاط در زیرفضاهای با ابعاد مختلف قابل مقایسه خواهند بود.

پس از تخمین چگالی نقطه داده img0 و همسایگانش در زیرفضای  

[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: img0

Output: img0

_________________________________________________________________________________________________________________________

Initialization: Set img0

for each img0 in img0:

·       img0 column of dataset matrix img0

     for each img0 in img0:

·       img0= Compute img0for data point img0 in img0

·       img0=Compute the average Euclidean distance img0 to its img0 nearest neighbors

    end

·       Compute img0 and img0 from all the quantities img0 

end

for eachimg0 in img0:

    for each img0 in img0:

·       img0=img0 column of dataset matrix img0

·       Compute the kernel width of the ith data point: img0

·       Compute the local density of the ith data point: img0

·       Compute the sum of local density for img0 nearest neighbors of the ith data point using the kernel width of the ith data point:

   img0

·       Compute the probability of the ith data point and its img0 on feature img0 by means of the normalization of their local density:

    img0

·       Compute the information provided by the ith data on feature img0: img0

·       Compute the local entropy of the ith data point on feature img0: img0

        if img0 :

·       Add img0 to img0:

        end

    end

end

 

 

شكل 2: الگوریتم 1.

 

 

img0، معیار عامل پرت مبتنی بر چگالی نسبی نقطه داده img0ام به صورت زیر تعریف می‌شود

img0        (13)

که img0 برابر نرخ میانگین چگالی نقاط همسایگی img0 به چگالی نقطه داده img0 است. اگر img0 بزرگ‌تر از 1 باشد، آن گاه نقطه داده img0 خارج از یک ناحیه چگال قرار دارد و بنابراین یک داده پرت می‌باشد. اگر img0 کوچک‌تر یا مساوی با 1 باشد، آن گاه نقطه داده img0 توسط یک ناحیه همسایگی با چگالی یکسان یا توسط ناحیه تنک‌تر احاطه شده که یک داده پرت نیست. الگوریتم نگاشت و امتیازدهی داده‌های پرت در الگوریتم 2 توصیف شده است (شکل 3).

در زیربخش‌های بالا، گام‌های الگوریتم با تمرکز بر انتخاب زیرفضای مرتبط و امتیازدهی داده پرت شرح داده شد. حال در الگوریتم 3، این مراحل در کنار هم قرار گرفته و شبه‌کد کلی روش پیشنهادی برای تشخیص داده‌های پرت با ابعاد بالا آورده شده است (شکل 4).

سرانجام به طور خلاصه روی پیچیدگی محاسباتی روش پیشنهادی بحث می‌شود. در الگوریتم پیشنهادی، زیرفضای مرتبط نقطه داده img0 بر اساس آنتروپی و اطلاعات محلی محاسبه شده و سپس میزان پرت‌بودن این نقطه داده در زیرفضای مرتبط بر اساس مقایسه چگالی محلی‌اش با چگالی نقاط داده همسایگی‌اش تعیین می‌گردد. در الگوریتم 1 بر اساس نقاط داده یک‌بعدی در راستای یک ویژگی، مرتبط‌بودن آن ویژگی به نقاط داده مختلف بررسی می‌گردد که محاسبات عمده در الگوریتم 1 مربوط به تعیین نقاط داده همسایگی است، به طوری که پیچیدگی محاسباتی یافتن kNN برای یک نقطه داده در راستای یک ویژگی برابر 

Algorithm 2: Local Density-based Outlier Scoring (LDOS)

Input: img0

Output: img0

___________________________________________________________________________________________________

for each img0 in img0:

·       img0=project data matrix img0 into img0

·       img0=compute img0 for data point img0 in the subspace img0

·       Compute the local density of the data point img0 and its neighbors img0 as follows:

   img0

   where img0 and img0

·       Compute the Relative Density-based Outlier Factor(RDOF) for data point img0:

    if img0:

        img0

    else

    img0, where img0

    end

end

شكل 3: الگوریتم 2.

 

 

Algorithm 3: Local Entropy-based Subspace Outlier Detection (LESOD)

Input: img0

Output: Outlier data points

___________________________________________________________

·       img0= Applying feature normalization/scaling on img0 

·       img0=Select the local relevant subspaces for outlier detection using
Algorithm 1 : img0

·       img0=Compute outlier scores for all data points in img0 using Algorithm 2: img0

Detect outlier data points given as img0 score values in the previous step

شكل 4: الگوریتم 3.

 

img0 است، البته با استفاده از ساختار درختی می‌تواند برای کل نقاط دادگان به img0 کاهش یابد. بدین ترتیب پیچیدگی زمانی الگوریتم 1، img0 است. در الگوریتم 2 برای امتیازدهی یک نقطه داده، نیاز به نگاشت دادگان به زیرفضای مرتبط متناظر با آن نقطه داده، یافتن نقاط همسایگی‌اش و سپس امتیازدهی نقطه داده مفروض است که پیچیدگی محاسباتی این عملیات از مرتبه img0 است. بنابراین پیچیدگی محاسباتی کلی روش تشخیص داده پرت آمده در الگوریتم 3 برابر img0 است. پیچیدگی محاسباتی روش پیشنهادی با برخی تکنیک‌های محلی تشخیص داده پرت با ابعاد بالا SOD [15]، COP [19] و OUTRES [16] با پیچیدگی به ترتیب برابر با img0، img0 و img0 قابل مقایسه است. پیچیدگی محاسباتی روش پیشنهادی بر حسب تعداد ابعاد، خطی است در حالی که پیچیدگی الگوریتم‌های 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 نرخ مثبت صحیح 2img0 در مقابل نرخ مثبت کاذب 

[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

 

 

1img0 با در نظر گرفتن حد آستانه‌های مختلف، ترسیم می‌گردد که img0 و img0 به صورت زیر محاسبه می‌شوند

img0        (14)

که img0، img0، img0 و img0 به ترتیب بیانگر تعداد نقاط داده‌ای که به درستی پرت تشخیص داده شده‌اند، تعداد کل نقاط داده پرت موجود در دادگان، تعداد نقاط داده‌ای که به اشتباه پرت تشخیص داده شده‌اند و تعداد کل نقاط نرمال در دادگان است. برای محاسبه سطح زیر منحنی ROC روش‌های ذوزنقه‌ای خطی2، ذوزنقه‌ای لگاریتمی3 و ذوزنقه‌ای خطی- لگاریتمی4 وجود دارد. روش ذوزنقه‌ای خطی از درون‌یابی خطی5 بین دو نقطه نمودار ROC برای محاسبه AUC استفاده می‌کند. برای یک بازه زمانی مشخص img0، AUC می‌تواند به صورت زیر محاسبه گردد

img0        (15)

که در آن img0 و img0 به ترتیب برابر مقادیر منحنی ROC در زمان‌های img0 و img0 هستند.

در آزمایش‌ها، روش پیشنهادی با چهار الگوریتم شناخته‌شده تشخیص داده پرت LOF [10]، HiCS [17]، COP [19] و Adaptive-KD [4] با استفاده از AUC مقایسه گردیده است.

4-2 نتایج

پارامترهای روش HiCS مطابق پیشنهاد نویسندگان [17] به صورت img0، img0 و img0 تنظیم شده است. پارامتر تعداد نزدیک‌ترین همسایه img0 در هر سه روش LOF، HiCS و Adaptive-KD مشابه با برخی کارهای تشخیص داده پرت قبلی [14] و [18] برابر img0 تنظیم شده است. در COP، پارامتر img0 باید به اندازه کافی بزرگ و مقدارش از تعداد ابعاد دادگان بزرگ‌تر باشد تا قادر به تخمین ساختار کواریانس محلی باشد. بنابراین از img0 روی تمام دادگان‌ استفاده شده است، به جز دادگان Arrhythmia که img0 برابر 200 تنظیم گردیده است. نتایج این سه روش روی هر یک از دادگان‌ آمده در جدول 1 بر حسب مقدار AUC در جدول 2 گزارش شده است. در این مقاله، از پیاده‌سازی‌های انجام‌شده الگوریتم‌های LOF [10]، HiCS [17] و COP [19] در چارچوب ELKI [29] استفاده گردیده و الگوریتم Adaptive-KD [4] به زبان پایتون پیاده‌سازی شده است.

در این آزمایش‌ها از هسته گاوسی استفاده شده که برای تعیین پهنای باند تطبیقی، نیاز به تنظیم سه پارامتر img0، img0 و img0 دارد. پارامترهای img0 و img0 به ترتیب برابر با 5/0 و 5-10 و پارامتر تعداد نزدیک‌ترین همسایه img0 برای هر دو گام تعیین انتخاب زیرفضای مرتبط و امتیازدهی داده پرت برابر img0 تنظیم شده است. با تنظیم این پارامترها، مقادیر 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-       نتیجه‌گیری و کارهای آتی

تشخیص داده پرت در فضای داده با ابعاد بالا، چالش‌برانگیز و هزینه‌بر است. در این خصوص، انتخاب زیرفضای مرتبط نقش مهمی در دقت و کارایی مسئله تشخیص داده پرت بازی می‌کند. در این مطالعه، یک روش بدون نظارت تشخیص داده پرت محلی مبتنی بر زیرفضا در داده‌های با ابعاد بالا پیشنهاد شده است. در الگوریتم پیشنهادی، زیرفضای مرتبط برای هر نقطه داده، بر اساس آنتروپی محلی و مقدار اطلاعات آن نقطه داده در دادگان محلی که با استفاده از تخمین چگالی تطبیقی محاسبه شده‌اند، تعریف می‌گردد. زیرفضای مرتبط محلی یک نقطه داده، متشکل از ابعادی است که مقدار اطلاعات آن نقطه داده در راستای آن ابعاد بزرگ‌تر از آنتروپی محلی باشد و بر این اساس، از تأثیر ویژگی‌های بی‌ربط روی تشخیص داده پرت می‌تواند به طور مؤثری جلوگیری کند و منجر به تشخیص داده‌های پرت پنهان‌شده در زیرفضاهای با ابعاد پایین‌تر گردد. همچنین در این مقاله یک روش امتیازدهی داده پرت مبتنی بر تخمین چگالی هسته پیشنهاد داده شده که برای کاهش اختلاف امتیاز پرت بین نقاط داده نرمال و برجسته‌نمودن نقاط داده پرت، از یک پهنای باند تطبیقی که رابطه معکوس با فاصله تا img0نزدیک‌ترین همسایگی دارد استفاده می‌کند. باید اشاره کرد که پهنای باند تطبیقی محاسبه‌شده برای یک نقطه داده، جهت تخمین چگالی نقاط داده همسایگی نیز استفاده می‌شود تا اختلاف‌های جزئی بین مقدار چگالی و امتیاز پرت نقاط داده نرمال از بین رود. با استفاده از دادگان واقعی، نتایج تجربی تأیید می‌کنند که روش پیشنهادی ما برای تشخیص داده پرت در دادگان با ابعاد بالا کارامد است.

در الگوریتم پیشنهادی برای انتخاب ابعاد مرتبط از معیار کلی آنتروپی استفاده شده که در کارهای آتی می‌توان از فاصله کولبک‌- لیبلر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

 

 


مقالات مرتبط

حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات رایمگ است.
حق نشر © 1403-1396

صفحه اصلی| عضویت/ ورود| درباره رایمگ| تماس با ما|
[English] [العربية] [en] [ar]