۱- شاخص خارجی[۷۵] که مشخص می‌کند که کدام خوشه‌های پیداشده به وسیله الگوریتم خوشه‌بندی با ساختارهای خارجی تطبیق دارند. در این روش نیاز به اطلاعات اضافی مثل برچسب نقاط داده، داریم. آنتروپی یک مثالی از شاخص خارجی است.
۲- شاخص داخلی[۷۶] که برای اندازه‌گیری میزان خوبی[۷۷] یک ساختار خوشه‌بندی بدون توجه به اطلاعات خارجی به کار میرود. [۷۸] یک نمونه از شاخص داخلی است.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
۳- شاخص نسبی[۷۹] که برای مقایسه دو خوشه‌بندی مختلف یا دو خوشه مختلف به کار میرود. اغلب یک شاخص خارجی یا داخلی برای این تابع استفاده می‌شود. برای مثال، دو خوشه‌بندی می‌توانند با مقایسه یا آنتروپی‌شان مقایسه شوند.
این فصل تعدادی از مهم‌ترین و رایج‌ترین روش‌های به‌کاررفته برای ارزیابی خوشه‌بندی را مرور خواهد کرد.
۲-۲-۲-۱. معیار SSE
یک معیار داخلی ارزیابی خوشه‌بندی، مثل ، می‌تواند برای ارزیابی یک خوشه‌بندی نسبت به خوشه‌بندی دیگر به کار رود. به علاوه، یک معیار داخلی اغلب می‌تواند برای ارزیابی یک خوشه‌بندی کامل یا یک خوشه تنها به استفاده شود. این اغلب به خاطر این است که این روش، سعی می‌کند تا میزان خوبی کلی خوشه‌بندی را به عنوان یک جمع وزن‌دار از خوبی‌های هر خوشه در نظر می‌گیرد. با بهره گرفتن از رابطه ۲-۲۵ محاسبه می‌شود [۶۸].
(۲-۲۵)
که یک نقطه داده در خوشه است و ، j-امین ویژگی از داده X است. ، j-امین ویژگی از مرکز خوشه می‌باشد. برای مقایسه دو خوشه‌بندی مختلف روی یک داده با یک تعداد مشابه، تنها مقایسه مقدارهای متناظر آن‌ها کافی است. هر چه مقدار کمتر باشد، آن خوشه‌بندی بهتر خواهد بود. البته، وقتی تعداد نقاط داده در دو خوشه متفاوت باشند، مقایسه مستقیم از روی مقدار خوب نخواهد بود. بنابراین، یک خوشه معیار مناسب تری برای مقایسه است. رابطه ۲-۲۶ این معیار را نشان می‌دهد که در آن مقدار تعداد کل نمونه‌هاست [۶۸].
(۲-۲۶)
تعداد درست خوشه‌ها در الگوریتم ، اغلب می‌تواند با بهره گرفتن از نگاه کردن به منحنی مشخص شود. این منحنی با رسم مقادیر به ازای های مختلف به دست می‌آید. تعداد خوشه‌های بهینه با توجه به منحنی ، ای است که به ازای آن نرخ کاهش مقدار ، قابل چشم‌پوشی شود. شکل ۲-۱۳-ب منحنی را برای داده‌های شکل ۲-۱۳-الف، نشان می‌دهد.
(الف)
(ب)
شکل۲-۱۳. (الف) مجموعه داده با تعداد ۱۰ خوشه واقعی. (ب) منحنی مربوطه [۶۸]
همان طور که از شکل ۲-۱۳-ب برمی‌آید، برای مقادیر های از صفر تا ۱۰ شیب منحنی نسبت به بقیه مقادیر ، تندتر می‌باشد. این امر نشان‌دهنده آن است که مقدار یک مقدار بهینه برای تعداد خوشه‌ها می‌باشد.
(الف)
(ب)
شکل۲-۱۴. (الف) مجموعه داده (ب) منحنی مربوطه [۲]
شکل ۲-۱۴-ب نیز منحنی را برای داده‌های شکل ۲-۱۴-الف، نشان می‌دهد. مشاهده می‌شود که در این داده‌ها، چون تعداد خوشه‌ها نسبت به شکل ۲-۱۴-الف کاملاً گویا نیست، بنابراین، منحنی آن نیز نرم تر خواهد بود . اما با توجه به شکل ۲-۱۴-ب، می‌توان گفت که تعداد نسبتاً خوب باشد. چون منحنی برای های بعد از ۸، دارای شیب کندتری خواهد شد. با توجه به نتایج فوق می‌توان گفت که اگرچه منحنی برای همه مسایل نمی‌تواند جواب بهینه برای تعداد بدهد، اما می‌تواند به عنوان یک معیار خوب برای این امر مطرح باشد.
۲-۲-۲-۲. معیار اطلاعات متقابل نرمال شده
معیار اطلاعات متقابل ( [۸۰]) توسط کاور و توماس [۷۱] معرفی شد که یک روش جهت اندازه‌گیری کیفیت اطلاعات آماری مشترک بین دو توزیع است. از آنجایی که این معیار وابسته به اندازه خوشه‌ها است در [۵۴] روشی جهت نرمال سازی آن ارائه شده است. فرد و جین [۱۹] روش نرمال سازی اطلاعات متقابل را اصلاح کردند و آن را تحت عنوان اطلاعات متقابل نرمال ( [۸۱]) ارائه داده‌اند. رابطه ۲-۲۷ اطلاعات متقابل نرمال شده را نشان می‌دهد[۱, ۲, ۱۹] .
(۲-۲۷)
در رابطه ۲-۲۷ پارامتر کل نمونه‌ها است و یعنی افرازهایی که اندیس آن‌ها شامل i با تمام مقادیر j می‌باشد و یعنی افرازهایی که تمام مقادیر i با و اندیس j را شامل شود. از رابطه ۲-۲۸ محاسبه می‌شود [۱, ۲, ۱۹].
(۲-۲۸)
, ,
در صورتی که دو افراز به صورت و که در آن کل داده و خوشه اول و خوشه دوم هر یک از افرازها باشد آنگاه نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد، نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد، نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد و نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد. در واقع و به ترتیب بیانگر کل نمونه‌های موجود در و می‌باشد [۱].
شکل ۲-۱۵ دو افراز اولیه را نشان می‌دهد که میزان پایداری برای هر کدام از خوشه‌های به دست آمده هم محاسبه شده است. در این مثال الگوریتم به عنوان الگوریتم خوشه‌بندی اولیه انتخاب شده است و تعداد خوشه‌های اولیه برابر با سه نیز به عنوان پارامتر آن از قبل مشخص شده است. همچنین، در این مثال تعداد افرازهای موجود در مجموعه مرجع برابر با ۴۰ می‌باشد. در ۳۶ افراز نتایجی مشابه با شکل ۲-۱۵ (a) و در ۴ حالت باقیمانده نیز نتایجی مشابه با شکل ۲-۱۵ (a) حاصل شده است [۱].
شکل۲-۱۵. دو افراز اولیه با تعداد سه خوشه. (a) خوشه‌بندی درست (b) خوشه‌بندی نادرست [۱]
از آن جایی که در مجموعه مرجع در ۹۰ % مواقع، داده‌های متراکم گوشه بالا‐چپ از شکل ۲-۱۵ در یک خوشه مجزا گروه‌بندی شده‌اند، بنابراین این خوشه باید مقدار پایداری بالایی را به خود اختصاص دهد. اگرچه این مقدار نباید دقیقاً برابر با یک باشد (چون در همه موارد این خوشه درست تشخیص داده نشده است)، مقدار پایداری با روش متداول اطلاعات متقابل نرمال شده مقدار یک را بر می‌گرداند. از آن جایی که ادغام دو خوشه سمت راست تنها در ۱۰ % موارد مانند شکل ۲-۱۵ (b) اتفاق افتاده است، خوشه حاصل باید مقدار پایداری کمی به دست آورد. اگر چه خوشه حاصل از ادغام دو خوشه سمت راستی، به ندرت ( ۱۰ % موارد) در مجموعه مرجع دیده شده است، مقدار پایداری برای این خوشه نیز برابر با یک به دست می‌آید. در اینجا مشکل روش متداول محاسبه پایداری با بهره گرفتن از اطلاعات متقابل نرمال شده ظاهر می‌شود. از آنجایی که معیار اطلاعات متقابل نرمال شده یک معیار متقارن است، مقدار پایداری خوشه بزرگ ادغامی سمت راست (با ۱۰ % تکرار) دقیقاً برابر با میزان پایداری خوشه متراکم گوشه بالا‐چپ (با ۹۰ % تکرار) به دست می‌آید. به عبارت دیگر در مواردی که داده‌های دو خوشه مکمل یکدیگر باشند، یعنی اجتماع داده‌های آن‌ها شامل کل مجموعه داده شود و اشتراک داده‌های آن‌ها نیز تهی باشد، مقدار پایداری برای هر دو به یک اندازه برابر به دست می‌آید. از دیدگاه دیگر، این اتفاق زمانی رخ می‌دهد که تعداد خوشه‌های تشکیل‌دهنده مجموعه در خوشه‌بندی مرجع عددی بیشتر از یک باشد. هر زمان که با ادغام دو یا بیشتر از خوشه‌ها به دست آید، منجر به نتایج نادرست در مقدار پایداری می‌شود. ما این مشکل را تحت عنوان مشکل تقارن در اطلاعات متقابل نرمال شده می‌شناسیم. در سال‌های اخیر روش‌هایی جهت حل این مشکل ارائه‌شده‌اند که یکی از آن‌ها را علیزاده و همکاران در [۱, ۹]ارائه داده‌اند که در آن بزرگ‌ترین خوشه از بین مجموعه مرجع (که بیش از نصف نمونه‌هایش در خوشه مورد مقایسه وجود دارد) جایگزین اجتماع همه خوشه‌ها می‌شود که ما آن را با عنوان روش Max می‌شناسیم. روش دیگر جهت رفع این مشکل معیار [۸۲]APMM می‌باشد. در ادامه به بررسی این معیار می‌پردازیم [۱, ۸, ۶۷].
۲-۲-۲-۳. معیار APMM
