خوشه بندی گراف کلونی مورچه انتخاب ویژگی

خوشه بندی گراف کلونی مورچه انتخاب ویژگی – ایران ترجمه – Irantarjomeh

مقالات ترجمه شده آماده گروه کامپیوتر

مقالات ترجمه شده آماده کل گروه های دانشگاهی

مقالات

چگونگی سفارش مقاله

الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.

www.irantarjomeh.com

یکپارچه سازی خوشه بندی گراف با استفاده از فرآیند بهینه سازی کلونی مورچه برای انتخاب ویژگی

چکیده

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

کلمات کلیدی: انتخاب ویژگی، بهینه سازی کلونی مورچه، روش فیلتر، خوشه بندی گراف

خوشه بندی گراف کلونی مورچه انتخاب ویژگی

۱- مقدمه

در خلال سالیان اخیر، با پیشرفت سریع علوم و فناوری، مقدار داده ها به سرعت رشد نموده و بنابراین روش های شناسایی الگو می بایست کار خود را با نمونه هایی که متشکل از هزاران ویژگی می باشند دنبال نمایند. این مسئله که تحت عنوان “نفرین ابعاد” خوانده می شود در بردارنده کاهش بعدیت بانک اطلاعات خواهد بود تا از این طریق قابلیت ردیابی و دنبال نمودن آسان آنها فراهم شود [۷، ۴۵، ۶۱]. روش های کاهش بعدیت فراهم آورنده راهکاری جهت درک بهتر داده ها هستند و سبب ارتقای عملکرد پیش بینی و کاهش زمان محاسباتی در ارتباط با برنامه های کاربردی شناسایی الگو می شوند. به عنوان یک قاعده کلی، برای یک مسئله دسته بندی با D بعد و C کلاس، یک نمونه آموزشی ۱۰ ´ D ´ C حداقلی مورد نیاز خواهد بود [۹]. در عین آنکه این ویژگی از نقطه نظر عملی جهت حاصل آوردن تعداد ضروری نمونه های آموزشی کاربرد ندارد، کاهش ویژگی ها سبب تقلیل اندازه نمونه آموزشی مورد نیاز شده و در نتیجه به ما در زمینه ارتقای عملکرد کلی الگوریتم دسته بندی کمک می نماید.

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

در خلال سالیان اخیر روش های تکاملی و ازدحام مبنای بسیاری همانند الگوریتم ژنتیک (GA) [8، ۵۶]، بهینه سازی کلونی مورچه ها (ACO) [1، ۱۱، ۱۷، ۵۴، ۶۰]، بهینه سازی ازدحام ذرات (PSO) [27، ۵۸] و کلونی زنبور عسل مصنوعی (ABC) [36، ۴۴] و الگوریتم جستجوی هماهنگ یا هارمونی (HSA) [62] جهت حل مشکلات انتخاب ویژگی ارائه شده اند. در بین روش های هوشمند مبنای ازدحام، ACO به صورت موفقی در ارتباط با تحقیقات انتخاب ویژگی بکار گرفته شده است. این الگوریتم به عنوان یک الگوریتم فرا ابتکاری جهت حل مسایل بهینه سازی ترکیبی سخت به شمار می آید [۳۵]. این الگوریتم به طور موفقی برای حل تعداد زیادی از مشکلات ترکیبی نظیر مسیریابی وسایل نقلیه یا خودرو [۴۷]َ، رنگ آمیزی گراف [۱۶]، و شبکه ارتباطاتی [۶۸] بکار گرفته شده اند. الگوریتم ACO به عنوان یک سیستم چند عامله به شمار آمده و دارای برخی از مزیت های خاص نظیر بازخورد مثبت، کاربرد حافظه طولانی مدت توزیعی، پیاده سازی طبیعی به یک روش موازی، توابع مشابه با موارد مرتبط با شماتیک فراگیری، و یک قابلیت جستجوی محلی و کلی مناسب به واسطه اجزای تصادفی و حریصانه در این الگوریتم. به علاوه، این الگوریتم به طور موفقی برای مسئله انتخاب ویژگی نیز بکار گرفته شده است [۱، ۱۱، ۱۲، ۱۷، ۲۶، ۳۱، ۳۲، ۳۷، ۵۲، ۵۴، ۶۷]. با وجود آنکه این الگوریتم به عنوان یک رویکرد کارآمد جهت یافتن زیر مجموعه های ویژگی به صورت بهینه (یا نزدیک بهینه) معرفی شده است، در عین حال الگوریتم مربوطه از برخی از کمبودها نیز در رنج می باشد که به شرح ذیل ارائه شده اند:

1. نمایش گراف: در بسیاری از روش های انتخاب ویژگی مبتنی بر ـ ACO فضا به وسیله یک گراف کاملاً متصل نمایش داده شده است [۱۱] که در آن فضای مسئله به وسیله یک گراف جهت دار که صرفاً دارای ۲n قوس می باشد نشان داده شده است که در آن n معرف تعداد ویژگی ها است. در مورد گراف های کاملاً متصل، در هر مرحله (یعنی مرحله t) هر مورچه می بایست قابلیت محاسبه قاعده احتمال برای ویژگی های انتخاب نشده را داشته باشد (یعنی n – t + 1، که در آن n معرف تعداد ویژگی ها است)، که نهایتاً منجر به افزایش پیچیدگی زمانی این الگوریتم خواهد شد. به طور مثال در صورتی که مورچه نیاز به سیر m تعداد از گره ها در گراف داشته باشد، (n)!/(n-m) محاسبه مورد نیاز خواهد بود. بنابراین لازم است تا قابلیت کاهش این محاسبات به وجود آید.

2. فرومون به روزرسانی شده: غالب روش های انتخاب ویژگی ACO ـ مبنا از یک مدل فراگیری در فرآیند جستجوی خود جهت ارزیابی یک زیرمجموعه ویژگی ایجادی استفاده نموده، و بنابراین آنها تحت عنوان مدل بسته بندی یا بسته بند دسته بندی می شوند [۱، ۳۷، ۶۰]. در عین حال، روش های مبتنی بر فرآیند بسته بند یا بسته بندی نیازمند زمان محاسباتی زیادی می باشند، مخصوصاً در بانک های اطلاعاتی که دارای تعداد زیادی از ویژگی ها هستند. از طرف دیگر، تنها در سه مورد به جای مدل یادگیری، برآوردهای تئوریکی اطلاعاتی جهت به روزرسانی فرومون بکار گرفته شده اند [۳۲، ۴۸، ۵۲، ۵۴].

3. …

…

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

خوشه بندی گراف کلونی مورچه انتخاب ویژگی

۲- تحقیقات مرتبط

ایده اصلی در خصوص انتخاب ویژگی،  گزینش یک زیر مجموعه از ویژگی های موجود  می باشد و برای این کار اقدام به حذف ویژگی های نامربوطی می شود که از هیچ / یا مقدار اندک اطلاعات قابل پیش بینی، همراه با ویژگی های زاید کاملاً همبسته، برخوردار هستند. جهت یافتن زیر مجموعه ویژگی بهینه لازم است تا قابلیت ارزیابی کلیه زیر مجموعه های محتمل آن ویژگی را داشته باشیم. کل فضای جستجو حاوی تمامی زیر مجموعه های محتمل ویژگی ها می باشد، بدان معنا که اندازه فضای جستجو برابر با ۲ⁿ است، در حالی که n بعدیت این مسئله به شمار می آید (یعنی تعداد ویژگی های اولیه). بنابراین، مسئله یافتن زیر مجموعه ویژگی بهینه به عنوان یک مسئله NP ـ سخت به شمار می آید [۱۰، ۱۹]. از آنجایی که ارزیابی کل زیر مجموعه ویژگی از نقطه نظر محاسباتی بسیار پرهزینه می باشد، و به علاوه زمانبر نیز است و همچنین برای مجموعه های ویژگی دارای اندازه محتمل غیرعملی نیز می باشد، راه حل نهایی را می بایست در محدوده زمانی محاسباتی محتمل و با یک رابطه متقابل منطقی بین کیفیت راه حل یافته شده و هزینه فضای زمانی در نظر گرفت. بنابراین، بسیاری از الگوریتم های انتخاب ویژگی شامل استراتژی های جستجوی تصادفی یا ابتکاری جهت یافتن زیر مجموعه های بهینه یا نزدیک بهینه از ویژگی ها به منظور کاهش زمان محاسباتی می باشند. انتخاب ویژگی به عنوان یک مسئله جستجوی اصلی در فراگیری ماشینی به شمار می آید و از تاریخچه طولانی از دهه ۱۹۷۰ برخوردار است و در این زمینه شاهد تلاش های زیادی جهت بررسی روش های انتخاب ویژگی می باشیم [۱۰، ۵۱].

خوشه بندی گراف کلونی مورچه انتخاب ویژگی

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

در این بخش یک روش جدید تشریح می شود که به صورت مؤثر و کارآمد قابلیت تعامل با هر دو مورد ویژگی های نامرتبط و زاید را خواهد داشت. این روش پیشنهادی متشکل از سه مرحله می باشد: (۱) نمایش گراف فضای مسئله، (۲) خوشه بندی ویژگی و (۳) جستجو برای زیر مجموعه ویژگی بهینه بر مبنای ACO. در اولین مرحله، مجموعه ویژگی به عنوان یک گرافی معرفی می شود که در آن هر گره در گراف معرف یک ویژگی می باشد و هر وزن یال نیز معرف مشابهت مقدار بین ویژگی های متناظر آن به شمار می آید. در مرحله دوم، این ویژگی ها به چندین خوشه با استفاده از یک روش تشخیص جامعه تقسیم می گردند [۵۹]. هدف خوشه بندی ویژگی ها گروه بندی بیشترین ویژگی های همبسته در یک خوشه می باشد. در مرحله سوم، یک الگوریتم انتخاب ویژگی جدید بر مبنای استراتژی جستجوی ACO جهت انتخاب زیر مجموعه ویژگی نهایی پیشنهاد می شود. شکل ۱ نشان دهنده طرح کلی روش سه مرحله ای پیشنهادی است. در شکل ۱ (الف) فضای ویژگی به عنوان گراف وزن داری معرفی می شود که در آن گره ها خود مشخص کننده ویژگی ها هستند و همچنین یال ها معرف مشابهت مقدار بین دو ویژگی متناظر خواهند بود. پس از بکارگیری خوشه بندی گراف، ویژگی مربوطه به سه خوشه گروه بندی می شود. شکل ۱ (ب) نشان دهنده نتیجه خوشه بندی برای این گراف می باشد. …

۳ـ۱٫ نمایش گراف

به طور کلی، جهت بکارگیری الگوریتم ACO، فضای جستجوی مسئله انتخاب ویژگی را می بایست به وسیله یک گراف بدون جهت کاملاً متصل نشان داد. بنابراین، ما سعی در مدل سازی مسئله انتخاب ویژگی با استفاده از یک شاخص تئوریکی گراف خواهیم نمود. تاکنون، مجموعه ویژگی به گراف معادل G = (F, E, w_F نگاشت شده است، که در آن F = {F₁, F₂, …, F_n} به عنوان مجموعه از ویژگی های اصلی، E = {(F_i, F_j) : F_i, F_j, Î F} به عنوان یال های گراف و w_ij به عنوان مشابهت بین دو ویژگی F_i و F_j متصل شده به وسیله یال (F_i, F_j) به شمار می آیند. روش های مرتبط با برآورد مقادیر مشابهت (یعنی وزن های یال) به صورت حیاتی مشخص کننده عملکرد الگوریتم انتخاب ویژگی گراف ـ مبنای متعاقب می باشند. در اینجا با برآوردهای مشابهت مختلفی روبرو می باشیم که می توان از آنها جهت مشخص سازی وزن های یال استفاده نمود و بنابراین لازم به ذکر است که روش های مختلف منجر به حاصل آوردن نتایج متفاوتی می شوند. بنابراین، ما می بایست به دقت قابلیت انتخاب مناسبترین برآورد را داشته باشیم. به طور کلی، فاصله اقلیدوسی و ضریب همبستگی پیرسون هر دو به طور گسترده ای به عنوان برآورد مشابهت استفاده می شوند. در این تحقیق، ضریب همبستگی پیرسون جهت برآورد مقدار مشابهت بین ویژگی های مختلف یک مجموعه آموزشی مشخص شده بکار گرفته شده است. همبستگی بین دو ویژگی F_i و F_j به شرح ذیل تعریف می گردد:

۳ـ۲٫ خوشه بندی ویژگی

ایده اصلی در ارتباط با خوشه بندی ویژگی گروه بندی ویژگی های اصلی به چندین خوشه بر حسب مقادیر مشابهت بین ویژگی ها می باشد. بنابراین، ویژگی های یک خوشه مشابه با یکدیگر تلقی می شوند. غالب روش های خوشه بندی ویژگی موجود از برخی از کمبودها در رنج هستند [۳۰]. اولین مورد، معرف تعداد مطلوب خوشه ها است، پارامتر k، را می بایست در این رابطه مشخص ساخت. به طور کلی، تعریف تعداد مناسب خوشه ها نیازمند آزمایشات خسته کننده و روش آزمون و خطا دارد. دوماً، توزیع داده ها در خوشه به عنوان یک عامل مهم به شمار آمده و روش های موجود قابلیت ملاحظه واریانس خوشه های اصلی در محاسبه مشابهت را نخواهند داشت. سوماً، کلیه ویژگی ها در خوشه دارای مقدار مشابهی از تعامل با ویژگی استخراجی حاصله می باشند. جهت تعامل با این مسایل در مقاله جاری، یک روش تشخیص اجتماع برای خوشه ویژگی ها بکار گرفته خواهد شد.

۳ـ۳٫ استراتژی جستجوی ACO ـ مبنا

در این زیر بخش یک استراتژی جستجوی ACO ـ مبنای جدید جهت انتخاب یک زیر مجموعه ویژگی از یک گراف خوشه بندی شده ارائه می شود. این الگوریتم متشکل از چندین رویه تکرار می باشد. قبل از آغاز تکرارها، مقدار فرومون تخصیص یافته برای هر گره به مقدار ثابت g تثبیت می شوند. به علاوه، توان تشخیص ویژگی F_i با استفاده از رتبه فیشر به شرح ذیل ارزیابی می گردد:

۳ـ۳ـ۱٫ قانون تصمیم احتمالی

در ACO یک قانون تصمیم احتمالی، مشخص کننده احتمال انتخاب گره ها، به وسیله ترکیب مطلوبیت ابتکاری و مقادیر چگالی فرومون گره ها طراحی می شود. در روش پیشنهادی، هر مورچه اقدام به عبور از گراف با استفاده از هر دو قاعده گذار حالت حریصانه و احتمالی خواهد نمود. در روش حریصانه، k اُمین مورچه اقدام به انتخاب ویژگی بعدی F_j نموده و از این طریق فرمول ذیل اعمال می شود:

۳ـ۳ـ۲٫ قاعده به روزرسانی فرومون

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

۳ـ۴٫ تحلیل پیچیدگی

در اولین مرحله روش پیشنهادی جهت ارائه این گراف، لازم است تا قابلیت محاسبه مقادیر مشابهت بین هر دو ویژگی وجود داشته باشد، به گونه ای که پیچیدگی زمانی این مرحله برابر با O(n²p) تلقی گردیده و در آن n به عنوان تعداد ویژگی های اصلی و p معرف تعداد الگوها باشد. به علاوه، در مرحله دوم، الگوریتم تشخیص جامعه لوواین جهت گروه بندی ویژگی ها به چندین خوشه بکار گرفته شده است و بر این مبنا پیچیدگی زمانی این الگوریتم برابر با O(n log n) است. به علاوه، در مرحله سوم، در ابتدا، مقادیر ارتباط این ویژگی ها با استفاده از برآورد امتیاز فیشر ارزیابی شده است در حالی که پیچیدگی زمانی برابر با O(ncp) بوده است در حالی که c تعداد کلاس ها منظور شده است. متعاقباً یک استراتژی جستجوی مبتنی بر کلونی مورچه خاص جهت انتخاب ویژگی های نهایی بکار گرفته می شود. بر مبنای این استراتژی، هر مورچه فرآیند جستجوی فضای راه حل از نقاط مختلف را آغاز می نماید. این فرآیند جستجو برای تعدادی از چرخه های تکرار اعمال خواهد شد (یعنی I)…

خوشه بندی گراف کلونی مورچه انتخاب ویژگی

۴- نتایج آزمایشی

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

۴ـ۱٫ مجموعه های اطلاعاتی

در این مقاله، چندین مجموعه اطلاعاتی با خواص مختلف جهت انجام آزمایشات و به منظور نشان دادن کارآمدی روش پیشنهادی ارائه شده اند. این مجموعه های اطلاعاتی شامل Wine، Hepatitis، WDBC، Ionosphere، Spambase، Sonar، Arrhythmia، Madelon، Colon و Arcene می باشند. ویژگی اصلی این ده مجموعه اطلاعاتی در جدول ۲ خلاصه شده است. توصیفات هر کدام از این موارد به استثنای Madelon و Arcene در مخزن فراگیری ماشینی ایرفین دانشگاه کالیفرنیا موجود است [۵]. به علاوه، مجموعه های اطلاعاتی Madelon و Arcene از NIPS2003 جمع آوری شده اند که در وب سایت مربوطه در دسترس قرار دارند و برخی از این ویژگی ها شامل مواردی با مقادیر مفقوده می باشند. بنابراین، جهت تعامل با این نوع از مقادیر در آزمایشات مربوطه، هر مقدار مفقوده جایگزین میانگین داده های موجود در ارتباط با ویژگی های خاص شده است [۵۵]. به علاوه، در بسیاری از موقعیت های عملی، طراح با یکسری از ویژگی ها روبرو می باشد که مقادیر آنها در محدوده های مختلفی جای می گیرند. بنابراین، ویژگی های که مرتبط با محدوده های بزرگ مقادیر هستند غالبا دارای اشراف بر موارد کم مقدار می باشند. جهت فایق آمدن بر چنین مشکلی، یک روش به هنجارسازی یا نرمال سازی غیر خطی تحت عنوان مقیاس بندی سافتمکس (softmax) [55] به منظور مقیاس بندی این مجموعه های اطلاعاتی ارائه شه است.

۴ـ۲٫ کلاسیفایرهای کاربردی

جهت نشان دادن کلیت روش پیشنهادی، ظرفیت پیش بینی دسته بندی ویژگی های انتخابی با استفاده از چندین کلاسیفایر کلاسیک کاملاً شناخته شده مورد آزمایش قرار گرفت، شامل ماشین بردار پشتیبان (SVM)، درخت تصمیم (DT)، بیسی ساده (NB)، نزدیک ترین همسایه یا گره مجاور ـ k (kNN) و جنگل تصادفی (RF). این کلاسیفایرها به عنوان تأثیرگذارترین الگوریتم هایی به شمار می آیند که به طور گسترده ای در فرآیند داده کاوی اجتماعی بکار گرفته شده اند. به علاوه، Weka (محیط Waikato تحلیل اطلاعات (نرم افزار متعلق به Hall و همکاران [۲۰]، که به عنوان الگوریتم های فراگیری ماشینی جمع آوری شده برای وظایف داده کاوی به شمار می آیند، به منظور معیارسنجی آزمایشات و ارزیابی ویژگی های انتخابی بکار گرفته شد. در این تحقیق، SMO، J48 (پیاده سازی الگوریتم C4.5)، بیسی ساده، IBk و RandomForest همراه با رویه پیاده سازی WEKA متعلق به SVM، DT، NB، kNN و RF نیز به ترتیب بکار گرفته شدند. به علاوه، پارامترهای کلاسیفایرهای ذکر شده برای هر آزمایش به مقادیر پیش فرض نرم افزار Weka تنظیم گردیدند.

۴ـ۳٫ پارامترهای خاص کاربران

چندین پارامتر خاص کاربران در روش های آزمایشی بکار گرفته شده و بنابراین مقادیر متناظر آنها می بایست به وسیله کاربران مشخص شوند. توجه شود که برخی از این پارامترها برای روش پیشنهادی مشخص نشده اند، و به طور کلی برای غالب روش های انتخاب ویژگی ACO ـ مبنا مورد نیاز هستند. این پارامترها پس از تعدادی از اجراهای اولیه انتخاب گردیدند، و بنابراین به عنوان موارد بهینه تلقی نمی شوند. از آنجایی که پارامترهای a و b در روش های ACO ـ مبنا به صورت ترتیبی اهمیت نسبی فرومون و اطلاعات ابتکاری را در نظر گرفته اند، انتخاب مناسب این پارامترها جهت حاصل آوردن یک تعادل کارآمد بین اکتشاف و بهره برداری ضروری می باشد. جدول ۳ نشان دهنده پارامترها و مقادیر متناظر آنها می باشد.

۴ـ۴٫ نتایج

در این زیر بخش، ما ارائه دهنده نتایج تجربی بر حسب دقت دسته بندی، تعداد ویژگی های انتخابی و زمان اجرا می باشیم. به علاوه، برای بررسی اهمیت آماری نتایج، ما یک آزمون فریدمن غیرپارامتری [۱۸] را به منظور مقایسه آماری روش های مختلف بر روی مجموعه های اطلاعاتی متعدد مورد آزمایش قرار دادیم.

۴ـ۴ـ۱٫ دقت دسته بندی

در این آزمایشات، در ابتدا عملکرد روش پیشنهادی با توجه به کلاسیفایرهای مختلف مورد ارزیابی قرار گرفت. جداول ۴ـ۸ نشان دهنده میانگین دقت دسته بندی (بر حسب درصد) روش پیشنهادی (یعنی GCACO) با ده اجرای مستقل با استفاده از کلاسیفایرهای SVM، DT، NB، kNN و RF به ترتیب می باشند. بهترین نتیجه هر مجموعه اطلاعاتی به صورت ضخیم نشان داده شده است و تعداد پرانتزها معرف رتبه الگوریتم ها می باشد. به علاوه، نتایج با نتایج حاصله روش های فیلتر شامل L-Score، F-Score، RRFS، mRMR، ReliefF و UFSACO مقایسه شده اند.

۴ـ۴ـ۲٫ تعداد ویژگی های انتخابی

جدول ۹ نشان دهنده تعداد ویژگی های انتخابی روش های انتخاب ویژگی مختلف با توجه به انجام ده مرحله مستقل می باشد. از این نتایج می توان مشاهده نمود که به طور کلی کلیه روش های انتخاب ویژگی قابلیت کاهش معنی دار بعدیت، از طریق انتخاب صرف بخش اندکی از ویژگی های اصلی، را خواهند داشت. به علاوه، نتایج نشان دهنده آن است که GCACO، به طور میانگین، قابلیت انتخاب کمترین تعداد ویژگی ها را دارد. به طور مثال، از نتایج می توان ملاحظه کرد که روش پیشنهادی تعداد میانگین ۱/۲۳ ویژگی را انتخاب نموده است، در حالی که روش های انتخابی ویژگی دیگر به طور میانگین قابلیت انتخاب ۵/۲۸ ویژگی را خواهند داشت.

۴ـ۴ـ۳٫ مقایسه با روش های مبتنی بر دسته بندی

عملکرد روش پیشنهادی با عملکرد روش های انتخاب ویژگی بر مبنای مؤلفه بسته بندی یا بسته بند مقایسه شده اند که شامل HGAFS [38]، ACOFS [37]، و PSOFS [65] در مجموعه های اطلاعاتی مختلف می باشند. جدول ۱۰ گزارش دهنده میانگین دقت دسته بندی در بیش از ۱۰ اجرای مستقل برای روش های HGAFS، ACOFS، PSOFS و GCACO با استفاده از کلاسیفایرهای SVM و NB می باشد. از نتایج می توان مشخص ساخت که روش پیشنهادی حاصل آورنده بالاترین دقت دسته بندی می باشد آن هم به هنگامی که بر روی مجموعه های اطلاعاتی Wine، Hepatitis، Ionosphere، Spambase وMadelon  برای کلاسیفایر NB بکار گرفته شده باشد. به علاوه، روش GCACO به عنوان دومین مورد از بهترین نتایج برای مجموعه های WDBC وArcene  به شمار می آید. در عین حال برای موارد دیگر روش های مبتنی بر بسته بندی بهترین نتایج را در مقایسه با روش پیشنهادی حاصل آورده اند. در نتیجه، از نتایج گزارش شده می توان به این نتیجه گیری رسید که عملکرد کلی روش GCACO قابل قیاس با موارد جدید روش های انتخاب ویژگی سیستم بسته بندی می باشد.

۴ـ۴ـ۴٫ پیچیدگی محاسباتی و مقایسه زمان اجرا

هدف این بخش مقایسه پیچیدگی محاسباتی و زمان اجرای روش های ذکر شده قبلی می باشد. جدول ۱۱ نشان دهنده پیچیدگی محاسباتی روش های انتخابی ویژگی بر مبنای رویه بسته بندی یا بسته بند است. به علاوه، توصیفات مربوط به نمادها نیز در این جدول نشان داده شده است. ذکر این نکته ضروری است که روش های انتخاب ویژگی بر مبنای سیستم دسته بندی نیازمند یک کلاسیفایر (همانند یک مدل فراگیری) جهت ارزیابی زیر مجموعه ویژگی انتخابی در هر بار تکرار می باشند. تاکنون، این روش ها کلاسیفایرهای مختلفی را نظیر DT، NN، kNN، SVM و RF بکار گرفته اند. به طور مثال، HGAFS یک کلاسیفایر NN خاص جهت محاسبه مقدار برازندگی ذرات بکار گرفته شده است. پیچیدگی های محاسباتی این کلاسیفایرها متفاوت از یکدیگر می باشند. بنابراین، در ارتباط با گزارش نمودن پیچیدگی محاسباتی روش های مبتنی بر سیستم بسته بندی (همانند ACOFS، HGAFS و PSOFS) ما به O(classifiere) با توجه به فرمول پیچیدگی محاسباتی متناظر آنها رجوع خواهیم نمود.

۴ـ۴ـ۵٫ نتایج آزمون آماری

در این آزمایشات، یک آزمون مهم آماری تحت عنوان آزمون فریدمن [۱۸] جهت مقایسه متعاقب روش های انتخاب ویژگی ذکر شده با توجه به مجموعه های اطلاعاتی متعدد، و با کلاسیفایر مختلف، برگزیده شد. آزمون فریدمن را می توان جهت مقایسه روش های k با مجموعه های ا طلاعات N از طریق رتبه بندی هر روش بر روی هر مجموعه اطلاعاتی به صورت مجزا بکار گرفت. روشی که قابلیت حاصل آوردن بهترین عملکرد را داشته باشد دارای رتبه ۱ گردیده و بعدی رتبه ۲ و به همین ترتیب رویه ادامه خواهد یافت. ما از آمار SPSS که به وسیله سیستم IBM برای این منظور ارائه شده است[۴۰] استفاده نمودیم. نتایج حاصله نشان دهنده آن است که آزمون فریدمن ارائه دهنده یک مقدار ـ p برابر با ۰۰۰۰۰۸/۰ برای مقادیر دقت دسته بندی کلاسیفایر SVM در جدول ۴ می باشد…

۴ـ۴ـ۶٫ تحلیل حساسیت پارامترها

همانند بسیاری از دیگر روش های انتخاب ویژگی، روش پیشنهادی نیازمند پارامتر w و q می باشد. w به عنوان پارامتر خاص کاربر تلقی می شود که کنترل کننده اندازه زیر مجموعه ویژگی نهایی می باشد. تنظیمات دقیق پارامتر w به طور قابل توجهی بر روی نتایج روش GCACO تأثیرگذار خواهند بود. این پارامتر را می توان به هر مقداری در محدوده [n: 1] تنظیم کرد و همچنان w ´ k می بایست کوچکتر از تعداد ویژگی های اولیه (یعنی w ´ K £ n) باشد. در صورتی که مقدار متناظر آن به یک مقدار بالا تنظیم گردد، بنابراین ویژگی های بسیاری انتخاب گردیده و الگوهای طبیعی در این داده با نویز روبرو گردیده و ویژگی های حشو یا افزونه را می توان با یک احتمال بالا انتخاب نمود. از طرف دیگر، به هنگامی که این پارامتر به یک مقدار کوچک تنظیم گردد، ویژگی های بسیار اندکی انتخاب گردیده و بنابراین، اطلاعات ناکافی برای وظیفه دسته بندی وجود خواهد داشت. به علاوه، به منظور بررسی تعیین مناسب مقادیر پارامتر w، چندین آزمایش جهت مشخص سازی چگونگی تغییر دقت سیستم دسته بندی با مقادیر مختلف این پارامتر انجام شده است.

۴ـ۵٫ مباحث

این زیر بخش به طور مختصر تشریح کننده این موضوع می باشد که چرا عملکرد GCACO بهتر از روش های انتخاب ویژگی دیگر می باشد. سه عامل متمایز وجود دارد که در ارتباط با بهتر بودن GCACO در مقایسه با دیگران مؤثر تلقی می شوند.

1. ویژگی های نامرتبط، همراه با ویژگی های زاید یا حشو، که به طور شدیدی بر روی دقت الگوریتم فراگیری تأثیر می گذارند [۸، ۱۰، ۳۴]. بنابراین، انتخاب ویژگی می بایست قابلیت شناسایی و حذف ویژگی های نامرتبط و زاید را تا حد ممکن داشته باشد. از بین بسیاری از روش های انتخاب ویژگی، برخی از آنها به طور کارآمد قابلیت حذف ویژگی های کارآمد را دارند اما نمی توانند ویژگی های زاید را به خوبی حذف کنند. در روش های یک متغیره (همانند L-Score، F-Score و RelifF) ارتباط یک ویژگی به صورت واحد برآورد شده و وابستگی محتمل بین ویژگی ها در پروسه انتخاب ویژگی نادیده انگاشته می شود. بنابراین، این روش ها قابلیت حذف ویژگی های زاید به صورت دقیق را ندارند. از طرف دیگر، برخی از روش های انتخاب ویژگی چند متغیره صرفاً اقدام به حذف ویژگی های زاید می نمایند. به طور مثال، هدف اصلی روش UFSACO انتخاب یک زیر مجموعه ویژگی ها با حداقل موارد زاید می باشد و بنابراین هیچ گونه تضمینی جهت انتخاب مجموعه ویژگی بهینه وجود ندارد. دلیل این امر به واسطه این حقیقت است که ویژگی های انتخابی ممکن است تشکیل دهنده بهترین مجموعه شاخص نباشند، با این حال آنها کاملاً با یکدیگر نامشابه هستند. تا اینجا، ما نسبت به توسعه یک روش نوین اقدام نمودیم که به صورت کارآمد و مؤثری می تواند ویژگی های غیرمرتبط و زاید را در نظر بگیرد. در روش پیشنهادی هر مورچه ویژگی هایی را با مشابهت حداقلی با موارد انتخاب شده قبلی برمی گزیند، در حالی که قابلیت به حداکثررسانی وابستگی به کلاس هدف را دارد. از طریق بکارگیری این نوع از قواعد انتخاب، احتمال کمتری برای گزینش ویژگی های نامرتبط با زاید وجود دارد.

2. …

خوشه بندی گراف کلونی مورچه انتخاب ویژگی

۵- نتیجه گیری

انتخاب ویژگی نقش مهمی را در دنیای فراگیری ماشینی بازی می نماید و مخصوصاً این نقش در ارتباط با وظیفه دسته بندی بسیار مهم تلقی می شود. به علاوه، هزینه محاسباتی تقلیل یافته و از طرف دیگر این مدل از داده های ساده شده به وجود آمده و بنابراین توانایی ارتقای قابلیت های کلی کلاسیفایرها را خواهد داشت. در این مقاله، یک روش انتخاب ویژگی جدید از طریق یکپارچه سازی مفهوم خوشه بندی گراف با توجه به فرآیند جستجو و بهینه سازی کلونی مورچه ارائه می شود.  روش پیشنهادی در سه  مرحله کار می کند: در مرحله اول، فضای مشکل به عنوان یک گراف از طریق ملاحظه کل مجموعه ویژگی به عنوان مجموعه رأس مشخص گردیده و دارای مشابهت ویژگی با وزن یال متناظر می باشد. در مرحله دوم، ویژگی ها به چندین خوشه از طریق بکارگیری یک روش تشخیص جامعه تقسیم می گردند. در نهایت، در مرحله سوم، ما از یک الگوریتم انتخاب ویژگی ACO ـ مبنا استفاده می نماییم که با استفاده از بکارگیری خوشه های ویژگی توسعه یافته است. روش پیشنهادی قابلیت تعامل با ویژگی های نامرتبط و موارد زاید را خواهد داشت. …