تعیین تعداد بهینه خوشه ها در پروژه های داده کاوی همواره یکی از چالش‌های اصلی پیاده سازی الگوریتم های خوشه بندی مبتنی بر تقسیم یا به عبارتی Partitioning Clustering مانند k-means است که در آنها کاربر باید تعداد خوشه ها، که معمولا با مقدار k نشان داده می‌شود را تعیین کند.
تعداد بهینه خوشه ها در الگوریتم های خوشه بندی کدام است؟
متاسفانه جواب قطعی برای تعیین تعداد بهینه خوشه ها در الگوریتم های خوشه بندی وجود ندارد! تعیین تعداد بهینه خوشه ها از سویی تابع معیار در نظر گرفته شده به عنوان معیار شباهت بین داده ها در الگوریتم خوشه بندی است و از سوی دیگر تابع پارامترهای تنظیم شده در الگوریتم موردنظر است. یک روش ساده و رایج بین کاربران، بررسی دندروگرام حاصل از یک الگوریتم خوشه بندی سلسله مراتبی مانند Agglomerative است تا از این طریق، در صورت حصول یک مقدار خاص برای خوشه ها از آن تعداد به عنوان مقدار k در الگوریتم های خوشه بندی مبتنی بر تقسیم استفاده شود. اما این روش، فاقد پشتوانه‌ی ریاضی و اثباتی قوی است.
تشریح روش های تعیین تعداد بهینه خوشه ها در الگوریتم های k-means ، k-medoids و خوشه بندی سلسله مراتبی
در این نوشتار، به تشریح روش های تعیین تعداد بهینه خوشه ها در الگوریتم های k-means ، k-medoids و خوشه بندی سلسله مراتبی خواهیم پرداخت.
روش های تعیین تعداد بهینه خوشه ها به دو دسته کلی روش های مستقیم یا Direct Methods و روش های مبتنی بر آزمون های آماری یا Statistical Testing Methods تقسیم می‌شوند:
روش های مستقیم تعیین تعداد بهینه خوشه ها در الگوریتم های خوشه بندی: این روش ها به دنبال بهینه سازی یک معیار به‌خصوص، مانند مجموع مربعات فواصل درون خوشه ای (Within-cluster Sum of Square یا WSS) یا سیلوئت میانگین (Average Silhouette) هستند. از جمله این متدها می‌توان به متد elbow و روش های مبتنی بر معیار silhouette اشاره کرد.
روش های مبتنی بر آزمون های آماری در تعیین تعداد بهینه خوشه ها در الگوریتم های خوشه بندی: این متدها به دنبال تطبیق مشاهدات با فرض صفر یک آزمون آماری هستند. از جمله این روش ها می‌توان به Gap Statistics اشاره کرد.
علاوه بر متدهای elbow، silhouette و gap statistics، بیش از 30 مورد روش و شاخص مختلف برای تعیین تعداد بهینه خوشه ها در مقالات مختلف ارائه شده است. در این مقاله با استفاده از زبان برنامه نویسی R و اجرای تنها یک تابع، به محاسبه هم‌زمان تعدادی از این روش‌ها و ارائه نتایج آنها پرداخته‌ایم.
پس از اجرای تابع، «قانون اکثریت» یا Majority Rule، تعداد بهینه خوشه ها را تعیین می‌کند. به عبارت دیگر تعداد بهینه خوشه ها، مقداری از k است که تعداد بیشتری از متدهای اجرا شده، آن را به عنوان خروجی ارائه کرده‌اند.
برای هر یک از 3 متد ذکر شده، موارد زیر پوشش داده شده است:
• ارایه ایده الگوریتم و مراحل آن
• پیاده‌سازی الگوریتم طرح شده در غالب کدهای R و ارایه مثال‌هایی از اجرای آنها برای تعیین تعداد بهینه خوشه ها
متد elbow
همانطور که می‌دانیم ایده اصلی روش های خوشه بندی مبتنی بر تقسیم مانند k-means به دست آوردن تعداد خوشه ها به نحوی است که مجموع فواصل درون خوشه ای داده ها (یا مجموع مربعات فواصل درون خوشه ای) حداقل شود. مجموع فواصل درون خوشه ای داده ها، میزان فشردگی خوشه بندی انجام شده را نشان می‌دهد و هدف، حداقل سازی آن تا جای ممکن است.
روش elbow، مجموع فواصل درون خوشه ای داده ها را به عنوان تابعی از تعداد خوشه ها در نظر می‌گیرد. به این ترتیب تعداد خوشه ها به نحوی انتخاب می‌شوند که افزودن یک خوشه دیگر، بهبودی در حداقل‌سازی WSS ایجاد نکند.
تعداد بهینه خوشه ها طبق الگوریتم زیر به‌دست می‌آید:
1- اجرای الگوریتم خوشه بندی مانند k-means برای مقادیر متفاوت k (به‌طور مثال با در نظر گرفتن مقدار k در بازه 1 تا 10)
2- محاسبه مقدار WSS برای هر مقدار k
3- رسم مقدار WSS بر حسب مقادیر مختلف k
4- نقطه زانوئی نمودار رسم شده، تعداد بهینه خوشه ها را نشان می‌دهد.
متد silhouette میانگین
تمرکز معیار سیلوئت بر کیفیت خوشه بندی انجام شده متکی است. در واقع این معیار مشخص می‌کند که پراکندگی داده ها در خوشه ها به چه صورت است. هر چه مقدار سیلوئت بالاتر باشد، کیفیت خوشه بندی نیز بالاتر است.
در متد سیلوئت میانگین ، الگوریتم خوشه بندی به ازای مقادیر مختلف k اجرا شده و به‌ازای هر اجرا، معیار سیلوئت برای هر یک از اعضای خوشه ها محاسبه می‌شود. سپس از سیلوئت های به‌دست آمده معدل گرفته می‌شود. مقدار بهینه k مقداری است که به ازای آن، سیلوئت میانگین ماکزیمم شود.
الگوریتم این متد مشابه روش elbow بوده و می‌توان آن را به صورت زیر نوشت:
1- اجرای الگوریتم خوشه بندی مانند k-means برای مقادیر متفاوت k (به طور مثال با در نظر گرفتن مقدار k در بازه 1 تا 10)
2- محاسبه مقدار سیلوئت هر یک از مشاهدات برای هر مقدار k و محاسبه میانگین آنها
3- رسم مقدار میانگین سیلوئت بر حسب مقادیر مختلف k
4- نقطه ماکزیمم نمودار رسم شده، تعداد بهینه خوشه ها را نشان می‌دهد.
متد Gap Statistics
این روش می‌تواند بر انواع مختلف الگوریتم های خوشه بندی اعمال شود. متد Gap Statistics به‌ازای هر یک از مقادیر در نظر گرفته شده برای k، مجموع تفاضلات درون خوشه ای داده ها را با مقادیر مورد انتظار آنها (توزیع داده ها با فرض درست بودن فرض صفر) مقایسه می‌کند. مقدار بهینه خوشه ها، مقداری است که آماره gap را ماکزیمم کند. این به آن معناست که ساختار خوشه بندی از توزیع یکنواخت تصادفی داده ها دور است.
الگوریتم این روش را می‌توان به فرم زیر نوشت:
1- خوشه بندی داده ها با در نظر گرفتن مقدار k در بازه 1 تا kmax . محاسبه مقدار تفاضلات درون خوشه ای برای هر یک از اجراها و قرار دادن آن در متغیر Wk
2- تولید تعداد B مجموعه داده از مجموعه داده های اصلی، به نحوی که دارای توزیع یکنواخت تصادفی باشند. خوشه بندی هر یک از این B مجموعه داده به‌ازای مقادیر مختلف k (در بازه 1 تا kmax ). محاسبه مقدار تفاضلات درون خوشه ای برای هر یک از اجراها و قرار دادن آن در متغیر Wkb
3- محاسبه آماره gap به صورت تفاضل مقادیر مشاهده شده Wk از مقادیر مورد انتظار آنها تحت فرض صفر Wkb و نیز محاسبه انحراف معیار آماره به‌دست آمده:
4- انتخاب تعداد بهینه خوشه ها به صورت کم‌ترین مقدار k بهطوریکه Gap(k)≥Gap(k+1)-sk+1
محاسبه تعداد بهینه خوشه ها در الگوریتم داده کاوی خوشه بندی با استفاده از زبان برنامه نویسی R
در این بخش به توصیف دو مورد از توابع زبان R که در تعیین تعداد بهینه خوشه ها در داده کاوی مورد استفاده قرار می‌گیرند می‌پردازیم:
1. تابع ()fviz_nbclust (در پکیج factoextra): از این تابع می‌توان در محاسبه هر یک از سه متد elbow، silhouette و gap statistics استفاده کرد. هم‌چنین این تابع قابلیت به‌کارگیری در انواع مختلف توابع خوشه بندی مبتنی بر تقسیم (مانند k-means، k-medoids (PAM)، CLARA و HCUT) را دارد. ذکر این نکته ضروری است که تابع ()hcut تنها از طریق پکیج factoextra قابل دسترسی است. این تابع خوشه بندی سلسله مراتبی بر روی داده ها انجام داده و درخت به‌دست آمده را به k خوشه تقسیم می‌کند و k مقداری از پیش تعیین شده است.
2. تابع ()NbClust (در پکیج NbClust): این تابع در داده کاوی برای تعیین تعداد بهینه خوشه ها، تعداد 30 شاخص مختلف را (تنها در یک بار اجرای تابع) برای خوشه بندی داده ها اجرا می‌کند. کاربر با دستکاری متغیرهایی چون تعداد خوشه ها، معیار محاسبه فاصله بین داده ها و روش خوشه بندی مورد استفاده، بهترین الگوی خوشه بندی را به عنوان خروجی تابع خواهد داد. تنها با یک بار اجرای این تابع، مقادیر بهینه این شاخص ها محاسبه شده و تعداد بهینه خوشه ها تعیین می‌شود.
پکیج‌های مورد نیاز در زبان برنامه نویسی R جهت تعیین تعداد خوشه ها
برای استفاده از توابع موجود در R جهت تعیین تعداد بهینه خوشه ها دو پکیج زیر در دسترس هستند:
• پکیج factoextra برای تعیین تعداد بهینه خوشه ها در الگوریتم خوشه بندی که به این پکیج داده می‌شود، و مصورسازی نتایج
• پکیج NbClust برای محاسبه 30 روش به طور هم‌زمان و تنها با یک بار اجرا، به منظور تعیین تعداد بهینه خوشه ها با تنها یک بار اجرای توابع این پکیج بر روی داده ها اجرا می‌کند.
برای نصب این پکیج‌ها به صورت زیر عمل می‌کنیم:
برای بارگذاری این پکیج‌ها نیز از دستورات زیر استفاده می‌کنیم:
آماده سازی داده ها
در این نوشتار از مجموعه داده های USArrests برای اجرای مدل ها و نمایش نتایج استفاده شده است. قبل از هر چیز با استفاده از دستورات زیر داده ها نرمال سازی شده‌اند تا امکان مقایسه فیلدهای داده‌ای با هم میسر شود:
نمایی از داده ها پس از نرمال سازی به شکل زیر است:
استفاده از تابع fviz_nbclust در محاسبه متدهای elbow، silhouette و gap statistics
شکل کلی این تابع به صورت زیر است:
;
در این تابع داریم:
• x: یک ماتریس عددی یا یک دیتا فریم
• FUNcluster: یک تابع تقسیم بندی. مقادیر مجاز این پارامتر عبارتنداز: kmeans، pam، clara و hcut (برای خوشه بندی سلسله مراتبی)
• Method: روش مورد نظر در تعیین تعداد بهینه خوشه ها
تعداد بهینه خوشه ها در الگوریتم خوشه بندی k-means به کمک کد زیر در زبان برنامه نویسی R محاسبه می‌شود:
برای اجرای این کد مقدار Kmax = 10 و B = 50 در نظر گرفته شده است. نتایج به‌دست آمده به شرح زیر است:
## Clustering k = 1,2,..., K.max (= 10): .. done
## Bootstrapping, b = 1,2,..., B (= 50) [one "." per sample]:
## .................................................. 50
بر این اساس می‌توان k=4 را به عنوان تعداد بهینه خوشه ها در نظر گرفت.
تابع NbClust: سی (30) شاخص در انتخاب بهترین تعداد خوشه ها
شکل کلی این تابع به صورت زیر است:
• data: ماتریس ورودی
• diss: ماتریس تفاضلات. مقدار این پارامتر به صورت پیش فرض NULL است. چنانچه از مقدار دیگری برای این پارامتر استفاده شود، مقدار پارامتر distance را NULL قرار می‌دهیم.
• distance: معیار محاسبه فاصله بین داده ها در ماتریس تفاضلات. مقادیر مجاز این پارامتر عبارتنداز:
"euclidean"، "manhattan" و "NULL"
• min.nc و max.nc: مینیمم و ماکزیمم تعداد خوشه های در نظر گرفته شده برای اجرای تابع
• method: متد خوشه بندی مورد استفاده در اجرای تابع. این پارامتر مقادیری چون "ward.D"، "ward.D2"، "single"، "complete"، "average"، "kmeans" و ... را می‌پذیرد.
• برای محاسبه تابع ()NbClust بر روی متد kmeans پارامتر method را به صورت "method="kmeans تنظیم می‌کنیم.
• برای محاسبه تابع ()NbClust بر روی متدهای خوشه بندی سلسله مراتبی، پارامتر method به صورت زیر تنظیم می‌شود:
method = c("ward.D", "ward.D2", "single", "complete", "average")
کد R ارائه شده در ادامه تابع NbClust را بر روی متد k-means اجرا می‌کند:
در ادامه تابع fviz_nbclust بر خروجی nb پیاده شده و نتایج ارائه شده است.
## Among all indices:
## ===================
## * 2 proposed 0 as the best number of clusters
## * 10 proposed 2 as the best number of clusters
## * 2 proposed 3 as the best number of clusters
## * 8 proposed 4 as the best number of clusters
## * 1 proposed 5 as the best number of clusters
## * 1 proposed 8 as the best number of clusters
## * 2 proposed 10 as the best number of clusters
## ## Conclusion
## =========================
## * According to the majority rule, the best number of clusters is 2 .
خلاصه
در این نوشتار به تشریح روش های انتخاب تعداد بهینه خوشه ها در اجرای الگوریتم های خوشه بندی در داده کاوی شامل روش های Elbow، silhouette و gap statistics پرداختیم. سپس نشان دادیم که چگونه با استفاده از تابع fviz_nbclust در پکیج factoextra در زبان برنامه نویسی R این متدها را بر دیتاست مورد نظر اعمال کنیم. علاوه بر این، به تشریح تابع ()NbClust پرداختیم که می‌توان از آن در اجرای هم‌زمان روش های مختلف برای محاسبه تعداد بهینه خوشه ها استفاده کرد.
گام بعدی پس از محاسبه تعداد بهینه خوشه ها، اجرای الگوریتم های کلاسترینگ مبتنی بر تقسیم بندی با مقدار k یعنی تعداد خوشه های به‌دست آمده است.
منابع مورد استفاده در تهیه این مقاله:
- Charrad, Malika, Nadia Ghazzali, Véronique Boiteau, and Azam Niknafs. 2014. "NbClust: An R Package for Determining the Relevant Number of Clusters in a Data Set." Journal of Statistical Software 61: 1–36. دانلود مقاله
- Kaufman, Leonard, and Peter Rousseeuw. 1990. Finding Groups in Data: An Introduction to Cluster Analysis.
منبع مستقیم این مقاله: وب سایت Statistical tools for high-throughput data analysis
نظرات (2)