توضیحات

 دانلود پاورپوینت مقدمه ای بر خوشه بندی و بررسی چالش‌های موجود در خوشهبندی مقید

خوشهبندی مقید Constrained Clustering

عنوان های پاورپوینت  : 

مقدمه ای بر خوشه بندی و بررسی چالش‌های موجود در خوشهبندی مقید

خوشهبندی مقید Constrained Clustering

فهرست مطالب

خوشهبندی

روشهای خوشهبندی (دسته بندی)

ارزیابی کلاسترینگ

ویژگیهای یک معیار ارزیابی مناسب (4 شرط)

ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟)

مسائل مطرح خوشهبندی

استفاده از اطلاعات جانبی در خوشهبندی

خوشهبندی مقید (دستهبندی)

مزایا و مشکلات استفاده از قیدها در خوشهبندی

چالش‌های موجود در خوشهبندی مقید

خوشهبندی مقید با رویکرد انتخاب فعال قیدها

خوشه بندی مقید

مدل خطی رویکرد دوم

مدل غیرخطی رویکرد دوم

انتخاب فعال قیدها (مستقل از الگوریتم خوشه بندی مقید)

انتخاب فعال قیدها

نگاه تکرارشونده به حل مساله در ادامه راه

منابع

قسمت ها و تکه های اتفاقی از فایل

استفاده از اطلاعات جانبی در خوشهبندی

اطلاعات جانبی

ساختار دادهها

هدف خوشهبندی

شکل خوشهها

بیشینه اندازه خوشهها

حداکثر اعضای هر خوشه

قیدهای در سطح نمونه

قیدهای باید-پیوند Must-link)ML)

قیدهای نفی-پیوند Cannot-link)CL)

قابلیت این قیدها در تعریف قیدهای پیچیده تر

قید وجود حداقل یک همسایه در فاصله ε: با ایجاد قید باید-پیوند میان هر داده و حداقل یکی از نقاط موجود در همسایگی ε

خوشهبندی مقید (دستهبندی )

مبتنی بر ارضاء قید:

ارضاء سخت:

ارضاء تمامی قیدها به طور کامل

رویکرد جستجوی حریصانه، عدم یافتن یک جواب ممکن برای مساله حتی در صورت وجود جواب

COP-KMEANS [Wagstaff01]

ارضاء نرم: تا حد ممکن سعی در ارضاء قیدها دارند.

خوشهبندی مقید (دستهبندی)

سلسله مراتبی:

با تغییر الگوریتم‌های خوشهبندی سلسلهمراتبی قابلیت برآورده کردن قیدها را نیز در آنها تعبیه می‌نمایند.

خوشهبندی با ساختن دندروگرامی از دادهها

روش پایه:

ابتدا هر داده به عنوان یک خوشه درنظر گرفته می شود.

عمل ادغام خوشهها تا هنگامی که ادغام آنها هیچ قیدی را نقض نکند

روش Davidson [Davidson05]

ابتدا بستارهای تراگذری مربوط به قیدهای باید-پیوند (ML) محاسبه می‌شود

خوشهبندی را با X1+r خوشه آغاز می‌نماید کهX1  تعداد نمونههایی است که هیچ قید باید-پیوندی بر روی آنها اعمال نشده و  r تعداد اجزاء همبند حاصل از قیدهای باید-پیوند است..

انتخاب دو نزدیکترین خوشه و ادغام آنها تا زمانی که دو خوشه برای ادغام وجود دارند.

خوشهبندی مقید (دستهبندی)

تغییر ماتریس فاصله

استفاده از اطلاعات قیدها قبل از خوشهبندی برای تغییر ماتریس فاصله و استفاده از آن در خوشهبندی نهایی

روش Klein [Klein02]

خوشهبندی مقید (دستهبندی)

یادگیری معیار فاصله به عنوان محبوب‌ترین روش خوشهبندی مقید

معیار فاصله اقلیدسی به عنوان معیار فاصله متداول در فرایند خوشهبندی

ناکارامدی معیار فاصله اقلیدسی در توصیف صحیح فاصله در یک مجموعه داده نوعی

معیار فاصله ماهالانوبیس بسیار مورد توجه قرار گرفته است

مزایا و مشکلات استفاده از قیدها در خوشهبندی

مزایا

افزایش میانگین دقت خوشهبندی [Wagstaff00]

تولید خوشههایی به شکل دلخواه [Wagstaff01b]

مشکلات

شدنی بودن (Feasibility)

مفید نبودن هر مجموعه ای از قیدها [Wagstaff06]

چالش‌های موجود در خوشهبندی مقید

با وجود الگویتم های بسیار در خوشه بندی مقید چالشهایی در این حوزه وجود دارد که نیازمند تحقیق گسترده می باشد.

چالش‌های موجود در خوشهبندی مقید

مجموعه قیدهای متفاوت سودمندی متفاوتی برای الگوریتم‌های خوشهبندی دارند

قیدهایی که الگوریتم خوشهبندی به خودی خود قادر به استخراج آن از دادهها باشد، تاثیر چندانی بر بهبود دقت خوشهبندی نخواهد داشت

تعیین سودمندی یک مجموعه قید قبل از خوشهبندی

به الگوریتم خوشهبندی این قابلیت را می‌دهد که تصمیم بگیرد که آیا از یک مجموعه قید در راستای خوشهبندی استفاده نماید یا خیر.

انتخاب بهترین مجموعه قید ممکن.

از 1000 بار انتخاب تصادفی مجموعه قیدهای 25 تایی، درصد مواردی که سبب کاهش دقت خوشهبندی در چند الگوریتم شده است. (جدول از [Davidson06])

چالش‌های موجود در خوشهبندی مقید

در یک مجموعه داده با n نمونه، n(n-1)/2  قید کاندید برای انتخاب وجود دارد.

انتخاب λ بهترین قید چگونه است؟

به گونه ای چالش اول را در خود دارد.

رفع این چالش با معرفی معیارهای کارامد برای تعیین سودمندی یک مجموعه قید، سبب کاهش هزینه گردآوری قیدها میگردد.

روشها

انتخاب قیدها از میان L داده  (L<n) است که در آن هزینه گردآوری قیدها، فقط شامل برچسب‌گذاری L داده می‌باشد.

پیمایش دورترین-اولین [Basu04]

انتخاب فعال قیدها به کمک تشخیص نقاط مرزی  [Xu05]

چالش‌های موجود در خوشهبندی مقید

تمامی روش‌های خوشه بندی مقید بر این فرض استوارند که انتشار محلی اطلاعات قیدها به همسایهها ایمن بوده و می‌تواند سبب بهبود نتیجه خوشهبندی گردد.

مسائل مهم:

تشخیص ایمن بودن انتشار قید بر روی یک مجموعه داده خاص

درجه انتشار قید به همسایهها (تعیین شعاع همسایگی بهینه و …

خوشهبندی مقید با رویکرد انتخاب فعال قیدها

مساله: خوشهبندی مقید با رویکرد انتخاب فعال قیدها

نگاه تکرارشونده به حل مساله

30 تا 70 درصد پروژه | پاورپوینت | سمینار | طرح های کارآفرینی و  توجیهی |  پایان-نامه |  پی دی اف  مقاله ( کتاب ) | نقشه | پلان طراحی |  های آماده به صورت رایگان میباشد ( word | pdf | docx | doc )