گیاهی ترین گیاهی ترین AnzanDigital فروشگاه

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

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

 

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

در روش خوشه بندی سلسله مراتبی، به خوشه‌های نهایی بر اساس میزان عمومیت آنها  ساختاری سلسله‌ مراتبی نسبت داده می‌شود. مانند روشSingle Link. ولی در خوشه‌بندی مسطح تمامی خوشه‌های نهایی دارای یک میزان عمومیت هستند مانندK-Means. به ساختار سلسله مراتبی حاصل از روشهای خوشه‌بندی سلسله مراتبی دندوگرام (Dendogram) گفته می‌شود.

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

 

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

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

 

  1. بالا به پایین (Top-Down) یا تقسیم کننده (Divisive): در این روش ابتدا تمام داده‌ها به عنوان یک خوشه در نظر گرفته می‌شوند و سپس در طی یک فرایند تکراری در هر مرحله داده‌هایی شباهت کمتری به هم دارند به خوشه‌های مجزایی شکسته می‌شوند و این روال تا رسیدن به خوشه‌هایی که دارای یک عضو هستند ادامه پیدا می‌کند.

 

  1. پایین به بالا (Bottom-Up) یا متراکم شونده (Agglomerative): در این روش ابتدا هر داده‌ها به عنوان خوشه‌ای مجزا در نظر گرفته می‌شود و در طی فرایندی تکراری در هر مرحله خوشه‌هایی که شباهت بیشتری با یکدیگر با یکدیگر ترکیب می‌شوند تا در نهایت یک خوشه و یا تعداد مشخصی خوشه حاصل شود. از انواع الگوریتمهای خوشه‌بندی سلسله مراتبی متراکم شونده رایج می‌توان از الگوریتمهایSingle-Link، Average-Link و Complete-Link نام برد. تفاوت اصلی در بین تمام این روشها به نحوه محاسبه شباهت بین خوشه‌ها مربوط می‌شود. که در بخشهای بعد به تشریح هر یک پرداخته خواهد شد.

 

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

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

شکل ۳: تفاوت بین روشهای بالا به پایین با روشهای پایین به بالا
ا

 

خوشه‌بندی با روش Single-Link

این روش یکی از قدیمی‌ترین و ساده‌ترین روشهای خوشه‌بندی است و جزء روشهای خوشه‌بندی سلسله مراتبی و انحصاری محسوب می‌شود. به این روش خوشه‌بندی، تکنیک نزدیکترین همسایه (Nearest Neighbour) نیز گفته می‌شود.  در این روش برای محاسبه شباهت بین دو خوشه A و B از معیار زیر استفاده می‌شود:

که i یک نمونه داده متعلق به خوشه A و j یک نمونه داده متعلق به خوشه B می‌باشد. در واقع در این روش شباهت بین دو خوشه، کمترین فاصله بین یک عضو از یکی با یک عضو از دیگری است. در شکل زیر این مفهوم بهتر نشان‌ داده شده است. [۵]

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

شکل ۴:  شباهت بین دو خوشه در روش Single-Link برابر است با کمترین فاصله بین داده‌های دو خوشه

۱-۱-۱-  مثال: در این قسمت سعی شده است تا در مثالی با  فرض داشتن ۶ نمونه داده و ماتریس فاصله بین آنها که در جدول ۱ نشان‌داده شده است، نحوه اعمال روش خوشه‌بندی Single-Link بهتر تشریح شود.

 

جدول ۱: ماتریس فاصله بین ۶ نمونه داده

۱ ۲ ۳ ۴ ۵ ۶
۱ ۰ ۴ ۱۳ ۲۴ ۱۲ ۸
۲ ۰ ۱۰ ۲۲ ۱۱ ۱۰
۳ ۰ ۷ ۳ ۹
۴ ۰ ۶ ۱۸
۵ ۰ ۸٫۵
۶ ۰

 

 

در ابتدا هر داده به عنوان یک خوشه در نظر گرفته می‌شود و یافتن نزدیکترین خوشه در واقع یافتن کمترین فاصله بین داده‌های بالا خواهد بود. با توجه به جدول ۱ مشخص است که داده‌های ۳ و ۵ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می‌شود که فاصله آن از سایر خوشه‌ها برابر است با کمترین فاصله بین ۳ و یا ۵ از سایر خوشه‌ها. نتیجه در جدول ۲ نشان ‌داده شده است.

 

جدول ۲: ماتریس فاصله بین ۵ خوشه حاصل از تکرار اول

۱ ۲ (۳ و ۵) ۴ ۶
۱ ۰ ۴ ۱۲ ۲۴ ۸
۲ ۰ ۱۰ ۲۲ ۱۰
(۳ و ۵) ۰ ۶ ۸٫۵
۴ ۰ ۱۸
۶ ۰

 

با توجه به جدول ۲ مشخص است که داده‌های ۱ و ۲ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می‌شود که فاصله آن از سایر خوشه‌ها برابر است با کمترین فاصله بین ۱ و یا ۲ از سایر خوشه‌ها. نتیجه در جدول ۳ نشان ‌داده شده است.

 

جدول ۳: ماتریس فاصله بین ۴ خوشه حاصل از تکرار دوم

(۱ و ۲) (۳ و ۵) ۴ ۶
(۱ و ۲) ۰ ۱۰ ۲۲ ۸
(۳ و ۵) ۰           ۶       ۸٫۵
۴ ۰ ۱۸
۶ ۰

 

با توجه به جدول ۳ مشخص است که خوشه‌های (۳ و ۵) و ۴ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می‌شود که فاصله آن از سایر خوشه‌ها برابر است با کمترین فاصله بین (۳ و ۵) و یا ۴ از سایر خوشه‌ها. نتیجه در جدول۴ نشان ‌داده شده است.

 

جدول ۴: ماتریس فاصله بین ۳ خوشه حاصل از تکرار سوم

(۱ و ۲) (۳، ۴ و ۵) ۶
(۱ و ۲) ۰ ۱۰ ۸
(۳، ۴ و ۵) ۰ ۸٫۵
۶ ۰

 

با توجه به جدول ۴ مشخص است که خوشه‌های (۱ و ۲) و ۶ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می‌شود که فاصله آن از سایر خوشه‌ها برابر است با کمترین فاصله بین (۱ و ۲) و یا ۶ از سایر خوشه‌ها. نتیجه در جدول۵ نشان ‌داده شده است.

 

جدول ۵: ماتریس فاصله بین ۲ خوشه حاصل از تکرار چهارم

(۱، ۲ و ۶) (۳، ۴ و ۵)
(۱، ۲ و ۶) ۰ ۸٫۵
(۳، ۴ و ۵) ۰

در نهایت این دو خو‌شه حاصل ا هم ترکیب می‌شوند. نتیجه در دندوگرام شکل ۵ نشان داده شده است.

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

شکل ۵: دندوگرام مثال Single-Link

 

خوشه‌بندی با روش Complete-Link

 

این روش همانند Single-Link جزء روشهای خوشه‌بندی سلسله مراتبی و انحصاری محسوب می‌شود. به این روش خوشه‌بندی، تکنیک دورترین همسایه (furthest Neighbour) نیز گفته می‌شود.  در این روش برای محاسبه شباهت بین دو خوشه Aو B از معیار زیر استفاده می‌شود:

(۲)

 

که i یک نمونه داده متعلق به خوشه A و j یک نمونه داده متعلق به خوشه B می‌باشد. در واقع در این روش شباهت بین دو خوشه بیشترین فاصله بین یک عضو از یکی با یک عضو از دیگری است. در شکل زیر این مفهوم بهتر نشان‌ داده شده است. [۵]

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

شکل ۶: شباهت بین دو خوشه در روش Complete-Link برابر است با بیشترین فاصله بین داده‌های دو خوشه.

 

 مثال: در این قسمت سعی شده است تا در مثالی با  فرض داشتن ۶ نمونه داده و ماتریس فاصله بین آنها که در جدول ۶ نشان ‌داده شده است، نحوه اعمال روش خوشه‌بندیComplete-Link بهتر تشریح شود.

 

جدول ۶: ماتریس فاصله بین ۶ نمونه داده

۱ ۲ ۳ ۴ ۵ ۶
۱ ۰ ۴ ۱۳ ۲۴ ۱۲ ۸
۲ ۰ ۱۰ ۲۲ ۱۱ ۱۰
۳ ۰ ۷ ۳ ۹
۴ ۰ ۶ ۱۸
۵ ۰ ۸٫۵
۶ ۰

 

در ابتدا هر داده به عنوان یک خوشه در نظر گرفته می‌شود و یافتن نزدیکترین خوشه در واقع یافتن کمترین فاصله بین داده‌های بالا خواهد بود. با توجه به جدول ۶ مشخص است که داده‌های ۳ و ۵ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می‌شود که فاصله آن از سایر خوشه‌ها برابر است بابیشترین فاصله بین ۳ و یا ۵ از سایر خوشه‌ها. نتیجه در جدول ۷ نشان ‌داده شده است.

 

جدول ۷: ماتریس فاصله بین ۵ خوشه حاصل از تکرار اول

۱ ۲ (۳ و ۵) ۴ ۶
۱ ۰ ۴ ۱۳ ۲۴ ۸
۲ ۰ ۱۱ ۲۲ ۱۰
(۳ و ۵) ۰ ۷ ۹
۴ ۰ ۱۸
۶ ۰

 

با توجه به جدول ۷ مشخص است که داده‌های ۱ و ۲ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می‌شود که فاصله آن از سایر خوشه‌ها برابر است با بیشترین فاصله بین ۱ و یا ۲ از سایر خوشه‌ها. نتیجه در جدول ۸ نشان ‌داده شده است.

 

جدول ۸: ماتریس فاصله بین ۴ خوشه حاصل از تکرار دوم

(۱ و ۲) (۳ و ۵) ۴ ۶
(۱ و ۲) ۰ ۱۳ ۲۴ ۱۰
(۳ و ۵) ۰ ۷ ۹
۴ ۰ ۱۸
۶ ۰

 

با توجه به جدول ۸ مشخص است که خوشه‌های (۳ و ۵) و ۴ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می‌شود که فاصله آن از سایر خوشه‌ها برابر است با بیشترین فاصله بین (۳ و ۵) و یا ۴ از سایر خوشه‌ها. نتیجه در جدول ۹ نشان ‌داده شده است.

 

جدول ۹: ماتریس فاصله بین ۳ خوشه حاصل از تکرار سوم

(۱ و ۲) (۳، ۴ و ۵) ۶
(۱ و ۲) ۰ ۲۴ ۱۰
(۳، ۴ و ۵) ۰ ۱۸
۶ ۰

 

با توجه به جدول ۹ مشخص است که خوشه‌های (۱ و ۲) و ۶ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می‌شود که فاصله آن از سایر خوشه‌ها برابر است با بیشترین فاصله بین (۱ و ۲) و یا ۶ از سایر خوشه‌ها. نتیجه در جدول ۱۰ نشان ‌داده شده است.

 

جدول ۱۰: ماتریس فاصله بین ۲ خوشه حاصل از تکرار چهارم

(۱، ۲ و ۶) (۳، ۴ و ۵)
(۱، ۲ و ۶) ۰ ۲۴
(۳، ۴ و ۵) ۰

 

در نهایت این دو خو‌شه حاصل ا هم ترکیب می‌شوند. نتیجه در دندوگرام شکل ۷ نشان داده شده است.

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

شکل ۷: دندوگرام مثال Complete-Link

 

خوشه‌بندی با روش Average-Link

 

این روش همانند Single-Link جزء روشهای خوشه‌بندی سلسله مراتبی و انحصاری محسوب می‌شود.  از آنجا که هر دو روش خوشه‌بندی Single-link و Complete-link بشدت به نویز حساس می‌باشد، این روش که محاسبات بیشتری دارد، پیشنهاد شد. در این روش برای محاسبه شباهت بین دو خوشه A و B از معیار زیر استفاده می‌شود:

(۳)

 

که i یک نمونه داده متعلق به خوشه A و j یک نمونه داده متعلق به خوشه B می‌باشد. و NA تعداد اعضاء خوشه A  و NB تعداد اعضاء خوشه B است. در واقع در این روش، شباهت بین دو خوشه میانگین فاصله بین تمام اعضاء یکی با تمام اعضاء دیگری است. در شکل زیر این مفهوم بهتر نشان‌ داده شده است. [۵]

 

شکل ۸: شباهت بین دو خوشه در روش Average-Link برابر است با میانگین فاصله بین داده‌های دو خوشه

 

  مثال: در این قسمت سعی شده است تا در مثالی با  فرض داشتن ۶ نمونه داده و ماتریس فاصله بین آنها که در جدول ۱۱ نشان ‌داده شده است، نحوه اعمال روش خوشه‌بندیAverage-Link بهتر تشریح شود.

 

جدول ۱۱: ماتریس فاصله بین ۶ نمونه داده

۱ ۲ ۳ ۴ ۵ ۶
۱ ۰ ۴ ۱۳ ۲۴ ۱۲ ۸
۲ ۰ ۱۰ ۲۲ ۱۱ ۱۰
۳ ۰ ۷ ۳ ۹
۴ ۰ ۶ ۱۸
۵ ۰ ۸٫۵
۶ ۰

 

در ابتدا هر داده به عنوان یک خوشه در نظر گرفته می‌شود و یافتن نزدیکترین خوشه در واقع یافتن کمترین فاصله بین داده‌های بالا خواهد بود. با توجه به جدول ۱۱ مشخص است که داده‌های ۳ و ۵ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می‌شود که فاصله آن از سایر خوشه‌ها برابر است بامیانگین فاصله بین ۳ و ۵ از سایر خوشه‌ها. نتیجه در جدول ۱۲ نشان ‌داده شده است.

 

جدول ۱۲: ماتریس فاصله بین ۵ خوشه حاصل از تکرار اول

۱ ۲ (۳ و ۵) ۴ ۶
۱ ۰ ۴ ۱۲٫۵ ۲۴ ۸
۲ ۰ ۱۰٫۵ ۲۲ ۱۰
(۳ و ۵) ۰ ۶٫۵ ۸٫۷۵
۴ ۰ ۱۸
۶ ۰

 

با توجه به جدول ۱۲ مشخص است که داده‌های ۱ و ۲ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می‌شود که فاصله آن از سایر خوشه‌ها برابر است با بیشترین فاصله بین ۱ و یا ۲ از سایر خوشه‌ها. نتیجه در جدول ۱۳ نشان ‌داده شده است.

 

جدول ۱۳: ماتریس فاصله بین ۴ خوشه حاصل از تکرار دوم

(۱ و ۲) (۳ و ۵) ۴ ۶
(۱ و ۲) ۰ ۱۱٫۵ ۲۳ ۹
(۳ و ۵) ۰ ۶٫۵ ۸٫۷۵
۴ ۰ ۱۸
۶ ۰

 

با توجه به جدول ۱۳ مشخص است که خوشه‌های (۳ و ۵) و ۴ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می‌شود که فاصله آن از سایر خوشه‌ها برابر است با بیشترین فاصله بین (۳ و ۵) و یا ۴ از سایر خوشه‌ها. نتیجه در جدول ۱۴ نشان ‌داده شده است.

 

جدول ۱۴: ماتریس فاصله بین ۳ خوشه حاصل از تکرار سوم

(۱ و ۲) (۳، ۴ و ۵) ۶
(۱ و ۲) ۰ ۲۳ ۹
(۳، ۴ و ۵) ۰ ۱۸
۶ ۰

 

با توجه به جدول ۱۴ مشخص است که خوشه‌های (۱ و ۲) و ۶ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می‌شود که فاصله آن از سایر خوشه‌ها برابر است با بیشترین فاصله بین (۱ و ۲) و یا ۶ از سایر خوشه‌ها. نتیجه در جدول ۱۵ نشان ‌داده شده است.

 

جدول ۱۵: ماتریس فاصله بین ۲ خوشه حاصل از تکرار چهارم

(۱، ۲ و ۶) (۳، ۴ و ۵)
(۱، ۲ و ۶) ۰ ۲۰٫۵
(۳، ۴ و ۵) ۰

 

در نهایت این دو خو‌شه حاصل ا هم ترکیب می‌شوند. نتیجه در دندوگرام شکل ۹ نشان داده شده است.

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

شکل ۹: دندوگرام مثال Average-Lin

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

telegramchanel کانال تلگرام    با عضویت در کانال تلگرام از مطالب آموزشی و مطالب جدید وب سایت مطلع شوید

@matlab24Dotir

جهت عضویت کلیک کنید

 

      طراحی وب سایت

طراحی وب

شماره تماس:09120563264