بخشی از پاورپوینت
اسلاید 1 :
خوشه بندي مقيد Constrained Clustering
اسلاید 2 :
فهرست مطالب
مقدمه ای بر خوشه بندی
ارزیابی خوشه بندی
خوشه بندی مقید
چالشها و راهکارها
پژوهش های انجام شده
اسلاید 3 :
خوشهبندي
خوشهبندي
گروهبندي دادهها به گونهاي که خصوصيات مشترک بين دادههاي هر گروه زياد و خصوصيات مشترک بين گروههاي متفاوت کم باشد.
سوال 1: خصوصيات مشترک؟ چگونگي تشخيص خصوصيات؟
طيف وسيع كاربرد
يادگيري ماشين، هوش مصنوعي، الگوشناسي، وب كاوي، تحليل پايگاه داده، پردازش متون و تصاوير، علوم پزشكي، علوم اجتماعي، اقتصاد و تجارت، علوم كامپيوتر، پزشكي
خوشهبندي به عنوان يك مساله مشكل
مهمترين دلايل مشكلبودن مساله:
ذات بدون ناظر بودن الگوريتمهاي خوشهبندي
ابهام در تعريف خوشه مناسب
مشكل بودن تعريف معيار فاصله مناسب
تعريف تابع هدف مناسب به منظور خوشهبندي
عدم وجود الگوريتم جامع براي حل همه مسائل خوشهبندي
اسلاید 4 :
روشهاي خوشهبندي (دسته بندی)
اسلاید 5 :
ارزیابی کلاسترینگ
چند مساله
تمایل به خوشه بندی شدن داده؟
آیا یک ساختار غیر تصادفی در داده وجود دارد؟
استفاده از تستهای آماری
تعداد خوشه ها؟
برخی الگوریتم ها نیاز به دانستن تعداد خوشه ها قبل از خوشه بندی دارند.
راهکارهای تقسیم و ادغام با معیارهایی از قبیل واریانس درون و برون خوشه ای
کیفیت خوشه بندی انجام شده؟
خوشه بندی انجام شده چقدر خوب است؟
ارائه معیارهای ارزیابی مناسب
اسلاید 6 :
ویژگیهای یک معیار ارزیابی مناسب (4 شرط)
Cluster homogeneity
هر چه خلوص در خوشه بندی (با دانستن کلاس اصلی داده ها، داده های هم کلاس در یک خوشه قرار بگیرند) بیشتر باشد این معیار بیشتر است.
داده های دسته های متفاوت در خوشه های متفاوت قرار داده شوند.
اسلاید 7 :
ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟)
Cluster completeness
نقطه مقابل Cluster homogeneity
داده ها ی دسته های یکسان در خوشه های یکسان قرار داده شوند.
اسلاید 8 :
ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟)
Rag bag
در برخی مسایل دسته ای به نام «متفرقه» داریم که شامل داده هایی است که نمی توانند با داده های دیگر کلاسها هم خوشه شوند.
جریمه انتساب این نوع داده ها به یک خوشه خالص بیشتر از انتساب آنها به خوشه متفرقه است .
اسلاید 9 :
ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟)
Small cluster preservation
هدف: ممانعت از شکسته شدن دسته های کوچک اشیا
تقسیم یک دسته کوچک از اشیا به دسته های ریز بسیار خطرناکتر از تقسیم دسته بزرگ به دسته های کوچکتر است.
داده ها ممکن است با فرض نویز یا outlier حذف شوند.
اسلاید 10 :
ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟)
معیار Bcubed
اسلاید 11 :
مسائل مطرح خوشهبندي
ذات بدون ناظر مساله
پيش فرضهاي اوليه
ساختار داده ها
معيارهاي فاصله و شباهت
تابع هدف
عدم انطباق پيش فرضها و مدل واقعي (Model mismatch)
راه حل؟
استفاده از اطلاعات جانبي
براي كمك به الگوريتمهاي خوشهبندي جهت توليد فرضهاي صحيح
اسلاید 12 :
اطلاعات جانبي
ساختار دادهها
هدف خوشهبندي
شكل خوشهها
بيشينه اندازه خوشهها
حداكثر اعضاي هر خوشه
قيدهاي در سطح نمونه
قيدهاي بايد-پيوند Must-link(ML)
قيدهاي نفي-پيوند Cannot-link(CL)
قابليت اين قيدها در تعريف قيدهاي پيچيده تر
قيد وجود حداقل يك همسايه در فاصله ε: با ايجاد قيد بايد-پيوند ميان هر داده و حداقل يكي از نقاط موجود در همسايگي ε
استفاده از اطلاعات جانبي در خوشهبندي
خوشه بندي مقيد
اسلاید 13 :
خوشهبندي مقيد (دستهبندي)
اسلاید 14 :
خوشهبندي مقيد (دستهبندي )
مبتني بر ارضاء قيد:
ارضاء سخت:
ارضاء تمامي قيدها به طور كامل
رويكرد جستجوي حريصانه، عدم يافتن يك جواب ممكن براي مساله حتي در صورت وجود جواب
COP-KMEANS [Wagstaff01]
ارضاء نرم: تا حد ممكن سعي در ارضاء قيدها دارند.
اسلاید 15 :
خوشهبندي مقيد (دستهبندي)
سلسله مراتبي:
با تغيير الگوريتمهاي خوشهبندي سلسلهمراتبي قابليت برآورده كردن قيدها را نيز در آنها تعبيه مينمايند.
خوشهبندي با ساختن دندروگرامي از دادهها
روش پايه:
ابتدا هر داده به عنوان يك خوشه درنظر گرفته مي شود.
عمل ادغام خوشهها تا هنگامي كه ادغام آنها هيچ قيدي را نقض نكند
روش Davidson [Davidson05]
ابتدا بستارهاي تراگذري مربوط به قيدهاي بايد-پيوند (ML) محاسبه ميشود
خوشهبندي را با X1+r خوشه آغاز مينمايد كهX1 تعداد نمونههايي است كه هيچ قيد بايد-پيوندي بر روي آنها اعمال نشده و r تعداد اجزاء همبند حاصل از قيدهاي بايد-پيوند است..
انتخاب دو نزديكترين خوشه و ادغام آنها تا زماني كه دو خوشه براي ادغام وجود دارند.
اسلاید 16 :
خوشهبندي مقيد (دستهبندي)
تغيير ماتريس فاصله
استفاده از اطلاعات قيدها قبل از خوشهبندي براي تغيير ماتريس فاصله و استفاده از آن در خوشهبندي نهايي
روش Klein [Klein02]
اسلاید 17 :
خوشهبندي مقيد (دستهبندي)
يادگيري معيار فاصله به عنوان محبوبترين روش خوشهبندي مقيد
معيار فاصله اقليدسي به عنوان معيار فاصله متداول در فرايند خوشهبندي
ناكارامدي معيار فاصله اقليدسي در توصيف صحيح فاصله در يك مجموعه داده نوعي
معيار فاصله ماهالانوبيس بسيار مورد توجه قرار گرفته است
اسلاید 18 :
مزايا و مشكلات استفاده از قيدها در خوشهبندي
مزايا
افزايش ميانگين دقت خوشهبندي [Wagstaff00]
توليد خوشههايي به شكل دلخواه [Wagstaff01b]
مشكلات
شدني بودن (Feasibility)
مفيد نبودن هر مجموعه اي از قيدها [Wagstaff06]
اسلاید 19 :
چالشهاي موجود در خوشهبندي مقيد
با وجود الگويتم هاي بسيار در خوشه بندي مقيد چالشهايي در اين حوزه وجود دارد كه نيازمند تحقيق گسترده مي باشد.
اسلاید 20 :
چالشهاي موجود در خوشهبندي مقيد
مجموعه قيدهاي متفاوت سودمندي متفاوتي براي الگوريتمهاي خوشهبندي دارند
قيدهايي كه الگوريتم خوشهبندي به خودي خود قادر به استخراج آن از دادهها باشد، تاثير چنداني بر بهبود دقت خوشهبندي نخواهد داشت
تعيين سودمندي يك مجموعه قيد قبل از خوشهبندي
به الگوريتم خوشهبندي اين قابليت را ميدهد كه تصميم بگيرد كه آيا از يك مجموعه قيد در راستاي خوشهبندي استفاده نمايد يا خير.
انتخاب بهترين مجموعه قيد ممكن.
از 1000 بار انتخاب تصادفي مجموعه قيدهاي 25 تايي، درصد مواردي كه سبب كاهش دقت خوشهبندي در چند الگوريتم شده است. (جدول از [Davidson06])
