الگوریتم خوشه بندی مبتنی بر چگالی (غلظت)

روش‌های مبتنی بر چگالی (density-based methods)

خوشه‌ها مناطقی با چگالی بیشتر هستند (نقاط داده متراکم‌تر) که با نواحی دارای چگالی کم‌تر (تراکم داده کم) از هم جدا شده‌اند. در این روش‌ها، نقاطی که در یک محدوده معین (یک شعاع همسایگی خاص) از هم قرار دارند در یک خوشه قرار می‌گیرند. در روش‌های مبتنی بر چگالی، معمولا یک حداقل چگالی در نظر گرفته می‌شود و در نواحی که این حداقل رعایت شده، خوشه‌بندی انجام می‌شود. این روش‌ها ذاتا برای فضای پیوسته تعریف شده‌اند، بنابراین استفاده از آن‌ها با انواع داده دلخواه، برای مثال سری‌های زمانی، بدون بهره‌گیری از تبدیل‌های خاص کار دشواری خواهد بود.

خوشه‌بندی ارجاع به کار شناسایی گروه‌ها یا خوشه‌ها در یک دیتاست داده می‌شود. در خوشه بندی مبتنی بر
چگالی (غلظت) ، یک خوشه‌، مجموعه‌ای از اشیای داده‌ای است که این اشیا در فضای داده در یک منطقه پیوسته‌ای با غلظت بالا از اشیا پخش شده‌اند. خوشه‌های مبتنی بر غلظت از یک دیگر به وسیله مناطق کم غلظت اشیا جدا هستند. اشیای داده در مناطق کم غلظت معمولا پر نویز یا پرت ملاحظه می‌شوند.

where the sum of (squared) pairwise dissimilarities between all cluster objects or the sum of (squared) dissimilarities of all cluster objects with respect to (w.r.t.) some cluster representative (e.g., the mean value) are minimized and the respective values between different clusters are maximized, given some dissimilarity function dis

ین فرضیه‌ها معمولا نتیجه در خوشه‌های کوژ یا شکلی دارند.

از نقطه نظر آمار چنین روش‌هایی همگام با رهیافت پارامتریکی است که که غلظت ناشناخته p(x) از داده به مخلوطی از کا غلظت p(x فرض می‌شود که هر یک با یک گروه از کا گروه در این داده همگام است. …

The pi(x) are assumed to belong to some parametric family (e.g., Gaussian distributions) with unknown parameters.

این پارامترها سپس بر نمونه معین (دیتاست) تخمین زده می‌شوند.

در مقابل خوشه‌بندی مبتنی بر غلظت رهیافت غیر پارامتریک است که خوشه‌ها در آن به عنوان نواحی پر غلظت از (p(x در نظر گرفته می‌شوند.

روش‌های مبتنی بر چگالی (غلظت) نیاز به تعداد خوشه‌ها به عنوان پارامترهای ورودی ندارد. خوشه‌بندی مبتنی بر چگالی نیازی به تعداد خوشه‌ها به عنوان پارامترهای وردی ندارد، و همین‌طور فرض‌های مرتبط با غلظت p(x) یا واریانسی که ممکن است در این خوش‌ها در دیتاست وجود داشته باشد انجام نمی‌دهد.

بعضی اوقات خوشه‌بندی مبتنی بر چگالی (غلظت) به خوشه‌های طبیعی ارجاع داده می‌شود چون آنها مخصوصا برای برنامه‌های نشات گرفته از طبیعت مناسب هستند. برای مثال در داده خاص، خوشه‌های نقاط در این فضا ممکن است همراه با ساختارهای طبیعی چون رودخانه‌ها، جاده‌ها، گسل‌های زلزله و … باشد.

اگر چه بعدها ضریب‌های کاراتری معرفی شد، خوشه‌بندی تک لینکه به دلیل تاثیر زنجیره نقد شده بود. این تاثیر می‌توانست منجر به روابط ناخواسته خوشه‌های متفاوت به وسیله وجود زنجیره‌ای از اشیای فردی میان دو خوشه باشد. بعدها ویچارت روشی برای حذف داده‌های نویز قبل از خوشه‌بندی به روش تک لینکه ارائه داد، این روش احتمالا اولین روش محاسباتی مبتنی بر چگالی (غلظت) بود. الگوریتم او برای تحلیل حالت سطح یک شامل شش مرحله بود:

۱: انتخاب آستانه فاصله، آستانه فرکانس، آر و کا

۲: محاسبه شباهت مثلی همه نقاط

۳: ارزیابی فرکانس کای آی، این فرکانس تعداد نقاط قرار گرفته شده در فاصله آر از نقطه ایکس آی را نشان می‌دهد، از این رو این یک سنجه غلظت است.

۴:‌ حذف همه نویزها یعنی نقاط بدون غلظت جایی که کای آی کوچکتر از کا است.

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

۶: سرانجام، نقاط نویز بر اساس معیارهایی می‌توانند به یک خوشه‌ مناسب اختصاص داده شوند.

1340 بازدید