Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

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

English · فارسی
Source

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

محمود امین‌طوسی، پاییز ۱۴۰۵

گروه علوم کامپیوتر، دانشگاه فردوسی مشهد

این صفحه فصل ۱۷ از zaki2020data را دنبال می‌کند: Clustering Validation.

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

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

  1. سنجه‌های بیرونی: از اطلاعات بیرونی، یعنی برچسب‌های حقیقت‌مبنا، بهره می‌برند.

  2. سنجه‌های درونی: فقط از داده و نتیجهٔ خوشه‌بندی بهره می‌برند.

  3. سنجه‌های نسبی: دو خوشه‌بندی از یک داده را با هم می‌سنجند، بدون هیچ حقیقت‌مبنایی.

اهداف یادگیری. در پایان باید بتوانید

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

  2. خلوص، دقت/بازآوری/F، بیشینهٔ تطبیق، جاکارد، رند، ARI و NMI را حساب و تفسیر کنید و بگویید هر کدام چه چیزی را نادیده می‌گیرد؛

  3. توضیح دهید چرا دقت را نمی‌توان روی برچسب‌های خوشه به کار برد؛

  4. از سنجه‌های درونی (سیلوئت، SSE، شکاف) بهره ببرید و بگویید چرا هیچ‌کدام «تعداد واقعی» خوشه‌ها را مشخص نمی‌کند؛

  5. امتیاز بیشینهٔ تطبیق را به‌عنوان یک مسئلهٔ تخصیص ببینید.

نمادگذاری

زکی rr را برای تعداد خوشه‌ها و kk را برای تعداد کلاس‌های حقیقت‌مبنا به کار می‌برد. این صفحه همان حروف را نگه می‌دارد تا فرمول‌ها با کتاب بخوانند؛ توجه داشته باشید که صفحه‌های k-means این درس kk را برای تعداد خوشه‌ها به کار می‌برند. در همهٔ فرمول‌های زیر nijn_{ij} تعداد نقطه‌های خوشهٔ CiC_i را می‌شمارد که به کلاس TjT_j تعلق دارند، و nn تعداد نقطه‌هاست.

سنجه‌های بیرونی

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

فرض کنید D={xi}i=1n\mathbf{D} = \{\mathbf{x}_i\}_{i=1}^n مجموعه‌داده‌ای با nn نقطه در فضایی dd-بعدی است که به kk خوشه افراز شده. بگذارید yi∈{1,2,…,k}y_i \in \left\{ 1, 2,\ldots , k \right\} عضویت یا برچسب حقیقت‌مبنای هر نقطه را نشان دهد.

خوشه‌بندی حقیقت‌مبنا چنین داده می‌شود:

T={T1,T2,…,Tk}\mathbf{T} = \left\{ T_1, T_2, \ldots, T_k \right\}

که در آن خوشهٔ TjT_{j} همهٔ نقطه‌های با برچسب jj را در بر دارد، یعنی

Tj={xi∈D∣yi=j}T_{j} = \left\{ \mathbf{x}_i \in \mathbf{D} \mid y_i = j \right\}

به T\mathbf{T} افراز حقیقت‌مبنا و به هر TiT_i یک بخش (کلاس) می‌گوییم.

بگذارید C={C1,…,Cr}\mathbf{C} = \{C_1, \ldots, C_r\} خوشه‌بندی همان مجموعه‌داده به rr خوشه را نشان دهد که با الگوریتمی خوشه‌بندی به دست آمده، و y^i∈{1,2,…,r}\hat{y}_i \in \left\{ 1, 2, \ldots, r \right\} برچسب خوشهٔ xi\mathbf{x}_i باشد.

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

همهٔ سنجه‌های بیرونی به جدول توافقی r×kr \times k یعنی N\mathbf{N} تکیه می‌کنند که خوشه‌بندی C\mathbf{C} و افراز حقیقت‌مبنای T\mathbf{T} پدید می‌آورند، و چنین تعریف می‌شود:

N(i,j)=nij=∣Ci∩Tj∣\mathbf{N}(i,j) = n_{ij} = \left| C_i \cap T_{j} \right|

شمارش nijn_{ij} تعداد نقطه‌هایی است که هم در خوشهٔ CiC_i و هم در بخش حقیقت‌مبنای TjT_{j} هستند.

بگذارید ni=∣Ci∣n_{i} = |C_i| تعداد نقطه‌های خوشهٔ CiC_i و mj=∣Tj∣m_{j} = |T_{j}| تعداد نقطه‌های بخش TjT_{j} باشد. جدول توافقی را می‌توان در زمان O(n)O(n) از T\mathbf{T} و C\mathbf{C} ساخت: برچسب بخش و خوشهٔ هر نقطه xi∈D\mathbf{x}_i \in \mathbf{D}، یعنی yiy_i و y^i\hat{y}_i، را ببینید و شمارندهٔ متناظر ny^i, yin_{\hat{y}_i,\,y_i} را یکی بیفزایید — اندیس اول برچسب خوشه و اندیس دوم برچسب کلاس است، پس سطرهای N\mathbf{N} خوشه‌ها و ستون‌هایش کلاس‌ها هستند.

Source

نخستین نقطهٔ مرجع: یک خوشه‌بندی بی‌عیب

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

این تنها حالتی است که در آن مقدار «آرمانی» هر سنجهٔ بیرونی معقول به دست می‌آید (یک برای خلوص، NMI و ARI). هر مثال دیگری در این صفحه را باید با همین خط پایه سنجید.

Loading...

یک خوشه‌بندی خوب با خطایی کوچک و متقارن

بیشتر خوشه‌بندی‌های واقعی تقریباً درست‌اند. اینجا C₀ هنوز کاملاً خالص است، ولی C₁ و C₂ هر کدام یک نقطه را با هم عوض کرده‌اند: یک نقطه از کلاس T₁ در C₂ افتاده و یکی از T₂ در C₁.

جدول تقریباً قطری است، پس خلوص، NMI و ARI همگی نزدیک به یک ولی کمی کمتر خواهند بود. این همان حالت معمول «کمی ناکامل» است که بیشتر الگوریتم‌های عملی تولید می‌کنند.

Loading...

شناسه‌های خوشه برچسب‌اند، نه ترتیب

افراز زیر دقیقاً همان افراز مثال B است؛ فقط شناسه‌های خوشه‌ها جای هم عوض شده‌اند. C₁ در این مثال همان است که پیش‌تر C₂ بود، و برعکس.

جدول همان جدول B است با سطرهای جابه‌جا‌شده — و هر سنجهٔ بیرونی همان مقدار عددی را می‌دهد. دلیلش این است که همهٔ سنجه‌های بیرونی باید نسبت به جایگشت شناسه‌های خوشه ناوردا باشند: عددهای 0، 1، 2 که KMeans.labels_ برمی‌گرداند فقط نام‌اند، نه رتبه‌بندی.

Loading...

یک خوشه‌بندی ضعیف با پراکندگی متقارن

اکنون خوشه‌بندی اصلاً نزدیک حقیقت‌مبنا نیست. هر خوشه نقطه‌هایی از دو کلاس مختلف دارد و هر کلاس میان دو خوشه تقسیم شده است. جدول در هر سطر و هر ستون چند درایهٔ ناصفر دارد، ولی هیچ سطر یا ستونی «خالص» نیست.

خلوص حدود ۰٫۵ خواهد بود و NMI و ARI به‌روشنی زیر یک. توجه کنید که هنوز اندکی سیگنال هست: درایه‌های قطری صفر نیستند، پس خوشه‌بندی تصادفی نیست — فقط ضعیف است.

Loading...

یک حالت فریبنده: جدولی کاملاً یکنواخت

این مثال جدول توافقی‌ای دارد که همهٔ درایه‌هایش دقیقاً برابرند. هر خوشه از هر کلاس یک نقطه دارد و هر کلاس به‌طور یکنواخت روی همهٔ خوشه‌ها پخش شده است.

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

خلوص دقیقاً 1/3 است و NMI و ARI دقیقاً صفر — همان مقدارهایی که یک تخصیص کاملاً تصادفی می‌دهد. منظم بودن جدول با سودمند بودن خوشه‌بندی یکی نیست.

Loading...

وقتی تعداد خوشه‌ها با تعداد کلاس‌ها فرق دارد

همهٔ مثال‌های تا اینجا k=rk = r داشتند: به تعداد کلاس‌های حقیقت‌مبنا خوشه. ولی K-means با یک K ثابت اجرا می‌شود که کاربر برمی‌گزیند، و هیچ تضمینی نیست K با تعداد کلاس‌های واقعی بخواند.

در مثال زیر حقیقت‌مبنا سه کلاس دارد ولی الگوریتم چهار خوشه ساخته — یکی از کلاس‌ها را به دو تکه بیش‌افراز کرده است. پس جدول توافقی مربع نیست و هیچ «دقت» ساده‌ای قابل محاسبه نیست: تناظر یک‌به‌یک میان شناسه‌های خوشه و کلاس وجود ندارد.

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

Loading...

حالت برعکس: خوشه‌های بسیار کم

اینجا وضعیت برعکس است: الگوریتم با K=2K = 2 اجرا شده، ولی سه کلاس واقعی داریم. دو تا از آن‌ها در یک خوشه ادغام شده‌اند.

جدول توافقی اکنون ماتریسی 2×32 \times 3 است که یک سطرش نقطه‌هایی از دو کلاس مختلف دارد. خلوص بی‌درنگ می‌افتد، چون آن سطر دو درایهٔ ناصفر با اندازهٔ نزدیک به هم دارد. پنهان‌کردن کم‌افرازی بسیار سخت‌تر از بیش‌افرازی است.

Loading...

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

Using direct indexing:
Loading...

Using np.add.at:
Loading...

۱. خلوص

خلوص می‌سنجد هر خوشه چقدر «خالص» است، با کسر نقطه‌های کلاس اکثریت:

purity=1n∑i=1rmax⁡j=1k{nij}\text{purity} = \frac{1}{n}\sum_{i=1}^r \max_{j=1}^k \{n_{ij}\}

که در آن:

  • n n = تعداد کل نقطه‌ها

  • r r = تعداد خوشه‌ها

  • k k = تعداد کلاس‌های واقعی

  • nij n_{ij} = تعداد نقطه‌های خوشهٔ i i از کلاس j j

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

داده‌های مثال

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

true_labels    = np.array([0, 0, 1, 1, 1, 2])
cluster_labels = np.array([0, 0, 1, 1, 2, 2])

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

محاسبهٔ جدول توافقی

با تابع compute_contingency_table جدول زیر به دست می‌آید:

Class 0Class 1Class 2
C₀200
C₁020
C₂011

محاسبه‌های میانی

گام ۱: بیشینهٔ هر سطر را بیابید:

  • max(C₀) = 2

  • max(C₁) = 2

  • max(C₂) = 1

گام ۲: بیشینه‌ها را جمع کنید: ∑max⁡(nij)=2+2+1=5 \sum \max(n_{ij}) = 2 + 2 + 1 = 5

گام ۳: خلوص را حساب کنید: Purity=∑max⁡(nij)∑nij=56≈0.833 \text{Purity} = \frac{\sum \max(n_{ij})}{\sum n_{ij}} = \frac{5}{6} \approx 0.833

Purity Score: 0.833

خلوص نسبت به برچسب‌های خوشه ناورداست، یعنی تا وقتی خود تخصیص یکسان بماند، تغییر نام خوشه‌ها امتیاز را عوض نمی‌کند.

بیایید همان خوشه‌بندی پیشین را برداریم ولی برچسب‌های خوشه را جابه‌جا کنیم (مثلاً نام خوشه‌ها را از C₀ →\rightarrow C₂، C₁ →\rightarrow C₀، C₂ →\rightarrow C₁ عوض کنیم):

Original Purity: 0.833
Shifted Labels Purity: 0.833

چرا خلوص ثابت می‌ماند؟

  • تناظر میان خوشه‌ها و بخش‌های حقیقت‌مبنا عوض نشده، فقط برچسب‌هایشان عوض شده است.

  • چون خلوص فقط به میزان خواندن خوشه‌ها با بخش‌های حقیقت‌مبنا بستگی دارد، تغییر نام خوشه‌ها روی محاسبهٔ آن اثری ندارد.

۲. دقت، بازآوری و سنجهٔ F

برای هر خوشهٔ Ci C_i :

  • دقت: کسر نقطه‌های خوشه که از کلاس اکثریت‌اند

  • بازآوری: کسر نقطه‌های کلاس که در خوشه یافت می‌شوند

دقت

خوشهٔ CiC_i را در نظر بگیرید و jij_i بخشی را نشان دهد که بیشترین نقطه‌های CiC_i را در خود دارد،

ji=arg⁡max⁡j=1k{nij}j_i = \arg\max_{j=1}^{k} \left\{ n_{ij} \right\}

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

preci=1nimax⁡j=1k{nij}=nijini\mathit{prec}_i = \frac{1}{n_{i}}\max_{j=1}^k \left\{ n_{ij} \right\} = \frac{n_{ij_i}}{n_i}

بازآوری

بازآوری خوشهٔ CiC_i چنین تعریف می‌شود:

recalli=niji∣Tji∣=nijimji\mathit{recall}_i = \frac{n_{ij_i}}{|\mathbf{T}_{j_i}|} =\frac{n_{ij_i}}{m_{j_i}}

که در آن mji=∣Tji∣m_{j_i} = |\mathbf{T}_{j_i}|.

سنجهٔ F

سنجهٔ F میانگین هارمونیک دقت و بازآوری برای هر CiC_i است:

Fi=21preci+1recalli=2⋅preci⋅recallipreci+recalli=2  nijini+mjiF_i = \frac{2}{\frac{1}{\mathit{prec}_i} + \frac{1}{\mathit{recall}_i}} = \frac{2 \cdot \mathit{prec}_i \cdot \mathit{recall}_i}{\mathit{prec}_i + \mathit{recall}_i} = \frac{2 \; n_{ij_i}}{n_{i} + m_{j_i}}

سنجهٔ F برای خوشه‌بندی C\mathbf{C} میانگین سنجه‌های F خوشه‌هاست:

F=1r∑i=1rFiF = \frac{1}{r} \sum_{i=1}^r F_i

۳. بیشینهٔ تطبیق

بهترین تطبیق میان خوشه‌ها و کلاس‌های واقعی را می‌یابد تا همپوشانی بیشینه شود:

match=1nmax⁡M∑(i,j)∈Mnij\text{match} = \frac{1}{n}\max_M \sum_{(i,j)\in M} n_{ij}

که در آن M M تطبیقی میان خوشه‌ها و کلاس‌هاست.

تطبیق با بیشترین وزن (به پیروی از zaki2020data)

بگذارید GG گرافی دوبخشی روی مجموعهٔ رأس‌های V=C∪TV = \mathbf{C} \cup \mathbf{T} باشد و مجموعهٔ یال‌ها E={(Ci,Tj)}E = \{ (C_i, T_{j}) \} با وزن‌های w(Ci,Tj)=nijw(C_i,T_{j}) = n_{ij}. یک تطبیق MM در GG زیرمجموعه‌ای از EE است که یال‌هایش دوبه‌دو مجاور نباشند، یعنی رأس مشترک نداشته باشند.

تطبیق با بیشترین وزن در GG چنین است:

match=max⁡M{w(M)n}\mathit{match} = \max_{M} \left\{ \frac{w(M)}{n} \right\}

که در آن w(M)w(M) مجموع وزن همهٔ یال‌های تطبیق MM است، یعنی w(M)=∑e∈Mw(e)w(M) = \sum_{e \in M} w(e).

مثال بیشینهٔ تطبیق (تفسیر گراف دوبخشی)

سناریو: فرض کنید ۱۰ میوه را در ۳ خوشه خوشه‌بندی کرده‌ایم و دسته‌های واقعی‌شان (حقیقت‌مبنا) را می‌دانیم:

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)2013
C₂ (orange1, orange2, apple3)1203
C₃ (banana2, banana3, orange3, apple4)1124
Total (mⱼ)433n = 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)

گام ۲: یافتن تطبیق با بیشترین وزن

می‌خواهیم هر خوشه حداکثر به یک دسته (و برعکس) تطبیق داده شود تا وزن کل بیشینه شود:

گزینه‌های ممکن تطبیق:

  1. Match C₁-T₁ (2), C₂-T₂ (2), C₃-T₃ (2) →\rightarrow Total weight = 6

  2. Match C₁-T₃ (1), C₂-T₂ (2), C₃-T₁ (1) →\rightarrow Total weight = 4

گزینهٔ اول تطبیق با بیشترین وزن را می‌دهد.

گام ۳: محاسبهٔ امتیاز بیشینهٔ تطبیق

match=Total matched weightn=2+2+210=0.6\text{match} = \frac{\text{Total matched weight}}{n} = \frac{2+2+2}{10} = 0.6
Optimal matching: [(np.int64(0), np.int64(0)), (np.int64(1), np.int64(1)), (np.int64(2), np.int64(2))]
Max weight: 6

مثال ۱۷.۱: خوشه‌بندی خوب در برابر بد روی دادهٔ زنبق

دو خوشه‌بندی مختلف از مجموعه‌دادهٔ زنبق را با مؤلفه‌های اصلی بررسی کنیم:

نتیجهٔ خوشه‌بندی خوب:

جدول توافقی

iris-setosairis-versicoloriris-virginicaTotal (n_i)
C₁ (squares)0471461
C₂ (circles)500050
C₃ (triangles)033639
Total (m_j)505050n = 150

Purity: 0.887
Match: 0.887
F: 0.885

نتیجهٔ خوشه‌بندی بد:

جدول توافقی

iris-setosairis-versicoloriris-virginicaTotal (n_i)
C₁ (squares)300030
C₂ (circles)204024
C₃ (triangles)0465096
Total (m_j)505050n = 150

Purity: 0.667
Match: 0.560
F: 0.658

بیشینه‌های سطر 30+20+50=10030+20+50=100 است، پس خلوص =100/150=0.667=100/150=0.667. بیشینهٔ تطبیق C1C_1–setosa (30)، C2C_2–versicolor (4) و C3C_3–virginica (50) را جفت می‌کند، پس match =84/150=0.560=84/150=0.560. خلوص و تطبیق اینجا فرق می‌کنند چون خلوص می‌تواند دو خوشه را به یک کلاس نسبت دهد ولی تطبیق نمی‌تواند.

۴. سنجه‌های جفتی

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

  • TP (مثبت‌های واقعی): جفت‌هایی در یک خوشه و در یک بخش واقعی

  • FP (مثبت‌های کاذب): جفت‌هایی در یک خوشه ولی در بخش‌های مختلف

  • TN (منفی‌های واقعی): جفت‌هایی در خوشه‌های مختلف و بخش‌های مختلف

  • FN (منفی‌های کاذب): جفت‌هایی در خوشه‌های مختلف ولی در یک بخش

با خوشه‌بندی C\mathbf{C} و افراز حقیقت‌مبنای T\mathbf{T}، بگذارید xi,xj∈D\mathbf{x}_i, \mathbf{x}_{j} \in \mathbf{D} دو نقطهٔ دلخواه با i≠ji \ne j باشند. yiy_i برچسب بخش واقعی و y^i\hat{y}_i برچسب خوشهٔ نقطهٔ xi\mathbf{x}_i را نشان دهد.

اگر xi\mathbf{x}_i و xj\mathbf{x}_{j} در یک خوشه باشند، یعنی y^i=y^j\hat{y}_i = \hat{y}_{j}، آن را رخدادی مثبت می‌نامیم، و اگر در یک خوشه نباشند، یعنی y^i≠y^j\hat{y}_i \ne \hat{y}_{j}، رخدادی منفی. بسته به توافق یا ناتوافقی برچسب‌های خوشه و بخش‌ها، چهار حالت پیش می‌آید:

مثبت‌های واقعی (TP)
xi\mathbf{x}_i و xj\mathbf{x}_{j} در T\mathbf{T} در یک بخش‌اند و در C\mathbf{C} هم در یک خوشه‌اند. تعداد جفت‌های مثبت واقعی چنین است:

TP=∣{(xi,xj):  yi=yj and y^i=y^j}∣\mathit{TP} = \bigl|\{(\mathbf{x}_i, \mathbf{x}_{j}):\; y_i = y_{j} \text{ and } \hat{y}_i = \hat{y}_{j} \}\bigr|

منفی‌های کاذب (FN)
xi\mathbf{x}_i و xj\mathbf{x}_{j} در T\mathbf{T} در یک بخش‌اند، ولی در C\mathbf{C} در یک خوشه نیستند. تعداد جفت‌های منفی کاذب چنین است:

FN=∣{(xi,xj):  yi=yj and y^i≠y^j}∣\mathit{FN} = \bigl|\{(\mathbf{x}_i, \mathbf{x}_{j}):\; y_i = y_{j} \text{ and } \hat{y}_i \ne \hat{y}_{j} \}\bigr|

مثبت‌های کاذب (FP)
xi\mathbf{x}_i و xj\mathbf{x}_{j} در T\mathbf{T} در یک بخش نیستند، ولی در C\mathbf{C} در یک خوشه‌اند. تعداد جفت‌های مثبت کاذب چنین است:

FP=∣{(xi,xj):  yi≠yj and y^i=y^j}∣\mathit{FP} = \bigl|\{(\mathbf{x}_i, \mathbf{x}_{j}):\; y_i \ne y_{j} \text{ and } \hat{y}_i = \hat{y}_{j} \}\bigr|

منفی‌های واقعی (TN)
xi\mathbf{x}_i و xj\mathbf{x}_{j} نه در T\mathbf{T} در یک بخش‌اند و نه در C\mathbf{C} در یک خوشه. تعداد چنین جفت‌های منفی واقعی چنین است:

TN=∣{(xi,xj):  yi≠yj and y^i≠y^j}∣\mathit{TN} = \bigl|\{(\mathbf{x}_i, \mathbf{x}_{j}):\; y_i \ne y_{j} \text{ and } \hat{y}_i \ne \hat{y}_{j} \}\bigr|

نگاه جفتی به سنجه‌های بیرونی

جاکارد و رند هر دو مسئلهٔ خوشه‌بندی را جور دیگری از جدول توافقی می‌بینند: به‌جای سنجیدن شناسه‌های خوشه با شناسه‌های کلاس، پرسشی دربارهٔ هر جفت نقطه می‌پرسند.

برای جفت (i, j) می‌توان دو پرسش بله/خیر پرسید:

  • آیا i و j در یک کلاس حقیقت‌مبنا هستند؟

  • آیا i و j در یک خوشه هستند؟

چهار حالت ممکن است:

same clusterdifferent cluster
same classTP (True Positive)FN (False Negative)
different classFP (False Positive)TN (True Negative)
  • TP — جفتی که در حقیقت‌مبنا و در خوشه‌بندی با هم‌اند.

  • TN — جفتی که در حقیقت‌مبنا و در خوشه‌بندی جدا از هم‌اند.

  • FP — جفتی که در حقیقت‌مبنا جدا است ولی خوشه‌بندی آن‌ها را ادغام کرده.

  • FN — جفتی که در حقیقت‌مبنا با هم است ولی خوشه‌بندی آن‌ها را شکسته است.

هر چه در پی می‌آید راه دیگری برای ترکیب این چهار شمارنده است.

ضریب جاکارد

Jaccard=TPTP+FN+FP\text{Jaccard} = \frac{TP}{TP + FN + FP}

شاخص رند

Rand=TP+TNTP+FN+FP+TN=TP+TN(n2)\text{Rand} = \frac{TP + TN}{TP + FN + FP + TN} = \frac{TP + TN}{\binom{n}{2}}

جاکارد در واقع چه چیزی را می‌سنجد

Jaccard=TPTP+FN+FP\text{Jaccard} = \frac{TP}{TP + FN + FP}

جاکارد فقط جفت‌های مثبت را می‌بیند — آن‌هایی که در دست‌کم یکی از دو افراز با هم‌اند — و می‌پرسد چه کسری از آن‌ها در هر دو با هم‌اند. شمارندهٔ TN کاملاً نادیده گرفته می‌شود.

چون TN با زیاد شدن تعداد خوشه‌ها بسیار سریع رشد می‌کند، نادیده‌گرفتنش انتخابی عامدانه است: جاکارد حتی وقتی تعداد خوشه‌ها زیاد است یا دو افراز تعداد گروه یکسان ندارند معنادار می‌ماند. از این نظر مقاوم‌ترین سنجهٔ جفتی است.

رند در واقع چه چیزی را می‌سنجد

Rand=TP+TNTP+FN+FP+TN=TP+TN(n2)\text{Rand} = \frac{TP + TN}{TP + FN + FP + TN} = \frac{TP + TN}{\binom{n}{2}}

رند هر دو نوع توافق را می‌شمارد: جفت‌هایی که در هر دو افراز با هم‌اند (TP) و جفت‌هایی که در هر دو افراز جدا هستند (TN). مخرج تعداد کل جفت‌هاست، پس رند می‌پرسد: در چه کسری از همهٔ جفت‌های ممکن، دو افراز هم‌نظرند؟

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

رند دقت نیست

در نگاه اول رند شبیه همتای خوشه‌بندیِ دقت است: هر دو تعداد «تصمیم‌های درست» را بر تعداد کل تصمیم‌ها تقسیم می‌کنند، هر دو در [0, 1] می‌افتند، و هر دو را در گفتار غیررسمی «درصد توافق» می‌نامند. ولی شباهت سطحی است. دقت و رند در سه اصل بنیادی فرق دارند.

۱. واحد شمرده‌شده فرق دارد.

دقت دربارهٔ هر نمونه می‌پرسد: آیا برچسب پیش‌بینی‌شده با برچسب واقعی یکی است؟ رند دربارهٔ هر جفت نقطه می‌پرسد: آیا این دو نقطه در دو افراز، یک سمت یکسانی دارند؟ یک خوشه‌بندی از n نقطه دارای n(n-1)/2 جفت است، پس رند به تعداد تصمیم‌هایی می‌رسد که با اندازهٔ مجموعه‌داده درجه‌دوم رشد می‌کنند. این‌ها اصلاً از یک جنس نیستند.

۲. تناظر یک‌به‌یک میان شناسه‌های خوشه و کلاس وجود ندارد.

در دسته‌بندی هر کلاس برچسبی معنادار و یگانه دارد. در خوشه‌بندی شناسه‌هایی که KMeans.labels_ می‌دهد دلبخواه‌اند: خوشهٔ 0 در یک اجرا ممکن است در اجرای بعد 1 باشد. دقت را نمی‌توان مستقیم روی شناسه‌های خوشه حساب کرد، چون برچسب حقیقت‌مبنایی برای سنجیدنشان نیست. رند کلاً از این مشکل می‌گریزد: هیچ‌جا از شناسه حرف نمی‌زند، فقط از رابطهٔ همان/متفاوت میان جفت‌ها، که نسبت به تغییر برچسب ناورداست.

۳. رند حتی وقتی k ≠ r باشد تعریف شده است.

دقت تعداد ثابتی کلاس را پیش‌فرض می‌گیرد. رند نه: چه الگوریتم خوشه بیشتری از تعداد کلاس‌ها ساخته باشد (بیش‌افرازی) و چه کمتر (کم‌افرازی)، کار می‌کند. همین باعث می‌شود رند در مثال‌هایی محاسبه‌شدنی بماند که دقت در آن‌ها اصلاً معنا ندارد.

تنها ضعفی که هر دو دارند. دقت روی دادهٔ نامتوازن گمراه‌کننده است: پیش‌بینی همه‌جا کلاس اکثریت امتیاز بالا می‌دهد بدون آنکه چیزی یاد بگیرد. رند همین ضعف را برای خوشه‌بندی‌هایی با گروه‌های زیاد دارد: هر چه k بزرگ‌تر شود، TN بر صورت غالب می‌شود و رند حتی برای برچسب‌گذاری تصادفی به یک نزدیک می‌شود. این دو سنجه هر یک جور دیگری شکست می‌خورند، ولی وقتی مسئله نامتوازن است هیچ‌کدام به‌تنهایی قابل اعتماد نیست.

شاخص رند تعدیل‌شده (ARI)

چون TN با بزرگ شدن k بسیار سریع رشد می‌کند، رند نسبت به تصادف تعدیل نشده: برچسب‌گذاری کاملاً تصادفی همان n نقطه با همان k خوشه از قبل مقدار رندِ مورد انتظار بالایی دارد. سنجه‌ای سودمند باید به چنین برچسب‌گذاری تصادفی صفر بدهد و تنها به یکی بی‌عیب یک.

شاخص رند تعدیل‌شده دقیقاً همین کار را می‌کند. مقداری را که رند در برچسب‌گذاری تصادفی انتظار می‌رود بگیرد کم می‌کند و بر بیشینهٔ تعدیل ممکن تقسیم می‌کند:

ARI=Rand−E[Rand]max⁡(Rand)−E[Rand]\text{ARI} = \frac{\text{Rand} - \mathbb{E}[\text{Rand}]} {\max(\text{Rand}) - \mathbb{E}[\text{Rand}]}

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

تفسیر ARI چنین است:

  • ARI = 1 — دو افراز یکی‌اند (به‌جز تغییر نام).

  • ARI = 0 — خوشه‌بندی از برچسب‌گذاری تصادفی با همان اندازهٔ خوشه‌ها بهتر نیست.

  • ARI < 0 — خوشه‌بندی از تصادفی بدتر است، که واقعاً می‌تواند پیش بیاید وقتی الگوریتم در اجراهای مختلف یک کلاس را همیشه به یک شکل می‌شکند.

در عمل ARI پیش‌فرض پیشنهادی برای سنجیدن دو افراز است، چون تنها سنجهٔ بیرونی رایجی است که هم‌زمان:

  • نسبت به تغییر نام خوشه‌ها ناورداست،

  • نسبت به تصادف تعدیل شده است،

  • وقتی k ≠ r تعریف شده است،

  • از بالا با یک کران دارد.

همچنین همان سنجه‌ای است که scikit-learn به‌طور پیش‌فرض با فراخوانی adjusted_rand_score(true_labels, cluster_labels) گزارش می‌کند.

اطلاعات متقابل نرمال‌شده (NMI)

رند و ARI بر جفت نقطه‌ها بنا شده‌اند. جانشین نظریهٔ اطلاعاتی می‌پرسد برچسب خوشه چقدر دربارهٔ کلاس واقعی می‌گوید. بگذارید H(C)H(\mathbf{C}) و H(T)H(\mathbf{T}) آنتروپی دو افراز باشند که از حاشیه‌های جدول توافقی برآورد می‌شوند، و I(C;T)I(\mathbf{C};\mathbf{T}) اطلاعات متقابل آن‌ها:

I(C;T)=∑i=1r∑j=1knijnlog⁡n nijni mj,NMI=I(C;T)H(C) H(T)∈[0,1]I(\mathbf{C};\mathbf{T}) = \sum_{i=1}^{r}\sum_{j=1}^{k} \frac{n_{ij}}{n} \log\frac{n\,n_{ij}}{n_i\,m_j}, \qquad \mathrm{NMI} = \frac{I(\mathbf{C};\mathbf{T})}{\sqrt{H(\mathbf{C})\,H(\mathbf{T})}} \in [0,1]

با قرارداد 0log⁡0=00\log 0 = 0. NMI دقیقاً وقتی یک است که دو افراز به‌جز تغییر نام یکی باشند، و صفر وقتی برچسب‌های خوشه هیچ اطلاعاتی دربارهٔ کلاس‌ها نداشته باشند. برای r≠kr \ne k هم خوش‌تعریف است و به تطبیق نیازی ندارد.

ضعفش این است که نسبت به تصادف تعدیل نشده: با خوشه‌های کوچک و زیاد، برچسب‌گذاری تصادفی از قبل NMI مثبتی می‌دهد و اندازهٔ این خط پایه به rr و kk بستگی دارد. پس مقدارها میان مسئله‌های مختلف قابل مقایسه نیستند، و همین دلیل ترجیح 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 برای رفعش طراحی شده است.

سنجه‌های درونی

سنجه‌های درونی فقط از داده D\mathbf{D} و افراز C\mathbf{C} بهره می‌برند: هیچ برچسب حقیقت‌مبنایی در کار نیست. پرسشی متفاوت از سنجه‌های بیرونی می‌پرسند — نه «آیا این گروه‌بندی واقعی است؟» بلکه «آیا این گروه‌بندی درونی منسجم است؟» — و مقدار بالا هرگز ثابت نمی‌کند خوشه‌ها معنایی دارند، فقط می‌گوید بر پایهٔ یک تعریف خاص جمع‌وجور و جدا هستند.

سنجه‌های نسبی، خانوادهٔ سوم، دو خوشه‌بندی از یک داده را با هم می‌سنجند، مثلاً یک الگوریتم با دو تنظیم پارامتر. فرمول جداگانه‌ای نیستند: هر سنجهٔ درونی یا بیرونی را می‌توان نسبی به کار برد، با داوری‌اش روی هر دو خوشه‌بندی و مقایسهٔ عددها. جاروب k=2,…,5k=2,\dots,5 در پایان این صفحه دقیقاً همین است.

۵. ضریب سیلوئت

سیلوئت برای هر نقطه فاصله‌اش تا خوشهٔ خودش را با فاصله‌اش تا نزدیک‌ترین خوشهٔ دیگر می‌سنجد. برای نقطهٔ xi\mathbf{x}_i در خوشهٔ CC بگذارید

  • aia_i میانگین فاصلهٔ xi\mathbf{x}_i تا نقطه‌های دیگر CC باشد (چسبندگی)؛

  • bib_i کمترین میانگین فاصلهٔ xi\mathbf{x}_i تا نقطه‌های خوشه‌ای دیگر باشد (جدایی).

آن‌گاه

si=bi−aimax⁡(ai, bi)∈[−1,1],s=1n∑i=1nsis_i = \frac{b_i - a_i}{\max(a_i,\,b_i)} \in [-1, 1], \qquad s = \frac{1}{n}\sum_{i=1}^{n} s_i

مقدار نزدیک یک یعنی نقطه به خوشهٔ خودش بسیار نزدیک‌تر از خوشهٔ بعدی است، نزدیک صفر یعنی خوشه‌ها به هم می‌رسند، و منفی یعنی نقطه احتمالاً در خوشهٔ اشتباه است. این امتیاز همهٔ فاصله‌های جفتی را لازم دارد، پس O(n2)O(n^2) هزینه دارد — روی زنبق به‌کارآمد و روی یک میلیون نقطه گران.

ویکی‌پدیا: سیلوئت

۶. SSE (اینرسی)

تابع هدف k-means خودش یک سنجهٔ درونی است:

SSE=∑i=1k∑x∈Ci∥x−μi∥2\mathrm{SSE} = \sum_{i=1}^{k}\sum_{\mathbf{x}\in C_i} \|\mathbf{x} - \mu_i\|^2

scikit-learn آن را KMeans.inertia_ گزارش می‌کند. دقیقاً همان کمیت k-Means است، پس ارزان است: بدون فاصلهٔ جفتی، یک گذر روی داده. دام این است که برای گزیدن kk به کار نمی‌آید: افزودن یک مرکز هرگز SSE را زیاد نمی‌کند، پس کمینه همیشه در k=nk = n است که SSE صفر می‌شود. قاعدهٔ معمول «آرنج» — kkای را بگیر که منحنی پس از آن صاف می‌شود — این را به یک تصمیم تبدیل می‌کند، ولی آرنج داوری چشمی است، و روی زنبق آرنج روشنی نیست.

۷. آمارهٔ شکاف

Tibshirani، Walther و Hastie (۲۰۰۱) آرنج چشمی را با مقایسه با نوفهٔ خالص جانشین می‌کنند. BB مجموعه‌دادهٔ مرجع را به‌طور یکنواخت روی جعبهٔ دربرگیرندهٔ داده بسازید، هر کدام را به kk گروه خوشه‌بندی کنید، و بگذارید

Wk=∑i=1k12ni∑x,x′∈Ci∥x−x′∥2,Gap(k)=E∗ ⁣[log⁡Wk]−log⁡WkW_k = \sum_{i=1}^{k} \frac{1}{2n_i}\sum_{\mathbf{x},\mathbf{x}'\in C_i} \|\mathbf{x} - \mathbf{x}'\|^2 , \qquad \mathrm{Gap}(k) = \mathbb{E}^{*}\!\left[\log W_k\right] - \log W_k

که E∗\mathbb{E}^{*} میانگین روی مجموعه‌داده‌های مرجع است. WkW_k پراکندگی جفتی درون‌خوشه‌ای است؛ بنا بر لم ۲ از k-Means همان SSE تقسیم بر nin_i است، پس شکاف منحنی مشاهده‌شده را با منحنی‌ای می‌سنجد که دادهٔ بی‌ساختار می‌دهد. کوچک‌ترین kkای را برگزینید که

Gap(k)  ≥  Gap(k+1)−sk+1,sk=sd∗ ⁣[log⁡Wk]1+1/B,\mathrm{Gap}(k) \;\ge\; \mathrm{Gap}(k+1) - s_{k+1}, \qquad s_k = \mathrm{sd}^{*}\!\left[\log W_k\right]\sqrt{1 + 1/B},

و اگر هیچ kkای آن را برآورده نکرد، k=1k = 1. هزینهٔ اضافه BB خوشه‌بندی برای هر kk نامزد است، و همین باعث می‌شود این قاعده کمتر از سیلوئت به کار رود.

مثال پایتون روی مجموعه‌دادهٔ زنبق

Loading...
Purity:    0.887
Jaccard:   0.682
Rand:      0.874   (3,030 agreement pairs out of 11,175)
ARI:       0.716
NMI:       0.742
SSE (inertia) of this k = 3 clustering : 78.9
silhouette coefficient (k = 3)         : 0.551

تفسیر نتیجه‌ها

  • خلوص، جاکارد، رند، ARI، NMI: بیشتر بهتر است، و 1 یعنی دو افراز توافق دارند (به‌جز تغییر نام). ARI و NMI را می‌توان میان مسئله‌ها مقایسه کرد؛ خلوص و رند را نه.

  • سیلوئت: در [−1,1][-1, 1]، بیشتر بهتر.

  • SSE: کمتر بهتر، ولی به‌حکم ساخت با kk کاهش می‌یابد، پس معیار گزیدن kk نیست.

از عددهای بالا دو هشدار برمی‌آید.

خلوص خوش‌بین است. روی زنبق با k=3k=3 خلوص نزدیک ۰٫۹ است، هرچند کلاس‌های versicolor و virginica اصلاً جدا نیستند: نقطه‌های این دو کلاس در هم‌اند و خلوص فقط می‌خواهد هر خوشه یک کلاس اکثریت داشته باشد. خوشه‌بندی‌ای که یک کلاس را به تکه‌های کوچک خالص بشکند، خلوص بالا جمع می‌کند بدون آنکه چیزی یافته باشد. ARI و NMI اینجا عددهای صادق‌اند.

هیچ سنجهٔ درونی‌ای به‌تنهایی تعداد واقعی خوشه‌ها را نمی‌یابد. جاروب سیلوئت در k=2k=2 اوج می‌گیرد (حدود ۰٫۶۸) در حالی که حقیقت‌مبنا سه کلاس دارد (حدود ۰٫۵۵). سیلوئت جدا‌شدنی درشت و خوب را پاداش می‌دهد، و «setosa در برابر بقیه» دقیقاً همان است: جواب دوگروهیِ بسیار تمیز که با این حال همان دسته‌بندی نیست. این درس کلیدی جلسه است — سنجهٔ درونی یک تعریف از خوشهٔ خوب را در خود دارد، نه حقیقت را. می‌توان آن را بهینه کرد، و بهینه‌کردنش می‌تواند جواب نادرست را برگزیند. چند سنجه را گزارش کنید، به داده نگاه کنید، و به سنجه‌ای اعتماد کنید که پرسش درونش همان پرسشی است که می‌پرسید.

شکل زیر با بستهٔ yellowbrick کشیده شده است (pip install yellowbrick)؛ امتیازهایی که چاپ می‌کند همان مقدارهای silhouette_score است که بالا حساب شد.

{2: 0.681, 3: 0.553, 4: 0.498, 5: 0.491}
<Figure size 1800x960 with 4 Axes>

منحنی SSE توضیح می‌دهد چرا قاعدهٔ آرنج قاعده نیست. کاهش تا k=3k=3 تند است و بعد صاف می‌شود، ولی هرگز متوقف نمی‌شود: در kk به‌قدر کافی بزرگ هر نقطه خوشهٔ خودش می‌شود و SSE دقیقاً صفر است.

<Figure size 840x480 with 1 Axes>
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

گزیدن سنجهٔ درست

  1. وقتی حقیقت‌مبنا در دسترس است از سنجه‌های بیرونی بهره ببرید

  2. وقتی برچسبی نیست از سنجه‌های درونی بهره ببرید

  3. برای داوری استوار چند سنجه را با هم ببینید

یادتان باشد هیچ سنجهٔ واحدی کل داستان را نمی‌گوید — سنجه‌های مختلف برای هدف‌های مختلف خوشه‌بندی مناسب‌ترند.

مسئلهٔ تخصیص در پس بیشینهٔ تطبیق

بیشینهٔ تطبیق با وزن نمونه‌ای از مسئلهٔ تخصیص است: با جدول توافقی r×kr \times k، جفت‌شدن یک‌به‌یک سطرها و ستون‌ها را برگزینید که وزن کل بیشینه شود. برای جدول‌های مربع، الگوریتم مجارستانی دقیقاً حلش می‌کند، که scipy.optimize.linear_sum_assignment پیاده‌سازی‌اش است؛ برای جدول‌های مستطیلی همان رویه جفت‌شدن بهینه‌ای برمی‌گرداند که سطرها یا ستون‌های اضافه را بی‌جفت می‌گذارد، و همین چیزی است که وقتی r≠kr \ne k می‌خواهیم.

همین مسئله هر جا دو مجموعه باید با قید یک‌به‌یک جفت شوند پیش می‌آید: دانش‌آموزان به مدرسه‌ها، داوران به مقاله‌ها، پرسش‌ها به سندها، یا ویژگی‌ها به مؤلفه‌ها. فصل ۱۷ زکی آن را برای اعتبارسنجی خوشه‌بندی گسترش می‌دهد؛ بحث کلی در همان کتاب است (zaki2020data).

تطبیق با بیشترین وزن با networkx

جدول توافقی را می‌توان گرافی دوبخشی هم خواند: خوشه‌ها یک سو، کلاس‌ها سوی دیگر، و یالی با وزن nijn_{ij} هر جا nij>0n_{ij} > 0 باشد. امتیاز بیشینهٔ تطبیق آن‌گاه وزن یک تطبیق با بیشترین وزن در همان گراف است.

networkx.algorithms.matching.max_weight_matching مسئلهٔ کلی را حل می‌کند؛ به گراف دوبخشی محدود نیست، پس اگر گراف یالی درون یک بخش داشته باشد ممکن است از آن بهره ببرد. اینجا هر یال یک خوشه را به یک کلاس می‌پیوندد، پس نتیجه تطبیقی در گراف دوبخشی است. weight="weight" را صریح بدهید — با پیش‌فرض weight=None وزن یال‌ها نادیده گرفته می‌شود و رویه تطبیقی با بیشترین تعداد یال برمی‌گرداند، که نسخهٔ پیشین این صفحه به‌اشتباه همین کار را می‌کرد.

matched pairs and weights:
  C2 - versicolor: 4
  virginica - C3: 50
  C1 - setosa: 30

matched weight = 84   match score = 0.560
<Figure size 720x480 with 1 Axes>

خلاصه

  • خوشه‌بندی اعتبارسنجی می‌خواهد: بی برچسب، «همگرا شد» هیچ چیزی دربارهٔ کیفیت نمی‌گوید.

  • سنجه‌های بیرونی از جدول توافقی r×kr \times k، یعنی nijn_{ij} (سطر = خوشه، ستون = کلاس) آغاز می‌شوند که در O(n)O(n) حساب می‌شود.

  • خلوص مجموع بیشینه‌های سطرهاست؛ خوش‌بین است، چون اجازه می‌دهد دو خوشه یک کلاس را ادعا کنند.

  • دقت، بازآوری و F نگاه ستونی را می‌افزایند؛ بیشینهٔ تطبیق جفت‌شدن یک‌به‌یک را تحمیل می‌کند و یک مسئلهٔ تخصیص است (linear_sum_assignment).

  • سنجه‌های جفتی توافق‌ها را روی جفت نقطه‌ها می‌شمارند: جاکارد TNTN را نادیده می‌گیرد، رند همه چیز را می‌شمارد و با kk باد می‌کند، ARI رند را نسبت به تصادف تعدیل می‌کند، NMI اطلاعات مشترک را می‌سنجد ولی تعدیل نشده است.

  • سنجه‌های درونی — سیلوئت، SSE، شکاف — فقط از داده بهره می‌برند؛ هیچ‌کدام تعداد واقعی خوشه‌ها را مشخص نمی‌کند، و بهینه‌کردن یکی از آن‌ها می‌تواند جواب نادرست بدهد.

  • چند سنجه را گزارش کنید و بگویید هر کدام به کدام پرسش پاسخ می‌دهد.