Manuscript ID : 1401121941529 Visit : 1695 Page: 273 - 283

Article Type: Original Research

Combination of Instance Selection and Data Augmentation Techniques for Imbalanced Data Classification

Subject Areas : electrical and computer engineering

Parastoo Mohaghegh ¹ , Samira Noferesti ² , Mehri Rajaei ³

1 - Faculty of Electrical and Computer Engineering, University of Sistan and Baluchestan
2 -
3 - University of Sistan and Baluchestan

Received: 2023-03-10 Accepted : 2023-10-02 Published : 2024-04-17

Keywords: Instance selection, data augmentation, classification, imbalanced data, data mining, machine learning,

Abstract :

Mohaghegh, S. Noferesti*, and M. Rajaei Abstract: In the era of big data, automatic data analysis techniques such as data mining have been widely used for decision-making and have become very effective. Among data mining techniques, classification is a common method for decision making and prediction. Classification algorithms usually work well on balanced datasets. However, one of the challenges of the classification algorithms is how to correctly predicting the label of new samples based on learning on imbalanced datasets. In this type of dataset, the heterogeneous distribution of the data in different classes causes examples of the minority class to be ignored in the learning process, while this class is more important in some prediction problems. To deal with this issue, in this paper, an efficient method for balancing the imbalanced dataset is presented, which improves the accuracy of the machine learning algorithms to correct prediction of the class label of new samples. According to the evaluations, the proposed method has a better performance compared to other methods based on two common criteria in evaluating the classification of imbalanced datasets, namely "Balanced Accuracy" and "Specificity".

References:

[1] H. Kim, H. Cho, and D. Ryu, "Corporate bankruptcy prediction using machine learning methodologies with a focus on sequential data," Computational Economics, vol. 59, pp. 1231-1249, 2022.
[2] D. Yousif Mikhail, F. Al-Mukhtar, and S. Wahab Kareem, "A comparative evaluation of cancer classification via TP53 gene mutations using machine learning," Asian Pacific J. of Cancer Prevention, vol. 23, no. 7, pp. 2459-2467, Jul. 2022.
[3] L. Yang and Y. Jiachen, "Few-shot cotton pest recognition and terminal," Computers and Electronics in Agriculture, vol. 169, Article ID: 105240, 2020.
[4] P. Kumar, R. Bhatnagar, K. Gaur, and A. Bhatnagar, "Classification of imbalanced data: review of methods and applications," IOP Conf. Series: Materials Science and Engineering, vol. 1099, no 1, Article ID: 012077, 2021.
[5] C. F. Tsai, W. C. Lin, Y. H. Hu, and G. T. Yao, "Under-sampling class imbalanced datasets by combining clustering analysis and instance selection," Information Sciences, vol. 477, pp. 47-54, Mar. 2019.
[6] I. Czarnowski and P. Jedrzejowicz, "An approach to imbalanced data classification based on instance selection and over-sampling," in Proc. 11th Int. Conf.on Computational Collective Intelligence, pp. 601-610, Hendaye, France, 4-6 Sept. 2019.
[7] D. Gan, J. Shen, B. An, M. Xu, and N. Liu, "Integrating TANBN with cost sensitive classification algorithm for imbalanced data in medical diagnosis," Computers & Industrial Engineering, vol. 140, Article ID: 106266, Feb. 2020.
[8] L. Yang and Y. Jiachen, "Meta-learning baselines and database for few-shot classification in agriculture," Computers and Electronics in Agriculture, vol. 182, Article ID: 106055, Mar. 2021.
[9] Z. Peng, Z. Li, J. Zhang, Y. Li, G. J. Qi, and J. Tang, "Few-shot image recognition with knowledge transfer," in Proc. of the IEEE/CVF Int. Conf. on Computer Vision, pp. 441-449, Seoul, South Korea, 27 Oct.-2 Nov. 2019.
[10] F. Jimenez, G. Sanchez, J. Palma, and G. Sciavicco, "Three-objective constrained evolutionary instance selection for classification: wrapper and filter approaches," Engineering Applications of Artificial Intelligence, vol. 107, Article ID: 104531, Jan. 2022.
[11] G. E. Melo-Acosta, F. Duitama-Muñoz, and J. D. Arias-Londoño, An Instance Selection Algorithm for Big Data in High Imbalanced Datasets Based on LSH, arXiv: 2210.04310, Oct. 2022.
[12] X. Chao and L. Zhang, "Few-shot imbalanced classification based on data augmentation," Multimedia Systems, vol. 29, no. 5, pp. 2843-2851, 2023.
[13] S. Bej, N. Davtyan, M. Wolfien, M. Nassar, and O. Wolkenhauer, "LoRas: an oversampling approach for imbalanced datasets," Machine Learning, vol. 110, pp. 279-301, 2021.
[14] J. C. Requelme, J. S. Aguilar-Ruiz, and M. Toro, "Finding representative patterns with ordered projections," Pattern Recognition, vol. 36, no. 4, pp. 1009-1018, Apr. 2003.
[15] D. R. Wilson and T. R. Martinez, "Instance pruning techniques," in Proc. of the 14th Int. Conf. on Machine Learning, pp. 400-411, 8-12 Jul. 1997.
[16] M. Moran, T. Cohen, Y. Ben-Zion, and G. Gordon, "Curious instance selection," Information Sciences, vol. 608, pp. 794-808, Aug. 2022.
[17] N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, "SMOTE: synthetic minority over-sampling technique," J. of Artificial Intelligence Research, vol. 16, pp. 321-357, Jan. 2002.
[18] ش. سرگلزایی، ف. حسین‌زاده سلجوقی و ﻫ. آقایاری، "ارائه روشی نوین برای رتبه‌بندی اعداد فازی با استفاده از مرکز محیطی دایره و کاربرد آن در ارزیابی عملکرد مدیریت زنجیره تأمین،" نشریه تصمیم‌گیری و تحقیق در عملیات، دوره 3، شماره 3، صص. 236-248، پاییز 1397.
[19] S. N. Kumpati and A. T. Mandayam, Learning Automata: An Introduction, Courier Corporation, 2012.
[20] J. C. Dominguz, et al., "Teaching chemical engeering using Jupyter notebook: problem generators and lecturing tools," Education for Chemical Engineers, vol. 37, pp. 1-10, Oct. 2021.
[21] M. Grandini, E. Bagli, and G. Visani, Multi-Class Classification: An Overview, arXiv:2008.05756, Aug. 2020.

Full-Text:

معرفي يک روش جديد خوشه‌يابي خودکار

مقاله پژوهشی

ترکیب تکنیک‌های انتخاب نمونه و داده‌افزایی برای
حل مسئله طبقه‌بندی مجموعه داده‌های نامتوازن

پرستو محقق، سمیرا نوفرستی و مهری رجائی

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

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

1- مقدمه

حجم کلان‌داده‌ها به‌گونه‌ای عظیم است که چالش‌های ذخیره‌سازی و تحلیل داده‌ها، کشف دانش و پیچیدگی محاسباتی را به دنبال دارد. از جمله کلان‌داده‌ها می‌توان به پروژه ژنوم انسان² اشاره کرد که چندین گیگابایت داده را از کد ژنتیکی انسان تجمیع کرده است. داده‌کاوی، مجموعه‌ای از روش‌های قابل اعمال بر مجموعه داده‌های بزرگ و پیچیده به‌منظور کشف الگوهای پنهان در میان داده‌هاست.

در میان تکنیک‌های مختلف داده‌کاوی، طبقه‌بندی³ از تکنیک‌هایی است که بیشترین استفاده را برای مسائل مختلف داراست؛ مانند پیش‌بینی ورشکستگی و تشخیص سرطان [1] و [2]. طبقه‌بندی یکی از روش‌های یادگیری ماشین است که بر اساس یک مجموعه داده آموزشی از نمونه‌های برچسب‌خورده به ساخت یک مدل پیش‌بینی‌کننده می‌پردازد که قادر است برچسب کلاس نمونه‌های جدید را تعیین کند.

یکی از مشکلاتی که الگوریتم‌های طبقه‌بندی با آن مواجه هستند، مجموعه داده‌های نامتوازن است. مشکل عدم توازن زمانی رخ می‌دهد که تعداد نمونه‌ها در یک کلاس (که کلاس اقلیت⁴ نامیده می‌شود) در مقایسه با سایر کلاس‌ها بسیار کمتر باشد؛ در حالی که کلاس اقلیت از لحاظ کاربرد اهمیت فراوانی دارد. به عنوان مثال می‌توان به مسائل زیر اشاره کرد. در شناسایی آفت‌های کشاورزی، برخی آفت‌ها پررخداد هستند و به‌کرات نمونه‌ دارند و برخی آفت‌ها به‌ندرت مشاهده می‌شوند و به همین دلیل، تعداد نمونه‌های کمی دارند [3]. در تشخیص نفوذ به شبکه‌های کامپیوتری (تشخیص ترافیک نرمال از ترافیک غیرنرمال شبکه) و تشخیص اشیا- جایی که اغلب تصاویر مجموعه آموزش فاقد شیء مورد نظر هستند- نیز برخی از کلاس‌ها تعداد نمونه‌های کمی دارند [4].

برای حل مشکل مجموعه‌ داده‌های نامتوازن، رویکردهای متعددی در سه سطح داده، مدل و ترکیبی ارائه شده‌اند. هدف رویکردهای سطح داده کاهش نسبت عدم تعادل بین کلاس‌های اکثریت⁵ و اقلیت با انتخاب نمونه⁶ کلاس اکثریت یا داده‌افزایی⁷ در کلاس اقلیت است [5] و [6]. رویکردهای سطح مدل عمدتاً توابع حساس به هزینه⁸ را معرفی می‌کنند [7]. رویکردهای این سطح غالباً شامل روش فرایادگیری⁹ و روش یادگیری انتقالی¹⁰ هستند [8] و [9]. روش‌های ترکیبی نیز مزایای رویکردهای سطح داده و سطح مدل را ترکیب می‌کنند.

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

به‌طور کلی، تکنیک‌های موجود برای حل مسئله مجموعه داده‌های نامتوازن به دو دسته انتخاب نمونه و داده‌افزایی تقسیم می‌شوند. روش‌های انتخاب نمونه، سعی در کاهش تعداد نمونه‌های کلاس اکثریت به‌منظور رسیدن به تعادل نسبی در اندازه کلاس‌ها دارند [10] و [11]. در روش‌های انتخاب نمونه، گاهی بخش عمده‌ای از اطلاعات که برای تهیه و برچسب‌گذاری آنها زمان و هزینه زیادی صرف شده است، از دست می‌روند و مشکل انتخاب نمونه بیش از حد رخ می‌دهد که منجر به کاهش عملکرد طبقه‌بند می‌شود.

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

برای اجتناب از مشکلات ذکرشده، در این مقاله روشی ترکیبی ارائه می‌شود که از مزایای هر دو روش انتخاب نمونه و داده‌افزایی بهره می‌برد. در روش پیشنهادی، ابتدا با ترکیب دو روش داده‌افزایی به گسترش مجموعه اقلیت پرداخته می‌شود و سپس با به‌کارگیری یک روش انتخاب نمونه مبتنی بر اتوماتای یادگیر¹¹، نمونه‌هایی از کلاس اقلیت گسترش‌یافته که تأثیر بیشتری بر دقت مدل پیش‌بینی‌کننده دارند، انتخاب می‌شوند. نتایج آزمایش‌های انجام‌گرفته، کارایی روش پیشنهادی را در مقایسه با روش‌های موجود نشان می‌دهند.

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

2- ‌مرور تحقیقات پیشین

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

2-1 تکنیک‌های انتخاب نمونه

تکنیک‌های انتخاب نمونه به دو دسته کلی فیلتر و رپر دسته‌بندی می‌شوند. تکنیک‌های فیلتر اغلب به رویکرد نزدیک‌ترین همسایگان یک نمونه جهت حذف یا حفظ آن وابسته هستند. روش‌های فیلتر بر اساس تابع انتخاب نمونه عمل می‌کنند و از لحاظ محاسباتی بسیار سریع‌تر از روش‌های رپر هستند و برای مجموعه‌ داده‌ها با ابعاد بزرگ نیز مناسب هستند. از جمله این روش‌ها می‌توان به روش پایه POP [14] اشاره کرد. این روش، نمونه‌های مرکزی را حذف و نمونه‌های مرزی را حفظ می‌کند. در متد POP مقدار Weakness برای هر یک از نمونه‌ها حساب می‌شود که نشانگر تعداد دفعاتی می‌باشد که نمونه مد نظر به‌عنوان نمونه مرکزی شناخته شده است. پس از آن، نمونه‌هایی که مقدار Weakness برایشان برابر تعداد ویژگی‌ها باشد، به‌عنوان نمونه مرکزی شناخته می‌شوند و حذف می‌گردند. در [10] یک روش فیلتر برای انتخاب نمونه پیشنهاد شده که بر بهینه‌کردن سه معیار همبستگی، افزونگی و سازگاری داده‌ها به‌صورت همزمان تمرکز می‌کند. در این روش، قیود حفظ نمونه بر مدل‌های بهینه‌سازی تحمیل می‌شوند تا حداکثر درصد نمونه‌هایی را که توسط تصمیم‌گیرنده ایجاد شده است حفظ کنند.

از جمله روش‌های رپر پایه می‌توان به مدل‌های 5-1DROP از ویلسون و مارتینز [15] اشاره کرد که در آن، ترتیب حذف نمونه‌ها اهمیت دارد. بدین صورت که اگر حذف یک نمونه از مجموعه کاهش‌یافته بر دقت طبقه‌بند تأثیری نداشته باشد، آن نمونه از حذف می‌شود. این مدل‌ها به‌ویژه 3DROP پایه بسیاری از روش‌های جدید انتخاب نمونه هستند [11].

تیسای و همکاران [5] روشی را با نام ¹²CBIS پیشنهاد دادند که در آن، مجموعه‌ آموزش نامتوازن با دو کلاس اکثریت و اقلیت بررسی می‌گردد. در گام اول از کلاس اقلیت صرف نظر می‌شود و الگوریتم خوشه‌بندی، نمونه‌های مشابه از کلاس اکثریت را در تعدادی خوشه گروه‌بندی می‌کند که به‌عنوان زیرکلاس‌هایی از کلاس اکثریت شناخته می‌شوند. سپس در گام بعد، الگوریتم انتخاب نمونه پایه مانند الگوریتم ژنتیک بر روی کلیه خوشه‌ها عمل فیلتر را انجام می‌دهد و دو مجموعه داده کاهش‌یافته با نمونه‌های نویزدار و بدون نویز ایجاد می‌شوند. مجموعه با نمونه‌های نویزدار کنار گذاشته می‌شود و مجموعه داده کاهش‌یافته نهایی بدون نویز انتخاب می‌گردد. سپس مجموعه داده کاهش‌یافته نهایی از کلاس اکثریت با نمونه‌های کلاس اقلیت ترکیب شده و به‌عنوان مجموعه آموزشی جدید به طبقه‌بند جهت ارزیابی عملکرد داده می‌شود. نتایج تجربی نشان می‌دهند بعد از اعمال روش CBIS بر روی مجموعه داده نامتوازن، نسبت عدم توازن مجموعه تا حدی کاهش می‌یابد.

در [16] روشی مبتنی بر یادگیری تقویتی برای انتخاب نمونه پیشنهاد شد که ابتدا خوشه‌هایی از نمونه‌ها را بر اساس یک معیار شباهت می‌سازد. سپس عاملی را در نظر می‌گیرد که می‌تواند تدریجاً داده‌ها را به مجموعه کاهش‌یافته نهایی اضافه کند. در یک حلقه، این عامل خوشه‌ای از نمونه‌ها (عمل) را برای اضافه‌شدن به نمونه‌های انتخاب‌شده (حالت)، انتخاب و پاداشی متناسب با کاهش خطای مدل پیش‌بینی‌کننده دریافت می‌کند. خروجی الگوریتم (سیاست عامل) ماتریسی است که توازن بین بهبود مدل و اندازه داده‌ها را نشان می‌دهد. هر درایه از ماتریس، ارزش افزودن یک خوشه به نمونه‌های موجود را نشان می‌دهد و این ماتریس توانایی متعادل‌کردن اهداف کاهش نویز و حجم داده را دارد.

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

شکل 1: مراحل روش پیشنهادی.

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

2-2 تکنیک‌های داده‌افزایی

ایده اصلی در روش‌های داده‌افزایی، گسترش تعداد نمونه‌های کلاس اقلیت برای متوازن‌سازی توزیع نمونه‌ها بین کلاس‌ها است. روش ¹³SMOTE در بین روش‌های داده‌افزایی از محبوبیت بیشتری برخوردار است [17]. ایده اصلی این روش به این صورت است که در کلاس اقلیت برای هر نمونه با توجه به میزان شباهتی که با دیگر نمونه‌های کلاس اقلیت دارد، نزدیک‌ترین همسایگانش از درون کلاس اقلیت تعیین می‌گردند و سپس بین هر دو نمونه از همسایگان، نمونه‌های جدید به‌صورت تصادفی تولید می‌شوند. مشکلی که روش SMOTE دارد این است که نمی‌تواند به‌خوبی بر مشکل توزیع نامتوازن داده‌ها غلبه کند؛ به دلیل اینکه ناحیه تولید نمونه‌ها (کلاس‌ اقلیت) محدود است و فاصله نمونه‌های مرکزی تولیدشده در مجموعه داده‌ای جدید با نمونه‌های مرکزی مجموعه داده آموزشی اصلی زیاد می‌شود.

چائو و ژانگ [12] نیز روش H-SMOTE را با هدف تولید نمونه‌های جدید یکنواخت‌تر و نزدیک‌تر به مرکز کلاس اقلیت معرفی کردند. در این روش عملیات صورت‌گرفته به‌طور عمده از دو عمل نمونه‌برداری و فیلتر نمونه‌های نویزدار تشکیل شده است. ابتدا نمونه مرکزی کلاس اقلیت با میانگین‌گیری از ویژگی‌ها مشخص می‌شود و سپس فاصله منهتن هر نمونه از کلاس اقلیت با مرکز، محاسبه و نمونه جدید در سطح اول تولید می‌گردد. این عمل برای نمونه‌های جدید و نمونه‌های کلاس اقلیت در سطح دوم نیز تکرار می‌شود. گرچه روش H-SMOTE عملکرد بهتری نسبت به الگوریتم‌های پایه مانند SMOTE دارد، اما همچنان مشکل کافی‌نبودن نمونه‌های تولیدشده در سطح اول و دوم برای متوازن‌سازی با افزایش نرخ عدم توازن را دارد.

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

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

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

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

روش پیشنهادی برای متوازن‌سازی کلاس اقلیت و اکثریت که به‌ترتیب با و نشان داده می‌شوند، دو مرحله اصلی دارد: 1) داده‌افزایی کلاس اقلیت با ترکیب دو روش‌ شناخته‌شده H-SMOTE [12]
و LoRAS [13] که منجر به ایجاد یک مجموعه جدید از رکوردهای آموزشی به نام کلاس اقلیت گسترش‌یافته می‌شود و 2) انتخاب نمونه با اتوماتاهای یادگیر بر روی کلاس . مراحل روش پیشنهادی در شکل 1 نشان داده شده‌اند. در ادامه جزئیات هر مرحله تشریح می‌گردد.

3-1 مرحله اول: داده‌افزایی

روش‌های داده‌افزایی، سعی در افزایش نمونه‌های کلاس اقلیت با هدف

(الف)

(ب)

(ج)

(د)

شکل 2: مصورسازی گام‌به‌گام روش داده‌افزایی LoRAS [13].

متعادل‌سازی توزیع نمونه‌ها بین کلاس‌ها دارند. از آنجا که روش پیشنهادی مقاله حاضر، سعی در متعادل‌سازی کلاس اقلیت با کلاس اکثریت دارد، ابتدا داده‌افزایی کلاس اقلیت با دو الگوریتم LoRAS [13] و H-SMOTE [12] صورت می‌گیرد. دلیل انتخاب دو الگوریتم مذکور، محبوبیت و نتایج موفقیت‌آمیز آنها در مقایسه با روش‌های موجود است. الگوریتم H-SMOTE دو مزیت اصلی دارد: توزیع پایدار و یکنواخت نمونه‌های تولیدشده و کارایی الگوریتم در مقایسه با روش‌های موجود [12]. الگوریتم LoRAS همچنین علاوه بر کارایی بالا، توانایی مدیریت

hsmote

شکل 3: داده‌افزایی مبتنی بر الگوریتم H-SMOTE [12].

مجموعه داده‌های بسیار نامتوازن و با ابعاد بالا را دارد [13]. در ادامه به معرفی دقیق‌تر این دو الگوریتم می‌پردازیم.

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

(1)

که مقدار 40 حداکثر تعداد نمونه‌های سایه برای یک نمونه والد را نشان می‌دهد. نمونه‌های سایه به وسیله تعدادی نویز با توجه به توزیع نرمال
با انحراف معیار استاندارد ایجاد می‌شوند و مقدار پیش‌فرض آن می‌باشد. سپس به‌صورت تصادفی به اندازه که پیش‌فرض تعداد ویژگی‌ها است از لیست نمونه‌های سایه، نمونه انتخاب شده و طبق (2) در وزن‌های بردار آفین ضرب می‌شوند و خروجی بردار به‌عنوان نمونه جدید به مجموعه نمونه‌های LoRAS افزوده می‌شود [13]. یک بردار آفین با وزن‌های تصادفی به‌صورت تعریف می‌گردد و نمونه جدید از طریق (2) به‌دست می‌آید

(2)

این الگوریتم تا زمانی که تعداد نمونه‌ها برای هر گروه نزدیک‌ترین همسایگی مطابق (3) به اندازه نرسد، اجرا می‌شود که تعداد نمونه‌های کلاس اقلیت و تعداد نمونه‌های کلاس اکثریت را نشان می‌دهد

(3)

در الگوریتم H-SMOTE، نمونه‌های اقلیت و اکثریت به‌عنوان ورودی به الگوریتم داده می‌شوند و خروجی الگوریتم، مجموعه داده‌ای از جنس کلاس اقلیت است که نمونه تکراری در آن وجود ندارد. مطابق شکل 3، در ابتدا برای به‌دست‌آوردن نمونه مرکزی در کلاس اقلیت، میانگین نمونه‌های کلاس اقلیت (نقاط آبی) محاسبه می‌شود. سپس در سطح اول برای هر نمونه از کلاس اقلیت مطابق (4) با محاسبه فاصله منهتن، نمونه جدید میان نمونه مرکزی و نمونه تولید می‌شود و در کلاس اقلیت قرار می‌گیرد (نقاط قرمز) [12]

(4)

[1] این مقاله در تاریخ 19 اسفند ماه 1401 دریافت و در تاریخ 9 مرداد ماه 1402 بازنگری شد.

پرستو محقق، دانشکده مهندسی برق و کامپیوتر، دانشگاه سیستان و بلوچستان، زاهدان، ایران، (email: P.mohaghegh@pgs.usb.ac.ir).

سمیرا نوفرستی (نویسنده مسئول)، دانشکده مهندسی برق و کامپیوتر، دانشگاه سیستان و بلوچستان، زاهدان، ایران، (email: snoferesti@ece.usb.ac.ir).

مهری رجائی، دانشکده مهندسی برق و کامپیوتر، دانشگاه سیستان و بلوچستان، زاهدان، ایران، (email: rajayi@ece.usb.ac.ir).

[2] . Human Genome

[3] . Classification

[4] . Minority Class

[5] . Majority Class

[6] . Instance Selection

[7] . Data Augmentation

[8] . Cost-Sensitive Functions

[9] . Meta-Learning

[10] . Transfer Learning

[11] . Learning Automata

[12] . Cluster-Based Instance Selection

[13] . Synthetic Minority Over Sampling Technique

[14] . Localized Random Affine Shadow Sampling

شکل 4: روندنمای الگوریتم انتخاب نمونه.

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

(5)

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

همان طور که گفته شد، داده‌افزایی تنها بر روی کلاس اقلیت انجام می‌شود و حاصل آن کلاس اقلیت گسترش‌یافته است. از آنجا که هر دو روش LoRAS و H-SMOTE سعی دارند تعداد نمونه‌های کلاس اقلیت را به تعداد نمونه‌های کلاس اکثریت برساند، با اعمال توأم هر دو روش به تعادل نسبی در تعداد نمونه‌های کلاس‌های اقلیت و اکثریت نمی‌رسیم؛ بلکه تعداد نمونه‌های کلاس اقلیت گسترش‌یافته بیشتر از تعداد نمونه‌های کلاس اکثریت می‌شود. برای حل این مشکل، پس از داده‌افزایی با دو روش LoRAS و H-SMOTE، مجموعه داده خروجی آنها ترکیب شده (که آن را می‌نامیم) و برای مرحله دوم (انتخاب نمونه) به‌کار گرفته می‌شود. مجموعه شامل کلیه رکوردهای و بوده که فراوانی برچسب کلاس بیشتر است. به همین دلیل برای رسیدن به تعادل در اندازه کلاس‌ها در مرحله دوم سعی می‌شود با انتخاب زیرمجموعه‌ای از رکوردهای کلاس در مجموعه که برای طبقه‌بندی مؤثرتر هستند و حذف رکوردهای نویز و زائد، در تعداد نمونه‌های دو کلاس اقلیت و اکثریت تعادل نسبی برقرار شود.

3-2 مرحله دوم: انتخاب نمونه

انتخاب نمونه یکی از مراحل پیش‌پردازش داده است که به دنبال انتخاب زیرمجموعه‌ای باکیفیت از کل داده‌های موجود با حذف رکوردهای نویز و زائد با هدف بهبود دقت الگوریتم‌های طبقه‌بند‌ی است. در این مقاله برای انتخاب نمونه از اتوماتای یادگیر استفاده شده است. اتوماتای یادگیر مدلی است که به‌طور تصادفی یک عمل را از مجموعه متناهی از اعمال انتخاب و در محیط اِعمال می‌کند. سپس محیط عمل انتخاب‌شده توسط اتوماتای یادگیر را ارزیابی می‌نماید و نتیجه ارزیابی خود را توسط یک سیگنال تقویتی به اتوماتای یادگیر اطلاع می‌دهد. اتوماتای یادگیر با دریافت این سیگنال تقویتی، وضعیت خود را به‌روز کرده و عمل بعدی خود را انتخاب می‌کند [19].

هدف استفاده از اتوماتای یادگیر، انتخاب زیرمجموعه‌ای باکیفیت از رکوردهای کلاس اقلیت گسترش‌یافته است. در واقع با حذف رکوردهای نویز و زائد از کلاس (که فراوانی بیشتری در مقایسه با کلاس دارد)، به دنبال ایجاد تعادل نسبی در اندازه کلاس اقلیت و اکثریت هستیم. در شکل 4 روندنمای الگوریتم انتخاب نمونه آمده است.

فرایند کار بدین صورت است که به هر نمونه (رکورد) در کلاس از مجموعه داده ترکیبی حاصل از مرحله اول، یک اتوماتای یادگیر تعلق می‌گیرد. هر اتوماتای بر اساس احتمال که متناظر با عمل انتخاب نمونه در تکرار ام است، یک عمل (انتخاب یا عدم انتخاب نمونه متناظر) را برمی‌گزیند. برای این منظور در تکرار ام، اتوماتای یادگیر که متعلق به نمونه در کلاس است، یک مقدار تصادفی را تولید می‌کند و اگر باشد، نمونه در مجموعه کاهش‌یافته قرار می‌گیرد که این مجموعه، حاصل الگوریتم در پایان تکرار ام است. در ابتدا هر نمونه از کلاس ، احتمالی یکسان (برابر 5/0) برای انتخاب یا عدم انتخاب جهت افزوده‌شدن به مجموعه کاهش‌یافته دارد.

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

(6)

(7)

که و دو مقدار ثابت هستند که به ترتیب پارامتر پاداش و جریمه نامیده می‌شوند. در این مقاله با سعی و خطا مقادیر این دو پارامتر 08/0 و 005/0 در نظر گرفته شده است. تا زمانی که شرط توقف (رسیدن به حداکثر تکرارها) اجرایی شود، فرایند فوق ادامه خواهد داشت. در پایان الگوریتم، بهترین راه حل حاصل به‌عنوان مجموعه کاهش‌یافته نهایی برگردانده می‌شود (شکل 4). حال خروجی الگوریتم انتخاب نمونه که مجموعه داده‌ای نسبتاً متوازن است به طبقه‌بند داده می‌شود و معیارهای مد نظر بر روی مجموعه داده تست محاسبه می‌گردند.

4- نتایج

در این بخش به ارزیابی کارایی روش پیشنهادی برای متعادل‌سازی مجموعه داده‌های نامتوازن پرداخته می‌شود. در ابتدا ابزار، مجموعه داده‌های نامتوازن مورد استفاده و تنظیمات پیاده‌سازی معرفی می‌گردد و سپس نتایج آزمایش‌های انجام‌گرفته ارائه می‌شود.

4-1 مجموعه‌ داده‌های مورد استفاده، ابزار و تنظیمات پیاده‌سازی

جهت پیاده‌سازی روش پیشنهادی برای متعادل‌سازی مجموعه داده‌های نامتوازن از ابزار Jupyter notebook [20] استفاده شده است. نرم‌افزار Jupyter notebook تحت زبان اجرا می‌شود.

مجموعه داده‌های نامتوازن، یک مورد خاص برای مسئله طبقه‌بندی هستند که توزیع نمونه‌ها در آنها در بین کلاس‌ها یکنواخت نیست. این مجموعه‌ها معمولاً دو کلاس اکثریت (negative) و اقلیت (positive) دارند. روش پیشنهادی بر روی 8 مجموعه داده نامتوازن انتخاب‌شده از مخزن داده KEEL² ارزیابی شده است. در این مقاله از مجموعه‌ داده‌های دودویی 6Glass، 3Ecoli، ، 4Yeast، 3Yeast، 6Yeast، 19Abalone و 0Page-blocks استفاده گردیده که در دسته‌های متفاوتی از نسبت عدم توازن ³ قرار دارند؛ از مجموعه‌ داده‌های نامتوازن با کم تا بسیار بالا. نسبت عدم توازن طبق (8) محاسبه می‌گردد

(8)

که تعداد نمونه‌های کلاس اقلیت و تعداد نمونه‌های کلاس اکثریت را نشان می‌دهد. هرچه نسبت عدم توازن به 1 نزدیک‌تر باشد، آن مجموعه داده‌ای متعادل‌تر است. در جدول 1 خلاصه‌ای از مشخصات مجموعه داده‌‌های مذکور آورده شده است.

طبق جدول 2 در روش LoRAS به در صورتی که باشد، به‌صورت پیش‌فرض مقدار 30 داده می‌شود و در غیر این صورت مقدار 5 می‌گیرد. اندازه برابر تعداد ویژگی‌هاست. مقادیر پارامترهای روش LoRAS بر اساس [13] انتخاب شده است.

4-2 ارزیابی روش پیشنهادی برای متعادل‌سازی مجموعه داده‌های نامتوازن

روش پیشنهادی با الگوریتم‌های H-SMOTE [12] و LoRAS [13] مقایسه شده است. در دو الگوریتم مذکور تنها به افزایش تعداد نمونه‌های کلاس اقلیت پرداخته شده و همچنان عدم توازن زیادی در مجموعه‌ داده‌های حاصل مشهود است. در روش پیشنهادی با انجام انتخاب نمونه بر روی ترکیب مجموعه‌‌ داده‌های حاصل از دو الگوریتم، نسبت عدم توازن به‌طور قابل توجهی کاهش می‌یابد و توازن نسبی حاصل می‌گردد.

در شکل 5، نسبت عدم توازن دو کلاس اقلیت و اکثریت برای روش پیشنهادی (با به‌کارگیری طبقه‌بندهای KNN و SVM) و دو الگوریتم داده‌افزایی مذکور آمده است. همان طور که مشاهده می‌شود، نسبت عدم توازن در روش پیشنهادی با هر دو طبقه‌بند نسبت به دو روش دیگر به 1 نزدیک‌تر است. به‌عنوان مثال نسبت عدم توازن در مجموعه داده حاصل

[1] . Accuracy

[2] . https://sci2s.ugr.es/keel/datasets.php

[3] . Imbalance Rate

شکل 5: نسبت عدم توازن (IR) مجموعه داده‌‍‌ها در روش پیشنهادی، H-SMOTE و LoRAS.

جدول 1: مشخصات مجموعه‌ داده‌های نامتوازن.

شناسه	مجموعه داده	تعداد نمونه‌ها	تعداد ویژگی‌ها	IR
مجموعه‌های داده‌ای با IR پایین (5/1 تا 9)
1D	6Glass	214	9	38/6
2D	3Yeast	1484	8	1/8
3D	0Page-blocks	5472	10	79/8
4D	3Ecoli	336	7	6/8
مجموعه‌های داده‌ای با IR بالا (بیشتر از 9)
5D	4Yeast	1484	8	41/28
6D	6Yeast	1484	8	4/41
7D		281	7	14/39
8D	19Abalone	4174	8	44/129

جدول 2: تنظیمات پارامترهای روش LoRAS.

مجموعه داده	تعداد نمونه‌های اقلیت	k
6Glass	29	5	9
3Yeast	163	30	8
0Page-blocks	559	30	10
3Ecoli	35	5	7
4Yeast	51	5	8
6Yeast	35	5	8
	7	5	7
19Abalone	32	5	8

از روش پیشنهادی با طبقه‌بند KNN برای مجموعه داده نامتوازن 4Yeast به شناسه 5D به میزان 12/0 با مقدار استاندارد توازن فاصله دارد؛ در حالی که در روش H-SMOTE حدود 51/0 با میزان توازن استاندارد فاصله دارد.

برای ارزیابی کارایی روش پیشنهادی برای مجموعه داده‌های نامتوازن، معیار صحت متعادل¹ طبقه‌بندهای KNN و SVM برای 8 مجموعه داده‌ای نامتوازن ارزیابی گردیده است. صحت متعادل یکی از معیارهای شناخته‌شده در طبقه‌بندی مجموعه داده‌های نامتوازن است که بر اساس ماتریس درهم‌ریختگی² (شکل 6) و مطابق (9) محاسبه می‌شود

(9)

اگر مجموعه داده کاملاً متعادل باشد- یعنی کلاس‌ها تقریباً یک اندازه باشند- صحت و صحت متعادل تمایل دارند به یک مقدار همگرا شوند. در واقع، تفاوت اصلی بین صحت متعادل و صحت، زمانی ظاهر می‌شود که مجموعه اولیه داده‌ها توزیع نامتعادلی را برای کلاس‌ها نشان دهد [21].

مطابق با جدول 3، صحت متعادل به‌دست‌آمده از دو طبقه‌بند KNN
و SVM در روش پیشنهادی نسبت به سایر روش‌ها بهبود قابل ملاحظه‌ای داشته است. در این میان صحت متعادل به‌دست‌آمده از روش H-SMOTE برای مجموعه داده 0Page-blocks با اختلاف اندکی (حدود 0048/0 برای KNN و 0115/0 برای SVM) نسبت به روش پیشنهادی بیشتر است؛ اما همچنان صحت متعادل روش پیشنهادی نسبت به روش LoRAS برای مجموعه داده 0Page-blocks در هر دو طبقه‌بند بیشتر است.

یکی دیگر از معیارهای سنجش کارایی طبقه‌بندی مجموعه داده‌های نامتوازن، ویژگی است. معیار ویژگی به میزان توانایی یک طبقه‌بند برای یافتن نمونه‌های مثبت اشاره دارد. طبق (10) برای به‌دست‌آوردن معیار ویژگی باید نسبت موارد منفی حقیقی را به مجموع موارد منفی حقیقی و مثبت کاذب حساب کرد

(10)

شکل 6: ماتریس درهم‌ریختگی.

در جدول 4، نتایج ارزیابی طبقه‌بندهای KNN و SVM برای مجموعه داده‌های نامتوازن بر اساس معیار ویژگی آمده است. بر اساس معیار ویژگی در اکثر مجموعه‌ داده‌ها روش پیشنهادی به نتیجه بهتری نسبت به سایر روش‌ها دست یافته است. در مجموعه داده‌ای 0Page-blocks، معیار ویژگی روش H-SMOTE با اختلافی حدود 0098/0 برای KNN و 0124/0 برای SVM نتیجه بهتری را داشته است؛ اما همان طور که ملاحظه می‌شود معیار ویژگی روش پیشنهادی برای این مجموعه نسبت به روش LoRAS بیشتر است. در مجموعه داده‌ای 4Yeast معیار ویژگی در روش LoRAS با طبقه‌بند SVM با اختلاف 0335/0 نسبت به روش پیشنهادی بیشتر می‌باشد و در مجموعه داده‌ای 19Abalone با طبقه‌بند KNN روش H-SMOTE و با طبقه‌بند SVM روش LoRAS عملکرد بهتری داشته است.

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

(11)

معیار بر اساس معیارهای دقت و فراخوانی محاسبه می‌شود؛ بنابراین به‌طور خلاصه به مفهوم معیارهای دقت و فراخوانی می‌پردازیم. معیار دقت برای یک طبقه‌بند با توجه به یک کلاس خاص، نسبت تعداد نمونه‌های به‌درستی پیش‌بینی‌شده به تعداد کل نمونه‌های آن کلاس است. فراخوانی برای یک کلاس خاص، نسبت نمونه‌هایی است که به‌درستی پیش‌بینی شده‌اند به تعداد کل نمونه‌هایی که واقعاً متعلق به کلاس هستند. معیارهای دقت و فراخوانی به‌ترتیب بر اساس (12) و (13) تعریف می‌شوند

(12)

(13)

معیار نیز میانگین هارمونیک دقت و فراخوانی است که مطابق (14) اندازه‌گیری می‌شود

(14)

منحنی (ROC) معیاری برای ارزیابی مسائل طبقه‌بندی دودویی است. ROC یک منحنی احتمال است که را در برابر ³ در آستانه‌های متفاوت ترسیم می‌کند. منحنی ROC را می‌توان با استفاده از مساحت زیر منحنی برای تشخیص میزان توانایی طبقه‌بند برای تمایز بین کلاس‌ها خلاصه کرد. هرچه میزان بالاتر باشد، عملکرد طبقه‌بند در تشخیص کلاس‌های اقلیت و اکثریت بهتر است. برای هر مجموعه داده، بالاترین مقدار صحت، و به‌دست‌آمده از هر طبقه‌بند در جداول 5 و 6 مشخص شده است.

همان طور که ذکر گردید جدول 5 نتایج ارزیابی معیارهای صحت، و از طبقه‌بند KNN را بر روی 8 مجموعه داده‌ای نشان می‌دهد. با توجه به نتایج ارائه‌شده از معیار صحت، روش پیشنهادی بر روی 5 مجموعه داده‌ای از 8 مجموعه داده عملکرد بهتری نسبت به سایر روش‌ها داشته و در سه مجموعه داده 0Page-blocks، 4Yeast و 19Abalone به‌ترتیب با اختلاف اندک 0052/0، 0025/0 و 0003/0، H-SMOTE معیار صحت بهتری داشته است.

مطابق با نتایج به‌دست‌آمده از معیار ، روش پیشنهادی در اکثر مجموعه داده‌ها بهتر عمل کرده است و فقط در مجموعه داده‌ای
0Page-blocks روش H-SMOTE با اختلاف 0005/0 کارایی بیشتری داشته است. به همین ترتیب نتایج روش پیشنهادی بر اساس معیار در اکثر مجموعه داده‌ها حکایت از عملکرد بهتر دارد؛ به غیر از مجموعه داده 0Page-blocks که با اختلاف 0048/0 روش H-SMOTE از نتیجه بهتری برخوردار بوده است.

مطابق با جدول 6 با توجه به نتایج ارائه‌شده از طبقه‌بند SVM، روش پیشنهادی بر اساس معیار صحت در 5 مجموعه داده از 8 مجموعه نتیجه بهتری را نشان می‌دهد؛ به‌جز سه مجموعه داده 0Page-blocks، 4Yeast و 19Abalone که با روش H-SMOTE صحت بالاتری داشتند. معیار روش پیشنهادی در اکثر مجموعه داده‌ها بالاتر است؛ به غیر از 0Page-blocks و 19Abalone که به ترتیب روش H-SMOTE و روش LoRAS نتیجه بهتری داشته است. بر اساس معیار نیز روش پیشنهادی در 7 مجموعه داده نتایج بهتری کسب کرده است؛ به‌جز در مجموعه داده 0Page-blocks که روش H-SMOTE کارایی بیشتری داشته است.

در آزمایش دیگر برای ارزیابی اثربخشی اتوماتای یادگیر در انتخاب نمونه، روش مبتنی بر اتوماتای یادگیر با روش حذف تصادفی مقایسه شده است. در روش حذف تصادفی، پس از مرحله داده‌افزایی با H-SMOTE و LoRAS برای ایجاد تعادل در اندازه کلاس اقلیت و اکثریت، نمونه‌های کلاس به‌صورت کاملاً تصادفی حذف می‌شوند. در جداول 7 و 8 کارایی اتوماتای یادگیر و روش حذف تصادفی برای دو طبقه‌بند KNN و SVM مقایسه شده است. همان طور که مشاهده می‌گردد روش مبتنی بر اتوماتای یادگیر در تمامی مجموعه داده‌ها و برای هر دو طبقه‌بند KNN و SVM از صحت، و بالاتری برخوردار است. دلیل این امر، به‌کارگیری اتوماتای یادگیر برای شناسایی و حذف نمونه‌هایی است که تأثیر کمتری در طبقه‌بندی دارند. به بیانی دیگر، حذف تصادفی نمونه‌ها ممکن است منجر به حذف نمونه‌های اصلی و مؤثر در طبقه‌بندی و به تبع آن، کاهش کارایی طبقه‌بندی شود.

به‌طور خلاصه نتایج آزمایش‌های انجام‌گرفته نشان می‌دهند که روش پیشنهادی برای متعادل‌سازی مجموعه داده‌های نامتوازن در هر دو طبقه‌بند KNN و SVM در اکثر مجموعه‌ داده‌های نامتوازن مورد مطالعه، عملکرد بهتری را در مقایسه با روش‌های H-SMOTE و LoRAS دارد. بر اساس نتایج به‌دست‌آمده برای روش پیشنهادی می‌توان اظهار کرد که برای طبقه‌بندی نمونه‌های مجموعه داده‌های نامتوازن به هر دو کلاس اقلیت و اکثریت، اهمیت یکسان داده می‌شود.

[1] . Balanced Accuracy

[2] . Confusion Matrix

[3] . False Positive Rate

جدول 3: نتایج ارزیابی طبقه‌بندهای KNN و SVM بر اساس معیار صحت متعادل.

مجموعه داده	H-SMOTE		LoRAS		روش پیشنهادی
مجموعه داده	SVM	KNN	SVM	KNN	SVM	KNN
6Glass	9775/0	9600/0	9627/0	9442/0	9897/0	9807/0
3Yeast	9481/0	9786/0	9585/0	9767/0	9689/0	9841/0
0Page-blocks	9780/0	9799/0	9452/0	9521/0	9665/0	9751/0
3Ecoli	9156/0	9482/0	9168/0	9624/0	9551/0	9778/0
4Yeast	9199/0	9562/0	8937/0	9449/0	9373/0	9625/0
6Yeast	9514/0	9785/0	9490/0	9739/0	9726/0	9871/0
	9712/0	9885/0	9106/0	9634/0	9885/0	9935/0
19Abalone	9020/0	9922/0	9090/0	9775/0	9170/0	9925/0

جدول 4: نتایج ارزیابی طبقه‌بندهای KNN و SVM بر اساس معیار ویژگی.

مجموعه داده	H-SMOTE		LoRAS		روش پیشنهادی
مجموعه داده	SVM	KNN	SVM	KNN	SVM	KNN
6Glass	9677/0	9322/0	9843/0	9285/0	1	1
3Yeast	9018/0	9668/0	9371/0	9693/0	9401/0	9769/0
0Page-blocks	9701/0	9748/0	9395/0	9486/0	9577/0	9650/0
3Ecoli	8390/0	8965/0	8586/0	9247/0	9204/0	9655/0
4Yeast	8457/0	9195/0	9282/0	9228/0	8947/0	9312/0
6Yeast	9097/0	9594/0	9461/0	9571/0	9493/0	9766/0
	9625/0	9770/0	8837/0	9268/0	9770/0	1
19Abalone	8052/0	9912/0	8698/0	9718/0	8412/0	9884/0

جدول 5: نتایج ارزیابی طبقه‌بند KNN بر اساس معیارهای صحت، و .

مجموعه داده	H-SMOTE			LoRAS			روش پیشنهادی
مجموعه داده	صحت	F	AUC	صحت	F	AUC	صحت	F	AUC
6Glass	9645/0	9565/0	9600/0	9382/0	9541/0	9442/0	9816/0	9827/0	9807/0
3Yeast	9821/0	9742/0	9786/0	9742/0	9806/0	9767/0	9846/0	9832/0	9841/0
0Page-blocks	9815/0	9732/0	9799/0	9508/0	9663/0	9521/0	9763/0	9727/0	9751/0
3Ecoli	9583/0	9454/0	9482/0	9469/0	9608/0	9624/0	9788/0	9767/0	9778/0
4Yeast	9679/0	9512/0	9562/0	9360/0	9529/0	9449/0	9654/0	9607/0	9625/0
6Yeast	9853/0	9763/0	9785/0	9685/0	9757/0	9739/0	9872/0	9870/0	9871/0
	9888/0	9880/0	9885/0	9491/0	9629/0	9634/0	9937/0	9934/0	9935/0
19Abalone	9926/0	9905/0	9922/0	9755/0	9822/0	9775/0	9923/0	9926/0	9925/0

جدول 6: نتایج ارزیابی طبقه‌بند SVM بر اساس معیارهای صحت، و .

مجموعه داده	H-SMOTE			LoRAS			روش پیشنهادی
مجموعه داده	صحت	F	AUC	صحت	F	AUC	صحت	F	AUC
6Glass	9787/0	9756/0	9775/0	9753/0	9843/0	9627/0	9905/0	9913/0	9897/0
3Yeast	9625/0	9431/0	9481/0	9518/0	9623/0	9585/0	9729/0	9677/0	9689/0
0Page-blocks	9805/0	9718/0	9780/0	9395/0	9592/0	9452/0	9669/0	9649/0	9665/0
3Ecoli	9305/0	9068/0	9156/0	8939/0	9186/0	9168/0	9569/0	9529/0	9551/0
4Yeast	9445/0	9106/0	9199/0	9049/0	9265/0	8937/0	9423/0	9320/0	9373/0
6Yeast	9659/0	9456/0	9514/0	9480/0	9607/0	9490/0	9739/0	9718/0	9726/0
	9722/0	9664/0	9712/0	8983/0	9268/0	9106/0	9878/0	9863/0	9885/0
19Abalone	9329/0	8909/0	9020/0	8952/0	9181/0	9090/0	9184/0	9094/0	9170/0

5- نتیجه‌گیری

عدم توازن کلاس‌ها در مجموعه‌ داده‌ها باعث نادیده‌گرفته‌شدن کلاسی می‌شود که تعداد نمونه‌های کمتری دارد (کلاس اقلیت) و این در حالی است که در اغلب مسائل طبقه‌بندی‌ این کلاس از اهمیت بیشتری برخوردار است. جهت رفع این مشکل بایست به متعادل‌نمودن این گونه

جدول 7: مقایسه کارایی روش مبتنی بر اتوماتای یادگیر با روش حذف تصادفی برای طبقه‌بند KNN.

مجموعه داده	حذف تصادفی			اتوماتای یادگیر
مجموعه داده	صحت	F	AUC	صحت	F	AUC
6Glass	9487/0	9433/0	9482/0	9816/0	9827/0	9807/0
3Yeast	9733/0	9735/0	9735/0	9846/0	9832/0	9841/0
0Page-blocks	9692/0	9689/0	9692/0	9763/0	9727/0	9751/0
3Ecoli	9267/0	9156/0	9220/0	9788/0	9767/0	9778/0
4Yeast	9528/0	9430/0	9472/0	9654/0	9607/0	9625/0
6Yeast	9737/0	9723/0	9731/0	9872/0	9870/0	9871/0
	9696/0	9714/0	9722/0	9937/0	9934/0	9935/0
19Abalone	9902/0	9899/0	9901/0	9923/0	9926/0	9925/0

جدول 8: مقایسه کارایی روش مبتنی بر اتوماتای یادگیر با روش حذف تصادفی برای طبقه‌بند SVM.

مجموعه داده	حذف تصادفی			اتوماتای یادگیر
مجموعه داده	صحت	F	AUC	صحت	F	AUC
6Glass	9572/0	9523/0	9560/0	9905/0	9913/0	9897/0
3Yeast	9543/0	9538/0	9549/0	9729/0	9677/0	9689/0
0Page-blocks	9624/0	9627/0	9623/0	9669/0	9649/0	9665/0
3Ecoli	9109/0	8944/0	9044/0	9569/0	9529/0	9551/0
4Yeast	9293/0	9140/0	9225/0	9423/0	9320/0	9373/0
6Yeast	9543/0	9509/0	9531/0	9739/0	9718/0	9726/0
	9636/0	9655/0	9666/0	9878/0	9863/0	9885/0
19Abalone	9101/0	8990/0	9079/0	9184/0	9094/0	9170/0

مجموعه داده‌ها پرداخت.

در این مقاله مشکل عدم توازن این گونه مجموعه داده‌ها، بررسی و در این راستا، روشی جدید برای متعادل‌نمودن مجموعه داده‌های نامتوازن پیشنهاد گردید. در روش پیشنهادی، ابتدا نمونه‌های کلاس اقلیت در
هر مجموعه داده‌ای نامتوازن با دو روش H-SMOTE و LoRAS داده‌افزایی شدند و با توجه به اینکه نسبت عدم توازن مجموعه داده‌ها همچنان بالا بود، روشی ابتکاری برای رسیدن به تعادل نسبی ارائه گردید. در این روش پس از داده‌افزایی، عمل انتخاب نمونه بر روی نمونه‌های کلاس اقلیت پیاده می‌شود. در عمل انتخاب نمونه به هر نمونه از کلاس اقلیت، یک اتوماتای یادگیر جهت انتخاب‌شدن یا نشدن در مجموعه کاهش‌یافته نهایی نسبت داده می‌شود و طبق نتیجه صحت طبقه‌بندهای SVM و KNN به اتوماتای یادگیر پاداش یا جریمه داده می‌شود.

بر اساس نتایج آزمایش‌های انجام‌گرفته در روش پیشنهادی نسبت به روش‌های H-SMOTE و LoRAS، مجموعه‌ داده‌ها از نسبت عدم توازن مناسب‌تری برخوردار هستند. همچنین در مجموع، روش پیشنهادی بر اساس معیارهای رایج طبقه‌بندی مجموعه داده‌های نامتوازن یعنی صحت متعادل و ویژگی در مقایسه با دو روش مذکور عملکرد بهتری داشته است.

مراجع

[1] H. Kim, H. Cho, and D. Ryu, "Corporate bankruptcy prediction using machine learning methodologies with a focus on sequential data," Computational Economics, vol. 59, pp. 1231-1249, 2022.

[2] D. Yousif Mikhail, F. Al-Mukhtar, and S. Wahab Kareem, "A comparative evaluation of cancer classification via TP53 gene mutations using machine learning," Asian Pacific J. of Cancer Prevention, vol. 23, no. 7, pp. 2459-2467, Jul. 2022.

[3] L. Yang and Y. Jiachen, "Few-shot cotton pest recognition and terminal," Computers and Electronics in Agriculture, vol. 169, Article ID: 105240, 2020.

[4] P. Kumar, R. Bhatnagar, K. Gaur, and A. Bhatnagar, "Classification of imbalanced data: review of methods and applications," IOP Conf. Series: Materials Science and Engineering, vol. 1099, no 1, Article ID: 012077, 2021.

[5] C. F. Tsai, W. C. Lin, Y. H. Hu, and G. T. Yao, "Under-sampling class imbalanced datasets by combining clustering analysis and instance selection," Information Sciences, vol. 477, pp. 47-54, Mar. 2019.

[6] I. Czarnowski and P. Jedrzejowicz, "An approach to imbalanced data classification based on instance selection and over-sampling," in Proc. 11th Int. Conf.on Computational Collective Intelligence, pp. 601-610, Hendaye, France, 4-6 Sept. 2019.

[7] D. Gan, J. Shen, B. An, M. Xu, and N. Liu, "Integrating TANBN with cost sensitive classification algorithm for imbalanced data in medical diagnosis," Computers & Industrial Engineering, vol. 140, Article ID: 106266, Feb. 2020.

[8] L. Yang and Y. Jiachen, "Meta-learning baselines and database for few-shot classification in agriculture," Computers and Electronics in Agriculture, vol. 182, Article ID: 106055, Mar. 2021.

[9] Z. Peng, Z. Li, J. Zhang, Y. Li, G. J. Qi, and J. Tang, "Few-shot image recognition with knowledge transfer," in Proc. of the IEEE/CVF Int. Conf. on Computer Vision, pp. 441-449, Seoul, South Korea, 27 Oct.-2 Nov. 2019.

[10] F. Jimenez, G. Sanchez, J. Palma, and G. Sciavicco, "Three-objective constrained evolutionary instance selection for classification: wrapper and filter approaches," Engineering Applications of Artificial Intelligence, vol. 107, Article ID: 104531, Jan. 2022.

[11] G. E. Melo-Acosta, F. Duitama-Muñoz, and J. D. Arias-Londoño, An Instance Selection Algorithm for Big Data in High Imbalanced Datasets Based on LSH, arXiv: 2210.04310, Oct. 2022.

[12] X. Chao and L. Zhang, "Few-shot imbalanced classification based on data augmentation," Multimedia Systems, vol. 29, no. 5, pp. 2843-2851, 2023.

[13] S. Bej, N. Davtyan, M. Wolfien, M. Nassar, and O. Wolkenhauer, "LoRas: an oversampling approach for imbalanced datasets," Machine Learning, vol. 110, pp. 279-301, 2021.

[14] J. C. Requelme, J. S. Aguilar-Ruiz, and M. Toro, "Finding representative patterns with ordered projections," Pattern Recognition, vol. 36, no. 4, pp. 1009-1018, Apr. 2003.

[15] D. R. Wilson and T. R. Martinez, "Instance pruning techniques," in Proc. of the 14th Int. Conf. on Machine Learning, pp. 400-411, 8-12 Jul. 1997.

[16] M. Moran, T. Cohen, Y. Ben-Zion, and G. Gordon, "Curious instance selection," Information Sciences, vol. 608, pp. 794-808, Aug. 2022.

[17] N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, "SMOTE: synthetic minority over-sampling technique," J. of Artificial Intelligence Research, vol. 16, pp. 321-357, Jan. 2002.

[18] ش. سرگلزایی، ف. حسین‌زاده سلجوقی و ﻫ. آقایاری، "ارائه روشی نوین برای رتبه‌بندی اعداد فازی با استفاده از مرکز محیطی دایره و کاربرد آن در ارزیابی عملکرد مدیریت زنجیره تأمین،" نشریه تصمیم‌گیری و تحقیق در عملیات، دوره 3، شماره 3، صص. 236-248، پاییز 1397.

[19] S. N. Kumpati and A. T. Mandayam, Learning Automata: An Introduction, Courier Corporation, 2012.

[20] J. C. Dominguz, et al., "Teaching chemical engeering using Jupyter notebook: problem generators and lecturing tools," Education for Chemical Engineers, vol. 37, pp. 1-10, Oct. 2021.

[21] M. Grandini, E. Bagli, and G. Visani, Multi-Class Classification: An Overview, arXiv:2008.05756, Aug. 2020.

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

سميرا نوفرستي تحصيلات خود را در مقاطع كارشناسي و كارشناسي ارشد مهندسي كامپيوتر به‌ترتيب در سال‌هاي 1382 و 1384 از دانشگاه صنعتي شريف و دانشگاه صنعتي اميركبير و در مقطع دكتري مهندسي كامپيوتر در سال 1394 از دانشگاه شهيد بهشتي به پايان رساند و هم‌اكنون استاديار دانشكده مهندسي برق و كامپيوتر دانشگاه سيستان و بلوچستان است. زمينه‌هاي تحقيقاتي اصلي مورد علاقه ايشان عبارتند از هوش مصنوعي، پردازش زبان طبيعي، متن‌كاوي و تحلیل احساسات.

مهري رجائي در سال 1382 مدرك كارشناسي مهندسي كامپيوتر خود را از دانشگاه صنعتي شريف و در سال 1384 مدرك كارشناسي ارشد مهندسي كامپيوتر خود را از دانشگاه صنعتي اميركبير دريافت نمود. در سال 1394 موفق به اخذ درجه دكترا در رشته مهندسي كامپيوتر از دانشگاه علم و صنعت شد. وي از سال 1384 در دانشكده مهندسي برق و كامپيوتر دانشگاه سيستان و بلوچستان مشغول به فعاليت گرديد و اينك نيز عضو هيأت علمي اين دانشكده است. زمينه‌هاي علمي مورد علاقه نام‌برده شامل شبكه‌هاي اجتماعي، حفظ حريم خصوصي در انتشار شبكه‌هاي اجتماعي، پايگاه داده و محاسبات نرم است.

Share To

Article Url

Combination of Instance Selection and Data Augmentation Techniques for Imbalanced Data Classification

Rimag

Links

Related Centers

Technical Support

Official pages