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

1) روش پایین به بالا (تجمعی Agglomerative):

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

فلوچارت این روش :

مثال 1)

گام های این روش را با ذکر یک مثال بیان می کنیم:(_خوشه بندی با روش پیوند مینگین انجام شده)

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

گام اول:

الگوریتم، تعداد N خوشه (به تعداد مشاهدات) را در نظر می گیرد و برای تمام N خوشه ماتریس فاصله را حساب می کند.

مثال: 5 مشاهده= 5 خوشه داریم

ماتریس فاصله( هر درایه:میزان عدم تشابه یعنی فاصله ی مشاهدات)

گام دوم:

 در ماتریس فاصله به دنبال کمترین مقدار فاصله ها بین خوشه ها هستیم پس دو مشاهده ای که کمترین میزان فاصله را داراست باهم ادغام شده و تشکیل خوشه ای جدید را میدهند در این مثال دو مشاهده a و b تشکیل خوشه می دهند.

پس خوشه های پایان گام اول : {aوb} ، {c} ،{d} ، {e} می باشند.

و حالا برای یافتن مقادیر ماتریس فاصله ی جدید  از تابع پیوند میانگین استفاده می کنیم.

هر درایه= مقادیر میزان عدم تشابه (  فاصله) خوشه ها

گام سوم:

کمترین فاصله مربوط به دو خوشه {d}و {e} می باشد پس خوشه جدید {d،e}.

متوسط میزان فاصله خوشه ها:

گام چهارم:

گامهای 2 و 3 تا زمانی که تنها یک خوشه که شامل تمامی مشاهدات است به همین منوال ادامه پیدا می کند.

برای نمایش بهتر اطلاعات از نمودار کمک میگیریم.

مثال 2)

یک مثال دیگر از این نوع خوشه بندی که با پیوند تکی انجام شده:

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

در این مثال 6 نمونه داده و ماتریس فاصله ی آنها در جدول 1 نشان داده شده است:

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

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

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

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

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

مثال 3)

یک مثال دیگر از این روش که با پیوند کامل انجام شده است:

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

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

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

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

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

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

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

2) روش بالا به پایین (تقسیم کننده Divisive):

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

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

عیب این روش:

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

یکی از الگوریتم های معروفDIANA(Divisive Analysis) .

فلوچارت این روش:

نمودار مثال 1 برای این روش به این صورت است:

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

همواره نتایج دو روش خوشه بندی سلسله مراتبی تجمعی و تقسیم کننده یکسان نیست و می تواند با یکدیگر متفاوت باشد.

اگر بخواهیم تفاوت این دو روش را در یک نمودار بیان کنیم به صورت زیر است:

منبع:

دانلود خوشه بندی و روشهای آن

دانلود تحلیل خوشه بندی(ppt)