خوشه‌بندی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
در خوشه‌بندی، هدف تقسیم داده به گروه‌های مختلف است که با رنگ‌های مختلف در اینجا نشان داده شده‌اند.

در آمار و یادگیری ماشینی، خوشه‌بندی یا آنالیز خوشه به فرایند گروه‌بندی اشیاء مشابه یکدیگر با هم است. مسئلهٔ خوشه‌بندی به دو شکل می‌تواند مطرح شود: (۱) یک ماتریس n\times n بی‌شباهتی داده می‌شود یا (۲) یک ماتریس n\times d که هر سطر آن یک شیء را توصیف می‌کند. خروجی الگوریتم می‌تواند به دو صورت باشد: (۱) گروه‌بندی اشیا به مجموعه‌های مجزا یا (۲) خوشه‌بندی سلسله مراتبی که یک درخت برای تقسیم‌بندی اشیا پیدا می‌کند. الگوریتم‌های نوع اول سریعتر هستند با زمان \mathcal{O}(nd) در مقابل زمان \mathcal{O}(n^2\log(n)) برای خوشه‌بندی سلسله‌مراتبی. از الگوریتم‌های مشهور برای خوشه‌بندی می‌توان به k-means اشاره کرد.[۱]

نگارخانه[ویرایش]

برخی از روش های خوشه بندی[ویرایش]

: hierarchical clustering

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

single linkage -1

این روش که به روش Bottom-Up و Agglomerative نیز معروف است روشی است که در آن ابتدا هر داده به عنوان یک خوشه در نظر گرفته می شود.در ادامه با به کار گیری یک الگوریتم هر بار خوشه های دارای ویژگی های نزدیک به هم با یکدیگر ادغام شده و این کار ادامه می یابد تا به چند خوشه ی مجزا برسیم. مشکال این روش حساس بودن به نویز و مصرف زیاد حافظه می باشد.

complete linkage -2

در این روش که به روش Top-Down و Divisive نیز معروف است ابتدا تمام داده ها به عنوان یک خوشه در نظر گرفته شده و با به کار گیری یک الگوریتم تکرار شونده هربار داده ای که کمترین شباهت را با داده های دیگر دارد به خوشه های مجزا تقسیم می شود.این کار ادامه می یابد تا یک یا چند خوشه یک عضوی ایجاد شود. مشکل نویز در این روش برطرف شده است.

: k-means clustering

روش میانگین k در عین سادگی یک روش بسیار کاربردی و پایه چند روش دیگر مثل خوشه بندی فازی و Segment-wise distributional clustering Algorithm میباشد. روش کار به این صورت است که ابتدا به تعداد دلخواه نقاطی به عنوان مرکز خوشه در نظر گرفته می شود.سپس با بررسی هر داده ، آن را به نزدیک ترین مرکز خوشه نسبت می دهیم.پس از اتمام این کار با گرفتن میانگین در هر خوشه می توانیم مراکز خوشه و به دنبال آن خوشه های جدید ایجاد کنیم.(با تکرار مراحل قبل) از جمله مشکلات این روش این است که بهینگی آن وابسته به انتخاب اولیه مراکز بوده و بنابراین بهینه نیست.مشکلات دیگر آن تعیین تعداد خوشه ها و صفر شدن خوشه ها می باشد.

: Density-based clustering

در این تکنیک این اصل مطرح می شود که خوشه ها مناطقی با چگالی بیشتر هستند که توسط مناطق با چگالی کمتر از هم جدا شده اند. یکی از مهم ترین الگوریتم ها در این زمینه الگوریتم DBSCAN است. روش این الگوریتم به این صورت است که هر داده متعلق به یک خوشه در دسترس چگالی سایر داده های همان خوشه است ، ولی در دسترسی چگالی سایر داده های خوشه های دیگر نیست. (چگالی داده همسایگی به مرکز داده و شعاع همسایگی دلخواه ε است) مزیت این روش این است که تعداد خوشه ها به صورت خودکار مشخص می شود . در تشخیص نویز نیز بسیار کاراست.


منابع[ویرایش]

  1. Murphy, Kevin. Machine learning a probabilistic perspective. MIT Press, 2012. 875. ISBN ‎0262018020.