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

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

اگر حس می‌کنید نیاز به معرفی روش k-means یا یادگیری بدون نظارت دارید حتما مطالب قبلی انتشارات شرکت علم داده ارزیاب رو بخونید.

الگوریتم لوید(Lloyd’s Algorithm):

در سال 1957 استوارت لوید، یک الگوریتم تکرار شونده ساده رو پیشنهاد داد تا به طور موثر یک کمینه محلی برای مساله خوشه بندی پیدا کند. این الگوریتم به این صورت عمل می‌کند که ابتدا به صورت تصادفی k نقطه رو به عنوان مراکز خوشه ها انتخاب می‌کند. سپس فاصله مشاهدات رو از مرکز هر خوشه می‌سنجد و نزدیک ترین فاصله را برای اختصاص دادن نقطه در آن خوشه انتخاب می‌کند. سپس با توجه به نقاط قرار گرفته در خوشه، میانگین جدید در هر خوشه محاسبه می‌شود. پس از محاسبه میانگین های جدید دوباره فاصله نقاط تا هر میانگین بررسی شده و دوباره نزدیک ترین فاصله هر نقطه تا میانگین جدید محاسبه می‌شود و نقاط در خوشه های جدید قرار می‌گیرند. این کار تا زمانی ادامه می‌یابد که تابع هدف (C)SSE که در اون C ها مراکز خوشه ها هستند؛ کمینه شود.

هدف ما در این الگوریتم این است که مراکز k خوشه را بنابر تابع هدف SSE که مربع فاصله بین تمام نقاط تا نزدیک ترین مرکز خوشه است؛ بیابیم.

در حالت کلی الگوریتم لوید به صورت زیر خلاصه میشه:

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

الگوریتم فورجی(Forgy Algorithm)

الگوریتم های لوید و فورجی هر دو جزء مدل های مرکزوار دسته‌ای(سانتروئیدی دسته‌ای) هستند.

سانتروئید مرکز هندسی یک جسم محدب است که می‌توان از اون به عنوان تعمیمی از میانگین یاد کرد.

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

از آن جایی که الگوریتم های افزایشی k-mean برای عضویت خوشه‌ای هر مشاهده یا انجام محاسبات دو خوشه نزدیک برای پردازش هر مشاهده نیاز به ذخیره دارند، که از نظر محاسباتی در داده های بزرگ گران هستند؛ بنابراین با در نظر گرفتن بهینه بودن، بهتره از الگوریتم های لوید و فورجی برای تحلیل مجموعه داده های بزرگ استفاده شود.

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

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

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

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

Lloyd =  kmeans(data, k, algorithm =&quotLloyd&quot)
Lloyd

خط اول کد تابع kmeans ازتون دو تا ورودی می‌گیره. اولیش مجموعه داده هست که در قالب دیتافریم باید به تابع این ورودی رو بدید و مهمه که داده شما عددی باشه. یعنی مثلا اگه توی مجموعه داده شما ستونی به اسم جنسیت وجود داره که مقادیرش زن و مرد هست باید مقادیرش رو عددی کنید و برای خودتون کد گذاری کنید.مثلا بگید زن معادل عدد 1 و مرد معادل هدد 0 در مجموعه داده تغییر یافته ای هست که میخوام به تابع kmeans ورودی بدم.

ورودی بعدی این تابع تعداد خوشه هایی هست که میخواید مجموعه داده شما خوشه بندی بشه. برای توضیح بهتر همون مثال معروف داده های iris رو میگم که معرف مشخصات سه نوع گل هست؛ اگه بخوایم این الگوریتم رو برای این داده ها پیاده سازی کنیم k رو برابر با 3 در نظر میگیریم.

در نهایت مقدار algorithm رو در این تابع باید برابر با "Lloyd" قرار بدید تا الگوریتم لوید روی مجموعه داده شما اجرا بشه.

خب شما توی خط اول دارید تابع kmeans رو اجرا میکنید و نتایج اون رو در متغیری به اسم Lloyd می‌ریزید. شما می‌تونید این نتایج رو توی متغیر با اسم های دیگه هم بریزید. نکته این قسمت اینه که Lloyd فقط یه متغیر هست که نتایج الگوریتم اجرا شده رو نشون میده. این متغیر میتونه هر اسم دیگه ای هم داشته باشه؛ مثلا میتونه اسمش fatemeh باشه :)

توی خط دوم شما دارید به R می‌گید که نتایج رو براتون پرینت کنه و با این دستور شما چندین خروجی می‌بینید:

1- Cluster means(میانگین های خوشه ها)
2- Clustering vector(بردار خوشه بندی)
3- Available components(اجزای موجود)

خروجی اول به شما یک به اصطلاح جدولی(table) رو نشون میده که ستون های اون شامل متغیر های مجموعه داده شماست که به تابع ورودی دادید و سطر های اون نشان دهنده میانگین هر خوشه به تفکیک متغیر های مجموعه داده شما هست. مثلا اگه شما k رو برابر با 3 در نظر گرفته باشید و مجموعه داده شما 4 تا متغیر داشته باشه؛ جدولی که به شما خروجی داده میشه شامل 4 ستون معرف متغر های شما و 3 سطر معرف تعداد خوشه هاست. مقادیر داخل جدول هم میانگین هر خوشه در متغیر مورد نظر را نشان می‌دهد.

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

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

Available components:
[1] "cluster" "centers" "totss" "withinss" "tot.withinss" "betweenss" "size" "iter" "ifault

این اسم اجزائی هست که اگر صداشون بزنید(به اصطلاح کال کنیدشون) اطلاعات مخصوص به خودشون رو در خوشه بندی اجرا شده چاپ می‌کنند. مثلا اگر تایپ کنید Lloyd$iter تعداد تکرار الگوریتم تا رسیدن به نتایج بهینه رو براتون چاپ میکنه.

کد های R برای پیاده سازی الگوریتم فورجی به صورت زیر هست:

Forgy = kmeans(data, k, algorithm =&quotForgy&quot)
Forgy

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

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

سوالات متداول درباره الگوریتم های خوشه بندی K-means

اگر براتون سوال پیش اومده که از کجا تعداد k رو محاسبه کنیم و توی این الگوریتم بهش بدیم باید بگم بنا بر مجموعه داده ای که دارید باهاش کار می‌کنید متفاوته این تعداد. بعضی اوقات ممکنه شما دیدی داشته باشید نسبت به مجموعه داده و تعداد k رو حدس بزنید؛ مثل مجموعه داده معروف iris که میدونیم توی این مجموعه داده 3 نوع گل وجود داره. پس تعداد خوشه ها رو برابر با 3 قرار می‌دیم. خیلی جا ها هم دید کافی نسبت به مجموعه داده نداریم و نمی‌دونیم بهتره که k چه عددی باشه. در این جور جا ها بهتره که چندین k رو با الگوریتم های پیشنهادی پیاده سازی کنیم و در نهایت با توجه به کیفیت خوشه بندی بسنجیم که کدوم k مناسب تر بوده. خب سوال بعدی اینه که کیفیت خوشه بندی رو چجوری بفهمیم؟؟ این باز مساله ای هست که راه های مختلف داره و حوصلش ازین مطلب خارجه. در بحث های بعدی سعی می‌کنم به این مطلب هم بپردازم و با پیاده سازی روی مجموعه داده های مختلف بهتون کیفیت خوشه بندی رو توضیح بدم.

در این قسمت فرصت شد تا دو تا از الگوریتم های روش k-means رو توضیح بدم. در قسمت های بعد حتما سعی می‌کنم به بقیه الگوریتم های این روش هم بپردازم.