Skip to content
بازگشت به نتایج جست‌وجو

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

معرفی‌شده توسط
Ward, J. H.
سال
1963
نوع
Unsupervised clustering (agglomerative)

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

خوشه‌بندی سلسله‌مراتبی یک روش نظارت‌نشده است که مشاهدات را در خوشه‌های تودرتو گروه‌بندی می‌کند و نتیجه را به صورت یک درخت‌نگاره (دندروگرام) ترسیم می‌کند، بنابراین نیازی به تعیین تعداد خوشه‌ها از پیش نیست. شکل تجمعی آن بر اساس معیار تابع هدف گروه‌بندی است که توسط جو وارد در سال ۱۹۶۳ معرفی شد.

شهود پشت روش

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

تاریخ

شکل تجمعی خوشه‌بندی سلسله‌مراتبی توسط جو اچ. وارد در سال ۱۹۶۳ بر پایه‌ی رسمی قرار گرفت، که ادغام خوشه‌ها را بهینه‌سازی یک تابع هدف قاب‌بندی کرد — به حداقل رساندن افزایش واریانس درون‌گروهی در هر ادغام. پیوند وارد یکی از معیارهای پرکاربردترین باقی مانده است و درخت‌نگاره‌ای که تولید می‌کند یک ابزار اکتشافی استاندارد در علوم اجتماعی، بهداشت و کسب‌وکار است.

چه زمانی استفاده شود

هنگامی که می‌خواهید ساختار را بدون تعیین تعداد خوشه‌ها از پیش کشف کنید، برای گروه‌بندی اکتشافی از آن استفاده کنید، بر روی ویژگی‌های پیوسته، ترتیبی یا دسته‌ای با حداقل حدود ۱۰ مشاهده. این روش فرضیات کمی دارد اما به دو انتخاب وابسته است: یک معیار فاصله مناسب و یک روش پیوند مناسب. در کمتر از حدود ۱۰ مشاهده، ماتریس فاصله قابل اعتماد نیست و درخت‌نگاره نمی‌تواند ساختار معناداری را نشان دهد، بنابراین K-means یک جایگزین امن‌تر است؛ در نمونه‌های بسیار کوچک، نتایج بیش از حد به روش پیوند حساس می‌شوند و عضویت خوشه‌ها ناپایدار است.

محدودیت‌ها و ملاحظات

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

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

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

کاربردها

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

چگونه کار می‌کند

چگونه کار می‌کند

1

ابتدا با استفاده از یک معیار فاصله انتخاب‌شده، فاصله‌ی بین هر جفت مشاهده محاسبه می‌شود و یک ماتریس فاصله تولید می‌گردد. انتخاب معیار مهم است: این معیار تعیین می‌کند چه چیزی «مشابه» تلقی می‌شود، و ویژگی‌های پیوسته، ترتیبی و دسته‌ای ممکن است به تعاریف متفاوتی از فاصله نیاز داشته باشند.

2

با شروع از اینکه هر مشاهده به تنهایی یک خوشه است، الگوریتم به طور مکرر دو خوشه‌ای را که بر اساس روش پیوند انتخاب‌شده نزدیک‌تر هستند، ادغام می‌کند. به عنوان مثال، معیار وارد، جفتی را ادغام می‌کند که کمترین افزایش در مجموع مربعات درون‌خوشه‌ای را ایجاد می‌کند و خوشه‌های حاصل را تا حد امکان فشرده نگه می‌دارد. انتخاب پیوند به شدت بر گروه‌بندی نهایی تأثیر می‌گذارد.

فرمول
\Delta(A,B) = \sum_{i \in A \cup B} \lVert x_i - m_{A \cup B}\rVert^2 - \sum_{i \in A}\lVert x_i - m_A\rVert^2 - \sum_{i \in B}\lVert x_i - m_B\rVert^2
3

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

دام‌های رایج

  • اجرای آن بر روی کمتر از حدود ۱۰ مشاهده، که در آن ماتریس فاصله و درخت‌نگاره قابل اعتماد نیستند.
  • انتخاب یک معیار فاصله و روش پیوند بدون توجیه و در نظر گرفتن نتیجه به عنوان قطعی.
  • اعتماد به عضویت‌های ناپایدار خوشه در یک نمونه کوچک به جای تغییر به K-means یا یک مخلوط گوسی.
  • اجبار به یک تعداد ثابت خوشه قبل از بررسی نقاط برش طبیعی درخت‌نگاره.

پرسش‌های متداول

آیا باید ابتدا تعداد خوشه‌ها را انتخاب کنم؟

خیر. خوشه‌بندی سلسله‌مراتبی درخت ادغام کامل را به هر حال می‌سازد و شما تعداد خوشه‌ها را بعداً با بریدن درخت‌نگاره در ارتفاع انتخاب‌شده تعیین می‌کنید — این یکی از مزایای اصلی آن نسبت به روش‌هایی مانند K-means است.

از کدام معیار فاصله و پیوند باید استفاده کنم؟

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

به چند مشاهده نیاز دارم؟

حداقل حدود ۱۰. کمتر از آن، ماتریس فاصله قابل اعتماد نیست و درخت‌نگاره نمی‌تواند ساختار معناداری را آشکار کند، بنابراین K-means جایگزین امن‌تری است.

چرا خوشه‌های من ناپایدار هستند؟

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

روش‌های مرتبط

منابع

  1. Ward, J. H. (1963). Hierarchical Grouping to Optimize an Objective Function. Journal of the American Statistical Association, 58(301), 236–244.

    باز کردن مرجع DOI
    کپی شد.