اطلاعات متقابل تنظیم شده

در نظریه احتمالات و نظریه اطلاعات، اطلاعات متقابل تنظیم شده، ممکن است تغییر نسخه ای از اطلاعات متقابل برای مقایسه خوشه‌بندی‌ها استفاده شود.^[۱] اثر توافق را صرفاً به دلیل شانس بین خوشه‌بندی‌ها تصحیح می‌کند، مشابه روشی که شاخص رند تنظیم‌شده، شاخص رند را تصحیح می‌کند. ارتباط نزدیکی با تنوع اطلاعات دارد:^[۲] هنگامی که تنظیم مشابهی برای شاخص VI انجام می‌شود، معادل AMI می‌شود.^[۱] با این حال، اندازه‌گیری تنظیم شده دیگر متریک نیست.^[۳]

اطلاعات متقابل دو بخش

با توجه به مجموعه S از N عنصر S = {s₁,s₂... ,s_N}، دو بخش از S را در نظر بگیرید، برای مثال U = {u₁,u₂... ,u_R} با R خوشه،

و V = {v₁,v₂... ,v_C} با C خوشه. در اینجا فرض می‌شود که بخش‌ها به اصطلاح خوشه‌های سخت هستند. بخش‌ها به صورت جفتی جدا هستند:

${\displaystyle U_{i}\cap U_{j}=\varnothing =V_{i}\cap V_{j}}$

به ازای همه ${\displaystyle i\neq j}$ :

${\displaystyle \bigcup _{i=1}^{R}U_{i}=\bigcup _{j=1}^{C}V_{j}=S}$

اطلاعات متقابل همپوشانی خوشه بین U و V را می‌توان در قالب یک جدول احتمالی RxC خلاصه کرد. که در آن ${\displaystyle n_{i,j}}$ تعداد اشیاء مشترک در خوشه‌های U_i و V_j را نشان می‌دهد. به این معنا که،

${\displaystyle n_{i,j}=|U_{i}\cap V_{j}|}$

فرض کنید یک شی به‌طور تصادفی از S انتخاب شده‌است. احتمال اینکه جسم به خوشه U_i بیفتد این است:

${\displaystyle P_{U}(i)={\operatorname {|U_{i}|} \over \operatorname {N} }}$

آنتروپی مرتبط با بخش‌بندی U عبارت است از:

${\displaystyle H(V)=-\textstyle \sum _{i=1}^{R}\displaystyle P_{U}(i)logP_{U}(i)}$

که در آن P_V(j) = |V_j|/N. اطلاعات متقابل بین دو بخش:

${\displaystyle MI(U,V)=\sum _{i=1}^{R}\sum _{j=1}^{C}P_{i,j}(i,j)log{P_{U,V}(i,j) \over P_{U}(i)P_{V}(j)}}$

که در آن P_UV(i,j) نشان دهنده این احتمال است که یک نقطه به خوشه U_i در U و خوشه V_j در V تعلق دارد:

${\displaystyle P_{U,V}(i,j)={\operatorname {|U_{i}\cap V_{j}|} \over \operatorname {N} }}$

MI یک کمیت غیر منفی است که با آنتروپی‌های H(U) و H(V) محدود شده‌است، اطلاعات به اشتراک گذاشته شده توسط دو خوشه بندی را کمی می‌کند و بنابراین می‌تواند به عنوان معیار تشابه خوشه بندی استفاده شود.

تعدیل برای شانس

مانند شاخص رند، مقدار پایه اطلاعات متقابل بین دو خوشه‌بندی تصادفی مقدار ثابتی به خود نمی‌گیرد و زمانی که دو پارتیشن تعداد خوشه‌های بیشتری داشته باشند (با تعداد ثابتی از عناصر مجموعه N) تمایل به بزرگ‌تر شدن دارد. با اتخاذ یک مدل فوق هندسی تصادفی، می‌توان نشان داد که اطلاعات متقابل مورد انتظار بین دو خوشه تصادفی عبارتند از:

${\displaystyle E[{MI(U,V)}]=\sum _{i=1}^{R}\sum _{j=1}^{C}\sum _{n_{i,j}=(a_{i}+b_{j}-N)^{+}}^{min(a_{i},b_{j})}{\operatorname {n_{i,j}} \over \operatorname {N} }log{\Biggl (}{\operatorname {N.n_{i,j}} \over \operatorname {a_{i}b_{j}} }{\Biggr )}\times {\operatorname {a_{i}!b_{j}!(N-a_{i})!(N-b_{j})!} \over \operatorname {N!n_{i,j}!(a_{i}-n_{i,j})!(b_{j}-n_{i,j})!(N-a_{i}-b_{j}+n_{i,j})!} }}$

هنگامی که دو پارتیشن یکسان هستند، AMI مقدار ۱ و زمانی که MI بین دو پارتیشن برابر با مقدار مورد انتظار بنابر شانس باشد، ۰ می‌گیرد.

منابع

1. Vinh, N. X.; Epps, J.; Bailey, J. (2009). "Information theoretic measures for clusterings comparison". Proceedings of the 26th Annual International Conference on Machine Learning - ICML '09. p. 1. doi:10.1145/1553374.1553511. ISBN 978-1-60558-516-1.
2. Meila, M. (2007). "Comparing clusterings—an information based distance". Journal of Multivariate Analysis. 98 (5): 873–895. doi:10.1016/j.jmva.2006.11.013.
3. Vinh, Nguyen Xuan; Epps, Julien; Bailey, James (2010), "Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance" (PDF), The Journal of Machine Learning Research, 11 (oct): 2837–54