خوشه بندی کلاس مهمی از یادگیری بدون ناظر است. الگوریتم خوشه بندی، خوشه (یا گروه) داده ها را بر اساس شباهت بین آنها خوشه بندی می کند. این گروه بندی از طبقه بندی (classification) متفاوت است. بر خلاف طبقه بندی، گروه ها از پیش تعریف نشده است.

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

یادگیری بدون ناظر (unsupervised learning) : در این نوع از الگوریتم‌ها، متغیر هدف نداریم و خروجی الگوریتم، نامشخص است. بهترین مثالی که برای این نوع از الگوریتم ها می توان زد، گروه بندی خودکار (خوشه بندی) یک جمعیت است مثلاً با داشتن اطلاعات شخصی و خریدهای مشتریان، به صورت خودکار آنها را به گروه های همسان و هم ارز تقسیم کنیم. الگوریتم Apriori و K-Means از این دسته هستند.

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

شاخص­ های اعتبار سنجی برای میزان صحت نتایج خوشه بندی به منظور مقایسه بین روش­های خوشه بندی مختلف یا مقایسه ­ی نتایج حاصل از یک روش با پارامترهای مختلف مورد استفاده قرار می ­گیرند که یکی از این شاخص­ ها، شاخص دیویس بولدین (Davies Bouldin index) می­ باشد. شاخص دیویس بولدین (Davies Bouldin index) از شباهت بین دو خوشه (Rij) استفاده می­ کند که بر اساس پراکندگی یک خوشه (Si) و عدم شباهت بین دو خوشه (Dij) تعریف می ­شود.

اندازه پراکندگی درون خوشه

فرض کنید Si میزان پراکندگی مربوط به خوشه Ci و d نیز یک تابع فاصله باشد. آنگاه میزان پراکندگی برای این خوشه توسط رابطه زیر قابل محاسبه است :

`S_i=[\frac{1}{|C_i|}\sum_{x\in c_i$$} d^r(x,c_i)]^{(\frac{1}{r})},   r>0`

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

عدم شباهت (فاصله) بین خوشه‌ها

فاصله بین دو خوشه نیز بر اساس فاصله بین دو نقطه مرکزی آن‌ها سنجیده می‌شود. اگر Vi و Vj‌ مراکز خوشه‌های i و j باشند، فاصله بین این دو خوشه با Dij نشان داده شده و توسط رابطه زیر بدست می‌آید:

`D_{ij}=[\sum d(V_i,V_j)^t]^{\frac{1}{t}}`

باز هم به نظر می‌رسد از فاصله مینکوفسکی برای سنجش فاصله بین دو خوشه استفاده شده است. حال با توجه به این دو مفهوم می‌توان میزان فاصله بین دو خوشه Ci و Cj را که با Rij نشان می‌دهیم به صورت زیر محاسبه کنیم :

`R_{ij}=\frac{S_i+S_j}{D_{ij}}`

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

`R_i=\max_{j\ne i}R_{ij}`

سپس میانگین بیشینه فاصله‌های محاسبه شده برای همه خوشه‌های ایجاد شده توسط الگوریتم را محاسبه می‌کنیم. این شاخص را با VDB نشان می‌دهند.

`V_{DB}=\frac{\sum_{i=1}^k R_i}{k}`

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

davies bouldin example

نمودار (1) مثال مقادیر دیویس بولدین مقاله درمحمدی و همکاران (1393)

برای مثال در مقاله درمحمدی و همکاران (1393) K=5 به دلیل کمتر بودن شاخص دیویس بولدین انتخاب می شود.