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

دندروگرام خوشه‌بندی سلسله‌مراتبی یگ گونه گیاهی (ساخته شده توسط R)[https://cran.r-project.org/web/packages/dendextend/vignettes/Cluster_Analysis.html منبع

]

در داده کاوی و آمار، خوشه بندی سلسله‌مراتبی (همچنین به نام تحلیل خوشه سلسله‌مراتبی) یک روش خوشه‌بندی می‌باشد که هدف آن ساخت یک سلسله مراتب از خوشه‌ها می‌باشد. روش‌های خوشه‌بندی سلسله‌مراتبی به دو دسته تقسیم می‌شوند:

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

هر سطح از سلسله‌مراتب یک دسته‌بندی از داده‌ها را نمایش می‌دهد که می‌توان به آن به شکل یک درخت نگاه کرد. هر کدام از برگ‌های درخت نشان دهنده یک مشاهده اولیه می‌باشند و ریشه درخت مجموعهٔ تمام مشاهدات است. نتایج یک خوشه‌بندی سلسله‌مراتبی عموماً به شکل یک دندروگرام نمایش داده می‌شوند.

میزان تفاوت بین خوشه‌ها

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

متریک

انتخاب یک متریک مناسب شکل خوشه‌ها را تحت تأثیر قرار می‌دهد، زیرا به ازای یک متریک چند مشاهده می‌توانند به یکدیگر نزدیک باشند ولی به ازای متریک دیگری فاصلهٔ آن‌ها از هم افزایش یابد. به عنوان مثال در یک فضای دو بعدی فاصلهٔ بین نقاط (۰و۰) و (۱و۰) بنابر روش‌های معمول یک می‌باشد، اما فاصلهٔ بین دو نقطه (۰و۰) و (۱و۱) با در نظر گرفتن فاصله منهتن ۲ می‌باشد، با در نظر گرفتن فاصله اقلیدسی رادیکال ۲ می‌باشد، و با در نظر گرفتن فاصله بیشینه ۱ می‌باشد.

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

نام	فرمول
فاصله اقلیدسی	$\|a-b\|_{2}={\sqrt {\sum _{i}(a_{i}-b_{i})^{2}}}$
مجذور فاصله اقلیدسی	$\|a-b\|_{2}^{2}=\sum _{i}(a_{i}-b_{i})^{2}$
فاصله منهتن	$\|a-b\|_{1}=\sum _{i}|a_{i}-b_{i}|$
فاصله بیشینه	$\|a-b\|_{\infty }=\max _{i}|a_{i}-b_{i}|$
فاصله ماهانولوبیس	${\sqrt {(a-b)^{\top }S^{-1}(a-b)}}$ که در آن $S$ ماتریس کوواریانس می‌باشد.

برای متون و سایر داده‌های غیر عددی، متریک‌هایی مانند فاصله همینگ یا فاصله لون‌اشتاین استفاده می‌شوند.

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

معیار پیوند

معیار پیوند فاصلهٔ بین دو مجموعه مشاهده را توسط تابعی از فاصله دو به دو بین مشاهدات هر مجموعه تعریف می‌کند.

بعضی از معیارهای پیوند رایج بین دو مجموعه مشاهده A و B:

نام	فرمول
بیشینه فاصله	$\max \,\{\,d(a,b):a\in A,\,b\in B\,\}.$
کمینه فاصله یا خوشه‌بندی تک‌پیوندی	$\min \,\{\,d(a,b):a\in A,\,b\in B\,\}.$
میانگین فاصله یا روش جفت گروه بدون وزن با میانگین حسابی	${\frac {1}{|A||B|}}\sum _{a\in A}\sum _{b\in B}d(a,b).$
فاصله مرکزوار یا UPGMC	$\|c_{s}-c_{t}\|$ که در آن $c_{s}$ و $c_{t}$ به ترتیب مرکزوارهای خوشه‌های s و t می‌باشند.
کمترین انرژی	${\frac {2}{nm}}\sum _{i,j=1}^{n,m}\|a_{i}-b_{j}\|_{2}-{\frac {1}{n^{2}}}\sum _{i,j=1}^{n}\|a_{i}-a_{j}\|_{2}-{\frac {1}{m^{2}}}\sum _{i,j=1}^{m}\|b_{i}-b_{j}\|_{2}$

که در آن‌ها d متریک است.

خوشه‌بندی تجمعی

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

مثال

داده‌های زیر را با متریک فاصلهٔ اقلیدسی و معیار پیوند میانگین خوشه‌بندی می‌کنیم.

داده‌های خام در یک صفحه دوبعدی

به ازای داده‌های زیر درخت سلسله‌مراتبی نیز به شکل زیر می‌باشد.

سلسله‌مراتب محاسبه شده بر اساس داده‌ها

نحوهٔ خوشه‌بندی

1. {b} و {c} با یکدیگر تجمیع می‌شوند
2. {d} و {e} با یکدیگر تجمیع می‌شوند
3. {f} با مجموعه {d,e} تجمیع می‌شود
4. مجموعه {d,e،f} و {b,c} با یکدیگر تجمیع می‌شوند
5. مجموعه {b,c،d,e،f} و {a} با یکدیگر تجمیع می‌شوند

خوشه‌بندی تجزیه‌ای

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

جستارهای وابسته

• شاخه‌بندی
• خوشه‌بندی
• فیلوژنتیک محاسباتی
• دندروگرام
• جستجوی نزدیک‌ترین همسایه

برای مطالعهٔ بیشتر

• Kaufman, L.; Rousseeuw, P.J. (1990). Finding Groups in Data: An Introduction to Cluster Analysis (1 ed.). New York: John Wiley. ISBN 0-471-87876-6.
• Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). "14.3.12 Hierarchical clustering". The Elements of Statistical Learning (2nd ed.). New York: Springer. pp. 520–528. ISBN 0-387-84857-6. Archived from the original (PDF) on 10 November 2009. Retrieved 2009-10-20.