LOGIN
ثبت نام یا ورود
Avatar
هنوز ثبت نام نکرده اید؟

هم اکنون عضو پلاک آبی شوید .و به اطلاعات وب سایت ما دسترسی داشته باشید

تنظیم مجدد کلمه عبور - نام کاربری را فراموش کرده ام

نام کاربری
کلمه عبور
مرا به خاطر بسپار

placabi articles

تعداد بهینه خوشه ها در الگوریتم های خوشه بندی کدام است؟ یافتن تعداد بهینه خوشه ها برای خوشه بندی در داده کاوی

تعداد بهینه خوشه ها در الگوریتم های خوشه بندی کدام است؟

  • این مورد را ارزیابی کنید
    (8 رای‌ها)

معرفی سه روش برای تعیین تعداد بهینه خوشه ها در الگوریتم های خوشه بندی در داده کاوی با اجرای تنها یک تابع در زبان برنامه نویسی R

تعیین تعداد بهینه خوشه ها در پروژه های داده کاوی همواره یکی از چالش‌های اصلی پیاده سازی الگوریتم های خوشه بندی مبتنی بر تقسیم یا به عبارتی 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- نقطه زانوئی نمودار رسم شده، تعداد بهینه خوشه ها را نشان می‌دهد.

 

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

متد 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 و نیز محاسبه انحراف معیار آماره به‌دست آمده:

محاسبه آماره gap

4- انتخاب تعداد بهینه خوشه ها به صورت کم‌ترین مقدار k به‌طوری‌که  Gap(k)≥Gap(k+1)-sk+1

ذکر این نکته ضروری است که مقدار B = 500 نتایج دقیقی ارائه می‌دهد، به‌طوریکه نمودار آماره gap با اجراهای مجدد الگوریتم بدون تغییر باقی می‌ماند.

 

محاسبه تعداد بهینه خوشه ها در الگوریتم داده کاوی خوشه بندی با استفاده از زبان برنامه نویسی 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 روش به طور هم‌زمان و تنها با یک بار اجرا، به منظور تعیین تعداد بهینه خوشه ها با تنها یک بار اجرای توابع این پکیج بر روی داده ها اجرا می‌کند.

برای نصب این پکیج‌ها به صورت زیر عمل می‌کنیم:

نصب پکیج R

برای بارگذاری این پکیج‌ها نیز از دستورات زیر استفاده می‌کنیم:

بارگذاری پکیج های R

آماده سازی داده ها

در این نوشتار از مجموعه داده های USArrests برای اجرای مدل ها و نمایش نتایج استفاده شده است. قبل از هر چیز با استفاده از دستورات زیر داده ها نرمال سازی شده‌اند تا امکان مقایسه فیلدهای داده‌ای با هم میسر شود:

استانداردسازی یا نرمال کردن داده ها در R

نمایی از داده ها پس از نرمال سازی به شکل زیر است:

نمایی از داده های نرمال شده

استفاده از تابع fviz_nbclust در محاسبه متدهای elbow، silhouette و gap statistics

شکل کلی این تابع به صورت زیر است:

;شکل کلی تابع fviz_nbclust در محاسبه متدهای elbow، silhouette و gap statistics

در این تابع داریم:

x: یک ماتریس عددی یا یک دیتا فریم
FUNcluster: یک تابع تقسیم بندی. مقادیر مجاز این پارامتر عبارتنداز: kmeans، pam، clara و hcut (برای خوشه بندی سلسله مراتبی)
Method: روش مورد نظر در تعیین تعداد بهینه خوشه ها

تعداد بهینه خوشه ها در الگوریتم خوشه بندی k-means به کمک کد زیر در زبان برنامه نویسی R محاسبه می‌شود:

محاسبه تعداد بهینه خوشه ها را در الگوریتم خوشه بندی 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

تعیین تعداد بهینه خوشه ها در خوشه بندی در داده کاوی

متد elbow تعداد 4 خوشه را به عنوان تعداد خوشه های بهینه ارایه کرده است.
متد silhouette تعداد 2 خوشه را به عنوان تعداد خوشه های بهینه ارایه کرده است.
متد gap statistic تعداد 4 خوشه را به عنوان تعداد خوشه های بهینه ارائه کرده‌است.

بر این اساس می‌توان k=4 را به عنوان تعداد بهینه خوشه ها در نظر گرفت.

نکته: یکی از نقاط ضعف روش های elbow و silhouette این است که برای تعیین تعداد بهینه خوشه ها، یک معیار عمومی خوشه بندی را اندازه گیری می‌کنند. در روشی پیچیده‌تر، می‌توان از متدGap Statistics برای رفع این نقیصه در روش های ذکر شده استفاده کرد و سپس آن‌ها را در تخمین تعداد بهینه خوشه ها به‌کار برد.

تابع NbClust: سی (30) شاخص در انتخاب بهترین تعداد خوشه ها

شکل کلی این تابع به صورت زیر است:

شکل کلی تابع NbClust در زبان برنامه نویسی R

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 اجرا می‌کند:

تابع NbClust برای روش k-means در زبان برنامه نویسی R

در ادامه تابع fviz_nbclust بر خروجی nb پیاده شده و نتایج ارائه شده است.

نتیجه پیاده سازی تابع fviz nbclust بر خروجی nb در زبان برنامه نویسی R

## 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 .

نمودار نتایج محاسبه تعداد بهینه خوشه ها در خوشه بندی در داده کاوی

 

• در 2 مورد از متدهای اجرا شده، تعداد خوشه های بهینه 0 محاسبه شده است.
• در 10 مورد از متدهای اجرا شده، تعداد خوشه های بهینه 2 محاسبه شده است.
• در 2 مورد از متدهای اجرا شده، تعداد خوشه های بهینه 3 محاسبه شده است.
• در 8 مورد از متدهای اجرا شده، تعداد خوشه های بهینه 4 محاسبه شده است.

با توجه به این نتایج، تعداد بهینه خوشه ها برابر است با: k=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

خواندن 1032 دفعه آخرین ویرایش در دوشنبه, 14 اسفند 1396 01:27
محسن یزدی نژاد

عضو گروه هوش کسب و کار ایرانیان

آموزش، مشاوره و پیاده سازی راهکارهای داده کاوی

 

مدرس و مدیر پروژه های داده کاوی شرکت پلاک آبی

دانشجوی دکتری هوش مصنوعی

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

  • هیچ نظری یافت نشد

نظر خود را اضافه کنید.

ارسال نظر به عنوان مهمان

0
نظر شما به دست مدیر خواهد رسید
 تماس با ما

شهرک غرب، بلوار فرحزادی، خیابان تربیت معلم،
انتهای خیابان گلبان،
مجتمع موج، واحد 105
کد پستی: 1998963193
تلفن: 5 - 88560784
فکس: 88560786
پست الکترونیک:
info @ p l a c a b i . com
ibig @ p l a c a b i . com

 

We use cookies to improve our website. By continuing to use this website, you are giving consent to cookies being used. More details…