13269

13269

انتخاب خوشه بندي تركيبي مبتني بر بهينه سازي رياضي و اجتماعي

دكتري

كامپيوتر - هوش مصنوعي و رباتيك

ارديبهشت 1393

ارديبهشت 1393

دكتر بهروز مينايي بيدگلي

دكتر مرتضي آنالويي

چكيده به مسئله خوشه بندي داده كه در آن خوشه هاي نهايي با تركيب يك مجموعه از نتايج خوشه بندي هاي پايه استخراج مي شوند، اصطلاحا مسئله خوشه بندي تركيبي گفته مي شود. همچنين، به چگونگي استخراج خوشه هاي نهايي با استفاده از تنها زيرمجموعه اي از نتايج مجمع اوليه خوشه ها، مسئله انتخاب خوشه بندي تركيبي گفته مي شود. در اين رساله به مسئله خوشه بندي تركيبي در حالت عام و مسئله انتخاب خوشه بندي تركيبي در حالت خاص پرداخته شده است. به خوشه اي كه در افرازهاي مختلف روي مجموعه داده هاي نمونه برداري شده به صورت متناوب تكرار شده باشد، اصطلاحا خوشه پايدار گفته مي شود. در اين رساله، يك چارچوب جديد براي مسئله انتخاب خوشه بندي تركيبي ارائه شده است كه در آن پس از ارزيابي پايداري خوشه هاي حاضر در مجمع، بخشي از خوشه هاي پايدارتر براي تشكيل مجمع نهايي خوشه ها انتخاب مي شوند. همچنين، چند معيار جديد مبتني برتئوري اطلاعات براي ارزيابي پايداري خوشه ارائه شده است. براي تجميع اطلاعات خوشه هاي انتخابي در ماتريس هم رويدادي، يك روش جديد به نام انباشت مدارك توسعه يافته ارائه شده است. با الهام از روش هاي مطرح شده در حوزه تحليل شبكه هاي اجتماعي، يك مدل برنامه ريزي مجذوري 1-0 براي بهينه سازي استخراج خوشه هايي با بالاترين پيمانگي پيشنهاد گرديده، و سپس راهكاري براي تبديل آن به مدل برنامه ريزي خطي 1-0 ارائه شد. به علاوه، يك روش جديد سلسله مراتبي تجمعي به نام اتصال مجموع به عنوان تابع توافقي براي بهينه سازي اين مدل و استخراج خوشه هاي نهايي پيشنهاد شده است. در اين رساله يك مدل سازي رياضي مبتني بر نمايش رشته اي (رشته هاي دودويي) براي مسئله خوشه بندي تركيبي ارايه شده است. با توجه به غيرخطي بودن اين مدل سازي و ناكارامدي ابزارهاي رياضي براي حل مسائل غيرخطي در حالت عمومي ، از الگوريتم ژنتيك با عملگرهاي تركيب و جهش خاص منظوره، براي حل آن بهره گرفته شده است. همچنين، با الهام از علوم اجتماعي، يك روش خوشه بندي تركيبي مبتني بر خرد جمعي ارائه شده است. در اين روش، علاوه بر بررسي پراكندگي (تنوع) نتايج حاضر در مجمع افرازهاي اوليه، به استقلال آنها نيز توجه شده و روش هاي جديدي براي ارزيابي هر دو معيار ارائه شده است. نتايج تجربي كه در آن از ١٧ تابع توافقي از 5 خانواده مختلف از الگوريتم هاي تركيب كننده استفاده شده است، نشان مي دهند كه استفاده از چارچوب پيشنهادي انتخاب خوشه بندي تركيبي منجر به بهبود بيش از ٣درصدي دقت نسبت به بهترين روش مورد مقايسه روي ميانگين ١٢ مجموعه داده استاندارد شده است. واژگان كليدي: خوشه بندي تركيبي، انتخاب خوشه بندي تركيبي، ارزيابي خوشه، بهينه سازي رياضي، بهينه سازي اجتماعي