«خوشه‌بندی» (Clustering)، روشی است که در آن دسته‌بندی یا طبقه‌بندی نقاط براساس خصوصیات و ویژگی‌هایشان انجام می‌شود. این کار اغلب با استفاده از یک «تابع شباهت» (Similarity Function) یا «عدم شباهت» (Dissimilarity) تعریف شده برای سنجش دوری یا نزدیکی نقاط از یکدیگر صورت می‌پذیرد. البته معمولا تابع عدم شباهت را همان «تابع فاصله» (Distance Function) در نظر می‌گیرند. هدف از ایجاد خوشه‌ها،‌ تفکیک نقاط به گروه‌هایی است که بیشترین شباهت (کمترین فاصله) را در درون گروه‌ها و کمترین شباهت (بیشترین فاصله) را بین گروه‌ها داشته باشند.

تعلق نقاط به هر خوشه، توسط عمل «برچسب‌گذاری» (Labeling) انجام می‌شود. با توجه به انواع مختلف ویژگی‌ها برای نقاط، روش‌ها و الگوریتم‌های متنوعی نیز برای خوشه‌بندی وجود دارد. در نتیجه، ارزیابی نتایج خوشه‌بندی ملاکی است برای انتخاب الگوریتم مناسب. در این مطلب، شاخص‌های ارزیابی بیرونی معرفی و بررسی می‌شوند.

روش‌های ارزیابی نتایج خوشه‌بندی با معیارهای بیرونی

از آنجایی که «تحلیل خوشه‌بندی» (Clustering Analysis) یک روش «بدون نظارت» (Unsupervised) محسوب می‌شود، روش‌های ارزیابی و سنجش کارایی آن با روش‌های «نظارت شده» (Supervised) تفاوت دارند.

معمولا ارزیابی نتایج خوشه‌بندی براساس تابع فاصله و برچسب‌های تولید شده در تحلیل خوشه‌بندی انجام می‌شود. ارزیابی نتایج خوشه‌بندی می‌تواند از دو منظر بررسی شود: ارزیابی درونی (Internal Index) و  ارزیابی بیرونی (External Index)

منظور از ارزیابی درونی، بررسی دستیابی به اهداف خوشه‌بندی است. همانطور که گفته شد هدف از خوشه‌بندی، ایجاد دسته‌هایی با بیشترین شباهت درونی و کمترین شباهت بین دسته‌ها است. در نتیجه در رویکرد ارزیابی درونی خوشه‌بندی از ترکیب توابع فاصله یا شباهت برای خوشه‌ها استفاده می‌شود. برای مثال اگر داده‌ها یک بعدی باشند،‌ «تحلیل واریانس» (Analysis of Variance) می‌تواند نسبت میانگین تغییرات بین خوشه‌ها را به میانگین تغییرات درون خوشه‌ها اندازه‌گیری کرده و مشخص کند که آیا خوشه‌ها کاملا از یکدیگر جدا هستند یا خیر.

ولی در روش ارزیابی با معیارهای بیرونی، برای همه نقاط یک «برچسب واقعی» (Benchmark) وجود دارد که نشان دهنده تعلق نقاط به دسته‌ها است. معمولا به برچسب‌های واقعی، «استاندارد طلایی» (Gold Standard) نیز می‌گویند. از طرفی «برچسب‌های خوشه‌بندی» (Clustering Label) نیز کد مربوط به خوشه‌ای است که یک نقطه درون آن قرار دارد. در این متن مجموعه دسته‌ها را با $S={S_1,S_2,ldots,S_l}$ و خوشه‌ها را به صورت $C={C_1,C_2,ldots,C_k}$ نشان می‌دهیم.

در روش ارزیابی بیرونی، مطابقت این دو گونه برچسب انجام می‌پذیرد. باید توجه داشت که ممکن است کدهای برچسب‌های حاصل از خوشه‌بندی با برچسب‌های واقعی یکسان نباشند. به این معنی که برچسب واقعی ۱ برای یک نقطه بیانگر متعلق بودن آن به دسته شماره ۱ است در حالیکه ممکن است شماره برچسب برای این نقطه در خوشه‌بندی برابر با ۴ باشد.

مثال ۱

فرض کنید برای ۵ نقطه برچسب واقعی و حاصل از خوشه‌بندی در جدول زیر قرار داشته باشد. هر چند برچسب‌ها یکسان نیستند ولی هر دو سری برچسب به دسته یا خوشه‌های یکسانی اشاره دارند.

مقدار ۵ ۴ ۶ ۲ ۱
برچسب واقعی ۱ ۱ ۱ ۲ ۲
برچسب خوشه ۲ ۲ ۲ ۱ ۱

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

شاخص خلوص

یکی از ساده‌ترین شاخص‌های ارزیابی بیرونی در خوشه‌بندی، «شاخص خلوص» (Purity Index) است که درصد مطابقت بین برچسب‌های خوشه‌بندی و برچسب‌های واقعی را می‌سنجد. در این حالت برچسب هر خوشه با برچسب واقعی دسته‌ای که بیشترین اشتراک را دارد مطابقت پیدا کرده و تعداد نقاطی از خوشه که در دسته صحیح طبقه‌بندی شده‌اند شمارش می‌شوند. نسبت این تعداد به تعداد کل نقاط شاخص خلوص را می‌سازد و شکل محاسباتی آن به صورت زیر است:

$$Purity(S,C)=dfrac{displaystyle sum_{m} displaystylemax_{n} |S_mcap C_n|}{N}$$

باید توجه داشت که منظور از $|S_mcap C_n|$ تعداد نقاط مشترک از خوشه $C_n$ با دسته $S_m$ و N‌ نیز تعداد کل نقاط است. با توجه به شیوه محاسبه شاخص خلوص، مشخص است که حداکثر مقدار برای آن ۱ خواهد بود و این در زمانی اتفاق می‌افتد که برچسب‌های حاصل از خوشه‌بندی کاملا با برچسب‌های واقعی مطابقت داشته باشند. همینطور اگر هیچ برچسب خوشه‌ای با برچسب واقعی مطابقت نداشته باشد، این شاخص صفر می‌شود.

مثال ۲

فرض کنید برای ۵ نقطه، برچسب‌های واقعی و برچسب‌های حاصل از تحلیل خوشه‌بندی در جدول زیر قرار دارند.

به منطور محاسبه شاخص خلوص، جدول متقاطعی از برچسب‌ها ایجاد می‌کنیم و محاسبات را طبق فرمول انجام می‌دهیم. شاخص شفافیت برای خوشه‌های ایجاد شده برابر است با ۰.۶ یا ۶۰٪.

نکته: در این روش احتیاجی نیست که تعداد دسته‌ها با خوشه‌ها برابر باشد.

خصوصیات شاخص خلوص

سادگی در محاسبات: با توجه به شیوه محاسبه این شاخص، محاسبات طولانی برای بدست آوردن میزان مطابقت لازم نیست.

مستقل از تعداد خوشه‌ها: شاخص خلوص به تعداد خوشه‌ها توجه ندارد. در نتیجه نمی‌توان این شاخص را به عنوان معیاری برای سنجش مطابقت تعداد خوشه‌ها نیز در نظر گرفت.

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

شاخص رَند اصلاح شده

برای نشان دادن میزان شباهت بین دو شیوه برچسب‌گذاری می‌توان از «شاخص رَند» (Rand Index) استفاده کرد. این شاخص توسط دانشمند آمار ویلیام رند (William Rand) در سال ۱۹۷۱ در مقاله‌ای با عنوان «معیارهای هدف برای ارزیابی روش‌های خوشه‌بندی» (Objective criteria for the evaluation of clustering methods) معرفی شد.

برای محاسبه آن باید دو پارامتر را اندازه‌گیری کنیم:

A: تعداد زوج‌هایی که هم در خوشه‌ها و هم در دسته‌ها در کنار هم هستند. به بیان دیگر هم در خوشه‌ها دارای برچسب یکسانی هستند و هم برچسب دسته‌ها برای آن‌ها یکسان است.

‌B: تعداد زوج‌هایی که هم در خوشه‌ها و هم در دسته‌ها از یکدیگر جدا هستند. یعنی برچسب خوشه‌هایشان متفاوت است و البته برچسب دسته‌های متفاوتی نیز دارند.

مثلا در جدول اطلاعاتی مربوط به مثال ۲، زوج‌های $(۴,۵)$‌ در یک دست و در یک خوشه هستند. هرچند ممکن است شماره برچسب‌های متفاوتی برای خوشه‌ها یا دسته‌ها وجود داشته باشد. همچنین زوج $(۵,۲)$ نیز در دو دسته جدا قرار داشته و ضمناً برچسب خوشه‌های جداگانه نیز دارند.

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

$$Rand(S,C)=dfrac{A+B}{N choose 2}=dfrac{A+B}{N(N-1)/2}$$

مثال ۳

اگر برای داده‌های مربوط به مثال ۲ شاخص Rand را محاسبه کنیم، مطابقت برچسب‌های واقعی و خوشه‌ای را به صورت زیر می‌توان مشاهده کرد.

$$Rand (S,C)=0.6$$

اگر خوشه‌ها مطابق با دسته‌ها ایجاد شده باشند، شاخص رند برابر با ۱ خواهد بود. ولی اگر خوشه‌بندی به صورت تصادفی ایجاد شده باشد، دلیلی ندارد که مقدار این شاخص برابر با صفر باشد. برای رفع این مشکل از «شاخص رند اصلاح شده» (Adjusted Rand Index) استفاده می‌شود. این شاخص را به صورت ARI‌ نشان داده و به شکل زیر محاسبه می‌شود:

$$ARI(S,C)=dfrac{Rand(S,C)-E(Rand(S,C))}{max (Rand (S,C))-E(Rand(S,C))}$$

منظور از E نیز امید-ریاضی شاخص رند است.

خصوصیات شاخص رند اصلاح شده

حدود مقدارها: ARI‌ مقداری بین ۱ و ۱- خواهد بود. در حالتی که ARI=1 باشد، مطابقت کامل بین برچسب‌های واقعی و خوشه‌ای وجود دارد و در مقابل اگر مقدار این شاخص برابر با ۱- باشد نشانگر برچسب‌گذاری تصادفی در حین خوشه‌بندی است.

  • شاخص کارا برای مقایسه‌ چندین روش: از آنجایی که این شاخص به توافق بین برچسب‌ها تکیه دارد، می‌توان از آن برای مقایسه دو روش خوشه‌بندی نیز استفاده کرد. برای مثال می‌توان مطابقت بین شیوه خوشه‌بندی و برچسب‌گذاری در الگوریتم k-میانگین را با روش فازی c-means‌ بررسی کرد.
  • بدون وابستگی به تعداد خوشه‌ها: با توجه به شیوه محاسبه این شاخص، تفاوت بین تعداد خوشه‌ها و دسته‌ها نیز در آن لحاظ شده است.
  • تقارن در ARI: اگر جای دسته‌ها و خوشه‌ها عوض شود، شاخص ARI تعییری نمی‌کند. به این معنی که $ARI(S,C)=ARI(C,S)$.
  • عدم حساسیت به تغییر برچسب‌ها: اگر برچسب‌های خوشه‌ها تغییر کند در نتیجه ARI تغییری بوجود نمی‌آید. برای مثال اگر همه برچسب‌های ۱ در خوشه‌بندی به برچسب ۲ تبدیل شوند، حاصل ARI‌ تغییری نخواهد کرد.

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

فرض کنید در اینجا $n_{ij}displaystyle $ تعداد عناصر مشترک در دسته i و خوشه j باشد. همچنین $a_i$‌ نیز مجموع مقدارهای $n_{ij}$ برای سطر iام و $b_j$ نیز جمع مقدارهای $n_{ij}$ در ستون jام باشد. جدول متقاطع زیر تعداد عناصر مشترک در بین دسته‌ها و خوشه‌ها را نشان می‌دهد.

جدول متقاطع خوشه‌ها و دسته‌ها

حال براساس محاسبه زیر می‌توان شاخص رند اصلاح شده را بدست آورد:

مثال ۴

با توجه به مثال ۲ مقدار شاخص اصلاح شده رند ۰.۰۹۰۹ خواهد بود که در مقایسه با مقدار شاخص رند کاملا متفاوت است. همینطور که دیده می‌شود، در این حالت عدم مطابقت تعداد خوشه‌ها با دسته‌ها در شاخص بسیار تاثیر گذار است.

$$dfrac{1-0.8}{3-0.8}=0.09090$$

 شاخص فولکز- مالوز