رقم المقالة : زيارة : 7420 الصفحة: -

نوع المخطوط:

انتخاب ویژگی چندبرچسبه با استفاده از راهکار ترکیبی مبتنی بر الگوریتم بهینه‌سازی ازدحام ذرات

الموضوعات : electrical and computer engineering

آذر رفیعی ¹ , پرهام مرادی ² , عبدالباقی قادرزاده ³

1 - دانشگاه آزاد اسلامی واحد سنندج
2 - دانشگاه کردستان
3 - دانشگاه آزاد اسلامی واحد سنندج

تاريخ التأكيد : 20 الثلاثاء , ذو الحجة, 1443 تاريخ الإصدار : 24 الأربعاء , رجب, 1444

الکلمات المفتاحية:

ملخص المقالة :

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

المصادر:

نص كامل:

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

مقاله پژوهشی

انتخاب ویژگی چندبرچسبه با استفاده از راهکار ترکیبی
مبتنی بر الگوریتم بهینه‌سازی ازدحام ذرات

آذر رفیعی، پرهام مرادی و عبدالباقی قادرزاده

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

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

1- مقدمه

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

تا کنون برای انتخاب ویژگی، روش‌های متنوعی استفاده شده که به طور کلی می‌توان آنها را به سه دسته اصلی تقسیم‌بندی کرد: روش‌های فیلتری [2] تا [7]، روش‌های پوششی [8] تا [12] و روش‌های ترکیبی [13] و [14]. روش‌های فیلتر با استفاده از معیارهای مبتنی بر تئوری اطلاعات، میزان اهمیت هر ویژگی را محاسبه می‌کنند. این روش‌ها از سرعت بالایی، برخوردار و برای داده‌های با ابعاد بالا مناسب هستند. در روش پوششی، معیار انتخاب ویژگی، کارایی الگوریتم طبقه‌بندی است و بنابراین این روش از دقت بالایی در مقایسه با روش‌های فیلتر برخوردار است، اما به دلیل اجرای الگوریتم طبقه‌بند برای ارزیابی میزان شایستگی هر زیرمجموعه از ویژگی‌های انتخاب‌شده، سرعت کار روش پوششی کمتر از روش فیلتر است. به همین دلیل استفاده از روش‌های پوششی برای داده‌های با ابعاد بالا محدودیت ایجاد می‌کند. روش‌های ترکیبی با به کارگیری مزیت‌های هر 2 روش، قادر به تولید جواب‌هایی بهتر هستند.

در سال‌های اخیر، الگوریتم‌های هوش جمعی و تکاملی زیادی از جمله بهینه‌سازی کلونی مورچه (ACO) [6]، [7] و [15] تا [18]، الگوریتم ژنتیک (GA) [11] و [19] تا [21]، تبرید شبیه‌سازی شده (SA) [22]
و [23] و بهینه‌سازی ازدحام ذرات (PSO) [10] و [24] تا [27] برای انتخاب ویژگی تک‌برچسبه ارائه شده‌اند.

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

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

۱) از یک استراتژی جستجوی محلی که با الگوریتم بهینه‌سازی ذرات ادغام شده است، به‌منظور کاهش ابعاد زیرمجموعه ویژگی و انتخاب زیرمجموعه مطلوب استفاده می‌گردد.

۲) هدف استراتژی جستجوی محلی، هدایت فرایند جستجوی الگوریتم بهینه‌سازی ازدحام ذرات به منظور انتخاب ویژگی‌های متمایز با درنظرگرفتن اطلاعات همبستگی آنها است.

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

۴) انتخاب تعداد کم ویژگی‌های برجسته با استفاده از یک طرح تعیین اندازه زیرمجموعه خاص انجام می‌شود.

5) این الگوریتم در مقایسه با الگوریتم [10] کارایی بهتر و سرعت همگرایی بالاتری دارد.

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

2- پیشینه تحقیق

هدف از انتخاب ویژگی، کاهش ابعاد فضای ویژگی و بهبود کارایی و عملکرد طبقه‌بندی از طریق ازبین‌بردن ویژگی‌های نامربوط و تکراری است. به طور کلی، روش‌های انتخاب ویژگی چندبرچسبی به سه دسته فیلتر²، پیچشی³ و ترکیبی تقسیم می‌شوند. روش‌های فیلتر مستقل از الگوریتم‌های یادگیری، ابعاد داده‌ها را نیز کاهش می‌دهند. این روش‌ها ویژگی‌های موجود را بر مبنای تعدادی معیار، رتبه‌بندی نموده و ویژگی‌هایی را که دارای رتبه کافی نیستند، حذف می‌کنند. تا کنون روش‌های فیلتر بسیاری مانند ReliefF و مشتقات آن [3]، بهره اطلاعاتی⁴ [4] و اطلاعات متقابل⁵ [29] در زمینه انتخاب ویژگی مطرح شده است.

روش‌های انتخاب ویژگی چندبرچسبی از نظر مدل داده به دو دسته کلی تقسیم می‌شوند: تبدیل مسأله و انطباق الگوریتم. در الگوریتم‌های تبدیل مسأله، ابتدا داده‌های چندبرچسبی به یک یا چند داده تک‌برچسبی تبدیل می‌گردند و سپس انتخاب ویژگی روی داده تک‌برچسبی انجام می‌شود. Chen و همکارانش [30]، یک روش تبدیل بر پایه آنتروپی پیشنهاد می‌دهند. همچنین Spolaor و همکارانش [31]، LP و BR
را برای تبدیل داده استفاده می‌کنند و برای انتخاب ویژگی، روش‌های ReliefF و بهره اطلاعاتی را به کار می‌گیرند و نهایتاً کارایی این روش‌ها را با یکدیگر مقایسه می‌کنند. قابل ذکر است که روش BR استفاده‌شده در این کار، قادر به تشخیص همبستگی بین برچسب‌ها نیست و LP نیز در فاز آموزش دارای پیچیدگی بالایی می‌باشد. Relief تعداد ویژگی‌های کمتری را انتخاب می‌کند و به این دلیل است که تعامل بین ویژگی‌ها را در نظر می‌گیرد. این روش، یک جستجوی چندمتغیره بوده و قادر به تمیزدادن دو نمونه از یک کلاس یا کلاس‌های متفاوت است. کاهش ابعاد بدون لطمه‌زدن به عملکرد طبقه‌بندی، وابستگی بین هر ویژگی و برچسب کلاس را مشخص می‌کند.

در [32]، یک روش تبدیل مسأله هرس‌شده برای تبدیل داده چندبرچسبی به تک‌برچسبی به کار گرفته شده و سپس یک روش انتخاب ویژگی حریصانه بر پایه اطلاعات چندبعدی اجرا گردیده است. این روش در ابعاد بالا کارایی چندانی ندارد و در آن، LP قادر به تشخیص همبستگی بین برچسب‌ها است و وابستگی بین برچسب‌ها در نظر گرفته می‌شود. همچنین روشی در [33]، نتایج اولیه [32] را گسترش و روشی برای انتخاب خودکار پارامتر هرس پیشنهاد می‌دهد. روشی نیز در [3] پیشنهاد گردیده که مسأله چندبرچسبی را با استفاده از تبدیل هرس‌شده (PPT)
به مسأله تک‌برچسبی تبدیل می‌کند و سپس الگوریتم ReliefF برای اختصاص وزن به هر ویژگی به کار گرفته می‌شود. این روش نشان می‌دهد که روش‌های انطباقی بهتر از روش‌های تبدیل مسأله هستند. در [34] یک روش انتخاب ویژگی سریع مبتنی بر رتبه‌دهی ویژگی ارائه شده که با حذف محاسبات غیر ضروری و شناسایی ترکیب برچسب‌های مهم

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

آذر رفیعی، دانشکده مهندسی کامپیوتر، واحد سنندج، دانشگاه آزاد اسلامی، سنندج، ایران، (email: azar.rafie@gmail.com).

پرهام مرادی (نویسنده مسئول)، دانشکده مهندسی کامپیوتر، دانشگاه کردستان، سنندج، ایران، (email: p.moradi@uok.ac.ir).

عبدالباقی قادرزاده، دانشکده مهندسی کامپیوتر، واحد سنندج، دانشگاه آزاد اسلامی، سنندج، ایران، (email: b.ghaderzadeh@iausdj.ac.ir).

[2] . Filter

[3] . Wrapper

[4] . Gain Information

[5] . Mutual Information

جدول 1: خلاصه‌ای از کارهای انجام‌شده در زمینه انتخاب ویژگی چندبرچسبی روش‌ها.

روش‌ها	انتخاب ویژگی	تبدیل داده	روش جستجو	الگوریتم طبقه‌بندی	مجموعه داده
ELA [29]	فیلتر	Entropy	بهره اطلاعاتی- OCFS	SVM	متن
MGFS [36]	فیلتر	-	PageRank	MLKNN	دامنه‌های مختلف
MLACO [18]	فیلتر	-	الگوریتم کلونی مورچه	MLKNN	دامنه‌های مختلف
RF-BR, RF-LP, IG-BR, IG-LP [30]	فیلتر	LP, BR	اطلاعات متقابل- ReliefF	BRKNN	دامنه‌های مختلف
MI [32]	فیلتر	PPT	اطلاعات متقابل	MLKNN	بیولوژی، متن، تصویر
Memetic [8]	پیچشی	-	الگوریتم ژنتیک	MLNB	دامنه‌های مختلف
MLFS [9]	پیچشی	-	اطلاعات متقابل- الگوریتم ژنتیک	MLKNN	متن، تصویر
MEFS [13]	ترکیبی	LP	Max Avg, LP-Chi	LEAD, SVM, MLNB, MLKNN	موزیک
Sun [37]	فیلتر	-	اطلاعات متقابل	MLKNN	دامنه‌های مختلف
MLNB [11]	پیچشی	-	الگوریتم ژنتیک	MLNB	بیولوژی، تصویر
MI [29]	پیچشی	-	اطلاعات متقابل	MLNB	بیولوژی، متن، تصویر
ReliefF [3]	فیلتر	PPT	ReliefF	MLKNN, BRKNN	دامنه‌های مختلف
Khan [12]	پیچشی	-	الگوریتم ژنتیک	SVM, DT	موزیک
MPSOFS [10]	پیچشی	-	الگوریتم ازدحام ذرات	MLKNN	دامنه‌های مختلف
MMFS [35]	پیچشی	-	NSGA-II	MLKNN	موزیک، بیولوژی، متن
MLInfoGain [36]	فیلتر	-	بهره اطلاعاتی	Various Classifiers	دامنه‌های مختلف
MFNMI [2]	فیلتر	-	اطلاعات متقابل	MLKNN	دامنه‌های مختلف
MDMR [5]	فیلتر	-	حداقل افزونگی- حداکثر ارتباط	MLKNN, LIFT	تصویر
MLMLFS [14]	ترکیبی	-		MLKNN	دامنه‌های مختلف
Doquire [31]	فیلتر	PPT, LP	اطلاعات متقابل	MLKNN, SVM	دامنه‌های مختلف
IGMF [4]	فیلتر	-	بهره اطلاعاتی	SVM, MLKNN	بیولوژی، تصویر، موزیک

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

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

روش‌های پیچشی از یک الگوریتم یادگیری از پیش تعریف شده استفاده می‌کنند و این روش، ویژگی‌هایی را انتخاب می‌کند که کارایی الگوریتم یادگیری را افزایش دهند. در [11]، استخراج ویژگی بر پایه PCA است که با یک روش انتخاب ویژگی پیچشی پیاده‌سازی‌شده با الگوریتم ژنتیک ترکیب گردیده است. در پژوهشی دیگر، یک روش انتخاب ویژگی چندبرچسبی ممتیک پیشنهاد شده که روش ممتیک برای تعریف مجدد زیرمجموعه ویژگی‌های یافته‌شده توسط جستجوی ژنتیک استفاده می‌شود [8]. همچنین در [35]، یک الگوریتم انتخاب ویژگی چندبرچسبی بر پایه اطلاعات متقابل و الگوریتم ژنتیک آمده است. در مرحله اول، اطلاعات متقابل برای تکمیل ویژگی‌های انتخابی به صورت محلی به کار گرفته شده و سپس الگوریتم ژنتیک طبق نتایج این مرحله، زیرمجموعه ویژگی‌های بهینه سراسری را انتخاب می‌کند.

یک سری از کارها نیز در زمینه انتخاب ویژگی چندبرچسبی انجام شده که از مفهوم بهینه‌سازی چندهدفه استفاده می‌کنند. همه این روش‌ها جزء روش‌های پیچشی هستند که به طور معمول بر اساس متاهیوریستیک‌ها می‌باشند. برای مثال، ژانگ و همکارانش در [10] از الگوریتم ازدحام ذرات و [12] از الگوریتم ژنتیک استفاده می‌کند. در همه این کارها، دو یا سه معیار ارزیابی به طور هم‌زمان بهینه می‌شوند. مثلاً در [12] از 3 معیار ارزیابی دقت¹، افت همینگ² و micro-Average و در [10] از افت همینگ و دقت استفاده می‌شود. در پژوهشی دیگر و در ابتدای کار، فضای راه حل به یک گراف وزن‌دار کامل، تبدیل و سپس با استفاده از روش PageRank، اهمیت هر ویژگی محاسبه می‌شود [36]. در [18]، یک روش فیلتر بر پایه الگوریتم کلونی مورچه پیشنهاد گردیده که شباهت کسینوسی نرمال بین ویژگی‌ها و برچسب‌ها در نظر گرفته می‌شود.

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

Algorithm 1: MPSOLS1-Multi label Feature Selection based on Particle Swarm Optimization and Local search strategy

Input: Feature, : maximum cycle number, NP: number of particles.

Output: Final set of features.

Begin algorithm

Begin initialization

Determining number of feature (s) to k using Eq (1)

for i1 to NP do

Create random particle .

Create random velocity .

end for

Compute and for all features using Eqs (2), (3)

Similar feature

Dissimilar feature

end initialization

for i1 to do

Compute updating the particle velocity using Eq (4)

Compute updating the position of particle using Eq (6)

Similar features.

Dissimilar features.

Remove all feature in that is 0 in particle x.

Calculate the value of and

Perform "particle movement" on each position of particle

and replace it.

if then

end for

Return

end algorithm

شکل 1: شبه‌کد روش پیشنهادی MPSOLS³.

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

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

الگوریتم PSO یک روش بهینه‌سازی مبتنی بر قواعد احتمال است که در سال 1995 برای اولین بار با الهام از رفتار پرندگان در هنگام جستجوی غذا توسط کندی و آبرهارت ابداع شد [38]. در این الگوریتم، ابتدا یک مجموعه جواب اولیه تولید می‌شود و سپس برای یافتن جواب بهینه در فضای پاسخ‌های ممکن، یا به‌هنگام‌کردن نسل‌ها، جستجوی پاسخ انجام می‌گیرد. هر ذره به صورت چندبعدی با دو مقدار موقعیت و سرعت تعریف می‌گردد و در هر مرحله از حرکت ذره، با دو شاخص سرعت و موقعیت، بهترین پاسخ‌ها از لحاظ شایستگی برای تمام ذرات تعیین می‌شوند [39].

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

3-1 تعیین اندازه زیرمجموعه و گروه‌بندی ویژگی‌ها

برای تعیین اندازه زیرمجموعه از یک تابع تصادفی احتمال استفاده می‌شود که تلاش می‌کند تعداد کمتری از ویژگی‌ها را برای تعیین اندازه زیرمجموعه فراهم کند [40]. ابتدا از (1) برای تعیین اندازه زیرمجموعه ویژگی‌ها استفاده می‌شود [41]

(1)

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

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

(2)

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

(3)

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

3-2 مقداردهی و به‌روزرسانی ذرات

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

(4)

که در آن نمایانگر تعداد تکرار، بهترین مقدار به دست آمده توسط ذره ام از آغاز اجرای الگوریتم تا تکرار ام، بهترین مقدار به دست آمده توسط جمعیت از آغاز اجرای الگوریتم تا تکرار ام و و دو عدد حقیقی ثابت هستند. همچنین و بردارهایی تصادفی هستند که مقادیر آنها در بازه صفر و یک قرار دارند. لازم به ذکر است که اگر سرعت ذرات بالا برود و از تجاوز کند، باید سرعت این بُعد را به مطابق معادله زیر محدود کرد

(5)

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

(6)

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

3-3 استراتژی جستجوی محلی

در این گام برای یک ذره، عملگر "ADD" و "Delete" به منظور بهبود جستجوی محلی ذره به کار گرفته شده است. یک ذره برای انتخاب تعدادی از ویژگی‌های مطلوب، عملگر "ADD" را به کار می‌برد و عملگر "Delete" جهت حذف یک تعداد از ویژگی‌های موجود استفاده می‌شود. به عبارتی اپراتور "ADD"، ویژگی‌های غیر مشابه را به ذره اضافه می‌کند و ویژگی‌های مشابه با اپراتور "Delete" از ذره حذف می‌شوند [40].
در عملگر جستجوی محلی، ابتدا همه ویژگی‌های انتخاب‌شده توسط ذره استخراج می‌گردند. سپس الگوریتم در هر ذره، تعدادی از بیت‌های یک را در ذره تولیدشده جدید مشخص می‌کند (مثال 1011000111) و آنها را درون زیرگروه قرار می‌دهد (مثال: ).

هر مؤلفه  با  و  مقایسه و زیرگروه  به  و  تقسیم می‌شود. شامل ویژگی‌هایی است که در  وجود دارند و ویژگی‌های باقیمانده  در  قرار می‌گیرند [44]. سپس در گام بعدی، همه ویژگی‌های  و  به ترتیب صعودی‌بودن و بر اساس مقدار همبستگی آنها مرتب می‌شوند که اولین ویژگی و آخرین ویژگی از
و  دارای بیشترین تمایز و بیشترین شباهت هستند. در حرکت ذره، نیازمند کنترل بادقت تعداد بیت‌های 1 در ذره تولیدشده جدید هستیم و با توجه به به‌روزرسانی سرعت ذرات، اگر سرعت از مقدار rand مشخص‌شده بیشتر باشد، موقعیت ذره مورد نظر 1 و اگر کمتر باشد، صفر خواهد شد.
در پایان، تعدادی از ویژگی‌های مشابه و غیر مشابه با محاسبه مقدار
و  معین می‌شوند. در اینجا  و  است، در حالی که  یک پارامتر خاص کاربر و  اندازه زیرمجموعه اولیه ویژگی‌هاست که در مرحله اول تخمین زده شد. سپس طول  و  را با یکدیگر مقایسه می‌کنیم، به طوری که اگر تعداد ویژگی‌های غیر مشابه در ذره کوچک‌تر از  باشد ، آن گاه  ویژگی درون  به ذره اضافه می‌شود و در غیر این صورت،  ویژگی درون  باید از ذره حذف گردد. این در حالی است که اگر تعداد ویژگی‌های مشابه بزرگ‌تر از  باشد ، باید  ویژگی مشابه درون  از ذره حذف شوند. به عبارت دیگر، زمانی که تعداد ویژگی‌های مشابه در ذره تولیدشده کوچک‌تر از  است،  ویژگی درون  به ذره اضافه می‌شود.

3-4 محاسبه تناسب

روش پیشنهادی از ML-kNN برای ارزیابی یک راه حل زیرمجموعه ویژگی کاندیدا استفاده می‌کند. قبل از فرایند ارزیابی، ابتدا هر ویژگی با مقیاس‌هایی بین ۱- و ۱ نرمال می‌شود. فرایند نرمال‌سازی، ویژگی‌های غالب با مقادیر عددی بیشتر را به ویژگی‌هایی با محدوده عددی محدود، تغییر می‌دهد. نتایج آزمایش‌ها نشان داد که مقیاس‌بندی مقادیر ویژگی‌ها می‌تواند به بهبود دقت طبقه‌بندی کمک کند. بنابراین در این مقاله، یک روش نرمال‌سازی خطی برای مقیاس‌بندی مجموعه‌های داده‌ به شرح زیر استفاده می‌شود

جدول 2: مشخصات 6 مجموعه داده با کاربردهای مختلف.

اسم	تعداد برچسب	تعداد ویژگی	تعداد نمونه	دامنه
Yeast	14	103	2417	زیست‌شناسی
Birds	19	260	645	صوت
Scene	6	294	2407	تصویر

(7)

که در آن و به ترتیب کران پایین و بالای فرایند نرمال‌سازی و و حداکثر و حداقل مقادیر ویژگی هستند. پس از فرایند نرمال‌سازی، مجموعه داده‌ جدید از مجموعه داده اصلی با ویژگی‌هایی
که در راه حل ذره وجود داشتند، استخراج گردیده و سپس مجموعه داده‌ها به بخش آموزش و تست تقسیم می‌شوند (60% برای مجموعه آموزشی
و 4۰% برای مجموعه تست). در این مرحله، روش اعتبارسنجی متقابل [45] برای ارزیابی هر ذره با استفاده از طبقه‌بندی کننده ML-kNN به کار گرفته می‌شود. پس برای هر مجموعه داده، مجموعه آموزشی به ۱۰ قسمت تقسیم می‌گردد که هر بخش همان نسبت را برای هر کلاس از داده‌ها به اشتراک می‌گذارد. بنابراین برای هر مجموعه داده، 9 قسمت اول داده‌ها در فرایند آموزش برای ساخت مدل یادگیری استفاده می‌شود، در حالی که آخرین بخش در فرایند اعتبارسنجی برای ارزیابی مقدار تناسب ذره مورد استفاده قرار می‌گیرد. اگر دقت دو راه حل یکسان باشد، راه حل با استفاده از تعداد کوچک‌تر ویژگی‌ها انتخاب می‌شود.

4- نتایج آزمایش‌ها

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

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

4-2 معیارهای ارزیابی

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

- افت همینگ: معیار افت همینگ، درصد برچسب‌هایی را که به درستی طبقه‌بندی نشده‌اند، محاسبه می‌کند. کمترین مقدار، بهترین کارایی را دارد

(8)

∆ تفاوت متقارن بین دو مجموعه است.

- یک خطا⁶: این معیار تعداد دفعاتی را می‌شمرد که برچسب با بیشترین درجه تعلق به یک نمونه، متعلق به آن نمونه نباشد

(9)

- پوشش⁷: این معیار تعداد گام‌هایی را می‌شمرد که باید لیست برچسب‌های درجه‌بندی‌شده را طی نمود تا تمام برچسب‌های هر نمونه را پوشش داد

(10)

- افت رتبه⁸: میانگین تعداد دفعاتی را محاسبه می‌کند که یک برچسب مرتبط، رتبه بالاتری از یک برچسب نامربوط گرفته است

(11)

- میانگین صحت⁹: میانگین درصد برچسب‌های مرتبط را از یک نمونه که رتبه آنها از رتبه یک برچسب مرتبط خاص متعلق به آن نمونه بیشتر باشد، می‌شمرد

(12)

4-3 نتایج و بحث

برای ارزیابی کارایی روش پیشنهادی و مقایسه آن با روش‌های MPSOFS [10]، MLNB [11]، ParetoFS [47]، PMU [48]، ELA-CHI [30]، PPT-CHI [35]، PPT-MI [32] و MLACO [18] آزمایش‌هایی انجام شده و این در حالی است که در تمامی روش‌ها از طبقه‌بند ML-KNN [46] استفاده گردیده است. همچنین به جز روش MPSOFS و MLNB که پیچشی هستند، سایر روش‌ها از نوع فیلتر می‌باشند. در آزمایش‌ها از مجموعه‌های داده‌ای مانند Yeast، Scene و Birds استفاده شده است. جداول 3 تا 5، مقایسه عملکرد الگوریتم‌های مورد آزمایش را از منظر معیارهای افت همینگ، افت رتبه، یک- خطا، پوشش و میانگین صحت بر روی مجموعه‌های مختلف داده نشان می‌دهد. برای هر معیار ارزیابی، علامت به صورت "مقدار بیشتر، بهتر است" و علامت به صورت "مقدار کمتر، بهتر است" تعریف می‌شود و همچنین نتیجه بهتر به صورت پررنگ‌تر نشان داده شده است. در این جدول، آزمون ویلکاکسون¹⁰ برای مقایسه کارایی روش‌های انتخاب ویژگی مورد استفاده قرار می‌گیرد. این روش، یک آزمون آماری استنباطی است که برای ارزیابی همانندی دو نمونه وابسته با مقیاس رتبه‌ای به کار می‌رود. این روش تفاوت بین هر جفت داده با ارزش را محاسبه کرده

[1] . Accuracy

[2] . Hamming Loss

[3] . Multi Label Feature Selection Based on Particle Swarm Optimization and Local Search

[4] . Roulette Wheel

[5] . http://mulan.sourceforge.net/datasets.html

[6] . One Error

[7] . Coverage

[8] . Ranking Loss

[9] . Average Precision

[10] . Wilcoxon

جدول 3: نتایج مقایسه روش پیشنهادی با سایر روش‌ها با 100 تکرار مستقل روی مجموعه داده Birds.

الگوریتم معیار	MPSOFS	MLACO	MLNB	PPT-CHI	PPT-MI	ELA-CHI	PMU	ParetoFS	MPSOLS	ویلکاکسون
افت همینگ ↓	04367/0	098455/0	093042/0	109038/0	190302/0	145968/0	101452/0	124785/0	0389/0	+
افت رتبه ↓	211628/0	227234/0	222522/0	21857/0	26698/0	26361/0	24897/0	287933/0	20546/0	+
یک- خطا ↓	517442/0	510153/0	593023/0	6014/0	589005/0	61342/0	603845/0	57548/0	55125/0	+
پوشش ↓	557276/2	515601/3	662539/2	75142/2	94756/2	66578/2	5357/2	562456/2	50983/2	+
میانگین صحت ↑	534813/0	507623/0	487686/0	52465/0	51426/0	51022/0	5352/0	547029/0	55796/0	+

جدول 4: نتایج مقایسه روش پیشنهادی با سایر روش‌ها با 100 تکرار مستقل روی مجموعه داده Yeast.

الگوریتم معیار	MPSOFS	MLACO	MLNB	PPT-CHI	PPT-MI	ELA-CHI	PMU	ParetoFS	MPSOLS	ویلکاکسون
افت همینگ ↓	193722/0	214774/0	214052/0	355700/0	415478/0	378954/0	344785/0	504541/0	17001/0	+
افت رتبه ↓	169225/0	192859/0	181467/0	70684/0	7312/0	673214/0	70245/0	76045/0	155846/0	+
یک- خطا ↓	248637/0	274561/0	245365/0	83710/0	682711/0	812034/0	9037/0	3553/0	24233/0	+
پوشش ↓	348964/6	754812/6	589967/6	230945/7	219387/7	227398/7	23247/7	196205/7	44826/6	+
میانگین صحت ↑	756879/0	737835/0	744186/0	255597/0	242264/0	253145/0	255897/0	236478/0	77002/0	+

جدول 5: نتایج مقایسه روش پیشنهادی با سایر روش‌ها با 100 تکرار مستقل روی مجموعه داده Scene.

الگوریتم معیار	MPSOFS	MLACO	MLNB	PPT-CHI	PPT-MI	ELA-CHI	PMU	ParetoFS	MPSOLS	ویلکاکسون
افت همینگ ↓	087375/0	135001/0	13364/0	261158/0	336425/0	254487/0	350564/0	358810/0	079421/0	+
افت رتبه ↓	094273/0	240369/0	123244/0	5602/0	61245/0	56024/0	53423/0	74125/0	10181/0	+
یک- خطا ↓	231605/0	45748/0	31689/0	74254/1	39449/1	82461/1	92906/1	86785/0	24261/0	+
پوشش ↓	58194/0	878625/0	714883/0	17624/1	169502/1	177431/1	178477/1	14350/1	60013/0	+
میانگین صحت ↑	82347/0	76548/0	803491/0	658241/0	56854/0	66458/0	67895/0	42998/0	83988/0	+

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

همان طور که مشاهده می‌کنید در تمام معیارها به جز پوشش، روش پیشنهادی بهترین عملکرد را داشته و در معیار پوشش نیز روش پیشنهادی پس از روش MPSOFS در جایگاه دوم قرار دارد. همچنین در بعضی از مجموعه‌های داده، اختلاف روش پیشنهادی با سایر روش‌ها بسیار قابل توجه است. به عنوان مثال، پوشش در مجموعه داده‌ای Scene برای روش پیشنهادی برابر 60013/0 و اختلاف پوشش در این روش با روش PPT-CHI تقریباً برابر 57/0 است. همچنین معیار افت رتبه در مجموعه داده Birds برای روش پیشنهادی برابر 2054/0 است که اختلاف آن با روش ParetoFS، 08/0 و با روش ELA-CHI، 05/0 می‌باشد. در معیار میانگین صحت مشاهده می‌کنیم که اختلاف روش پیشنهادی در مجموعه داده Yeast نسبت به روش ParetoFS، 53/0 می‌باشد و این در حالی است که با توجه به این معیار، در سایر مجموعه‌های داده نیز روش پیشنهادی نتایج بهتری را کسب کرده است. روش پیشنهادی از نظر معیار افت همینگ در برخی مجموعه‌های داده با اختلاف بالایی نسبت به سایر روش‌ها جایگاه اول را به دست آورده است. برای نمونه، اختلاف این معیار در مجموعه داده Birds با توجه به روش پیشنهادی نسبت به روش PPT-MI، 15/0 یا در مجموعه داده Scene نسبت به روش ParetoFS، 27/0 می‌باشد. روش پیشنهادی در تمامی معیارها در مقایسه با روش MLACO نیز نتایج قابل توجهی را به دست آورده است. جدول 3 نشان می‌دهد که روش پیشنهادی بهترین عملکرد را در بین تمام روش‌های انتخاب ویژگی دارد. همان طور که مشاهده می‌شود، در جدول 3 نتایج آماری به‌دست‌آمده کارایی بهتر روش پیشنهادی نسبت به دیگر روش‌ها را بیان می‌کنند.

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

(الف)

(ب)

(ج)

(د)

شکل 2: نتایج آزمایش‌ها بر روی مجموعه داده Yeast، (الف) افت همینگ، (ب) افت رتبه، (ج) پوشش و (د) میانگین صحت.

ترتیب، مقایسه عملکرد الگوریتم‌های مورد آزمایش را از نظر معیارهای افت همینگ، افت رتبه، یک- خطا، پوشش و میانگین صحت نشان می‌دهند. در همه نمودارهای موجود در آزمایش‌ها، محور افقی نشان‌دهنده تعداد ویژگی‌های انتخاب‌شده و محور عمودی بیانگر کارایی طبقه‌بندی است. تعداد ویژگی انتخاب‌شده توسط کاربر تعریف می‌شود و هر روش دارای 200 تکرار مستقل می‌باشد. در شکل‌های 2 تا 4 واضح است که روش پیشنهادی، کمترین افت همینگ را در مجموعه‌های داده Yeast و Scene به دست آورده است. در این مجموعه‌های داده، روش پیشنهادی با افزایش تعداد ویژگی‌های انتخاب‌شده به نتایج بهتری دست یافته و می‌توان نتیجه گرفت که قدرت ویژگی‌های پیش‌بینی‌کننده به طور قابل توجهی افزایش یافته است. معیار پوشش در مجموعه‌های داده Birds و Yeast کمترین مقدار را نسبت به سایر روش‌ها دارد و این معیار در این مجموعه‌های داده با بیشترشدن تعداد ویژگی‌ها، شیب نزولی بیشتری را

(الف)

(ب)

(ج)

(د)

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

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

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

(الف)

(ب)

(ج)

(د)

شکل 4: نتایج آزمایش‌ها بر روی مجموعه داده Scene، (الف) افت همینگ، (ب) افت رتبه، (ج) پوشش و (د) میانگین صحت.

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

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

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

شکل 5: نمودار راداری بر روی مجموعه داده Birds.

شکل 6: نمودار راداری بر روی مجموعه داده Scene.

شکل 7: نمودار راداری بر روی مجموعه داده Yeast.

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

مراجع

[1] م. رحمانینیا و پ. مرادی، "يك الگوريتم انتخاب ويژگي برخط در جريان دادهها با استفاده از اطلاعات متقابل چندمتغيره،" نشریه مهندسی برق و مهندسی كامپیوتر ایران، ب- مهندسی کامپیوتر، سال 18، شماره 4، صص. 336-327، زمستان 1399.

[2] Y. Lin, Q. Hu, J. Liu, J. Chen, and J. Duan, "Multi-label feature selection based on neighborhood mutual information," Applied Soft Computing, vol. 38, pp. 244-256, Jan. 2016.

[3] O. Reyes, C. Morell, and S. Ventura, "Scalable extensions of the ReliefF algorithm for weighting and selecting features on the multi-label learning context," Neurocomputing, vol. 161, pp. 168-182, Aug. 2015.

[4] L. Li, et al., "Multi-label feature selection via information gain," in Proc. Int. Conf. on Advanced Data Mining and Applications, ADMA'14, pp. 345-355, Guilin, China, 19-21 Dec. 2014.

[5] Y. Lin, Q. Hu, J. Liu, and J. Duan, "Multi-label feature selection based on max-dependency and min-redundancy," Neurocomputing, vol. 168, pp. 92-103, Nov. 2015.

[6] S. Tabakhi and P. Moradi, "Relevance-redundancy feature selection based on ant colony optimization," Pattern Recognition, vol. 48, no. 9, pp. 2798-2811, Sept. 2015.

[7] P. Moradi and M. Rostami, "Integration of graph clustering with
ant colony optimization for feature selection," Knowledge-Based Systems, vol. 84, pp. 144-161, Aug. 2015.

[8] J. Lee and D. W. Kim, "Memetic feature selection algorithm for multi-label classification," Information Sciences, vol. 293, pp. 80-96, Feb. 2015.

[9] Y. Yu and Y. Wang, "Feature selection for multi-label learning using mutual information and GA," in Proc. 9th Int. Conf. on Rough Sets and Knowledge Technology, RSKT'14, pp. 454-463, Shanghai, China, 24-26 Oct. 2014.

[10] Y. Zhang, D. W. Gong, X. Y. Sun, and Y. N. Guo, "A PSO-
based multi-objective multi-label feature selection method in classification," Scientific Reports, vol. 7, Article ID: 376, Mar. 2017.

[11] M. L. Zhang, J. M. Peña, and V. Robles, "Feature selection for multi-label naive bayes classification," Information Sciences, vol. 179, no. 19, pp. 3218-3229, Sept. 2009.

[12] M. A. Khan, A. Ekbal, E. L. Mencía, and J. Fürnkranz, "Multi-objective optimisation-based feature selection for multi-label classification," in Proc. Int. Conf. on Applications of Natural Language to Information Systems, NLDB'17, pp. 38-41, Liege, Belgium, 21-23 Jun. 2017.

[13] M. You, J. Liu, G. Z. Li, and Y. Chen, "Embedded feature selection for multi-label classification of music emotions," International J. of Computational Intelligence Systems, vol. 5, no. 4, pp. 668-678, Aug. 2012.

[14] P. Zhu, Q. Xu, Q. Hu, C. Zhang, and H. Zhao, "Multi-label feature selection with missing labels," Pattern Recognition, vol. 74, pp. 488-502, Feb. 2018.

[15] S. Tabakhi, A. Najafi, R. Ranjbar, and P. Moradi, "Gene selection for microarray data classification using a novel ant colony optimization," Neurocomputing, vol. 168, pp. 1024-1036, Nov. 2015.

[16] R. K. Sivagaminathan and S. Ramakrishnan, "A hybrid approach for feature subset selection using neural networks and ant colony optimization," Expert Systems with Applications, vol. 33, no. 1, pp. 49-60, Jul. 2007.

[17] M. H. Aghdam, N. Ghasem-Aghaee, and M. E. Basiri, "Text feature selection using ant colony optimization," Expert Systems with Applications, vol. 36, no. 3, pt. 2, pp. 6843-6853, Apr. 2009.

[18] M. Paniri, M. B. Dowlatshahi, and H. Nezamabadi-pour, "MLACO: a multi-label feature selection algorithm based on ant colony optimization," Knowledge-Based Systems, vol. 192, Article ID: 105285, Mar. 2020.

[19] J. Yang and V. Honavar, "Feature subset selection using a genetic algorithm," IEEE Intelligent Systems, vol. 13, no. 2, pp. 117-136, Mar. 1998.

[20] M. Rostami and P. Moradi, "A clustering based genetic algorithm for feature selection," in Proc. 6th Conf. on Information and Knowledge Technology, IKT'14, pp. 112-116, Shahrood, Iran, 27-29 May. 2014.

[21] T. M. Hamdani, J. M. Won, A. M. Alimi, and F. Karray, "Hierarchical genetic algorithm with new evaluation function and bi-coded representation for the selection of features considering their confidence rate," Applied Soft Computing, vol. 11, no. 2, pp. 2501-2509, Mar. 2011.

[22] S. W. Lin, Z. J. Lee, S. C. Chen, and T. Y. Tseng, "Parameter determination of support vector machine and feature selection using simulated annealing approach," Applied Soft Computing, vol. 8, no. 4, pp. 1505-1512, Sep. 2008.

[23] S. W. Lin, T. Y. Tseng, S. Y. Chou, and S. C. Chen, "A simulated-annealing-based approach for simultaneous parameter optimization and feature selection of back-propagation networks," Expert Systems with Applications, vol. 34, no. 2, pp. 1491-1499, Feb. 2008.

[24] L. Y. Chuang, C. H. Yang, and J. C. Li, "Chaotic maps based on binary particle swarm optimization for feature selection," Applied Soft Computing, vol. 11, no. 1, pp. 239-248, Jan. 2011.

[25] Y. Liu, et al., "An improved particle swarm optimization for feature selection," J. of Bionic Engineering, vol. 8, no. 2, pp. 191-200, Jun. 2011.

[26] B. Xue, M. Zhang, and W. N. Browne, "Particle swarm optimisation for feature selection in classification: novel initialisation and updating mechanisms," Applied Soft Computing, vol. 18, pp. 261-276, May 2014.

[27] H. M. Abdelsalam and A. M. Mohamed, "Optimal sequencing of design projects' activities using discrete particle swarm optimisation," International J. of Bio-Inspired Computation, vol. 4, no. 2, pp. 100-110, 2012.

[28] K. Demir, B. H. Nguyen, B. Xue, and M. Zhang, " Particle swarm optimisation for sparsity-based feature selection in multi-label classification," in Proc. of the Genetic and Evolutionary Computation Conf. Companion, pp. 232-235, Boston, MA, USA, 9-13 Jul. 2022.

[29] J. Lee and D. W. Kim, "Mutual information-based multi-label feature selection using interaction information," Expert Systems with Applications, vol. 42, no. 4, pp. 2013-2025, Mar. 2015.

[30] W. Chen, J. Yan, B. Zhang, Z. Chen, and Q. Yang, "Document transformation for multi-label feature selection in text categorization," in Proc of 7th IEEE Int. Conf. on Data Mining, ICDM'07, vol. ???, pp. 451-456, Omaha, NE, USA, 28-31 Oct. 2007.

[31] N. Spolaôr, E. A. Cherman, M. C. Monard, and H. D. Lee, "A comparison of multi-label feature selection methods using the problem transformation approach," Electronic Notes in Theoretical Computer Science, vol. 292, pp. 135-151, Mar. 2013.

[32] G. Doquire and M. Verleysen, "Feature selection for multi-label classification problems," in Proc of Int. Work-Conf. on Artificial Neural Networks, IWANN'11, pp. 9-16, Torremolinos-Málaga, Spain, 8-10 Jun. 2011.

[33] G. Doquire and M. Verleysen, "Mutual information-based feature selection for multilabel classification," Neurocomputing, vol. 122, pp. 148-155, Dec. 2013.

[34] J. Lee and D. W. Kim, "Fast multi-label feature selection based on information-theoretic feature ranking," Pattern Recognition, vol. 48, no. 9, pp. 2761-2771, Sept. 2015.

[35] J. Read, B. Pfahringer, and G. Holmes, "Multi-label classification using ensembles of pruned sets," in Proc of 8th IEEE Int. Conf. on Data Mining, pp. 995-1000, Pisa, Italy, 15-19 Dec. 2008.

[36] A. Hashemi, M. B. Dowlatshahi, and H. Nezamabadi-pour, "MGFS: a multi-label graph-based feature selection algorithm via PageRank centrality," Expert Systems with Applications, vol. 142, Article ID: 113024, Mar. 2020.

[37] Z. Sun, et al., "Mutual information based multi-label feature selection via constrained convex optimization," Neurocomputing, vol. 329, pp. 447-456, Feb. 2019.

[38] J. Kennedy and R. Eberhart, "Particle swarm optimization," in Proc. of Int. Conf. on Neural Networks, ICNN'95, vol. 4, pp. 1942-1948, Perth, Australia, 27 Nov.-1 Dec. 1995.

[39] ح. افراخته و پ. مرادی، "روشی جدید به‌منظور خوشه‌بندی داده‌های سرعت باد در نیروگاه‌های بادی با استفاده از الگوریتم‌های FCM و PSO ،" نشریه مهندسی برق و مهندسی كامپیوتر ایران، ب- مهندسی کامپیوتر، سال 8، شماره 3،
صص. 214-210، پاییز 1389.

[40] M. M. Kabir, M. Shahjahan, and K. Murase, "A new local search based hybrid genetic algorithm for feature selection," Neurocomputing, vol. 74, no. 17, pp. 2914-2928, Oct. 2011.

[41] D. P. Muni, N. R. Pal, and J. Das, Genetic Programming for Simultaneous Feature Selection and Classifier Design, 2006.

[42] M. M. Kabir, M. M. Islam, and K. Murase, "A new wrapper feature selection approach using neural network," Neurocomputing, vol. 73, pp. 3273-3283, Oct. 2010.

[43] P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom, and J. Riedl, "GroupLens: an open architecture for collaborative filtering of netnews," in Proc. of the ACM Conf. on Computer Supported Cooperative Work, CSCW'94, pp. 175-186, Chapel Hill, NC, USA, 22-26 Oct. 1994.

[44] X. He, D. Cai, and P. Niyogi, "Laplacian score for feature selection," in Proc. of the 18th Int. Conf. on Neural Information Processing Systems, NIPS'05, pp. 507-514, Vancouver, Canada, 5-8 Dec. 2005.

[45] M. Stone, "Cross‐validatory choice and assessment of statistical predictions," J. of the Royal Statistical Society: Series B (Methodological), vol. 36, pp. 111-133, 1974.

[46] 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.

[47] S. Kashef and H. Nezamabadi-pour, "A label-specific multi-label feature selection algorithm based on the Pareto dominance concept," Pattern Recognition, vol. 88, pp. 654-667, 2019.

[48] J. Lee and D. W. Kim, "Feature selection for multi-label classification using multivariate mutual information," Pattern Recognition Letters, vol. 34, no. 3, pp. 349-357, Feb. 2013.

[49] D. J. Sheskin, Handbook of Parametric and Nonparametric Statistical Procedures, 5th ed., Chapman & Hall, 2011.

آذر رفیعی كارشناسي و كارشناسي ارشد و دکتری مهندسي كامپيوتر را بهترتيب در
سالهاي 1391 و 1394 و 1401 دریافت كرد. وي از سال 1394 در دانشگاه، مشغول تدريس ميباشد. علايق تحقيقاتي وي شامل دادهکاوی، یادگیری ماشین و یادگیری عمیق ميباشد.

پرهام مرادي دوره كارشناسي را در رشته مهندسي كامپيوتر در سال 1381 در دانشگاه صنعتي اميركبير به پايان رسانيد. ايشان همچنين دوره كارشناسي ارشد و دكتري را در رشته علوم كامپيوتر دانشگاه صنعتي اميركبير بهترتيب در سالهاي 1384 و 1389 به پايان رسانيد. ايشان بخشي از تحقيقات دوره دكتري را به عنوان فرصت مطالعاتي را در دانشگاه پلي تكنيك فدرال لوزان سوئیس (EPFL) در سال 1388 به انجام رسانيد.
نامبرده در سال 1389 به عنوان هيأت علمي در گروه مهندسي كامپيوتر دانشگاه كردستان مشغول فعاليت گردید. در ادامه در سال 1395 به مرتبه دانشياري ارتقاء يافت. حاصل تحقيقات ايشان تاكنون انتشار بيش از 90 مقاله در مجلات و كنفرانسهاي معتبر بوده است. ايشان همچنين بر اساس گزارش منتشره دانشگاه استنفورد، به عنوان دانشمند دو درصد برتر در سال 2019 شناخته شدند. تحقيقات ايشان شامل يادگيري ماشين، يادگيري تقويتي، تحليل شبكههاي اجتماعي، علوم داده و سيستمهاي توصيهگر است. ايشان در دانشگاه كردستان مسئوليت هايي همچون مدير گروه، مدير آموزش هاي آزاد و مجازي و رياست دانشكده مهندسي را بر عهده داشته است.

عبدالباقی قادرزاده در سال ۱۳۸۳ مدرک کارشناسی خود را در رشته علوم کامپیوتر از دانشگاه تبریز و در سال ۱۳۸۶ مدرک کارشناسی ارشد خود را در رشته مهندسی فناوری اطلاعات ، طراحی و تولید نرم افزار از دانشگاه علم و صنعت ایران دریافت کرد. در سال ۱۳۸۷ بهعنوان هیأت علمی ماده ۱ در دانشگاه علوم‌پزشکی کردستان مشغول بهکار گردید. از سال ۱۳۹۰ بهعنوان هیأت علمی در دانشگاه آزاد اسلامی واحد سنندج شروع به فعالیت کرد و از سال ۱۳۹۱ دوره دکتری مهندسی کامپیوتر سیستمهای نرمافزاری را در دانشگاه آزاد اسلامی واحد علوم و تحقیقات تهران آغاز و در ۱۳۹۶ فارغ‌التحصیل گردید. زمینههای تحقیقاتی ایشان علوم داده، سیستمهای توزیعشده و یادگیری برخط در این شاخهها است.

شارک

عنوان URL للمقالة

انتخاب ویژگی چندبرچسبه با استفاده از راهکار ترکیبی مبتنی بر الگوریتم بهینه‌سازی ازدحام ذرات

رایمگ

الروابط

المراكز ذات الصلة

دعامة

الصفحات الرسمية