اعتبارسنجی سایه‌نما (خوشه‌بندی)

اعتبارسنجی سایه‌نما یا سیلوئت (به انگلیسی: silhouette) به روشی برای تفسیر و صحت ثبات در خوشه‌بندی اشاره دارد. این تکنیک یک نمایش گرافیکی مختصر از میزان طبقه‌بندی هر یک از اشیا ارائه می‌دهد.

مقدار سیلوئت معیار میزان شباهت یک شی به خوشه خودش (انسجام) در مقایسه با خوشه‌های دیگر (جداسازی شده) است. محدوده سیلوئت از 1− تا ۱+ است، که در آن مقدار زیاد نشان می‌دهد که شی به خوبی با خوشه خود مطابقت دارد و با خوشه‌های همسایه همسان نیست. اگر بیشتر اشیا از مقدار بالایی برخوردار باشند، ساختار خوشه بندی مناسب است. اگر بسیاری از نقاط دارای مقدار کم یا منفی باشند، در این صورت ممکن است ساختار خوشه بندی دارای خوشه‌های بسیار زیاد یا بسیار کم باشد.

سیلوئت را می‌توان با هر معیار سنجش فاصله، مانند فاصله اقلیدسی یا فاصله منهتن، محاسبه کرد.

تعریف

نمودار نشان دهندهٔ مقدار Silhouette برای سه نوع از حیوانات از dataset باغ وحش ارائه شده توسط مجموعه داده کاوی Orange است. در پایین نمودار، سیلوئت دلفین و گرازماهی را به عنوان دادهٔ پرت از گروه پستانداران شناسایی می‌کند.

فرض کنید داده‌ها به $k$ خوشه از طریق هر تکنیکی مانند خوشه‌بندی کی-میانگین در آن خوشه بندی شده‌اند

برای داده‌ای مانند نقطهٔ $i\in C_{i}$ (نقطه $i$ متعلق به خوشه $C_{i}$)، قرار دهید:

$a(i)={\frac {1}{|C_{i}|-1}}\sum _{j\in C_{i},i\neq j}d(i,j)$

میانگین فاصله بین دادهٔ نقطه $i$ و سایر نقاط داده در همان خوشه، که در آن $d(i,j)$ فاصله بین نقاط دادهٔ $i$ و $j$ در خوشه $C_{i}$ (تقسیم بر $|C_{i}|-1$ را انجام می‌دهیم زیرا فاصله$d(i,i)$ را در جمع وارد نمی‌کنیم) ما می‌توانیم $a(i)$ را به عنوان اینکه چه اندازه $i$ به خوبی به خوشه خود اختصاص داده شده‌است تفسیر کنیم (هرچه مقدار کوچکتر باشد ، انتساب بهتر است).

سپس میانگین عدم شباهت نقطه $i$ را به بعضی خوشه‌های $C_{k}$ به عنوان میانگین فاصله از $i$ به تمام نقاط در $C_{k}$ تعریف می‌کنیم (که در آن $C_{k}\neq C_{i}$)

برای هر نقطهٔ داده $i\in C_{i}$ ، اکنون تعریف می‌کنیم

$b(i)=\min _{k\neq i}{\frac {1}{|C_{k}|}}\sum _{j\in C_{k}}d(i,j)$

کوچکترین بودن (از این رو $\min$ عملگر در فرمول) میانگین فاصله $i$ با همه نقاط درخوشه‌های دیگر، که $i$ عضو آنها نیست. خوشه ای با کوچکترین میانگین عدم شباهت «خوشه همسایه» ی $i$ نامیده می‌شود، زیرا این بهترین خوشه مناسب بعدی برای نقطه $i$ است.

اکنون (مقدار) سیلوئت یک نقطه داده $i$ تعریف می‌کنیم

$s(i)={\frac {b(i)-a(i)}{\max\{a(i),b(i)\}}}$ ، اگر $|C_{i}|>1$

و

$s(i)=0$ ، اگر $|C_{i}|=1$

که می‌توان به صورت زیر نوشت:

$s(i)={\begin{cases}1-a(i)/b(i),&{\mbox{if }}a(i)<b(i)\\0,&{\mbox{if }}a(i)=b(i)\\b(i)/a(i)-1,&{\mbox{if }}a(i)>b(i)\\\end{cases}}$

از تعریف بالا مشخص می‌شود که

$-1\leq s(i)\leq 1$

همچنین، توجه داشته باشید که مقدار $s(i)$ برای خوشه‌هایی با اندازه مساوی ۱ مقدار عددی ۰ است. این محدودیت برای جلوگیری از افزایش قابل توجه تعداد خوشه‌ها اضافه شده‌است.

برای $s(i)$ نزدیک به ۱ ما نیاز به $a(i)\ll b(i)$ داریم. از آنجایی که $a(i)$ یک معیار چگونگی عدم شباهت $i$ با خوشهٔ خودش است، پس مقدار کوچک آن به معنی مطابقت خوب آن است. بعلاوه بزرگی $b(i)$ حاکی از آن است که $i$ با خوشه‌های همسایه مطابقت خوبی نداشته‌است. در نتیجه $s(i)$ نزدیک به یک به معنی خوشه بندی مناسب است. اگر $s(i)$ نزدیک به منفی یک باشد با همان منطق ما می‌بینیم که $i$مناسب تر خواهد بود اگر در خوشه همسایه، خوشه بندی شده باشد. یک $s(i)$ نزدیک به صفر به این معنی است که داده در مرز طبیعی دو خوشه است.

میانگین ای $s(i)$که روی همه نقاط یک خوشه بسته می‌شود، معیاری از این است که چه مقدار نقاط دسته‌بندی شده در یک خوشه به هم نزدیک هستند؛ بنابراین میانگین بر روی همهٔ داده‌های کل دیتاست به عنوان معیاری از میزان مناسب بودن داده‌های خوشه بندی شده‌است. اگر تعداد خوشه‌ها بسیار زیاد یا بسیار کم باشد، که این زمانی اتفاق می‌افتد که یک انتخاب بد برای k در الگوریتم خوشه بندی استفاده می‌شود، (به عنوان مثال: خوشه‌بندی کی-میانگین)، بعضی از خوشه‌ها معمولاً سیلوئت‌های باریک تری نسبت به بقیه نشان می‌دهند؛ بنابراین می‌توان از نمودارها، میانگین و ابزارهای سیلوئت برای تعیین تعداد طبیعی خوشه‌ها در یک مجموعه داده استفاده کرد. همچنین می‌توان با مقیاس گذاری مجدد داده‌ها با استفاده از وزن ویژگی‌های خاص خوشه، به حداکثر رساندن سیلوئت در تعداد صحیح خوشه‌ها را افزایش داد.

کافمن و همکاران واژه ضریب سیلوئت را برای حداکثر رساندن مقدار میانگین$s(i)$ بر روی همهٔ داده‌های کل دیتاست معرفی کرده‌اند.

$SC=\max _{k}{\tilde {s}}\left(k\right)$

بطوریکه ${\tilde {s}}\left(k\right)$ نشاندهندهٔ میانگین $s(i)$ را بر روی همهٔ داده‌های کل دیتاست برای یک تعداد خاصی از خوشه $k$هااست.

جستارهای وابسته

• شاخص دیویس – بولدین
• کی-واسط
• تعیین تعداد خوشه‌ها در یک مجموعه داده
• خوشه‌بندی
• خوشه‌بندی کی-میانگین