. الگوریتم پیوندی منفرد با استفاده از معیار فاصله 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
فصل اول
مقدمه
1. مقدمه
1-1. خوشه‌بندی
به عنوان یکی از شاخه‌های وسیع و پرکاربرد هوش مصنوعی1، یادگیری ماشین2 به تنظیم و اکتشاف شیوه‌ها و الگوریتم‌هایی می‌پردازد که بر اساس آن‌ها رایانه‌ها و سامانه‌های اطلاعاتی توانایی تعلم و یادگیری پیدا می‌کنند. طیف پژوهش‌هایی که در مورد یادگیری ماشینی صورت می‌گیرد گسترده ‌است. در سوی نظر‌ی آن پژوهش‌گران بر آن‌اند که روش‌های یادگیری تازه‌ای به وجود بیاورند و امکان‌پذیری و کیفیت یادگیری را برای روش‌هایشان مطالعه کنند و در سوی دیگر عده‌ای از پژوهش‌گران سعی می‌کنند روش‌های یادگیری ماشینی را بر مسائل تازه‌ای اعمال کنند. البته این طیف گسسته نیست و پژوهش‌های انجام‌شده دارای مؤلفه‌هایی از هر دو رو‌یکرد هستند. امروزه، داده‌کاوی3 به عنوان یک ابزار قوی برای تولید اطلاعات و دانش از داده‌های خام، در یادگیری ماشین شناخته‌شده و همچنان با سرعت در حال رشد و تکامل است. به طور کلی می‌توان تکنیک‌های داده‌کاوی را به دو دسته بانظارت4 و بدون نظارت5 تقسیم کرد [29, 46].
در روش بانظارت ما ورودی (داده یادگیری6) و خروجی (کلاس7 داده) یک مجموعه داده را به الگوریتم هوشمند می‌دهیم تا آن الگوی8 بین ورودی و خروجی را تشخیص دهد در این روش خروجی کار ما مدلی9 است که می‌تواند برای ورودی‌های جدید خروجی درست را پیش‌بینی10 کند. روش‌های طبقه‌بندی11 و قوانین انجمنی12 از این جمله تکنیک‌ها می‌باشد. روش‌های با نظارت کاربرد فراوانی دارند اما مشکل عمده این روش‌ها این است که همواره باید داده‌ای برای یادگیری وجود داشته باشد که در آن به ازای ورودی مشخص خروجی درست آن مشخص شده باشد. حال آنکه اگر در زمینه‌ای خاص داده‌ای با این فرمت وجود نداشته باشد این روش‌ها قادر به حل این‌گونه مسائل نخواهند بود [29, 68]. در روش بدون نظارت برخلاف یادگیری بانظارت هدف ارتباط ورودی و خروجی نیست، بلکه تنها دسته‌بندی ورودی‌ها است. این نوع یادگیری بسیار مهم است چون خیلی از مسائل (همانند دنیای ربات‌ها) پر از ورودی‌هایی است که هیچ برچسبی13 (کلاس) به آن‌ها اختصاص داده نشده است اما به وضوح جزئی از یک دسته هستند [46, 68]. خوشه‌بندی14 شاخص‌ترین روش در داده‌کاوی جهت حل مسائل به صورت بدون ناظر است. ایده اصلی خوشه‌بندی اطلاعات، جدا کردن نمونه‌ها از یکدیگر و قرار دادن آن‌ه
ا در گروه‌های شبیه به هم می‌باشد. به این معنی که نمونه‌های شبیه به هم باید در یک گروه قرار بگیرند و با نمونه‌های گروه‌های دیگر حداکثر متفاوت را دارا باشند [20, 26]. دلایل اصلی برای اهمیت خوشه‌بندی عبارت‌اند از:
اول، جمع‌آوری و برچسب‌گذاری یک مجموعه بزرگ از الگوهای نمونه می‌تواند بسیار پرکاربرد و باارزش باشد.
دوم، می‌توانیم از روش‌های خوشه‌بندی برای پیدا کردن و استخراج ویژگی‌ها15 و الگوهای جدید استفاده کنیم. این کار می‌تواند کمک به سزایی در کشف دانش ضمنی16 داده‌ها انجام دهد.
سوم، با خوشه‌بندی می‌توانیم یک دید و بینشی از طبیعت و ساختار داده به دست آوریم که این می‌تواند برای ما باارزش باشد.
چهارم، خوشه‌بندی می‌تواند منجر به کشف زیر رده‌های17 مجزا یا شباهت‌های بین الگوها ممکن شود که به طور چشمگیری در روش طراحی طبقه‌بندی قابل استفاده باشد.
1-2. خوشه‌بندی ترکیبی
هر یک از الگوریتم‌های خوشه‌بندی، با توجه به اینکه بر روی جنبه‌های متفاوتی از داده‌ها تاکید می‌کند، داده‌ها را به صورت‌های متفاوتی خوشه‌بندی می‌نماید. به همین دلیل، نیازمند روش‌هایی هستیم که بتواند با استفاده از ترکیب این الگوریتم‌ها و گرفتن نقاط قوت هر یک، نتایج بهینه‌تری را تولید کند. در واقع هدف اصلی خوشه‌بندی ترکیبی18 جستجوی بهترین خوشه‌ها با استفاده از ترکیب نتایج الگوریتم‌های دیگر است [1, 8, 9, 54, 56]. به روشی از خوشه‌بندی ترکیبی که زیرمجموعه‌ی منتخب از نتایج اولیه برای ترکیب و ساخت نتایج نهایی استفاده می‌شود خوشه‌بندی ترکیبی مبتنی بر انتخاب19 زیرمجموعه نتایج اولیه می‌گویند. در این روش‌ها بر اساس معیاری توافقی مجموعه‌ای از مطلوب‌ترین نتایج اولیه را انتخاب کرده و فقط توسط آن‌ها نتیجه نهایی را ایجاد می‌کنیم [21]. معیارهای مختلفی جهت انتخاب مطلوب‌ترین روش پیشنهاد شده است که معیار اطلاعات متقابل نرمال شده20، روش ماکزیموم21 و 22APMM برخی از آن‌ها می‌باشند [8, 9, 21, 67]. دو مرحله مهم در خوشه‌بندی ترکیبی عبارت‌اند از:
اول، الگوریتم‌های ابتدایی خوشه‌بندی که خوشه‌بندی