الگوریتم‌ خوشه‌بندی 6

الگوریتم Hierarchical

الگوریتم‌های خوشه‌بندی سلسله مراتبی (Hierarchical) در 2 دسته: از بالا به پایین یا پایین به بالا قرار می‌گیرند. الگوریتم‌های پایین به بالا هر نقطه داده را در ابتدا به عنوان یک خوشه واحد در نظر می‌گیرند و سپس به طور پی در پی جفت خوشه‌ها را ادغام می‌کنند (یا جمع می شوند) تا زمانی که همه خوشه‌ها در یک خوشه واحد ادغام می‌شوند که شامل تمام نقاط داده است.   از این رو خوشه‌بندی سلسله مراتبی از پایین به بالا خوشه جمع بندی سلسله مراتبی یا HAC گفته می شود. این خوشه‌های سلسله مراتبی به عنوان یک درخت یا dendrogram نشان داده می‌شود. ریشه درخت یک خوشه منحصر به فرد است که همه نمونه‌ها را جمع می‌کند برگ‌های خوشه فقط یک نمونه هستند. قبل از رفتن به مراحل الگوریتم تصویر زیر را بررسی کنید.

۱- ما با پردازش هر نقطه داده به عنوان یک خوشه واحد شروع می‌کنیم یعنی اگر X داده در مجموعه داده ما وجود داشته باشد  X خوشه داریم. سپس یک معیار فاصله را انتخاب می‌کنیم که فاصله بین دو خوشه را اندازه می‌گیرد. به عنوان مثال ما فاصله بین دو خوشه را میانگین فاصله بین نقاط داده در خوشه اول و نقاط داده در خوشه دوم تعریف می‌کنیم.

۲- در هر تکرار دو خوشه را با هم ترکیب می‌کنیم. دو خوشه‌ای که باید ترکیب شوند خوشه‌هایی با کمترین فاصله هستند. و بنابراین بیشترین شباهت را دارند و باید با هم ترکیب شوند.

۳- مرحله ۲ را تکرار می‌کنیم تا زمانی که به ریشه درخت برسیم یعنی فقط یک خوشه داریم که شامل تمام نقاط داده است. به این ترتیب می‌توانیم انتخاب کنیم که در پایان چه تعداد خوشه می‌خواهیم به سادگی با انتخاب زمان متوقف کردن ترکیب خوشه‌ها

خوشه‌بندی سلسله مراتبی نیازی به تعیین تعداد خوشه ندارد و حتی می‌توانیم بعد از ساختن درخت تعیین کنیم تعداد خوشه‌ها چقدر باشد مناسب‌تر است. علاوه بر این الگوریتم به انتخاب اندازه فاصله حساس نیست. در حالی که در الگوریتم‌های دیگر خوشه‌بندی  انتخاب اندازه فاصله بسیار مهم است. یک مورد استفاده از روش‌های خوشه‌بندی سلسله مراتبی این است که داده‌ها دارای ساختار سلسله مراتبی هستند و می‌خواهید سلسله مراتب را بازیابی کنید. دیگر الگوریتم‌های خوشه‌بندی نمی‌توانند این کار را انجام دهند. این مزایای خوشه‌بندی سلسله مراتبی بهای کمتری دارد زیرا برخلاف پیچیدگی خطی K-Means و GMM دارای پیچیدگی زمانی O (n³)  است.