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

R)
در داده کاوی و آما ر، خوشه بندی سلسله‌مراتبی (همچنین به نام تحلیل خوشه سلسله‌مراتبی ) یک روش خوشه‌بندی می‌باشد که هدف آن ساخت یک سلسله مراتب از خوشه‌ها می‌باشد. روش‌های خوشه‌بندی سلسله‌مراتبی به دو دسته تقسیم می‌شوند:
تجمعی : رویکرد این دسته «پایین به بالا» می‌باشد: با شروع از پایین، در هر مرحله دو خوشه با یکدیگر تجمیع شده و یک خوشه جدید تشکیل می‌دهند. خوشه‌های جدید در سطح‌های بالاتر قرار گرفته و این روند تکرار می‌شود.
تجزیه‌ای : رویکرد این دسته «بالا به پایین» می‌باشد: با شروع از بالا، در هر مرحله یک خوشه به خوشه‌های کوچکتری تجزیه می‌شود که در سطح پایین‌تر قرار می‌گیرند.
هر سطح از سلسله‌مراتب یک دسته‌بندی از داده‌ها را نمایش می‌دهد که می‌توان به آن به شکل یک درخت نگاه کرد. هر کدام از برگ‌های درخت نشان دهنده یک مشاهده اولیه می‌باشند و ریشه درخت مجموعه‌ی تمام مشاهدات است. نتایج یک خوشه‌بندی سلسله‌مراتبی عموما به شکل یک دندروگرام نمایش داده می‌شوند.
میزان تفاوت بین خوشه‌ها
برای این که بفهمیم کدام خوشه‌ها باید با هم تجمیع بشوند یا از یکدیگر تقسیم بشوند باید معیاری از تفاوت بین خوشه‌ها تعریف شود. در اکثر روش‌ها، این معیار به کمک تعریف یک متریک و یک معیار پیوند حاصل می‌شود. متریک فاصله‌ی بین دو تک مشاهده را تعیین کرده و معیار پیوند فاصله‌ی بین دو مجموعه مشاهده را توسط تابعی از فاصله دو به دو بین مشاهدات هر مجموعه تعریف می‌کند.
متریک
انتخاب یک متریک مناسب شکل خوشه‌ها را تحت تاثیر قرار می‌دهد، زیرا به ازای یک متریک چند مشاهده می‌توانند به یکدیگر نزدیک باشند ولی به ازای متریک دیگری فاصله‌ی آن‌ها از هم افزایش یابد. به عنوان مثال در یک فضای دو بعدی فاصله‌ی بین نقاط (۰و۰) و (۱و۰) بنابر روش‌های معمول یک می‌باشد، اما فاصله‌ی بین دو نقطه (۰و۰) و (۱و۱) با در نظر گرفتن فاصله منهتن ۲ می‌باشد، با در نظر گرفتن فاصله اقلیدسی رادیکال ۲ می‌باشد، و با در نظر گرفتن فاصله بیشینه ۱ می‌باشد.
بعضی از متریک‌های رایج برای استفاده در خوشه‌بندی سلسله‌مراتبی:
نام
فرمول
فاصله اقلیدسی
مجذور فاصله اقلیدسی
فاصله منهتن
فاصله بیشینه
فاصله ماهانولوبیس
که در آن ماتریس کوواریانس می‌باشد
برای متون و سایر داده‌های غیر عددی، متریک‌هایی مانند فاصله همینگ یا فاصله لون‌اشتاین استفاده می‌شوند.
یک مرور در خوشه‌بندی‌های استفاده شده در تحقیقات سلامت روان نشان می‌دهد که بیشترین معیار فاصله استفاده شده در مطالعات منتشر شده در آن حوزه از فاصله اقلیدسی یا مجذور آن استفاده می‌کند.
معیار پیوند
معیار پیوند فاصله‌ی بین دو مجموعه مشاهده را توسط تابعی از فاصله دو به دو بین مشاهدات هر مجموعه تعریف می‌کند.
بعضی از معیارهای پیوند رایج بین دو مجموعه مشاهده A و B:
نام
فرمول
بیشینه فاصله
کمینه فاصله
میانگین فاصله یا روش جفت گروه بدون وزن با میانگین حسابی
فاصله مرکزوار یا UPGMC
که در آن و به ترتیب مرکزوارهای خوشه‌های s و t می‌باشند.
کمترین انرژی
که در آن‌ها d متریک است.
خوشه‌بندی تجمعی
خوشه‌بندی تجمعی با یک خوشه به ازای هر مشاهده شروع شده و در هر مرحله، دو خوشه که کمترین تفاوت را با یکدیگر دارند تجمیع شده و یک خوشه بزرگتر را تشکیل می‌دهند. این کار باعث می‌شود تا در سطح بالاتر یک خوشه کمتر وجود داشته باشد و تا زمانی که تعداد خوشه‌ها به یک برسد این کار ادامه پیدا می‌کند.
مثال
داده‌های زیر را با متریک فاصله‌ی اقلیدسی و معیار پیوند میانگین خوشه‌بندی می‌کنیم.
داده‌های خام در یک صفحه دوبعدی
به ازای داده‌های زیر درخت سلسله‌مراتبی نیز به شکل زیر می‌باشد.
سلسله‌مراتب محاسبه شده بر اساس داده‌ها
نحوه خوشه‌بندی:
{b و {c با یکدیگر تجمیع می‌شوند
{d و {e با یکدیگر تجمیع می‌شوند
{f با مجموعه {d,e تجمیع می‌شود
مجموعه {d,e،f و {b,c با یکدیگر تجمیع می‌شوند
مجموعه {b,c،d,e،f و {a با یکدیگر تجمیع می‌شوند
خوشه‌بندی تجزیه‌ای
خوشه‌بندی تجزیه‌ای با یک خوشه که شامل تمامی مشاهدات می‌باشد شروع شده و سپس به طور بازگشتی یکی از خوشه‌های موجود را به خوشه‌های کوچکتری تقسیم می‌کند. یکی از برتری‌های این روش نسبت به خوشه‌بندی تجمعی برای مواردی است که بخواهیم داده‌ها را به تعداد کمی خوشه تجزیه کنیم. برای تجزیه هر خوشه می‌توان از الگوریتم‌های متفاوتی مانند K-Means یا K-Medoids با K=2 استفاده کرد. به طور کلی هر الگوریتم خوشه‌بندی که حداقل دو خوشه خروجی تولید می‌کند در خوشه‌بندی تجزیه‌ای قابل استفاده است.
شاخه‌بندی
خوشه‌بندی
فیلوژنتیک محاسباتی
دندروگرام
جستجوی نزدیک‌ترین همسایه