پیاده سازی الگوریتم های لوید و فورجی - قسمت اول (مجموعه داده Iris)

در مطلب معرفی روش خوشه بندی K-means به معرفی کلی این روش پرداختم و الگوریتم های آن را به صورت موردی نام بردم. در مطالب الگوریتم های خوشه بندی لوید و فورجی و الگوریتم های خوشه بندی هارتیگان-ونگ و مک‌کوئین نیز به توضیح کامل چگونگی کارکرد این الگوریتم ها پرداختیم. در این مطلب قصد دارم به نحوه پیاده سازی الگوریتم های لوید و فورجی بر روی یک مجموعه داده بسیار ساده بپردازم.

معرفی مجموعه داده Iris

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

اولین مجموعه داده‌ای که باهاش سر و کار داریم دیتاست معروف Iris هست که از 5 متغیر تشکیل شده. این مجموعه داده شامل 150 مشاهده است که چهار ویژگی طول و عرض کاسبرگ و گلبرگ را در سه نوع گل بررسی کرده است. یعنی متغیر های این مجموعه داده شامل این موارد هست:

1- طول کاسبرگ

2- عرض کاسبرگ

3- طول گلبرگ

4- عرض گلبرگ

5- نام گونه گیاه

در شکل های زیر می‌توان نمودار های نقطه‌ای این مجموعه داده را مشاهده کرد. در این نمودار ها دو متغیر طول و عرض گلبرگ در مقابل هم و دو متغیر طول و عرض کاسبرگ در مقابل هم رسم شده‌اند.

نکته‌ای که در این مجموعه داده وجود داره اینه که در کنار ویژگی های طول و عرض کاسبرگ و گلبرگ یک متغیر اسم وجود داره که میشه در مسائل طبقه بندی که زیر مجموعه‌ای ای مسائل یادگیری تحت نظارت هستند؛ به عنوان برچسب داده ها استفاده کرد. با این حال چون مساله در اینجا خوشه بندی است و و خوشه‌بندی زیر مجموعه یادگیری بدون نظارت هست ما مجبوریم این متغیر را کنار کذاشته و در پیاده سازی ها از اون استفاده نکنیم. پس مجموعه داده جدید ما به صورت 4 متغیر طول و عرض گلبرگ و کاسبرگ است و مساله اصلی ما به این صورته:

سه نوع گل داریم که از هر نوع گل 50 مشاهده استخراج کردیم و 4 ویژگی طول گلبرگ، عرض گلبرگ، طول کاسبرگ و عرض کاسبرگ رو ثبت کردیم. ما نمیدونیم که هر رکورد یا مشاهده مرتبط با چه نوع گلی هست ولی مسالمون اینه که 150 مشاهده رو خوشه بندی کنیم و بگیم هر رکورد در چه خوشه‌ای قرار می‌گیره.

برای درک بهتر از مجموعه داده می‌تونید 5 مشاهده اول مجموعه داده یا به اصطلاحی دیگر head دیتاست رو در تصویر زیر ببینید:

پیاده سازی الگوریتم لوید

در این قسمت به وسیله نرم افزار R، الگوریتم لوید از روش خوشه‌بندی k-mean را بر روی داده های Iris پیاده سازی می‌کنیم. با توجه به نوع مجموعه داده، تعداد خوشه ها در هر یک از الگوریتم ها را برابر با 3 در نظر می‌گیریم(k=3). نکته قابل ذکر در این قسمت این است که ما می‎‌دانیم ماهیت دیتاست سه خوشه را شامل می‌شود؛ سوالی که پیش میاد اینه که خب اگر در یک مجموعه داده ندونیم دیتا چه ماهیتی داره چی؟ قطعا به یک مثال دیگه هم توی پیاده سازی این الگوریتم خواهم پرداخت که ندونیم ماهیت دیتاست چیه و حل مساله رو از نگاه من ببینید. در اینجا چون اولین دیتاستی هست که داریم کار می‌کنیم بهتره توی این مرحله برای درک بهتر همه چی تا حدی ساده باشه.

خب کد های برنامه R برای پیاده سازی الگوریتم لوید بر روی داده های Iris به صورت زیر هست:

> # the data has been numeric to use algorithms
> # so we have this codes:
> iris1 = iris[,1:4]

> #Lloyd Algorithm
> Lloyd =  kmeans(iris1, 3, algorithm =&quotLloyd&quot)
> Lloyd

خب دو خط اول درواقع کامنت هست و توضیح داده که داده ها باید نامریک باشند تا بشه الگوریتم ها رو روشون پیاده سازی کرد و از روی دیتاست اصلی یک دیتاست جدید ساخته که 4 متغیر طول و عرض گلبرگ و کاسبرگ رو شامل میشه.

خط بعدی درواقع پیاده سازی الگوریتم لوید با 3 خوشه بر روی دیتاست جدید است که با تابع kmeans و پارامتر های مجموعه داده، تعداد خوشه و نام الگوریتم پیاده سازی شده و در یک متغیر به اسم Lloyd ریخته شدند.

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

K-means clustering with 3 clusters of sizes 61, 50, 39

Cluster means:
Sepal.Length Sepal.Width Petal.Length Petal.Width
1     5.883607    2.740984     4.388525    1.434426
2     5.006000    3.428000     1.462000    0.246000
3     6.853846    3.076923     5.715385    2.053846

خط اول که رسما اعلام میکنه از بین 150 مشاهده چند مشاهده به هر کدوم از خوشه ها اختصاص داده شده. توی این مثال 61 مشاهده به خوشه اول، 50 مشاهده به خوشه دوم و 39 مشاهده به خوشه سوم تعلق گرفته. خب ازونجایی که با مجموعه داده آشنایی داریم میتونیم واضحا بگیم این خوشه بندی قطعا درصدی خطا داره؛ چرا که اگر بی نقص بود باید به هر خوشه 50 مشاهده تخصیص داده می‌شد.

خط بعدی عنوان یک جدول هست به نام Cluster means یا میانگین خوشه. در این جدول هر ردیف یا رکورد نماینده خوشه هست و هر ستون نماینده متغیر ها. رکورد های داخل جدول هم میانگین متغیر مربوطه در خوشه مشخص هستند. برای مثال میانگین متغیر Sepal.Length در خوشه دوم برابر با 5.006000 است.

جدول cluster means یه جورایی مهمه. چرا؟ چون شما با نگاه کردن به ردیف ها که نماینده هر خوشه هستند می‌تونید مقایسه کنید که واریانس کدوم متغیر زیاد تره. اینطوری می‌تونید در یک نگاه متوجه شید که کدوم یکی از متغیر ها در خوشه‌بندی تاثیر بیشتری گذاشتند. هرچی که واریانس بین خوشه ها در یک متغیر خاص در جدول میانگین خوشه‌ای بیشتر باشه اون متغیر تاثیر بیشتری در خوشه‌بندی شما گذاشته.

?نکته: تو این قسمت واریانس رو توضیح دادم و هرکس با مفهومش آشنا هست می‌تونه این قسمت رو رد کنه :)

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

اگه بخوام تکنیکالی فرمول بالا رو کامل توضیح بدم واریانس جامعه برابر میشه با:
مجموع تفاضل های همه رکورد های جامعه از میانگین جامعه به توان دو تقسیم بر تعداد رکورد های جامعه. یا به بیان دیگر
1- از جامعت میانگین بگیر و اسمش رو بذار میو.
2- بعد همه رکورد های جامعه رو تک تک از میانگین کل جامعه که اسمش رو گذاشته بودی میو کم کن.
3- نتیجه تفاضل های انجام شده رو تک تک به توان دو برسون
4- نتایج به توان دو رسیده رو باهم جمع کن
5- مجموع بدست اومده رو به تعداد کل رکورد های جامعه تقسیم کن

می‌خوام با ذکر یک مثال از محاسبه واریانس در جدول میانگین خوشه مبحث cluster means رو تموم کنم و برم سر خروجی بعدی. توی جدول میانگین خوشه‌ای این مجموعه داده واریانس متغیر های sepal length و petal length محاسبه شده و به ترتیب برابر با 0.8543489 و 4.736064 هست. میشه این برداشت رو کرد که متغیر petal length به دلیل واریانس بیشتر در این جدول دارای تاثیر گذاری بیشتری روی خوشه بندی هست.

این که اهمیت تاثیر گذاری هر متغیر رو توی خوشه بندی محاسبه کنیم شاید الان مهم نباشه ولی در کل برای بهینه کردن مدل خوشه‌بندی‌مون می‌تونه مفید باشه.

خب خروجی بعدی Clustering vector هست که نشان می‌ده که هرکدام از مشاهدات به چه خوشه‌ای اختصاص داده شده‌اند. برای مثال اگر دقت کنید مشاهدات 1 تا 50 به خوشه دوم اختصاص داده شدند.

Clustering vector:
[1] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
[26] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
[51] 3 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[76] 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[101] 3 1 3 3 3 3 1 3 3 3 3 3 3 1 1 3 3 3 3 1 3 1 3 1 3
[126] 3 1 1 3 3 3 3 3 1 3 3 3 3 1 3 3 3 1 3 3 3 1 3 3 1

Available components:
[1] &quotcluster&quot      &quotcenters&quot      &quottotss&quot
[4] &quotwithinss&quot     &quottot.withinss&quot &quotbetweenss&quot
[7] &quotsize&quot         &quotiter&quot         &quotifault&quot

خروجی آخر هم همونطور که در مطلب الگوریتم های خوشه بندی لوید و فورجی گفتم نشان دهنده مواردی هست که می‌تونید اطلاعات بگیرید از خوشه بندی‌تون. برای مثال ما به کد زیر توجه کنید:

> Lloyd$iter
[1] 11

این نشان دهنده تعداد تکرار الگوریتم برای رسیدن به بهینه ترین خوشه بندی هست. یا Lloyd$centers به طور خاص فقط جدول میانگین خوشه‌ای رو بهتون خروجی میده و چاپ میکنه.

نمودار نقطه‌ای الگوریتم لوید

در این نمودار می‌تونید دسته بندی هایی که الگوریتم لوید بر روی داده ها انجام داده رو ببینید:

پیاده سازی الگوریتم فورجی

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

راستش کد ها و توضیح و شرح خروجی ها زیاد متفاوت نیست با الگوریتم لوید اما بهتره به صورت یک جا پیاده سازی این الگوریتم هم ببینیم:

> #Forgy Algorithm
> Forgy = kmeans(iris1, 3, algorithm =&quotForgy&quot)
> Forgy
K-means clustering with 3 clusters of sizes 50, 61, 39

Cluster means:
Sepal.Length Sepal.Width Petal.Length Petal.Width
1     5.006000    3.428000     1.462000    0.246000
2     5.883607    2.740984     4.388525    1.434426
3     6.853846    3.076923     5.715385    2.053846

Clustering vector:
[1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[26] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[51] 3 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
[76] 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
[101] 3 2 3 3 3 3 2 3 3 3 3 3 3 2 2 3 3 3 3 2 3 2 3 2 3
[126] 3 2 2 3 3 3 3 3 2 3 3 3 3 2 3 3 3 2 3 3 3 2 3 3 2

Available components:
[1] &quotcluster&quot      &quotcenters&quot      &quottotss&quot
[4] &quotwithinss&quot     &quottot.withinss&quot &quotbetweenss&quot
[7] &quotsize&quot         &quotiter&quot         &quotifault&quot

> Forgy$iter
[1] 4

با توجه به نتایج بالا تعداد تکرار در اجرای این الگوریتم برابر با 4 شده است و درحالت کلی از 150 داده، 50 مشاهده به خوشه 1، 61 مشاهده به خوشه 2 و 39 مشاهده به خوشه 3 ام تعلق گرفته.

با مقایسه نتایج جدول میانگین مشخصه های هر خوشه در اجرای الگوریتم لوید و فورجی بر روی مجموعه داده Iris می‌توان دریافت که هر دوی این الگوریتم ها خروجی یکسان دادند. با این تفاوت که تعداد تکرار در الگوریتم لوید بیشتر از تعداد تکرار در الگوریتم فورجی است. در عمل خوشه های سوم این الگوریتم ها با یکدیگر برابر است؛ با توجه به اختیاری بودن برچسب ها در الگوریتم ها مشاهده می‌شود خوشه های الگوریتم لوید و فورجی بایکدیگر برابرند. دلیل این برابری هم همون‌طور که در بخش نظری نیز به اون پرداخته شد، اینه که این دو الگوریتم عملکرد یکسانی دارند.

نمودار نقطه‌ای الگوریتم فورجی

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

مقایسه دو الگوریتم لوید و فورجی در دیتاست Iris

در آخر می‌تونم بگم اگر دو تا نمودار خوشه‌بندی الگوریتم های لوید و فورجی رو باهم مقایسه کنیم به راحتی می‌تونیم این مساله که این دو الگوریتم هیچ تفاوت عملکردی ای توی خوشه‌بندی دیتاست Iris نداشتند؛ ببینیم. تنها تفاوت تعداد تکرار ها بود که الگوریتم فورجی به دلیل تکرار کمتر عملکرد بهتری داشته تا به اینجا.

?نکته مهم: این که نتیجه پیاده سازی این دو الگوریتم روی مجموعه داده آموزشی Iris کاملا یکسان بوده دلیل نمیشه که عملکردشون کاملا یکسان باشه. این فقط یک مثال از پیاده سازی این دو تا الگوریتم روی یک دیتاست کاملا آموزشی بود.

خب این مطلب تازه یک مقدمه از پیاده سازی الگوریتم ها و مقایسه سطحی‌شون باهم بود؛ هنوز کلی سوال هست که جواب داده نشده و هر مطلبی که جلوتر می‌ریم یک لول عمیق‌تر می‌شیم. سعی می‌کنم در مطالب بعدی با پیاده سازی این دو الگوریتم بر روی یک مجموعه داده بزرگ‌تر نتایج و عملکرد هاشون رو باهم مقایسه کنم.

مطالبی که پیشنهاد می‌کنم به ترتیب اولویت در این رشته مبحث بخونید به این صورته:

1- یادگیری ماشین و مدل سازی آماری(شباهت ها و تفاوت ها)

2- یادگیری تحت نظارت و بدون نظارت در یادگیری ماشین در سه دقیقه

3- خوشه بندی چیست و چگونه عمل می‌کند؟

4- معرفی روش خوشه بندی K-means

5- الگوریتم های خوشه بندی لوید و فورجی(K-means)

6- الگوریتم های خوشه بندی هارتیگان-ونگ و مک‌کوئین (K-means)

خوشحال می‌شم اگه بازخوردی دارید حتما بهم پیشنهاد بدید :)