بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
- مقدمه ای بر خوشه بندی
- ارزیابی خوشه بندی
- خوشه بندی مقید
- چالشها و راهکارها
- پژوهش های انجام شده
اسلاید 2 :
- خوشهبندي
گروهبندي دادهها به گونهاي که خصوصيات مشترک بين دادههاي هر گروه زياد و خصوصيات مشترک بين گروههاي متفاوت کم باشد.
سوال 1: خصوصيات مشترک؟ چگونگي تشخيص خصوصيات؟
- طيف وسيع كاربرد
يادگيري ماشين، هوش مصنوعي، الگوشناسي، وب كاوي، تحليل پايگاه داده، پردازش متون و تصاوير، علوم پزشكي، علوم اجتماعي، اقتصاد و تجارت، علوم كامپيوتر، پزشكي
- خوشهبندي به عنوان يك مساله مشكل
- مهمترين دلايل مشكلبودن مساله:
- ذات بدون ناظر بودن الگوريتمهاي خوشهبندي
- ابهام در تعريف خوشه مناسب
- مشكل بودن تعريف معيار فاصله مناسب
- تعريف تابع هدف مناسب به منظور خوشهبندي
- عدم وجود الگوريتم جامع براي حل همه مسائل خوشهبندي
اسلاید 3 :
- چند مساله
- تمایل به خوشه بندی شدن داده؟
- آیا یک ساختار غیر تصادفی در داده وجود دارد؟
- استفاده از تستهای آماری
- تعداد خوشه ها؟
- برخی الگوریتم ها نیاز به دانستن تعداد خوشه ها قبل از خوشه بندی دارند.
- راهکارهای تقسیم و ادغام با معیارهایی از قبیل واریانس درون و برون خوشه ای
- کیفیت خوشه بندی انجام شده؟
- خوشه بندی انجام شده چقدر خوب است؟
- ارائه معیارهای ارزیابی مناسب
اسلاید 4 :
- Cluster homogeneity
- هر چه خلوص در خوشه بندی (با دانستن کلاس اصلی داده ها، داده های هم کلاس در یک خوشه قرار بگیرند) بیشتر باشد این معیار بیشتر است.
- داده های دسته های متفاوت در خوشه های متفاوت قرار داده شوند.
اسلاید 5 :
- Cluster completeness
- نقطه مقابل Cluster homogeneity
- داده ها ی دسته های یکسان در خوشه های یکسان قرار داده شوند.
اسلاید 6 :
- Rag bag
- در برخی مسایل دسته ای به نام «متفرقه» داریم که شامل داده هایی است که نمی توانند با داده های دیگر کلاسها هم خوشه شوند.
- جریمه انتساب این نوع داده ها به یک خوشه خالص بیشتر از انتساب آنها به خوشه متفرقه است .
اسلاید 7 :
- Small cluster preservation
- هدف: ممانعت از شکسته شدن دسته های کوچک اشیا
- تقسیم یک دسته کوچک از اشیا به دسته های ریز بسیار خطرناکتر از تقسیم دسته بزرگ به دسته های کوچکتر است.
- داده ها ممکن است با فرض نویز یا outlier حذف شوند.
اسلاید 8 :
- اطلاعات جانبي
- ساختار دادهها
- هدف خوشهبندي
- شكل خوشهها
- بيشينه اندازه خوشهها
- حداكثر اعضاي هر خوشه
- قيدهاي در سطح نمونه
- قيدهاي بايد-پيوند Must-link(ML)
- قيدهاي نفي-پيوند Cannot-link(CL)
- قابليت اين قيدها در تعريف قيدهاي پيچيده تر
- قيد وجود حداقل يك همسايه در فاصله ε: با ايجاد قيد بايد-پيوند ميان هر داده و حداقل يكي از نقاط موجود در همسايگي ε
اسلاید 9 :
- مبتني بر ارضاء قيد:
- ارضاء سخت:
- ارضاء تمامي قيدها به طور كامل
- رويكرد جستجوي حريصانه، عدم يافتن يك جواب ممكن براي مساله حتي در صورت وجود جواب
- COP-KMEANS [Wagstaff01]
- ارضاء نرم: تا حد ممكن سعي در ارضاء قيدها دارند.
اسلاید 10 :
- سلسله مراتبي:
- با تغيير الگوريتمهاي خوشهبندي سلسلهمراتبي قابليت برآورده كردن قيدها را نيز در آنها تعبيه مينمايند.
- خوشهبندي با ساختن دندروگرامي از دادهها
- روش پايه:
- ابتدا هر داده به عنوان يك خوشه درنظر گرفته مي شود.
- عمل ادغام خوشهها تا هنگامي كه ادغام آنها هيچ قيدي را نقض نكند
- روش Davidson [Davidson05]
- ابتدا بستارهاي تراگذري مربوط به قيدهاي بايد-پيوند (ML) محاسبه ميشود
- خوشهبندي را با X1+r خوشه آغاز مينمايد كهX1 تعداد نمونههايي است كه هيچ قيد بايد-پيوندي بر روي آنها اعمال نشده و r تعداد اجزاء همبند حاصل از قيدهاي بايد-پيوند است..
- انتخاب دو نزديكترين خوشه و ادغام آنها تا زماني كه دو خوشه براي ادغام وجود دارند.