—d1143

فصل چهارم
جدول4-1. مجموعه داده ........................................................................................................................................ 117
جدول4-2. لیست مجموعه الگوریتم‌های پایه ........................................................................................................ 119
جدول4-3. جدول نگاشت استاندارد کد ................................................................................................................ 120
جدول4-4. دقت نتایج این الگوریتم‌های خوشه‌بندی را نسبت به کلاس‌های واقعی داده ...................................... 130
جدول4-5. جدول مقایسه معیار اطلاعات متقابل نرمال‌ شده (NMI) نتایج آزمایش .............................................. 132

فهرست تصاویر و نمودار
فصل دوم
شکل 2-1. یک خوشه‌بندی سلسله مراتبی و درخت متناظر ..................................................................................... 10
شکل 2-2. ماتریس مجاورت .................................................................................................................................... 11
شکل 2-3. رابطه دودویی و گراف آستانه ................................................................................................................. 12
شکل 2-4. گراف‌های آستانه برای ماتریس ........................................................................................................ 12
شکل 2-5. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی منفرد ..................................................................... 13
شکل 2-6. دندوگرام پیوندی منفرد برای ماتریس............................................................................................... 13
شکل 2-7. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی کامل ...................................................................... 14
شکل 2-8. دندوگرام پیوندی کامل برای ماتریس ............................................................................................... 14
شکل 2-9. الگوریتم خوشه‌بندی افرازبندی...................................................................................... 16
شکل 2-10. الگوریتم فازی خوشه‌بندی ...................................................................................................... 18
شکل 2-11. خوشه‌بندی کاهشی .............................................................................................................................. 23
شکل 2-12. شبه‌کد الگوریتم MKF ........................................................................................................................ 26
شکل2-13. (الف) مجموعه داده با تعداد 10 خوشه واقعی. (ب) منحنی ........................................................ 29
شکل2-1۴. (الف) مجموعه داده (ب) منحنی مربوطه ..................................................................................... 29
شکل2-15. دو افراز اولیه با تعداد سه خوشه ........................................................................................................... 31
شکل2-16. نمونه‌های اولیه در نتایج الگوریتم ................................................................................ 36
شکل 2-17. زیر شبه کد الگوریتم خوشه‌بندی ترکیبی توسط مدل مخلوط .............................................................. 43
شکل 2-18. خوشه‌بندی ترکیبی ............................................................................................................................... 44
شکل 2-19. نمونه ماتریس، جهت تبدیل خوشه‌بندی به ابر گراف ................................................................. 45
شکل 2-20. ماتریس شباهت بر اساس خوشه برای مثال شکل (3-5) .................................................................... 46
شکل 2-21. الگوریتم افرازبندی ابر گراف ............................................................................................................... 47
شکل 2-22. الگوریتم فرا خوشه‌بندی ..................................................................................................................... 49
شکل2-23. الگوریتم خوشه‌بندی ترکیبی مبتنی بر ماتریس همبستگی ...................................................................... 50
شکل2-24. الگوریتم افرازبندی با تکرار ................................................................................................................... 53
شکل2-25. نمایش گراف مجاورت در مراحل کاهش درجه ماتریس و شمارش آن ................................................ 54
شکل2-26. مثال روند تغییر توزیع تعداد خوشه ....................................................................................................... 55
شکل2-27. جریان کار عمومی برای پیاده‌سازی الگوریتم افرازبندی گراف .............................................................. 55
شکل 2-28. گراف تابع در بازه بین صفر و یک ............................................................................................. 62
شکل 2-29. الگوریتم خوشه‌بندی ترکیبی طیفی مبتنی بر انتخاب بر اساس شباهت ................................................ 63
شکل 2-30. مثالی از ماتریس اتصال ........................................................................................................................ 66
شکل 2-31. شبه کد خوشه‌بندی ترکیبی انتخابی لی‌مین .......................................................................................... 68
شکل 2-32. روش ارزیابی خوشهی یک افراز در روش MAX ............................................................................... 69
شکل 2-33. چهارچوب خوشهبندی ترکیبی مبتنی بر انتخاب با استفاده از مجموعه‌ای از خوشه‌های یک افراز ...... 71
شکل 2-34. چهارچوب روش بهترین افراز توافقی اعتبارسنجی شده ...................................................................... 72
فصل سوم
شکل3-1. چهارچوب الگوریتم خوشه‌بندی خردمند با استفاده از آستانه‌گیری ......................................................... 82
شکل3-۲. محاسبه درجه استقلال دو خوشه‌بندی ..................................................................................................... 86
شکل3-3. تأثیر عدم تمرکز بر روی پیچیدگی داده ................................................................................................... 89
شکل3-3. تأثیر انتخاب افرازها در خوشه‌بندی ترکیبی مبتنی بر انتخاب بر مقدار NMI ارزیابی‌شده ........................ 91
شکل3-4. شبه کد خوشه‌بندی خردمند با استفاده از آستانه‌گیری .............................................................................. 92
شکل3-5. دسته‌بندی الگوریتم‌های خوشه‌بندی ........................................................................................................ 94
شکل3-6. کد الگوریتم K-means به زبان استقلال الگوریتم‌ خوشه‌بندی ................................................................. 98
شکل3-7. تبدیل کد‌های شروع و پایان به گراف .................................................................................................... 100
شکل3-8. تبدیل عملگر شرط ساده به گراف ......................................................................................................... 100
شکل3-9. تبدیل عملگر شرط کامل به گراف ......................................................................................................... 101
شکل3-10. تبدیل عملگر شرط تو در تو به گراف ................................................................................................. 101
شکل3-11. تبدیل عملگر حلقه ساده به گراف ....................................................................................................... 102
شکل3-12. تبدیل عملگر حلقه با پرش به گراف ................................................................................................... 102
شکل3-13. پیاده‌سازی شرط ساده بدون هیچ کد اضافی ........................................................................................ 103
شکل3-14. پیاده‌سازی شرط ساده با کدهای قبل و بعد آن .................................................................................... 103
شکل3-15. پیاده‌سازی شرط کامل ......................................................................................................................... 104
شکل3-16. پیاده‌سازی شرط‌ تو در تو .................................................................................................................... 104
شکل3-17. پیاده‌سازی یک شرط کامل در یک شرط ساده .................................................................................... 105
شکل3-18. پیاده‌سازی یک شرط کامل در یک شرط کامل دیگر ........................................................................... 105
شکل3-19. پیاده‌سازی حلقه ساده .......................................................................................................................... 106
شکل3-20. پیاده‌سازی یک حلقه ساده داخل حلقه‌ای دیگر ................................................................................... 106
شکل3-21. پیاده‌سازی یک حلقه داخل یک شرط کامل ........................................................................................ 106
شکل3-22. پیاده‌سازی یک شرط کامل داخل یک حلقه ساده ................................................................................ 107
شکل3-23. ماتریس درجه وابستگی‌ کد ................................................................................................................. 108
شکل3-24. شبه کد مقایسه محتوای دو خانه از آرایه‌های استقلال الگوریتم .......................................................... 108
شکل3-25. چهارچوب خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم ...................................................... 110
شکل3-26. شبه کد خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم ............................................................ 113
فصل چهارم
شکل۴-۱. مجموعه داده Halfring .......................................................................................................................... 118
شکل4-2. الگوریتم K-means ................................................................................................................................ 121
شکل4-3. الگوریتم FCM ...................................................................................................................................... 121
شکل4-4. الگوریتم Median K-Flats .................................................................................................................... 122
شکل4-5. الگوریتم Gaussian Mixture ................................................................................................................ 122
شکل4-6. الگوریتم خوشه‌بندی Subtractive ......................................................................................................... 122
شکل4-7. الگوریتم پیوندی منفرد با استفاده از معیار فاصله اقلیدسی ..................................................................... 123
شکل4-8. الگوریتم پیوندی منفرد با استفاده از معیار فاصله Hamming ................................................................ 123
شکل4-9. الگوریتم پیوندی منفرد با استفاده از معیار فاصله Cosine ..................................................................... 123
شکل4-10. الگوریتم پیوندی کامل با استفاده از معیار فاصله اقلیدسی ................................................................... 124
شکل4-1۱. الگوریتم پیوندی کامل با استفاده از معیار فاصله Hamming .............................................................. 124
شکل4-1۲. الگوریتم پیوندی کامل با استفاده از معیار فاصله Cosine .................................................................... 124
شکل4-1۳. الگوریتم پیوندی میانگین با استفاده از معیار فاصله اقلیدسی ............................................................... 124
شکل4-14. الگوریتم پیوندی میانگین با استفاده از معیار فاصله Hamming .......................................................... 125
شکل4-15. الگوریتم پیوندی میانگین با استفاده از معیار فاصله Cosine ............................................................... 125
شکل4-16. الگوریتم پیوندی بخشی با استفاده از معیار فاصله اقلیدسی ................................................................ 125
شکل4-17. الگوریتم پیوندی بخشی با استفاده از معیار فاصله Hamming ............................................................ 125
شکل4-18. الگوریتم پیوندی بخشی با استفاده از معیار فاصله Cosine ................................................................. 126
شکل4-19. طیفـی با استفاده از ماتریس شباهت نامتراکم ...................................................................................... 126
شکل4-20. طیفـی با استفاده از روش نیستروم با متعادل ساز .............................................................................. 127
شکل4-21. طیفـی با استفاده از روش نیستروم بدون متعادل ساز ......................................................................... 127
شکل4-22. نرم‌افزار تحلیل‌گر کد استقلال الگوریتم ............................................................................................... 128
شکل4-23. ماتریس AIDM ................................................................................................................................... 129
شکل4-24. میانگین دقت الگوریتم‌های خوشه‌بندی ............................................................................................... 131
شکل4-25. رابطه میان آستانه استقلال و زمان اجرای الگوریتم در روش پیشنهادی اول ........................................ 133
شکل4-26. رابطه میان آستانه پراکندگی و زمان اجرای الگوریتم در روش پیشنهادی اول ..................................... 133
شکل4-27. رابطه میان آستانه استقلال و دقت نتیجه نهایی در روش پیشنهادی اول .............................................. 134
شکل4-28. رابطه میان آستانه پراکندگی و دقت نتیجه نهایی در روش پیشنهادی اول ............................................ 134
شکل4-29. رابطه میان آستانه عدم تمرکز و دقت نتیجه نهایی در روش پیشنهادی اول ......................................... 135
شکل4-30. رابطه میان آستانه پراکندگی و زمان اجرای الگوریتم در روش پیشنهادی دوم ..................................... 135
شکل4-31. رابطه میان آستانه پراکندگی و دقت نتایج نهایی در روش پیشنهادی دوم ............................................ 136
شکل4-32. رابطه میان آستانه عدم تمرکز و دقت نتایج نهایی در روش پیشنهادی دوم ......................................... 137
شکل4-33. مقایسه زمان اجرای الگوریتم‌ ............................................................................................................... 138
فصل اول
مقدمه
center3187700
1. مقدمه1-1. خوشه‌بندیبه عنوان یکی از شاخه‌های وسیع و پرکاربرد هوش مصنوعی، یادگیری ماشین به تنظیم و اکتشاف شیوه‌ها و الگوریتم‌هایی می‌پردازد که بر اساس آن‌ها رایانه‌ها و سامانه‌های اطلاعاتی توانایی تعلم و یادگیری پیدا می‌کنند. طیف پژوهش‌هایی که در مورد یادگیری ماشینی صورت می‌گیرد گسترده ‌است. در سوی نظر‌ی آن پژوهش‌گران بر آن‌اند که روش‌های یادگیری تازه‌ای به وجود بیاورند و امکان‌پذیری و کیفیت یادگیری را برای روش‌هایشان مطالعه کنند و در سوی دیگر عده‌ای از پژوهش‌گران سعی می‌کنند روش‌های یادگیری ماشینی را بر مسائل تازه‌ای اعمال کنند. البته این طیف گسسته نیست و پژوهش‌های انجام‌شده دارای مؤلفه‌هایی از هر دو رو‌یکرد هستند. امروزه، داده‌کاوی به عنوان یک ابزار قوی برای تولید اطلاعات و دانش از داده‌های خام، در یادگیری ماشین شناخته‌شده و همچنان با سرعت در حال رشد و تکامل است. به طور کلی می‌توان تکنیک‌های داده‌کاوی را به دو دسته بانظارت و بدون نظارت تقسیم کرد [29, 46].
در روش بانظارت ما ورودی (داده یادگیری) و خروجی (کلاس داده) یک مجموعه داده را به الگوریتم هوشمند می‌دهیم تا آن الگوی بین ورودی و خروجی را تشخیص دهد در این روش خروجی کار ما مدلی است که می‌تواند برای ورودی‌های جدید خروجی درست را پیش‌بینی کند. روش‌های طبقه‌بندی و قوانین انجمنی از این جمله تکنیک‌ها می‌باشد. روش‌های با نظارت کاربرد فراوانی دارند اما مشکل عمده این روش‌ها این است که همواره باید داده‌ای برای یادگیری وجود داشته باشد که در آن به ازای ورودی مشخص خروجی درست آن مشخص شده باشد. حال آنکه اگر در زمینه‌ای خاص داده‌ای با این فرمت وجود نداشته باشد این روش‌ها قادر به حل این‌گونه مسائل نخواهند بود [29, 68]. در روش بدون نظارت برخلاف یادگیری بانظارت هدف ارتباط ورودی و خروجی نیست، بلکه تنها دسته‌بندی ورودی‌ها است. این نوع یادگیری بسیار مهم است چون خیلی از مسائل (همانند دنیای ربات‌ها) پر از ورودی‌هایی است که هیچ برچسبی (کلاس) به آن‌ها اختصاص داده نشده است اما به وضوح جزئی از یک دسته هستند [46, 68]. خوشه‌بندی شاخص‌ترین روش در داده‌کاوی جهت حل مسائل به صورت بدون ناظر است. ایده اصلی خوشه‌بندی اطلاعات، جدا کردن نمونه‌ها از یکدیگر و قرار دادن آن‌ها در گروه‌های شبیه به هم می‌باشد. به این معنی که نمونه‌های شبیه به هم باید در یک گروه قرار بگیرند و با نمونه‌های گروه‌های دیگر حداکثر متفاوت را دارا باشند [20, 26]. دلایل اصلی برای اهمیت خوشه‌بندی عبارت‌اند از:
اول، جمع‌آوری و برچسب‌گذاری یک مجموعه بزرگ از الگوهای نمونه می‌تواند بسیار پرکاربرد و باارزش باشد.
دوم، می‌توانیم از روش‌های خوشه‌بندی برای پیدا کردن و استخراج ویژگی‌ها و الگوهای جدید استفاده کنیم. این کار می‌تواند کمک به سزایی در کشف دانش ضمنی داده‌ها انجام دهد.
سوم، با خوشه‌بندی می‌توانیم یک دید و بینشی از طبیعت و ساختار داده به دست آوریم که این می‌تواند برای ما باارزش باشد.
چهارم، خوشه‌بندی می‌تواند منجر به کشف زیر رده‌های مجزا یا شباهت‌های بین الگوها ممکن شود که به طور چشمگیری در روش طراحی طبقه‌بندی قابل استفاده باشد.
1-2. خوشه‌بندی ترکیبیهر یک از الگوریتم‌های خوشه‌بندی، با توجه به اینکه بر روی جنبه‌های متفاوتی از داده‌ها تاکید می‌کند، داده‌ها را به صورت‌های متفاوتی خوشه‌بندی می‌نماید. به همین دلیل، نیازمند روش‌هایی هستیم که بتواند با استفاده از ترکیب این الگوریتم‌ها و گرفتن نقاط قوت هر یک، نتایج بهینه‌تری را تولید کند. در واقع هدف اصلی خوشه‌بندی ترکیبی جستجوی بهترین خوشه‌ها با استفاده از ترکیب نتایج الگوریتم‌های دیگر است [1, 8, 9, 54, 56]. به روشی از خوشه‌بندی ترکیبی که زیرمجموعه‌ی منتخب از نتایج اولیه برای ترکیب و ساخت نتایج نهایی استفاده می‌شود خوشه‌بندی ترکیبی مبتنی بر انتخاب زیرمجموعه نتایج اولیه می‌گویند. در این روش‌ها بر اساس معیاری توافقی مجموعه‌ای از مطلوب‌ترین نتایج اولیه را انتخاب کرده و فقط توسط آن‌ها نتیجه نهایی را ایجاد می‌کنیم [21]. معیارهای مختلفی جهت انتخاب مطلوب‌ترین روش پیشنهاد شده است که معیار اطلاعات متقابل نرمال شده، روش ماکزیموم و APMM برخی از آن‌ها می‌باشند [8, 9, 21, 67]. دو مرحله مهم در خوشه‌بندی ترکیبی عبارت‌اند از:
اول، الگوریتم‌های ابتدایی خوشه‌بندی که خوشه‌بندی اولیه را انجام می‌دهد.
دوم، جمع‌بندی نتایج این الگوریتم‌های اولیه (پایه) برای به دست آوردن نتیجه نهایی.
1-3. خرد جمعینظریه خرد جمعی که اولین بار توسط سورویکی در سال 2004 در کتابی با همان عنوان منتشر شد، استنباطی از مسائل مطرح‌شده توسط گالتون و کندورست می‌باشد، و نشان می‌دهد که قضاوت‌های جمعی و دموکراتیک از اعتبار بیشتری نسبت به آنچه که ما انتظار داشتیم برخوردار است، ما تأثیرات این ایده را در حل مسائل سیاسی، اجتماعی در طی سال‌های اخیر شاهد هستیم. در ادبیات خرد جمعی هر جامعه‌ای را خردمند نمی‌گویند. از دیدگاه سورویکی خردمند بودن جامعه در شرایط چهارگانه پراکندگی، استقلال، عدم تمرکز و روش ترکیب مناسب است [55].
1-4. خوشه‌بندی مبتنی بر انتخاب بر اساس نظریه خرد جمعیهدف از این تحقیق استفاده از نظریه خرد جمعی برای انتخاب زیرمجموعه‌ی مناسب در خوشه‌بندی ترکیبی می‌باشد. تعاریف سورویکی از خرد جمعی مطابق با مسائل اجتماعی است و در تعاریف آن عناصر سازنده تصمیمات رأی افراد می‌باشد. در این تحقیق ابتدا مبتنی بر تعاریف پایه سورویکی از خرد جمعی و ادبیات مطرح در خوشه‌بندی ترکیبی، تعریف پایه‌ای از ادبیات خرد جمعی در خوشه‌بندی ترکیبی ارائه می‌دهیم و بر اساس آن الگوریتم پیشنهادی خود را در جهت پیاده‌سازی خوشه‌بندی ترکیبی ارائه می‌دهیم [55]. شرایط چهارگانه خوشه‌بندی خردمند که متناسب با تعاریف سورویکی باز تعریف شده است به شرح زیر می‌باشد:
پراکندگی نتایج اولیه، هر الگوریتم خوشه‌بندی پایه باید به طور جداگانه و بدون واسطه به داده‌های مسئله دسترسی داشته و آن را تحلیل و خوشه‌بندی کند حتی اگر نتایج آن غلط باشد.
استقلال الگوریتم، روش تحلیل هر یک از خوشه‌بندی‌های پایه نباید تحت تأثیر روش‌های سایر خوشه‌بندی‌های پایه تعیین شود، این تأثیر می‌تواند در سطح نوع الگوریتم (گروه) یا پارامترهای اساسی یک الگوریتم خاص (افراد) باشد.
عدم تمرکز، ارتباط بین بخش‌های مختلف خوشه‌بندی خرد جمعی باید به گونه‌ای باشد تا بر روی عملکرد خوشه‌بندی پایه تأثیری ایجاد نکند تا از این طریق هر خوشه‌بندی پایه شانس این را داشته باشد تا با شخصی سازی و بر اساس دانش محلی خود بهترین نتیجه ممکن را آشکار سازد.
مکانیزم ترکیب مناسب، باید مکانیزمی وجود داشته باشد که بتوان توسط آن نتایج اولیه الگوریتم‌های پایه را با یکدیگر ترکیب کرده و به یک نتیجه نهایی (نظر جمعی) رسید.
در این تحقیق دو روش برای ترکیب خوشه‌بندی ترکیبی و خرد جمعی پیشنهاد شده است. با استفاده از تعاریف بالا الگوریتم روش اول مطرح خواهد شد که در آن، جهت رسیدن به نتیجه نهایی از آستانه‌گیری استفاده می‌شود. در این روش الگوریتم‌های خوشه‌بندی اولیه غیر هم نام کاملاً مستقل فرض خواهند شد و برای ارزیابی استقلال الگوریتم‌های هم نام نیاز به آستانه‌گیری می‌باشد. در روش دوم، سعی شده است تا دو بخش از روش اول بهبود یابد. از این روی جهت مدل‌سازی الگوریتم‌ها و ارزیابی استقلال آن‌ها نسبت به هم یک روش مبتنی بر گراف شبه کد ارائه می‌شود و میزان استقلال به دست آمده در این روش به عنوان وزنی برای ارزیابی پراکندگی در تشکیل جواب نهایی مورد استفاده قرار می‌گیرد. جهت ارزیابی، روش‌های پیشنهادی با روش‌های پایه، روش‌ ترکیب کامل و چند روش معروف ترکیب مبتنی بر انتخاب مقایسه خواهد شد. از این روی از چهارده داده استاندارد و یا مصنوعی که عموماً از سایت UCI [76] جمع‌آوری شده‌اند استفاده شده است. در انتخاب این داده‌ها سعی شده، داده‌هایی با مقیاس‌ کوچک، متوسط و بزرگ انتخاب شوند تا کارایی روش بدون در نظر گرفتن مقیاس داده ارزیابی شود. همچنین جهت اطمینان از صحت نتایج تمامی آزمایش‌های تجربی گزارش‌شده حداقل ده بار تکرار شده است.
1-4-1- فرضیات تحقیقاین تحقیق بر اساس فرضیات زیر اقدام به ارائه روشی جدید در خوشه‌بندی ترکیبی مبتنی بر انتخاب بر اساس نظریه خرد جمعی می‌کند.
۱ ) در این تحقیق تمامی آستانه‌گیری‌ها بر اساس میزان صحت نتایج نهایی و مدت زمان اجرای الگوریتم به صورت تجربی انتخاب می‌شوند.
۲ ) در این تحقیق جهت ارزیابی عملکرد یک الگوریتم، نتایج اجرای آن را بر روی‌داده‌های استاندارد UCI در محیطی با شرایط و پارامترهای مشابه نسبت به سایر الگوریتم‌ها ارزیابی می‌کنیم که این داده‌ها الزاماً حجیم یا خیلی کوچک نیستند.
۳ ) جهت اطمینان از صحت نتایج آزمایش‌ها ارائه‌شده در این تحقیق، حداقل اجرای هر الگوریتم بر روی هر داده ده بار تکرار شده و نتیجه‌ی نهایی میانگین نتایج به دست آمده می‌باشد.
4 ) از آنجایی که روش مطرح‌شده در این تحقیق یک روش مکاشفه‌ای است سعی خواهد شد بیشتر با روش‌های مکاشفه‌ای مطرح در خوشه‌بندی ترکیبی مقایسه و نتایج آن مورد بررسی قرار گیرد.
در این فصل اهداف، مفاهیم و چالش‌های این تحقیق به صورت خلاصه ارائه شد. در ادامه این تحقیق، در فصل دوم، الگوریتم‌های خوشه‌بندی پایه و روش‌های خوشه‌بندی‌ ترکیبی مورد بررسی قرار می‌گیرد. همچنین به مرور روش‌های انتخاب خوشه و یا افراز در خوشه‌بندی ترکیبی مبتنی بر انتخاب خواهیم پرداخت. در فصل سوم، نظریه خرد جمعی و دو روش پیشنهادی خوشه‌بندی خردمند ارائه می‌شود. در فصل چهارم، به ارائه نتایج آزمایش‌های تجربی این تحقیق و ارزیابی آن‌ها می‌پردازیم و در فصل پنجم، به ارائه‌ی نتایج و کار‌های آتی خواهیم پرداخت.

فصل دوم
مروری بر ادبیات تحقیق
center2132965
2. مروری بر ادبیات تحقیق2-1. مقدمهدر این بخش، کارهای انجام‌شده در خوشه‌بندی و خوشه‌بندی ترکیبی را مورد مطالعه قرار می‌دهیم. ابتدا چند الگوریتم‌ پایه خوشه‌بندی معروف را معرفی خواهیم کرد. سپس چند روش کاربردی جهت ارزیابی خوشه، خوشه‌بندی و افرازبندی را مورد مطالعه قرار می‌دهیم. در ادامه به بررسی ادبیات خوشه‌بندی ترکیبی خواهیم پرداخت و روش‌های ترکیب متداول را بررسی خواهیم کرد. از روش‌های خوشه‌بندی ترکیبی، روش ترکیب کامل و چند روش معروف مبتنی بر انتخاب را به صورت مفصل شرح خواهیم داد.
2-2. خوشه‌بندیدر این بخش ابتدا انواع الگوریتم‌های خوشه‌بندی پایه را معرفی می‌کنیم و سپس برخی از آن‌ها را مورد مطالعه قرار می‌دهیم سپس برای ارزیابی نتایج به دست آمده چند متریک معرفی خواهیم کرد.
2-2-1. الگوریتم‌های خوشه‌بندی پایهبه طور کلی، الگوریتم‌های خوشه‌بندی را می‌توان به دو دسته کلی تقسیم کرد:
1- الگوریتم‌های سلسله مراتبی
2- الگوریتم‌های افرازبندی
الگوریتم‌های سلسله مراتبی، یک روال برای تبدیل یک ماتریس مجاورت به یک دنباله از افرازهای تو در تو، به صورت یک درخت است. در این روش‌ها، مستقیماً با داده‌ها سروکار داریم و از روابط بین آن‌ها برای به دست آوردن خوشه‌ها استفاده می‌کنیم. یکی از ویژگی‌های این روش قابلیت تعیین تعداد خوشه‌ها به صورت بهینه می‌باشد. در نقطه مقابل الگوریتم‌های سلسله مراتبی، الگوریتم‌های افرازبندی قرار دارند. هدف این الگوریتم‌ها، تقسیم داده‌ها در خوشه‌ها، به گونه‌ای است که داده‌های درون یک خوشه بیش‌ترین شباهت را به همدیگر داشته باشند؛ و درعین‌حال، بیش‌ترین فاصله و اختلاف را با داده‌های خوشه‌های دیگر داشته باشند. در این فصل تعدادی از متداول‌ترین الگوریتم‌های خوشه‌بندی، در دو دسته سلسله مراتبی و افرازبندی، مورد بررسی قرار می‌گیرند. از روش سلسله‌ مراتبی چهار الگوریتم‌ از سری الگوریتم‌های پیوندی را مورد بررسی قرار می‌دهیم. و از الگوریتم‌های افرازبندی K-means، FCM و الگوریتم طیفی را مورد بررسی خواهیم داد.
2-2-1-1. الگوریتم‌های سلسله مراتبیهمان‌گونه که در شکل 2-1 مشاهده می‌شود، روال الگوریتم‌های خوشه‌بندی سلسله مراتبی را می‌تواند به صورت یک دندوگرام نمایش داد. این نوع نمایش تصویری از خوشه‌بندی سلسله مراتبی، برای انسان، بیشتر از یک لیست از نمادها قابل‌درک است. در واقع دندوگرام، یک نوع خاص از ساختار درخت است که یک تصویر قابل‌فهم از خوشه‌بندی سلسله مراتبی را ارائه می‌کند. هر دندوگرام شامل چند لایه از گره‌هاست، به طوری که هر لایه یک خوشه را نمایش می‌دهد. خطوط متصل‌کننده گره‌ها، بیانگر خوشه‌هایی هستند که به صورت آشیانه‌ای داخل یکدیگر قرار دارند. برش افقی یک دندوگرام، یک خوشه‌بندی را تولید می‌کند [33]. شکل 2-1 یک مثال ساده از خوشه‌بندی و دندوگرام مربوطه را نشان می‌دهد.

شکل 2-1. یک خوشه‌بندی سلسله مراتبی و درخت متناظر
اگر الگوریتم‌های خوشه‌بندی سلسله مراتبی، دندوگرام را به صورت پایین به بالا بسازند، الگوریتم‌های خوشه‌بندی سلسله مراتبی تراکمی نامیده می‌شوند. همچنین، اگر آن‌ها دندوگرام را به صورت بالا به پایین بسازند، الگوریتم‌های خوشه‌بندی سلسله مراتبی تقسیم‌کننده نامیده می‌شوند [26]. مهم‌ترین روش‌های خوشه‌بندی سلسله مراتبی الگوریتم‌های سری پیوندی می‌باشد که در این بخش تعدادی از کاراترین آن‌ها مورد بررسی قرار خواهند گرفت که عبارت‌اند از:
الگوریتم پیوندی منفرد
الگوریتم پیوندی کامل
الگوریتم پیوندی میانگین
الگوریتم پیوندی بخشی
2-2-1-1-1. تعاریف و نماد‌ها
شکل 2-2. ماتریس مجاورت
قبل از معرفی این الگوریتم‌ها، در ابتدا نمادها و نحوه نمایش مسئله نمایش داده خواهد شد. فرض کنید که یک ماتریس مجاورت متقارن داریم. وارده در هر سمت قطر اصلی قرار دارد که شامل یک جای گشت اعداد صحیح بین 1 تا است. ما مجاورت‌ها را عدم شباهت در نظر می‌گیریم. به این معنی است که اشیاء 1 و 3 بیشتر از اشیاء 1 و 2 به هم شبیه‌اند. یک مثال از ماتریس مجاورت معمول برای است که در شکل 2-2 نشان داده شده است. یک گراف آستانه، یک گراف غیر جهت‌دار و غیر وزن‌دار، روی گره، بدون حلقه بازگشت به خود یا چند لبه است. هر نود یک شیء را نمایش می‌دهد. یک گراف آستانه برای هر سطح عدم شباهت به این صورت تعریف می‌شود: اگر عدم شباهت اشیاء و از حد آستانه کوچک‌تر باشد، با واردکردن یک لبه بین نودهای ویک گراف آستانه تعریف می‌کنیم.
(2-1)if and only if
شکل 2-3 یک رابطه دودویی به دست آمده از ماتریس مربوط به شکل 2-2 را برای مقدار آستانه 5 نشان می‌دهد. نماد "*" در موقعیت ماتریس، نشان می‌دهد که جفت متعلق به رابطه دودویی می‌باشد. شکل 2-4، گراف‌های آستانه برای ماتریس را نمایش می‌دهد.

شکل 2-3. رابطه دودویی و گراف آستانه برای مقدار آستانه 5.

شکل 2-4. گراف‌های آستانه برای ماتریس
2-2-1-1-2. الگوریتم پیوندی منفرداین الگوریتم روش کمینه و روش نزدیک‌ترین همسایه نیز نامیده می‌شود [26]. اگر و خوشه‌ها باشند، در روش پیوندی منفرد، فاصله آن‌ها برابر خواهد بود با:
(2-2)
که نشان‌دهنده فاصله (عدم شباهت) بین نقاط a و b در ماتریس مجاورت است. شکل 2-5 این الگوریتم را نمایش می‌دهد. شکل 2-6 دندوگرام حاصل از روش پیوندی منفرد را برای ماتریس ، را نشان می‌دهد.
Step 1. Begin with the disjoint clustering implied by threshold graph, which contains no edges and which places every object in a unique cluster, as the current clustering. Set.
Step 2. From threshold graph.
If the number of comonents (maximally connected subgraphs) in, is less than the number of clusters in the current clustering, redefiene the current clustering by naming each component of as a cluster.
Step 3. If consists of a single connected graph, stop. Else, setand go to step 2.
شکل 2-5. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی منفرد

شکل 2-6. دندوگرام پیوندی منفرد برای ماتریس
2-2-1-1-3. الگوریتم پیوندی کاملاین الگوریتم روش بیشینه یا روش دورترین همسایه نیز نامیده می‌شود. الگوریتم پیوندی کامل می‌گوید که وقتی دو خوشه و شبیه به هم هستند که بیشینه روی تمام ها در و کوچک باشد. به عبارت دیگر، در این الگوریتم، برای یکی کردن دو خوشه، همه جفت‌ها در دو خوشه باید شبیه به هم باشند [26]. اگر و خوشه‌ها باشند، در روش پیوندی کامل، فاصله آن‌ها برابر خواهد بود با:
(2-3)
که نشان‌دهنده فاصله(عدم شباهت) بین نقاط a و در ماتریس مجاورت است. شکل 2-7 این الگوریتم و شکل 2-8 دندوگرام حاصل از این روش را برای ماتریس ، را نشان می‌دهد.
Step 1. Begin with the disjoint clustering implied by threshold graph, which contains no edges and which places every object in a unique cluster, as the current clustering. Set.
Step 2. From threshold graph.
If two of the current clusters from a clique (maximally complete sub graph) in, redefine the current clustering by merging these two clusters into a single cluster.
Step 3. If, so that is the complete graph on the nodes, stop. Else, set and go to step 2.
شکل 2-7. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی کامل

شکل 2-8. دندوگرام پیوندی کامل برای ماتریس
2-2-1-1-4. الگوریتم پیوندی میانگینالگوریتم پیوندی منفرد اجازه می‌دهد تا خوشه‌ها به صورت دراز و نازک رشد کنند. این در شرایطی است که الگوریتم پیوندی کامل خوشه‌های فشرده‌تری تولید می‌کند. هر دو الگوریتم مستعد خطا با داده‌های خارج از محدوده هستند. الگوریتم خوشه‌بندی پیوندی میانگین، یک تعادلی بین مقادیر حدی الگوریتم‌های پیوندی منفرد و کامل است. الگوریتم پیوندی میانگین همچنین، روش جفت-گروه بدون وزن با استفاده از میانگین حسابی نامیده می‌شود. این الگوریتم، یکی از پرکاربردترین الگوریتم‌های خوشه‌بندی سلسله مراتبی می‌باشد [26]. اگر یک خوشه با تعداد تا عضو، و یک خوشه دیگر با تعداد تا عضو باشند، در روش پیوندی میانگین، فاصله آن‌ها برابر خواهد بود با:
(2-4)
که نشان‌دهنده فاصله(عدم شباهت) بین نقاط a و در ماتریس مجاورت است.
2-2-1-1-5. الگوریتم پیوندی بخشیروش پیوندی بخشی که از مربع مجموع خطا‌های (SSE) خوشه‌های یک افراز برای ارزیابی استفاده می‌کند، یکی دیگر از روش‌های سلسله مراتبی می‌باشد [60]. اگر یک خوشه با تعداد تا عضو، و یک خوشه دیگر با تعداد تا عضو باشند و نماد به معنای فاصله اقلیدسی و و مراکز خوشه‌های و باشد آنگاه در روش پیوندی بخشی، فاصله آن‌ها برابر خواهد بود با:
(2-5)
2-2-1-2. الگوریتم‌های افرازبندییک خاصیت مهم روش‌های خوشه‌بندی سلسله مراتبی، قابلیت نمایش دندوگرام است که تحلیل‌گر را قادر می‌سازد تا ببیند که چگونه اشیاء در سطوح متوالی مجاورت، در خوشه‌ها به هم پیوند می‌خورند یا تفکیک می‌شوند. همان طور که اشاره شد، هدف الگوریتم‌های افرازبندی، تقسیم داده‌ها در خوشه‌ها، به گونه‌ای است که داده‌های درون یک خوشه بیش‌ترین شباهت را به همدیگر داشته باشند؛ و درعین‌حال، بیش‌ترین فاصله و اختلاف را با داده‌های خوشه‌های دیگر داشته باشند. آن‌ها یک افراز منفرد از داده را تولید می‌کنند و سعی می‌کنند تا گروه‌های طبیعی حاضر در داده را کشف کنند. هر دو رویکرد خوشه‌بندی، دامنه‌های مناسب کاربرد خودشان را دارند. معمولاً روش‌های خوشه‌بندی سلسله مراتبی، نیاز به ماتریس مجاورت بین اشیاء دارند؛ درحالی‌که روش‌های افرازبندی، به داده‌ها در قالب ماتریس الگو نیاز دارند. نمایش رسمی مسئله خوشه‌بندی افرازبندی می‌تواند به صورت زیر باشد:
تعیین یک افراز از الگوها در گروه، یا خوشه، با داشتن الگو در یک فضای d-بعدی؛ به طوری که الگوها در یک خوشه بیش‌ترین شباهت را به هم داشته و با الگوهای خوشه‌های دیگر بیش‌ترین، تفاوت را داشته باشند. تعداد خوشه‌ها،، ممکن است که از قبل مشخص‌شده نباشد، اما در بسیاری از الگوریتم‌های خوشه‌بندی افرازبندی، تعداد خوشه‌ها باید از قبل معلوم باشند. در ادامه برخی از معروف‌ترین و پرکاربردترین الگوریتم‌های افرازبندی مورد بررسی قرار خواهند گرفت.
2-2-1-2-1. الگوریتم K-meansدر الگوریتم مراکز خوشه‌ها بلافاصله بعد از اینکه یک نمونه به یک خوشه می‌پیوندد محاسبه می‌شوند. به طور معمول بیشتر روش‌های خوشه‌بندی ترکیبی از الگوریتم جهت خوشه‌بندی اولیه خود استفاده می‌کنند [37, 47, 57]. اما مطالعات اخیر نشان داده‌اند که با توجه به رفتار هر مجموعه داده، گاهی اوقات یک روش خوشه‌بندی خاص پیدا می‌شود که دقت بهتری از برای بعضی از مجموعه داده‌ها می‌دهد [1, 54]. اما الگوریتم به دلیل سادگی و توانایی مناسب در خوشه‌بندی همواره به عنوان انتخاب اول مطالعات خوشه‌بندی ترکیبی مورد مطالعه قرار گرفته است. در شکل 2-10 شبه کد الگوریتم را مشاهده می‌کنید:
1. Place K points into the space represented by the objects that are being clustered.
These points represent initial group centroids.
2. Assign each object to the group that has the closest centroid.
3. When all objects have been assigned, recalculate the positions of the K centroids.
4. Repeat Steps 2 and 3 until the centroids no longer move. This produces a separation
of the objects into groups from which the metric to be minimized can be calculated
شکل 2-9. الگوریتم خوشه‌بندی افرازبندی
مقادیر مراکز اولیه‌ی‌ متفاوت برای الگوریتم می‌تواند منجر به خوشه‌بندی‌های مختلفی شود. به خاطر اینکه این الگوریتم مبتنی بر مربع خطا است، می‌تواند به کمینه محلی همگرا شود، مخصوصاً برای خوشه‌هایی که به طور خیلی خوبی از هم تفکیک نمی‌شوند، این امر صادق است. نشان داده شده است که هیچ تضمینی برای همگرایی یک الگوریتم تکراری به یک بهینه سراسری نیست [33]. به طور خلاصه می‌توان ویژگی‌های الگوریتم را به صورت زیر برشمرد:
1- بر اساس فاصله اقلیدسی تمامی ویژگی‌ها می‌باشد.
2- منجر به تولید خوشه‌هایی به صورت دایره، کره و یا ابر کره می‌شود.
3- نسبت به روش‌های دیگر خوشه‌بندی، ساده و سریع است.
4- همگرایی آن به یک بهینه محلی اثبات شده است، اما تضمینی برای همگرایی به بهینه سراسری وجود ندارد.
5- نسبت به مقداردهی اولیه مراکز خوشه‌ها خیلی حساس است.
2-2-1-2-2. الگوریتم FCMالگوریتم FCM اولین بار توسط دون [13] ارائه شد. سپس توسط بزدک [66] بهبود یافت. این متد دیدگاه جدیدی را در خوشه‌بندی بر اساس منطق فازی [62] ارائه می‌دهد. در این دیدگاه جدید، به جای اینکه داده‌ها در یک خوشه عضو باشند، در تمامی خوشه‌ها با یک ضریب عضویت که بین صفر و یک است، عضو هستند و ما در این نوع خوشه‌بندی، دنبال این ضرایب هستیم. در روش‌های معمول در جایی که ما داده داشته باشیم، جواب نهایی ماتریس خواهد بود که هر خانه شامل برچسب خوشه‌ی داده‌ی نظیر آن می‌باشد. ولی در این روش در صورت داشتن خوشه، جواب نهایی یک ماتریس خواهد بود که در آن هر ردیف شامل ضرایب عضویت داده‌ی نظیر به آن خوشه است. بدیهی است که جمع افقی هر ردیف (ضرایب عضویت یک داده خاص) برابر با یک خواهد بود. یک روش معمول جهت رسیدن به جواب‌هایی غیر فازی بر اساس نتایج نهایی الگوریتم فازی، برچسب‌زنی داده بر اساس آن ضریبی که مقدار حداکثر را در این داده دارد، می‌باشد. رابطه 2-6 معادله پایه در روش فازی است: [66]
(2-6) ,
در رابطه 2-6 متغیرm یک عدد حقیقی بزرگ‌تر از یک و درجه عضویت داده در خوشه j-ام می‌باشد، که خود ، i-امین داده d-بُعدی از داده‌ی مورد مطالعه می‌باشد و مرکز d-بعدی خوشه j-ام‌ است و هر روش معمول جهت اندازه‌گیری شباهت میان داده و مرکز خوشه می‌باشد. در روش خوشه‌بندی فازی مراکز خوشه () و درجه عضویت () با تکرار مکرر به ترتیب بر اساس رابطه‌های 2-7 و 2-8 به‌روزرسانی می‌شوند، تا زمانی که شرط توقف درست در آید. در این شرط مقدار یک مقدار توافقی بسیار کوچک‌تر از یک می‌باشد که مطابق با نوع داده و دقت خوشه‌بندی قابل جایگذاری خواهد بود. بدیهی است که هر چقدر این مقدار به سمت صفر میل کند درجه عضویت دقیق‌تر و مقدار زمان اجرا بیشتر خواهد بود [66].
(2-7)
(2-8)
مراحل اجرای الگوریتم در شبه کد شکل 2-11 شرح داده شده است:
1.Initialize matrix,
2.At k-step: calculate the centers vectors with

3.Update ,

4. If then STOP; otherwice returen to step 2.
شکل 2-10. الگوریتم فازی خوشه‌بندی
2-2-1-2-3. الگوریتم طیفیروش خوشه‌بندی طیفی که بر اساس مفهوم گراف طیفی [11] مطرح شده است، از ماتریس شباهت برای کاهش بعد داده‌ها در خوشه‌بندی استفاده می‌کند. در این روش یک گراف وزن‌دار بدون جهت به نحوی تولید می‌شود که رئوس گراف نشان‌دهنده‌ی مجموعه نقاط و هر یال وزن‌دار نشان‌دهنده‌ی میزان شباهت جفت داده‌های متناظر باشد. بر خلاف روش‌های کلاسیک، این روش، روی‌ داده‌ای پراکنده‌ در فضایی با شکل‌ هندسی غیر محدب، نتایج مطلوبی تولید می‌کند [63]. کاربرد این روش در محاسبات موازی [69, 70]، تنظیم بار [15]، طراحی VLSI [28]، طبقه‌بندی تصاویر [35] و بیوانفورماتیک [31, 59] می‌باشد.
در خوشه‌بندی طیفی از بردارهای ویژگی در ماتریس شباهت برای افراز مجموعه‌ داده استفاده می‌شود. در اغلب این روش‌ها، مقدار ویژه اولویت بردارها را تعیین می‌کند. ولی این نحوه‌ی انتخاب، انتخاب بهترین بردارها را تضمین نمی‌دهد. در اولین تحقیقی که در این زمینه توسط ژیانگ و گنگ [61] انجام شد، مسئله‌ی انتخاب بردارهای ویژگی مناسب جهت بهبود نتایج خوشه‌بندی پیشنهاد گردید. در روش پیشنهادی آن‌ها شایستگی هر یک از بردارهای با استفاده از تابع چگالی احتمال هر بردار تخمین زده می‌شود. وزنی به بردارهایی که امتیاز لازم را به دست آورندگ، اختصاص یافته و برای خوشه‌بندی از آن‌ها استفاده می‌شود. در کاری دیگر که توسط ژائو [64] انجام شده است، هر یک از بردارهای ویژه به ترتیب حذف می‌شوند و مقدار آنتروپی مجموعه بردارهای باقی‌مانده محاسبه می‌شود. برداری که حذف آن منجر به افزایش آنتروپی و ایجاد بی‌نظمی بیشتر در مجموعه داده شود، اهمیت بیشتری داشته و در رتبه بالاتری قرار می‌گیرد. سپس زیرمجموعه‌ای از مناسب‌ترین بردارها برای خوشه‌بندی مورد استفاده قرار می‌گیرند. الگوریتم خوشه‌بندی طیفی دارای متدهای متفاوتی جهت پیاده‌سازی است، که الگوریتم‌های برش نرمال، NJW، SLH وPF از آن جمله می‌باشد. در تمامی این روش‌ها، بخش اول، یعنی تولید گراف، مشترک می‌باشد. ما در ادامه ابتدا به بررسی بخش مشترک این روش‌ها می‌پردازیم. سپس به تشریح دو روش پر کاربرد برش نرمال و NJW می‌پردازیم.
در الگوریتم خوشه‌بندی طیفی، افراز داده‌ها بر اساس تجزیه‌ی ماتریس شباهت و به دست آوردن بردارها و مقادیر ویژه‌ی آن صورت می‌گیرد. مجموعه‌ی با داده‌یبعدی را در نظر بگیرید، می‌توان برای این مجموعه گراف وزن‌دار و بدون جهت را ساخت به صورتی که رئوس گراف نشان‌دهنده داده و یال‌ها که ماتریس شباهت را تشکیل می‌دهند بیانگر میزان شباهت بین هر جفت داده متناظر باشند. ماتریس شباهت به صورت رابطه 2-9 تعریف می‌شود:
(2-9)
تابع میزان شباهت بین دو داده را اندازه می‌گیرد. می‌تواند یک تابع گوسی به صورت باشد. که در آن فاصله‌ی بین دو نمونه را نشان می‌دهد و پارامتر مقیاس سرعت کاهش تابع با افزایش فاصله بین دو نمونه را مشخص می‌کند. در ادامه به بررسی دو الگوریتم خوشه‌بندی طیفی برش نرمال و NJW می‌پردازیم.
2-2-1-2-3-1. الگوریتم برش نرمالالگوریتم برش نرمال توسط شی و ملیک [35] برای قطعه‌بندی تصاویر ارائه شده است. در این روش، میزان تفاوت بین خوشه‌های مختلف و شباهت بین اعضا یک خوشه، بر اساس فاصله‌ی داده‌ها محاسبه می‌کند. رابطه 2-10 اشاره به مفهوم شباهت داده دارد که با استفاده از آن اقدام به ساخت گراف وزن‌دار می‌نماییم:
(2-10)
موقعیت i-امین داده (پیکسل در تصاویر) و بردار ویژگی از صفات داده (مانند روشنایی در تصاویر) می‌باشد. با کمک حد آستانه می‌توان میزان تنکی ماتریس شباهت را با توجه به تعداد اثرگذار داده‌های همسایه تعیین کرد. گام‌های این الگوریتم به صورت زیر می‌باشد:
محاسبه ماتریس درجه.
محاسبه ماتریس لاپلاسین.
محاسبه دومین بردار ویژگی متناظر با دومین کوچک‌ترین مقدار ویژه.
استفاده از برای خوشه‌بندی (قطعه‌بندی در تصاویر) گراف.
روش برش نرمال بیشتر در قطعه‌بندی تصاویر کاربرد دارد و معمولاً در خوشه‌بندی داده از سایر الگوریتم‌های خوشه‌بندی طیفی استفاده می‌کنند.
2-2-1-2-3-2. الگوریتم NJWایده الگوریتم استفاده از اولین بردار ویژه متناظر با بزرگ‌ترین مقدار ویژه ماتریس لاپلاسین است. مراحل این الگوریتم به صورت زیر می‌باشد: [51]

دانلود پایان نامه ارشد- مقاله تحقیق

 برای دانلود فایل کامل به سایت منبع مراجعه کنید  : homatez.com

یا برای دیدن قسمت های دیگر این موضوع در سایت ما کلمه کلیدی را وارد کنید :

 

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

2-2-1-2-4. الگوریتم خوشه‌بندی کاهشیالگوریتم خوشه‌بندی کاهشی یکی از سریع‌ترین الگوریتم‌های تک گذر، برای تخمین تعداد خوشه و مراکز آن‌ها در مجموعه‌ی داده می‌باشد. این مفهوم یعنی به جای تحت تأثیر قرار گرفتن محاسبات از ابعاد مسئله، متناسب با اندازه مسئله آن را انجام دهیم. با این وجود، مراکز واقعی خوشه الزاماً یکی از نقاط داده موجود در مجموعه داده نیست ولی در بیشتر موارد این انتخاب تخمین خوبی است که به صورت ویژه از این رویکرد در محاسبات کاهشی استفاده می‌شود. اگر هر نقطه از مجموعه داده به عنوان گزینه‌ای برای مرکز خوشه در نظر گرفته شود، معیار تراکم هر نقطه به صورت زیر تعریف می‌شود [79].
(2-11)
در رابطه بالا یک ثابت مثبت است، که نشان‌دهنده‌ی شعاع همسایگی (سایر نقاط داده که نزدیک‌ترین نقاط به این داده خاص هستند) می‌باشد، و نشان‌دهنده‌ی سایر داده‌های مجموعه، و نشان‌دهنده‌ی تعداد این داده‌ها است. از این روی، داده‌ای دارای بیش‌ترین مقدار تراکم می‌باشد که بیش‌ترین نقاط داده در همسایگی آن است. اولین مرکز خوشه بر اساس بزرگ‌ترین مقدار تراکم انتخاب می‌شود. بعد از این انتخاب میزان تراکم هر یک از نقاط داده به صورت زیر به‌روز می‌شود [79].
(2-12)
در رابطه بالا ثابت مثبت همسایگی را تعریف می‌کند که میزان کاهش تراکم قابل اندازه‌گیری را نشان می‌دهد. از آنجایی که نقاط داده در نزدیکی مرکز خوشه اول به طور قابل‌توجهی مقادیر چگالی را کاهش می‌دهند بعد از به‌روز کردن مقادیر تابع چگالی توسط رابطه بالا مرکز خوشه بعدی بر اساس داده‌ای که بزرگ‌ترین مقدار چگالی را دارد انتخاب می‌شود. این فرآیند آن قدر تکرار می‌شود تا به تعداد کافی مرکز خوشه ایجاد شود. پس از اتمام این فرآیند می‌توان توسط الگوریتم که مراکز داده در آن توسط فرآیند بالا به صورت دستی داده شده است (نه به صورت تصادفی)، داده‌ها را خوشه‌بندی کرد. شبه کد شکل زیر روند فرآیند بالا را نشان می‌دهد که در آن ابتدا مقادیر ثابت‌ها () و مجموعه داده به عنوان ورودی گرفته می‌شود و پس از ساخت مراکز داده مطابق با تعاریف بالا، این مراکز برای خوشه‌بندی در الگوریتم استفاده می‌شود [79].
Inputs Dataset, Constants
Output Clusters
Steps
1. Initialize constants and density values
2. Make a new cluster center.
3. Update density values
4. If the sufficient number of clusters are not obtained, go to 2.
3. Clustering the dataset by k-means, using fix centers.
شکل 2-11. خوشه‌بندی کاهشی
2-2-1-2-5. الگوریتم خوشه‌بندی Median K-Flatالگوریتم Median K-Flat یا به اختصار MKF مجموعه داده‌یرا به K خوشه‌ی افراز می‌کند که هر خوشه یک شبه فضای d-بُعدی تقریباً خطی می‌باشد. پارامتر‌ با فرض ماتریسی با ابعاد می‌باشد، که هر یک از خانه‌های آن تخمین شبه فضای خطی متعامد می‌باشد. قابل به ذکر است که می‌باشد. در این جا تخمین شبه فضای خوشه‌های را نام‌گذاری می‌کنیم. مطابق تعاریف بالا تابع انرژی برای افرازهای ‌ بر اساس شبه فضای به شکل زیر تعریف می‌شود [77].
(2-13)
این الگوریتم سعی می‌کند تا مجموعه داده را به خوشه‌های ‌تبدیل کند به نحوی که تابع انرژی کمینه باشد. تا وقتی که سطوح تخت اساسی به شکل شبه فضای خطی هستند ما می‌توانیم به صورت فرضی المان‌های X را در یک حوضه واحد نرمال کنیم به طوری که برای و تابع انرژی را به شکل زیر بیان کنیم: [77]
(2-14)
این الگوریتم برای کمینه‌سازی تابع انرژی الگوریتمMKF از روش کاهش گرادیان تصادفی استفاده می‌کند. مشتق تابع انرژی بر اساس ماتریس به شرح زیر است:
(2-15)
این الگوریتم نیاز به تطبیق بر اساس مؤلفه‌ی متعامد مشتق دارد. بخشی از مشتق که با شبه فضای موازی است به شرح زیر می‌باشد.
(2-16)
از این روی مؤلفه متعامد برابر است با رابطه 2-17 می‌باشد.
(2-17)
در رابطه بالا برابر با رابطه 2-18 است.
(2-18)
با در نظر گرفتن محاسبات بالا، الگوریتم MKF تصمیم می‌گیرد که داده تصادفی از مجموعه داده، عضو کدام باشد، و از این طریق شروع به چیدن داده‌ها می‌کند. آن گاه، الگوریتم تابع را به‌روز کند که در آن (مرحله زمانی) پارامتری است که توسط کاربر تعیین می‌شود. این فرآیند آن قدر تکرار می‌شود تا ضابطه همگرایی دیده شود. آنگاه هر نقطه از مجموعه داده به نزدیک‌ترین شبه فضای که تعیین‌کننده خوشه‌هاست اختصاص داده می‌شود. شبه کد زیر فرآیند الگوریتم MKF را نشان می‌دهد [77].
Input:
: Data, normalized onto the unit sphere, d: dimension of subspaces K: number of subspaces, the initialized subspaces. : step parameter.
Output: A partition of X into K disjoint clusters
Steps:
1. Pick a random point in X
2. Find its closest subspace , where
3. Compute by
4. Update
5. Orthogonalize
6. Repeat steps 1-5 until convergence
7. Assign each xi to the nearest subspace
شکل 2-12. شبه‌کد الگوریتم MKF [77]
2-2-1-2-6. الگوریتم خوشه‌بندی مخلوط گوسییک مخلوط گوسی یا همان را می‌توان ترکیب محدبی از چگالی‌های گوسی دانست. یک چگالی گوسی در فضای d-بُعدی به ازای میانگین، توسط ماتریس هم‌وردایی با ابعاد به صورت زیر تعریف می‌شود: [83]
(2-19)
در رابطه بالا پارامتر‌های و را تعریف می‌کند. از این روی مؤلفه به صورت زیر تعریف می‌شود:
(2-20)
در رابطه (2-20) پارامتر وزن مخلوط کردن و مؤلفه مخلوط می‌باشد. از آنجا که در مقایسه با تخمین چگالی غیر پارامتری، تعداد کمتری از توابع چگالی در تخمین چگالی مخلوط باید ارزیابی شود، از این روی ارزیابی چگالی کارآمدتر خواهد بود. علاوه بر آن، استفاده از اجرای محدودیت هموار کردن بر روی برخی از مؤلفه‌های مخلوط در نتیجه‌ی چگالی به ما اجازه می‌دهد تا چگالی مستحکم‌تری را تخمین بزنیم. الگوریتم حداکثر-انتظار یا همان به ما اجازه به‌روز کردن پارامتر‌های مؤلفه‌ی مخلوط را مطابق با مجموعه داده به ازای هر می‌دهد، به طوری که احتمال هرگز کوچک‌تر از مخلوط جدید نشود. به‌روز کردن الگوریتم می‌تواند در یک فرآیند تکراری برای تمامی مؤلفه‌های مطابق با رابطه‌های زیر انجام شود: [83]
(2-21)
(2-22)
(2-23)
(2-24)
در این تحقیق از روش پیشنهادی بومن و همکاران برای پیاده‌سازی الگوریتم مخلوط گوسی استفاده شده است. از آنجایی که روش پیاده‌سازی و توضیحات مربوط به الگوریتم مخلوط گوسی در روش ترکیب مبتنی بر مخلوط استفاده می‌شود از این روی در بخش روش‌های ترکیب نتایج با تابع توافقی آن را بررسی خواهیم کرد.
2-2-2. معیارهای ارزیابیدر یادگیری با ناظر ارزیابی راحت تر از یادگیری بدون ناظر است. برای مثال آن چیز که ما در رده‌بندی باید ارزیابی کنیم مدلی است که ما توسط داده‌های یادگیری به الگوریتم هوش مصنوعی آموزش داده‌ایم. در روش‌های با ناظر ورودی و خروجی داده معلوم است و ما بخشی از کل داده را برای آزمون جدا کرده و بخش دیگر را به عنوان داده یادگیری استفاده می‌کنیم و پس از تولید مدل مطلوب ورودی داده آزمون را در مدل وارد کرده و خروجی مدل را با خروجی واقعی می‌سنجیم. از این روی معیارهای بسیاری برای ارزیابی روش‌های با ناظر ارائه‌شده‌اند.
در یادگیری بدون ناظر روش متفاوت است. در این روش هیچ شاخص معینی در داده جهت ارزیابی وجود ندارد و ما به دنبال دسته‌بندی کردن داده‌ها بر اساس شباهت‌ها و تفاوت‌ها هستیم. از این روی برخلاف تلاش‌های خیلی از محققان، ارزیابی خوشه‌بندی خیلی توسعه داده نشده است و به عنوان بخشی از تحلیل خوشه‌بندی رایج نشده است. در واقع، ارزیابی خوشه‌بندی یکی از سخت‌ترین بخش‌های تحلیل خوشه‌بندی است [33]. معیارهای عددی، یا شاخص‌هایی که برای قضاوت جنبه‌های مختلف اعتبار یک خوشه به کار می روند، به سه دسته کلی تقسیم می‌شوند:
1- شاخص خارجی که مشخص می‌کند که کدام خوشه‌های پیداشده به وسیله الگوریتم خوشه‌بندی با ساختارهای خارجی تطبیق دارند. در این روش نیاز به اطلاعات اضافی مثل برچسب نقاط داده، داریم. آنتروپی یک مثالی از شاخص خارجی است.
2- شاخص داخلی که برای اندازه‌گیری میزان خوبی یک ساختار خوشه‌بندی بدون توجه به اطلاعات خارجی به کار می‌‌رود. یک نمونه از شاخص داخلی است.
3- شاخص نسبی که برای مقایسه دو خوشه‌بندی مختلف یا دو خوشه مختلف به کار می‌رود. اغلب یک شاخص خارجی یا داخلی برای این تابع استفاده می‌شود. برای مثال، دو خوشه‌بندی می‌توانند با مقایسه یا آنتروپی‌شان مقایسه شوند.
این فصل تعدادی از مهم‌ترین و رایج‌ترین روش‌های به‌کاررفته برای ارزیابی خوشه‌بندی را مرور خواهد کرد.
2-2-2-1. معیار SSEیک معیار داخلی ارزیابی خوشه‌بندی، مثل، می‌تواند برای ارزیابی یک خوشه‌بندی نسبت به خوشه‌بندی دیگر به کار رود. به علاوه، یک معیار داخلی اغلب می‌تواند برای ارزیابی یک خوشه‌بندی کامل یا یک خوشه تنها به استفاده شود. این اغلب به خاطر این است که این روش، سعی می‌کند تا میزان خوبی کلی خوشه‌بندی را به عنوان یک جمع وزن‌دار از خوبی‌های هر خوشه در نظر می‌گیرد. با استفاده از رابطه 2-25 محاسبه می‌شود [68].
(2-25)
کهیک نقطه داده در خوشه است و، j-امین ویژگی از داده X است. ، j-امین ویژگی از مرکز خوشه می‌باشد. برای مقایسه دو خوشه‌بندی مختلف روی یک داده با یک تعداد مشابه، تنها مقایسه مقدارهای متناظر آن‌ها کافی است. هر چه مقدار کمتر باشد، آن خوشه‌بندی بهتر خواهد بود. البته، وقتی تعداد نقاط داده در دو خوشه متفاوت باشند، مقایسه مستقیم از روی مقدار خوب نخواهد بود. بنابراین، یک خوشه معیار مناسب تری برای مقایسه است. رابطه 2-26 این معیار را نشان می‌دهد که در آن مقدار تعداد کل نمونه‌هاست [68].
(2-26)
تعداد درست خوشه‌ها در الگوریتم ، اغلب می‌تواند با استفاده از نگاه کردن به منحنی مشخص شود. این منحنی با رسم مقادیر به ازایهای مختلف به دست می‌آید. تعداد خوشه‌های بهینه با توجه به منحنی، ای است که به ازای آن نرخ کاهش مقدار، قابل چشم‌پوشی شود. شکل 2-13-ب منحنی را برای داده‌های شکل 2-13-الف، نشان می‌دهد.

(الف)
(ب)
شکل2-13. (الف) مجموعه داده با تعداد 10 خوشه واقعی. (ب) منحنی مربوطه [68]
همان طور که از شکل 2-13-ب برمی‌آید، برای مقادیرهای از صفر تا 10 شیب منحنی نسبت به بقیه مقادیر، تندتر می‌باشد. این امر نشان‌دهنده آن است که مقدار یک مقدار بهینه برای تعداد خوشه‌ها می‌باشد.

(الف)
(ب)
شکل2-14. (الف) مجموعه داده (ب) منحنی مربوطه [2]
شکل 2-14-ب نیز منحنی را برای داده‌های شکل 2-14-الف، نشان می‌دهد. مشاهده می‌شود که در این داده‌ها، چون تعداد خوشه‌ها نسبت به شکل 2-14-الف کاملاً گویا نیست، بنابراین، منحنی آن نیز نرم تر خواهد بود . اما با توجه به شکل 2-14-ب، می‌توان گفت که تعداد نسبتاً خوب باشد. چون منحنی برای های بعد از 8، دارای شیب کندتری خواهد شد. با توجه به نتایج فوق می‌توان گفت که اگرچه منحنی برای همه مسایل نمی‌تواند جواب بهینه برای تعداد بدهد، اما می‌تواند به عنوان یک معیار خوب برای این امر مطرح باشد.
2-2-2-2. معیار اطلاعات متقابل نرمال شدهمعیار اطلاعات متقابل () توسط کاور و توماس [71] معرفی شد که یک روش جهت اندازه‌گیری کیفیت اطلاعات آماری مشترک بین دو توزیع است. از آنجایی که این معیار وابسته به اندازه خوشه‌ها است در [54] روشی جهت نرمال سازی آن ارائه شده است. فرد و جین [19] روش نرمال سازی اطلاعات متقابل را اصلاح کردند و آن را تحت عنوان اطلاعات متقابل نرمال () ارائه داده‌اند. رابطه 2-27 اطلاعات متقابل نرمال شده را نشان می‌دهد[1, 2, 19] .
(2-27)
در رابطه 2-27 پارامتر کل نمونه‌ها است و یعنی افرازهایی که اندیس آن‌ها شامل i با تمام مقادیر j می‌باشد و یعنی افرازهایی که تمام مقادیر i با و اندیس j را شامل شود. از رابطه 2-28 محاسبه می‌شود [1, 2, 19].
(2-28)
, ,
در صورتی که دو افراز به صورت و که در آن کل داده و خوشه اول و خوشه دوم هر یک از افرازها باشد آنگاه نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد، نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد، نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد و نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد. در واقع و به ترتیب بیانگر کل نمونه‌های موجود در و می‌باشد [1].
شکل 2-15 دو افراز اولیه را نشان می‌دهد که میزان پایداری برای هر کدام از خوشه‌های به دست آمده هم محاسبه شده است. در این مثال الگوریتم به عنوان الگوریتم خوشه‌بندی اولیه انتخاب شده است و تعداد خوشه‌های اولیه برابر با سه نیز به عنوان پارامتر آن از قبل مشخص شده است. همچنین، در این مثال تعداد افرازهای موجود در مجموعه مرجع برابر با ۴۰ می‌باشد. در ۳۶ افراز نتایجی مشابه با شکل 2-15 (a) و در 4 حالت باقیمانده نیز نتایجی مشابه با شکل 2-15 (a) حاصل شده است [1].

شکل2-15. دو افراز اولیه با تعداد سه خوشه. (a) خوشه‌بندی درست (b) خوشه‌بندی نادرست [1]
از آن جایی که در مجموعه مرجع در ۹۰ % مواقع، داده‌های متراکم گوشه بالا‐چپ از شکل 2-15 در یک خوشه مجزا گروه‌بندی شده‌اند، بنابراین این خوشه باید مقدار پایداری بالایی را به خود اختصاص دهد. اگرچه این مقدار نباید دقیقاً برابر با یک باشد (چون در همه موارد این خوشه درست تشخیص داده نشده است)، مقدار پایداری با روش متداول اطلاعات متقابل نرمال شده مقدار یک را بر می‌گرداند. از آن جایی که ادغام دو خوشه سمت راست تنها در ۱۰ % موارد مانند شکل 2-15 (b) اتفاق افتاده است، خوشه حاصل باید مقدار پایداری کمی به دست آورد. اگر چه خوشه حاصل از ادغام دو خوشه سمت راستی، به ندرت ( ۱۰ % موارد) در مجموعه مرجع دیده شده است، مقدار پایداری برای این خوشه نیز برابر با یک به دست می‌آید. در اینجا مشکل روش متداول محاسبه پایداری با استفاده از اطلاعات متقابل نرمال شده ظاهر می‌شود. از آنجایی که معیار اطلاعات متقابل نرمال شده یک معیار متقارن است، مقدار پایداری خوشه بزرگ ادغامی سمت راست (با ۱۰ % تکرار) دقیقاً برابر با میزان پایداری خوشه متراکم گوشه بالا‐چپ (با ۹۰ % تکرار) به دست می‌آید. به عبارت دیگر در مواردی که داده‌های دو خوشه مکمل یکدیگر باشند، یعنی اجتماع داده‌های آن‌ها شامل کل مجموعه داده شود و اشتراک داده‌های آن‌ها نیز تهی باشد، مقدار پایداری برای هر دو به یک اندازه برابر به دست می‌آید. از دیدگاه دیگر، این اتفاق زمانی رخ می‌دهد که تعداد خوشه‌های تشکیل‌دهنده مجموعه در خوشه‌بندی مرجع عددی بیشتر از یک باشد. هر زمان که با ادغام دو یا بیشتر از خوشه‌ها به دست آید، منجر به نتایج نادرست در مقدار پایداری می‌شود. ما این مشکل را تحت عنوان مشکل تقارن در اطلاعات متقابل نرمال شده می‌شناسیم. در سال‌های اخیر روش‌هایی جهت حل این مشکل ارائه‌شده‌اند که یکی از آن‌ها را علیزاده و همکاران در [1, 9]ارائه داده‌اند که در‌ آن بزرگ‌ترین خوشه از بین مجموعه مرجع (که بیش از نصف نمونه‌هایش در خوشه مورد مقایسه وجود دارد) جایگزین اجتماع همه خوشه‌ها می‌شود که ما آن را با عنوان روش Max می‌شناسیم. روش دیگر جهت رفع این مشکل معیار APMM می‌باشد. در ادامه به بررسی این معیار می‌پردازیم [1, 8, 67].
2-2-2-3. معیار APMMبر خلاف معیارکه برای اندازه‌گیری شباهت دو افراز طراحی شده است معیار روشی برای اندازه‌گیری میزان شباهت یک خوشه در یک افراز است که توسط عـلیزاده و همکاران [8, 67] معرفی شده است رابطه 2-29 این معیار را معرفی می‌کند.
(2-29)
در رابطه 2-29 پارامتر خوشه i-ام در افراز می‌باشد و افراز متناظر با خوشه در خوشه‌بندی است. پارامتر تعداد کل نمونه‌های مجموعه داده و تعداد نمونه‌های مشترک بین خوشه‌های و می‌باشد. همچنین، تعداد خوشه‌های موجود در افراز می‌باشد. در این روش برای محاسبه پایداری خوشه از رابطه 2-30 استفاده می‌کنیم [8, 67].
(2-30)
در رابطه 2-30 پارامتر نشان‌دهنده j-امین افراز از مجموعه مرجع است و تعداد کل افرازها است [8, 67]. از آنجایی که این معیار برای ارزیابی شباهت یک خوشه است می‌توان هم برای ارزیابی خوشه و هم برای ارزیابی افراز استفاده کرد. جهت استفاده از این معیار برای ارزیابی یک افراز کافی است آن را برای تک‌تک خوشه‌های آن افراز استفاده کنیم و در نهایت از کل مقادیر میانگین بگیریم.
2-۳. خوشه‌بندی ترکیبیکلمه’Ensemble‘ ریشه فرانسوی دارد و به معنی باهم بودن یا در یک زمان می‌باشد و معمولاً اشاره به واحدها و یا گروه‌های مکملی دارد که باهم در اجرای یک کار واحد همکاری می‌کنند. ترکیب تاریخ طولانی در دنیای واقعی دارد، نظریه هیئت‌منصفه ی کندورست که در سال 1785 میلادی مطرح شده است و این ایده را مطرح می‌کند که، احتمال نسبی درستی نظر گروهی از افراد (رأی اکثریت) بیشتر از نظر هر یک از افراد به تنهایی می‌باشد را می‌توان دلیلی برای ترکیب نتایج در دنیای واقعی دانست [10, 27]. خوشه‌بندی ترکیبی روشی جدید در خوشه‌بندی می‌باشد که از ترکیب نتایج روش‌های خوشه‌بندی متفاوت به دست می‌آید از آنجایی که اکثر روش‌های خوشه‌بندی پایه روی جنبه‌های خاصی از داده‌ها تاکید می‌کنند، در نتیجه روی مجموعه داده‌های خاصی کارآمد می‌باشند. به همین دلیل، نیازمند روش‌هایی هستیم که بتواند با استفاده از ترکیب این الگوریتم‌ها و گرفتن نقاط قوت هر یک، نتایج بهینه‌تری را تولید کند. هدف اصلی خوشه‌بندی ترکیبی جستجوی نتایج بهتر و مستحکم‌تر، با استفاده از ترکیب اطلاعات و نتایج حاصل از چندین خوشه‌بندی اولیه است [18, 54]. خوشه‌بندی ترکیبی می‌تواند جواب‌های بهتری از نظر استحکام، نو بودن، پایداری و انعطاف‌پذیری نسبت به روش‌های پایه ارائه دهد [3, 21, 54, 57]. به طور خلاصه خوشه‌بندی ترکیبی شامل دو مرحله اصلی زیر می‌باشد : [34, 54]
1- تولید نتایج متفاوت از خوشه‌بندی‌ها، به عنوان نتایج خوشه‌بندی اولیه بر اساس اعمال روش‌های مختلف که این مرحله را، مرحله ایجاد تنوع یا پراکندگی می‌نامند.
2- ترکیب نتایج به دست آمده از خوشه‌بندی‌های متفاوت اولیه برای تولید خوشه نهایی؛ که این کار توسط تابع توافقی (الگوریتم ترکیب‌کننده) انجام می‌شود.
2-۳-1. ایجاد تنوع در خوشه‌بندی ترکیبیدر خوشه‌بندی ترکیبی، هرچه خوشه‌بندی‌های اولیه نتایج متفاوت تری ارائه دهند نتیجه نهایی بهتری حاصل می‌شود. در واقع هرچه داده‌ها از جنبه‌های متفاوت‌تری مطالعه و بررسی شوند (تشخیص الگوهای پنهان داده) نتیجه نهایی که از ترکیب این نتایج حاصل می‌شود متعاقباً دارای دقت بالاتری خواهد بود که این امر منجر به کشف دانش ضمنی پنهان در داده نیز خواهد شد. تنوع در این بخش به این معنا می‌باشد که با استفاده از روش‌های متفاوت مجموعه داده را از دیدگاه‌های گوناگونی مورد بررسی قرار دهیم. در این فصل برای ایجاد پراکندگی در بین نتایج حاصل چند راه‌کار مختلف پیشنهاد می‌کنیم و به بررسی مطالعات انجام‌شده در هر یک از آن‌ها می‌پردازیم. راه‌های مختلفی برای ایجاد پراکندگی در خوشه‌بندی ترکیبی وجود دارد که عبارت‌اند از:
استفاده از الگوریتم‌های متفاوت خوشه‌بندی.
تغییر مقادیر اولیه و یا سایر پارامترهای الگوریتم خوشه‌بندی انتخاب‌شده.
انتخاب بعضی از ویژگی داده‌ها یا ایجاد ویژگی‌های جدید.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *