چكيدهخوشهبندي وظيفه کاوش الگوهاي پنهان در دادههاي بدون برچسب را بر عهده دارد. به خاطر پيچيدگي مسئله و ضعف روشهاي خوشهبندي پايه، امروزه روشهاي خوشهبندي ترکيبي مورد استفاده قرار ميگيرند. به روشي از خوشهبندي ترکيبي که در آن از زيرمجموعهاي منتخب از نتايج اوليه براي ترکيب و ساخت نتيجه نهايي استفاده ميشود خوشهبندي ترکيبي مبتني بر انتخاب زيرمجموعه نتايج اوليه ميگويند. در سالهاي اخير تمرکز بر روي ارزيابي نتايج اوليه براي انتخاب خوشه در خوشهبندي ترکيبي مورد توجه محققين زيادي قرار گرفته است. اما پاسخ به بعضي از سؤالات در اين زمينه همچنان با ابهامات زيادي روبروست. از طرفي ديگر، نظريه خرد جمعي که اولين بار توسط سورويکي منتشر شده است، نشان ميدهد که قضاوتهاي جمعي و دموکراتيک از اعتبار بيشتري نسبت به آنچه که ما انتظار داشتيم برخوردار هستند. اين نظريه چهار شرط پراکندگي، استقلال، عدم تمرکز و روش ترکيب مناسب آراء را براي هر جمعيت خردمند لازم و کافي ميداند. هدف اين تحقيق پيشنهاد فرآيندي جهت نگاشت و بهکارگيري نظريه خرد جمعي در انتخاب زيرمجموعه مناسب در خوشهبندي ترکيبي مبتني بر انتخاب ميباشد. از اين روي در اين تحقيق ابتدا با استفاده از تعاريف مطرحشده در نظريه خرد جمعي باز تعريفي متناسب با خوشهبندي ترکيبي مبتني بر انتخاب ارائه ميشود و بر اساس آن دو روش براي ترکيب اين دو مفهوم پيشنهاد ميشود. در روش پيشنهادي اول الگوريتمهاي خوشهبندي اوليه غير هم نام کاملاً مستقل فرض خواهند شد و براي ارزيابي استقلال الگوريتمهاي هم نام نياز به آستانهگيري ميباشد. در روش دوم، سعي شده است تا دو بخش از روش اول بهبود يابد. از اين روي جهت مدلسازي الگوريتمها و ارزيابي استقلال آنها نسبت به هم يک روش مبتني بر گراف کد الگوريتم ارائه ميشود و ميزان استقلال به دست آمده در اين روش به عنوان وزني براي ارزيابي پراکندگي در تشکيل جواب نهايي مورد استفاده قرار ميگيرد. جهت بررسي ادعاهاي اين تحقيق در بخش ارزيابي دقت و اطلاعات متقابل نرمال شدهي روشهاي پيشنهادي بر روي دادهّهاي استاندارد با روشهاي پايه، روش ترکيب کامل و چند روش معروف خوشهبندي ترکيبي مبتني بر انتخاب مقايسه ميشوند که اين مقايسه کاراريي بالاي روشهاي پيشنهادي اين تحقيق در اکثر موارد نسبت به ساير روشهاي مطرح شده را نشان ميدهد. همچنين در بخش نتيجهگيري چندين روش توسعه جهت كارهاي آتي پيشنهاد ميشود.واژههاي كليدي: خوشهبندي ترکيبي، خرد جمعي، استقلال الگوريتمهاي خوشهبندي، پراکندگي نتايج خوشهبندي اوليه، عدم تمرکز در چهارچوب خوشهبندي ترکيبيفهرست مطالبفصل اول1. مقدمه21-1. خوشهبندي21-2. خوشهبندي تركيبي41-3. خرد جمعي41-4. خوشهبندي مبتني بر انتخاب بر اساس نظريه خرد جمعي51-4-1- فرضيات تحقيق6فصل دوم2. مروري بر ادبيات تحقيق92-1. مقدمه92-2. خوشهبندي92-2-1. الگوريتمهاي خوشهبندي پايه92-2-1-1. الگوريتمهاي سلسله مراتبي102-2-1-1-1. تعاريف و نمادها112-2-1-1-2. الگوريتم پيوندي منفرد132-2-1-1-3. الگوريتم پيوندي کامل132-2-1-1-4. الگوريتم پيوندي ميانگين142-2-1-1-5. الگوريتم پيوندي بخشي152-2-1-2. الگوريتمهاي افرازبندي152-2-1-2-1. الگوريتم K-means162-2-1-2-2. الگوريتم FCM172-2-1-2-3. الگوريتم طيفي192-2-1-2-3-1. الگوريتم برش نرمال202-2-1-2-3-2. الگوريتم NJW212-2-1-2-4. الگوريتم خوشهبندي کاهشي222-2-1-2-5. الگوريتم خوشهبندي Median K-Flat232-2-1-2-6. الگوريتم خوشهبندي مخلوط گوسي252-2-2. معيارهاي ارزيابي272-2-2-1. معيار SSE282-2-2-2. معيار اطلاعات متقابل نرمال شده302-2-2-3. معيار APMM322-۳. خوشهبندي ترکيبي332-۳-1. ايجاد تنوع در خوشهبندي ترکيبي342-۳-1-1. استفاده از الگوريتمهاي مختلف خوشهبندي ترکيبي352-۳-1-2. تغيير پارامترهاي اوليه خوشهبندي ترکيبي352-۳-1-3. انتخاب يا توليد ويژگيهاي جديد362-۳-1-4. انتخاب زيرمجموعهاي از مجموعه داده اصلي362-۳-2. تركيب نتايج با تابع توافقي372-۳-2-1. روش مبتني بر مدل مخلوط372-۳-2-2. روش مبتني بر ابر گراف442-۳-2-2-1. روش CSPA462-۳-2-2-2. روش HGPA472-۳-2-2-3. روش MCLA482-۳-2-3. روشهاي مبتني بر ماتريس همبستگي502-۳-2-3-1. الگوريتمهاي سلسله مراتبي تراكمي512-۳-2-3-2. الگوريتم افرازبندي گراف با تکرار522-3-3. الگوريتمهاي خوشهبندي تركيبي كامل562-4. خوشهبندي تركيبي مبتني بر انتخاب562-4-1. خوشهبندي تركيبي مبتني بر انتخاب فرن و لين572-4-1-1. تعريف معيار کيفيت در روش فرن و لين572-۴-۱-2. تعريف معيار پراکندگي در روش فرن و لين582-۴-۱-3. راهکار انتخاب خوشه براي تشکيل نتيجه نهايي در روش فرن و لين582-4-2. الگوريتم هوشمند طبقهبندي مجموعه دادهها602-4-3. خوشهبندي ترکيبي طيفي مبتني بر انتخاب بر اساس شباهت612-4-3-1. معيار ارزيابي در روش پيشنهادي ژيا612-4-3-2. انتخاب خوشهبندي بر اساس قانون نزديکترين همسايه در روش ژيا622-4-4. خوشهبندي ترکيبي انتخابي ليمين642-4-4-1. انتخاب افراز مرجع در روش ليمين642-4-4-2. راهکار انتخاب خوشه در روش ليمين662-4-4-3. چهارچوب الگوريتم خوشهبندي انتخابي ليمين682-4-5. خوشهبندي بر اساس معيار MAX با استفاده از مجموعهاي از خوشههاي يک افراز692-4-5-1. راهكار ارزيابي خوشهي MAX692-4-5-2. روش انباشت مدارك توسعهيافته702-4-6. خوشهبندي بر اساس معيار APMM با استفاده از مجموعهاي از خوشههاي يک افراز702-5. روش بهترين افراز توافقي اعتبارسنجي شده722-6. استفاده از نظريه خرد جمعي در علوم رايانه73 فصل سوم3. روش تحقيق763-1. مقدمه763-2. نظريه خرد جمعي773-2-1. شرايط جامعه خردمند783-2-1-1. تعريف معيار پراكندگي783-2-1-2. تعريف معيار استقلال793-2-1-3. تعريف معيار عدم تمركز793-2-1-4. روش تركيب مناسب803-2-2. اهميت و رابطه استقلال و پراكندگي در خرد جمعي803-2-3. استثناءها در خرد جمعي823-3. خوشهبندي خردمند با استفاده از آستانهگيري823-3-1. روش ارزيابي پراکندگي نتايج843-3-2. روش ارزيابي استقلال الگوريتمها853-3-3. عدم تمرکز در بخشهاي سازنده خوشهبندي ترکيبي883-3-4. مکانيزم ترکيب مناسب903-3-5. بررسي تأثير مکانيزم بازخورد در کيفيت نتيجه نهايي903-3-6. شبه کد خوشهبندي خردمند با استفاده از آستانهگيري913-4. خوشهبندي خردمند مبتني بر گراف استقلال الگوريتم933-4-1. بررسي مکانيزم حل مسائل توسط الگوريتمهاي خوشهبندي933-4-2. مدلسازي گراف استقلال الگوريتم953-4-2-1. زبان استقلال الگوريتم خوشهبندي963-4-2-2. تبديل کد به گراف استقلال الگوريتم993-4-۲-۳. ارزيابي گراف استقلال الگوريتم1073-4-3. چهارچوب خوشهبندي خردمند مبتني بر گراف استقلال الگوريتم1103-4-3-1. ارزيابي استقلال الگوريتم1103-4-3-2. روش انباشت مدارک وزندار1123-4-3-3. شبه کد خوشهبندي خردمند مبتني بر گراف استقلال الگوريتم113فصل چهارم4. پيادهسازي و تحليل نتايج1164-1. مقدمه1164-2. مجموعه داده1164-3. مدلسازي الگوريتمها به زبان استقلال الگوريتم1184-4. ابزار تحليلگر کد استقلال الگوريتم1284-5. نتايج آزمايشها130فصل پنجم5. جمعبندي و کارهاي آينده1405-1. جمعبندي1405-2. کارهاي آينده141منابع و مآخذ142 فهرست جداولفصل سومجدول3-1.نگاشت لغات لاتين در خوشهبندي ترکيبي به نظريه خرد جمعي .......................................................... 93جدول3-2.يک نمونه از جدول نگاشت استاندارد کد .............................................................................................. 98فصل چهارمجدول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فصل اولمقدمهبه عنوان يکي از شاخههاي وسيع و پرکاربرد هوش مصنوعي[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] مجزا يا شباهتهاي بين الگوها ممكن شود كه به طور چشمگيري در روش طراحي طبقهبندي قابل استفاده باشد.هر يك از الگوريتمهاي خوشهبندي، با توجه به اينكه بر روي جنبههاي متفاوتي از دادهها تاكيد ميکند، دادهها را به صورتهاي متفاوتي خوشهبندي مينمايد. به همين دليل، نيازمند روشهايي هستيم كه بتواند با استفاده از تركيب اين الگوريتمها و گرفتن نقاط قوت هر يك، نتايج بهينهتري را توليد كند. در واقع هدف اصلي خوشهبندي تركيبي[18] جستجوي بهترين خوشهها با استفاده از تركيب نتايج الگوريتمهاي ديگر است [1, 8, 9, 54, 56]. به روشي از خوشهبندي ترکيبي که زيرمجموعهي منتخب از نتايج اوليه براي ترکيب و ساخت نتايج نهايي استفاده ميشود خوشهبندي ترکيبي مبتني بر انتخاب[19] زيرمجموعه نتايج اوليه ميگويند. در اين روشها بر اساس معياري توافقي مجموعهاي از مطلوبترين نتايج اوليه را انتخاب كرده و فقط توسط آنها نتيجه نهايي را ايجاد ميکنيم [21]. معيارهاي مختلفي جهت انتخاب مطلوبترين روش پيشنهاد شده است كه معيار اطلاعات متقابل نرمال شده[20]، روش ماكزيموم[21] و [22]APMM برخي از آنها ميباشند [8, 9, 21, 67]. دو مرحله مهم در خوشهبندي ترکيبي عبارتاند از:اول، الگوريتمهاي ابتدايي خوشهبندي که خوشهبندي اوليه را انجام ميدهد.دوم، جمعبندي نتايج اين الگوريتمهاي اوليه (پايه) براي به دست آوردن نتيجه نهايي.نظريه خرد جمعي[23] كه اولين بار توسط سورويکي[24] در سال 2004 در كتابي با همان عنوان منتشر شد، استنباطي از مسائل مطرحشده توسط گالتون[25] و کندورست[26] ميباشد، و نشان ميدهد که قضاوتهاي جمعي و دموکراتيک از اعتبار بيشتري نسبت به آنچه که ما انتظار داشتيم برخوردار است، ما تأثيرات اين ايده را در حل مسائل سياسي، اجتماعي در طي سالهاي اخير شاهد هستيم. در ادبيات خرد جمعي هر جامعهاي را خردمند نميگويند. از ديدگاه سورويكي خردمند بودن جامعه در شرايط چهارگانه پراكندگي[27]، استقلال[28]، عدم تمركز[29] و روش ترکيب مناسب[30] است [55].هدف از اين تحقيق استفاده از نظريه خرد جمعي برای انتخاب زيرمجموعهي مناسب در خوشهبندي ترکيبي ميباشد. تعاريف سورويکي از خرد جمعي مطابق با مسائل اجتماعي است و در تعاريف آن عناصر سازنده تصميمات رأي افراد ميباشد. در اين تحقيق ابتدا مبتني بر تعاريف پايه سورويکي از خرد جمعي و ادبيات مطرح در خوشهبندي ترکيبي، تعريف پايهاي از ادبيات خرد جمعي در خوشهبندي ترکيبي ارائه ميدهيم و بر اساس آن الگوريتم پيشنهادي خود را در جهت پيادهسازي خوشهبندي ترکيبي ارائه ميدهيم [55]. شرايط چهارگانه خوشهبندي خردمند که متناسب با تعاريف سورويکي باز تعريف شده است به شرح زير ميباشد:
خوشهبندي مبتني بر انتخاب بر اساس نظريه خرد جمعي word
چكيدهخوشهبندي وظيفه کاوش الگوهاي پنهان در دادههاي بدون برچسب را بر عهده دارد. به خاطر پيچيدگي مسئله و ضعف روشهاي خوشهبندي پايه، امروزه روشهاي خوشهبندي ترکيبي مورد استفاده قرار ميگيرند. به روشي از خوشهبندي ترکيبي که در آن از زيرمجموعهاي منتخب از نتايج اوليه براي ترکيب و ساخت نتيجه نهايي استفاده ميشود خوشهبندي ترکيبي مبتني بر انتخاب زيرمجموعه نتايج اوليه ميگويند. در سالهاي اخير تمرکز بر روي ارزيابي نتايج اوليه براي انتخاب خوشه در خوشهبندي ترکيبي مورد توجه محققين زيادي قرار گرفته است. اما پاسخ به بعضي از سؤالات در اين زمينه همچنان با ابهامات زيادي روبروست. از طرفي ديگر، نظريه خرد جمعي که اولين بار توسط سورويکي منتشر شده است، نشان ميدهد که قضاوتهاي جمعي و دموکراتيک از اعتبار بيشتري نسبت به آنچه که ما انتظار داشتيم برخوردار هستند. اين نظريه چهار شرط پراکندگي، استقلال، عدم تمرکز و روش ترکيب مناسب آراء را براي هر جمعيت خردمند لازم و کافي ميداند. هدف اين تحقيق پيشنهاد فرآيندي جهت نگاشت و بهکارگيري نظريه خرد جمعي در انتخاب زيرمجموعه مناسب در خوشهبندي ترکيبي مبتني بر انتخاب ميباشد. از اين روي در اين تحقيق ابتدا با استفاده از تعاريف مطرحشده در نظريه خرد جمعي باز تعريفي متناسب با خوشهبندي ترکيبي مبتني بر انتخاب ارائه ميشود و بر اساس آن دو روش براي ترکيب اين دو مفهوم پيشنهاد ميشود. در روش پيشنهادي اول الگوريتمهاي خوشهبندي اوليه غير هم نام کاملاً مستقل فرض خواهند شد و براي ارزيابي استقلال الگوريتمهاي هم نام نياز به آستانهگيري ميباشد. در روش دوم، سعي شده است تا دو بخش از روش اول بهبود يابد. از اين روي جهت مدلسازي الگوريتمها و ارزيابي استقلال آنها نسبت به هم يک روش مبتني بر گراف کد الگوريتم ارائه ميشود و ميزان استقلال به دست آمده در اين روش به عنوان وزني براي ارزيابي پراکندگي در تشکيل جواب نهايي مورد استفاده قرار ميگيرد. جهت بررسي ادعاهاي اين تحقيق در بخش ارزيابي دقت و اطلاعات متقابل نرمال شدهي روشهاي پيشنهادي بر روي دادهّهاي استاندارد با روشهاي پايه، روش ترکيب کامل و چند روش معروف خوشهبندي ترکيبي مبتني بر انتخاب مقايسه ميشوند که اين مقايسه کاراريي بالاي روشهاي پيشنهادي اين تحقيق در اکثر موارد نسبت به ساير روشهاي مطرح شده را نشان ميدهد. همچنين در بخش نتيجهگيري چندين روش توسعه جهت كارهاي آتي پيشنهاد ميشود.واژههاي كليدي: خوشهبندي ترکيبي، خرد جمعي، استقلال الگوريتمهاي خوشهبندي، پراکندگي نتايج خوشهبندي اوليه، عدم تمرکز در چهارچوب خوشهبندي ترکيبيفهرست مطالبفصل اول1. مقدمه21-1. خوشهبندي21-2. خوشهبندي تركيبي41-3. خرد جمعي41-4. خوشهبندي مبتني بر انتخاب بر اساس نظريه خرد جمعي51-4-1- فرضيات تحقيق6فصل دوم2. مروري بر ادبيات تحقيق92-1. مقدمه92-2. خوشهبندي92-2-1. الگوريتمهاي خوشهبندي پايه92-2-1-1. الگوريتمهاي سلسله مراتبي102-2-1-1-1. تعاريف و نمادها112-2-1-1-2. الگوريتم پيوندي منفرد132-2-1-1-3. الگوريتم پيوندي کامل132-2-1-1-4. الگوريتم پيوندي ميانگين142-2-1-1-5. الگوريتم پيوندي بخشي152-2-1-2. الگوريتمهاي افرازبندي152-2-1-2-1. الگوريتم K-means162-2-1-2-2. الگوريتم FCM172-2-1-2-3. الگوريتم طيفي192-2-1-2-3-1. الگوريتم برش نرمال202-2-1-2-3-2. الگوريتم NJW212-2-1-2-4. الگوريتم خوشهبندي کاهشي222-2-1-2-5. الگوريتم خوشهبندي Median K-Flat232-2-1-2-6. الگوريتم خوشهبندي مخلوط گوسي252-2-2. معيارهاي ارزيابي272-2-2-1. معيار SSE282-2-2-2. معيار اطلاعات متقابل نرمال شده302-2-2-3. معيار APMM322-۳. خوشهبندي ترکيبي332-۳-1. ايجاد تنوع در خوشهبندي ترکيبي342-۳-1-1. استفاده از الگوريتمهاي مختلف خوشهبندي ترکيبي352-۳-1-2. تغيير پارامترهاي اوليه خوشهبندي ترکيبي352-۳-1-3. انتخاب يا توليد ويژگيهاي جديد362-۳-1-4. انتخاب زيرمجموعهاي از مجموعه داده اصلي362-۳-2. تركيب نتايج با تابع توافقي372-۳-2-1. روش مبتني بر مدل مخلوط372-۳-2-2. روش مبتني بر ابر گراف442-۳-2-2-1. روش CSPA462-۳-2-2-2. روش HGPA472-۳-2-2-3. روش MCLA482-۳-2-3. روشهاي مبتني بر ماتريس همبستگي502-۳-2-3-1. الگوريتمهاي سلسله مراتبي تراكمي512-۳-2-3-2. الگوريتم افرازبندي گراف با تکرار522-3-3. الگوريتمهاي خوشهبندي تركيبي كامل562-4. خوشهبندي تركيبي مبتني بر انتخاب562-4-1. خوشهبندي تركيبي مبتني بر انتخاب فرن و لين572-4-1-1. تعريف معيار کيفيت در روش فرن و لين572-۴-۱-2. تعريف معيار پراکندگي در روش فرن و لين582-۴-۱-3. راهکار انتخاب خوشه براي تشکيل نتيجه نهايي در روش فرن و لين582-4-2. الگوريتم هوشمند طبقهبندي مجموعه دادهها602-4-3. خوشهبندي ترکيبي طيفي مبتني بر انتخاب بر اساس شباهت612-4-3-1. معيار ارزيابي در روش پيشنهادي ژيا612-4-3-2. انتخاب خوشهبندي بر اساس قانون نزديکترين همسايه در روش ژيا622-4-4. خوشهبندي ترکيبي انتخابي ليمين642-4-4-1. انتخاب افراز مرجع در روش ليمين642-4-4-2. راهکار انتخاب خوشه در روش ليمين662-4-4-3. چهارچوب الگوريتم خوشهبندي انتخابي ليمين682-4-5. خوشهبندي بر اساس معيار MAX با استفاده از مجموعهاي از خوشههاي يک افراز692-4-5-1. راهكار ارزيابي خوشهي MAX692-4-5-2. روش انباشت مدارك توسعهيافته702-4-6. خوشهبندي بر اساس معيار APMM با استفاده از مجموعهاي از خوشههاي يک افراز702-5. روش بهترين افراز توافقي اعتبارسنجي شده722-6. استفاده از نظريه خرد جمعي در علوم رايانه73 فصل سوم3. روش تحقيق763-1. مقدمه763-2. نظريه خرد جمعي773-2-1. شرايط جامعه خردمند783-2-1-1. تعريف معيار پراكندگي783-2-1-2. تعريف معيار استقلال793-2-1-3. تعريف معيار عدم تمركز793-2-1-4. روش تركيب مناسب803-2-2. اهميت و رابطه استقلال و پراكندگي در خرد جمعي803-2-3. استثناءها در خرد جمعي823-3. خوشهبندي خردمند با استفاده از آستانهگيري823-3-1. روش ارزيابي پراکندگي نتايج843-3-2. روش ارزيابي استقلال الگوريتمها853-3-3. عدم تمرکز در بخشهاي سازنده خوشهبندي ترکيبي883-3-4. مکانيزم ترکيب مناسب903-3-5. بررسي تأثير مکانيزم بازخورد در کيفيت نتيجه نهايي903-3-6. شبه کد خوشهبندي خردمند با استفاده از آستانهگيري913-4. خوشهبندي خردمند مبتني بر گراف استقلال الگوريتم933-4-1. بررسي مکانيزم حل مسائل توسط الگوريتمهاي خوشهبندي933-4-2. مدلسازي گراف استقلال الگوريتم953-4-2-1. زبان استقلال الگوريتم خوشهبندي963-4-2-2. تبديل کد به گراف استقلال الگوريتم993-4-۲-۳. ارزيابي گراف استقلال الگوريتم1073-4-3. چهارچوب خوشهبندي خردمند مبتني بر گراف استقلال الگوريتم1103-4-3-1. ارزيابي استقلال الگوريتم1103-4-3-2. روش انباشت مدارک وزندار1123-4-3-3. شبه کد خوشهبندي خردمند مبتني بر گراف استقلال الگوريتم113فصل چهارم4. پيادهسازي و تحليل نتايج1164-1. مقدمه1164-2. مجموعه داده1164-3. مدلسازي الگوريتمها به زبان استقلال الگوريتم1184-4. ابزار تحليلگر کد استقلال الگوريتم1284-5. نتايج آزمايشها130فصل پنجم5. جمعبندي و کارهاي آينده1405-1. جمعبندي1405-2. کارهاي آينده141منابع و مآخذ142 فهرست جداولفصل سومجدول3-1.نگاشت لغات لاتين در خوشهبندي ترکيبي به نظريه خرد جمعي .......................................................... 93جدول3-2.يک نمونه از جدول نگاشت استاندارد کد .............................................................................................. 98فصل چهارمجدول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فصل اولمقدمهبه عنوان يکي از شاخههاي وسيع و پرکاربرد هوش مصنوعي[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] مجزا يا شباهتهاي بين الگوها ممكن شود كه به طور چشمگيري در روش طراحي طبقهبندي قابل استفاده باشد.هر يك از الگوريتمهاي خوشهبندي، با توجه به اينكه بر روي جنبههاي متفاوتي از دادهها تاكيد ميکند، دادهها را به صورتهاي متفاوتي خوشهبندي مينمايد. به همين دليل، نيازمند روشهايي هستيم كه بتواند با استفاده از تركيب اين الگوريتمها و گرفتن نقاط قوت هر يك، نتايج بهينهتري را توليد كند. در واقع هدف اصلي خوشهبندي تركيبي[18] جستجوي بهترين خوشهها با استفاده از تركيب نتايج الگوريتمهاي ديگر است [1, 8, 9, 54, 56]. به روشي از خوشهبندي ترکيبي که زيرمجموعهي منتخب از نتايج اوليه براي ترکيب و ساخت نتايج نهايي استفاده ميشود خوشهبندي ترکيبي مبتني بر انتخاب[19] زيرمجموعه نتايج اوليه ميگويند. در اين روشها بر اساس معياري توافقي مجموعهاي از مطلوبترين نتايج اوليه را انتخاب كرده و فقط توسط آنها نتيجه نهايي را ايجاد ميکنيم [21]. معيارهاي مختلفي جهت انتخاب مطلوبترين روش پيشنهاد شده است كه معيار اطلاعات متقابل نرمال شده[20]، روش ماكزيموم[21] و [22]APMM برخي از آنها ميباشند [8, 9, 21, 67]. دو مرحله مهم در خوشهبندي ترکيبي عبارتاند از:اول، الگوريتمهاي ابتدايي خوشهبندي که خوشهبندي اوليه را انجام ميدهد.دوم، جمعبندي نتايج اين الگوريتمهاي اوليه (پايه) براي به دست آوردن نتيجه نهايي.نظريه خرد جمعي[23] كه اولين بار توسط سورويکي[24] در سال 2004 در كتابي با همان عنوان منتشر شد، استنباطي از مسائل مطرحشده توسط گالتون[25] و کندورست[26] ميباشد، و نشان ميدهد که قضاوتهاي جمعي و دموکراتيک از اعتبار بيشتري نسبت به آنچه که ما انتظار داشتيم برخوردار است، ما تأثيرات اين ايده را در حل مسائل سياسي، اجتماعي در طي سالهاي اخير شاهد هستيم. در ادبيات خرد جمعي هر جامعهاي را خردمند نميگويند. از ديدگاه سورويكي خردمند بودن جامعه در شرايط چهارگانه پراكندگي[27]، استقلال[28]، عدم تمركز[29] و روش ترکيب مناسب[30] است [55].هدف از اين تحقيق استفاده از نظريه خرد جمعي برای انتخاب زيرمجموعهي مناسب در خوشهبندي ترکيبي ميباشد. تعاريف سورويکي از خرد جمعي مطابق با مسائل اجتماعي است و در تعاريف آن عناصر سازنده تصميمات رأي افراد ميباشد. در اين تحقيق ابتدا مبتني بر تعاريف پايه سورويکي از خرد جمعي و ادبيات مطرح در خوشهبندي ترکيبي، تعريف پايهاي از ادبيات خرد جمعي در خوشهبندي ترکيبي ارائه ميدهيم و بر اساس آن الگوريتم پيشنهادي خود را در جهت پيادهسازي خوشهبندي ترکيبي ارائه ميدهيم [55]. شرايط چهارگانه خوشهبندي خردمند که متناسب با تعاريف سورويکي باز تعريف شده است به شرح زير ميباشد: