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

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

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

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

مقالات رایگان

مطالعه 20 الی 100% رایگان مقالات ترجمه شده

1- قابلیت مطالعه رایگان 20 الی 100 درصدی مقالات 2- قابلیت سفارش فایل های این ترجمه با قیمتی مناسب مشتمل بر 3 فایل: pdf انگیسی و فارسی مقاله همراه با msword فارسی -- تذکر: برای استفاده گسترده تر کاربران گرامی از مقالات آماده ترجمه شده، قیمت خرید این مقالات بسیار کمتر از قیمت سفارش ترجمه می باشد.  

چگونگی سفارش

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

www.irantarjomeh.com

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

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

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

چکیده

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

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

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

1- مقدمه

در خلال سالیان اخیر، با پیشرفت سریع علوم و فناوری، مقدار داده ها به سرعت رشد نموده و بنابراین روش های شناسایی الگو می بایست کار خود را با نمونه هایی که متشکل از هزاران ویژگی می باشند دنبال نمایند. این مسئله که تحت عنوان “نفرین ابعاد” خوانده می شود در بردارنده کاهش بعدیت بانک اطلاعات خواهد بود تا از این طریق قابلیت ردیابی و دنبال نمودن آسان آنها فراهم شود [7، 45، 61]. روش های کاهش بعدیت فراهم آورنده راهکاری جهت درک بهتر داده ها هستند و سبب ارتقای عملکرد پیش بینی و کاهش زمان محاسباتی در ارتباط با برنامه های کاربردی شناسایی الگو می شوند. به عنوان یک قاعده کلی، برای یک مسئله دسته بندی با D بعد و C کلاس، یک نمونه آموزشی 10 ´ D ´ C حداقلی مورد نیاز خواهد بود [9]. در عین آنکه این ویژگی از نقطه نظر عملی جهت حاصل آوردن تعداد ضروری نمونه های آموزشی کاربرد ندارد، کاهش ویژگی ها سبب تقلیل اندازه نمونه آموزشی مورد نیاز شده و در نتیجه به ما در زمینه ارتقای عملکرد کلی الگوریتم دسته بندی کمک می نماید.

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

در خلال سالیان اخیر روش های تکاملی و ازدحام مبنای بسیاری همانند الگوریتم ژنتیک (GA) [8، 56]، بهینه سازی کلونی مورچه ها (ACO) [1، 11، 17، 54، 60]، بهینه سازی ازدحام ذرات (PSO) [27، 58] و کلونی زنبور عسل مصنوعی (ABC) [36، 44] و الگوریتم جستجوی هماهنگ یا هارمونی (HSA) [62] جهت حل مشکلات انتخاب ویژگی ارائه شده اند. در بین روش های هوشمند مبنای ازدحام، ACO به صورت موفقی در ارتباط با تحقیقات انتخاب ویژگی بکار گرفته شده است. این الگوریتم به عنوان یک الگوریتم فرا ابتکاری جهت حل مسایل بهینه سازی ترکیبی سخت به شمار می آید [35]. این الگوریتم به طور موفقی برای حل تعداد زیادی از مشکلات ترکیبی نظیر مسیریابی وسایل نقلیه یا خودرو [47]َ، رنگ آمیزی گراف [16]، و شبکه ارتباطاتی [68] بکار گرفته شده اند. الگوریتم ACO به عنوان یک سیستم چند عامله به شمار آمده و دارای برخی از مزیت های خاص نظیر بازخورد مثبت، کاربرد حافظه طولانی مدت توزیعی، پیاده سازی طبیعی به یک روش موازی، توابع مشابه با موارد مرتبط با شماتیک فراگیری، و یک قابلیت جستجوی محلی و کلی مناسب به واسطه اجزای تصادفی و حریصانه در این الگوریتم. به علاوه، این الگوریتم به طور موفقی برای مسئله انتخاب ویژگی نیز بکار گرفته شده است [1، 11، 12، 17، 26، 31، 32، 37، 52، 54، 67]. با وجود آنکه این الگوریتم به عنوان یک رویکرد کارآمد جهت یافتن زیر مجموعه های ویژگی به صورت بهینه (یا نزدیک بهینه) معرفی شده است، در عین حال الگوریتم مربوطه از برخی از کمبودها نیز در رنج می باشد که به شرح ذیل ارائه شده اند:

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

2. فرومون به روزرسانی شده: غالب روش های انتخاب ویژگی ACO ـ مبنا از یک مدل فراگیری در فرآیند جستجوی خود جهت ارزیابی یک زیرمجموعه ویژگی ایجادی استفاده نموده، و بنابراین آنها تحت عنوان مدل بسته بندی یا بسته بند دسته بندی می شوند [1، 37، 60]. در عین حال، روش های مبتنی بر فرآیند بسته بند یا بسته بندی نیازمند زمان محاسباتی زیادی می باشند، مخصوصاً در بانک های اطلاعاتی که دارای تعداد زیادی از ویژگی ها هستند. از طرف دیگر، تنها در سه مورد به جای مدل یادگیری، برآوردهای تئوریکی اطلاعاتی جهت به روزرسانی فرومون بکار گرفته شده اند [32، 48، 52، 54].

3. انتخاب ویژگی های اضافه: در غالب روش های انتخاب ویژگی ACO ـ مبنا، وابستگی احتمالی بین ویژگی ها در فرآیند جستجو نادیده انگاشته می شود [1، 11، 60]. این روش ها در نظر می گیرند که ویژگی ها از نقطه نظر شرطی مستقل به شمار آمده و بنابراین، به هنگامی که یک مورچه اقدام به انتخاب ویژگی بعدی می نماید، وابستگی این ویژگی بر مورد قبلاً انتخاب شده در محاسبات نادیده انگاشته می شود. بنابراین، زیر مجموعه ایجادی ممکن است حاوی ویژگی های زیادی باشد، که خود سبب کاهش عملکرد کلاسیفایر خواهد شد.

4. اندازه نهایی زیر مجموعه: تعداد ویژگی های انتخابی که مشخص کننده طول مسیر سیر مورچه ها می باشد، خود تحمیل کننده چالش دیگری بر روی روش های ACO ـ مبنا است. در غالب روش های انتخاب ویژگی ACO ـ مبنا، تعداد گره های سیر شده می بایست قبل از آنکه مورچه فرآیند جستجوی خود را آغاز نماید به صورت از قبل تعیین شده باشند [48، 52، 54]. به علاوه، دقت این روش ها منوط به بهینگی تعریف اندازه زیرمجموعه ویژگی خواهد بود.

جهت فایق آمدن بر کمبودهای ذکر شده، در این مقاله، ما نسبت به ارائه یک روش انتخاب ویژگی فیلتر مبنای جدید بر حسب الگوریتم ACO اقدام می نماییم. این روش سعی در انتخاب ویژگی های با کیفیت در یک محدوده زمانی منطقی می کند. الگوریتم پیشنهادی که تحت عنوان روش انتخاب ویژگی ACO بر مبنای خوشه بندی گراف می باشد، و به صورت اختصار GCACO خوانده می شود، در سه مرحله کار می کند. در مرحله اول، فضای مسئله به عنوان یک گراف ارائه می گردد که در آن هر گره یک ویژگی خاص را ارائه داده و وزن های یال ها بین ویژگی ها به صورت مشابه می باشند. در مرحله دوم، ویژگی ها به چندین خوشه از طریق بکارگیری الگوریتم تشخیص جامعه کارآمد تقسیم می شود [59]. در نهایت، در مرحله سوم، یک استراتژی جستجوی ACO ـ مبنای جدید برای انتخاب زیر مجموعه ویژگی نهایی پیشنهاد می گردد. در این استراتژی، یک مورچه که بر روی یک خوشه انتخاب شده تصادفی قرار گرفته است، در هر مرحله، تصمیم بر انتخاب موقعیت بعدی خود در خوشه جاری نموده و یا آنکه تصمیم بر حرکت به خوشه دیگری می گیرد. در مورد باقی ماندن در همان خوشه، مقادیر احتمال صرفاً برای ویژگی های آن خوشه محاسبه خواهد شد. در مقابل برای موارد دیگر، مقادیر احتمال برای ویژگی های خوشه انتخاب بعدی محاسبه می شوند. این فرآیند تا زمانی ادامه خواهد یافت که کلیه خوشه ها بازدید شده باشند. بنابراین، تعداد ویژگی هایی که به وسیله هر مورچه در هر چرخه انتخاب گردیده، و همچنین زیر مجموعه ویژگی نهایی را می توان به صورت اتوماتیک بر مبنای تعداد خوشه های موجود در فضای مسئله مشخص ساخت.

این رویکرد کاملاً متفاوت از رویکردهایی می باشد که اقدام به بررسی طرح های موجود [48، 52، 54] نموده اند، آن هم زمانی که اندازه زیر مجموعه ایجادی به وسیله یک عدد ثابت مشخص می گردد. به علاوه، هدف کاربرد شاخص های مبتنی بر جامعه در خصوص فضای مسئله گروه بندی ویژگی های کاملاً همبسته در همان خوشه می باشد. بنابراین، فرآیند جستجوی ACO ـ مبنا به گونه ای کنترل و هدایت می شود که تعداد تقریباً کمتری از ویژگی های همبسته با یک نسبت بالا با توجه به ویژگی های همبسته تر به تکرارهای متوالی مرتبط تزریق شوند. به علاوه، مشابهت بین ویژگی ها در محاسبه ارتباط ویژگی مدنظر قرار می گیرد، که در آن قابلیت به حداقل رسانی موارد تکراری یا زاید بین ویژگی های انتخابی وجود خواهد داشت. بنابراین، استراتژی خوشه مبنای روش پیشنهادی از احتمال زیادی در خصوص شناسایی یک زیرمجموعه مفید و ویژگی های مستقل آن برخوردار است. به علاوه، خوشه بندی ویژگی ها در فضای مسئله منجر به کاهش پیچیدگی زمانی مقادیر احتمال خواهد شد چرا که به هنگامی که یک مورچه بر یک خوشه مشخص شده قرار می گیرد، مقدار احتمال صرفاً برای ویژگی های موجود در آن خوشه محاسبه خواهد شد. به علاوه، بر خلاف غالب روش های انتخاب ویژگی ACO ـ مبنای موجود، که از الگوریتم فراگیری یا یادگیری [1، 11، 37] جهت ارزیابی زیرمجموعه های ایجادی استفاده می نمایند، در این مقاله، یک زیر مجموعه ویژگی به وسیله یک ماتریس شاخص تفکیک پذیری بدون کاربرد هر گونه روش فراگیری ارزیابی می شود. بنابراین، روش پیشنهادی را می توان به عنوان یک رویکرد فیلتر مبنا دسته بندی کرد و از اینرو این مورد از نقطه نظر محاسباتی برای بانک های اطلاعاتی دارای ابعاد بزرگ کارآمد تلقی می گردد.

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

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

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

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

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

در این بخش یک روش جدید تشریح می شود که به صورت مؤثر و کارآمد قابلیت تعامل با هر دو مورد ویژگی های نامرتبط و زاید را خواهد داشت. این روش پیشنهادی متشکل از سه مرحله می باشد: (1) نمایش گراف فضای مسئله، (2) خوشه بندی ویژگی و (3) جستجو برای زیر مجموعه ویژگی بهینه بر مبنای ACO. در اولین مرحله، مجموعه ویژگی به عنوان یک گرافی معرفی می شود که در آن هر گره در گراف معرف یک ویژگی می باشد و هر وزن یال نیز معرف مشابهت مقدار بین ویژگی های متناظر آن به شمار می آید. در مرحله دوم، این ویژگی ها به چندین خوشه با استفاده از یک روش تشخیص جامعه تقسیم می گردند [59]. هدف خوشه بندی ویژگی ها گروه بندی بیشترین ویژگی های همبسته در یک خوشه می باشد. در مرحله سوم، یک الگوریتم انتخاب ویژگی جدید بر مبنای استراتژی جستجوی ACO جهت انتخاب زیر مجموعه ویژگی نهایی پیشنهاد می شود. شکل 1 نشان دهنده طرح کلی روش سه مرحله ای پیشنهادی است. در شکل 1 (الف) فضای ویژگی به عنوان گراف وزن داری معرفی می شود که در آن گره ها خود مشخص کننده ویژگی ها هستند و همچنین یال ها معرف مشابهت مقدار بین دو ویژگی متناظر خواهند بود. پس از بکارگیری خوشه بندی گراف، ویژگی مربوطه به سه خوشه گروه بندی می شود. شکل 1 (ب) نشان دهنده نتیجه خوشه بندی برای این گراف می باشد. در نهایت شکل 1 (ج) نشان دهنده جستجوی مورچه ها برای زیر مجموعه ویژگی بهینه در گروه های مختلف ویژگی ها می باشد. به طور مثال، همانگونه که می توان از شکل 1 (ج) مشاهده نموده مورچه کار خود را از خوشه 1 آغاز نموده و ویژگی F₁ را از این خوشه انتخاب می کند. ذکر این نکته ضروری است که این ویژگی ها در چنین خوشه ای بر مبنای مقادیر احتمال آنها انتخاب می شوند که قابلیت حاصل آوردن آنها از طریق بکارگیری برآورد رتبه فیشر و بررسی مشابهت ویژگی های انتخابی قبلی وجود خواهد داشت. بنابراین در مرحله بعدی، مورچه دارای دو انتخاب خواهد بود: باقی ماندن در همان خوشه یا رفتن به خوشه دیگر. در مورد باقی ماندن در همان خوشه، مورچه مربوطه باقی ماندن را بر حسب مقادیر احتمال مرتبط بر می گزیند. از طرف دیگر به هنگامی که مورچه خواستار حرکت به خوشه دیگر باشد، ویژگی بعدی در این خوشه انتخاب خواهد شد. چنین موردی را می توان از شکل 1 (ج) مشاهده نمود که بر مبنای آن مورچه به خوشه 2 حرکت نموده و اقدام به انتخاب ویژگی F₆ از این خوشه می نماید. به علاوه، در مرحله سوم، مورچه سعی در انتخاب موقعیت بعدی در خوشه جاری می نماید (یعنی خوشه 2) و متعاقباً ویژگی F₅ را ا نتخاب می کند. بعداً در مرحله چهارم ویژگی F₈ از خوشه سه انتخاب می شود. در نهایت، کلیه خوشه ها طی شده و مورچه اقدام به ایجاد زیر مجموعه ویژگی (یعنی {F₁, F₆, F₅, F₈}} ) نموده است. زیر مجموعه حاصله با استفاده از روش ماتریس شاخص تفکیک پذیری مورد ارزیابی قرار می گیرد و هیچ نیازی برای مدل های یادگیری وجود نخواهد داشت. جزئیات بیشتر در زیر بخش های متناظر آن مورد بررسی قرار خواهند گرفت.

3ـ1. نمایش گراف

به طور کلی، جهت بکارگیری الگوریتم 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 به شرح ذیل تعریف می گردد:

3ـ2. خوشه بندی ویژگی

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

3ـ3. استراتژی جستجوی ACO ـ مبنا

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

3ـ3ـ1. قانون تصمیم احتمالی

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

3ـ3ـ2. قاعده به روزرسانی فرومون

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

3ـ4. تحلیل پیچیدگی

در اولین مرحله روش پیشنهادی جهت ارائه این گراف، لازم است تا قابلیت محاسبه مقادیر مشابهت بین هر دو ویژگی وجود داشته باشد، به گونه ای که پیچیدگی زمانی این مرحله برابر با O(n²p) تلقی گردیده و در آن n به عنوان تعداد ویژگی های اصلی و p معرف تعداد الگوها باشد. به علاوه، در مرحله دوم، الگوریتم تشخیص جامعه لوواین جهت گروه بندی ویژگی ها به چندین خوشه بکار گرفته شده است و بر این مبنا پیچیدگی زمانی این الگوریتم برابر با O(n log n) است. به علاوه، در مرحله سوم، در ابتدا، مقادیر ارتباط این ویژگی ها با استفاده از برآورد امتیاز فیشر ارزیابی شده است در حالی که پیچیدگی زمانی برابر با O(ncp) بوده است در حالی که c تعداد کلاس ها منظور شده است. متعاقباً یک استراتژی جستجوی مبتنی بر کلونی مورچه خاص جهت انتخاب ویژگی های نهایی بکار گرفته می شود. بر مبنای این استراتژی، هر مورچه فرآیند جستجوی فضای راه حل از نقاط مختلف را آغاز می نماید. این فرآیند جستجو برای تعدادی از چرخه های تکرار اعمال خواهد شد (یعنی I). بنابراین، پیچیدگی زمانی این بخش برابر با O(IAkf_k) می باشد، که در آن A تعداد مورچه ها، k تعداد خوشه ها و f_k معرف میانگین تعداد ویژگی ها در هر خوشه است که برابر با n/k تلقی می شود، بنابراین این پیچیدگی را می توان با استفاده از O(IAn) مشخص ساخت. به علاوه، در صورتی که مورچه ها در یک حالت موازی حرکت نمایند، پیچیدگی محاسباتی به O(In) کاهش خواهد یافت. به علاوه، در انتهای هر تکرار در مرحله سوم، کیفیت هر زیر مجموعه محدود شده به وسیله یک شاخص تفکیک پذیری مورد ارزیابی قرار می گیرد. پیچیدگی زمانی این شاخص برابر با O(s²np) می باشد، که در آن s به عنوان ویژگی عدد صحیح زیر مجموعه انتخابی به شمار می آید. به هنگامی که الگوریتم ACO به اتمام رسد، کلیه ویژگی ها بر مبنای مقادیر فرومون آنها و با توجه به پیچیدگی زمانی O(nlogn) دسته بندی گردیده و متعاقباً m ویژگی با بالاترین مقدار به عنوان زیر مجموعه نهایی ویژگی ها انتخاب می شود. بنابراین، پیچیدگی زمانی مرحله سوم برابر با O(ncp + In + s²np + nlogn) خواهد بود. در نتیجه، پیچیدگی زمانی نهایی روش GCACO برابر با O(n²p + n log n + ncp + In + s²np + n log n) می باشد. به هنگامی که تعداد ویژگی ها که به وسیله هر مورچه انتخاب می گردد (یعنی s) بسیار کمتر از تعداد ویژگی های اصلی باشد (s² << n)، پیچیدگی محاسباتی روش پیشنهادی را می توان تا O(n² p + In) تقلیل داد.

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

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

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

4ـ1. مجموعه های اطلاعاتی

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

4ـ2. کلاسیفایرهای کاربردی

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

4ـ3. پارامترهای خاص کاربران

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

4ـ4. نتایج

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

4ـ4ـ1. دقت دسته بندی

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

4ـ4ـ2. تعداد ویژگی های انتخابی

جدول 9 نشان دهنده تعداد ویژگی های انتخابی روش های انتخاب ویژگی مختلف با توجه به انجام ده مرحله مستقل می باشد. از این نتایج می توان مشاهده نمود که به طور کلی کلیه روش های انتخاب ویژگی قابلیت کاهش معنی دار بعدیت، از طریق انتخاب صرف بخش اندکی از ویژگی های اصلی، را خواهند داشت. به علاوه، نتایج نشان دهنده آن است که GCACO، به طور میانگین، قابلیت انتخاب کمترین تعداد ویژگی ها را دارد. به طور مثال، از نتایج می توان ملاحظه کرد که روش پیشنهادی تعداد میانگین 1/23 ویژگی را انتخاب نموده است، در حالی که روش های انتخابی ویژگی دیگر به طور میانگین قابلیت انتخاب 5/28 ویژگی را خواهند داشت.

4ـ4ـ3. مقایسه با روش های مبتنی بر دسته بندی

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

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

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

4ـ4ـ5. نتایج آزمون آماری

در این آزمایشات، یک آزمون مهم آماری تحت عنوان آزمون فریدمن [18] جهت مقایسه متعاقب روش های انتخاب ویژگی ذکر شده با توجه به مجموعه های اطلاعاتی متعدد، و با کلاسیفایر مختلف، برگزیده شد. آزمون فریدمن را می توان جهت مقایسه روش های k با مجموعه های ا طلاعات N از طریق رتبه بندی هر روش بر روی هر مجموعه اطلاعاتی به صورت مجزا بکار گرفت. روشی که قابلیت حاصل آوردن بهترین عملکرد را داشته باشد دارای رتبه 1 گردیده و بعدی رتبه 2 و به همین ترتیب رویه ادامه خواهد یافت. ما از آمار SPSS که به وسیله سیستم IBM برای این منظور ارائه شده است[40] استفاده نمودیم. نتایج حاصله نشان دهنده آن است که آزمون فریدمن ارائه دهنده یک مقدار ـ p برابر با 000008/0 برای مقادیر دقت دسته بندی کلاسیفایر SVM در جدول 4 می باشد. از آنجایی که این مقدار زیر 05/0 است، ما می توانیم ادعا نماییم که اهمیت آماری نتایج روش پیشنهادی قابل توجه می باشد. به علاوه، آزمون فریدمن مقادیر ـ p 0، 0، 000003/0 و 000001/0 را برای کلاسیفایرهای دیگر شامل به ترتیب DT، NB، kNN و RF پیشنهاد نموده است. بنابراین، این کلاسیفایرها دارای مقادیر ـ p زیر 05/0 هستند که سبب می شوند تا این نتایج از نقطه نظر آماری معنی دار تلقی شوند. به علاوه، آزمون فریدمن همچنین برای نتایج گزارش شده روش های مبتنی بر بسته بندی ارائه شده است (همانند جدول 10). در این مورد، آزمون آماری گزارش شده مقادیر ـ p 000026/0 و 085801/0 برای کلاسیفایرهای SVM و NB به ترتیب در نظر گرفته شده اند. در کلاسیفایر SVM، مقدار ـ p حاصله کمتر از 05/0 می باشد، بنابراین، می توان به این نتیجه گیری رسید که نتایج دقت دسته بندی حاصله با توجه به کلاسیفایر SVM قابل توجه و معنی دار هستند. در مقابل مورد مرتبط با کلاسیفایر NB، نتایج متناظر از اهمیت آماری برخوردار نیستند و می توان اینگونه استنباط نمود که هیچ کدام روش های انتخاب ویژگی دارای عملکرد بهتری در مقایسه با دیگران نخواهند بود.

4ـ4ـ6. تحلیل حساسیت پارامترها

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

4ـ5. مباحث

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

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

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

3. روش GCACO اقدام به یکپارچه سازی روش خوشه بندی گراف با فرآیند جستجوی الگوریتم ACO می نماید. با استفاده از روش خوشه بندی ویژگی قابلیت ارتقای عملکرد روش پیشنهادی با توجه به چندین ویژگی و مؤلفه به وجود خواهد آمد. در ابتدا، پیچیدگی زمانی در مقایسه با روش های انتخاب ویژگی ACO ـ مبنای دیگر کاهش می یابد. علت این امر به واسطه این حقیقت است که مورچه نیازی برای سیر یک گراف کامل را نخواهد داشت. بنابراین، محاسبه احتمال در یک گراف خوشه ای در مقایسه با محاسبه در گراف کامل کاهش می یابد. دوماً، فرآیند جستجو به گونه ای کنترل و هدایت می شود که حداقل یک ویژگی در هر خوشه، با توجه به فرآیند جستجوی هر مورچه، انتخاب گردیده و همچنین ویژگی های همبسته کمتری با تناسب بیشتر با توجه به ویژگی های همبسته بیشتر با موارد تکراری متوالی تزریق گردند.

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

5- نتیجه گیری

انتخاب ویژگی نقش مهمی را در دنیای فراگیری ماشینی بازی می نماید و مخصوصاً این نقش در ارتباط با وظیفه دسته بندی بسیار مهم تلقی می شود. به علاوه، هزینه محاسباتی تقلیل یافته و از طرف دیگر این مدل از داده های ساده شده به وجود آمده و بنابراین توانایی ارتقای قابلیت های کلی کلاسیفایرها را خواهد داشت. در این مقاله، یک روش انتخاب ویژگی جدید از طریق یکپارچه سازی مفهوم خوشه بندی گراف با توجه به فرآیند جستجو و بهینه سازی کلونی مورچه ارائه می شود.  روش پیشنهادی در سه  مرحله کار می کند: در مرحله اول، فضای مشکل به عنوان یک گراف از طریق ملاحظه کل مجموعه ویژگی به عنوان مجموعه رأس مشخص گردیده و دارای مشابهت ویژگی با وزن یال متناظر می باشد. در مرحله دوم، ویژگی ها به چندین خوشه از طریق بکارگیری یک روش تشخیص جامعه تقسیم می گردند. در نهایت، در مرحله سوم، ما از یک الگوریتم انتخاب ویژگی ACO ـ مبنا استفاده می نماییم که با استفاده از بکارگیری خوشه های ویژگی توسعه یافته است. روش پیشنهادی قابلیت تعامل با ویژگی های نامرتبط و موارد زاید را خواهد داشت. علت این امر را می توان در این حقیقت جستجو کرد که هر مورچه در گراف خوشه بندی شده سعی در جستجوی ویژگی ها با حداقل مشابهت نموده و بنابراین قابلیت به حداکثررسانی وابستگی بر روی کلاس هدف را خواهد داشت. روش پیشنهادی با شش روش نوین شناخته شده مقایسه شدند که عبارتند از: L-Score، F-Score، RRFS، Mrmr، ReliefF و UFSACO. بعلاوه این روش با سه روش مبتنی بر سیستم بسته بندی مقایسه شدند که شامل HGAFS، ACOFS و PSOFS از سه ویژگی مختلف دقت دسته بندی، اندازه ویژگی های انتخابی زیر مجموعه و زمان اجرا می باشند. نتایج گزارش شده نشان دهنده آن هستند که در غالب موارد روش پیشنهادی حاصل آورنده بهترین دقت دسته بندی می باشد. به علاوه، این نتایج مشخص کننده آن هستند که زمان اجرای روش پیشنهادی در قیاس با روش های انتخاب ویژگی خواهد بود. به علاوه، آزمون آماری انجام شده در ارتباط با سه برآورد مختلف شامل دقت دسته بندی، تعداد ویژگی های انتخابی و زمان اجرا، نشان دهنده آن می باشد که نتایج حاصله از نقطه نظر آماری معنی دار و مهم تلقی می شوند.

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