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

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

1- خوشه‌بندی سلسله مراتبی (Hierarchical) و مسطح (Flat)

2- خوشه‌بندی انحصاری (Exclusive or Hard Clustering) و خوشه‌بندی با هم‌پوشی (Overlapping or Soft Clustering)

خوشه بندی به روش سلسله مراتبی:در این روش داده های موجود براساس معیار شباهت در گروه یا دسته­هایی قرار می­گیرند.در روش خوشه بندی سلسله مراتبی، بعد از اتمام کار، یعنی مشخص شدن خوشه ها، بر اساس میزان عمومیت آنها ساختاری سلسله‌ مراتبی( معمولا به صورت ساختار درختی )به خوشه ها نسبت داده می‌شود. به این درخت سلسله مراتبی دندوگرام (dendogram) می‌گویند.

در الگوریتمهای سلسله مراتبی بر خلاف الگوریتم های partitional که خوشه بندی در یک مرحله انجام می شود و داده ها در یک state به یک خوشه تبدیل می شوند، داده ها  به تدریج شکسته می شوند یا از پایین به بالا ترکیب می شوند.

 روش کار تکنیکهای خوشه‌بندی سلسله‌مراتبی معمولا بر اساس الگوریتمهای حریصانه  (Greedy Algorithms)  و بهینگی مرحله‌ای (stepwise-optimal) است.

 روشهای خوشه‌بندی بر اساس ساختار سلسله مراتبی تولیدی توسط آنها معمولا به دو دستة زیر تقسیم می‌شوند:

•   بالا به پایین (Top-Down) یا تقسیم کننده(Divisive)

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

•    پایین به بالا (Bottom-Up) یا متراکم شونده-تجمیعی (Agglomerative)

در این روش ابتدا هر داده ‌به عنوان خوشه‌ای مجزا در نظر گرفته می‌شود، در طی فرایندی تکراری در هر مرحله خوشه‌هایی که شباهت بیشتری با یکدیگر دارند باهم ترکیب می‌شوند تا در نهایت یک خوشه و یا تعداد مشخصی خوشه حاصل شود. از انواع الگوریتمهای خوشه‌بندی سلسله مراتبی متراکم شونده رایج می‌توان از الگوریتمهای Single-Linkage،  Average-Linkage  وComplete-Linkage نام برد. تفاوت اصلی در بین تمام این روشها به نحوة محاسبة شباهت بین خوشه‌ها مربوط می‌شود.

شکل زیر فرایند فوق را نشان می دهد

   •خوشه‌بندی انحصاری (or Hard Clustering   Exclusive) و 
   • خوشه‌بندی با هم‌پوشی (Overlapping  or Soft Clustering)

در خوشه‌بندی انحصاری، پس از خوشه‌بندی هر داده دقیقأ به یک خوشه تعلق می‌گیرد مانند روش خوشه‌بندی K-Means. ولی در خوشه‌بندی با همپوشی پس از خوشه‌بندی، هر داده می‌تواند با نسبتهای متفاوتی به چندین خوشه تعلق داشته باشد. نمونه‌ای از آن خوشه‌بندی فازی است