خوشه‌بندی

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

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

مسئلهٔ خوشه‌بندی به دو شکل می‌تواند مطرح شود: (۱) یک ماتریس بی‌شباهتی داده می‌شود یا (۲) یک ماتریس که هر سطر آن یک شیء را توصیف می‌کند. خروجی الگوریتم می‌تواند به دو صورت باشد: (۱) گروه‌بندی اشیا به مجموعه‌های مجزا یا (۲) خوشه‌بندی سلسله مراتبی که یک درخت برای تقسیم‌بندی اشیا پیدا می‌کند. الگوریتم‌های نوع اول سریعتر هستند با زمان در مقابل زمان برای خوشه‌بندی سلسله‌مراتبی. از الگوریتم‌های مشهور برای خوشه‌بندی می‌توان به 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-ارزیابی جهت‌دار بودن خوشه‌ها

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

آماره هاپکینز شاخصی در آمار است که تصادفی بودن مقدار متغیرها را می‌آزماید. این سنجش بر اساس یک آزمون فرض است که به صورت زیر تعریف شده است:

  • فرض صفر: داده‌ها به صورت یکنواخت توزیع شده‌اند و هیچ خوشه معنی‌داری در آنها وجود ندارد.
  • فرض یک: داده‌ها به صورت یکنواخت توزیع نشده‌اند و در آنها خوشه معنی‌دار مشاهده می‌شود.

این آزمون را می‌توان با تکرارهای مختلف انجام داد. در صورتی که آماره آزمون بزرگتر از 0.5 باشد می‌توانیم فرض یک را رد کنیم و بپذیریم که داده‌ها به صورت یکنواخت توزیع شده‌اند.

2-ارزیابی تعداد خوشه‌ها

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

3-ارزیابی کیفیت خوشه‌ها

کیفیت خوشه‌ها در روشهای یادگیری بدون نظارت از طریق روشهای ارزیابی درونی انجام می‌شود. این روشها ارزیابی می‌کنند که خوشه‌ها تا چه حد از هم جدا هستند و تا چه حد به هم فشرده‌اند. نمونه‌ای از این شاخص‌ها شاخص سیلوئت می‌باشد که به شکل زیر تعریف می‌شود:

a)o) به صورت میانگین فاصله بین o و سایر اشیاء خوشه‌ای که o به آن تعلق دارد، تعریف می‌شود. به روش مشابهی b)o) کمترین میانگین فاصله بین o و همه خوشه‌هایی است که o به آنها تعلق ندارد.

مقدار این شاخص بین 1- و 1 است. مقدار a)o) فشردگی خوشه‌ای را که o به آن تعلق دارد نشان می‌دهد. این مقدار هر چه کمتر باشد خوشه فشرده‌تر است. مقدار b)o) نشان می‌دهد که o چه‌قدر از سایر خوشه‌ها جدا است. هر چه b)o) بیشتر باشد o از سایر خوشه‌ها بیشتر جدا شده است. بنابراین در شاخص سیلوئت هر چه مقدار شاخص به یک نزدیک می‌شود خوشه فشرده‌تر است و از سایر خوشه‌ها دورتر است بنابراین حالت مطلوبی است. در شرایطی که شاخص سیلوئت منفی باشد، به این معناست که o به اشیاء خوشه دیگری غیر از خوشه‌ای که به آن تعلق دارد، نزدیکتر است. این حالت نا مطلوب است و باید از بروز آن جلوگیری کرد.

جستارهای وابسته[ویرایش]

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

  1. Murphy, Kevin. Machine learning a probabilistic perspective. MIT Press, 2012. 875. ISBN ‎0262018020. 
  2. Han, J., Kamber, M., & Pei, J. (2011). Data mining : concepts and techniques (3rd ed.). Morgan Kaufmann Publishers