الگوریتم ژنتیک گروهی جهت ارتقای عملکرد خوشه بندی ویژگی

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

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

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

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

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

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

چگونگی سفارش

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

www.irantarjomeh.com

الگوریتم ژنتیک گروهی جهت ارتقای عملکرد خوشه بندی ویژگی

استفاده از الگوریتم ژنتیک گروهی جهت ارتقای عملکرد خوشه بندی ویژگی

چکیده

انتخاب ویژگی به عنوان یک مرحله پیش پردازشی در ارتباط با داده کاوی و فراگیری ماشینی به شمار آمده و در خصوص تحلیل داده های ابعادی سطح  بالا بسیار مهم تلقی می شود. خوشه بندی ویژگی برای انتخاب ویژگی پیشنهاد شده است. در صورتی که قابلیت خوشه بندی ویژگی های مشابه را در گروه ها داشته باشیم، در صورت از دست دادن برخی از مقادیر ویژگی ها آنها را متعاقباً می توان به آسانی به وسیله خوشه های دیگر در همان گروه جایگزین نمود. Hong و همکاران جهت یافتن خوشه های ویژگی مناسب یک الگوریتم ژنتیک (GA) را پیشنهاد نمودند. با این وجود، در این رویکردها، کروموزوم های متعدد معرف نتیجه خوشه بندی ویژگی مشابه (راه حل محتمل) به واسطه خصیصه های ترکیبی هستند، و بنابراین فضای جستجو بزرگتر از حد ضروری می باشد. این مطالعه اقدام به ارتقای عملکرد فرآیند خوشه بندی ویژگی بر مبنای الگوریتم ژنتیک و با توجه به الگوریتم ژنتیک گروهی (GGA) می نماید. در رویکرد پیشنهادی، شاخص ها و عملگرهای GGA جهت کاهش افزونگی در شاخص های کروموزوم در ارتباط با خوشه بندی ویژگی بکار گرفته می شوند. آزمایشات همچنین جهت مقایسه کارایی رویکرد پیشنهادی با رویکرد موجود اعمال شده اند. نتایج معرف آن می باشند که رویکرد پیشنهادی می تواند سبب حصول دستاوردهای مناسب و کارآمد در خصوص گروه بندی ویژگی شود.

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

1- مقدمه

انتخاب ویژگی به عنوان یک مؤلفه مهم پیش پردازشی در داده کاوی و فرآیند ماشینی به شمار می آید [8]. یک مجموعه فرعی مناسب ویژگی ها نه تنها قابلیت کاهش زمان اجرای مورد نیاز برای قواعد حاصله را خواهد داشت [2]، بلکه می تواند دقت دسته بندی را نیز افزایش دهد. انتخاب ویژگی همچنین به عنوان یک مورد حیاتی در خصوص طبقه بندی داده ها و فراخوانی آنها به شمار آمده و به طور گسترده ای در بسیاری از رشته های تحقیقی، نظیر شناسایی الگو، ویژگی های آماری و داده کاوی بکار گرفته شده است. از آنجایی که انتخاب ویژگی در حقیقت به عنوان یک مسئله بهینه سازی تلقی می شود، تکنیک های زیادی را می توان مورد استفاده قرار داد. برخی از رویکردهای شناخته شده در این مبحث همانند الگوریتم ژنتیک [15، 17]، الگوریتم بهینه سازی ازدحام ذرات [20، 21]، الگوریتم بهینه سازی کلونی مورچه [13]، و دیگر الگوریتم های بهینه سازی الهام گرفته از ویژگی های زیستی [9، 10، 22] در این زمینه قابل توجه می باشند.

رویکردهای الگوریتم ژنتیک مبنای بسیاری وجود دارند که برای انتخاب ویژگی پیشنهاد شده اند [15، 17]. به علاوه برخی از الگوریتم های مبتنی بر PSO یا ACO نیز برای مشکلات مربوط به انتخاب ویژگی عرضه گردیده اند [13، 21]. به طور مثال، در مرجع [21]، یک رویکرد بهینه سازی ازدحام ذرات چند هدفه (PSO) برای انتخاب ویژگی بکار گرفته شد. هدف این رویکرد ایجاد مجموعه ای از راه حل های پارتو (زیر مجموعه های ویژگی) برای دسته بندی می باشد. در مرجع [13]، یک الگوریتم فراابتکاری ترکیبی تحت عنوان الگوریتم بهینه سازی کلونی مورچه ـ فاخته پیشنهاد شد، که به عنوان یک مؤلفه ترکیبی الگوریتم کلونی مورچه و جستجوی فاخته برای انتخاب ویژگی در فرآیند ماموگرافی دیجیتال به شمار می آید. به عبارت دیگر، هدف اصلی این رویکردها فراهم آوردن مجموعه ای از ویژگی های انتخابی برای دسته بندی می باشد.

با این وجود، به منظور فایق آمدن بر مشکل بعدیت بالا، تکینکی های انتخاب ویژگی مختلفی پیشنهاد شده اند [1، 23]. یک زیر مجموعه ویژگی مناسب قابلیت کمک در زمینه پذیرش الگوریتم فراگیری و حاصل آوردن نتایج بهتر در زمان کمتر را خواهد داشت. یافتن یک زیرمجموعه ویژگی بهینه به عنوان یک مسئله NP ـ سخت به شمار می آید [3]. در سال 2007، Hong و Liou یک رویکرد انتخاب ویژگی بر مبنای مفهوم خوشه بندی ویژگی را عرضه داشتند [12]. در این رویکرد، مشکل انتخاب k ویژگی از ویژگی های ورودی را می توان به عنوان یک مسئله خوشه بندی ـ k در نظر گرفت، که در آن هر خوشه قابلیت فراهم آوردن یک ویژگی به عنوان عضو زیرمجموعه ویژگی نهایی را خواهند داشت. این رویکرد قابلیت یافتن یک زیر مجموعه ویژگی تقریبی را برای دسته بندی خواهد داشت. به علاوه، این الگوریتم می تواند نسبت به یافتن ویژگی دیگر جهت جایگزینی ویژگی انتخابی اقدام نماید، آن هم در صورتی که با مفقود شدگی مقدار ویژگی آن آبجکت یا موضوع خاص روبرو شده باشیم. بر مبنای ایده مشابه، Hong و Wang [16، 17] روش های خوشه بندی مبتنی بر الگوریتم ژنتیک را برای خوشه بندی ویژگی پیشنهاد نمودند تا قابلیت یافتن یک زیر مجموعه ویژگی تقریبی برای دسته بندی را داشته باشند. همانگونه که Falkenauer خاطرنشان ساخته است، الگوریتم ژنتیک دارای نقص هایی به هنگام حل مشکلات گروه بندی می باشد [6]. بر مبنای طرح کدگذاری، کروموزوم های متعدد قابلیت نگاشت به نتیجه خوشه بندی ویژگی مشابه (راه حل محتمل) به واسطه خواص ترکیبی را داشته و بنابراین فضای جستجو بزرگتر از حد ضروری می گردد.

به علاوه، عملیات الگوریتم ژنتیک قابلیت متمایز سازی کروموزوم هایی که به نتیجه یکسانی نگاشت شده اند را نخواهد داشت. در چنین موردی، دو کروموزوم با نتیجه یکسان ممکن است اقدام به ایجاد یک کروموزومی نمایند که کاملاً متمایز از والدین خود می باشد، بدان معنا که روش های مبتنی بر الگوریتم ژنتیک نیاز به زمان بیشتری جهت همگرایی دارند. Falkenauer [6] نسبت به ارائه الگوریتم ژنتیک گروهی (GGA) جهت مخاطب قرار دادن این مسئله اقدام نموده است. الگوریتم GGA از جریان کاری مشابهی همانند الگوریتم ژنتیک یا GA برخوردار می باشد، اما از طرح های کدگذاری و عملگرهای مختلفی استفاده می نماید. بنابراین این مورد مشخص شده است که کارایی الگوریتم GGA بهتر از الگوریتم GA در برخی از نواحی مخصوصاً با توجه به مشکلات گروه بندی می باشد [4].

بنابراین، مطالعه جاری اقدام به ارائه یک رویکرد خوشه بندی ویژگی مبتنی بر ـ GGA  می نماید. به عبارت دیگر، هدف اصلی تقسیم ویژگی ها  به  k  گروه برای  دسته بندی  می باشد. ویژگی های موجود در یک گروه خاص بدان معنا خواهد بود که آنها دارای خواص یکسانی می باشند. بنابراین، ما قابلیت انتخاب ویژگی ها از هر گروه را خواهیم داشت و می توانیم آنها را به صورت توأم برای دسته بندی در اختیار داشته باشیم. بنابراین، در موردی که یک ویژگی انتخابی K دارای مقادیر مفقوده بسیاری باشد، ما قابلیت انتخاب ویژگی B از همان گروه جهت جایگزینی با A را خواهیم داشت. بنابراین، بر مبنای الگوریتم GGA، ما می توانیم شاخص های کروموزوم، عملیات ژنتیک و تابع برازندگی را تعریف نماییم (به بخش 3 رجوع شود) که در ارتباط با رویکرد پیشنهادی برای حل مشکل خوشه بندی ویژگی می باشد. بنابراین، این مقاله موارد ذیل را در نظر می گیرد: (1) یک رویکرد گروه بندی ویژگی بر مبنای الگوریتم GGA برای حل مسئله خوشه بندی ویژگی در ارتباط با دسته بندی پیشنهاد می شود، (2) از طریق بکارگیری نتایج خوشه بندی ویژگی حاصله، به هنگامی که یک ویژگی A دارای مقادیر مفقوده بسیار یا نمونه های داده های کمتری باشد، به جای ویژگی A، یک ویژگی B در همان گروه را می توان برای دسته بندی انتخاب نمود.

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

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

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

2ـ1. انتخاب ویژگی

انتخاب ویژگی به عنوان یک مؤلفه پیش پردازشی مهم در زمینه فراگیری ماشینی و داده کاوی به شمار می آید، مخصوصاً به هنگامی که فرآیند یادگیری بر روی مجموعه های اطلاعاتی دارای ویژگی های ابعادی بالا اجرا می شود. Dash و همکاران [5] اقدام به تعریف انتخاب ویژگی برای دسته بندی به عنوان مشخصه جهت یافتن زیر مجموعه های با اندازه حداقلی ویژگی ها که قابلیت حفظ دقت دسته بندی در توزیع کلاس حاصله را دارد نموده اند. یک زیر مجموعه ویژگی مناسب نه تنها قابلیت کاهش زمان آموزش و ضروریات I/O را خواهد داشت، بلکه منجر به درک بهتر داده ها و پیش بینی های دقیقتری می شود. یک مجموعه ویژگی ورودی غالباً دارای برخی از ویژگی های خاص می باشد که برای اهداف مربوطه بصورت حشو یا غیرمرتبط به شمار می آیند. این ویژگی ها ممکن است سبب شوند تا کلاسیفایر مسیر نادرستی را جهت یافتن نتایج استنباط نماید و بنابراین سبب کاهش سرعت فرآیند می گردد. ویژگی های نامربوط نیز سبب کاهش عملکرد هدف مورد نظر خواهند شد. ویژگی های اضافه در ارتباط با اهداف مورد نظر تلقی  گردیده اما می توان آنها را جایگزین ویژگی های دیگری نمود. هدف انتخاب ویژگی بر این مبنا یافتن زیرمجموعه مناسبی از ویژگی هایی می باشد که در ارتباط با مفهوم هدف هستند. به عبارت دیگر، چنین موردی به عنوان راهکاری به شمار می آید که قابلیت حذف ویژگی های نامرتبط یا اضافه جهت ارتقای کارایی برنامه های کاربردی، که در تعامل با مجموعه های اطلاعاتی دارای ابعادی بالا می باشند، را دارد. رویکردهای GA ـ مبنای بسیاری برای انتخاب ویژگی پیشنهاد شده اند [15، 17]. به علاوه، برخی از الگوریتم های مبتنی بر PSO یا ACO نیز برای مشکلات مربوط به انتخاب ویژگی پیشنهاد گردیده اند [13، 21]. هدف اصلی این رویکردها فراهم آوردن مجموعه ای از ویژگی های انتخابی برای دسته بندی می باشد. در تحقیق قبلی ما، یک الگوریتم GA ـ مبنا برای گروه بندی ویژگی [17]، و نه صرفاً برای انتخاب ویژگی، بکار گرفته شده است.

2ـ2. برآوردهای وابستگی های ویژگی

برآوردهای وابستگی جهت ارزیابی مشابهت بین ویژگی ها بکار گرفته می شوند. آنها به وسیله Han و همکاران [11] و Li و همکاران [14] پیشنهاد شده اند. Hong و Liou از برآورد وابستگی در روش خوشه بندی ویژگی خود بر مبنای رویکردهای انتخاب ویژگی استفاده نمودند [10]. ویژگی هایی که دارای تعامل مشابهی با دسته بندی هستند از وابستگی بالایی به یکدیگر برخوردار می باشند. به طور رسمی، با توجه به دو ویژگی A_i و A_j، مقدار نسبی وابستگی A_i با توجه به A_j تحت عنوان Dep(A_i, A_j) مشخص می گردد که خود بر حسب فرمول (1) به شرح ذیل تعیین شده است:

2ـ3. خوشه بندی ویژگی بر مبنای الگوریتم های ژنتیک

Hong و Wang [16] یک روش خوشه بندی مبتنی بر الگوریتم ژنتیک برای خوشه بندی ویژگی را پیشنهاد نمودند که قابلیت یافتن زیر مجموعه های ویژگی تقریبی را برای دسته بندی دارد. آنها در ابتدا رویکردی را پیشنهاد کردند که دقت میانگین دسته بندی را در نظر داشته و قابلیت ایجاد نوعی تعادل در خصوص خوشه های ویژگی، ارائه شده به وسیله کروموزوم ها، و با توجه به معیار ارزیابی برازندگی، را خواهد داشت. دقت میانگین دسته بندی جهت محاسبه کلیه ترکیب های زیر مجموعه ویژگی محتمل از نتایج خوشه بندی کروموزوم بکار گرفته شده و متعاقباً به منظور ارزیابی قابلیت این دسته بندی زیر مجموعه ویژگی های انتخابی با توجه به مجموعه های داده های مشخص شده مورد استفاده قرار می گیرند. برآورد دیگر استفاده شده در این رویکرد تعادل خوشه است که جهت کمک به فرآیند خوشه بندی الگوریتم ژنتیک به منظور یافتن خوشه های دارای تعداد مشابهی از ویژگی ها مورد استفاده قرار می گیرد. در صورتی که نتیجه خوشه بندی ارائه شده به وسیله یک کروموزوم از تعادل بیشتری برخوردار باشد، متعاقباً این مقدار بزرگتر خواهد بود.

2ـ4. الگوریتم های ژنتیک و مشکلات گروه بندی

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

اولین ضعف، طرح کدگذاری استاندارد الگوریتم ژنتیک از ویژگی های کاملاً اضافه با توجه به مشکلات گروه بندی در رنج  می باشد. در نظر بگیرید که  N  موضوع  یا  آبجکت را  می بایست در K خوشه تحت فرآیند خوشه بندی قرار داد. هر کروموزوم ممکن است به عنوان یک توالی N ـ ژن به شمار آید، که بر مبنای آن هر ژن به عنوان یکی از سمبل های k گروه به شمار آمده و معرف موضوع یا آبجکت ژنی می باشد که متعلق به آن گروه است. به طور مثال، در نظر بگیرید که یک کروموزوم ABBAC وجود دارد، که معرف پنج آبجکت در سه گروه می باشد. اولین و چهارمین آبجکت در گروه A قرار داشته و دومین و سومین آبجکت در گروه دیگر B قرار گرفته اند و پنجمین آبجکت در یک گروه تکی C قرار می گیرد. این طرح کدگذاری دارای K! کروموزوم متمایز جهت مشخص سازی نتیجه گروه بندی یکسان می باشد، و عملگرهای ژنتیک قابلیت مشخص سازی آنها را نخواهند داشت. بنابراین، فضای جستجو به واسطه دوبله شدگی این طرح افزایش شدیدی یافته و به طور جدی بر روی کارایی الگوریتم ژنتیک تأثیر می گذارد.

2ـ5. الگوریتم ژنتیک گروه بندی

از آنجایی که رویکرد الگوریتم ژنتیک متعارف دارای ضعف هایی به هنگام بکارگیری در خصوص مسایل گروه بندی می باشد، همانگونه که در بالا ذکر شد، Falkenauer اقدام به ارائه الگوریتم ژنتیک گروهی (GGA) نموده است. این الگوریتم به صورت موفقی برای مسایل مرتبط با گروه بندی و خوشه بندی مختلف نظیر مشکلات چیدمان جعبه ها و صرفه جویی های مقیاسی [7] بکار گرفته شده است. به علاوه، Pankratz یک ویژگی خاص مربوط به این الگوریتم را برای مشکل مسیریابی وسایل نقلیه بکار گرفت [18] و Rekiek نیز از این الگوریتم برای حل مسئله جابجایی و حمل و نقل افراد معلول استفاده کرد [19]. نتایج آزمایشات Falkenauer نشان دهنده آن می باشد که عملکرد الگوریتم ژنتیک گروهی بهتر از الگوریتم ژنتیک عادی با توجه به حل این مشکلات به شمار می آید [6].

2ـ5ـ1. ارائه ویژگی های کروموزوم

در تحقیق Falkenauer در خصوص ویژگی های الگوریتم ژنتیک گروهی، یک کروموزوم متشکل از دو بخش می باشد که هر بخش برای آبجکت و گروه مدنظر است. بخش آبجکت قابلیت ذخیره سازی اطلاعات در زمینه چگونگی گروه بندی آبجکت ها را خواهد داشت و بخش گروه به عنوان یک لیست مرتب شده گروه ها به شمار می آید. بخش گروه به وسیله یک رشته دارای طول ثابت شکل می گیرد، که در آن هر ژن در آن رشته معرف برچسب گروه یک آبجکت می باشد. به طور مثال، یک بخش آبجکت را در کروموزوم در نظر بگیرید: ACBBA. این کروموزوم معرف آن است که اولین و پنجمین آبجکت متعلق به گروه “A” می باشند. سومین و چهارمین آبجکت متعلق به گروه “B” به شمار آمده و دومین آبجکت متعلق به گروه “C” می باشد. بخش گروه به عنوان تفاوت اصلی از الگوریتم ژنتیک سنتی به شمار می آید. این بخش قابلیت ذخیره سازی نام های گروه در یک ترتیب طول متغیر را خواهد داشت. در الگوریتم ژنتیک گروهی، یک کروموزوم معرف آن خواهد بود که چگونه آبجکت های مشخص شده گروه بندی می شوند. بر چسب ها یا تگ های گروه صرفاً جهت ایجاد تمایز در این زمینه بکار گرفته می شوند که کدام یک از آبجکت ها در یک گروه خاص قرار می گیرند و کدام یک در آن گروه نیستند، و بنابراین تگ مربوط به گروه مشخصی از آبجکت ها در کروموزوم های مختلف به معنای آن نخواهد بود که هیچ گونه ارتباطی بین گروه ها وجود دارد. مثالی از کروموزوم های کامل به شرح ذیل ارائه شده است:

2ـ5ـ2. کراس اور

متمایز از کراس اور الگوریتم ژنتیک، کراس اور یا فرآیند تولید مثل الگوریتم ژنتیک گروهی بر مبنای گروه ها به جای آبجکت ها می باشد. Falkenauer از پنج مرحله ذیل برای این عملگر کراس اور GGA استفاده نموده است [6].

1. انتخاب موقعیت درج در بخش گروه اولین والدین و متعاقباً انتخاب تصادفی یک قسمت مربوط به بخش گروه والدین دیگر.

2. کپی کلیه محتویات اولین والدین به هر کروموزوم خالی، و متعاقباً کپی و درج قسمت گروه انتخابی دیگر والدین انتخاب شده به کروموزوم جدید.

3. حذف آبجکت های تکراری که از اولین والد کپی شده اند.

4. تعدیل گروه های حاصله بر مبنای قیدهای سخت مسئله ای که می بایست آن را حل نمود.

5. بکارگیری مراحل 1 الی 4 برای جفتی از والدین با توجه به تبادل نقش آنها جهت تولید کودکان دیگر.

یک مثال در این زمینه ذیلاً جهت نشان دادن عملیات کراس اور ارائه شده است. بنابراین اینگونه فرض می شود که دو کروموزوم وجود دارند:

ADBBCCAD: ACBD و aabbbccd: adbc

در اولین مرحله، موقعیت درج در بخش گروه اولین والدین و قسمت تصادفی دومین والدین انتخاب می شود. فرض شود که موقعیت درج در اولین والد به صورت موقعیت میله ای نشان داده شده ذیل باشد:

2ـ5ـ3. جهش و وارونگی

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

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

روش پیشنهادی اقدام به تقسیم مجموعه کامل ویژگی به k مجموعه فرعی ویژگی مناسب می نماید، به گونه ای که انتخاب ویژگی و جابجایی را بتوان به آسانی با عملکرد مناسب انجام داد. در اینجا، k به عنوان یک ثابت از قبل تعیین شده می باشد. روش پیشنهادی اقدام به پذیرش الگوریتم ژنتیک گروهی پیشنهاد شده به وسیله Falkenauer جهت یافتن گروه های ویژگی مناسب می نماید [6]. یک شاخص مشخص در ابتدا جهت کدگذاری هر کدام از نتایج خوشه بندی ویژگی محتمل در یک کروموزوم طراحی شده است. رویکرد الگوریتم ژنتیک گروهی متعاقباً به اجرا درآمده تا بر اساس آن قابلیت یافتن بهترین کروموزوم حاصل شود، که به عنوان نتیجه نهایی خوشه بندی تلقی می شود. به علاوه، تابع برازندگی ارائه شده در هر دو مورد الگوریتم های ویژگی مبتنی بر ـ GGA و GA به وسیله Hong و Wang [17] مورد استفاده قرار گرفته تا قابلیت مقایسه مناسب کارایی های آنها به وجود آید. ویژگی کروموزوم رویکرد پیشنهادی به شرح ذیل توصیف می شود.

3ـ1. شاخص کروموزوم

در رویکرد خوشه بندی ویژگی پیشنهادی، هر کروموزوم معرف یک نتیجه خوشه بندی ویژگی محتمل می باشد. حال اجازه دهید تا یک مجموعه ویژگی A متشکل از n ویژگی باشد که به وسیله  نشان داده می شود. در صورتی که هدف انتخاب k ویژگی از A باشد بنابراین یک پارتیشن یا دسته بندی با K گروه ویژگی شکل خواهد گرفت. مجموعه ویژگی نهایی شامل ویژگی ها، با هر مورد انتخاب شده از یک گروه، خواهد بود. به طور رسمی، حال اجازه دهید تا i امین گروه ویژگی به صورت G_i مشخص گردد. بنابراین،  و  حاصل خواهد شد. یک کروموزوم که شامل اطلاعات پارتیشن k گروه است به صورت (G₁, G₂, …, G_K) نشان داده می شود. همانگونه که در بالا ذکر شد، و با توجه به اصلاح اندک، یک کروموزوم GGA متشکل از دو بخش، یکی برای ویژگی ها و مورد دیگر برای گروه ها در نظر گرفته خواهد شد.

3ـ2. جمعیت اولیه

در ابتدا، یک جمعیت مربوط به کروموزوم ها به صورت تصادفی ایجاد می شود. حال فرض کنید که ما خواستار تقسیم بندی N ویژگی به K گروه می باشیم. در ابتدا، K گروه خالی G = {G₁, G₂, …, G_K) ایجاد می شود. N ویژگی متعاقباً به صورت تصادفی به گروه ها تخصیص می یابد، آن هم با توجه به یک ویژگی برای یک گروه فرضی. در صورتی که همچنان یک گروه خالی پس از تخصیص کلیه ویژگی ها باقی مانده باشد، یک گروه به صورت تصادفی از مجموعه  برگزیده شده و به دو گروه تصادفی تقسیم می گردد. فرآیند فوق تا زمانی تکرار خواهد شد که K گروه غیرخالی وجود داشته باشد.

3ـ3. برازندگی و انتخاب

در رویکرد پیشنهادی، تابع برازندگی پیشنهادی به وسیله Hong و Wang [17] جهت یافتن زیر مجموعه های ویژگی مناسب بکار گرفته شده است. این تابع برازندگی متشکل از دو عامل می باشد، دقت خوشه و تعادل خوشه، که به شرح ذیل به صورت مختصر تشریح می شوند.

3ـ4. کراس اور

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

3ـ5. جهش و وارونگی

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

4- الگوریتم پیشنهادی

بر مبنای توصیف فوق، الگوریتم GGA ـ مبنای پیشنهادی برای خوشه بندی ویژگی به شرح ذیل طراحی می شود.

الگوریتم خوشه بندی ویژگی GGA ـ مبنای پیشنهادی

ورودی: یک مجموعه داده آموزشی با N ویژگی و K خوشه

خروجی: یک نتیجه خوشه بندی ویژگی مناسب

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

مرحله 2. محاسبه مقدار برازندگی هر کروموزوم C_i با استفاده از مراحل فرعی ذیل:

مرحله 2ـ1. محاسبه میانگین دقت کلیه ترکیب های ویژگی محتمل کروموزوم از طریق فرمول (2).

مرحله 2ـ2. محاسبه تعادل خوشه کروموزوم، که از طریق تعداد ویژگی ها در گروه، با توجه به فرمول (3)، مشخص می شود. یک کروموزوم به هنگامی دارای مقدار تعادل بیشتری خواهد بود که نتیجه خوشه بندی آن متعادل تر باشد.

مرحله 2ـ3. جامعیت مقادیر مراحل 2ـ2 و 2ـ3 جهت ارزیابی برازندگی کروموزوم به وسیله فرمول (4).

مرحله 3. اجرای عملیات کراس اور GGA.

مرحله 4. اجرای عملیات جهش GGA.

مرحله 5. اجرای عملیات وارونگی .GGA

مرحله 6. اجرای مقادیر برازندگی کروموزوم های جدید.

مرحله 7. ا نتخاب کروموزوم ها برای نسل بعد با استفاده از استراتژی انتخاب چرخ رولت.

مرحله 8 . تکرار مراحل 3 الی 7 تا آنکه معیار اتمام حاصل شود.

مرحله 9. خروجی کروموزوم با بهترین مقدار برازندگی.

5- یک مثال

در این بخش، یک مثال جهت توصیف رویکرد خوشه بندی ویژگی GGA ـ مبنای پیشنهادی ارائه می شود. در نظر بگیرید که پنج شخص با هفت ویژگی ذیل وجود دارند:

جنسیت (S)، انگلیسی (E)، کشور (C)، درآمد (I)، سن (A)، وضعیت تأهل (M)، خرید کامپیوتر (B). نام کلاس Credit می باشد. مجموعه داده ها در جدول 1 نشان داده شده اند.

6- نتایج تجربی

در این بخش، نتایج تجربی برای الگوریتم پیشنهادی در زمینه ویژگی خوشه بندی ارائه می شوند. یک مجموعه اطلاعاتی توموگرافی (SPECT) در این آزمایش بکار گرفته شد. ویژگی های این مجموعه اطلاعاتی در جدول 4 نشان داده شده است. آزمایشات با استفاده از زبان C++ بر روی یک کامپیوتر شخصی با ظرفیت پردازنده 2 Duo  E8400 3-GHz CPU و رم 4 گیگابایت انجام شدند.

7- نتیجه گیری و تحقیقات آتی

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

الگوریتم ژنتیک گروهی جهت ارتقای عملکرد خوشه بندی ویژگی