در رابطه بالا، بیانگر تعیین میزان فاصله هر داده نسبت به مرکز خوشه موردنظر می­باشد.
مراحل الگوریتم k-means بصورت زیر است:
گام اول: الگوریتم، داده ­ها و تعداد خوشه ­ها (k)را به‌عنوان ورودی دریافت می­ کند.
گام دوم: الگوریتم، تعداد k آیتم از داده ­ها را بصورت تصادفی به‌عنوان مراکز اولیه خوشه ­ها انتخاب می­نماید.
گام سوم: سایر آیتم­های داده ­ها، برحسب میزان فاصله با مراکز خوشه ­ها، به یکی از خوشه ­ها نسبت داده می­شوند. معیار تخصیص داده به هر خوشه، نزدیکی به مرکز خوشه است.
گام چهارم: میانگین هر خوشه مجدداً محاسبه شده و به‌عنوان مرکز جدید آن خوشه انتخاب می­گردد.
گام­های سوم و چهارم تا زمانی که چیدمان داده­ در خوشه ­ها تغییر نکرده و یا میزان تغییر بسیار ناچیز باشد، ادامه می­یابد[۱۲۰].
همان‌گونه که در بالا نشان داده شده است، این الگوریتم با تعیین مراکز اولیه شروع می­ شود. این مراکز بایستی به‌گونه‌ای انتخاب شوند که به میزان کافی از یکدیگر فاصله داشته تا نتایج حاصله، نتایج مناسبی باشد[۱۱۹]. بنابراین می­توان بیان داشت که، موفقیت الگوریتم k-means به انتخاب صحیح مراکز خوشه ­های اولیه و تعداد خوشه ­ها وابسته است.
الگوریتم K-means علیرغم سادگی و قدرت بالا، از مشکلات اساسی زیر رنج می­برد:

 

برای دانلود متن کامل پایان نامه به سایت tinoz.ir مراجعه کنید.

 

جواب نهایی الگوریتم به انتخاب مراکز اولیه وابسته است(همگرایی به بهینه محلی)؛ چنانچه در مجموعه داده ­ها، داده ­های پِرت وجود داشته باشد و یا مراکز خوشه ­ها به‌خوبی انتخاب نشوند آنگاه الگوریتم به پاسخی می­رسد که پاسخ درستی نیست. برای حل این مشکل می­توان الگوریتم را چندین مرتبه بر روی داده ­های موردنظر پیاده­سازی کرد.

روشی دقیقی برای تعیین مراکز اولیه وجود ندارد.

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

با توجه به ایـن مشکلـات، امـروزه از الگوریتـم­های تکامـلی در کنار K-means بسیـار استفاده می­شـود. الگوریتم­های تکاملی با توجه به ماهیت تکمیل شونده­ای که دارند، می­توانند مشکلات الگوریتم K-means را به‌خوبی برطرف نمایند. در ادامه الگوریتم­های تکاملی معرفی و نحوه تعامل آن‌ ها با الگوریتم K-means شرح داده شده است.

 

الگوریتم های تکاملی

قانون انتخاب طبیعی به این صورت است که تنها گونه‌هایی از یک جمعیت ادامه نسل می‌دهند که بهترین خصوصیات را داشته باشند و آن‌ هایی که این خصوصیات را نداشته باشند به‌تدریج و در طی زمان از بین می‌روند. مبنای کار الگوریتم­های تکاملی نیز به همین‌گونه است. الگوریتم­های تکاملی دسته­ای از الگوریتم­های موجود هستند که با ایجاد یک جمعیت اولیه شروع کرده و به‌مرورزمان سعی می­ کنند تا جواب­ها را بهبود بخشیده و بهینه­ترین پاسخ را تولید کنند. الگوریتم­های تکاملی این توانایی را دارند که با کمترین دانش موجود، بیشترین کارایی و بهترین جواب­ها را ایجاد کنند.
در هر الگوریتم تکاملی دو مفهوم بسیار مهم وجود دارد:

 

 

جستجو[۱۱۰]: مفهوم جستجو به معنای توانایی الگوریتم در تولید پاسخ­های جدید و ناشناخته در فضای جستجو است. مفهوم جستجو از به دام افتادن الگوریتم در بهینه­های محلی جلوگیری می­ کند. بهترین الگوریتم در جستجوی فضاهای جدید الگوریتم جستجوی تصادفی[۱۱۱] است. به‌منظور پیاده­سازی این مفهوم در هر الگوریتم تکاملی یک گام برای جستجوی فضاهای ناشناخته در نظر گرفته شده است.

بهره­برداری[۱۱۲]: مفهوم بهره ­برداری به معنای بهبود پاسخ­های موجود برای دستیابی به یک بهینه محلی است. این مفهوم این امکان را بوجود می­آورد تا پاسخ­های ایجاد شده تا حد امکان بهبود یافته و بهینه شوند. این امکان نیز بایستی در الگوریتم­های تکاملی وجود داشته باشد.

الگوریتمی مناسب­تر است که از این ۲ مفهوم به‌طور مناسب و در کنار هم استفاده شود.
یکی از کاربردهای الگوریتم­های تکاملی، خوشه­بندی اسناد، مدارک، مشتریان و… است. در ادامه تعدادی از این الگوریتم­ها و مطالعات انجام‌شده با بهره گرفتن از آن‌ ها در خوشه­بندی مورد بررسی قرار گرفته است.

 

الگوریتم ژنتیک

الگوریتم ژنتیک یکی از معروف­ترین و پرکاربردترین الگوریتم­های تکاملی است که در سال ۱۹۶۲ توسط هالند[۱۱۳] معرفی گردید. الگوریتم ژنتیک با بهره گرفتن از اصول انتخاب طبیعی، برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌شـوند. این الگوریتـم با بکارگیری عملگرهای ویـژه­، بر روی مجمـوعه­ای از راه­ حل­های مسئله، به‌گونه‌ای استفاده می­ شود که جمعیت جدید در مقایسه با جمعیت قبلی و مطابق با تابع معیار از پیش تعریف شده، اصلاح شود. خروجی الگوریتم بهترین راه­حلی است که در طول تکامل الگوریتم یافت شده است[۱۲۱]. الگوریتم ژنتیک با کدگذاری راه­ حل­های یک مسئله، بهترین جواب را برای مسئله پیدا می­ کنند. روشی که طبق آن راه­حل­ها کدگذاری می­شوند، نقش بسزایی در کارایی الگوریتم دارد. کدگذاری نامنـاسب، می ­تواند منجر به کـارایی ضعیف الگوریتم شود. عملگرهای کلی الگوریتم ژنتیک عبارتند از:
انتخاب(Selection)
ترکیب(Crossover)
جهش(Mutation)
شمای کلـی الگوریتم ژنتیک در شکل۲- ۲۵ آمده است.

 

 

 

 

 

شکل۲- ۲۵ شمای کلی الگوریتم ژنتیک

در ادامه تعدادی از مطالعاتی که از الگوریتم ژنتیک در فرایند خوشه­بندی استفاده کرده ­اند مورد بررسی قرار گرفته است.
در سال ۲۰۱۱، هان[۱۱۴] و دوستان [۱۲۱]، با بهره گرفتن از یک فرایند ۲ مرحله­ ای اقدام به دسته­بندی مشتریان صنعت تلفن همراه در کره جنوبی نمودند. در مرحله اول آن‌ ها بر روی داده ­های دموگرافیک و الگوی خریدهای پیشین مشتریان حاضر در بازار تلفن­های همراه، الگوریتم­های شبکه عصبی، درخت تصمیم و رگرسیون منطقی را اجرا نموده و پتانسیل خرید آینده هر یک از مشتریان را تعیین نمودند. در مرحله دوم، آن‌ ها با بهره گرفتن از الگوریتم ژنتیک به بررسی میزان شباهت نتایج بوجود آمده از هر الگوریتم پرداختند. هدف آن‌ ها یافتن مشتریان هدف در صنعت تلفن همراه برای افزایش متوسط درآمد از هر کاربر[۱۱۵] بر اساس فروش متقاطع[۱۱۶] بود. آن‌ ها با بهره گرفتن از GA توانستند مشتریان هدف را تعیین کردند.
در سال ۲۰۰۸، چان[۱۱۷] و دوستان [۱۲]، برای انتخاب مشتریان هدف و تشکیل کمپین مشتریان روشی نوین برای دسته­بندی مشتریان بر اساس ترکیب الگوریتم­های RFM و LTV و GA ارائه کردند. برای استفاده از این مدل، چان و دوستان ابتدا مقادیر مربوط به هر یک از متغیرهای RFM را به قالب دودویی تبدیل کردند. ازآنجاکه LTV پتانسیل خرید مشتری در آینده را مشخص می­ کند، لذا آن‌ ها مدل LTV را به‌عنوان تابع برازش در الگوریتم ژنتیک در نظر گرفتند. با بهره گرفتن از الگوریتم ژنتیک و ورودی­ های آن‌که ارزش مشتریان هستند(RFM و LTV)، مشتریان به خوشه ­های مختلف دسته­بندی می­شوند. این مدل در سال ۲۰۰۸ بر روی مشتریان شرکت خودروسازی نیسان پیاده­سازی گردید و مشتریان را به ۸ خوشه تقسیم ­بندی کرده و استراتژی­ های بازاریابی برای هر خوشه تعیین گردید.
در سال ۲۰۱۲، هو[۱۱۸] و همکاران [۱۲۲]، با تمرکز بر مشکلات الگوریتم k-means در خوشه­بندی، مدل جدیدی بر مبنای الگوریتم ژنتیک ارائه کردند. شمای کلی این مدل در شکل۲- ۲۶ نشان داده شده است.

 

 

 

 

 

شکل۲- ۲۶ ترکیب GA و K-means (منبع:[۱۲۲])

با بهره گرفتن از مدل ارائه‌شده در شکل۲- ۲۶، مشکلات الگوریتم k-means(وابستگی به نحوه انتخاب مراکز اولیه و تعیین تعداد خوشه ­ها) برطرف شده و خوشه­بندی مشتریان نتیجه بهتری بدنبال خواهد داشت.
در سال ۲۰۱۴ در [۱۲۳]، برای محاسبه نرخ وفاداری مشتریان و تشخیص مشتریان وفادار از غیر وفادار از الگوریتم ژنتیک در کنار RFM استفاده شده است. در این مطالعه ابتدا با بهره گرفتن از الگوریتم ژنتیک خصوصیات و ویژگی­های مشتریان وفادار در هر خوشه شناسایی شده، سپس میزان اهمیت هر یک از این ویژگی­ها با بهره گرفتن از ضریب همبستگی اسپیرمن[۱۱۹] تعیین شده و در انتها با بهره گرفتن از الگوریتم RFM نرخ وفاداری هریک از مشتریان تعیین می­گردد. روند محاسبه نرخ وفاداری مشتریان در این مطالعه در ادامه شرح داده شده است:

 

 

خوشه­بندی مشتریان با بهره گرفتن از الگوریتم k-means.

محاسبه ضریب همبستگی اسپیرمن برای تمامی ویژگی­ها.

تعیین ویژگی­های تأثیرگذار بر وفاداری مشتریان هر خوشه با بهره گرفتن از الگوریتم ژنتیک.

تعیین نرخ وفاداری مشتریان با بهره گرفتن از مدل RFM.

در [۱۲۴] نیز یک تکنیک رده‏بندی بیزین[۱۲۰] برای مدل‏سازی پاسخ مشتریان، بر پایه یک الگوریتم نوین ژنتیک ارائه‌شده است. در این مطالعه، برای تجزیه‌وتحلیل ساختار، از الگوریتم ژنتیک استفاده شده تا بتوان شبکه‏ای بهینه به‌عنوان ورودی شبکه‏ی بیزین آموزش داد.

 

الگوریتم رقابت استعماری

الگوریتم رقابت استعماری(ICA[121])[122] یکی از انواع الگوریتم­های تکاملی است که در سال ۲۰۰۷ توسط آقای آتش­پز و همکارش در [۱۲۶] معرفی گردید. ICA الهام گرفته شده از فرایند اجتماعی-سیاسی جهان واقعی است. این الگوریتم با تقلید از روند تکامل اجتماعی، اقتصادی و سیاسی کشورها و با مدل­سازی ریاضی بخش­هایی از این فرایند، عملگرهایی را در قالب منظم به صورت الگوریتم ارائه می‌دهد که می‌توانند به حل مسائل پیچیده بهینه سازی کمک کنند. همانند سایر الگوریتم­های تکاملی، الگوریتم ICA نیز با تشکیل مجموعه ­ای از جواب­های احتمالی اولیه، فعالیت خود را آغاز می­ کند. در ICA به هر یک از این جواب­های اولیه یک “کشور[۱۲۳]” می­گویند. هدف الگوریتم رقابت استعماری بهبود این کشورها و یافتن بهینه­ترین جواب است، که برای دستیابی به این هدف روندی خاص در این الگوریتم طی می­ شود. الگوریتم با روندهای خاصی که در طبیعت خود نهفته است به آرامی به بهبود کشورها(جواب­های مسئله) می ­پردازد و درنهایت، جواب مناسب(کشورمطلوب) مسئله بهینه­سازی را تعیین می­ کند[۱۲۷]. عملگرهای اصلی این الگوریتم را سیاست همسان­سازی[۱۲۴]، رقابت استعماری[۱۲۵] و انقلاب[۱۲۶] تشکیل می‌دهند. مراحل الگوریتم رقابت استعماری عبارتند از:
تصویر درباره جامعه شناسی و علوم اجتماعی

 

 

ایجاد کشورهای اولیه

انتخاب بهترین کشورها به‌عنوان استعمارگر

تخصیص سایر کشورها به‌عنوان مستعمره به استعمارگرها(ایجاد امپراتوری‌های(Emperialist) اولیه)

اعمال سیاست جذب(Assimilation)

اعمال سیاست انقلاب(Revolution)

مقایسه مستعمرات با استعمارگرها و جابجایی موقعیت مستعمره و استعمارگر در صورت لزوم

ارزیابی امپراتوری‌ها

رقابت استعماری