شاخص دیویس بولدین

شاخص دیویس بولدین (DBI) که توسط David L. Davies و Donald W. Bouldin در سال ۱۹۷۹ معرفی شد، روشی برای ارزیابی الگوریتم‌های خوشه‌بندی است. یک روش ارزیابی درونی، که در آن از مقادیر و ویژگی های ذاتی مجموعه داده استفاده می‌شود. اشکال این روش این است که وقتی یک مقدار خوب توسط این روش برای ارزیابی خوشه‌بندی گزارش می‌شود به این معنا نیست که بهترین اطلاعات موجود، مورد استفاده قرار گرفته‌اند.

مقدمات

تعدادی داده n بعدی داریم. C_i را خوشه ای از این داده‌ها و X_j را یک بردار ویژگی n بعدی که به خوشه C_i نسبت داده شده است، در نظر میگیریم.

$S_{i}=\left({\frac {1}{T_{i}}}\sum _{j=1}^{T_{i}}{\left|\left|X_{j}-A_{i}\right|\right|_{p}^{q}}\right)^{1/q}$

$A_{i}$، مرکز C _i و T _i، اندازه خوشه‌ی i است . $S_{i}$ ریشه‌ی q، از گشتاور مرتبه q، در داده‌های خوشه i، حول میانگین می‌باشد. اگر $q=1$ باشد‌‌، آنگاه $S_{i}$ میانگین فاصله‌ی بین بردارهای ویژگی در خوشه i و مرکز خوشه i است. معمولا مقدار p برابر ۲ است و یعنی فاصله در اینجا بر اساس تابع فاصله اقلیدسی عمل میکند. در موارد متنوع و داده های ابعاد بالاتر، جایی که ممکن است فاصله اقلیدسی بهترین معیار برای تشخیص خوشه‌ها نباشد، میتوان از معیارهای فاصله دیگری استفاده کرد. توجه به این نکته مهم است که برای نتایج معنادار، این معیار فاصله باید با معیار استفاده شده در خود روش خوشه بندی مطابقت داشته باشد.

$M_{i,j}=\left|\left|A_{i}-A_{j}\right|\right|_{p}={\Bigl (}\displaystyle \sum _{k=1}^{n}\left|a_{k,i}-a_{k,j}\right|^{p}{\Bigr )}^{\frac {1}{p}}$

$M_{i,j}$ معیار اندازه گیری فاصله بین خوشه $C_{i}$ و $C_{j}$ است.

$a_{k,i}$، k امین عنصر $A_{i}$ است و n عنصر مانند آن در A وجود دارند، زیرا A یک مرکز خوشه‌ی n بعدی است.

در اینجا k ویژگی‌های داده‌ها را نشان میدهد و وقتی p برابر 2 باشد، اساساً فاصله اقلیدسی بین مراکز خوشه‌های i و j را نشان میدهد.

تعریف

R_i,j را معیاری برای ارزیابی خوشه بندی در نظر میگیریم. این معیار بر اساس تعریف باید M_i,j و S_i را محاسبه کند که M_i,j فاصله بین خوشه i و j را نشان میدهد و در حالت ایدئال تا حد امکان باید بزرگ باشد، و S_i پراکندگی درونی خوشه i را نشان میدهد و تا حد امکان باید کوچک باشد. بنابراین شاخص دیویس بولدین به عنوان نسبت S_i و M_i,j طوری تعریف میشود که ویژگی های زیر حفظ شوند:

1. $R_{i,j}\geqslant 0$ .
2. $R_{i,j}=R_{j,i}$ .
3. وقتی $S_{j}\geqslant S_{k}$ و $M_{i,j}=M_{i,k}$ آنگاه داشته باشیم $R_{i,j}>R_{i,k}$ .
4. وقتی $S_{j}=S_{k}$ و $M_{i,j}\leqslant M_{i,k}$ آنگاه داشته باشیم $R_{i,j}>R_{i,k}$ .

با این محدودیت‌ها، هرچه مقدار R_i,j کمتر باشد، جداسازی خوشه‌ها بهتر و «سختی» درون خوشه‌ها بیشتر است.

روشی برای محاسبه‌ی R_i,j که محدودیت‌های بالا برقرار باشد داریم:

$R_{i,j}={\frac {S_{i}+S_{j}}{M_{i,j}}}$

برای تعریف D_i داریم:

$D_{i}\equiv \max _{j\neq i}R_{i,j}$

اگر N تعداد خوشه ها باشد:

${\mathit {DB}}\equiv {\frac {1}{N}}\displaystyle \sum _{i=1}^{N}D_{i}$

DB شاخص دیویس بولدین نامیده می شود. که هم به داده ها و هم به الگوریتم وابسته است. D_i بدترین حالت(بیشترین مقدار R_i,j) را انتخاب می کند یعنی شبیه‌ترین خوشه به خوشه i را در نظر میگیرد. تغییرات زیادی میتواند در این فرمول وجود داشته باشد، مانند استفاده از میانگین شباهت خوشه‌ها، میانگین وزنی و غیره.

توضیح

این شرایط شاخص تعریف شده را به متقارن و غیر منفی بودن، محدود می کند. با توجه به نحوه تعریف شاخص، به عنوان تابعی از نسبت پراکندگی درون خوشه به فاصله‌ی خوشه‌ها، مقدار کمتر آن به این معنی است که خوشه بندی بهتر انجام شده است. در واقع این شاخص شباهت بین هر خوشه و مشابه ترین خوشه‌ی آن به صورت میانگین است که این میانگین روی همه خوشه ها گرفته شده است، جایی که شباهت به صورت S _i در بالا تعریف شده است. این امر این ایده را تأیید می کند که هیچ خوشه ای نباید شبیه به دیگری باشد، و از این رو بهترین خوشه بندی اساساً شاخص دیویس بولدین را به حداقل مقدار می رساند. این شاخص که به این ترتیب تعریف می‌شود میانگینی است برای همه خوشه‌های i ، و از این رو یک معیار خوب برای تصمیم‌گیری اینکه واقعاً چند خوشه در داده‌ها وجود دارد، نمودار مقدار شاخص و مقدار i (تعداد خوشه‌هایی که روی آنها محاسبه انجام شده است) می‌باشد. جایی که مقدار شاخص کمترین است، عدد i معیار خوبی برای تعداد خوشه‌ها است که داده‌ها را می‌توان به طور ایدئال طبقه‌بندی کرد. این مبحث در تعیین مقدار k در الگوریتم k میانگین کاربرد دارد، جایی که مقدار k از قبل مشخص نیست.

پیاده سازی ها

جعبه ابزار SOM شامل پیاده سازی متلب است. یک پیاده‌سازی متلب نیز از طریق جعبه ابزار آمار و یادگیری ماشین متلب با استفاده از دستور "evalcluster" در دسترس است.

یک پیاده سازی جاوا در ELKI یافت شده است و می توان آن را با بسیاری از شاخص های کیفیت خوشه بندی دیگر مقایسه کرد.

مقالات مرتبط

• سیلوئت (خوشه بندی)
• شاخص دان

لینک‌های خارجی

• http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.2072
• https://books.google.com/books?id=HY8gB2OIqSoC
• http://nl.mathworks.com/help/stats/clustering.evaluation.daviesbouldinevaluation-class.html