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

شکل2-2 مراحل خوشه بندی
2-2-5- انواع روشهای خوشهبندی
Widget not in any sidebars

روشهای کلاسترینگ به انواع مختلف و در طبقه بندیهای مختلف معرفی میشوند. این روشها را می توان از چندین جنبه تقسیمبندی کرد[20]:
خوشهبندی انحصاری و خوشهبندی با همپوشی
در روش انحصاری پس از خوشهبندی، هر داده دقیقاً به یک خوشه تعلق می گیرد مانند روش خوشه بندی k-means . ولی در خوشهبندی با روش همپوشی پس از خوشهبندی، به هر داده یک درجهی تعلق به ازاء هر خوشه نسبت داده میشود یعنی یک داده میتواند با نسبتهای متفاوتی به چندین خوشه تعلق داشته باشد. نمونهای از این روش، خوشهبندی فازی است.
خوشهبندی سلسله مراتبی و خوشهبندی مسطح
در روش سلسله مراتبی، به خوشههای نهایی بر اساس میزان عمومیت آنها، ساختاری سلسله مراتبی نسبت داده میشود مانند روش اتصال منفرد. در روش مسطح تمام خوشههای نهایی دارای یک میزان عمومیت هستند مانند k-means.
با توجه به اینکه روشهای خوشهبندی سلسله مراتبی اطلاعات بیشتر و دقیق تری تولید میکنند برای تحلیل دادههای با جزئیات پیشنهاد میشوند، ولی از آن جایی که پیچیدگی محاسباتی بالایی دارند، برای مجموعه دادههای بزرگ روش خوشهبندی مسطح پیشنهاد میشود.
2-2-6- خوشهبندی سلسله مراتبی
همانگونه که بیان شد، در روش خوشهبندی سلسله مراتبی به خوشههای نهایی بر اساس میزان عمومیت آنها، ساختاری سلسله مراتبی، معمولاً به صورت درختی نسبت داده میشود. به این درخت سلسله مراتبی دندوگرام میگویند. گره ریشهی نمودار درختی، تمام مجموعه داده را نشان میدهد و هرگره برگ، به عنوان یک نقطه داده در نظرگرفته میشود. بنابراین، گرههای میانی حوزهی اشیایی که به هم  نزدیک هستند؛ را توصیف می کنند و ارتفاع نمودار درختی معمولاً فاصلهی بین یک نقطه داده و یک خوشه را بیان میکند. نتایج نهایی خوشه بندی میتواند با برش نمودار درختی در سطوح مختلف به دست آید. این نمودار توصیفات آموزندهای از ساختار خوشه بندی داده را فراهم میکند، مخصوصاً وقتی ارتباطات سلسله مراتبی حقیقی در دادهها وجود داشته باشد. این روش خوشهبندی بر اساس ساختار سلسله مراتبی تولیدی توسط آنها به دو دسته تقسیم می شود[21]: بالا به پایین یا تقسیم شونده و پایین به بالا یا متراکم شونده.
2-2-6-1- خوشه بندی سلسله مراتبی تقسیم شونده
در این روش ابتدا تمام دادهها به عنوان یک خوشه در نظر گرفته می شوند و سپس طی یک فرآیند تکراری، دادههایی که شباهت کمتری به هم دارند به خوشههای مجزایی شکسته میشوند. این روال تا رسیدن به خوشههایی که دارای یک عضو هستند؛ ادامه پیدا میکند.
2-2-6-2- خوشه بندی سلسله مراتبی متراکم شونده
ابتدا هر داده به عنوان خوشهای مجزا در نظر گرفته می شود و در طی یک فرآیند تکراری در هر مرحله خوشههایی که شباهت بیشتری با هم دارند با یکدیگر ترکیب شده تا در نهایت یک یا تعداد مشخصی خوشه حاصل شود. از انواع الگوریتمهای خوشهبندی سلسله مراتبی متراکم شونده می توان اتصال منفرد، اتصال کامل و اتصال میانگین را نام برد. تفاوت اصلی بین این روشها به نحوهی محاسبهی شباهت بین خوشه ها مربوط می شود.

شکل2 3 محاسبه فاصله در اتصال منفرد، اتصال میانگین و اتصال کامل
Agglomerative
Divisive
شکل 2-4 تفاوت بین روش متراکم شوتده و تقسیم کننده
اتصال منفرد
به این روش خوشه‌بندی، تکنیک نزدیکترین همسایه نیز گفته می‌شود. این الگوریتم برای دادههائی که خواص مشترکی ندارند (پراکندگی خوب، زنجیرهای مانند و یا هم مرکز ) بسیار خوب عمل میکند. این در حالی است که الگوریتم پارتیشنی چون K-means بر روی مجموعه دادههائی که همسانگرد هستند، کارا میباشد. در اتصال منفرد، فاصله‌ی بین دو خوشه برابر با کمترین فاصله بین جفت اشیایی است که هر کدام متعلق به یکی از دو خوشه است (شکل 2-3، قسمت الف). به بیان دیگر، ودو خوشه هستند و فاصله‌ی بین دو عضو و است. بهکارگیری الگوریتم اتصال منفرد هنگامی مفید است که خوشه‌ها دارای اشیای نزدیک به هم باشند؛ بهعبارت دیگر، خوشه پیوسته باشد.
اتصال میانگین
 از آنجا که هر دو روش خوشه‌بندی اتصال منفرد و اتصال کامل به شدت به نویز حساس می‌باشد، این روش که محاسبات بیشتری دارد، پیشنهاد شد. در این الگوریتم، فاصلهی ‌بین دو خوشه به صورت میانگین فاصله ‌بین همهی ‌جفت‌هایـــی است که یکی از آنها در خوشــهی ‌نخست و دیگری در خوشهی ‌دوم باشد (شکل 2-3، قسمت ب). به بیان دیگر:
که و دو خوشه هستند، و تعداد اشیای متعلق به دو خوشه‌ی و هستند و فاصلهی ‌بین دو عضو و است. خوشه‌هایی که اتصال میانگین تولید می‌کند، فشرده‌تر از خوشه‌هایی است که در اتصال منفرد تولید می‌شوند.