«خوشه‌بندی» (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\}$$ نشان می‌دهیم.

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

مثال ۱

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

مقدار 5 4 6 2 1
برچسب واقعی 1 1 1 2 2
برچسب خوشه 2 2 2 1 1

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

شاخص خلوص

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

$$Purity(S,C)=\dfrac{\displaystyle \sum_{m} \displaystyle\max_{n} |S_m\cap C_n|}{N}$$

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

مثال 2

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

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

نکته: در این روش احتیاجی نیست که تعداد دسته‌ها با خوشه‌ها برابر باشد. به ماتریس بالا که چنین وضعیتی را نشان می‌دهد دقت کنید.

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

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

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

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

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

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

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

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

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

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

حال برای محاسبه شاخص رند کافی است که حاصل جمع 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ام باشد. جدول متقاطع زیر تعداد عناصر مشترک در بین دسته‌ها و خوشه‌ها را نشان می‌دهد.

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

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

مثال ۴

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

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

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

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

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

  • مثبت صحیح: اگر زوجی از مشاهدات که در یک دسته هستند، در یک خوشه نیز قرار بگیرند، نتیجه خوشه‌بندی را برای این زوج «مثبت صحیح« (True Positive) می‌نامیم. مثبت صحیح را با TP نیز نشان می‌دهند.
  • منفی صحیح: اگر زوجی از مشاهدات که در دو دسته مجزا قرار دارند، در دو خوشه مجزا نیز جای گیرند،‌ نتیجه خوشه‌بندی را برای این زوج «منفی صحیح» (True Negative) می‌نامیم. منفی صحیح را با TN نیز نشان می‌دهند.
  • مثبت کاذب:  اگر زوجی از مشاهدات که در دو دسته مجزا قرار دارند، در یک خوشه جای گیرند، نتیجه خوشه‌بندی برای این زوج «مثبت کاذب» (False Positive) است. مثبت کاذب را با FP‌ نیز نشان می‌دهند.
  •  منفی کاذب: اگر زوجی از مشاهدات که در یک دسته قرار دارند به اشتباه در دو خوشه قرار گیرند،‌ نتیجه خوشه‌بندی برای این زوج «منفی کاذب» (False Negative) است. منفی کاذب را با FN‌ نیز نشان می‌دهند.

جدول زیر که وظیفه مقایسه بین تعداد نتایج خوشه‌بندی توسط الگوریتم و دسته‌بندی اصلی را به عهده دارد، به «ماتریس درهم‌ریختگی» (Confusion Matrix) شهرت دارد که توجه به آن به درک و شیوه محاسبه اشخص فولکر-مالوز و اصطلاحات گفته شده، کمک می‌کند.

نتیجه خوشه‌بندی برای زوج $$(x,y)$$ دسته‌بندی واقعی
در یک دسته در دو دسته مجزا
خوشه‌بندی در یک خوشه TP FP
در دو خوشه مجزا FN TN

حال اگر تعداد زوج‌های مثبت صحیح را با $$|TP|$$، تعداد مثبت کاذب را با $$|FP|$$ و تعداد منفی کاذب را با $$|FN|$$ نشان بدهیم، شاخص «فولکز- مالوز» (Fowlkes-Mallows) که با FMI نشان داده می‌شود به صورت زیر محاسبه می‌شود:

$$FMI(S,C)=\dfrac{|TP|}{[(|TP|+|FP|)(|TP|+|FN|)]^\tfrac{1}{2}}$$

 مقدار این شاخص نیز بین ۰ تا ۱ تغییر می‌کند. هر چه FMI به ۱ نزدیکتر باشد، مطابقت بین دو شیوه برچسب‌گذاری بیشتر است. در صورتی که این شاخص به صفر برسد، خوشه‌بندی به صورت تصادفی انجام شده.

مثال 5

با توجه به مثال ۱ و ۲ شاخص فولکز-مالوز بر اساس اطلاعات زیر قابل محاسبه است.

TP=1 FP=3
FN=1 TN=5

$$|TP|= 1, \;\;\;\; |FP|=3, \;\;\;|FN|=1$$

$$FMI=\dfrac{1}{[(1+3)(1+1)]^\tfrac{1}{2}}=\dfrac{1}{2\sqrt{2}}=0.3535$$

اندازه F

همانطور که دیده شده، استفاده از مفاهیم مثبت کاذب، مثبت صحیح، منفی کاذب و منفی صحیح در محاسبه شاخص ارزیابی نتایج خوشه‌بندی اهمیت زیادی دارد. با توجه به این مفاهیم می‌توان شاخص رند را به صورت زیر نیز محاسبه کرد:

$$Rand (S,C)=\dfrac{|TP|+|TN|}{|TP|+|FP|+|TN|+|FN|}$$

در این حالت وزن یا اهمیت مربوط به منفی کاذب (FN) یا مثبت کاذب (FP) در محاسبه شاخص یکسان است. ولی در «اندازه F» ($$F\;\; Measure$$) می‌توان وزن‌ آن‌ها را با پارامتر $$\beta$$ تغییر داد. اگر P و R را به صورت زیر تعریف کنیم:

$$P=\dfrac{|TP|}{|TP|+|FP|},\;\;\;\;\;R=\dfrac{|TP|}{|TP|+|FN|}$$

آنگاه شاخص F را به ازاء $$\beta \neq 0$$ به شکل زیر محاسبه می‌شود:

$$F_{\beta}=\dfrac{(\beta^2+1)PR}{\beta^2P+R}$$

مثال 6

اندازه $$F_2$$ برای داده‌های مربوط به مثال ۲ برابر است با:

$$P=\dfrac{1}{1+3}=\frac{1}{4},\;\;\;\;R=\dfrac{1}{1+1}=\frac{1}{2},\;\;\;\;$$

$$F_{2}=\dfrac{(2^2+1)(\frac{1}{4}\times \frac{1}{2})}{(2^2\times \frac{1}{4})+\frac{1}{2}}=0.8333$$

با این کار وزن پارامتر FN بیشتر از FP در نظر گرفته شده است.

اگر به یادگیری مباحث مشابه این مطلب علاقه‌مند هستید، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

«آرمان ری‌بد» دکتری آمار در شاخه آمار ریاضی دارد. از علاقمندی‌های او، یادگیری ماشین، خوشه‌بندی و داده‌کاوی است و در حال حاضر نوشتارهای مربوط به آمار و یادگیری ماشین را در مجله فرادرس تهیه می‌کند.

بر اساس رای 3 نفر

آیا این مطلب برای شما مفید بود؟

4 نظر در “روش‌ های ارزیابی نتایج خوشه‌ بندی (Clustering Performance) — معیارهای بیرونی (External Index)

  • سلام. ممنونم از مطالبتون
    خب میدونیم که خوشه بندی از نوع Unsupervised و معنی اش اینه که ما برای داده ها label نداریم. حالا پس این موضوع برچسب واقعی (Benchmark یا gold standard) دیگه چیه؟ یعنی اگه داده ها label دارند و قراره از این labelها استفاده بشه (حتی برای ارزیابی الگوریتم) میشه supervised و نیازی به clustering نداریم

    یا اگه من بد فهمیدم خواهش میکنم راهنمایی بفرمایید

    1. سلام و درود
      از اینکه همراه مجله فرادرس هستید بسیار سپاسگزاریم.
      آنچه به عنوان ایراد به مشخص کردن برچسب فرمودید، کاملا صحیح است. ولی توجه داشته باشید که در نظر گرفتن برچسب‌های واقعی فقط زمانی مورد نظر است که بخواهیم یک روش خوشه‌‌بندی را با روش دیگر مقایسه کنیم و کارایی هر یک را بسنجیم. در نتیجه براساس مشاهدات برچسب دار، سعی در پیدا کردن بهترین الگوریتم می‌کنیم. در اینجا خوشه‌بندی هدف نیست بلکه ارزیابی روش خوشه‌بندی موضوع بحث است.
      به این ترتیب مجموعه داده‌ای که از قبل برچسب‌گذاری شده را مبنا قرار داده و مشخص می‌کنیم که نتیجه روش خوشه‌بندی (بدون در نظر گرفتن برچسب‌ها) چقدر با برچسب‌های واقعی همخوانی دارد.
      به همین دلیل شاخص‌های ارائه شده از نوع بیرونی هستند یعنی با الگویی خارج از خوشه‌ها، الگوریتم سنجیده می‌شود.
      اما استفاده از معیارهای درونی، بدون در نظر گرفتن برچسب عمل می‌کند و فقط ویژگی‌ها اصلی بهینه برای خوشه‌ها را در نظر می‌گیرد.

      شاد و تندرست باشید.

  • خیلی خوب توضیح داده بودین
    سپاسگزارم
    اگر براتون مقدره ممکنه معیار ارزیابی Bcubed رو هم با مثال شرح بدین و فرق آن را با f-measure بفرمایید

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *