پیاده سازی الگوریتم خوشه بندی KMenas با استفاده از Map Reduce

مقدمه

این پژوهش کلیدی هست که در این زمینه انجام شده و شاکله این نوشته رو تشکیل داده. ممنون از نویسندگان برجسته این پژوهش. قبل از هرچیزی باید به سری محدودیت های الگوریتم خوشه بندی KMeans اشاره کنم. KMeans وقتی که خوشه ها تو این سه ویژگی با هم متفاوت باشن دچار مشکل میشه:

سایز
چگالی
و غیر کروی بودن خوشه ها

ضمنا KMeans وقتی دیتای ما دارای Outlier هست هم با مشکل مواجه میشه. تو KMenas هزینه دار ترین بخش، فاز محاسبه فواصل هست، بطوری که درهر دور تکرار الگوریتم نیاز هست به محاسبه تمام فواصل (nk) هست.

(nk)

n به تعداد آبجکت ها اشار داره و k به تعداد خوشه هایی که ساخته شده.

اگر بخوایم با استفاده از چارچوب هدوپ مثلا بیایم و خوشه بندی KMenas با استفاده از Map Reduce رو انجام بدیم بیس کار بدین شکل هستش. اما مشخص هستش که محاسبات فاصله بین یک آبجکت با مراکز نسبت به محاسبات فاصله بین سایر آبجکت ها با مراکز مربوطه ارتباطی نداره. برای همین محاسبه فاصله بین آبجکت های متفاوت با مراکز بصورت موازی اجرا میشه. در ادامه در هر تکرار ، مراکز جدید ، که در تکرار بعدی استفاده می شوند ، باید آپدیت بشن.

یه نکته هم در رابطه با گام Combine بگم که میاد و فرآیند summation نقاطی که یه کلاسترهای یکسان منتسب شده رو انجام میده. برای اینکه بیایم و مقدار میانگین آبجکت های هر کلاستر رو محاسبه کنیم باید تعداد نمونه های دیتامون رو در خوشه یکسان در فاز Map یکسان ثبت و ضبط کنیم.

تابع مپ میاد هر Sample رو به نزدیکترین مرکزش اختصاص میده و تابع ردیوس کارش آپدیت مراکز جدیدخوشه هستش. (البته این وسط یه تابع Combine هم داریم که خروجی اش میشه ورودی Reducer).

در ضمن برای کاهش هزینه سربار ارتباطات شبکه از یه تابع Combine هم کمک گرفتیم تا کار Summation نمونه دیتاها و مقادیرشون رو تو یه فاز Map انجام بده. در پایان هم می تونیم برای تکرارهای بعدی مراکزجدید رو داشته باشیم.

اما دیتاست باید اول Split بشه و بعد به صورت سراسری به تمامی Mapper هامون Broadcast بشه. این وسط محاسبه فواصل هم بصورت موازی اجرا میشه. برای هر Map task هم، الگوریتم PKMenas میاد و مراکز سراسری متغیر رو می سازه، اما منظور ما از مراکز سراسری متغیر چی هستش؟ یه آرایه که اطلاعات مربوط به مراکز خوشه رو در خودش نگهداری میکنه.

با داشتن این آرایه از اطلاعات مراکز خوشه ها، یه Mapper میتونه نزدیکترین مرکز برای هر نمونه از دیتامون رو محاسبه کنه. مقادیر میانی هم شامل دو بخش هستند: