پایان نامه: ارائه روش هیبرید خوشه بندی فازی و الگوریتم رقابت استعماری برای طبقه بندی داده ها

فهرست مطالب

عنوان                                                                                                                      صفحه            

چکیده………………………………………………………………………………………………………………………………………………………۱

۱-فصل اول: مقدمه    2

۱-۱- مقدمه. ۳

۱-۲- بیان مسئله. ۴

۱-۳- سوالات اصلی پژوهش… ۷

۱-۴- اهدف پژوهش… ۷

۱-۴-۱- اهداف اصلی.. ۸

۱-۵- جنبه نوآوری و جديد بودن تحقيق. ۸

۱-۶- ساختار پایان‌نامه. ۸

۲-فصل دوم: مفاهیم پیش‌زمینه و مروری بر ادبیات.. ۱۰

۲-۱-مقدمه    11

۲-۲-تعاریف، اصول و مبانی نظری.. ۱۱

۲-۲-۱- خوشه بندی.. ۱۱

۲-۲-۲- داده‌های عظیم. ۱۳

۲-۳-مروری بر الگوریتمهای خوشه بندی در داد های عظیم. ۱۳

۲-۳-۱- الگوریتمهای خوشه بندی بر مبنای شناسه. ۱۴

۲-۳-۲- الگوریتم خوشه بندی با کوچکترین شناسه(LIC) 14

۲-۳-۳- الگوریتم تشکیل d خوشه بیشینه-کمینه. ۱۵

۲-۳-۴- الگوریتمهای خوشه بندی بر مبنای اتصال. ۱۵

۲-۳-۵- الگوریتم خوشه بندی بزرگترین اتصال (HCC) 16

۲-۳-۶- الگوریتم خوشه بندیKCONID.. 16

۲-۳-۷- الگوریتم خوشه بندی تطبیقی تعادل بار خوشه. ۱۷

۲-۳-۸- الگوریتم خوشه بندی تطبیقی چندگامی.. ۱۷

۲-۳-۹- الگوریتمهای خوشه بندی با آگاهی از تحرک.. ۱۸

۲-۳-۱۰- الگوریتم خوشه بندی d گامی بر مبنای تحرک.. ۱۸

۲-۳-۱۱- الگوریتم خوشه بندی با معیاری بر مبنای تحرک.. ۱۹

۲-۳-۱۲- الگوریتم خوشه بندی تطبیقی با چهارچوبی بر مبنای تحرک.. ۱۹

۲-۳-۱۳- الگوریتمهای خوشه بندی بر مبنای هزینه کمتر برای نگهداری خوشه. ۲۰

۲-۳-۱۴- الگوریتم خوشه بندی کمترین تغییر خوشه (LCC) 20

۲-۳-۱۵- الگوریتم خوشه بندی تطبیقی برای شبکه بیسیم متحرک.. ۲۱

۲-۳-۱۶- الگوریتم خوشه بندی وزندار بر مبنای آنتروپی.. ۲۳

۲-۴-برخی ازکارهای انجام شده تا سال ۲۰۲۰٫ ۲۳

۲-۵-داده کاوی انجام شده در نرم افزار Weka. 27

۳-فصل سوم      32

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

۳-۲-مروري تاريخي بر پديده استعمار ۳۳

۳-۳-الگوريتم رقابت استعماری.. ۳۷

۳-۳-۱- شکل دهي امپراطوري‌هاي اوليه. ۳۹

۳-۴-مدل‌سازي سياست جذب: حرکت مستعمره‌ها به سمت امپرياليست.. ۴۳

۳-۴-۱- جابجايي موقعيت مستعمره و امپرياليست.. ۴۶

۳-۴-۲- قدرت کل يک امپراطوري.. ۴۷

۳-۴-۳- رقابت استعماري.. ۴۷

۳-۴-۴- سقوط امپراطوري‌هاي ضعيف.. ۵۱

۳-۴-۵- همگرايي.. ۵۱

۳-۵-خوشه بندی C میانگین فازی.. ۵۳

۳-۶-روش کار ۵۹

۳-۷-مجموعه داده مورد استفاده ۶۰

۴-فصل چهارم نتایج    62

۴-۱-مقدمه        63

۴-۲-معرفی مجموعه داده‌ها ۶۴

۴-۲-۱- داده‌های ساختگی.. ۶۴

۴-۲-۲- داده‌های استاندارد با حجم کم. ۶۶

۴-۲-۳- داده‌های شبکه. ۶۷

۴-۲-۴- خوشه بندی محلی داده‌های ساختگی.. ۶۸

۴-۲-۵- خوشه بندی محلی داده‌های واقعی.. ۷۳

۴-۲-۶- ارزیابی خوشه بندی توزیع‌شده ۷۴

۴-۳-مقایسه  75

۴-۴-نتیجه گیری………………………………………………………………………………………………………………………….. …………………………………………………………………………………………… ۷۷

۵-فصل پنجم ۷۸

۵-۱-نتیجه گیری………………………………………………………………………………………………………………………….. …………………………………………………………………………………………… ۷۹

۵-۲-پیشنهادات   80

فهرست اشکال

 عنوان                                                                                                                              صفحه       

شکل ‏۲‑۱  ساختار خوشه ها در یک شبکه ویژه سیار. ۱۵

شکل ‏۲‑۲ دو مرحله مدل سازی امتیاز دهی رفتاری(Liu, P., et al. (2007).) 27

شکل ‏۳‑۱ اعمال سياست جذب از طرف استعمارگران بر مستعمرات.. ۳۷

شکل ‏۳‑۲ فلوچارت الگوريتم استعماری.. ۳۹

شکل ‏۳‑۳ چگونگي شکل‌گيري امپراطوري‌هاي اوليه. ۴۴

شکل ‏۳‑۴ شماي کلي حرکت مستعمرات به سمت امپرياليست. ۴۵

شکل ‏۳‑۵  حرکت واقعي مستعمرات به سمت امپرياليست.. ۴۶

شکل ‏۳‑۶ تغيير جاي استعمارگر و مستعمره ۴۸

شکل ‏۳‑۷ کل امپراطوري، پس از تغيير موقعيت‌ها ۴۸

شکل ‏۳‑۸ شماي کلي رقابت استعماري: امپراطوري‌هاي بزرگ‌تر، با احتمال بيشتري، مستعمرات امپراطوري‌هاي ديگر را تصاحب مي‌کنند. ۴۹

شکل ‏۳‑۹  سقوط امپراطوري‌ ضعيف؛ امپراطوري شماره ۴، به علت از دست دادن کليه مستعمراتش، ديگر قدرتي براي رقابت ندارد و بايد از ميان بقيه امپراطوري‌ها حذف شود. ۵۳

شکل ‏۳‑۱۰ شبه کد مربوط به الگوريتم رقابت استعماري.. ۵۴

شکل‏۳‑۱۱:روش کلی کار. ۶۱

شکل ‏۴‑۱ مجموعه داده‌های ساختگی: آتش‌بازی (a) و هلال‌ها (b) 67

شکل ‏۴‑۲ خوشه بندی داده‌های «هلال‌ها» توسط الگوریتم  فازی  با پارامترهای مختلف.. ۷۱

شکل ‏۴‑۳ خوشه بندی داده‌های «هلال‌ها» توسط الگوریتم  رقابت استعماری  با پارامترهای مختلف.. ۷۲

شکل ‏۴‑۴  خوشه بندی داده‌های «آتش‌بازی» توسط الگوریتم  فازی  با پارامترهای مختلف.. ۷۳

شکل ‏۴‑۵ خوشه بندی داده‌های «آتش‌بازی» توسط الگوریتم  رقابت استعماری  با پارامترهای مختلف.. ۷۴

شکل ‏۴‑۶:مقایسه درصد صحت سه طبقه بند. ۷۸

شکل ‏۴‑۷: درصد صحت طبقه بندهای موردنظر در روش پیشنهادی(FCM) و کار(Pedregosa, F., et al. (2011).) 79

فهرست جداول

عنوان                                                                                                                         صفحه        

جدول ‏۲‑۱:مرور کلی بر کاهای پیشین.. ۴۲

جدول ‏۳‑۱: خصوصیات مجموعه داده ۷۳

جدول ‏۴‑۱ مجموعه داده‌های ساختگی.. ۷۷

جدول ‏۴‑۲ خلاصه اطلاعات مجموعه داده‌های UCI 78

جدول ‏۴‑۳ خلاصه‌ی اطلاعات زیرمجموعه‌ی KDDCup99. 80

جدول ‏۴‑۴ معیارهای مختلف ارزیابی خوشه بندی داده‌های با الگوریتم‌های  فازی  و  رقابت استعماری.. ۸۴

جدول ‏۴‑۵ خوشه بندی مجموعه داده‌های UCI با روش‌های مبتنی بر چگالی.. ۸۶

چکيده

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

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

۱-       فصل اول:
مقدمه

  1. ۱-۱- مقدمه

داده‌های حجیم به مجموعه داده‌هایی گفته می‌شود که مدیریت، کنترل و پردازش آن‌ها فراتر از توانایی ابزارهای نرم‌افزاری در یک ‌زمان مورد انتظار باشد. این داده‌ها به‌قدری بزرگ و حجیم هستند که با ابزارهای سنتی، تکنیک‌ها و ابزارهای معمول داده‌کاوی قابل‌تحلیل، آنالیز و داده‌کاوی نیستند(Chen, Mao et al. 2014). تحلیل، آنالیز دقیق و نهایتاً داده‌کاوی کلان داده‌ها افق بسیار وسیعی را در جهت بهبود خدمات سلامت، رشد اقتصادی و ارائه خدمات بهتر اجتماعی فراهم می‌نماید. تحلیل و نمایش این نوع داده‌ها چالشی بزرگ محسوب می‌شود.

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

خوشه بندی مبتنی بر چگالی با نام الگوریتم[۱]DBSCAN عجین شده است. این الگوریتم در سال ۱۹۹۶ توسط استر[۲] و همکارانش در (Ester, Kriegel et al. 1996)ارائه شد. هدف این الگوریتم شناسایی خوشه هایی با شکل دلخواه در محیط نویزی است. در این فصل ابتدا به بیان مسئله پرداخته می‌شود سپس اهداف پژوهش و نوآوری‌های پژوهش بیان می‌شود و در پایان ساختار کلی پایان‌نامه مشخص می‌شود.

در تجزیه و تحلیل خوشه یا خوشه بندی، گروه بندی مجموعه ای از اشیاء انجام می‌شود اینکار به این صورت است که اشیاء در یک گروه (به نام خوشه) در مقایسه با دیگر دسته‌ها (خوشه ها) مشابه تر هستند. این وظیفه اصلی داده کاوی اکتشافی و یک روش معمول برای تجزیه و تحلیل داده‌های آماری است که در بسیاری از زمینه‌ها از جمله یادگیری ماشین(Manogaran et al., 2018)، تشخیص الگو (Wen, Zhou, & Yang, 2019)،تجزیه و تحلیل تصویر(Zhong, Ma, soon Ong, Zhu, & Zhang, 2018)، بازیابی اطلاعات(Passalis & Tefas, 2018)، بیوانفورماتیک(Zou, Lin, Jiang, Liu, & Zeng, 2018)، فشرده سازی داده‌ها (Marchetti, Nguyen, Braverman, & Cressie, 2018)و گرافیک کامپیوتری (Kwon et al., 2018)استفاده می‌شود.

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

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

   مدل‌های متصل: به عنوان مثال، خوشه بندی سلسله مراتبی، مدل‌هایی براساس فاصله متصل را ایجاد می‌کند.

   مدل‌های مرکزی: به عنوان مثال، الگوریتم k-means ، هر خوشه را با یک بردار متوسط نشان می‌دهد.

   مدل‌های توزیع: خوشه ها با استفاده از توزیع‌های آماری، مانند توزیع نرمال چند متغیره که در الگوریتم حداکثر انتظار ، استفاده شده‌است.

   مدلهای تراکم: به عنوان مثال، DBSCAN و OPTICS خوشه را به عنوان مناطق متراکم متصل در فضای داده تعریف می‌کنند.

   مدل‌های زیر فضایی: در biclustering (که به عنوان خوشه مشترک یا خوشه ای دو حالت شناخته می‌شود)، خوشه ها با هر دو اعضای خوشه و ویژگی‌های مرتبط مدل‌سازی می‌شوند.

   مدل‌های گروهی: برخی از الگوریتم‌ها یک مدل تصحیح شده برای نتایج خود را ارائه نمی‌دهند و فقط اطلاعات گروه بندی را ارائه می‌دهند.

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

  مدل‌های عصبی: شبکه عصبی بدون نظارت، که شناخته شده‌ترین آنها نگاشت خود سازمان ده است و معمولاً این مدل‌ها می‌توانند به عنوان مشابه با یک یا چند مدل فوق شامل مدل‌های زیر فضایی، زمانی که شبکه‌های عصبی یک فرم تجزیه و تحلیل مؤلفه اصلی یا مستقل تجزیه و تحلیل المان می‌باشد .

“خوشه بندی” اساسا مجموعه ای از خوشه ها است که معمولاً شامل تمام اشیاء در مجموعه داده‌ها می‌شود. علاوه بر این، می‌توان رابطه خوشه ها را به یکدیگر تعریف کند، به عنوان مثال، سلسله مراتب خوشه های تعبیه شده در یکدیگر.

خوشه بندی را می‌توان براساس سختی تمایز به صورت زیر تفکیک کرد:

   خوشه بندی سخت: هر شیء متعلق به یک خوشه است یا نه.

   خوشه بندی نرم (همچنین: خوشه فازی): هر شیء با درجه خاصی به هر خوشه متعلق است (به عنوان مثال، احتمال وابستگی به خوشه)

الگوریتم خوشه بندی فازی یا FCM یکی از قدرتمندترین روشهای خوشه بندی است که توفیقات چشمگیری در حل مسائل مختلف داشته است امایکی از مشکلات این الگوریتم، نحوه یادگیری آن است که مبتنی بر روشهای کلاسیک بوده که بر اساس مشتق عمل میکند. این الگوریتم ها مشکل گرفتار شدن در مینیمم های محلی را دارند. یکی از راه حل هایی که برای رفع این مشکل پیشنهاد شده است، استفاده از الگوریتم های فراابتکاری برای آموزش FCM است.

۱- چگونه میتوان مسئله آموزش FCM را به یک مسئله بهینه سازی تبدیل نمود؟

۲- روش مناسب برای تنظیم پارامترهای FCM بر اساس الگوریتم رقابت استعماری چیست؟

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

تبدیل مسئله آموزش FCM به یک مسئله بهینه سازی برای حل آن توسط الگوریتم های فراابتکاری

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

  1. برای تحلیل نیاز به عامل انسانی را حداقل می‌کند.
  2. کشف خوشه های بهینه با شکل‌های مختلف نمونه اولیه و انعطاف‌پذیر بودن در مقابل خوشه هایی با چگالی مختلف.
  3. شناسایی نمونه‌های با نویز جهت خوشه بندی.
  4. قابلیت مقیاس‌پذیری بالا و کم کردن زمان تحلیل به دلیل اینکه چند بار الگوریتم بر روی داده‌های اجرا نمی‌شود.

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

۲-       فصل دوم:
مفاهیم پیش‌زمینه و مروری بر ادبیات

۲-۱- مقدمه

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

۲-۲- تعاریف، اصول و مبانی نظری

در این قسمت جهت روشن بودن ادامه مباحث در قسمت‌های بعدی، مفاهیم مطرح در مباحث خوشه بندی داده‌های عظیم مطرح می‌گردند.

۲-۲-۱- خوشه بندی

در منابع مختلف برای خوشه بندی تعاریف گوناگونی ارائه داده‌اند. برخی از تعاریف ارائه‌شده برای خوشه بندی از این قرارند:

  • خوشه بندی یا تحلیل خوشه های داده به عملیات تقسیم داده‌ها به تعدادی گروه (خوشه) جهت خلاصه‌سازی یا بهبود درک آن‌ها گفته می‌شود. طی عملیات خوشه بندی، سعی بر آن شده که داده‌های مشابه در یک خوشه قرار بگیرند.(Fahad, Alshatri et al. 2014)
  • مسئله خوشه بندی مسئله قرار دادن داده‌ها در مجموعه‌ای گروه (خوشه) است به‌صورتی که داده‌های یک خوشه به یکدیگر شبیه‌تر باشند تا داده‌های خوشه های دیگر.(Jain 2010)

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

با قرار دادن تعداد زیادی نمونه در تعداد بسیار کمتری خوشه، مسئله ساده می‌شود. خوشه بندی شکلی از مدل کردن داده است. بدین ترتیب ریشه خوشه بندی را می‌توان در ریاضیات و آمار جستجو کرد. از دید یادگیری ماشین، خوشه بندی به پیدا کردن الگوهای مخفی مرتبط می‌شود و به جستجو به دنبال خوشه ها یادگیری بی ناظر به‌حساب می‌آید. بدین ترتیب خوشه بندی یادگیری بی ناظر یک مفهوم مخفی در داده است. با اعمال خوشه بندی در کاربردهای داده‌کاوی سه پیچیدگی به مسئله افزوده می‌گردد: (الف) داده‌های زیاد (ب) نمونه‌هایی با خصیصه‌های زیاد (ج) خصیصه‌هایی با انواع مختلف. این پیچیدگی‌ها نیازمندی‌های محاسباتی بسیار زیادی دارند که برای روش‌های خوشه بندی کلاسیک چالش‌های بزرگی ایجاد می‌کند(Rana, Jasola et al. 2011). در این پژوهش تمرکز بر پیچیدگی اول، یعنی داده‌های زیاد در ترافیک شبکه بوده است.

۲-۲-۲- داده‌های عظیم

داده‌های عظیم واژه‌ای است که برای توصیف مجموعه داده‌هایی با اندازه زیاد، تنوع فراوان و ساختار پیچیده به کار می‌رود به‌طوری‌که ذخیره‌سازی، تحلیل و به تصویر کشیدن آن‌ها با سختی مواجه است. به فرآیند پژوهش در مقادیر عظیم داده جهت افشای الگوهای پنهان و هم‌بستگی‌های مخفی در آن‌ها نیز تحلیل داده‌های عظیم گفته می‌شود(Chen, Mao et al. 2014). درواقع، در هر برهه‌ای از زمان می‌توان وجود داده‌هایی را متصور شد که پردازش آن‌ها فراتر از توانایی‌های پردازشی رایانه‌های متداول است؛ اما آنچه باعث مطرح‌شدن هر چه بیشتر داده‌های عظیم در زمان حال کرده، تسهیل امکان پردازش این نوع داده‌ها در محیط‌های توزیع‌شده است.

۲-۳- مروری بر الگوریتم­های خوشه بندی در داد های عظیم

در این بخش مفهوم خوشه بندی در داد های عظیم در چندین کار تحقیقاتی بررسی می­شود. می­توان این تحقیقات را به ۳ روند اصلی از نظر پیشرفت تقسیم نمود (Wang, W., et al. (1997)). گروه نخست تحقیقات، روی درجه اتصال بالا تمرکز داشتند (Das, S., & Sil, S. (2010))گروه دوم روی کشف گره­های با شناسه (ID[3]) کوچکتر تمرکز کردند (Mishra, D., & Naik, B. (2019)) ترکیب این دو نوع از الگوریتم ها نیز بکار برده شده است. گروه سوم بر اساس وزن گره­ها است که مقدار ویژگی­های گره را برای انتخاب سرخوشه می­گیرد (Doğan, B., & Korürek, M. (2012). Emami, H., & Derakhshan, F. (2015))

شکل ۲-۱، نمونه­ای از ساختار خوشه ها را در یک شبکه ویژه سیار نشان می­دهد. در این خوشه بندی ۳ نوع گره وجود دارد: گره سرخوشه، گره معمولی و گره دروازه[۴]. گره­های دروازه گره­هایی هستند که به چند خوشه تعلق دارند.

گره سرخوشهگره معمولیگره دروازه

شکل ‏۲‑۱  ساختار خوشه ها در یک شبکه ویژه سیار

در اینجا یک تقسیم­بندی کلی برای الگوریتم­های خوشه بندی در داد های عظیم خواهیم داشت( Emami, H., & Derakhshan, F. (2015).)

۲-۳-۱- الگوریتم­های خوشه بندی بر مبنای شناسه

در این نوع الگوریتم­ها به هر گره یک شناسه اختصاص داده می­شود و انتخاب سرخوشه بر مبنای شناسه گره­ها صورت می­گیرد.

۲-۳-۲- الگوریتم خوشه بندی با کوچکترین شناسه(LIC)[5]

در این الگوریتم (Doğan, B., & Korürek, M. (2012))به هر گره یک شناسه منحصر به فرد اختصاص داده می­شود.گره­ها شناسه همسایگان و سرخوشه خود را می­شناسند.سرخوشه و عضوها به روش زیر انتخاب می­شوند:

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

۲-۳-۳- الگوریتم تشکیل d خوشه بیشینه-کمینه[۶]

تعمیم تعریف خوشه به یک مجموعه از گره­هاست که به میزان dگام دور از یک سرخوشه هستند. گره­ها بر مبنای شناسه­شان برای سرخوشه شدن داوطلب می­شوند.اگر یک گره A در d-همسایگی گره B بزرگترین باشد، آنگاه گره A به عنوان سرخوشه انتخاب می­شود، حتی اگر چه ممکن است در d-همسایگی خود بزرگترین نباشد.این روش مقدار داده­ای که باید هنگام مبادله از یک خوشه به خوشه دیگر بیرون رود را کمینه می­کند (Doğan, B., & Korürek, M. (2012)).

۲-۳-۴- الگوریتم­های خوشه بندی بر مبنای اتصال

روش انتخاب سرخوشه در این نوع از الگوریتم­ها بر مبنای درجه اتصال گره­ها می­باشد. منظور از درجه اتصال هر گره شمار گره­هایی است که در دامنه در دسترس آن گره قرار دارند.

۲-۳-۵- الگوریتم خوشه بندی بزرگترین اتصال (HCC)[7]

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

همسایه­های هر خوشه، عضوهای آن خوشه می­شوند و نمی­توانند دخالت بیشتری در فرآیند انتخاب سرخوشه نمایند و تنها یک سرخوشه برای هر خوشه مجاز است. هنگامی که سرخوشه بطور مستقیم به هریک از همسایگانش در خوشه متصل باشد، هر دو گره در یک خوشه حداکثر دو گام از هم دورند. بطور کلی هر گره یا سرخوشه می­شود، یا یک گره معمولی باقی می­ماند ()Doğan, B., & Korürek, M. (2012)).

۲-۳-۶- الگوریتم خوشه بندیKCONID[8]

ترکیب دو الگوریتم خوشه بندی اکتشافی کوچکترین ID و بزرگترین درجه است.به منظور انتخاب سرخوشه، اتصال به عنوان اولویت نخست و ID کوچکتر به عنوان اولویت دوم بررسی می­شود. خوشه ها در این روش (Das, S., & Sil, S. (2010) بوسیله یک سرخوشه تشکیل می­شوند و همه گره­ها در فاصله حداکثر kگام از سرخوشه قرار می­گیرند.

در شروع الگوریتم، یک گره درخواست خوشه بندی به تمام گره­ها می­فرستد. هنگامی که k=1 اتصال گره، همان درجه گره است.

هر گره در شبکه با یک جفت did=(d,ID) تعیین می­شود. dدرجه اتصال گره  و ID شناسه گره است.

یک گره به عنوان سرخوشه انتخاب می­شود، اگر بزرگترین اتصال را داشته باشد و در موارد تساوی اولویت با کوچکترین شناسه است.

۲-۳-۷- الگوریتم خوشه بندی تطبیقی تعادل بار خوشه[۹]

در روش خوشه بندی HCC یک سرخوشه هنگامی که به تعداد زیادی میزبان خدمات می­دهد، ممکن است انرژی­اش تمام شود، این مطلوب نیست و سرخوشه یک تنگنا می­شود.

در این روش (Mishra, D., & Naik, B. (2019).)، در فرمت پیام HELLO یک بخش انتخاب[۱۰] وجود دارد؛ بطوریکه اگر یک گره فرستنده، سرخوشه باشد، تعداد گره­های عضو خوشه­اش را به عنوان مقدار انتخاب خواهد نشاند. اما هنگامی که گره فرستنده سرخوشه نیست و یا اینکه سرخوشه بودن یا نبودن آن مشخص نباشد بخش انتخاب به صفر بازنشانی می­شود.

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

۲-۳-۸- الگوریتم خوشه بندی تطبیقی چند­گامی[۱۱]

یک طرح خوشه بندی چند­هاپی با توانایی تعادل بار است(Emami, H., & Derakhshan, F. (2015)). هر گره بطور دوره­ای اطلاعات درباره شناسه، شناسه سرخوشه، و وضعیت خود (سرخوشه، عضو، دروازه) را به دیگر گره­های همان خوشه پخش می­کند. با این روش هر گره اطلاعات توپولوژی خوشه را بدست می­آورد. هر دروازه نیز بطور دوره­ای اطلاعات را با دروازه­های همسایه در خوشه های مختلف مبادله کرده و به سرخوشه­اش گزارش می­دهد. این روش کران بالا و پایینی روی شمار عضوهای تحت اداره یک سرخوشه می­گذارد.

۲-۳-۹- الگوریتم­های خوشه بندی با آگاهی از تحرک

این الگوریتم­ها خوشه بندی و انتخاب سرخوشه را بر مبنای میزان تحرک گره­ها در شبکه انجام می­دهند.

۲-۳-۱۰- الگوریتم خوشه بندی d گامی بر مبنای تحرک[۱۲]

این الگوریتم (Shim, K. (2013).) یک شبکه ویژه سیار را بر مبنای معیار تحرک به dگام تقسیم می­کند. روش کار بر مبنای معیار تحرک و قطر یک خوشه است و نسبت به تحرک گره تطبیق­پذیر است.

این الگوریتم فرض می­کند که هر گره می­تواند شدت سیگنال دریافتی خودش را اندازه­گیری کند. یک گره می­تواند فاصله خودش تا گره همسایه­اش را تخمین بزند. شدت سیگنال دریافتی قوی نزدیکی بین دو گره را نتیجه می­دهد.

پایداری محلی به منظور انتخاب برخی گره­ها به عنوان سرخوشه محاسبه می­شود. یک گره می­تواند سرخوشه شود اگر بفهمد که در بین همسایه­هایش بیشترین پایداری و ثبات را دارد. اگر یک گره بتواند پیام hello را از دیگر گره­های خوشه های دیگر بشنود، نقش یک دروازه را خواهد داشت. در غیر اینصورت یک گره معمولی در خوشه است

۲-۳-۱۱- الگوریتم خوشه بندی با معیاری بر مبنای تحرک[۱۳]

این الگوریتم (Wang, W., et al. (1997).)، یک معیار تحرک محلی برای فرآیند تشکیل خوشه پیشنهاد می­دهد به قسمی که گره­های متحرک با سرعت کمتر نسبت به همسایه­هایشان برای سرخوشه شدن شانس بیشتر دارند. با محاسبه واریانس سرعت یک گره متحرک نسبت به هر یک از همسایه­هایش، سرعت محلی تجمع یک گره متحرک تخمین زده می­شود. مقدار واریانس پایین نشان می­دهد که این گره نسبت به همسایه­هایش تحرک کمتری دارد. در نتیجه می­تواند به عنوان سرخوشه انتخاب شود.

۲-۳-۱۲- الگوریتم خوشه بندی تطبیقی با چهارچوبی بر مبنای تحرک[۱۴]

تعدادی از گره­های متحرک را به خوشه های چند­گامی بر مبنای اولویت (a,t) تقسیم می­کند(Vinh, N. X., et al. (2009).). اولویت (a,t) نشان می­دهد که هر گره متحرک در یک خوشه، یک مسیر به هر گره دیگری دارد که روی دوره زمانی t با یک احتمال a صرف نظر از فاصله گام بینشان در دسترس باشد. چهارچوب خوشه بر مبنای یک معماری انطباقی طراحی می­شود که تحرک گره ها درون خوشه ها بطور پویا سازماندهی شود بصورتی که در آن احتمال دسترسی مسیر کراندار و شدت سربار مسیر نیز می تواند بطور موثری مدیریت شود.

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

۲-۳-۱۳- الگوریتم­های خوشه بندی بر مبنای هزینه کمتر برای نگهداری خوشه

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

۲-۳-۱۴- الگوریتم خوشه بندی کمترین تغییر خوشه (LCC)[15]

این الگوریتم (Ting, K. M., et al. (2013).) پیشرفت معنی­داری نسبت به الگوریتم­های LIC و HCC دارد، زیرا هزینه نگهداری خوشه در آن بررسی می­شود. بیشتر پروتکل­ها فرآیند خوشه بندی را بصورت دوره­ای اجرا می­کنند، و برای برآورده کردن شرایط خاص سرخوشه ها، خوشه بندی مجدد را انجام می­دهند. در HCC، خوشه بندی بصورت دوره­ای برای چک کردن “بزرگترین درجه گره محلی” از منظر یک سرخوشه اجرا می­شود. هنگامی که یک سرخوشه گره عضوی با درجه بالاتر پیدا می­کند، مجبور است نقش سرخوشه­ای خود را ترک کند. این مکانیسم شامل خوشه بندی­های تکراری است. در LCC الگوریتم خوشه بندی به دو مرحله تقسیم می­شود: تشکیل خوشه و نگهداری خوشه. مرحله تشکیل خوشه به سادگی مانند LIC انجام می­شود، یعنی گره­های متحرک اولیه با کوچکترین شناسه در همسایگی­هایشان به عنوان سرخوشه انتخاب می­شوند. خوشه بندی مجدد رویدادگرا است و فقط در دو مورد درخواست می­شود:

  • هنگامیکه دو سرخوشه به درون دامنه در دسترس یکدیگر می­رسند،  یکی باید نقش سرخوشه­ای خود را رها کند.
  • هنگامیکه یک گره نمی­تواند به هیچ  خوشه­ای دسترسی داشته باشد، ساختار خوشه را برای شبکه مطابق با LIC بازسازی می­کند.

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

۲-۳-۱۵- الگوریتم خوشه بندی تطبیقی برای شبکه بی­سیم متحرک[۱۶]

این الگوریتم (Ting, K. M., et al. (2013).) سربار را برای مجموعه­های کوچک تضمین می­کند، زیرا هر گره متحرک فقط یک پیام برای ساخت خوشه پخش می­کند. در این طرح خوشه بندی انطباقی، هر گره متحرک i، شناسه خودش و شناسه گره­های در همسایگی مستقیمش را در یک مجموعه Gi نگهداری می­کند. هر گره متحرک با کوچکترین شناسه در منطقه محلی­اش به عنوان سرخوشه اعلان می­شود و شناسه­اش را به عنوان شناسه خوشه قرار می­دهد ([۱۷]CID). اطلاعات شناسه خوشه شامل شناسه یک گره متحرک و شناسه خوشه است. هنگامی که گره متحرک i اطلاعات شناسه را از گره همسایه j دریافت می­کند، j را از مجموعه Gi­اش پاک می­کند. اگر اطلاعات شناسه خوشه از j ادعای سرخوشه بودن باشد، گره متحرک شناسه خوشه خودش را چک می­کند. اگر شناسه ­اش رضایت­بخش نباشد (هنوز هیچ خوشه­ای نداشته باشد) یا بزرگتر از شناسه (شناسه خوشه) j باشد، j را به عنوان سرخوشه قرار می­دهد. فرآیند تا هنگامی که همه گره­های متحرک به خوشه­ای دسترسی داشته باشند ادامه می­یابد. سپس تشکیل خوشه پایان یافته، سرخوشه ها به مدت طولانی در مرحله نگهداری خوشه استفاده نمی­شوند. در مرحله نگهداری، هنگامی که گره متحرک i فاصله­اش از گره j در همان خوشه بیشتر از ۲ گاممی­شود، یک فرآیند نگهداری خوشه را درخواست می­کند. اگر i همسایه مستقیم گره با بزرگترین اتصال خوشه ورودی در همان خوشه باشد، در خوشه مانده و گره j را حذف می­کند، در غیر اینصورت به یک خوشه همسایه وصل می­شود. به محض اینکه خوشه مناسبی برای پیوستن وجود نداشته باشد، یک خوشه جدید را برای پوشاندن خودش تشکیل می­دهد. از آنجاییکه این فرآیند احتمالا خوشه های جدید را بدون حذف خوشه یا فرآیند ادغام تشکیل می­دهد، با پیشرفت زمان اندازه خوشه کاهش و شمار خوشه ها افزایش می­یابد. سرانجام، تقریبا هر خوشه یک خوشه با گره تنها تشکیل می­دهد و ساختار خوشه ناپدید می­شود.

۲-۳-۱۶- الگوریتم خوشه بندی وزندار بر مبنای آنتروپی[۱۸]

در WCAتحرک بالای گره باعث تکرار بالای تجدید پیوستگی[۱۹] می شود که سربار شبکه را افزایش می­دهد. تکرار بالاتر تجدید پیوستگی منجر به تجدید محاسبات بیشتر تخصیص خوشه و در نتیجه افزایش سربار ارتباطات می­شود. الگوریتم خوشه بندی بر مبنای آنتروپی (Shim, K. (2013).) اشکال WCAرا برطرف می­کند و یک شبکه با پایداری بیشتر را تشکیل می­دهد. این الگوریتم از یک مدل بر مبنای آنتروپی برای ارزیابی پایداری مسیر در شبکه­های ادهاک و انتخاب سرخوشه استفاده می­کند. آنتروپی عدم اطمینان را نشان می­دهد و اندازه­ای برای بی­نظمی در یک سیستم است. بنابراین یک شاخص بهتر برای پایداری و تحرک شبکه ویژه سیار است.

۲-۴- برخی ازکارهای انجام شده تا سال ۲۰۲۰

مديريت ارتباط با مشتري (CRM) در برگيرنده مجموعه اي از فرايند ها مي باشد و سازمانها را قادر (CRM) مديريت ارتباط با مشتري مي سازد تا از استراتژيهاي كسب و كار در جهت ايجاد روابط بلند مدت و سودآور با مشتريان خاص پشتيباني نمايند(Wang, W., et al. (1997).). رشد سريع اينترنت و تكنولوژي هاي وابته به طور قابل توجهاي فرصت هاي را براي بازاريابي افزايش داده است و راه هاي برقراري ارتباط با مشتري نيز تغير يافته است.

اگرچهCRM به طور گسترده به عنوان يك روش مهم كسب و كار شناخته شده است، يك تعريف پذيرفته شده جهاني در مورد آن موجود ندارد نگاي در سال ۲۰۰۵ CRM را به عنوان “رويكردي سازماني براي فهميدن و تاثيرگذاري بر رفتار مشتري از طريق ارتباط معني دار به منظور بهبود جذب مشتري، حفظ مشتري، وفاداري مشتري و سودآوري مشتري” تعريف مي كند(Emami, H., & Derakhshan, F. (2015).)

همچنين كين سايد  CRM را به عنوان “استفاده استراتژيك از اطلاعات، فرايندها، تكنولوژي و افراد براي مديريت كردن روابط مشتري با سازمان” نگريسته است. اين تعاريف بر اهميت در نظر گرفتن CRM  به عنوان فرايند جامع جذب و حفظ مشتري جهت بيشيه سازي ارزش مشتري براي سازمان تاكيد دارند.

هسيه  در سال ۲۰۰۴ تحقيقي تحت عنوان مدل يكپارچه داده كاوي و رتبه بندي رفتاري براي تجزيه و تحليل رفتار مشتريان بانك پرداخته است. در اين تحقيق به بررسي الگوي رفتاري مشتريان با استفاد از شبكه هاي عصبي و روش خود سازمان دهنده، مشتريان بانك طبقه بندي شده اند و با بررسي رفتار مالي مشتريان، گروه بندي از مشتريان سود آور ارائه گرديده است.

در اين تحقيق مشتريان بانك را به سه گروه اصلي تقسيم مي نمايد. اين مطالعه نشان مي دهد كه شناسايي مشخصه هاي مشتريان با استفاده از مدل رتبه بندي رفتاري مفيد مي باشد و توسعه استراتژي هاي بازاريابي را تسهيل مي نمايد. همانطور که در شکل ۳-۱ مشاهده می شود، دراین مطالعه یک رویکرد دو مرحله ای برای تجزیه و تحلیل امتیاز دهی رفتاری دانش ضمنی با استفاده از حساب مشتری بانک و داده تراکنشی  ارائه شده است.

موضوعات مورد بحث  دراین مطالعه شامل پیش پردازش داده ها، مدل سازی رتبه بندي رفتار مشتری، تجزیه و تحلیل حساسیت اهمیت نسبی صفات کمکی پروفایل مشتری، و دو مرحله مدل رتبه بندي مربوط رفتاری است.

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

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

بخش دوم دوم عمل استخراج داده ها ی است که برای تجزیه و تحلیل مفید در نظر گرفته شدند. بخش سوم عمل استفاده از آمار ساده برای محاسبه مجموع پیش بینی جدید رتبه بندی رفتاری است(Liu, P., et al. (2007).).

شکل ‏۲‑۲ دو مرحله مدل سازی امتیاز دهی رفتاری(Liu, P., et al. (2007).)

حسين جواهري در سال ۲۰۰۸ به ارائه مدلي پاسخ دهنده در بازاريابي مستقيم جهت پايان نامه كارشناسي ارشد پرداخته است. روش اين تحقيق مبتني بر داده كاوي جهت شناسايي بازار هدف مي باشد. هدف اين تحقيق شناسايي آن دسته از مشتريان بانك پارسيان مي باشند كه با احتمال بيشتري به محصولات ارائه شده پاسخ مثبت مي دهند.

مدل پاسخ دهنده نوعي روش دسته بندي باينري(صفر و يك)  مي باشد كه در اين مدل مشتريان به دو دسته مشتريان پاسخ دهنده و مشتريان غير پاسخ دهنده تقسيم بندي مي گردند(Ng, R. T. and J. Han (2002).).

کامیلوریچ در سال۲۰۰۸ در مقاله خود کاربردهای داده کاوی برایCRM در حوزه ارتباطات تلفنی بیان نموده اسد .در این مقاله ذکر شده که به دلیل حجم انبوه داده های تولید ده توسط شرکتهای مخابراتی، این اطلاعات را نمیتوان توسط روشهای سنتی و تحلیل استی تجربه و تحلیل نمود.  بنابراین روشهای مختلفی داده کاوی باید اعمال گردند.روشهای داده کاوی به این شرکتها کمک می کند تا بهتر مشتریان خود را بشناسند.و سپس دو کاربرد داده کاوی برای شرکتهای مخابراتی معرفی شد. این کاربردها شانل بخش بندی مشتریان و پیش بینی نرخ پولی که مشتریان در طول یک دوره از دست می دهند(O’callaghan, L., et al. (2002).).

نگاي  در سال ۲۰۰۹ به مرور و دسته بندي ادبيات در زمينه كاربردهاي داده كاوي در مديريت ارتباط با مشتري پرداخته است. در اين تحقيق ضمن بيان ضرورت كاربردهاي تكنيك هاي داده كاوي در مديريت ارتباط با مشتري به دسته بندي تكنيك ها و مقايسه روش هاي داده كاوي در اين زمينه پرداخته است. در انتها چارچوبي جهت انجام تحقيقات آتي در زمينه كاربردهاي داده كاوي در حوزه CRM ارائه شده است(Ott, J. and G. Lathrop (1990).).

۲-۵- داده کاوی انجام شده در نرم افزار Weka

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

گان[۲۱] و همکارانش در مقاله ای، الگوریتم فازی k-mode را پیشنهاد دادند که این الگوریتم به عنوان یک خوشه بند میتواند مورد استفاده قرار گیرد. در این الگوریتم برای یافتن ماتریس های تابع عضویت فازی مناسب که بتواند توابع هدف فازی را حداقل نماید، الگوریتم هیبرید fuzzy k-mode و  ژنتیک ارائه شده است. این الگوریتم روی مجموعه داده سویا که شامل ۴۷ نمونه و هر نمونه شامل ۳۵ ویژگی است اعمال شده است. تعداد خوشه ها ۴ عدد در نظر گرفته شده و بعد از ۱۰۰ بار اجرای الگوریتم، تمامی اشیا در خوشه های مربوطه به درستی قرار داده شده بودند(Gan, Wu, & Yang, 2009).

داس[۲۲] و همکاران در مقاله ای دیگر یک روش خوشه بندی فازی جدید را برای گروه بندی خودکار پیکسل های یک عکس در نواحی مختلف در حالیکه تعداد خوشه ها از قبل مشخص نیست ارائه دادند. کار خوشه بندی در فضای شدت نور، به عنوان یک مسئله بهینه سازی فرموله شده است. در این مقاله از الگوریتم تکامل تفاضلی برای تعیین خودکار تعداد خوشه ها و همچنین تعیین مرکز خوشه ها استفاده شده است. مقایسه روش آنها با روشهای خوشه بندی فازی-ژنتیک و الگوریتم کلاسیک FCM، نشان دهنده برتری الگوریتم پیشنهادی از نظر سرعت، دقت و پایداری است(Das, Konar, & Chakraborty, 2006).

ژائو در مقاله ای، روشی بر اساس الگوریتم مورچگان برای خوشه بندی n شی در k خوشه ارائه نمود. این الگوریتم از بروزرسانی فرومون کلی و اطلاعات اکتشافی برای ایجاد راه حل های خوشه بندی و اپراتور تقاطع یکنواخت برای بهبود بیشتر جواب های کشف شده توسط مورچه ها استفاده نمود. این الگوریتم روی مجموعه داده IRIS اعمال شده که شامل ۱۵۰ نمونه از ۳ نوع گل زنبق است. هر نمونه با ۴ ویژگی توصیف میشود. نتایج نشان داد که این الگوریتم تعداد ارزیابی توابع هزینه را نسبت به الگوریتم ژنتیک به اندازه ۶ برابر کاهش داده است. همچنین زمان CPU نیز به اندازه ۸۵% کاهش را نشان میدهد(Zhao, 2007).

توماس و همکارانش در مقاله ای روشی برای خوشه بندی بر اساس کمینه سازی مدل FCM ارائه نمودند. آنها دو روش مجزا برای کمینه نمودن تابع هزینه بازنویسی شده FCM با استفاده از PSO ارائه دادند. در روش PSO-V هر ذره یک مرکز خوشه را نشان میدهد. در PSO-U  هر ذره یک مقدار تابع عضویت غیرمقیاس و غیرنرمال شده را نشان میدهد. تعداد حداکثر تکرار برابر ۵۰ در نظر گرفته شده و با ۱۰ ذره، تعداد کل ارزیابی تابع هزینه ۵۰۰ در نظر گرفته شده و ۱۰۰ بار الگوریتم اجرا شده است. نشان داده شده است که نقطه بهینه سراسری در ۱% نتایج AO ، در ۲۰% نتایج ACO و در ۸۵% نتایج روش پیشنهادی توسط الگوریتم کشف شده است(Runkler & Katz, 2006).

الگوریتم کلونی زنبور عسل که توسط کارابوگا[۲۳] به عنوان یک روش بهینه سازی عددی مطرح شده است. عملکرد این الگوریتم در مسائل بنچ مارک طبقه بندی مورد ارزیابی قرار گرفته است. کار طبقه بندی توسط شبکه عصبی و خوشه بندی صورت گرفته است. آنها در این مقاله روشی برای اعمال الگوریتم کلونی زنبور در خوشه بندی فازی ارائه دادند. نتایج اعمال روش روی مجموعه داده Cancer، نشان از بهبود ۲٫۶۵% نتایج ناشی از استفاده از ABC و FCM در مقایسه با FCM استاندارد دارد(Karaboga & Ozturk, 2010).

جدول ‏۲‑۱:مرور کلی تحقیقات انجام شده

عنوان مقالهروشهای بکاررفتهنویسنده(گان)
An integrated data mining and behavioral scoring model for analyzing bank customers.شبكه هاي عصبي و روش خود سازمان دهندههسيه نان چین درسال۲۰۰۴
Response modeling in direct marketing: a data mining based approach for target selectionتجزیه و تحلیل RFM وSVMصدف حسين جواهري در سال ۲۰۰۸
Application of data mining techniques in customer relationship management: A literature review and classificationمرور روشهای داده کاوینگاي  در سال ۲۰۰۹
Optimizated K-means algorithm and application in CRM systemالگوریتم بهینه شده K–meansشیائوپنگ کیان و همکاران در سال ۲۰۱۰
Hybrid Retention Strategy Formulation in Telecom Based on k-means Clustering Analysisخوشه بندی K-Meansلی و همکاران (۲۰۱۱)
Customer Relationship Management in the Hairdressing Industry: An Application of Data Mining Techniquesخوشه بندی k-means ترکیبی با نگاشت خود سازمانده som))وجوتینگ وی و همکاران درسال ۲۰۱۳
Customer Relationship Management Classification Using Data Mining Techniquesچهار طبقه بند J48 ، Naïve Bayes،SVM ،   KNNنتچیر و همکاران در سال ۲۰۱۴
A Review of Different Data Mining Techniques in Customer Segmentationمرور تکنیک­های مختلف خوشه بندی و طبقه بندیتنانه پارسا کرد آسیابی و رضا تولی در سال ۲۰۱۵
An Efficient CRM-Data Mining Framework for the Prediction of Customer Behaviourبیزین و شبکه عصبیفامینا بهاری و همکاران در سال ۲۰۱۵
Using datamining techniques for profiling profitable hotel customers: An application of RFM analysisتجزیه و تحلیل RFMاسلیان دورسون وملتم کابر (۲۰۱۶)
Customer Clustering Using a Combination of Fuzzy C-Means and Genetic Algorithmsخوشه بندی c-means و الگوریتم ژنتیکآذرنوش انصاری  و آرش ریاضی  در سال ۲۰۱۶
Data mining: Techniques for Enhancing Customer Relationship Management in Fast Moving Consumer Goods Industriesتکنیک خوشه بندی توده کردن سلسله مراتبیدکتر رام چاندرا در سال ۲۰۱۶

۳-       فصل سوم

روش پیشنهادی

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

در اين فصل، الگوريتمی براي جستجوي عام معرفي مي‌شود که از رقابت‌هاي استعماري الهام گرفته شده است. این الگوریتم برای نخستین بار توسط معصومه آتش­پز(۱۳۹۲) در پایان­نامه کارشناسی ارشد وی ارائه شده است. بطور خلاصه، اين الگوريتم، از چندين کشور در حالت اوليه شروع مي‌شود. کشورها در حقيقت جوابهاي ممکن مساله هستند و معادل کروموزوم در الگوريتم ژنتيک و ذره در بهينه‌سازي گروه ذرات هستند. همه‌ي کشورها، به دو دسته تقسيم مي‌شوند: امپرياليست و مستعمره. کشورهاي استعمارگر با اعمال سياست جذب (همگون‌سازي) در راستاي محورهاي مختلف بهينه‌سازي، کشورهاي مستعمره را به سمت خود مي‌شکند. رقابت امپرياليستي در کنار سياست همگون‌سازي، هسته‌ي اصلي اين الگوريتم را تشکيل مي‌دهد و باعث مي‌شود که کشورها به سمت مينيمم مطلق تابع حرکت کنند. در اين فصل به استعمار به عنوان جزئي لاينفک از سير تکامل تاريخي انسان نگريسته شده و از چگونگي اثرگذاري آن بر کشورهاي استعمارگر و مستعمره و نيز کل تاريخ، به عنوان منبع الهام يک الگوريتم کارا و نو در زمينه محاسبات تکاملي استفاده شده است. اين فصل، چگونگي مدل‌سازي رقابت امپرياليستي، و نيز چگونگي پياده‌سازي الگوريتم را توضيح مي‌دهد.

۳-۲- مروري تاريخي بر پديده استعمار

امپرياليزم[۲۴]، در لغت به سياست توسعه قدرت و نفوذ يک کشور در حوزه خارج از قلمرو شناخته شده براي آن، اطلاق مي‌شود. يک کشور مي‌تواند کشور ديگر را به طور قانونگذاري مستقيم و يا از طريق روش‌هاي غير مستقيم، مثل کنترل کالاها و مواد خام، کنترل کند. مورد اخير اغلب استعمار نو[۲۵] خوانده مي‌شود. استعمار يک پديده ذاتي در تاريخ بوده است. استعمار در مراحل ابتدايي، به صورت نفوذ سياسي‌ـ‌نظامي در کشورها و به صورت صرف استفاده از منابع زميني، انساني و سياسي بوده است. بعضي مواقع نيز استعمار، به صرف جلوگيري از نفوذ کشور استعمارگر رقيب انجام مي‌شد. به هر حال کشورهاي استعمارگر رقابت شديدي را براي به استعمار کشيدن مستعمرات همديگر نشان مي‌دادند. اين رقابت به نوبه خود باعث رشد و توسعه کشورهاي استعمارگر از لحاظ سياسي، نظامي و اقتصادي گرديد. زيرا کشورها براي داشتن امکان رقابت، مجبور به توسعه بودند.

در حالت‌هاي قديمي‌تر، استعمارگران با بهره‌گيري از منابع زميني، انساني و غيره کشور مستعمره، فقط در صدد افزايش قدرت خود بودند و اينکه آيا مستعمرات پيشرفت مي‌کنند يا نه مهم نبود. اما بعدها با فزايش ارتباط ميان ملل و رشد انساني، استعمارگران براي ادامه نفوذ خود، به نوعي از اقبال عمومي (حمايت مردمي) نيز احتياج پيدا کردند. بدين ترتيب کشورهاي استعمارگر شروع به ايجاد عمران و آبادي (هر چند ظاهري) در مستعمراتشان نمودند. بدين ترتيب، مستعمرات، شاهد پيشرفت در زمينه‌هاي اقتصادي، اجتماعي و انساني شدند که عامل اين پيشرفت به اجبار، کشور استعمارگر بود. دليل نامگذاري اين فرايند با نام “استعمار” که ريشه در کلمه عمران و آبادي دارد، نيز، همين مساله مي‌باشد.  البته دريافت اقبال عمومي تنها دليل ايجاد عمران توسط استعمارگران در مستعمرات نبود. يک دليل ديگر ايجاد سلطه فرهنگي بر مسعمرات در راستاي اجراي سياست همگون‌سازي بود. به عنوان مثال کشورهايي نظير فرانسه و انگليس به ايجاد مدارس انگليسي زبان و فرانسوی زبان در مستعمرات خود پرداختند. اين اقدام به دلايل مختلفي صورت مي‌گرفت که در راس اين دلايل افزايش نفوذ فرهنگي در مستعمرات بوده است. نا گفته نماند که فرايند استعمار (حد اقل بعد فرهنگي آن) با همه تبعات منفي آن در بعضي از کشورهاي امپرياليست به چشم يک جهاد فکري براي نجات بشر نيز نگريسته مي‌شد. اشعاري وجود دارند که به مدح و ستايش جوانان انگليسي مي‌پردازند که با هدف آموزش راهي کشورهاي مستعمره شده‌اند و در آنها از اين جوانان به عنوان قهرمانان ملي در جبهه نجات بشري ياد مي‌شود.

امپرياليزم، نگرش عمومي نسبت به تمدن غرب را تغيير داد. داروينيست‌هاي اجتماعي، امپرياليزم را تفسير کرده و اين ايده که فرهنگ غرب، نسبت به فرهنگ شرق، برتر است؛ را تقويت کردند. در آفريقا تنها آنهايي که بعضي از استانداردهاي فرهنگي غرب را داشتند، داراي بخشي از حقوق اجتماعي خود بودند. پرتغالي‌ها اين مردم را جذب شده[۲۶] و فرانسوي‌ها بطور توهين‌آميزي آن‌ها را تکامل‌يافته[۲۷] مي‌ناميدند.

به هرحال مستقل از اثرات و تبعات مثبت و منفي آن، استعمار به عنوان يک فرايند ذاتي در تاريخ بشر ايجاد شد، و در عين وارد کردن خسارتهاي جبران ناپذير به زيربناهاي اساسي يک کشور (خصوصاً زيربناهاي فرهنگي) در بعضي موارد اثرات مثبتي را نيز براي کشورها مستعمره داشت. از ديد بهينه‌سازي، استعمار بعضي از کشورها را که در يک دره معمولي تمدن قرار داشتند، خارج کرده و آنها را به يک حوزه مينيمم ديگر برد که در بعضي موارد وضعيت اين حوزه مينيمم بهتر از موقعيت قبلي کشور مستعمره بود. اما به هر حال اين حرکت مستلزم پيشروي مستعمره در راستاي محورهاي مختلف اقتصادي و فرهنگي به سمت يک امپرياليست قويتر بود، يعني از ميان رفتن بعضي از ساختارهاي فرهنگي و اجتماعي. شکل ۳-۱ اين وضعيت را به خوبي نشان مي‌دهد. در اين شکل، مستعمره در نتيجه سياست همگون‌سازي از يک ناحيه مينيمم خارج شده و وارد يک ناحيه مينيمم ديگر مي‌شود که در آن وضعيت بهتري را دارا مي‌باشد. به هر حال هزينه‌اي که بابت اين حرکت پرداخت شده است، نزديکي به کشور استعمار‌گر در راستاي محورهاي مختلف اقتصادي، سياسي و اجتماعي است. ادامه اين حرکت مي‌تواند به جذب کامل کشور مستعمره در کشور استعمارگر بيانجامد.

شکل ‏۳‑۱ اعمال سياست جذب از طرف استعمارگران بر مستعمرات

در اين بخش به بررسي چند مورد از مستعمرات کشورهاي استعماري و رفتار متقابل آنها نسبت به هم مي‌پردازيم و سعي بر آن است تا با دسته‌بندي اين رفتارها و با کشف نظم دروني آنها و در نهايت مدل‌سازي رياضي واکنشهاي متقابل مستعمرات و استعمارگران، اين پديده‌ي پيچيده‌ي اجتماعي را در قالب يک الگوريتم بهينه‌سازي رياضي بريزيم.

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

شکل ۳-۲ فلوچارت الگوريتم رقابت استعماری را نشان مي‌دهد. همانند ديگر الگوريتم‌هاي تکاملي، اين الگوريتم، نيز با تعدادي جمعيت اوليه تصادفي که هر کدام از آنها يک “کشور” ناميده مي‌شوند؛ شروع مي‌شود. تعدادي از بهترين عناصر جمعيت (معادل نخبه‌ها در الگوريتم ژنتيک) به عنوان امپرياليست[۲۸] انتخاب مي‌شوند. باقيمانده جمعيت نيز به عنوان مستعمره[۲۹]، در نظر گرفته مي‌شوند. استعمارگران بسته به قدرتشان، اين مستعمرات را با يک روند خاص که در ادامه مي‌آيد؛ به سمت خود مي‌کشند. قدرت کل هر امپراطوري، به هر دو بخش تشکيل دهنده آن يعني کشور امپرياليست (به عنوان هسته مرکزي) و مستعمرات آن، بستگي دارد. در حالت رياضي، اين وابستگي با تعريف قدرت امپراطوري به صورت مجموع قدرت کشور امپرياليست، به اضافه در صدي از ميانگين قدرت مستعمرات آن، مدل شده است.

با شکل‌گيري امپراطوري‌هاي اوليه، رقابت امپرياليستي ميان آن‌ها شروع مي‌شود. هر امپراطوري‌اي که نتواند در رقابت استعماري، موفق عمل کرده و بر قدرت خود بيفزايد (و يا حداقل از کاهش نفوذش جلوگيري کند)، از صحنه رقابت استعماري، حذف خواهد شد. بنابراين بقاي يک امپراطوري، وابسته به قدرت آن در جذب مستعمرات امپراطوري‌هاي رقيب، و به سيطره در آوردن آنها خواهد بود. در نتيجه، در جريان رقابت‌هاي امپرياليستي، به تدريج بر قدرت امپراطوري‌هاي بزرگتر افزوده شده و امپراطوري‌هاي ضعيف‌تر، حذف خواهند شد. امپراطوري‌ها براي افزايش قدرت خود، مجبور خواهند شد تا مستعمرات خود را نيز پيشرفت دهند.

شکل ‏۳‑۲ فلوچارت الگوريتم استعماری

با گذشت زمان، مستعمرات، از لحاظ قدرت به امپراطوري‌ها نزديک‌تر خواهند شد و شاهد يک نوع همگرايي خواهيم بود. حد نهايي رقابت استعماري، زماني است که يک امپراطوري واحد در دنيا داشته باشيم، با مستمراتي که از لحاظ موقعيت، به خود کشور امپرياليست، خيلي نزديک هستند.

در ادامه مباحث اين فصل، بخش‌هاي مختلف الگوريتم، مورد بررسي قرار مي‌گيرند.

۳-۳-۱- شکل دهي امپراطوري‌هاي اوليه

در بهينه‌سازي، هدف يافتن يک جواب بهينه بر حسب متغير‌هاي مسئله، است. ما يک آرايه از متغير‌هاي مسئله را که بايد بهينه‌ شوند، ايجاد مي‌کنيم. در الگوريتم ژنتيک اين آرايه، کروکوزوم[۳۰] ناميده مي‌شود. در اينجا نيز آن را يک کشور مي‌ناميم. در يک مسئله‌ي بهينه‌سازي بعدي، يک کشور، يک آرايه‌ي  است. اين آرايه به صورت زير تعريف مي‌شود.

(‏۳‑۱)

مقادير متغيره‌ها در يک کشور، به صورت اعداد اعشاري نمايش داده مي‌شوند. از ديدگاه تاريخي‌ـ‌فرهنگي، اجزاي تشکيل دهنده يک کشور را مي‌توان ويژگي هاي اجتماعي– سياسي آن کشور، همچون فرهنگ، زبان، ساختار اقتصادي و ساير ويژگي‌ها در نظر گرفت. شکل ۳-۳ اين مسئله را به خوبي نشان مي‌دهد. مطابق اين شکل متغيرهاي مجهول تابع هزينه که ما در طي فرايند بهينه‌سازي به دنبال آنها مي‌گرديم، در نگاه اجتماعي‌ـ‌سياسي ويژگي‌هاي تاريخي و فرهنگي‌اي هستند که يک کشور را به نقطه مينيمم تابع هزينه رهنمون مي‌سازند. در حقيقت در حل يک مسئله بهينه‌سازي توسط الگوريتم معرفي شده، ما به دنبال بهترين کشور (کشوري با بهترين ويژگي هاي اجتماعي‌ـ‌سياسي) هستيم. يافتن اين کشور در حقيقت معادل يافتن بهترين پارامتهاي مسئله است که کمترين مقدار تابع هزينه را توليد مي‌کنند.

به عنوان يک مثال فرض کنيم که مي‌خواهيم يک کنترل کننده PID براي يک سيستم کنترلي طراحي کنيم که مثلاً داراي کمترين ميزان مجموع فراجهش و انتگرال قدر مطلق خطا باشد. در يک حالت نوعي، جوابهاي ممکنه مي‌توانند به صورت جوابهايي که به يک خروجي پايدار منجر مي‌شوند، تعريف شوند. براي اين مسئله دسته‌اي از جوابهاي ممکنه به صورت اوليه ايجاد مي‌کنيم. در اين مساله کشور iام به صورت زير تعريف مي‌شود.












 


[۱] Density-based spatial clustering of applications with noise

[۲] Ester

[۳] Identifier (ID)

[۴] Gateway

[۵] Lowest ID Cluster algorithm (LIC)

۱Max-Min d-cluster formation algorithm

[۷]Highest Connectivity Clustering algorithm (HCC)

۳K-hop CONnectivity ID clustering algorithm (KCONID)

[۹]Adaptive cluster load balance method

[۱۰] Option

[۱۱] Adaptive multihop clustering

۱Mobility-based d-hop clustering algorithm

۲Mobility Based Metric for Clustering

۱Mobility-based Frame Work for Adaptive

[۱۵]Least Cluster Change algorithm (LCC)

۱Adaptive clustering for mobile wireless network

[۱۷] Cluster ID (CID)

[۱۸]Entropy-based Weighted clustering algorithm

[۱۹]Reaffiliation

[۲۰] Weka

[۲۱] Gan

[۲۲] Das

[۲۳] Karaboga

[۲۴] Imperialism

[۲۵]neocolonialism

[۲۶]assimilados

[۲۷]evolues

[۲۸] Imperialist

[۳۰]chromosome

[۲۹] Colony

برچسبها
مطالب مرتبط

دیدگاهی بنویسید.

بهتر است دیدگاه شما در ارتباط با همین مطلب باشد.

0