• Home
  • Introducing Intelligent Mutation Method Based on PSO Algorithm to Solve the Feature Selection Problem

Share To

Article Url


Manuscript ID : 1400071531706 Visit : 4217 Page: 185 - 195

20.1001.1.16823745.1401.20.3.4.2

Article Type: Original Research

Introducing Intelligent Mutation Method Based on PSO Algorithm to Solve the Feature Selection Problem

Subject Areas : electrical and computer engineering

Mahmoud Parandeh 1 , Mina Zolfy Lighvan 2 * , jafar tanha 3

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

Received: 2021-10-12 Accepted : 2022-06-11 Published : 2022-11-02

Keywords: Feature selection, multi-objective optimization, PSO algorithm, adaptive weight sum method, intelligent mutation, elitism,

Abstract :

Today, with the increase in data production volume, attention to machine learning algorithms to extract knowledge from raw data has increased. Raw data usually has redundant or irrelevant features that affect the performance of learning algorithms. Feature selection algorithms are used to improve efficiency and reduce the computational cost of machine learning algorithms. A variety of methods for selecting features are provided. Among the feature selection methods are evolutionary algorithms that have been considered because of their global optimization power. Many evolutionary algorithms have been proposed to solve the feature selection problem, most of which have focused on the target space. The problem space can also provide vital information for solving the feature selection problem. Since evolutionary algorithms suffer from the pain of not leaving the local optimal point, it is necessary to provide an effective mechanism for leaving the local optimal point. This paper uses the PSO evolutionary algorithm with a multi-objective function. In the proposed algorithm, a new mutation method that uses the particle feature score is proposed along with elitism to exit the local optimal points. The proposed algorithm is tested on different datasets and examined with existing algorithms. The simulation results show that the proposed method has an error reduction of 20%, 11%, 85%, and 7% in the Isolet, Musk, Madelon, and Arrhythmia datasets, respectively, compared to the new RFPSOFS method.

References:

[1] B. Xue, M. Zhang, W. N. Browne, and X. Yao, "A survey on evolutionary computation approaches to feature selection," IEEE Trans. on Evolutionary Computation, vol. 20, no. 4, pp. 606-626, Aug. 2015.
[2] J. Miao and L. Niu, "A survey on feature selection," Procedia Computer Science, vol. 91, pp. 919-926, 2016.
[3] I. Guyon and A. Elisseeff, "An introduction to variable and feature selection," J. of Machine Learning Research, vol. 3, , pp. 1157-1182, 2003.
[4] R. Kohavi and G. H. John, "Wrappers for feature subset selection," Artificial Intelligence, vol. 97, no. 1-2, pp. 273-324, Dec. 1997.
[5] G. Chandrashekar and F. Sahin, "A survey on feature selection methods," Computers & Electrical Engineering, vol. 40, no. 1, pp. 16-28, Jan. 2014.
[6] S. S. Darshan and C. Jaidhar, "Performance evaluation of filter-based feature selection techniques in classifying portable executable files," Procedia Computer Science, vol. 125, pp. 346-356, 2018.
[7] S. Karasu, A. Altan, S. Bekiros, and W. Ahmad, "A new forecasting model with wrapper-based feature selection approach using multi-objective optimization technique for chaotic crude oil time series," Energy, vol. 212, Article ID: 118750, 2020.
[8] H. Liu, M. Zhou, and Q. Liu, "An embedded feature selection method for imbalanced data classification," IEEE/CAA J. of Automatica Sinica, vol. 6, no. 3, pp. 703-715, May 2019.
[9] R. Vijayanand, D. Devaraj, and B. Kannapiran, "Intrusion detection system for wireless mesh network using multiple support vector machine classifiers with genetic-algorithm-based feature selection," Computers & Security, vol. 77, pp. 304-314, Aug. 2018.
[10] M. Amoozegar and B. Minaei-Bidgoli, "Optimizing multi-objective PSO based feature selection method using a feature elitism mechanism," Expert Systems with Applications, vol. 113, pp. 499-514, 15 Dec. 2018.
[11] A. Lin, W. Sun, H. Yu, G. Wu, and H. Tang, "Global genetic learning particle swarm optimization with diversity enhancement by ring topology," Swarm and Evolutionary Computation, vol. 44, pp. 571-583, Feb. 2019.
[12] R. Tanabe and H. Ishibuchi, "An easy-to-use real-world multi-objective optimization problem suite," Applied Soft Computing, vol. 89, Article ID: 106078, Apr. 2020.
[13] R. Eberhart and J. Kennedy, "A new optimizer using particle swarm theory," in. Proc. 6th IEEE Int. Symp. on Micro Machine and Human Science, MHS'95, pp. 39-43, Nagoya, Japan, 4-6 Oct. 1995.
[14] N. Jain, U. Nangia, and J. Jain, "A review of particle swarm optimization," J. of the Institution of Engineers India: Series B, vol. 99, no. 4, pp. 407-411, 2018.
[15] N. Gunantara, "A review of multi-objective optimization: methods and its applications," Cogent Engineering, vol. 5, no. 1, Article ID: 1502242, 2018.
[16] T. C. Bora, V. C. Mariani, and L. dos Santos Coelho, "Multi-objective optimization of the environmental-economic dispatch with reinforcement learning based on non-dominated sorting genetic algorithm," Applied Thermal Engineering, vol. 146, pp. 688-700, Jan. 2019.
[17] R. Zhang, F. Nie, X. Li, and X. Wei, "Feature selection with multi-view data: a survey," Information Fusion, vol. 50, pp. 158-167, Oct. 2019.
[18] B. Venkatesh and J. Anuradha, "A review of feature selection and its methods," Cybernetics and Information Technologies, vol. 19, no. 1, pp. 3-26, Mar. 2019.
[19] P. Pudil, J. Novovičová, and J. Kittler, "Floating search methods in feature selection," Pattern Recognition Letters, vol. 15, no. 11, pp. 1119-1125, Nov. 1994.
[20] B. Xue, M. Zhang, and W. N. Browne, "Particle swarm optimization for feature selection in classification: a multi-objective approach," IEEE Trans. on Cybernetics, vol. 43, no. 6, pp. 1656-1671, Dec. 2012.
[21] Y. Zhang, D. W. Gong, and J. Cheng, "Multi-objective particle swarm optimization approach for cost-based feature selection in classification," IEEE/ACM Trans. on Computational Biology and Bioinformatics, vol. 14, no. 1, pp. 64-75, Jan.-Feb. 2015.
[22] H. B. Nguyen, B. Xue, I. Liu, P. Andreae, and M. Zhang, "New mechanism for archive maintenance in PSO-based multi-objective feature selection," Soft Computing, vol. 20, no. 10, pp. 3927-3946, 2016.
[23] M. L. Zhang and Z. H. Zhou, "ML-KNN: a lazy learning approach to multi-label learning," Pattern Recognition, vol. 40, no. 7, pp. 2038-2048, Jul. 2007.
[24] S. Gu, R. Cheng, and Y. Jin, "Feature selection for high-dimensional classification using a competitive swarm optimizer," Soft Computing, vol. 22, no. 3, pp. 811-822, 2018.
[25] T. M. Hamdani, J. M. Won, A. M. Alimi, and F. Karray, "Multi-objective feature selection with NSGA II," in Proc. Int. Conf. on Adaptive and Natural Computing Algorithms, pp. 240-247, Warsaw, Poland, . 2007.
[26] L. Cagnina, S. C. Esquivel, and C. C. Coello, "A particle swarm optimizer for multi-objective optimization," J. of Computer Science and Technology, vol. 5, no. 4, pp. 204-210, 11-14. 2005.
Full-Text:
معرفي يک روش جديد خوشه‌يابي خودکار

نشریه مهندسی برق و مهندسی كامپیوتر ایران، ب- مهندسی کامپیوتر، سال 20، شماره 3، پاییز 1401  185

مقاله پژوهشی

ارائه روش جهش هوشمند مبتنی بر الگوریتم PSO 
برای حل مسئله انتخاب ویژگی

محمود پرنده، مینا زلفی لیقوان و جعفر تنها

 

 

1 

چكیده: امروزه با افزایش حجم تولید داده، توجه به الگوریتم‌های یادگیری ماشین جهت استخراج دانش از داده‌های خام افزایش یافته است. داده خام معمولاً دارای ویژگی‌های اضافی یا تکراری است که بر روی عملکرد الگوریتم‌های یادگیری تأثیر می‌گذارد. جهت افزایش کارایی و کاهش هزینه محاسباتی الگوریتم‌های یادگیری ماشین، از الگوریتم‌های انتخاب ویژگی استفاده می‌شود 
که روش‌های متنوعی برای انتخاب ویژگی ارائه شده است. از جمله روش‌های انتخاب ویژگی، الگوریتم‌های تکاملی هستند که به دلیل قدرت بهینه‌سازی سراسری خود مورد توجه قرار گرفته‌اند. الگوریتم‌های تکاملی بسیاری برای حل مسئله انتخاب ویژگی ارائه شده که بیشتر آنها روی فضای هدف تمرکز داشته‌اند. فضای مسئله نیز می‌تواند اطلاعات مهمی برای حل مسئله انتخاب ویژگی ارائه دهد. از آنجایی که الگوریتم‌های تکاملی از مشکل عدم خروج از نقطه بهینه محلی رنج می‌برند، ارائه یک مکانیزم مؤثر برای خروج از نقطه بهینه محلی ضروری است. در این مقاله از الگوریتم تکاملی PSO با تابع چندهدفه برای انتخاب ویژگی استفاده شده که در آن یک روش جدید جهش که از امتیاز ویژگی‌های ذرات استفاده می‌کند، به همراه نخبه‌گرایی برای خروج از نقاط بهینه محلی 
ارائه گردیده است. الگوریتم ارائه‌شده بر روی مجموعه داده‌های مختلف تست و با الگوریتم‌های موجود بررسی شده است. نتایج شبیه‌سازی‌ها نشان می‌دهند 
که روش پیشنهادی در مقایسه با روش جدید RFPSOFS بهبود خطای 20%، 11%، 85% و 7% به ترتیب در دیتاست‌های Isolet، Musk، Madelon و Arrhythmia دارد.

 

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

1-       مقدمه

امروزه با پیشرفت تکنولوژی، حجم تولید داده افزایش یافته است. بیشتر داده‌های تولیدشده دارای ابعاد بسیاری هستند که این مشکل با نام "نفرین ابعاد2" شناخته می‌شود [1]. از آنجایی که برای تبدیل داده به دانش از الگوریتم‌های یادگیری ماشین استفاده می‌شود، هرچه ابعاد داده کمتر باشد، باعث افزایش کارایی و کاهش هزینه محاسباتی الگوریتم یادگیری می‌شود. برای کاهش ابعاد داده از الگوریتم‌های انتخاب ویژگی استفاده می‌گردد. هدف الگوریتم‌های انتخاب ویژگی، حذف ویژگی‌های تکراری یا اضافی است. منظور از ویژگی‌های تکراری، ویژگی‌هایی است که در سایر ویژگی‌های داده اثر خود را نمایان ساخته‌اند و منظور از ویژگی‌های اضافی، ویژگی‌هایی هستند که در دقت الگوریتم یادگیری ماشین هیچ تأثیری ندارند [2]. انتخاب ویژگی معمولاً باعث بهبود دقت الگوریتم یادگیری شده و منجر به ساخت مدلی ساده‌تر می‌گردد.

یکی از جنبه‌های مهم الگوریتم‌های انتخاب ویژگی، استفاده از معیارهای ارزیابی است که کیفیت ویژگی‌های انتخاب‌شده را بررسی نماید. به صورت کلی، 3 نوع روش انتخاب ویژگی وجود دارد که شامل روش Filter [3]، روش Wrapper [4] و روش Embedded [5] است. در روش‌های مبتنی بر Filter از معیارهای از پیش تعریف شده که مستقل از فاز یادگیری هستند، استفاده می‌شود. به همین دلیل هیچ تضمینی وجود ندارد که ویژگی‌های انتخاب‌شده در بهبود الگوریتم یادگیری تأثیرگذار باشند. با این که روش‌های مبتنی بر Filter کم‌هزینه هستند، اما در آنها به دلیل عدم استفاده از الگوریتم‌های یادگیری، احتمال انتخاب ویژگی‌های نامرتبط با کلاس داده افزایش می‌یابد [6]. روش‌های مبتنی بر Wrapper از روش‌های مبتنی بر Filter عملکرد بهتری دارند، اما از لحاظ محاسباتی پیچیده‌تر هستند. در این روش‌ها از الگوریتم‌های یادگیری متنوعی برای ارزیابی ویژگی‌های انتخاب‌شده استفاده می‌شود [7]. سومین گروه از روش‌های انتخاب ویژگی، روش‌های مبتنی بر Embedded هستند که 
در آنها از ترکیب روش‌های مبتنی بر Filter و Wrapper استفاده شده است [8].

اخیراً روش‌های الگوریتم‌های تکاملی مبتنی بر Wrapper مانند الگوریتم‌های ژنتیک [9] و 3PSO [10] در انتخاب ویژگی به دلیل قدرت بهینه‌سازی سراسری خود مورد توجه قرار گرفته‌اند. در این روش‌ها هیچ اطلاعاتی از فضای مسئله مورد نیاز نیست و به صورت فرااکتشافی4 اقدام به حل مسئله می‌کنند. این روش‌ها به دو دسته تک‌هدفه یا چندهدفه تقسیم می‌شوند. از آنجایی که مسئله انتخاب ویژگی یک مسئله چندهدفه است، از الگوریتم‌های چندهدفه برای حل مسئله انتخاب ویژگی استفاده می‌شود که یکی از اهداف، کاهش تعداد ویژگی و هدف دیگر افزایش دقت الگوریتم یادگیری است [11].

در این مقاله، از روش‌های مبتنی بر Wrapper به کمک الگوریتم PSO استفاده شده و همان طور که پیشتر اشاره شد، مسئله انتخاب ویژگی یک مسئله چندهدفه است. برای حل این گونه مسائل دو روش وجود دارد: 1) روش‌های فشرده‌سازی که در آن توابع هدف با هم ترکیب شده و یک تابع هدف جدید تولید می‌کنند و 2) روش‌ Pareto Front است که در آن هدف، یافتن یک مجموعه از جواب‌هایی است که دیگر جواب‌ها نتوانند 
بر آن غلبه کنند [12]. در این مقاله از روش مجموع وزن‌دار تطبیق‌پذیر5 برای حل مسئله چندهدفه استفاده شده است. در این روش، در گام‌های ابتدایی، وزن دقت الگوریتم بیشتر است و سپس با افزایش گام‌های اجرای الگوریتم، وزن تعداد ویژگی‌ها افزایش یافته تا الگوریتم بتواند در کنار دقت بالا، ویژگی‌های کمتری را انتخاب کند. در انتهای گام‌های اجرای الگوریتم، مجدد وزن دقت الگوریتم افزایش یافته تا خطای الگوریتم کاهش یابد. همچنین از مکانیزم آرشیو6 برای نگهداری بهترین جواب‌های یافت‌شده تا کنون استفاده می‌گردد که برای رتبه‌دهی ویژگی‌ها کاربرد دارد. علاوه بر این از یک روش جهش جدید به همراه نخبه‌گرایی با استفاده از رتبه‌های ویژگی در روش پیشنهادی استفاده شده است. نو‌آوری روش پیشنهادی به شرح زیر است:

•        استفاده از روش مجموع وزن‌دار تطبیق‌پذیر

•        استفاده از روش جهش هوشمند به همراه نخبه‌گرایی برای خروج از نقاط بهینه محلی

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

2-       پیشینه و کارهای مرتبط

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

2-1 الگوریتم PSO

PSO مبتنی بر روش‌های فرااکتشافی است که حرکت دسته‌ای از پرندگان را شبیه‌سازی می‌کند [13]. هر ذره7 در این دسته8 نشان‌دهنده یک جواب است که در فضای چندبعدی حرکت می‌کند و از بهترین موقعیت خود و همچنین بهترین موقعیت کل دسته برای بهبود موقعیت خود استفاده می‌نماید. عملکرد هر ذره بر اساس تابع برازش از پیش تعریف شده محاسبه می‌گردد.

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

img0        (1)

img0        (2)

که در آن img0 شماره تکرار، img0 شماره ذره، img0 بعد ذره و img0 ضریب اینرسی است که سرعت ذره را کنترل می‌کند و هرچه مقدار آن بیشتر باشد، سرعت ذره افزایش یافته و از بهینه محلی خارج می‌شود. مقادیر img0 و img0 برای کنترل این است که ذره به سمت بهینه محلی خود یا به سمت بهینه سراسری حرکت کند. مقادیر img0 و img0 نیز اعداد تصادفی با توزیع نرمال بین 0 و 1 هستند. الگوریتم PSO دارای نسخه‌های مختلفی است که پایه آنها مشابه یکدیگر است [14].

2-2 بهینه‌سازی چندهدفه

بسیاری از مسائل وجود دارند که دارای چند هدف برای بهینه‌سازی هستند. این اهداف معمولاً در تضاد با یکدیگرند و به همین دلیل بهینه‌سازی چندهدفه برای حل این گونه مسائل ارائه شده است [15]. از آنجایی که این اهداف با هم در یک راستا نیستند، بایستی از روش‌های فشرده‌سازی یا Pareto Front استفاده نمود که در ادامه به توضیح این دو روش می‌پردازیم.

2-2-1 روش فشرده‌سازی

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

img0        (3)

که در آن img0 و img0 وزن‌های اهداف بوده که مجموع آنها برابر یک است.

2-2-2 روش Pareto Front

در این روش جواب‌هایی انتخاب می‌شوند که سایر جواب‌ها نتوانند بر آن غلبه کنند. فرض کنید مسئله دارای دو هدف img0 و img0 بوده که در آن img0 در راستای بیشینه‌سازی و img0 در راستای کمینه‌سازی است. برای این که یک جواب در Pareto Front قرار بگیرد، باید 2 شرط زیر هم‌زمان در آن صادق باشد:

1)        جوابی غالب است که هر دو تابع هدف img0 و img0 در آن بهتر یا برابر جواب‌های دیگر باشد.

2)        جوابی غالب است که حتماً یکی از توابع img0 و img0 در آن بهتر از سایر جواب‌ها باشد.

و جواب‌هایی که شرایط بالا را داشته باشند در Pareto Front قرار می‌گیرند [16].

2-3 روش Wrapper

روش‌های مبتنی بر Wrapper برای ارزیابی ویژگی‌های انتخاب‌شده در الگوریتم‌های یادگیری ماشین استفاده می‌شوند. این روش‌ها دارای دو جزء الگوریتم یادگیری و استراتژی جستجو هستند. الگوریتم Wrapper دارای دو نوع استراتژی جستجو است که نوع اول آن انتخاب ترتیبی و نوع دوم آن الگوریتم‌های تکاملی هستند که بر اساس الگوریتم یادگیری استفاده‌شده، ویژگی‌های انتخاب‌شده ارزیابی می‌شوند [17].

2-3-1 روش انتخابی

روش‌های انتخابی9 3 نوع هستند: 1) روش انتخاب رو به جلو، 2) روش انتخاب رو به عقب و 3) روش انتخاب دوطرفه. در روش انتخاب 
رو به جلو، ویژگی‌ها اضافه می‌شوند تا تابع هدف بهینه شود. برعکس، 
در روش انتخاب رو به عقب، ویژگی‌ها حذف می‌شوند. در روش انتخاب دوطرفه، هر دو حالت افزودن/ حذف‌کردن ویژگی امکان‌پذیر است. این روش‌ها از مشکل "اثر تودرتو10" رنج می‌برند. در این اثر در روش رو به جلو، ویژگی‌ای که انتخاب نشده است، دیگر شانس انتخاب مجدد ندارد. همچنین در روش رو به عقب، ویژگی‌ای که انتخاب شده دیگر کنار گذاشته نمی‌شود [18]. برای رفع این مشکل دو روش 11SBFS و 12SFFS ارائه شده‌اند [19].

2-3-2 روش الگوریتم‌های تکاملی

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

2-4 کارهای مرتبط

الگوریتم‌های بسیاری مبتنی بر روش Wrapper و با استفاده از الگوریتم‌های تکاملی ارائه گردیده است که در این قسمت به بررسی برخی از این روش‌ها می‌پردازیم. دو الگوریتم 13CMDPSOFS [20] و 14HMDPSOFS [21] برای انتخاب ویژگی ارائه شده‌اند. در روش CMDPSOFS از عملگر جهش به صورت یکنواخت و غیر یکنواخت استفاده شده و از این دو روش جهت حفظ تنوع ذرات و بهبود توانایی جستجوی الگوریتم استفاده گردیده است. برای رسیدن به این هدف مجموعه ذرات را به 3 قسمت مساوی تقسیم کرده و اعمال جهش مربوط را بر روی 2 قسمت از آن اعمال می‌کند. در روش HMDPSOFS از یک جهش ترکیبی استفاده شده که در روش اول آن در هر تکرار، 10% از ذرات اجازه دارند که مقدار سرعت خود را با مقدار اولیه تنظیم نمایند. در روش دوم نیز از جهش پرشی15 استفاده شده که در آن ذرات با احتمال مشخص‌شده امکان جهش به صورت یکنواخت را دارند. این کار باعث افزایش قدرت جستجوی سراسری الگوریتم شده است. روش دیگر ISRPSO [22] نام دارد که در آن از تکنیک‌های جستجوی محلی برای بهبود آرشیو (که در آن بهترین جواب‌ها نگهداری می‌شوند) استفاده می‌شود. در تکنیک جستجوی محلی از 3 روش درج‌کردن16، مبادله‌کردن17 و حذف‌کردن18 برای بهبود آرشیو استفاده شده است. در روش درج‌کردن، ویژگی‌هایی که در آرشیو وجود دارند دارای اهمیت بالایی هستند. برای ساخت یک جواب دیگر، این ویژگی‌ها بر اساس دقت الگوریتم مرتب شده و از آنها برای ایجاد جواب جدید استفاده می‌گردد. در روش حذف، الگوریتم شروع به حذف ویژگی از جواب ایجادشده می‌کند و این کار را تا جایی ادامه می‌دهد که جواب ایجادشده، دقت الگوریتم را افزایش دهد. در روش مبادله، برخلاف دو روش قبل که اقدام به حذف و اضافه‌کردن می‌کرد، اقدام به مبادله ویژگی‌ها در جواب ایجادشده با ویژگی‌های دارای رتبه بالا در آرشیو می‌شود. یکی دیگر از روش‌های جدید برای انتخاب ویژگی 19RFPSOFS [10] نام دارد که در آن از آرشیو برای ذخیره‌کردن بهترین جواب‌ها استفاده شده و امتیاز هر ویژگی بر اساس تکرار آن ویژگی در آرشیو محاسبه می‌گردد. در این روش نیز ذرات به 3 دسته تقسیم شده و بر روی دو دسته از آنها عملگر جهش به دو صورت یکنواخت و غیر یکنواخت اعمال می‌شود.

در ادامه به توضیح روش پیشنهادی می‌پردازیم.

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

همان طور که بحث شد، انتخاب ویژگی یک مسئله چندهدفه است 
که در آن هدف، کاهش تعداد ویژگی‌های انتخاب‌شده و نیز افزایش دقت الگوریتم یادگیری است. در روش پیشنهادی با نام 20AWMOPSOFS از فشرده‌سازی برای تبدیل تابع چندهدفه به تک‌هدفه استفاده شده است. همچنین به دلیل سادگی و هزینه محاسباتی پایین الگوریتم PSO، این الگوریتم به عنوان الگوریتم تکاملی مبتنی بر Wrapper انتخاب شده است. در روش پیشنهادی نیز از آرشیو به عنوان فضایی جهت ذخیره‌سازی بهترین جواب‌هایی که تا کنون الگوریتم یافته است، استفاده شده است. امتیازدهی به ویژگی‌های موجود در آرشیو نیز از فرایندهای مهم در روش پیشنهادی است. در ادامه، گام‌های روش پیشنهادی به صورت کلی در شکل‌های 1 و 2 آمده و نو‌آوری‌های روش پیشنهادی در بخش‌های 3-6 تا 3-8 به تفصیل توضیح داده شده است.

3-1 کدگذاری ذرات

در روش پیشنهادی، ذرات که نمایانگر ویژگی‌های مسئله هستند به صورت (4) کدگذاری شده‌اند

img0        (4)

که در آن img0 ذره در تکرار img0 و img0 ویژگی img0ام ذره img0ام که مقدار آن بین صفر و یک است، می‌باشد و img0 تعداد ویژگی‌های مسئله است. از آنجایی که در مسئله انتخاب ویژگی نیاز به کدگذاری به صورت صفر و یک داریم، از یک مقدار آستانه با نام img0 برای این کار استفاده می‌کنیم. مقدار img0 با توجه به [10] برابر 6/0 در نظر گرفته شده است. بنابراین img0هایی که مقدارشان از img0 بزرگ‌تر باشد، برابر یک و در غیر این صورت برابر صفر در نظر گرفته خواهند شد. نسخه دودویی img0 در (5) آمده است

img0        (5)

که در آن img0 نسخه دودویی img0، img0 نشان‌دهنده انتخاب یا عدم انتخاب ویژگی img0ام ذره img0ام و img0 تعداد ویژگی‌های مسئله است.

 

تقسیم داده‌های مجموعه داده به آموزشی و تست و سپس اعمال گام‌های زیر بر روی داده‌های آموزشی:

گام 1: مقداردهی اولیه جمعیت بر اساس قسمت 3-1

گام 2: ارزیابی مقدار برازش جمعیت بر اساس روش مجموع وزن‌دار تطبیق‌پذیر

گام 3: به روز رسانی آرشیو بر اساس مقدار برازش جمعیت

گام 4: به روز رسانی جمعیت بر اساس (11) و (12)

گام 5: اعمال جهش هوشمند و به روز رسانی ذرات

گام 6: به روز رسانی آرشیو پس از اعمال جهش هوشمند

گام 7: محاسبه و به روز رسانی امتیاز هر ذره بر اساس آرشیو

گام 8: اعمال عملگر نخبه‌گرایی بر روی جمعیت آرشیو

گام 9: اگر الگوریتم به بیشینه مقدار تکرار رسیده بود، به گام 10 برو و در غیر این صورت به گام 4 برگرد.

گام 10: استخراج اعضای موجود در آرشیو به عنوان بهترین جواب‌های روش پیشنهادی

 

شکل 1:  گام‌های الگوریتم پیشنهادی.

 

3-2 ارزیابی برازش ذرات

همان طور که پیشتر اشاره شد، در روش‌های مبتنی بر Wrapper، الگوریتم یادگیری نیز در انتخاب ویژگی دخالت دارد. به همین دلیل برای ارزیابی ویژگی‌های انتخاب‌شده از الگوریتم یادگیری KNN [23] استفاده گردیده است. در این مقاله دو هدف تعداد ویژگی انتخاب‌شده و دقت الگوریتم به عنوان اهداف تابع برازش انتخاب شده‌اند که با هم در تضاد هستند. به همین دلیل به جای دقت الگوریتم از خطای الگوریتم استفاده می‌کنیم تا اهداف هر دو در یک راستا شوند. در (6) نحوه محاسبه خطای الگوریتم آمده است

img0        (6)

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

img0        (7)

که در آن img0 تعداد ویژگی‌های انتخاب‌شده و img0 تعداد کل ویژگی‌های مسئله است.

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

img0        (8)

که در آن img0 و img0 به ترتیب وزن‌های خطای الگوریتم و تعداد ویژگی‌های انتخاب‌شده هستند.

3-3 آرشیو

برای ذخیره‌کردن بهترین ذرات یافته‌شده در تکرارهای الگوریتم از مکانیزم آرشیو استفاده شده است. پس از هر تکرار، مقدار برازش هر ذره محاسبه می‌گردد و ذراتی که مقدار برازش آنها از بقیه ذرات بهتر باشد در آرشیو  ذخیره  می‌شوند.  از  آنجایی  که  اندازه  آرشیو  محدود  است،  در  صورتی 

img0 

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

 

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

3-4 امتیازدهی به ویژگی‌ها

هدف اصلی انتخاب ویژگی، یافتن بهترین ویژگی‌ها و حذف ویژگی‌های اضافی است. برای رسیدن به این هدف، ویژگی‌ها بر اساس تعداد مشاهده در آرشیو امتیازدهی می‌شوند. دلیل این امر آن است که آرشیو، بهترین جواب‌ها را نگه می‌دارد. معادله (9) نمایش‌دهنده نحوه محاسبه امتیاز ویژگی است

img0        (9)

که img0 یک بردار با img0 بعد و به صورت img0 است که در آن img0 مقدار امتیاز هر ویژگی می‌باشد. img0 نمایانگر آرشیو و img0 مقدار دودودیی ویژگی در تکرار img0 است که در (5) نشان داده شده بود. اگر ویژگی img0ام در هیچ یک از اعضای آرشیو انتخاب نشده باشد، مقدار آن برابر صفر خواهد بود و بیشینه مقدار امتیاز ویژگی‌ها برابر اندازه آرشیو است.

3-5 به روز رسانی موقعیت ذره

در مسئله انتخاب ویژگی، المان‌های ذرات همان ویژگی‌ها هستند که 
با تغییر مقادیر ویژگی ذرات حرکت می‌کنند. پس از به روز رسانی آرشیو، مجموعه ذرات دوبه‌دو با هم مقایسه می‌شوند. ذره‌ای که برازش بهتری داشت، به عنوان ذره برنده انتخاب شده و به گروه برنده‌ها تعلق می‌گیرد 
و ذره بازنده نیز به گروه بازنده‌ها اضافه می‌شود. ذراتی که در گروه برنده هستند، به طور مستقیم به تکرار بعدی منتقل می‌شوند و ذراتی که در گروه بازنده‌ها هستند به کمک (10) تا (12) [24] به روز رسانی می‌شوند

img0        (10)

img0        (11)

img0        (12)

 

Input: population, archive, features rank

Output: updated population

Begin

for img0 to img0, img0 is size of population do

     if generated uniform random less than img0 then

          for img0 to img0, img0 is total number of features do

               if img0 is less than img0 then

                   img0

               else

                   img0

end

 

شکل 3:  روش جهش هوشمند یکنواخت. (endهای اضافی حذف شد)

 

Input: population, archive, features rank

Output: updated population

Begin

for img0 to img0, img0 is size of population do

     if generated uniform random less than img0 then

          for img0 to img0, img0 is total number of features do

               if generated uniform random less than 0.5 then

                    if img0 is less than img0 and img0 less than img0 then

                        img0

                    else

                        img0

end

 

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

 

که در آن img0 میانگین ذرات موجود در گروه برنده در تکرار img0، img0، img0 و img0 اعداد تصادفی بین صفر و یک و img0 یک ضریب از پیش تعریف شده است. img0 موقعیت ذره برنده در تکرار img0، img0 موقعیت ذره بازنده و img0 نیز سرعت ذره بازنده در تکرار img0 در نظر گرفته شده است.

3-6 جهش هوشمند

در گام قبل ممکن است که ذرات پس از چندین تکرار در نقطه بهینه محلی گرفتار شوند و به همین دلیل نیاز به مکانیزمی است تا ذرات بتوانند از نقطه بهینه محلی خارج شوند. برای حل این مشکل مکانیزم جهش هوشمند ارائه گردیده است. در این روش، ابتدا جمعیت به سه دسته مساوی تقسیم می‌شود که دلیل این امر، حفظ جستجوی محلی در کنار جستجوی جهانی فضای حالت است. دسته اول بدون تغییر به نسل بعدی منتقل می‌شوند. در دسته دوم، یک عدد تصادفی تولید شده و اگر از یک مقدار پیش‌فرض img0 کمتر باشد، مقادیر ویژگی‌ها عوض می‌شوند. به این صورت که در آن اگر ویژگی انتخاب شده بود، به انتخاب‌نشده تغییر می‌کند و اگر انتخاب نشده بود، به انتخاب‌شده تغییر خواهد کرد. این عمل برای تمامی ویژگی‌های ذره انجام خواهد گردید. در دسته سوم نیز یک عدد تصادفی تولید می‌شود و اگر از مقدار پیش‌فرض img0 کمتر بود، این ذره برای جهش انتخاب شده و برای هر المان ذره یک عدد تصادفی دیگر تولید می‌شود. اگر این عدد تصادفی از 5/0 کمتر بود، بر روی آن المان هیچ گونه جهشی انجام نمی‌شود و در غیر این صورت، اگر عدد تصادفی تولیدشده بیشتر از 5/0 بود، بر روی آن المان در صورتی که امتیاز آن کمتر از مقدار پیش‌فرض img0 باشد، عمل جهش انجام می‌شود. شبه‌کد مربوط به دو روش جهش پیشنهادی در شکل‌های 3 و 4 آورده شده است.

 

 

Input: archive, features rank

Output: updated archive

Begin

    img0select img0 where img0 greater than img0,

    img0 is feature rank of img0th feature

    img0copy of img0, img0 is img0th feature of particle img0 in archive

     for img0 to size of archive do

     begin

         img0 where img0 greater than img0

         img0sum of img0 where img0 greater than img0

         img0select img0 of img0 randomly

          for img0 to size of img0 do

              img0

          for img0 to size of img0 do

              img0

          calculate fitness of img0

          if fitness of img0 is better than img0 then

              img0

     end

end

 

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

 

3-7 نخبه‌گرایی

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

img0        (13)

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

3-8 مجموع وزن‌دار تطبیق‌پذیر

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

جدول 1: توضیحات مجموعه داده.

 

نام 
مجموعه داده

تعداد ویژگی‌ها

تعداد داده‌ها

ویژگی نامشخص

تعداد کلاس

Isolet

617

7797

خیر

26

Musk

167

6598

خیر

2

Madelon

500

4400

نامشخص

2

Arrhythmia

279

425

بله

16

Cnae

857

1080

نامشخص

9

 

جدول 2: آزمایش یافتن مقدار بهینه img0.

 

مقدار img0

بهترین جواب 1

بهترین جواب 2

بهترین جواب 3

خطا

تعداد 

ویژگی

خطا

تعداد 

ویژگی

خطا

تعداد 

ویژگی

10/0

34/0

7

36/0

6

37/0

5

15/0

33/0

10

35/0

6

34/0

7

20/0

35/0

6

35/0

12

37/0

4

25/0

31/0

6

30/0

8

33/0

6

30/0

39/0

9

29/0

9

31/0

8

35/0

29/0

5

30/0

5

30/0

5

40/0

32/0

5

33/0

6

33/0

6

45/0

30/0

5

30/0

5

30/0

7

50/0

31/0

5

31/0

5

31/0

6

 

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

4-       نتایج شبیه‌سازی

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

4-1 مجموعه داده

در این مقاله از مجموعه داده‌های عمومی UCI استفاده گردیده و خلاصه‌ای از ویژگی‌های این مجموعه داده‌ها در جدول 1 آمده است. در این جدول تعداد ویژگی‌ها، تعداد داده‌ها، آیا داده‌ای دارای ویژگی با مقدار نامشخص است یا نه و تعداد کلاس هر مجموعه داده آورده شده است.

4-2 پارامترها

همان طور که پیشتر اشاره شد، ذرات در الگوریتم تکاملی PSO به صورت پیوسته در نظر گرفته شده‌اند. بنابراین نیاز به فرایندی است تا نقاط پیوسته به گسسته تبدیل شوند و برای این کار از پارامتر img0 استفاده 
شده بود که مقدار آن برابر 6/0 است. از الگوریتم KNN با مقدار img0 برابر 5 به عنوان الگوریتم یادگیری استفاده شده است. برای انتخاب مقادیر img0 و img0 روی مجموعه داده Arrhythmia آزمایش‌هایی با 30 تکرار انجام شده که بهترین نتایج آن در جداول 2 و 3 آورده شده است.  با  توجه  به  این  آزمایش‌ها،  مقادیر img0 و img0 به  ترتیب 

جدول 3: آزمایش یافتن مقدار بهینه img0.

 

مقدار img0

بهترین جواب 1

بهترین جواب 2

بهترین جواب 3

خطا

تعداد 

ویژگی

خطا

تعداد 

ویژگی

خطا

تعداد 

ویژگی

10/0

30/0

8

30/0

8

33/0

7

15/0

31/0

6

32/0

6

33/0

5

20/0

34/0

8

34/0

6

38/0

5

25/0

33/0

6

33/0

6

32/0

8

30/0

33/0

7

33/0

7

32/0

8

35/0

33/0

5

33/0

5

32/0

6

40/0

32/0

6

32/0

6

33/0

7

45/0

31/0

8

31/0

8

30/0

9

50/0

33/0

5

32/0

8

33/0

5

 

جدول 4: مقداردهی پارامترهای الگوریتم پیشنهادی.

 

نام پارامتر

مقدار پارامتر

img0 

6/0

img0 

75/0

img0 

25/0

img0 

1/0

img0 

3/0

img0 

35/0

img0 

4/0

 

برابر 4/0 و 35/0 انتخاب شده و سایر پارامترهای الگوریتم پیشنهادی در جدول 4 آمده است.

در سایر روش‌های مبتنی بر PSO، سایز جمعیت برابر 30، بیشینه مقدار تکرار برابر 100، بیشینه مقدار سرعت یا همان img0 برابر 6/0، مقادیر img0 و img0 برابر 146/0، مقدار img0 برابر 729/0 و مقدار img0 برابر 6/0 در نظر گرفته شده است. پارامترهای مخصوص هر روش بر اساس گزارش‌های آنها تنظیم شده‌ و احتمال پرش در روش HMPSOFS برابر 01/0 است. در روش CMDPSOFS وزن اینرسی به صورت تصادفی بین 1/0 و 5/0، مقادیر img0 و img0 اعداد تصادفی بین 5/1 و 2 و همچنین نرخ جهش در این روش برابر img0 که در آن img0 تعداد ویژگی‌های مجموعه داده می‌باشد، در نظر گرفته شده است. برای NSGAII نیز پارامترها مشابه روش CMDPSOFS و نرخ برش برابر 9/0 است. لازم به ذکر است که در روش NSGAII کروموزوم‌ها به صورت یک آرایه img0بعدی هستند که اگر مقدار آن برابر یک باشد به معنی انتخاب ویژگی و اگر مقدار آن برابر صفر باشد، به معنی عدم انتخاب ویژگی است [25].

4-3 بررسی نتایج شبیه‌سازی

در روش پیشنهادی، از پنج مجموعه داده "Isolte"، "Musk"، "Madelon"، "Arrhythmia" و "Cnae" برای مقایسه استفاده گردیده و تمامی مجموعه داده‌های ذکرشده دارای بیش از 100 ویژگی هستند. روش AWMOPSOFS با پنچ روش که دو تای آنها روش‌های پایه NSGAII [25] و MOPSO [26] و سه تای آنها روش‌های مؤثر با نام‌های CMDPSOFS، HMPSOFS و RFPSOFS هستند، مقایسه شده است. در شکل‌های 6 تا 10 نتایج شبیه‌سازی آمده است. همان طور که در شکل‌ها مشخص است، روش پیشنهادی به دلیل استفاده از جهش هوشمند  و  نخبه‌گرایی  هوشمند  توانسته  که  تعداد  ویژگی  کمتری  با  در  نظر 

img0 

شکل 6:  نتایج شبیه‌سازی در مجموعه داده Musk.

 

img0 

شکل 7:  نتایج شبیه‌سازی در مجموعه داده Madelon.

 

img0 

شکل 8:  نتایج شبیه‌سازی در مجموعه داده Cnae.

 

گرفتن خطای الگوریتم انتخاب کند. با توجه به نتایج جدول 5، روش پیشنهادی در مقایسه با سایر روش‌ها تعداد ویژگی کمتری انتخاب کرده است. در مجموعه داده‌های "Musk" و "Madelon" روش پیشنهادی تعداد ویژگی کمتر قابل توجهی به نسبت سایر روش‌ها انتخاب کرده است. با در نظر گرفتن تعداد ویژگی‌های انتخاب‌شده، خطای الگوریتم نیز به نسبت سایر روش‌ها کمتر است. با این که در برخی مجموعه داده‌ها خطای سایر الگوریتم‌ها مانند NSGAII و CMDPSOFS در مجموعه داده "Musk" بهتر از روش پیشنهادی است، اما تعداد ویژگی‌های انتخاب‌شده در آنها بیشتر می‌باشد. در برخی مجموعه داده‌ها مانند "Madelon" بیشینه تعداد ویژگی انتخاب‌شده توسط روش پیشنهادی کمتر از کمینه تعداد ویژگی انتخاب‌شده در سایر روش‌ها است.

img0 

شکل 9:  نتایج شبیه‌سازی در مجموعه داده Isolte.

 

img0 

شکل 10:  نتایج شبیه‌سازی در مجموعه داده Arrhythmia.

 

در جدول 6 نیز بهترین تعداد ویژگی‌های انتخاب‌شده در 30 تکرار اجرای هر الگوریتم آمده است. نتایج به دست آمده به دلیل شرایط مختلف و تصادفی هر الگوریتم در شروع متفاوت است. با توجه به جدول 5، تعداد ویژگی‌های انتخاب‌شده توسط الگوریتم پیشنهادی در مجموعه داده "Cnae" بهتر از سایر روش‌ها در مجموعه داده‌های مختلف است.

در جدول 7 نیز شماره ویژگی‌های انتخاب‌شده در دو حالت بهترین تعداد ویژگی انتخاب‌شده و بهترین خطای الگوریتم آمده است.

در جداول 8 تا 13 نیز میانگین، انحراف معیار و واریانس خطا و تعداد ویژگی روش پیشنهادی در 30 بار تکرار آورده شده است.

همچنین زمان اجرای الگوریتم‌ها بر روی دو مجموعه داده Isolet و Madelon بررسی گردید و نتایج به ثانیه در جدول 14 آورده شده است.

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

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

[1] این مقاله در تاریخ 15 مهر ماه 1400 دریافت و در تاریخ 31 فروردین ماه 1401 بازنگری شد. 

محمود پرنده، دانشکده مهندسی برق و کامپیوتر، دانشگاه تبریز، تبریز، ایران، 
(email: parandeh@tabrizu.ac.ir).

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

جعفر تنها، دانشکده مهندسی برق و کامپیوتر، دانشگاه تبریز، تبریز، ایران، 
 (email: tanha@tabrizu.ac.ir).

 

[2] . Curse of Deminsionality

[3] . Particle Swarm Optimization

[4] . Meta-Heuristics

[5] . Adaptive Weighted Sum

[6] . Archive

[7] . Particle

[8] . Swarm

[9] . Selection

[10] . Nested Effects

[11] . Sequential Backward Floating Selection

[12] . Sequential Forward Floating Selection

[13] . Crowding Mutation Dominance PSO Feature Selection

[14] . Hybrid Mutation Dominance PSO Feature Selection

[15] . Jumping Mutation

[16] . Inserting

[17] . Swapping

[18] . Removing

[19] . Ranked Feature PSO Feature Selection

[20] . Adaptive Weight Multi Objective PSO Feature Selection

جدول 5: مقایسه تعداد ویژگی‌های انتخاب‌شده و خطای الگوریتم.

 

 

Isolet

Musk

Madelon

Arrhythmia

Cnae

AWMOPSOFS

خطا

23/0

07/0

238/0

396/0

39/0

تعداد ویژگی

24

3

5

6

68

NSGAII

خطا

22/0

07/0

503/0

414/0

237/0

تعداد ویژگی

175

26

142

54

288

CMDPSOFS

خطا

228/0

048/0

468/0

448/0

271/0

تعداد ویژگی

170

34

122

54

257

HMPSOFS

خطا

307/0

083/0

5016/0

433/0

425/0

تعداد ویژگی

76

9

31

13

116

MOPSO

خطا

269/0

064/0

501/0

426/0

240/0

تعداد ویژگی

131

21

103

50

215

RFPSOFS

خطا

277/0

078/0

4416/0

426/0

293/0

تعداد ویژگی

51

15

39

14

91

 

 

جدول 6: مقایسه تعداد ویژگی‌های انتخاب‌شده در روش‌های مختلف.

 

نام مجموعه داده

نام الگوریتم

تعداد ویژگی‌های انتخاب‌شده

Musk

AWMOPSOFS

7، 5، 4، 4، 3، 3، 3

NSGAII

45، 38، 36، 30، 28، 26

CMDPSOFS

49، 47، 46، 45، 34

HMPSOFS

35، 29، 25، 24، 22، 17، 13، 11، 9

MOPSO

38، 34، 29، 28، 21

RFPSOFS

23، 21، 19، 18، 15

Madelon

AWMOPSOFS

9، 8، 6، 5

NSGAII

160، 152، 148، 144، 142

CMDPSOFS

153، 126، 122

HMPSOFS

48، 33، 32، 31

MOPSO

115، 114، 110، 105، 103

RFPSOFS

47، 45، 41، 39

Cnae

AWMOPSOFS

119، 103، 98، 88، 68

NSGAII

308، 306، 297، 294، 288

CMDPSOFS

300، 287، 282، 268، 257

HMPSOFS

148، 144، 133، 131، 127، 119، 116

MOPSO

232، 231، 220، 217، 215

RFPSOFS

144، 114، 105، 93، 91

Isolet

AWMOPSOFS

۵۶، ۴۷، ۳۸، ۳۲، ۲۷، ۲۴

NSGAII

۲۰۴، ۲۰۰، ۱۸۹، ۱۷۹، ۱۷۸، ۱۷۵

CMDPSOFS

۱۸۸، ۱۸۲، ۱۷۴، ۱۷۰

HMPSOFS

۹۳، ۸۹، ۸۵، ۷۶

MOPSO

۱۵۶، ۱۵۳، ۱۵۱، ۱۳۸، ۱۳۱

RFPSOFS

۸۵، ۷۶، ۶۲، ۵۶، ۵۱

Arrhythmia

AWMOPSOFS

۱۲، ۱۰، ۹، ۶

NSGAII

۶۶، ۶۱، ۵۷، ۵۴

CMDPSOFS

۸۲، ۶۶، ۶۵، ۵۸، ۵۴

HMPSOFS

۲۶، ۲۶، ۲۳، ۱۹، ۱۳

MOPSO

۶۴، ۵۷، ۵۶، ۵۰

RFPSOFS

۲۳، ۲۰، ۱۷، ۱۵، ۱۴

 

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

روش پیشنهادی با تعدادی از بهترین روش‌های موجود مقایسه شد و نتایج شبیه‌سازی نشان داد که این روش در مقایسه با روش‌های پایه NSGAII و MOPSO و روش‌های مؤثر با نام‌های CMDPSOFS، HMPSOFS و RFPSOFS عملکرد بهتری دارد. نتایج شبیه‌سازی بر روی 5 مجموعه داده که هر کدام دارای بیش از 100 ویژگی بودند، اجرا گردید. الگوریتم AWMOPSOFS دارای خطای 048/0 و تعداد ویژگی انتخاب‌شده 7 در مجموعه داده Musk بود و در مقایسه با روش RFPSOFS که روش جدیدی است بهتر عمل کرد. سایر نتایج الگوریتم AWMOPSOFS برای مجموعه داده‌های Madelon، Cnae، Isolet و Arrhythmia به ترتیب دارای خطا و تعداد ویژگی 158/0 و 9، 174/0 و 119، 162/0 و 56 و 331/0 و 12 بود.

مراجع

[1]       B. Xue, M. Zhang, W. N. Browne, and X. Yao, "A survey on evolutionary computation approaches to feature selection," IEEE Trans. on Evolutionary Computation, vol. 20, no. 4, pp. 606-626, Aug. 2015.

[2]       J. Miao and L. Niu, "A survey on feature selection," Procedia Computer Science, vol. 91, pp. 919-926, 2016.

[3]       I. Guyon and A. Elisseeff, "An introduction to variable and feature selection," J. of Machine Learning Research, vol. 3, , pp. 1157-1182, 2003.

[4]       R. Kohavi and G. H. John, "Wrappers for feature subset selection," Artificial Intelligence, vol. 97, no. 1-2, pp. 273-324, Dec. 1997.

[5]       G. Chandrashekar and F. Sahin, "A survey on feature selection methods," Computers & Electrical Engineering, vol. 40, no. 1, pp. 16-28, Jan. 2014.

[6]       S. S. Darshan and C. Jaidhar, "Performance evaluation of filter-based feature selection techniques in classifying portable executable files," Procedia Computer Science, vol. 125, pp. 346-356, 2018.

[7]       S. Karasu, A. Altan, S. Bekiros, and W. Ahmad, "A new forecasting model with wrapper-based feature selection approach using multi-objective optimization technique for chaotic crude oil time series," Energy, vol. 212, Article ID: 118750, 2020.

[8]       H. Liu, M. Zhou, and Q. Liu, "An embedded feature selection method for imbalanced data classification," IEEE/CAA J. of Automatica Sinica, vol. 6, no. 3, pp. 703-715, May 2019.

[9]       R. Vijayanand, D. Devaraj, and B. Kannapiran, "Intrusion detection system for wireless mesh network using multiple support vector machine classifiers with genetic-algorithm-based feature selection," Computers & Security, vol. 77, pp. 304-314, Aug. 2018.

[10]       M. Amoozegar and B. Minaei-Bidgoli, "Optimizing multi-objective PSO based feature selection method using a feature elitism mechanism," Expert Systems with Applications, vol. 113, pp. 499-514, 15 Dec. 2018.

.

 

جدول 7: شماره ویژگی‌های انتخاب‌شده توسط AWMOPSOFS.

 

نام مجموعه داده

تعداد ویژگی انتخاب‌شده

شماره ویژگی‌های انتخاب‌شده

خطای الگوریتم

Musk 

(بهترین تعداد ویژگی)

3

۸، ۳۵، ۱۲۳

054/0

Musk 

(بهترین خطا)

77

۰، ۳، ۵، ۸، ۹۱، ۱۳۱، ۱۳۹

048/0

Madelon 

(بهترین تعداد ویژگی)

5

۰، ۱۵۳، ۳۱۸، ۳۷۸، ۴۷۵

209/0

Madelon 

(بهترین خطا)

6

۲، ۴۸، ۴۳۳، ۴۵۱، ۴۵۵، ۴۷۵

1335/0

Isolet 

(بهترین تعداد ویژگی)

24

۰، ۳، ۸، ۹، ۱۳، ۱۷، ۱۹، ۲۰، ۲۱، ۲۳، ۳۱، ۳۴، ۷۳، ۸۰، ۸۴، ۱۰۶، ۱۲۹، ۱۴۵، ۱۶۸، ۱۷۴، ۲۰۲، ۲۰۴، ۲۱۱، ۲۲۸، ۲۴۴، ۳۰۷، ۳۴۷، ۳۵۷، ۳۸۶، ۳۸۸، ۳۹۲، ۳۹۴، ۳۹۵، ۴۱۱، ۴۱۶، ۴۳۷، ۴۵۶، ۴۷۹، ۴۸۲، ۵۲۲، ۵۳۶، ۵۵۰، ۵۸۱، ۵۸۴

216/0

Isolet 

(بهترین خطا)

56

۰، ۳، ۴، ۵، ۶، ۸، ۱۰، ۱۳، ۱۵، ۱۶، ۲۰، ۲۱، ۲۳، ۲۴، ۲۷، ۲۸، ۲۹، ۳۴، ۳۸، ۳۹، ۴۱، ۴۲، ۴۳، ۴۴، ۴۵، ۴۶، ۴۹، ۵۲، ۵۸، ۷۱، ۸۵، ۱۰۰، ۱۰۳، ۱۰۷، ۱۰۹، ۱۱۴، ۱۳۱، ۱۶۶، ۱۷۶، ۱۸۸، ۱۹۶، ۲۰۳، ۳۵۷، ۳۶۳، ۳۹۳، ۴۱۱، ۴۱۷، ۴۲۶، ۴۵۲، ۴۸۸، ۴۹۵، ۵۰۰، ۵۰۹، ۵۱۵، ۵۶۶، ۵۸۰

163/0

Cnae 

(بهترین تعداد ویژگی)

56

۰، ۱، ۲، ۳، ۴، ۶، ۷، ۸، ۱۱، ۱۳، ۱۶، ۱۸، ۱۹، ۲۰، ۲۲، ۲۳، ۲۴، ۲۷، ۲۹، ۳۲، ۳۵، ۳۸، ۴۴، ۴۵، ۵۱، ۵۷، ۵۸، ۶۲، ۶۴، ۷۰، ۷۲، ۷۶، ۸۹، ۱۵۴، ۱۵۶، ۱۶۹، ۱۹۰، ۲۰۱، ۲۱۰، ۲۱۵، ۲۴۸، ۲۸۲، ۳۲۱، ۳۳۷، ۳۶۶، ۴۲۰، ۴۸۳، ۴۹۴، ۵۴۵، ۵۷۰، ۶۱۴، ۷۰۶، ۷۲۵، ۷۹۰، ۸۱۸، ۸۳۱

329/0

Cnae 

(بهترین خطا)

119

۰، ۴، ۵، ۶، ۸، ۹، ۱۰، ۱۱، ۱۲، ۱۴، ۱۵، ۲۱، ۲۲، ۲۴، ۲۵، ۲۶، ۲۷، ۲۸، ۲۹، ۳۰، ۳۱، ۳۲، ۳۳، ۳۴، ۳۶، ۳۷، ۳۸، ۴۱، ۴۳، ۴۴، ۴۵، ۴۸، ۵۰، ۵۳، ۵۶، ۵۸، ۶۶، ۶۸، ۶۹، ۷۱، ۷۲، ۷۶، ۷۸، ۸۴، ۸۵، ۸۸، ۹۹، ۱۰۴، ۱۰۷، ۱۰۸، ۱۲۳، ۱۳۸، ۱۴۱، ۱۵۶، ۱۷۴، ۱۸۹، ۱۹۰، ۱۹۸، ۲۰۱، ۲۱۰، ۲۳۸، ۲۴۰، ۲۴۵، ۲۵۶، ۲۸۵، ۳۰۹، ۳۱۸، ۳۳۲، ۳۵۲، ۳۵۵، ۳۶۴، ۳۷۱، ۳۷۲، ۳۷۸، ۴۱۴، ۴۲۰، ۴۳۱، ۴۴۱، ۴۴۲، ۴۸۶، ۴۸۸، ۵۱۵، ۵۱۷، ۵۱۸، ۵۲۱، ۵۴۵، ۵۵۸، ۵۸۲، ۵۹۲، ۵۹۴، ۶۰۶، ۶۱۸، ۶۳۰، ۶۴۴، ۶۸۴، ۶۸۵، ۷۲۵، ۷۳۲، ۷۳۶، ۷۸۲، ۷۹۷، ۸۰۷، ۸۳۷

174/0

Arrhythmia 

(بهترین تعداد ویژگی)

5

۴، ۸، ۹۰، ۱۱۱، ۲۷۶

3327/0

Arrhythmia 

(بهترین خطا)

6

۷، ۱۴، ۹۰، ۹۴، ۱۱۳، ۱۹۶

267/0

 

جدول 8: میانگین، انحراف معیار و واریانس خطا و تعداد ویژگی.

 

AWMOPSOFS

Isolet

Musk

Madelon

Arrhythmia

Cnae

میانگین

خطا

196/0

061/0

1937/0

3677/0

277/0

تعداد ویژگی

33/37

28/4

1/7

25/9

2/95

انحراف معیار

خطا

0250/0

007/0

0342/0

027/0

085/0

تعداد ویژگی

29/12

79/1

82/1

5/2

88/18

واریانس

خطا

0006/0

00005/0

0011/0

00077/0

0072/0

تعداد ویژگی

06/151

23/3

33/3

25/6

7/356

 

جدول 9: میانگین، انحراف معیار و واریانس خطا و تعداد ویژگی.

 

RFPSOFS

Isolet

Musk

Madelon

Arrhythmia

Cnae

میانگین

خطا

2264/0

060/0

404/0

3794/0

233/0

تعداد ویژگی

1/66

2/19

2/43

8/17

4/109

انحراف معیار

خطا

0316/0

0104/0

028/0

0384/0

0468/0

تعداد ویژگی

15/14

031/3

65/3

70/3

47/21

واریانس

خطا

0010/0

00011/0

00083/0

0014/0

0021/0

تعداد ویژگی

5/200

19/9

33/13

7/13

3/461

 

 

[11]       A. Lin, W. Sun, H. Yu, G. Wu, and H. Tang, "Global genetic learning particle swarm optimization with diversity enhancement by ring topology," Swarm and Evolutionary Computation, vol. 44, pp. 571-583, Feb. 2019.

[12]       R. Tanabe and H. Ishibuchi, "An easy-to-use real-world multi-objective optimization problem suite," Applied Soft Computing,
vol. 89, Article ID: 106078, Apr. 2020.

[13]       R. Eberhart and J. Kennedy, "A new optimizer using particle swarm theory," in. Proc. 6th IEEE Int. Symp. on Micro Machine and Human Science, MHS'95, pp. 39-43, Nagoya, Japan, 4-6 Oct. 1995.

[14]       N. Jain, U. Nangia, and J. Jain, "A review of particle swarm optimization," J. of the Institution of Engineers India: Series B, vol. 99, no. 4, pp. 407-411, 2018.

[15]       N. Gunantara, "A review of multi-objective optimization: methods and its applications," Cogent Engineering, vol. 5, no. 1, Article ID: 1502242, 2018.

[16]       T. C. Bora, V. C. Mariani, and L. dos Santos Coelho, "Multi-objective optimization of the environmental-economic dispatch with reinforcement learning based on non-dominated sorting genetic

جدول 10: میانگین، انحراف معیار و واریانس خطا و تعداد ویژگی.

 

CMDPSOFS

Isolet

Musk

Madelon

Arrhythmia

Cnae

میانگین

خطا

2094/0

0464/0

4349/0

3794/0

2327/0

تعداد ویژگی

5/178

2/44

33/130

1/65

8/278

انحراف معیار

خطا

01895/0

0025/0

0305/0

04971/0

04246/0

تعداد ویژگی

0622/8

89/5

31/16

72/10

713/12

واریانس

خطا

00035/0

000006/0

0009/0

00247/0

0018/0

تعداد ویژگی

1/65

7/34

33/266

2/115

62/161

 

جدول 11: میانگین، انحراف معیار و واریانس خطا و تعداد ویژگی.

 

HMPSOFS

Isolet

Musk

Madelon

Arrhythmia

Cnae

میانگین

خطا

2628/0

06372/0

475/0

41470/0

2729/0

تعداد ویژگی

75/85

55/20

2/36

4/21

14/131

انحراف معیار

خطا

04154/0

01862/0

0863/0

02118/0

07890/0

تعداد ویژگی

2743/7

7193/8

0415/8

5045/5

88/11

واریانس

خطا

001725/0

00034/0

0074/0

00044/0

00622/0

تعداد ویژگی

9166/52

027/76

66/64

3/30

142/141

 

جدول 12: میانگین، انحراف معیار و واریانس خطا و تعداد ویژگی.

 

MOPSO

Isolet

Musk

Madelon

Arrhythmia

Cnae

میانگین

خطا

210256/0

05770/0

4416/0

3658/0

1966/0

تعداد ویژگی

8/145

1/30

4/109

75/56

2/223

انحراف معیار

خطا

03900/0

006004/0

0400/0

05570/0

02759/0

تعداد ویژگی

7563/10

4420/6

3197/5

7373/5

9686/7

واریانس

خطا

001521/0

000036/0

0016/0

003103/0

00076/0

تعداد ویژگی

7/115

5/41

3/28

916/32

5/63

 

جدول 13: میانگین، انحراف معیار و واریانس خطا و تعداد ویژگی.

 

NSGAII

Isolet

Musk

Madelon

Arrhythmia

Cnae

میانگین

خطا

19444/0

05533/0

4434/0

3967/0

1901/0

تعداد ویژگی

5/187

83/33

2/149

5/59

6/298

انحراف معیار

خطا

01823/0

009628/0

0383/0

02066/0

03167/0

تعداد ویژگی

2433/12

1670/7

1554/7

19615/5

354/8

واریانس

خطا

00033/0

000092/0

0014/0

00042/0

0010/0

تعداد ویژگی

9/149

36/51

2/51

12/27

8/69

 

جدول 14: مقایسه زمان اجرای الگوریتم‌ها.

 

دیتاست

NSGAII

MOPSO

HMPSOFS

CMDPSOFS

RFPSOFS

AWMOPSOFS

Isolet

087/25

096/15

233/14

102/17

868/16

249/18

Madelon

788/30

927/16

829/15

382/18

837/17

106/19

 

 

algorithm," Applied Thermal Engineering, vol. 146, pp. 688-700, Jan. 2019.

[17]       R. Zhang, F. Nie, X. Li, and X. Wei, "Feature selection with multi-view data: a survey," Information Fusion, vol. 50, pp. 158-167, Oct. 2019.

[18]       B. Venkatesh and J. Anuradha, "A review of feature selection and its methods," Cybernetics and Information Technologies, vol. 19, no. 1, pp. 3-26, Mar. 2019.

[19]       P. Pudil, J. Novovičová, and J. Kittler, "Floating search methods in feature selection," Pattern Recognition Letters, vol. 15, no. 11, pp. 1119-1125, Nov. 1994.

[20]       B. Xue, M. Zhang, and W. N. Browne, "Particle swarm optimization for feature selection in classification: a multi-objective approach," IEEE Trans. on Cybernetics, vol. 43, no. 6, pp. 1656-1671, Dec. 2012.

[21]       Y. Zhang, D. W. Gong, and J. Cheng, "Multi-objective particle swarm optimization approach for cost-based feature selection in classification," IEEE/ACM Trans. on Computational Biology and Bioinformatics, vol. 14, no. 1, pp. 64-75, Jan.-Feb. 2015.

[22]       H. B. Nguyen, B. Xue, I. Liu, P. Andreae, and M. Zhang, "New mechanism for archive maintenance in PSO-based multi-objective feature selection," Soft Computing, vol. 20, no. 10, pp. 3927-3946, 2016.

[23]       M. L. Zhang and Z. H. Zhou, "ML-KNN: a lazy learning approach to multi-label learning," Pattern Recognition, vol. 40, no. 7, pp. 2038-2048, Jul. 2007.

[24]       S. Gu, R. Cheng, and Y. Jin, "Feature selection for high-dimensional classification using a competitive swarm optimizer," Soft Computing, vol. 22, no. 3, pp. 811-822, 2018.

[25]       T. M. Hamdani, J. M. Won, A. M. Alimi, and F. Karray, "Multi-objective feature selection with NSGA II," in Proc. Int. Conf. on Adaptive and Natural Computing Algorithms, pp. 240-247, Warsaw, Poland, . 2007.

[26]       L. Cagnina, S. C. Esquivel, and C. C. Coello, "A particle swarm optimizer for multi-objective optimization," J. of Computer Science and Technology, vol. 5, no. 4, pp. 204-210, 11-14. 2005.

 

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

 

 

مینا زلفی لقیوان تحصیلات خود را در مقطع کارشناسی در رشته مهندس کامپیوتر سخت افزار و کارشناسی ارشد در رشته مهندسی کامپیوتر سخت افزار گرایش معماری کارمپیوتر و دکترای تخصصی در رشته مهندسی الکترونیک گرایش الکترونیک دیجیتال  به ترتیب در سال‌های 1378 از دانشگاه تهران و 1381 از دانشگاه تهران و 1391 از دانشگاه تبریز به پایان رسانده است. هم اکنون به عنوان هیأت علمی در دانشگاه تبریز درحال فعالیت است.

 

جعفر تنها تحصیلات دکترای تخصصی خود در را در رشته هوش مصنوعی در سال 1392 از دانشگاه آمستردام هلند دریافت کرده است. ایشان هم اکنون به عنوان هیأت علمی در دانشگاه تبریز در حال فعالیت است. یکی از حوزه‌های تخصصی نام­برده در زمینه یادگیری ماشین نیمه­نظارتی است.

 

 

 

 


Related articles

The rights to this website are owned by the Raimag Press Management System.
Copyright © 2017-2024

Home| Login| About Rimag| Contact Us|
[فارسی] [العربية] [fa] [ar]