بخشی از مقاله
چکیده
در این مقاله روشی برای دستهبندی مجموعه دادههای متشکل از ویژگیهای مرکب - هم ویژگیهای عددی و هم ویژگیهای رستهای - ارائه شده است. اکثر مجموعه دادههای واقعی متشکل از ویژگیهای مرکب هستند و بیشتر الگوریتمهای خوشهبندی مرسوم، برای مجموعه دادههایی شامل یک نوع ویژگی - یا عددی یا رستهای - طراحی و بهکار برده شدهاند. همچنین اخیرا روشهای جدیدی برای خوشهبندی دادههایی با ویژگیهای مرکب ارائه شده است که از مکانیزم تبدیل ویژگیها به نحوی که مستقیما توسط الگوریتم قابل استفاده باشد، استفاده میکنند اما این روشها نیز با چالشهای مهمی از جمله فقدان اطلاعات، تولید نتایج تحریف شده و ایجاد خوشهبندی با صحت پایینتر روبرو هستند.
لذا در این مقاله برای حل این مشکل ضمن معرفی مساله خوشهبندی به عنوان یک مساله بهینهسازی چند هدفه، یک چارچوب برای مجموعه داده با ویژگیهای مرکب بدون نیاز به تبدیل دادهها ارائه شده است و از الگوریتم تکاملی چندهدفه NSGA ii برای حل مساله استفاده شده است. الگوریتم تکاملی چندهدفه ارائه شده با بهینهسازی دو معیار آنتروپی و مجذور مربعات خطا 1 - SSE - جوابهای خوشهبندی با خلوص و همبستگی بیشتر را ارائه مینماید. همچنین در این مقاله شیوهای بهبودیافته برای ایجاد عملگرهای جهش و تقاطع، به منظور گسترش فضای جستوجو و جلوگیری از تغییر جمعیت اولیه و تاثیر روی همگرایی جواب و حذف خوشهها در حین بهکارگیری عملگرها ارائه شده است. معرفی ضریب وزنی برای یکسان سازی تاثیر دادههای عددی و نامی بر معیار مجذور مربعات خطا نیز پیشنهاد شده است.
-1 مقدمه
خوشهبندی زیر گروه مهمی از روشهای یادگیری بدون نظارت و تکنیکی برای تقسیم دادهها به چندین خوشه - گروه یا بخش - است که هر خوشه میتواند چندین عضو را شامل شود. اجزا بر مبنای شباهتشان به هم گروهبندی میشوند. بنابراین خوشهبندی بهتر به این معناست که اجزای یک خوشه از برخی جهات شبیهترین به هم هستند. در حالی که اجزای خوشههای متفاوت با هم تفاوت دارند. در روشهای کلاسیک خوشهبندی، یک تک معیار در مساله بهینه سازی میشود در حالی که پژوهشها نشان میدهد بهینهسازی چندین معیار در روشهای ابتکاری میتواند به مراتب بهتر از روشهای کلاسیک عمل کند زیرا مساله خوشهبندی، اساسا یک مساله چند هدفه است.
یکی از روشهای موثر برای خوشهبندی استفاده از الگوریتم ژنتیک است . توانایی ژنتیک در تعیین تعداد درست خوشهها و تشکیل خوشههای مناسب پذیرفته شده است. الگوریتم ژنتیک قادر است عملیات جستوجو را در فضایی پیچیده، گسترده و چند مدله انجام دهد و جوابی نزدیک به بهینه را برای هدف و تابع درستنمایی یک مساله بهینهسازی ارائه دهد - شیخ، راگوانشی و همکاران، . - 2008 لذا هدف از این پژوهش ارائه روشی موثر برای خوشهبندی مشتریان بانک با استفاده از الگوریتم ژنتیک چندهدفه با عملگرهای اصلاح شده میباشد.
روش ارائه شده میتواند برای دادههای رستهای2 و عددی مورد استفاده قرار بگیرد. همچنین خوشهبندی ارائه شده شمای مناسبی را از وضعیت مشتریان برای بانک فراهم آورد و یک روش مناسب برای دستهبندی، تحلیل و انجام مدلهای اعتباری میباشد. پس از مقدمه، این مقاله به این شکل سازماندهی میشود ابتدا به بررسی مطالعات انجام شده در این موضوع پرداخته میشود سپس ضمن معرفی الگوریتم ژنتیک چندهدفه به کار برده شده، عملگرهای بهبود یافته و معیارهای بهینهسازی آن تشریح میشود و در انتها الگوریتم روی دادههای واقعی مجموعه داده آلمان پیادهسازی شده و نتایج ارزیابی میگردد.
-2 مطالعات انجام شده
در چند سال گذشته الگوریتمهای محاسباتی تکاملی به صورت گسترده در مسائل خوشهبندی به کار گرفته شده است زیرا این الگوریتمها ظرفیت بالایی در حل مسائل با تنوع زیاد با کمترین تغییرات را دارا میباشند. همچنین این الگوریتمها میتوانند چندین محدودیت را از طریقی کارا مدیریت کنند. راشکا و ابکن الگوریتم ژنتیک را برای یک مساله خوشهبندی به کار گرفتهاند. در این پژوهش یک روش کدگذاری ساده با کروموزومهایی با طول ثابت به کار گرفته شده است.
تابع هدف همگونی در داخل هر خوشه و عدم همگونی را بین خوشههای مختلف به صورت همزمان بیشینه میکند. همچنین در این روش تعداد مناسب خوشهها با توجه به یک معیار خارجی - سیلوئت - 3 محاسبه شده است - روشکا و ابکن، . - 2003 در مطالعات شانگ و چائو یک الگوریتم ابتکاری برای خوشهبندی ارائه شده است که تابع هدف بر مبنای یک تابع شباهت مبتنی بر پیغام ساخته شده است که پیغام دهی را بین اشیاء و مراکز بهینه خوشهها، شبیهسازی میکند.
عملکرد روش در مثالهای ترکیبی و همچنین در مجموعه دادهای واقعی نشان داده شده است - شانگ، ژائو و همکاران، . - 2012 لیو و وو یک الگوریتم ابتکاری کدشده واقعی با یک عملگر جهش خاص و یک تابع درست نمایی مبتنی بر شاخص دیویس-بولدین4 را ارائه دادند. نویسندهها عملکرد خوب روش را در مسائل مختلف و مجموعه داده شناخته شده سرطان سینه نشان دادند - لیو و وو، . - 2011 الگوریتمهای تکاملی همچنین برای بهبود روش کی-مینز5 ارائه شده است.
برای مثال کریشنا و مورتی الگورینم کی-مینز مبتنی بر ژنتیکی ارائه دادند که در مسائل خوشهبندی دشوار بهتر از کی- مینز عمل میکند - دنگ، هه و همکاران،. - 2010 بابو و مرتی الگوریتم ژنتیکی برای انتخاب مراکز خوشه اولیه در الگوریتم کی-مینز ارائه کردند که در آن از نمایش رشته بیتی استفاده میشود. در این الگوریتم از یک عملگر ساده بازترکیبی برای جابجایی مراکز خوشه والدین استفاده میشود. به طوریکه این جابجایی به صورت کاملا تصادفی در فضای مجموعه دادهها انجام میشود - بابو و مورتی، . - 1993
در - لین و یانگ، . - 2005 نویسنده یک روش خوشهبندی بدون نظارت مبتنی بر ژنتیک که مراکز خوشهها را به صورت مستقیم از مجموعه داده انتخاب میکند، ارائه داده است. در این الگوریتم فاصله بین تمام جفت نقاط داده نگهداری میشود و برای کدکردن یک متغیر عددی از مراکز خوشه، از نمایش باینری استفاده میشود. همچنین نوع موثرتری از عملگرهای تقاطع، جهش و تولید نسل ارائه شده است.
-3مدل پیشنهادی
در این بخش ساختار الگوریتم ژنتیک چند هدفه ارائه شده به همراه عملگرهای اصلاح شده و اهداف بهینهسازی به تشریح مورد بررسی قرار میگیرد.
1-3 جمعیت اولیه
برای نمایش جمعیت اولیه از یک رشته n تایی - تعداد دادها - از ژنها استفاده شده است. به هر ژن عددی بین 1 تا k تعلق میگیرد که k نشان دهنده تعداد دستههای وارد شده از طرف کاربر است. شماره ستون هر ژن نشان دهنده شماره داده میباشد. هرچند این نوع کدینگ نسبت به کدینگهای الگوریتمهای ژنتیک مرسوم که برای فرایند کی-مینز به کار میروند و در آنها از مراکز خوشهها به عتوان مقادیر درون ژنها استفاده میشود، دارای حجم بیشتری است، اما نمایش بهتری را از جوابها ارائه مینماید.
2-3 نمایش کروموزومها
هر فرد یک ماتریس سطری 1 ∗ را نمایش میدهد که n تعداد مشاهدات است. هر ژن شامل اعداد صحیح [1,..,k] است که خوشهای را که هر مشاهده به آن تعلق دارد را نمایش میدهد. همانطور که در شکل 1مشاهده میشود اولین ژن در کروموزوم 4 است که این به این معناست که مشاهده 1 در خوشه چهارم قرار دارد.
3-3 عملگر تقاطع
تقاطع6 یک پروسه احتمالی است که اطلاعات را از والدین به کروموزوم فرزند منتقل میکند. این عملگر یک عملگرِ ترکیبی است که انواع مختلفی دارد - چاترجی و موخوپادهای، . - 2013 در این مقاله از عملگر تقاطع با نرخ احتمال تقاطع ثابت استفاده شده است. عملگر تقاطع در الگوریتمهای ژنتیک سنتی تک نقطهای یا چند نقطهای بودند اما این مکانیزم باعث تغییر جمعیت اولیه و تاثیر روی همگرایی جواب بهینه میشود. برای مثال اگر کروموزوم اول 3}،2،2،1،1،{1 و کروموزوم دوم 2}،1،1،3،3،{3 باشد. این دو کروموزوم اساسا نتایج خوشهبندی یکسانی دارند.
در هر دوی آنها سه شیء اول در یک خوشه، شیء چهارم و پنجم در خوشه دیگر و شیء ششم در آخرین خوشه قرار دارند. بنابراین مقدار تابع برازندگی یکسانی دارند. حال اگر یک عمگر تقاطع تک نقطهای روی پنجمین موقعیت اعمال شود بعد از تقاطع خواهیم داشت: کروموزوم اول2}،1،2،1،1،{1 و کروموزوم دوم3}،2،1،3،3،.{3 همانطور که مشاهده میشود در اولین فرزند تعداد خوشهها تغییر میکند. برای اجتناب از این مساله از روش برچسبگذاری مبتنی بر گراف دو بخشی7 استفاده شده است.
اگر کروموزوم اول3}،1،3،2،1،2،1،3،{1 و کروموزوم دوم 1}، 1،1،3،3،3، 2،2،{2 باشد. عدم تشابه بین خوشه iام از کروموزوم اول و خوشه jام از کروموزوم دوم محاسبه می شود. | | یعنی اندازه خوشه .i بعد از محاسبه ماتریس عدم تشابه از یک گراف دوبخشی مبتنی بر این مقادیر عدم تشابه استفاده میکنیم. برای مثال گراف دو بخشی سه راس در هر مجموعه دارد. فرض کنیم مجموعه سمت چپ - برای کروموزوم اول - سه راس داشته باشد و مجموعه سمت راست - برای کروموزوم دوم - سه راس داشته باشد. هر راس نشان دهنده یک خوشه کد شده در کروموزوم است.
