دو معیار پایه اندازه ­گیری برای ارزیابی و انتخاب خوشه­های بهینه عبارتند از:

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

• • تراکم^[۱۸] : داده ­های متعلق به یک خوشه بایستی تا حد ممکن به یکدیگر نزدیک باشند. معیار رایج برای تعیین میزان تراکم داده ­ها واریانس داده ­ها است.

• • جدایی ^[۱۹]: خوشه ­ها خود بایستی به اندازه کافی از هم جدا باشند. سه راه برای سنجش میزان جدایی خوشه ها مورد استفاده قرار می گیرد:

• • فاصله بین نزدیک­ترین داده ­ها از دو خوشه

• • فاصله بین دورترین داده ­ها از دو خوشه

• • فاصله بین مراکز خوشه ­ها

هم­چنین، روش­های ارزیابی خوشه­های حاصل از خوشه­بندی را به سه دسته تقسیم می کنند: شاخص­ های خارجی، شاخص­ های داخلی و شاخص­ های نسبی.
شاخص­ های خارجی: شاخص­ های خارجی مبتنی بر بعضی ساختارهای از پیش تعیین شده اند که بازیاب اطلاعات قبلی درمورد داده ها بوده و به عنوان استانداردی برای اعتبار راه­ حل­های خوشه­بندی استفاده می­شوند.
شاخص­ های داخلی: تست داخلی به اطلاعات خارجی(دانش پیشین) وابستگی ندارد. آن­ها مستقیماً ساختار خوشه­بندی را از روی داده ­های اصلی، آزمایش می­نمایند. از روش­های ساده و معروف در این زمینه T-test می­باشد.
شاخص­ های نسبی: معیارهای نسبی بر تفاوت­ ساختـــارهای خوشه­بندی تأکید می­نماید، به­ طوری که به عنوان مرجعی می ­تواند شایستگی خوشه ­ها را آشکار نماید.
Cluster
Pattern
Feature selection
Interpattern similarity
Grouping
شکل۲-۲ مراحل خوشه بندی
۲-۲-۵- انواع روش­های خوشه­بندی
روش­های کلاسترینگ به انواع مختلف و در طبقه بندی­های مختلف معرفی می­شوند. این روش­ها را می توان از چندین جنبه تقسیم ­بندی کرد[۲۰]:

1. 1. خوشه­بندی انحصاری^[۲۰] و خوشه­بندی با همپوشی^[۲۱]

در روش انحصاری پس از خوشه­بندی، هر داده دقیقاً به یک خوشه تعلق می گیرد مانند روش خوشه بندی k-means . ولی در خوشه­بندی با روش همپوشی پس از خوشه­بندی، به هر داده یک درجه­ تعلق به ازاء هر خوشه نسبت داده می­ شود یعنی یک داده می ­تواند با نسبت­های متفاوتی به چندین خوشه تعلق داشته باشد. نمونه ­ای از این روش، خوشه­بندی فازی است.

1. 1. خوشه­بندی سلسله مراتبی^[۲۲] و خوشه­بندی مسطح^[۲۳]

در روش سلسله مراتبی، به خوشه­های نهایی بر اساس میزان عمومیت آن­ها، ساختاری سلسله مراتبی نسبت داده می­ شود مانند روش اتصال منفرد. در روش مسطح تمام خوشه­های نهایی دارای یک میزان عمومیت هستند مانند k-means.
با توجه به اینکه روش­های خوشه­بندی سلسله مراتبی اطلاعات بیشتر و دقیق تری تولید می­ کنند برای تحلیل داده ­های با جزئیات پیشنهاد می­شوند، ولی از آن جایی که پیچیدگی محاسباتی بالایی دارند، برای مجموعه داده ­های بزرگ روش خوشه­بندی مسطح پیشنهاد می­ شود.
۲-۲-۶- خوشه­بندی سلسله مراتبی
همان­گونه که بیان شد، در روش خوشه­بندی سلسله مراتبی به خوشه­های نهایی بر اساس میزان عمومیت آن­ها، ساختاری سلسله مراتبی، معمولاً به صورت درختی نسبت داده می­ شود. به این درخت سلسله مراتبی دندوگرام^[۲۴] می­گویند. گره ریشه­ نمودار درختی، تمام مجموعه داده را نشان می­دهد و هرگره برگ، به عنوان یک نقطه داده در نظرگرفته می­ شود. بنابراین، گره­های میانی حوزه­ اشیایی که به هم  نزدیک هستند؛ را توصیف می کنند و ارتفاع نمودار درختی معمولاً فاصله­ی بین یک نقطه داده و یک خوشه را بیان می­ کند. نتایج نهایی خوشه بندی می ­تواند با برش نمودار درختی در سطوح مختلف به دست آید. این نمودار توصیفات آموزنده­ای از ساختار خوشه بندی داده را فراهم می­ کند، مخصوصاً وقتی ارتباطات سلسله مراتبی حقیقی در داده ­ها وجود داشته باشد. این روش خوشه­بندی بر اساس ساختار سلسله مراتبی تولیدی توسط آن­ها به دو دسته تقسیم می شود[۲۱]: بالا به پایین یا تقسیم شونده^[۲۵] و پایین به بالا یا متراکم شونده^[۲۶].
۲-۲-۶-۱- خوشه بندی سلسله مراتبی تقسیم شونده
در این روش ابتدا تمام داده ­ها به عنوان یک خوشه در نظر گرفته می شوند و سپس طی یک فرایند تکراری، داده­هایی که شباهت کمتری به هم دارند به خوشه­های مجزایی شکسته می­شوند. این روال تا رسیدن به خوشه­هایی که دارای یک عضو هستند؛ ادامه پیدا می­ کند.
۲-۲-۶-۲- خوشه بندی سلسله مراتبی متراکم شونده
ابتدا هر داده به عنوان خوشه­ای مجزا در نظر گرفته می شود و در طی یک فرایند تکراری در هر مرحله خوشه­هایی که شباهت بیشتری با هم دارند با یکدیگر ترکیب شده تا در نهایت یک یا تعداد مشخصی خوشه حاصل شود. از انواع الگوریتم­های خوشه­بندی سلسله مراتبی متراکم شونده می توان اتصال منفرد، اتصال کامل و اتصال میانگین را نام برد. تفاوت اصلی بین این روش­ها به نحوه­ محاسبه­ی شباهت بین خوشه ها مربوط می شود.
شکل۲‑ ۳ محاسبه فاصله در اتصال منفرد، اتصال میانگین و اتصال کامل
Agglomerative
Divisive
شکل ۲-۴ تفاوت بین روش متراکم شوتده و تقسیم کننده

• • اتصال منفرد

به این روش خوشه‌بندی، تکنیک نزدیک­ترین همسایه^[۲۷] نیز گفته می‌شود. این الگوریتم برای داده­هائی که خواص مشترکی ندارند^[۲۸] (پراکندگی خوب، زنجیره­ای مانند و یا هم مرکز ) بسیار خوب عمل می­ کند. این در حالی است که الگوریتم پارتیشنی چون K-means بر روی مجموعه داده­هائی که همسانگرد^[۲۹] هستند، کارا می­باشد. در اتصال منفرد، فاصله‌­ی بین دو خوشه برابر با کمترین فاصله بین جفت اشیایی است که هر کدام متعلق به یکی از دو خوشه است (شکل ۲-۳، قسمت الف). به بیان دیگر،  و  دو خوشه هستند و  فاصله‌­ی بین دو عضو  و  است. به­ کارگیری الگوریتم اتصال منفرد هنگامی مفید است که خوشه‌ها دارای اشیای نزدیک به هم باشند؛ به­عبارت دیگر، خوشه پیوسته باشد.