ارائه روش جهش هوشمند مبتنی بر الگوریتم PSO برای حل مسئله انتخاب ویژگی
محورهای موضوعی : مهندسی برق و کامپیوتر
محمود پرنده
1
(دانشگاه تبریز،دانشکده مهندسی برق و کامپیوتر)
مینا زلفی لیقوان
2
(دانشگاه تبریز،دانشکده مهندسی برق و کامپیوتر)
جعفر تنها
3
(دانشگاه تبریز،دانشکده مهندسی برق و کامپیوتر)
کلید واژه: انتخاب ویژگی, بهینهسازی چندهدفه, الگوریتم PSO, مجموع وزندار تطبیقپذیر, جهش هوشمند, نخبهگرایی,
چکیده مقاله :
امروزه با افزایش حجم تولید داده، توجه به الگوریتمهای یادگیری ماشین جهت استخراج دانش از دادههای خام افزایش یافته است. داده خام معمولاً دارای ویژگیهای اضافی یا تکراری است که بر روی عملکرد الگوریتمهای یادگیری تأثیر میگذارد. جهت افزایش کارایی و کاهش هزینه محاسباتی الگوریتمهای یادگیری ماشین، از الگوریتمهای انتخاب ویژگی استفاده میشود که روشهای متنوعی برای انتخاب ویژگی ارائه شده است. از جمله روشهای انتخاب ویژگی، الگوریتمهای تکاملی هستند که به دلیل قدرت بهینهسازی سراسری خود مورد توجه قرار گرفتهاند. الگوریتمهای تکاملی بسیاری برای حل مسئله انتخاب ویژگی ارائه شده که بیشتر آنها روی فضای هدف تمرکز داشتهاند. فضای مسئله نیز میتواند اطلاعات مهمی برای حل مسئله انتخاب ویژگی ارائه دهد. از آنجایی که الگوریتمهای تکاملی از مشکل عدم خروج از نقطه بهینه محلی رنج میبرند، ارائه یک مکانیزم مؤثر برای خروج از نقطه بهینه محلی ضروری است. در این مقاله از الگوریتم تکاملی PSO با تابع چندهدفه برای انتخاب ویژگی استفاده شده که در آن یک روش جدید جهش که از امتیاز ویژگیهای ذرات استفاده میکند، به همراه نخبهگرایی برای خروج از نقاط بهینه محلی ارائه گردیده است. الگوریتم ارائهشده بر روی مجموعه دادههای مختلف تست و با الگوریتمهای موجود بررسی شده است. نتایج شبیهسازیها نشان میدهند که روش پیشنهادی در مقایسه با روش جدید RFPSOFS بهبود خطای 20%، 11%، 85% و 7% به ترتیب در دیتاستهای Isolet، Musk، Madelon و Arrhythmia دارد.
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.
[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.
نشریه مهندسی برق و مهندسی كامپیوتر ایران، ب- مهندسی کامپیوتر، سال 20، شماره 3، پاییز 1401 185
مقاله پژوهشی
ارائه روش جهش هوشمند مبتنی بر الگوریتم PSO
برای حل مسئله انتخاب ویژگی
محمود پرنده، مینا زلفی لیقوان و جعفر تنها
چكیده: امروزه با افزایش حجم تولید داده، توجه به الگوریتمهای یادگیری ماشین جهت استخراج دانش از دادههای خام افزایش یافته است. داده خام معمولاً دارای ویژگیهای اضافی یا تکراری است که بر روی عملکرد الگوریتمهای یادگیری تأثیر میگذارد. جهت افزایش کارایی و کاهش هزینه محاسباتی الگوریتمهای یادگیری ماشین، از الگوریتمهای انتخاب ویژگی استفاده میشود
که روشهای متنوعی برای انتخاب ویژگی ارائه شده است. از جمله روشهای انتخاب ویژگی، الگوریتمهای تکاملی هستند که به دلیل قدرت بهینهسازی سراسری خود مورد توجه قرار گرفتهاند. الگوریتمهای تکاملی بسیاری برای حل مسئله انتخاب ویژگی ارائه شده که بیشتر آنها روی فضای هدف تمرکز داشتهاند. فضای مسئله نیز میتواند اطلاعات مهمی برای حل مسئله انتخاب ویژگی ارائه دهد. از آنجایی که الگوریتمهای تکاملی از مشکل عدم خروج از نقطه بهینه محلی رنج میبرند، ارائه یک مکانیزم مؤثر برای خروج از نقطه بهینه محلی ضروری است. در این مقاله از الگوریتم تکاملی 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 نشاندهنده یک جواب است که در فضای چندبعدی حرکت میکند و از بهترین موقعیت خود و همچنین بهترین موقعیت کل دسته برای بهبود موقعیت خود استفاده مینماید. عملکرد هر ذره بر اساس تابع برازش از پیش تعریف شده محاسبه میگردد.
فرضاً فضای ما دارای بعد است و تعداد
ذره در دسته وجود دارد. هر ذره یک موقعیت به صورت
و یک سرعت به صورت
دارد که
است. در الگوریتم PSO هر ذره در راستای بهترین موقعیت خود که به صورت
و بهترین موقعیت دسته که به صورت
است، حرکت میکند. سرعت و مکان جدید هر ذره مطابق با روابط زیر محاسبه میشوند
(1)
(2)
که در آن شماره تکرار،
شماره ذره،
بعد ذره و
ضریب اینرسی است که سرعت ذره را کنترل میکند و هرچه مقدار آن بیشتر باشد، سرعت ذره افزایش یافته و از بهینه محلی خارج میشود. مقادیر
و
برای کنترل این است که ذره به سمت بهینه محلی خود یا به سمت بهینه سراسری حرکت کند. مقادیر
و
نیز اعداد تصادفی با توزیع نرمال بین 0 و 1 هستند. الگوریتم PSO دارای نسخههای مختلفی است که پایه آنها مشابه یکدیگر است [14].
2-2 بهینهسازی چندهدفه
بسیاری از مسائل وجود دارند که دارای چند هدف برای بهینهسازی هستند. این اهداف معمولاً در تضاد با یکدیگرند و به همین دلیل بهینهسازی چندهدفه برای حل این گونه مسائل ارائه شده است [15]. از آنجایی که این اهداف با هم در یک راستا نیستند، بایستی از روشهای فشردهسازی یا Pareto Front استفاده نمود که در ادامه به توضیح این دو روش میپردازیم.
2-2-1 روش فشردهسازی
این روش یکی از سادهترین روشهای حل مسئله چندهدفه است که در آن برای هر هدف یک وزن در نظر گرفته میشود. سپس وزنها در اهداف ضرب شده و با یکدیگر جمع میشوند و هدف جدیدی را ایجاد میکنند. برای استفاده از این روش باید تمامی اهداف در یک راستا باشند (به صورت کمینهسازی یا بیشینهسازی). در ادامه، (3) نشاندهنده نحوه محاسبه تابع هدف در روش فشردهسازی است
(3)
که در آن و
وزنهای اهداف بوده که مجموع آنها برابر یک است.
2-2-2 روش Pareto Front
در این روش جوابهایی انتخاب میشوند که سایر جوابها نتوانند بر آن غلبه کنند. فرض کنید مسئله دارای دو هدف و
بوده که در آن
در راستای بیشینهسازی و
در راستای کمینهسازی است. برای این که یک جواب در Pareto Front قرار بگیرد، باید 2 شرط زیر همزمان در آن صادق باشد:
1) جوابی غالب است که هر دو تابع هدف و
در آن بهتر یا برابر جوابهای دیگر باشد.
2) جوابی غالب است که حتماً یکی از توابع و
در آن بهتر از سایر جوابها باشد.
و جوابهایی که شرایط بالا را داشته باشند در 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) کدگذاری شدهاند
(4)
که در آن ذره در تکرار
و
ویژگی
ام ذره
ام که مقدار آن بین صفر و یک است، میباشد و
تعداد ویژگیهای مسئله است. از آنجایی که در مسئله انتخاب ویژگی نیاز به کدگذاری به صورت صفر و یک داریم، از یک مقدار آستانه با نام
برای این کار استفاده میکنیم. مقدار
با توجه به [10] برابر 6/0 در نظر گرفته شده است. بنابراین
هایی که مقدارشان از
بزرگتر باشد، برابر یک و در غیر این صورت برابر صفر در نظر گرفته خواهند شد. نسخه دودویی
در (5) آمده است
(5)
که در آن نسخه دودویی
،
نشاندهنده انتخاب یا عدم انتخاب ویژگی
ام ذره
ام و
تعداد ویژگیهای مسئله است.
تقسیم دادههای مجموعه داده به آموزشی و تست و سپس اعمال گامهای زیر بر روی دادههای آموزشی: گام 1: مقداردهی اولیه جمعیت بر اساس قسمت 3-1 گام 2: ارزیابی مقدار برازش جمعیت بر اساس روش مجموع وزندار تطبیقپذیر گام 3: به روز رسانی آرشیو بر اساس مقدار برازش جمعیت گام 4: به روز رسانی جمعیت بر اساس (11) و (12) گام 5: اعمال جهش هوشمند و به روز رسانی ذرات گام 6: به روز رسانی آرشیو پس از اعمال جهش هوشمند گام 7: محاسبه و به روز رسانی امتیاز هر ذره بر اساس آرشیو گام 8: اعمال عملگر نخبهگرایی بر روی جمعیت آرشیو گام 9: اگر الگوریتم به بیشینه مقدار تکرار رسیده بود، به گام 10 برو و در غیر این صورت به گام 4 برگرد. گام 10: استخراج اعضای موجود در آرشیو به عنوان بهترین جوابهای روش پیشنهادی |
شکل 1: گامهای الگوریتم پیشنهادی.
3-2 ارزیابی برازش ذرات
همان طور که پیشتر اشاره شد، در روشهای مبتنی بر Wrapper، الگوریتم یادگیری نیز در انتخاب ویژگی دخالت دارد. به همین دلیل برای ارزیابی ویژگیهای انتخابشده از الگوریتم یادگیری KNN [23] استفاده گردیده است. در این مقاله دو هدف تعداد ویژگی انتخابشده و دقت الگوریتم به عنوان اهداف تابع برازش انتخاب شدهاند که با هم در تضاد هستند. به همین دلیل به جای دقت الگوریتم از خطای الگوریتم استفاده میکنیم تا اهداف هر دو در یک راستا شوند. در (6) نحوه محاسبه خطای الگوریتم آمده است
(6)
که در آن ،
،
و
به ترتیب برابر مثبت واقعی، مثبت کاذب، منفی واقعی و منفی کاذب هستند. در (7) نیز نحوه محاسبه تعداد ویژگیهای انتخابشده نشان داده شده است
(7)
که در آن تعداد ویژگیهای انتخابشده و
تعداد کل ویژگیهای مسئله است.
هر دو تابع هدف به صورت نرمالشده در نظر گرفته شدهاند که مقدار هر کدام بین صفر و یک است. اکنون به کمک روش مجموع وزندار تطبیقپذیر، تابع هدف نهایی به کمک (8) محاسبه میشود
(8)
که در آن و
به ترتیب وزنهای خطای الگوریتم و تعداد ویژگیهای انتخابشده هستند.
3-3 آرشیو
برای ذخیرهکردن بهترین ذرات یافتهشده در تکرارهای الگوریتم از مکانیزم آرشیو استفاده شده است. پس از هر تکرار، مقدار برازش هر ذره محاسبه میگردد و ذراتی که مقدار برازش آنها از بقیه ذرات بهتر باشد در آرشیو ذخیره میشوند. از آنجایی که اندازه آرشیو محدود است، در صورتی
شکل 2: روندنمای روش پیشنهادی.
که اندازه آرشیو به مقدار بیشینه خود رسیده بود، هنگام به روز رسانی آرشیو، اعضایی که مقدار تابع برازش آنها کمتر از کاندیدای جدید بود، با کاندیدای جدید عوض میشود. این فرایند باعث میشود که همواره بهترین جوابهای الگوریتم در طول اجرا در آرشیو نگهداری شوند.
3-4 امتیازدهی به ویژگیها
هدف اصلی انتخاب ویژگی، یافتن بهترین ویژگیها و حذف ویژگیهای اضافی است. برای رسیدن به این هدف، ویژگیها بر اساس تعداد مشاهده در آرشیو امتیازدهی میشوند. دلیل این امر آن است که آرشیو، بهترین جوابها را نگه میدارد. معادله (9) نمایشدهنده نحوه محاسبه امتیاز ویژگی است
(9)
که یک بردار با
بعد و به صورت
است که در آن
مقدار امتیاز هر ویژگی میباشد.
نمایانگر آرشیو و
مقدار دودودیی ویژگی در تکرار
است که در (5) نشان داده شده بود. اگر ویژگی
ام در هیچ یک از اعضای آرشیو انتخاب نشده باشد، مقدار آن برابر صفر خواهد بود و بیشینه مقدار امتیاز ویژگیها برابر اندازه آرشیو است.
3-5 به روز رسانی موقعیت ذره
در مسئله انتخاب ویژگی، المانهای ذرات همان ویژگیها هستند که
با تغییر مقادیر ویژگی ذرات حرکت میکنند. پس از به روز رسانی آرشیو، مجموعه ذرات دوبهدو با هم مقایسه میشوند. ذرهای که برازش بهتری داشت، به عنوان ذره برنده انتخاب شده و به گروه برندهها تعلق میگیرد
و ذره بازنده نیز به گروه بازندهها اضافه میشود. ذراتی که در گروه برنده هستند، به طور مستقیم به تکرار بعدی منتقل میشوند و ذراتی که در گروه بازندهها هستند به کمک (10) تا (12) [24] به روز رسانی میشوند
(10)
(11)
(12)
Input: population, archive, features rank Output: updated population Begin for if generated uniform random less than for if else end |
شکل 3: روش جهش هوشمند یکنواخت. (endهای اضافی حذف شد)
Input: population, archive, features rank Output: updated population Begin for if generated uniform random less than for if generated uniform random less than 0.5 then if else end |
شکل 4: روش جهش هوشمند غیر یکنواخت.
که در آن میانگین ذرات موجود در گروه برنده در تکرار
،
،
و
اعداد تصادفی بین صفر و یک و
یک ضریب از پیش تعریف شده است.
موقعیت ذره برنده در تکرار
،
موقعیت ذره بازنده و
نیز سرعت ذره بازنده در تکرار
در نظر گرفته شده است.
3-6 جهش هوشمند
در گام قبل ممکن است که ذرات پس از چندین تکرار در نقطه بهینه محلی گرفتار شوند و به همین دلیل نیاز به مکانیزمی است تا ذرات بتوانند از نقطه بهینه محلی خارج شوند. برای حل این مشکل مکانیزم جهش هوشمند ارائه گردیده است. در این روش، ابتدا جمعیت به سه دسته مساوی تقسیم میشود که دلیل این امر، حفظ جستجوی محلی در کنار جستجوی جهانی فضای حالت است. دسته اول بدون تغییر به نسل بعدی منتقل میشوند. در دسته دوم، یک عدد تصادفی تولید شده و اگر از یک مقدار پیشفرض کمتر باشد، مقادیر ویژگیها عوض میشوند. به این صورت که در آن اگر ویژگی انتخاب شده بود، به انتخابنشده تغییر میکند و اگر انتخاب نشده بود، به انتخابشده تغییر خواهد کرد. این عمل برای تمامی ویژگیهای ذره انجام خواهد گردید. در دسته سوم نیز یک عدد تصادفی تولید میشود و اگر از مقدار پیشفرض
کمتر بود، این ذره برای جهش انتخاب شده و برای هر المان ذره یک عدد تصادفی دیگر تولید میشود. اگر این عدد تصادفی از 5/0 کمتر بود، بر روی آن المان هیچ گونه جهشی انجام نمیشود و در غیر این صورت، اگر عدد تصادفی تولیدشده بیشتر از 5/0 بود، بر روی آن المان در صورتی که امتیاز آن کمتر از مقدار پیشفرض
باشد، عمل جهش انجام میشود. شبهکد مربوط به دو روش جهش پیشنهادی در شکلهای 3 و 4 آورده شده است.
Input: archive, features rank Output: updated archive Begin for begin for for calculate fitness of if fitness of end end |
شکل 5: روش نخبهگرایی هوشمند.
3-7 نخبهگرایی
ایده اصلی نخبهگرایی، ایجاد جواب بهتر در آرشیو میباشد و برای این منظور یک مکانیزم هوشمند ارائه شده است. در این روش ابتدا ویژگیها بر اساس امتیازشان رتبهبندی میشوند، سپس بر اساس (13) مجموعهای از ویژگیهای برتر انتخاب میگردند
(13)
که لیست بهترین ویژگیها و
مقدار امتیاز ویژگی
ام است. سپس این ویژگیها به صورت تصادفی با یکچهارم ویژگیهایی که مقدار آنها برابر یک است، جایگزین میشوند. در صورتی که مقدار برازش ذره جدید ایجادشده از ذره قبلی بهتر بود، با آن ذره تعویض میشود. این فرایند بر روی تمامی اعضای آرشیو اجرا میشود. شبهکد نخبهگرایی در شکل 5 آمده است.
3-8 مجموع وزندار تطبیقپذیر
همان طور که پیشتر اشاره شد، از روشهای حل مسائل بهینهسازی چندهدفه، استفاده از روشهای مبتنی بر فشردهسازی است و در این مقاله از روش مجموع وزندار تطبیقپذیر استفاده شده است. در این روش ابتدا وزنهای خطای الگوریتم و تعداد ویژگیهای انتخابشده که به ترتیب برابر و
هستند، مقداردهی اولیه میشوند. سپس از گام 30 به بعد با افزایش مضرب 10 از گامهای تکرار الگوریتم، از اهمیت وزن
کم شده و به وزن
اضافه میشود. این فرایند تا گام 70 ادامه مییابد. سپس از گام 70 به بعد با افزایش مضرب 10 از گامهای تکرار
به اهمیت وزن افزوده شده و از اهمیت
کاسته میشود. در ابتدای الگوریتم، اهمیت خطا بیشتر از تعداد ویژگیهای انتخابشده است. این کار باعث میشود که الگوریتم سعی در یافتن جوابهایی نماید که خطای کمتری دارند. سپس با افزایش گام تکرار، الگوریتم سعی در یافتن
جدول 1: توضیحات مجموعه داده.
نام | تعداد ویژگیها | تعداد دادهها | ویژگی نامشخص | تعداد کلاس |
Isolet | 617 | 7797 | خیر | 26 |
Musk | 167 | 6598 | خیر | 2 |
Madelon | 500 | 4400 | نامشخص | 2 |
Arrhythmia | 279 | 425 | بله | 16 |
Cnae | 857 | 1080 | نامشخص | 9 |
جدول 2: آزمایش یافتن مقدار بهینه .
مقدار | بهترین جواب 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 به صورت پیوسته در نظر گرفته شدهاند. بنابراین نیاز به فرایندی است تا نقاط پیوسته به گسسته تبدیل شوند و برای این کار از پارامتر استفاده
شده بود که مقدار آن برابر 6/0 است. از الگوریتم KNN با مقدار برابر 5 به عنوان الگوریتم یادگیری استفاده شده است. برای انتخاب مقادیر
و
روی مجموعه داده Arrhythmia آزمایشهایی با 30 تکرار انجام شده که بهترین نتایج آن در جداول 2 و 3 آورده شده است. با توجه به این آزمایشها، مقادیر
و
به ترتیب
جدول 3: آزمایش یافتن مقدار بهینه .
مقدار | بهترین جواب 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: مقداردهی پارامترهای الگوریتم پیشنهادی.
نام پارامتر | مقدار پارامتر |
| 6/0 |
| 75/0 |
| 25/0 |
| 1/0 |
| 3/0 |
| 35/0 |
| 4/0 |
برابر 4/0 و 35/0 انتخاب شده و سایر پارامترهای الگوریتم پیشنهادی در جدول 4 آمده است.
در سایر روشهای مبتنی بر PSO، سایز جمعیت برابر 30، بیشینه مقدار تکرار برابر 100، بیشینه مقدار سرعت یا همان برابر 6/0، مقادیر
و
برابر 146/0، مقدار
برابر 729/0 و مقدار
برابر 6/0 در نظر گرفته شده است. پارامترهای مخصوص هر روش بر اساس گزارشهای آنها تنظیم شده و احتمال پرش در روش HMPSOFS برابر 01/0 است. در روش CMDPSOFS وزن اینرسی به صورت تصادفی بین 1/0 و 5/0، مقادیر
و
اعداد تصادفی بین 5/1 و 2 و همچنین نرخ جهش در این روش برابر
که در آن
تعداد ویژگیهای مجموعه داده میباشد، در نظر گرفته شده است. برای NSGAII نیز پارامترها مشابه روش CMDPSOFS و نرخ برش برابر 9/0 است. لازم به ذکر است که در روش NSGAII کروموزومها به صورت یک آرایه
بعدی هستند که اگر مقدار آن برابر یک باشد به معنی انتخاب ویژگی و اگر مقدار آن برابر صفر باشد، به معنی عدم انتخاب ویژگی است [25].
4-3 بررسی نتایج شبیهسازی
در روش پیشنهادی، از پنج مجموعه داده "Isolte"، "Musk"، "Madelon"، "Arrhythmia" و "Cnae" برای مقایسه استفاده گردیده و تمامی مجموعه دادههای ذکرشده دارای بیش از 100 ویژگی هستند. روش AWMOPSOFS با پنچ روش که دو تای آنها روشهای پایه NSGAII [25] و MOPSO [26] و سه تای آنها روشهای مؤثر با نامهای CMDPSOFS، HMPSOFS و RFPSOFS هستند، مقایسه شده است. در شکلهای 6 تا 10 نتایج شبیهسازی آمده است. همان طور که در شکلها مشخص است، روش پیشنهادی به دلیل استفاده از جهش هوشمند و نخبهگرایی هوشمند توانسته که تعداد ویژگی کمتری با در نظر
شکل 6: نتایج شبیهسازی در مجموعه داده Musk.
شکل 7: نتایج شبیهسازی در مجموعه داده Madelon.
شکل 8: نتایج شبیهسازی در مجموعه داده Cnae.
گرفتن خطای الگوریتم انتخاب کند. با توجه به نتایج جدول 5، روش پیشنهادی در مقایسه با سایر روشها تعداد ویژگی کمتری انتخاب کرده است. در مجموعه دادههای "Musk" و "Madelon" روش پیشنهادی تعداد ویژگی کمتر قابل توجهی به نسبت سایر روشها انتخاب کرده است. با در نظر گرفتن تعداد ویژگیهای انتخابشده، خطای الگوریتم نیز به نسبت سایر روشها کمتر است. با این که در برخی مجموعه دادهها خطای سایر الگوریتمها مانند NSGAII و CMDPSOFS در مجموعه داده "Musk" بهتر از روش پیشنهادی است، اما تعداد ویژگیهای انتخابشده در آنها بیشتر میباشد. در برخی مجموعه دادهها مانند "Madelon" بیشینه تعداد ویژگی انتخابشده توسط روش پیشنهادی کمتر از کمینه تعداد ویژگی انتخابشده در سایر روشها است.
شکل 9: نتایج شبیهسازی در مجموعه داده Isolte.
شکل 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 از دانشگاه آمستردام هلند دریافت کرده است. ایشان هم اکنون به عنوان هیأت علمی در دانشگاه تبریز در حال فعالیت است. یکی از حوزههای تخصصی نامبرده در زمینه یادگیری ماشین نیمهنظارتی است.