( Hierarchical Clustering ) خوشەبندی سلسه مراتبی

دوشنبه ۱۲ خرداد ۱۳۹۹سامان

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

روش کار تکنیکهای خوشه‌بندی سلسله‌مراتبی معمولا بر اساس الگوریتمهای حریصانه و بهینگی مرحله‌ای است. خوشه بندی سلسله مراتبی چگونگی ترتیب مشاهدات و خوشه ها با هم را، به صورت نمودار درختی نمایش می دهد. می توان به کمک نمودار درختی، نحوه و ترتیب خوشه ها را مشخص کرد. از مزیت های خوشه بندی سلسله مراتبی، سادگی و قابلیت درک برای تمامی پژوهشگران است. این روش شامل مد لهای متنوعی است که میتواند نیازهای متعددی را رفع کند. داد ههایی که بر روی آن تکنیک های خوشه بندی را اجرا میکنیم، داد ههای جمع اوری شده به روش ثبتی، و یا داده هایی شبیه سازی شده هستند. در آزمایشگا ههای آمار برای آموزش و یا بررسی کارایی و دقت یک روش و یا مدل از روش های شبیه سازی داد هها استفاده می کنیم. روشهای خوشه‌بندی بر اساس ساختار سلسله مراتبی تولیدی توسط انها معمولا به دو دستة زیر تقسیم می‌شوند: 1. بالا به پایین  یا تقسیم کننده :در این روش ابتدا تمام داده‌ها به عنوان یک خوشه در نظر گرفته می‌شوند و سپس در طی یک فرایند تکراری در هر مرحله داده‌هایی شباهت کمتری به هم دارند به خوشه‌های مجزایی شکسته می‌شوند و این روال تا رسیدن به خوشه‌هایی که دارای یک عضو هستند ادامه پیدا می‌کند. 2.پایین به بالا یا تجمعی : با در نظر گرفتن هر نقطه به صورت یک خوشه روند خوشەبندی را شروع میکند و در هرگام دو نزدیک ترین خوشه را باهم ترکیب کرده و روند را تا رسیدن به یک خوشه یا (K خوشه) ادامه میدهد. از انواع الگوریتمهای خوشه‌بندی سلسله مراتبی تجمعی رایج می‌توان از الگوریتمهای Single-Link، Average-Linkو Complete-Linkنام برد. تفاوت اصلی در بین تمام این روشها به نحوة محاسبة شباهت بین خوشه‌ها مربوط می‌شود. بحث خوشه بندی سلسله مراتبی یکی از مباحث داغ در خوشه بندی بیگ دیتا هست.

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

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

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

1. Compute the proximity matrix

2. Let each data point be a cluster

3. Repeat

4. Merge the two closest clusters

5. Update the proximity matrix

6. Until only a single cluster remains

نکته کلیدی در این خوشه بندی محاسبه مجاورت بین دو خوشه است که استفاده از روشهای مختلف برای محاسبەی فاصلەی بین خوشەها باعث به وجود آمدن روشهای مختلف خوشەبندی سلسله مراتبی تجمعی شده است

به عنوان مثال مجموعه داده زیر را در نظر بگیرید که شامل ١٢ رکورد میباشد، ماتریس موجود در شکل زیر، ماتریس مجاورت را برای این مجموعه ذاده نشان میدهد

فرض کنید بعد از اجرای چند گام خوشەهای زیر به دست آمدەاند

را ترکیب کرده و ماتریس مجاورت را به روزرسانی کنیم  C و 5 C میخواهیم دو خوشه نزدیک 2

اما چگونه باید ماتریس مجاورت را به روزرسانی کرد؟

 قبلا هم گفتیم کلیدی ترین نکته در این خوشه بندی محاسبه مجاورت بین دو خوشه است که در این جا چند مورد برسی میشود:

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

 

(MIN-Single Link) خوشەبندی تجمعی کمینەای

در این روش شباهت بین دو خوشه بر مبنای دو شبیەترین (نزدیکترین) نقطه از آنها تعریف میشود

به عنوان مثال:برای یک مجموعه داده که ماتریس مجاورت آن به شکل زیر است، دندروگرام خوشەبندی سلسله مراتبی تجمعی کمینەای به صورت زیر است: 

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

(MAX-Complete linkage) خوشەبندی تجمعی بیشینەای
.در این روش شباهت بین دو خوشه بر مبنای دو نقطه که کمترین شباهت (بیشترین فاصله) را دارند، تعریف میشود
 

 

 

(Group Average) خوشەبندی تجمعی میانگینی

در این روش مجاورت بین دو خوشه به صورت میانگین مجاورت جفت نقاط درون خوشەها تعریف میشود. 

خوشەبندی تجمعی مرکزی 

در این الگوریتم پس از محاسبه مرکز هر خوشه، فاصله بین دو خوشه به صورت فاصله بین مراکز آنها تعریف میشود.

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

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

مراحل انجام این روش را میتوان به صورت زیر در نظر گرفت :

  1. بعد از اینکه تمامی رکوردها به صورت یک خوشه در نظر گرفته شد، رکوردی را که بیشترین فاصله با رکوردهای دیگر دارد را انتخاب و به صورت یک خوشه جدید در نظر میگیریم
  2. برای هر رکورد i با استفاده از رابطه زیر مقدار Di را حساب میکنیم
  3. رکوردی که بیش ترین مقدار D را دارد، یافته و ان را به عنوان مرکز خوشه جدید در نظر میگیریم
  4. دو مرحله قبل را انقدر تکرار میکنیم تا مقدار D برای تمامی رکورد ها منفی شود