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

اعتبارسنجی سایه‌نما یا سیلوئت (به انگلیسی: 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$هااست.

مثال امتیاز سایه نما خوشه بندی در پایتون

پکیج‌های پایتون که روش‌های مختلفی برای محاسبه امتیاز خوشه بندی در اختیار ما قرار می‌دهند:

• Silhoute_score (sklearn.metrics) در هر دیتاست برای اندازه‌گیری میانگین امتیاز سایه نما خوشه بند برای هر سمپل در هر خوشه به کار می‌رود.
• Silhpute_samples (sklearn.metrics) برای هر سمپل در خوشه‌های مختلف امتیاز سایه بند را محاسبه می‌کند.

محاسبه امتیازبندی خوشه نما در k همسایه مجاور(k-means cluster) با n دسته

در زیر قطعه کدی برای محاسبه امتیاز سایه نما در پایتون برای الگوریتم k-means با n = ۳ (تعداد خوشه‌ها برابر ۳) در دیتاست IRIS نوشته شده.

from sklearn import datasets
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
## Load IRIS dataset
iris = datasets.load_iris()
X = iris.data
y = iris.target
## Instantiate the KMeans models
km = KMeans(n_clusters=3, random_state=42)
# Fit the KMeans model
km.fit_predict(X)
# Calculate Silhoutte Score
score = silhouette_score(X, km.labels_, metric='euclidean')
# Print the score
print('Silhouetter Score: %.3f' % score)

با اجرای کد بالا به امتیاز ۰٫۵۵ می‌رسیم.

روشی برای یافتن بهترین مقدار k با استفاده از امتیاز سایه نما

در ابتدا برای این کار از پکیج yellowBrick برای نمایش نمودارهای سایه نما برای الگوریتم k—means با مقادیر مختلف خوشه‌ها 2,3,4,5.

from yellowbrick.cluster import SilhouetteVisualizer
import matplotlib.pyplot as plt

fig, ax = plt.subplots(2, 2, figsize=(15,8))
scores = []
for i in [2, 3, 4, 5]:
    '''
    Create KMeans instance for different number of clusters
    '''
    km = KMeans(n_clusters=i, init='k-means++', n_init=10, max_iter=100, random_state=42)
    # Fit the KMeans model
    km.fit_predict(X)
    # Calculate Silhoutte Score
    score = silhouette_score(X, km.labels_, metric='euclidean')
    scores.append(score)
    q, mod = divmod(i, 2)
    '''
    Create SilhouetteVisualizer instance with KMeans instance
    Fit the visualizer
    '''
    visualizer = SilhouetteVisualizer(km, colors='yellowbrick', ax=ax[q-1][mod])
    visualizer.fit(X)

print(max(scores), scores.index(max(scores)))

با اجرای کد بالا به ۴ نمودار زیر می‌رسیم که به ترتیب از چپ بالا به سمت راست پایین برای تعداد خوشه‌های ۲و ۳و۴و۵ می‌باشند.

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

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