اعتبارسنجی خوشهبندی

Source
import numpy as np
import matplotlib.pyplot as plt
plt.rcParams['figure.dpi'] = 120اعتبارسنجی خوشهبندی¶
محمود امینطوسی، پاییز ۱۴۰۵
گروه علوم کامپیوتر، دانشگاه فردوسی مشهد
این صفحه فصل ۱۷ از zaki2020data را دنبال میکند: Clustering Validation.
درآمدی بر اعتبارسنجی خوشهبندی¶
اعتبارسنجی خوشهبندی کیفیت یک خوشهبندی را میسنجد. هر الگوریتمی یک افراز از داده برمیگرداند؛ پرسش این است که آن افراز چقدر خوب است و دو افراز نامزد را چگونه میتوان با هم سنجید. سنجهها در سه خانواده میگنجند:
سنجههای بیرونی: از اطلاعات بیرونی، یعنی برچسبهای حقیقتمبنا، بهره میبرند.
سنجههای درونی: فقط از داده و نتیجهٔ خوشهبندی بهره میبرند.
سنجههای نسبی: دو خوشهبندی از یک داده را با هم میسنجند، بدون هیچ حقیقتمبنایی.
اهداف یادگیری. در پایان باید بتوانید
جدول توافقی یک خوشهبندی را در برابر حقیقتمبنا بسازید و بخوانید؛
خلوص، دقت/بازآوری/F، بیشینهٔ تطبیق، جاکارد، رند، ARI و NMI را حساب و تفسیر کنید و بگویید هر کدام چه چیزی را نادیده میگیرد؛
توضیح دهید چرا دقت را نمیتوان روی برچسبهای خوشه به کار برد؛
از سنجههای درونی (سیلوئت، SSE، شکاف) بهره ببرید و بگویید چرا هیچکدام «تعداد واقعی» خوشهها را مشخص نمیکند؛
امتیاز بیشینهٔ تطبیق را بهعنوان یک مسئلهٔ تخصیص ببینید.
نمادگذاری¶
زکی را برای تعداد خوشهها و را برای تعداد کلاسهای حقیقتمبنا به کار میبرد. این صفحه همان حروف را نگه میدارد تا فرمولها با کتاب بخوانند؛ توجه داشته باشید که صفحههای k-means این درس را برای تعداد خوشهها به کار میبرند. در همهٔ فرمولهای زیر تعداد نقطههای خوشهٔ را میشمارد که به کلاس تعلق دارند، و تعداد نقطههاست.
سنجههای بیرونی¶
سنجههای بیرونی فرض میکنند خوشهبندی درست یا حقیقتمبنا پیش از هر چیز معلوم است و همان برای داوری یک خوشهبندی دادهشده به کار میرود.
فرض کنید مجموعهدادهای با نقطه در فضایی -بعدی است که به خوشه افراز شده. بگذارید عضویت یا برچسب حقیقتمبنای هر نقطه را نشان دهد.
خوشهبندی حقیقتمبنا چنین داده میشود:
که در آن خوشهٔ همهٔ نقطههای با برچسب را در بر دارد، یعنی
به افراز حقیقتمبنا و به هر یک بخش (کلاس) میگوییم.
بگذارید خوشهبندی همان مجموعهداده به خوشه را نشان دهد که با الگوریتمی خوشهبندی به دست آمده، و برچسب خوشهٔ باشد.
سنجههای داوری بیرونی میکوشند اندازهای را بگیرند که نقطههای یک بخش در یک خوشه بیفتند، و نقطههای بخشهای مختلف در خوشههای مختلف گروه شوند.
همهٔ سنجههای بیرونی به جدول توافقی یعنی تکیه میکنند که خوشهبندی و افراز حقیقتمبنای پدید میآورند، و چنین تعریف میشود:
شمارش تعداد نقطههایی است که هم در خوشهٔ و هم در بخش حقیقتمبنای هستند.
بگذارید تعداد نقطههای خوشهٔ و تعداد نقطههای بخش باشد. جدول توافقی را میتوان در زمان از و ساخت: برچسب بخش و خوشهٔ هر نقطه ، یعنی و ، را ببینید و شمارندهٔ متناظر را یکی بیفزایید — اندیس اول برچسب خوشه و اندیس دوم برچسب کلاس است، پس سطرهای خوشهها و ستونهایش کلاسها هستند.
Source
import pandas as pd
def display_contingency_table_pandas(table, class_names=None, cluster_names=None):
r, k = table.shape
if class_names is None:
class_names = [f"Class {j}" for j in range(k)]
if cluster_names is None:
subscript = "₀₁₂₃₄₅₆₇₈₉"
cluster_names = [f"C{subscript[i]}" for i in range(r)]
df = pd.DataFrame(table, index=cluster_names, columns=class_names)
display(df.style
.set_properties(**{'text-align': 'center'})
.set_table_styles([
{'selector': 'th',
'props': [('text-align', 'center'),
('background-color', '#f2f2f2'),
('border', '1px solid #ccc')]},
{'selector': 'td',
'props': [('border', '1px solid #ccc')]},
]))import numpy as np
def compute_contingency_table(cluster_labels, true_labels):
"""Contingency table of a clustering against the ground truth.
Returns an ``(r, k)`` integer matrix: rows index clusters, columns index classes,
so ``table[i, j]`` is the number of points of cluster ``i`` in class ``j``.
"""
unique_classes, class_map = np.unique(true_labels, return_inverse=True)
unique_clusters, cluster_map = np.unique(cluster_labels, return_inverse=True)
table = np.zeros((len(unique_clusters), len(unique_classes)), dtype=int)
np.add.at(table, (cluster_map, class_map), 1)
return tableنخستین نقطهٔ مرجع: یک خوشهبندی بیعیب¶
پیش از آنکه به چیزی که خراب میشود نگاه کنیم، به یک خط پایه نیاز داریم. جدول زیر وقتی به دست میآید که هر خوشه دقیقاً با یک کلاس حقیقتمبنا بخواند. ماتریس توافقی قطری است: هر درایهٔ بیرون قطری صفر است.
این تنها حالتی است که در آن مقدار «آرمانی» هر سنجهٔ بیرونی معقول به دست میآید (یک برای خلوص، NMI و ARI). هر مثال دیگری در این صفحه را باید با همین خط پایه سنجید.
# Example A — perfect clustering
true_labels = np.array([0, 0, 0, 1, 1, 1, 2, 2, 2])
cluster_labels = np.array([0, 0, 0, 1, 1, 1, 2, 2, 2])
table = compute_contingency_table(cluster_labels, true_labels)
display_contingency_table_pandas(table)یک خوشهبندی خوب با خطایی کوچک و متقارن¶
بیشتر خوشهبندیهای واقعی تقریباً درستاند. اینجا C₀ هنوز کاملاً خالص است، ولی C₁ و C₂ هر کدام یک نقطه را با هم عوض کردهاند: یک نقطه از کلاس T₁ در C₂ افتاده و یکی از T₂ در C₁.
جدول تقریباً قطری است، پس خلوص، NMI و ARI همگی نزدیک به یک ولی کمی کمتر خواهند بود. این همان حالت معمول «کمی ناکامل» است که بیشتر الگوریتمهای عملی تولید میکنند.
# Example B — almost perfect, one swap
true_labels = np.array([0, 0, 0, 1, 1, 1, 2, 2, 2])
cluster_labels = np.array([0, 0, 0, 1, 1, 2, 2, 2, 1])
table = compute_contingency_table(cluster_labels, true_labels)
display_contingency_table_pandas(table)شناسههای خوشه برچسباند، نه ترتیب¶
افراز زیر دقیقاً همان افراز مثال B است؛ فقط شناسههای خوشهها جای هم عوض شدهاند. C₁ در این مثال همان است که پیشتر C₂ بود، و برعکس.
جدول همان جدول B است با سطرهای جابهجاشده — و هر سنجهٔ بیرونی همان مقدار عددی را میدهد. دلیلش این است که همهٔ سنجههای بیرونی باید نسبت به جایگشت شناسههای خوشه ناوردا باشند: عددهای 0، 1، 2 که KMeans.labels_ برمیگرداند فقط ناماند، نه رتبهبندی.
# Example C — same partition as B, cluster ids relabelled
true_labels = np.array([0, 0, 0, 1, 1, 1, 2, 2, 2])
cluster_labels = np.array([1, 1, 1, 2, 2, 0, 0, 0, 2])
table = compute_contingency_table(cluster_labels, true_labels)
display_contingency_table_pandas(table)یک خوشهبندی ضعیف با پراکندگی متقارن¶
اکنون خوشهبندی اصلاً نزدیک حقیقتمبنا نیست. هر خوشه نقطههایی از دو کلاس مختلف دارد و هر کلاس میان دو خوشه تقسیم شده است. جدول در هر سطر و هر ستون چند درایهٔ ناصفر دارد، ولی هیچ سطر یا ستونی «خالص» نیست.
خلوص حدود ۰٫۵ خواهد بود و NMI و ARI بهروشنی زیر یک. توجه کنید که هنوز اندکی سیگنال هست: درایههای قطری صفر نیستند، پس خوشهبندی تصادفی نیست — فقط ضعیف است.
# Example D — weak clustering, scattered table
true_labels = np.array([0, 0, 1, 1, 2, 2])
cluster_labels = np.array([0, 1, 1, 2, 2, 0])
table = compute_contingency_table(cluster_labels, true_labels)
display_contingency_table_pandas(table)یک حالت فریبنده: جدولی کاملاً یکنواخت¶
این مثال جدول توافقیای دارد که همهٔ درایههایش دقیقاً برابرند. هر خوشه از هر کلاس یک نقطه دارد و هر کلاس بهطور یکنواخت روی همهٔ خوشهها پخش شده است.
این آموزندهترین حالت صفحه است. جدول مرتب و منظم به نظر میرسد، ولی هیچ اطلاعاتی ندارد: دانستن اینکه نقطهای به کدام خوشه افتاده، هیچ چیزی دربارهٔ کلاس واقعیاش نمیگوید.
خلوص دقیقاً 1/3 است و NMI و ARI دقیقاً صفر — همان مقدارهایی که یک تخصیص کاملاً تصادفی میدهد. منظم بودن جدول با سودمند بودن خوشهبندی یکی نیست.
# Example E — deceptive, uniform contingency table
true_labels = np.array([0, 0, 0, 1, 1, 1, 2, 2, 2])
cluster_labels = np.array([0, 1, 2, 1, 2, 0, 2, 0, 1])
table = compute_contingency_table(cluster_labels, true_labels)
display_contingency_table_pandas(table)وقتی تعداد خوشهها با تعداد کلاسها فرق دارد¶
همهٔ مثالهای تا اینجا داشتند: به تعداد کلاسهای حقیقتمبنا خوشه. ولی K-means با یک K ثابت اجرا میشود که کاربر برمیگزیند، و هیچ تضمینی نیست K با تعداد کلاسهای واقعی بخواند.
در مثال زیر حقیقتمبنا سه کلاس دارد ولی الگوریتم چهار خوشه ساخته — یکی از کلاسها را به دو تکه بیشافراز کرده است. پس جدول توافقی مربع نیست و هیچ «دقت» سادهای قابل محاسبه نیست: تناظر یکبهیک میان شناسههای خوشه و کلاس وجود ندارد.
خلوص همچنان محاسبهشدنی و معنادار است: برای هر خوشه میپرسد چقدر خالص است و بعد میانگین میگیرد. ولی یک خوشهبندی بیشافراز خلوصی بهطور مشکوک بالا میگیرد، چون ساختن خوشههای کوچک و خالص آسان است. NMI و ARI این را درست جریمه میکنند، و همین دلیل ترجیحشان در عمل است وقتی K از پیش معلوم نیست.
# Example F — k = 4 clusters vs r = 3 classes (over-segmentation)
# The 3 points of class T₀ are split across two clusters: C₀ and C₃.
true_labels = np.array([0, 0, 0, 1, 1, 1, 2, 2, 2])
cluster_labels = np.array([0, 0, 3, 1, 1, 1, 2, 2, 2])
table = compute_contingency_table(cluster_labels, true_labels)
display_contingency_table_pandas(table)حالت برعکس: خوشههای بسیار کم¶
اینجا وضعیت برعکس است: الگوریتم با اجرا شده، ولی سه کلاس واقعی داریم. دو تا از آنها در یک خوشه ادغام شدهاند.
جدول توافقی اکنون ماتریسی است که یک سطرش نقطههایی از دو کلاس مختلف دارد. خلوص بیدرنگ میافتد، چون آن سطر دو درایهٔ ناصفر با اندازهٔ نزدیک به هم دارد. پنهانکردن کمافرازی بسیار سختتر از بیشافرازی است.
# Example G — k = 2 clusters vs r = 3 classes (under-segmentation)
# Classes T₀ and T₁ have been merged into a single cluster C₀.
true_labels = np.array([0, 0, 0, 1, 1, 1, 2, 2, 2])
cluster_labels = np.array([0, 0, 0, 0, 0, 0, 1, 1, 1])
table = compute_contingency_table(cluster_labels, true_labels)
display_contingency_table_pandas(table)ساختن کارای جدول توافقی با np.add.at¶
هنگام پیادهسازی سنجههای اعتبارسنجی خوشهبندی، ساختن جدول توافقی گام کلیدی است. یک راه کارا در NumPy استفاده از np.add.at است. این روش هنگام وجود اندیسهای تکراری، انباشت درست شمارندهها را تضمین میکند.
چرا np.add.at؟¶
برخلاف افزایش اندیسمحور ساده، مانند:
contingency_table[cluster_map, class_map] += 1نمایهسازی فانتزی NumPy یک رونوشت موقت میسازد، یعنی بهروزرسانی اندیسهای تکراری ممکن است درست انباشته نشود. در عوض np.add.at تغییر درجا را تضمین میکند:
np.add.at(contingency_table, (cluster_map, class_map), 1)مثال: تفاوت نمایهسازی مستقیم و np.add.at¶
مثال زیر نشان میدهد np.add.at اندیسهای تکراری را درست مدیریت میکند در حالی که نمایهسازی مستقیم ممکن است شکست بخورد:
import numpy as np
def compute_contingency_table_direct(cluster_labels, true_labels):
"""Same table, built with direct indexed incrementation."""
unique_classes, class_map = np.unique(true_labels, return_inverse=True)
unique_clusters, cluster_map = np.unique(cluster_labels, return_inverse=True)
table = np.zeros((len(unique_clusters), len(unique_classes)), dtype=int)
table[cluster_map, class_map] += 1 # a temporary copy is written back: duplicates are lost
return tableimport numpy as np
true_labels = np.array([0, 0, 1, 1, 1, 2, 2, 2, 2])
cluster_labels = np.array([0, 1, 1, 1, 1, 2, 2, 2, 2])
contingency_table_at = compute_contingency_table(cluster_labels, true_labels)
contingency_table_direct = compute_contingency_table_direct(cluster_labels, true_labels)
print("Using direct indexing:")
display_contingency_table_pandas(contingency_table_direct)
print("\nUsing np.add.at:")
display_contingency_table_pandas(contingency_table_at)Using direct indexing:
Using np.add.at:
۱. خلوص¶
خلوص میسنجد هر خوشه چقدر «خالص» است، با کسر نقطههای کلاس اکثریت:
که در آن:
= تعداد کل نقطهها
= تعداد خوشهها
= تعداد کلاسهای واقعی
= تعداد نقطههای خوشهٔ از کلاس
def purity_score(cluster_labels, true_labels):
contingency_matrix = compute_contingency_table(cluster_labels, true_labels)
return np.sum(np.amax(contingency_matrix, axis=1)) / np.sum(contingency_matrix)مثالی را ببینیم که در آن خلوص بالا به دست میآید، یعنی خوشهبندی با افراز حقیقتمبنا همراستاست.
دادههای مثال¶
فرض کنید خوشهبندی و برچسبهای حقیقتمبنای زیر را داریم:
true_labels = np.array([0, 0, 1, 1, 1, 2])
cluster_labels = np.array([0, 0, 1, 1, 2, 2])اینجا هر خوشه بهتر با یک کلاس واقعی میخواند.
محاسبهٔ جدول توافقی¶
با تابع compute_contingency_table جدول زیر به دست میآید:
| Class 0 | Class 1 | Class 2 | |
|---|---|---|---|
| C₀ | 2 | 0 | 0 |
| C₁ | 0 | 2 | 0 |
| C₂ | 0 | 1 | 1 |
محاسبههای میانی¶
گام ۱: بیشینهٔ هر سطر را بیابید:
max(C₀) = 2max(C₁) = 2max(C₂) = 1
گام ۲: بیشینهها را جمع کنید:
گام ۳: خلوص را حساب کنید:
true_labels = np.array([0, 0, 1, 1, 1, 2])
cluster_labels = np.array([0, 0, 1, 1, 2, 2])
score = purity_score(cluster_labels, true_labels)
print(f"Purity Score: {score:.3f}") # Expected output: 0.833Purity Score: 0.833
خلوص نسبت به برچسبهای خوشه ناورداست، یعنی تا وقتی خود تخصیص یکسان بماند، تغییر نام خوشهها امتیاز را عوض نمیکند.
بیایید همان خوشهبندی پیشین را برداریم ولی برچسبهای خوشه را جابهجا کنیم (مثلاً نام خوشهها را از C₀ C₂، C₁ C₀، C₂ C₁ عوض کنیم):
import numpy as np
# Original clustering labels
true_labels = np.array([0, 0, 1, 1, 1, 2])
cluster_labels = np.array([0, 0, 1, 1, 2, 2])
shifted_cluster_labels = np.array([2, 2, 0, 0, 1, 1]) # Shifted cluster labels (mapping: 0 → 2, 1 → 0, 2 → 1)
# Compute purity scores for both cases
original_purity = purity_score(cluster_labels, true_labels)
shifted_purity = purity_score(shifted_cluster_labels, true_labels)
print(f"Original Purity: {original_purity:.3f}") # Expected output: 0.833
print(f"Shifted Labels Purity: {shifted_purity:.3f}") # Expected output: 0.833 (same!)Original Purity: 0.833
Shifted Labels Purity: 0.833
چرا خلوص ثابت میماند؟
تناظر میان خوشهها و بخشهای حقیقتمبنا عوض نشده، فقط برچسبهایشان عوض شده است.
چون خلوص فقط به میزان خواندن خوشهها با بخشهای حقیقتمبنا بستگی دارد، تغییر نام خوشهها روی محاسبهٔ آن اثری ندارد.
۲. دقت، بازآوری و سنجهٔ F¶
برای هر خوشهٔ :
دقت: کسر نقطههای خوشه که از کلاس اکثریتاند
بازآوری: کسر نقطههای کلاس که در خوشه یافت میشوند

دقت¶
خوشهٔ را در نظر بگیرید و بخشی را نشان دهد که بیشترین نقطههای را در خود دارد،
یعنی اندیس بزرگترین درایهٔ سطر در جدول توافقی. دقت خوشهٔ همان خلوص آن است:
بازآوری¶
بازآوری خوشهٔ چنین تعریف میشود:
که در آن .
سنجهٔ F¶
سنجهٔ F میانگین هارمونیک دقت و بازآوری برای هر است:
سنجهٔ F برای خوشهبندی میانگین سنجههای F خوشههاست:
۳. بیشینهٔ تطبیق¶
بهترین تطبیق میان خوشهها و کلاسهای واقعی را مییابد تا همپوشانی بیشینه شود:
که در آن تطبیقی میان خوشهها و کلاسهاست.
تطبیق با بیشترین وزن (به پیروی از zaki2020data)
بگذارید گرافی دوبخشی روی مجموعهٔ رأسهای باشد و مجموعهٔ یالها با وزنهای . یک تطبیق در زیرمجموعهای از است که یالهایش دوبهدو مجاور نباشند، یعنی رأس مشترک نداشته باشند.
تطبیق با بیشترین وزن در چنین است:
که در آن مجموع وزن همهٔ یالهای تطبیق است، یعنی .
مثال بیشینهٔ تطبیق (تفسیر گراف دوبخشی)¶
سناریو: فرض کنید ۱۰ میوه را در ۳ خوشه خوشهبندی کردهایم و دستههای واقعیشان (حقیقتمبنا) را میدانیم:
True Categories (T₁=apples, T₂=oranges, T₃=bananas):
T₁: apple1, apple2, apple3, apple4
T₂: orange1, orange2, orange3
T₃: banana1, banana2, banana3
Cluster Assignments (C₁, C₂, C₃):
C₁: [apple1, apple2, banana1]
C₂: [orange1, orange2, apple3]
C₃: [banana2, banana3, orange3, apple4]
جدول توافقی¶
| Apples (T₁) | Oranges (T₂) | Bananas (T₃) | Total (nᵢ) | |
|---|---|---|---|---|
| C₁ (apple1, apple2, banana1) | 2 | 0 | 1 | 3 |
| C₂ (orange1, orange2, apple3) | 1 | 2 | 0 | 3 |
| C₃ (banana2, banana3, orange3, apple4) | 1 | 1 | 2 | 4 |
| Total (mⱼ) | 4 | 3 | 3 | n = 10 |
گام ۱: ساختن گراف دوبخشی
میان خوشهها و دستهها یالهایی با وزن برابر همپوشانی میسازیم:
Clusters Categories
C₁ ------------- T₁ (weight=2: apple1,apple2)
\------------ T₃ (weight=1: banana1)
C₂ ------------- T₁ (weight=1: apple3)
\------------ T₂ (weight=2: orange1,orange2)
C₃ ------------- T₁ (weight=1: apple4)
\------------ T₂ (weight=1: orange3)
\------------ T₃ (weight=2: banana2,banana3)گام ۲: یافتن تطبیق با بیشترین وزن
میخواهیم هر خوشه حداکثر به یک دسته (و برعکس) تطبیق داده شود تا وزن کل بیشینه شود:
گزینههای ممکن تطبیق:
Match C₁-T₁ (2), C₂-T₂ (2), C₃-T₃ (2) Total weight = 6
Match C₁-T₃ (1), C₂-T₂ (2), C₃-T₁ (1) Total weight = 4
گزینهٔ اول تطبیق با بیشترین وزن را میدهد.
گام ۳: محاسبهٔ امتیاز بیشینهٔ تطبیق
import numpy as np
from scipy.optimize import linear_sum_assignment
# Define contingency table
contingency = np.array([
[2, 0, 1], # C₁: 2 apples, 0 oranges, 1 banana
[1, 2, 0], # C₂: 1 apple, 2 oranges, 0 bananas
[1, 1, 2] # C₃: 1 apple, 1 orange, 2 bananas
])
# Find optimal matching
row_ind, col_ind = linear_sum_assignment(contingency, maximize=True)
# Perform indexing correctly
max_weight = contingency[row_ind, col_ind].sum()
print(f"Optimal matching: {list(zip(row_ind, col_ind))}")
print(f"Max weight: {max_weight}")
# Optimal matching: [(0, 0), (1, 1), (2, 2)] # C₁-T₁, C₂-T₂, C₃-T₃Optimal matching: [(np.int64(0), np.int64(0)), (np.int64(1), np.int64(1)), (np.int64(2), np.int64(2))]
Max weight: 6
مثال ۱۷.۱: خوشهبندی خوب در برابر بد روی دادهٔ زنبق¶
دو خوشهبندی مختلف از مجموعهدادهٔ زنبق را با مؤلفههای اصلی بررسی کنیم:
نتیجهٔ خوشهبندی خوب:¶

جدول توافقی¶
| iris-setosa | iris-versicolor | iris-virginica | Total (n_i) | |
|---|---|---|---|---|
| C₁ (squares) | 0 | 47 | 14 | 61 |
| C₂ (circles) | 50 | 0 | 0 | 50 |
| C₃ (triangles) | 0 | 3 | 36 | 39 |
| Total (m_j) | 50 | 50 | 50 | n = 150 |
Purity: 0.887
Match: 0.887
F: 0.885
نتیجهٔ خوشهبندی بد:¶

جدول توافقی¶
| iris-setosa | iris-versicolor | iris-virginica | Total (n_i) | |
|---|---|---|---|---|
| C₁ (squares) | 30 | 0 | 0 | 30 |
| C₂ (circles) | 20 | 4 | 0 | 24 |
| C₃ (triangles) | 0 | 46 | 50 | 96 |
| Total (m_j) | 50 | 50 | 50 | n = 150 |
Purity: 0.667
Match: 0.560
F: 0.658
بیشینههای سطر است، پس خلوص . بیشینهٔ تطبیق –setosa (30)، –versicolor (4) و –virginica (50) را جفت میکند، پس match . خلوص و تطبیق اینجا فرق میکنند چون خلوص میتواند دو خوشه را به یک کلاس نسبت دهد ولی تطبیق نمیتواند.
۴. سنجههای جفتی¶
نخست چند کمیت کلیدی را که در سنجههای بیرونی به کار میروند تعریف کنیم:
TP (مثبتهای واقعی): جفتهایی در یک خوشه و در یک بخش واقعی
FP (مثبتهای کاذب): جفتهایی در یک خوشه ولی در بخشهای مختلف
TN (منفیهای واقعی): جفتهایی در خوشههای مختلف و بخشهای مختلف
FN (منفیهای کاذب): جفتهایی در خوشههای مختلف ولی در یک بخش
با خوشهبندی و افراز حقیقتمبنای ، بگذارید دو نقطهٔ دلخواه با باشند. برچسب بخش واقعی و برچسب خوشهٔ نقطهٔ را نشان دهد.
اگر و در یک خوشه باشند، یعنی ، آن را رخدادی مثبت مینامیم، و اگر در یک خوشه نباشند، یعنی ، رخدادی منفی. بسته به توافق یا ناتوافقی برچسبهای خوشه و بخشها، چهار حالت پیش میآید:
مثبتهای واقعی (TP)
و در در یک بخشاند و در هم در یک خوشهاند. تعداد جفتهای مثبت واقعی چنین است:
منفیهای کاذب (FN)
و در در یک بخشاند، ولی در در یک خوشه نیستند. تعداد جفتهای منفی کاذب چنین است:
مثبتهای کاذب (FP)
و در در یک بخش نیستند، ولی در در یک خوشهاند. تعداد جفتهای مثبت کاذب چنین است:
منفیهای واقعی (TN)
و نه در در یک بخشاند و نه در در یک خوشه. تعداد چنین جفتهای منفی واقعی چنین است:
نگاه جفتی به سنجههای بیرونی¶
جاکارد و رند هر دو مسئلهٔ خوشهبندی را جور دیگری از جدول توافقی میبینند: بهجای سنجیدن شناسههای خوشه با شناسههای کلاس، پرسشی دربارهٔ هر جفت نقطه میپرسند.
برای جفت (i, j) میتوان دو پرسش بله/خیر پرسید:
آیا
iوjدر یک کلاس حقیقتمبنا هستند؟آیا
iوjدر یک خوشه هستند؟
چهار حالت ممکن است:
| same cluster | different cluster | |
|---|---|---|
| same class | TP (True Positive) | FN (False Negative) |
| different class | FP (False Positive) | TN (True Negative) |
TP — جفتی که در حقیقتمبنا و در خوشهبندی با هماند.
TN — جفتی که در حقیقتمبنا و در خوشهبندی جدا از هماند.
FP — جفتی که در حقیقتمبنا جدا است ولی خوشهبندی آنها را ادغام کرده.
FN — جفتی که در حقیقتمبنا با هم است ولی خوشهبندی آنها را شکسته است.
هر چه در پی میآید راه دیگری برای ترکیب این چهار شمارنده است.
جاکارد در واقع چه چیزی را میسنجد¶
جاکارد فقط جفتهای مثبت را میبیند — آنهایی که در دستکم یکی از دو افراز با هماند — و میپرسد چه کسری از آنها در هر دو با هماند. شمارندهٔ TN کاملاً نادیده گرفته میشود.
چون TN با زیاد شدن تعداد خوشهها بسیار سریع رشد میکند، نادیدهگرفتنش انتخابی عامدانه است: جاکارد حتی وقتی تعداد خوشهها زیاد است یا دو افراز تعداد گروه یکسان ندارند معنادار میماند. از این نظر مقاومترین سنجهٔ جفتی است.
رند در واقع چه چیزی را میسنجد¶
رند هر دو نوع توافق را میشمارد: جفتهایی که در هر دو افراز با هماند (TP) و جفتهایی که در هر دو افراز جدا هستند (TN). مخرج تعداد کل جفتهاست، پس رند میپرسد: در چه کسری از همهٔ جفتهای ممکن، دو افراز همنظرند؟
رند در نگاه اول شبیه دقت در دستهبندی است، ولی این دو سنجه یکی نیستند. دو زیربخش بعدی دلیلش را میگویند.
رند دقت نیست¶
در نگاه اول رند شبیه همتای خوشهبندیِ دقت است: هر دو تعداد «تصمیمهای درست» را بر تعداد کل تصمیمها تقسیم میکنند، هر دو در [0, 1] میافتند، و هر دو را در گفتار غیررسمی «درصد توافق» مینامند. ولی شباهت سطحی است. دقت و رند در سه اصل بنیادی فرق دارند.
۱. واحد شمردهشده فرق دارد.
دقت دربارهٔ هر نمونه میپرسد: آیا برچسب پیشبینیشده با برچسب واقعی یکی است؟ رند دربارهٔ هر جفت نقطه میپرسد: آیا این دو نقطه در دو افراز، یک سمت یکسانی دارند؟ یک خوشهبندی از n نقطه دارای n(n-1)/2 جفت است، پس رند به تعداد تصمیمهایی میرسد که با اندازهٔ مجموعهداده درجهدوم رشد میکنند. اینها اصلاً از یک جنس نیستند.
۲. تناظر یکبهیک میان شناسههای خوشه و کلاس وجود ندارد.
در دستهبندی هر کلاس برچسبی معنادار و یگانه دارد. در خوشهبندی شناسههایی که KMeans.labels_ میدهد دلبخواهاند: خوشهٔ 0 در یک اجرا ممکن است در اجرای بعد 1 باشد. دقت را نمیتوان مستقیم روی شناسههای خوشه حساب کرد، چون برچسب حقیقتمبنایی برای سنجیدنشان نیست. رند کلاً از این مشکل میگریزد: هیچجا از شناسه حرف نمیزند، فقط از رابطهٔ همان/متفاوت میان جفتها، که نسبت به تغییر برچسب ناورداست.
۳. رند حتی وقتی k ≠ r باشد تعریف شده است.
دقت تعداد ثابتی کلاس را پیشفرض میگیرد. رند نه: چه الگوریتم خوشه بیشتری از تعداد کلاسها ساخته باشد (بیشافرازی) و چه کمتر (کمافرازی)، کار میکند. همین باعث میشود رند در مثالهایی محاسبهشدنی بماند که دقت در آنها اصلاً معنا ندارد.
تنها ضعفی که هر دو دارند. دقت روی دادهٔ نامتوازن گمراهکننده است: پیشبینی همهجا کلاس اکثریت امتیاز بالا میدهد بدون آنکه چیزی یاد بگیرد. رند همین ضعف را برای خوشهبندیهایی با گروههای زیاد دارد: هر چه k بزرگتر شود، TN بر صورت غالب میشود و رند حتی برای برچسبگذاری تصادفی به یک نزدیک میشود. این دو سنجه هر یک جور دیگری شکست میخورند، ولی وقتی مسئله نامتوازن است هیچکدام بهتنهایی قابل اعتماد نیست.
شاخص رند تعدیلشده (ARI)¶
چون TN با بزرگ شدن k بسیار سریع رشد میکند، رند نسبت به تصادف تعدیل نشده: برچسبگذاری کاملاً تصادفی همان n نقطه با همان k خوشه از قبل مقدار رندِ مورد انتظار بالایی دارد. سنجهای سودمند باید به چنین برچسبگذاری تصادفی صفر بدهد و تنها به یکی بیعیب یک.
شاخص رند تعدیلشده دقیقاً همین کار را میکند. مقداری را که رند در برچسبگذاری تصادفی انتظار میرود بگیرد کم میکند و بر بیشینهٔ تعدیل ممکن تقسیم میکند:
مقدار مورد انتظار از مجموع سطرها و ستونهای جدول توافقی (اندازهٔ خوشهها و اندازهٔ کلاسها) حساب میشود، پس هیچ فرضی دربارهٔ داده نمیکند.
تفسیر ARI چنین است:
ARI = 1— دو افراز یکیاند (بهجز تغییر نام).ARI = 0— خوشهبندی از برچسبگذاری تصادفی با همان اندازهٔ خوشهها بهتر نیست.ARI < 0— خوشهبندی از تصادفی بدتر است، که واقعاً میتواند پیش بیاید وقتی الگوریتم در اجراهای مختلف یک کلاس را همیشه به یک شکل میشکند.
در عمل ARI پیشفرض پیشنهادی برای سنجیدن دو افراز است، چون تنها سنجهٔ بیرونی رایجی است که همزمان:
نسبت به تغییر نام خوشهها ناورداست،
نسبت به تصادف تعدیل شده است،
وقتی
k ≠ rتعریف شده است،از بالا با یک کران دارد.
همچنین همان سنجهای است که scikit-learn بهطور پیشفرض با فراخوانی adjusted_rand_score(true_labels, cluster_labels) گزارش میکند.
اطلاعات متقابل نرمالشده (NMI)¶
رند و ARI بر جفت نقطهها بنا شدهاند. جانشین نظریهٔ اطلاعاتی میپرسد برچسب خوشه چقدر دربارهٔ کلاس واقعی میگوید. بگذارید و آنتروپی دو افراز باشند که از حاشیههای جدول توافقی برآورد میشوند، و اطلاعات متقابل آنها:
با قرارداد . NMI دقیقاً وقتی یک است که دو افراز بهجز تغییر نام یکی باشند، و صفر وقتی برچسبهای خوشه هیچ اطلاعاتی دربارهٔ کلاسها نداشته باشند. برای هم خوشتعریف است و به تطبیق نیازی ندارد.
ضعفش این است که نسبت به تصادف تعدیل نشده: با خوشههای کوچک و زیاد، برچسبگذاری تصادفی از قبل NMI مثبتی میدهد و اندازهٔ این خط پایه به و بستگی دارد. پس مقدارها میان مسئلههای مختلف قابل مقایسه نیستند، و همین دلیل ترجیح ARI (و اطلاعات متقابل تعدیلشده، AMI) بهعنوان پیشفرض است.
خلاصه: کدام سنجه را به کار ببریم¶
| سنجه | واحد | تعدیلشده برای تصادف | وقتی k ≠ r کار میکند | بازه |
|---|---|---|---|---|
| دقت | نمونه | — (بدون تعدیل تصادف) | ❌ | [0, 1] |
| جاکارد | جفت | ❌ | ✅ | [0, 1] |
| رند | جفت | ❌ | ✅ | [0, 1] |
| NMI | نمونه | ❌ | ✅ | [0, 1] |
| ARI | جفت | ✅ | ✅ | [-1, 1] |
جاکارد انتخاب درست است وقتی جفتهای مثبت (تصمیمهای «با هم بودن») برایتان مهماند و سنجهای میخواهید که با انبوه جفتهای بدیهیـمتفاوت باد نکند.
رند خط پایهٔ تاریخی مقایسهٔ جفتی است و برای آموزش خوب است، ولی نسبت به تصادف تعدیل نشده و با
kباد میکند.NMI انتخاب معمول است وقتی خوشهبندی با یک متغیر بیرونی سنجیده میشود که افرازی از همان نقطهها نیست، و در ادبیات نظریهٔ اطلاعات؛ برای افرازها ARI رفتار بهتری دارد.
ARI پیشفرض پیشنهادی است: نزدیکترین همتای دقت که از دو مشکل ساختاری خوشهبندی (شناسههای دلبخواه و
kناشناخته) جان سالم به در میبرد.
مثالهای این صفحه طوری برگزیده شدهاند که همین تفاوتها دیده شوند: خوشهبندی بیعیب به Jaccard = Rand = ARI = 1 میرسد، خوشهبندی ضعیف هر سه را پایین میآورد، و حالت بیشافراز رند را بالا نگه میدارد در حالی که ARI میافتد — همان حالت شکستی که ARI برای رفعش طراحی شده است.
سنجههای درونی¶
سنجههای درونی فقط از داده و افراز بهره میبرند: هیچ برچسب حقیقتمبنایی در کار نیست. پرسشی متفاوت از سنجههای بیرونی میپرسند — نه «آیا این گروهبندی واقعی است؟» بلکه «آیا این گروهبندی درونی منسجم است؟» — و مقدار بالا هرگز ثابت نمیکند خوشهها معنایی دارند، فقط میگوید بر پایهٔ یک تعریف خاص جمعوجور و جدا هستند.
سنجههای نسبی، خانوادهٔ سوم، دو خوشهبندی از یک داده را با هم میسنجند، مثلاً یک الگوریتم با دو تنظیم پارامتر. فرمول جداگانهای نیستند: هر سنجهٔ درونی یا بیرونی را میتوان نسبی به کار برد، با داوریاش روی هر دو خوشهبندی و مقایسهٔ عددها. جاروب در پایان این صفحه دقیقاً همین است.
۵. ضریب سیلوئت¶
سیلوئت برای هر نقطه فاصلهاش تا خوشهٔ خودش را با فاصلهاش تا نزدیکترین خوشهٔ دیگر میسنجد. برای نقطهٔ در خوشهٔ بگذارید
میانگین فاصلهٔ تا نقطههای دیگر باشد (چسبندگی)؛
کمترین میانگین فاصلهٔ تا نقطههای خوشهای دیگر باشد (جدایی).
آنگاه
مقدار نزدیک یک یعنی نقطه به خوشهٔ خودش بسیار نزدیکتر از خوشهٔ بعدی است، نزدیک صفر یعنی خوشهها به هم میرسند، و منفی یعنی نقطه احتمالاً در خوشهٔ اشتباه است. این امتیاز همهٔ فاصلههای جفتی را لازم دارد، پس هزینه دارد — روی زنبق بهکارآمد و روی یک میلیون نقطه گران.
۶. SSE (اینرسی)¶
تابع هدف k-means خودش یک سنجهٔ درونی است:
scikit-learn آن را KMeans.inertia_ گزارش میکند. دقیقاً همان کمیت k-Means است، پس ارزان است: بدون فاصلهٔ جفتی، یک گذر روی داده. دام این است که برای گزیدن به کار نمیآید: افزودن یک مرکز هرگز SSE را زیاد نمیکند، پس کمینه همیشه در است که SSE صفر میشود. قاعدهٔ معمول «آرنج» — ای را بگیر که منحنی پس از آن صاف میشود — این را به یک تصمیم تبدیل میکند، ولی آرنج داوری چشمی است، و روی زنبق آرنج روشنی نیست.
۷. آمارهٔ شکاف¶
Tibshirani، Walther و Hastie (۲۰۰۱) آرنج چشمی را با مقایسه با نوفهٔ خالص جانشین میکنند. مجموعهدادهٔ مرجع را بهطور یکنواخت روی جعبهٔ دربرگیرندهٔ داده بسازید، هر کدام را به گروه خوشهبندی کنید، و بگذارید
که میانگین روی مجموعهدادههای مرجع است. پراکندگی جفتی درونخوشهای است؛ بنا بر لم ۲ از k-Means همان SSE تقسیم بر است، پس شکاف منحنی مشاهدهشده را با منحنیای میسنجد که دادهٔ بیساختار میدهد. کوچکترین ای را برگزینید که
و اگر هیچ ای آن را برآورده نکرد، . هزینهٔ اضافه خوشهبندی برای هر نامزد است، و همین باعث میشود این قاعده کمتر از سیلوئت به کار رود.
مثال پایتون روی مجموعهدادهٔ زنبق¶
import numpy as np
from sklearn import datasets
from sklearn.cluster import KMeans
from sklearn.metrics import adjusted_rand_score, normalized_mutual_info_score
# Load Iris dataset
iris = datasets.load_iris()
X = iris.data
y = iris.target
# Cluster with K-means
kmeans = KMeans(n_clusters=3, random_state=42)
cluster_labels = kmeans.fit_predict(X)
# External measures: the contingency table and the scores built on it
contingency = compute_contingency_table(cluster_labels, y)
display_contingency_table_pandas(
contingency, class_names=[name.split("-")[-1] for name in iris.target_names])
def pairwise_counts(y_true, y_pred):
"""TP, FP, FN, TN over all pairs of points."""
tp = fp = fn = tn = 0
n = len(y_true)
for i in range(n):
for j in range(i + 1, n):
same_cluster = y_pred[i] == y_pred[j]
same_class = y_true[i] == y_true[j]
if same_cluster and same_class:
tp += 1
elif same_cluster and not same_class:
fp += 1
elif not same_cluster and same_class:
fn += 1
else:
tn += 1
return tp, fp, fn, tn
tp, fp, fn, tn = pairwise_counts(y, cluster_labels)
jaccard = tp / (tp + fn + fp)
rand = (tp + tn) / (tp + fp + fn + tn)
print(f"Purity: {purity_score(cluster_labels, y):.3f}")
print(f"Jaccard: {jaccard:.3f}")
print(f"Rand: {rand:.3f} ({tp:,} agreement pairs out of {tp + fp + fn + tn:,})")
print(f"ARI: {adjusted_rand_score(y, cluster_labels):.3f}")
print(f"NMI: {normalized_mutual_info_score(y, cluster_labels):.3f}")Purity: 0.887
Jaccard: 0.682
Rand: 0.874 (3,030 agreement pairs out of 11,175)
ARI: 0.716
NMI: 0.742
from sklearn.metrics import silhouette_score
print(f"SSE (inertia) of this k = 3 clustering : {kmeans.inertia_:.1f}")
print(f"silhouette coefficient (k = 3) : {silhouette_score(X, cluster_labels):.3f}")SSE (inertia) of this k = 3 clustering : 78.9
silhouette coefficient (k = 3) : 0.551
تفسیر نتیجهها¶
خلوص، جاکارد، رند، ARI، NMI: بیشتر بهتر است، و 1 یعنی دو افراز توافق دارند (بهجز تغییر نام). ARI و NMI را میتوان میان مسئلهها مقایسه کرد؛ خلوص و رند را نه.
سیلوئت: در ، بیشتر بهتر.
SSE: کمتر بهتر، ولی بهحکم ساخت با کاهش مییابد، پس معیار گزیدن نیست.
از عددهای بالا دو هشدار برمیآید.
خلوص خوشبین است. روی زنبق با خلوص نزدیک ۰٫۹ است، هرچند کلاسهای versicolor و virginica اصلاً جدا نیستند: نقطههای این دو کلاس در هماند و خلوص فقط میخواهد هر خوشه یک کلاس اکثریت داشته باشد. خوشهبندیای که یک کلاس را به تکههای کوچک خالص بشکند، خلوص بالا جمع میکند بدون آنکه چیزی یافته باشد. ARI و NMI اینجا عددهای صادقاند.
هیچ سنجهٔ درونیای بهتنهایی تعداد واقعی خوشهها را نمییابد. جاروب سیلوئت در اوج میگیرد (حدود ۰٫۶۸) در حالی که حقیقتمبنا سه کلاس دارد (حدود ۰٫۵۵). سیلوئت جداشدنی درشت و خوب را پاداش میدهد، و «setosa در برابر بقیه» دقیقاً همان است: جواب دوگروهیِ بسیار تمیز که با این حال همان دستهبندی نیست. این درس کلیدی جلسه است — سنجهٔ درونی یک تعریف از خوشهٔ خوب را در خود دارد، نه حقیقت را. میتوان آن را بهینه کرد، و بهینهکردنش میتواند جواب نادرست را برگزیند. چند سنجه را گزارش کنید، به داده نگاه کنید، و به سنجهای اعتماد کنید که پرسش درونش همان پرسشی است که میپرسید.
شکل زیر با بستهٔ yellowbrick کشیده شده است (pip install yellowbrick)؛ امتیازهایی که چاپ میکند همان مقدارهای silhouette_score است که بالا حساب شد.
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], force_model=True, is_fitted=True)
visualizer.fit(X)
print({k: round(s, 3) for k, s in zip([2, 3, 4, 5], scores)}){2: 0.681, 3: 0.553, 4: 0.498, 5: 0.491}

منحنی SSE توضیح میدهد چرا قاعدهٔ آرنج قاعده نیست. کاهش تا تند است و بعد صاف میشود، ولی هرگز متوقف نمیشود: در بهقدر کافی بزرگ هر نقطه خوشهٔ خودش میشود و SSE دقیقاً صفر است.
ks = range(1, 11)
sse = [KMeans(n_clusters=k, random_state=42).fit(X).inertia_ for k in ks]
plt.figure(figsize=(7, 4))
plt.plot(list(ks), sse, marker="o")
plt.xlabel("number of clusters $k$")
plt.ylabel("SSE (inertia)")
plt.title("SSE decreases monotonically, so it cannot choose $k$")
plt.xticks(list(ks))
plt.grid(alpha=0.3)
plt.show()
for k, value in zip(ks, sse):
print(f"k = {k:2d} SSE = {value:8.2f}")
k = 1 SSE = 681.37
k = 2 SSE = 152.35
k = 3 SSE = 78.86
k = 4 SSE = 57.35
k = 5 SSE = 46.47
k = 6 SSE = 39.07
k = 7 SSE = 34.31
k = 8 SSE = 30.48
k = 9 SSE = 29.91
k = 10 SSE = 28.55
گزیدن سنجهٔ درست¶
وقتی حقیقتمبنا در دسترس است از سنجههای بیرونی بهره ببرید
وقتی برچسبی نیست از سنجههای درونی بهره ببرید
برای داوری استوار چند سنجه را با هم ببینید
یادتان باشد هیچ سنجهٔ واحدی کل داستان را نمیگوید — سنجههای مختلف برای هدفهای مختلف خوشهبندی مناسبترند.
مسئلهٔ تخصیص در پس بیشینهٔ تطبیق¶
بیشینهٔ تطبیق با وزن نمونهای از مسئلهٔ تخصیص است: با جدول توافقی ، جفتشدن یکبهیک سطرها و ستونها را برگزینید که وزن کل بیشینه شود. برای جدولهای مربع، الگوریتم مجارستانی دقیقاً حلش میکند، که scipy.optimize.linear_sum_assignment پیادهسازیاش است؛ برای جدولهای مستطیلی همان رویه جفتشدن بهینهای برمیگرداند که سطرها یا ستونهای اضافه را بیجفت میگذارد، و همین چیزی است که وقتی میخواهیم.
همین مسئله هر جا دو مجموعه باید با قید یکبهیک جفت شوند پیش میآید: دانشآموزان به مدرسهها، داوران به مقالهها، پرسشها به سندها، یا ویژگیها به مؤلفهها. فصل ۱۷ زکی آن را برای اعتبارسنجی خوشهبندی گسترش میدهد؛ بحث کلی در همان کتاب است (zaki2020data).
تطبیق با بیشترین وزن با networkx¶
جدول توافقی را میتوان گرافی دوبخشی هم خواند: خوشهها یک سو، کلاسها سوی دیگر، و یالی با وزن هر جا باشد. امتیاز بیشینهٔ تطبیق آنگاه وزن یک تطبیق با بیشترین وزن در همان گراف است.
networkx.algorithms.matching.max_weight_matching مسئلهٔ کلی را حل میکند؛ به گراف دوبخشی محدود نیست، پس اگر گراف یالی درون یک بخش داشته باشد ممکن است از آن بهره ببرد. اینجا هر یال یک خوشه را به یک کلاس میپیوندد، پس نتیجه تطبیقی در گراف دوبخشی است. weight="weight" را صریح بدهید — با پیشفرض weight=None وزن یالها نادیده گرفته میشود و رویه تطبیقی با بیشترین تعداد یال برمیگرداند، که نسخهٔ پیشین این صفحه بهاشتباه همین کار را میکرد.
import networkx as nx
import matplotlib.pyplot as plt
from networkx.algorithms import bipartite
# the contingency table of the bad clustering, as a bipartite graph
table = np.array([[30, 0, 0], [20, 4, 0], [0, 46, 50]])
clusters = ["C1", "C2", "C3"]
classes = ["setosa", "versicolor", "virginica"]
G = nx.Graph()
G.add_nodes_from(clusters, bipartite=0)
G.add_nodes_from(classes, bipartite=1)
for i, cluster in enumerate(clusters):
for j, cls in enumerate(classes):
if table[i, j] > 0:
G.add_edge(cluster, cls, weight=int(table[i, j]))
matching = nx.algorithms.matching.max_weight_matching(G, weight="weight")
total = sum(G[u][v]["weight"] for u, v in matching)
print("matched pairs and weights:")
for u, v in matching:
print(f" {u} - {v}: {G[u][v]['weight']}")
print(f"\nmatched weight = {total} match score = {total / table.sum():.3f}")
pos = {**{n: (0, i) for i, n in enumerate(clusters)},
**{n: (1, i) for i, n in enumerate(classes)}}
plt.figure(figsize=(6, 4))
nx.draw(G, pos, with_labels=True, node_color="lightblue", node_size=2000, font_size=10)
nx.draw_networkx_edges(G, pos, edgelist=list(matching), width=2.5, edge_color="red")
nx.draw_networkx_edge_labels(G, pos, font_size=9,
edge_labels={(u, v): G[u][v]["weight"] for u, v in G.edges})
plt.title("Bipartite graph of the contingency table, maximum weight matching in red")
plt.show()matched pairs and weights:
C2 - versicolor: 4
virginica - C3: 50
C1 - setosa: 30
matched weight = 84 match score = 0.560

خلاصه¶
خوشهبندی اعتبارسنجی میخواهد: بی برچسب، «همگرا شد» هیچ چیزی دربارهٔ کیفیت نمیگوید.
سنجههای بیرونی از جدول توافقی ، یعنی (سطر = خوشه، ستون = کلاس) آغاز میشوند که در حساب میشود.
خلوص مجموع بیشینههای سطرهاست؛ خوشبین است، چون اجازه میدهد دو خوشه یک کلاس را ادعا کنند.
دقت، بازآوری و F نگاه ستونی را میافزایند؛ بیشینهٔ تطبیق جفتشدن یکبهیک را تحمیل میکند و یک مسئلهٔ تخصیص است (
linear_sum_assignment).سنجههای جفتی توافقها را روی جفت نقطهها میشمارند: جاکارد را نادیده میگیرد، رند همه چیز را میشمارد و با باد میکند، ARI رند را نسبت به تصادف تعدیل میکند، NMI اطلاعات مشترک را میسنجد ولی تعدیل نشده است.
سنجههای درونی — سیلوئت، SSE، شکاف — فقط از داده بهره میبرند؛ هیچکدام تعداد واقعی خوشهها را مشخص نمیکند، و بهینهکردن یکی از آنها میتواند جواب نادرست بدهد.
چند سنجه را گزارش کنید و بگویید هر کدام به کدام پرسش پاسخ میدهد.