درآمدی بر کلاسترینگ

4 جولای 2019

اخیرا با گروهی همکار شدم که در مسیر توسعه نرم افزار به چالش های بعضا جالبی بر می خوریم. چالشی که این روزها درگیرش بودم به نوعی یک مساله خوشه بندی (Clustering) هستش. صورت مساله به این صورته که ما باید روی پنل ادمین روی نقشه، وضعیت کلی درخواست ها و همچنین راننده های سیستم رو ببینیم. خب اینکه داده ها رو به صورت خام به کلاینت بفرستیم قطعا مردوده و باید داده ها پردازش و سپس به کلاینت برای نمایش ارسال بشن. هدف این هستش که مدیران سیستم بتونن در لحظه چگالی عرضه و تقاضا رو مشاهده کنن و متناسب با مشاهداتشون عرضه رو به سمت تقاضا هدایت کنن!

K-Means ساده و کاربردی

در بین الگوریتم های خوشه بندی به طور قطع K-Means به خاطر سادگی در فهم و پیچیدگی زمانی پایین یکی از محبوب ترین هاست. این الگوریتم با دانستن تعداد خوشه ها (K) داده های ما رو بهK خوشه ی مشابه هم تقسیم بندی می کنه. در این روش شباهت داده ها رو با استفاده از محاسبه ی فاصله ی اقلیدسی نقاط به دست میاریم. این الگوریتم به طور خلاصه به صورت زیر پیاده سازی می شود:

در ابتدا K نقطه را از میان داده ها به صورت اتفاقی به عنوان نقاط میانه (مرکز کلاستر) انتخاب می کنیم.

هر نقطه به نزدیک ترین مرکز نسبت داده می شود. سپس مرکز جدید با میانگین نقاط دسته بندی شده در آن خوشه بروزرسانی می شود.

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

علیرغم اینکه این الگوریتم پیچیدگی زمانی پایینی داره اما ایراد مهمی که به اون وارد هست آینه که از قبل بایستی تعداد کلاستر های موجود رو بدونیم!‌که باعث میشه این روش به کار ما نیاد.

Hierarchical clustering

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

این شیوه ی خوشه بندی به دو صورت بالا به پایین (Divisive) و پایین به بالا (Agglomerative) انجام می شود.

در روش بالا به پایین در ابتدا تمام داده ها به صورت یک کلاستر در نظر گرفته می شوند و سپس این کلاستر به دو کلاستر کمتر شبیه به هم تقسیم می شوند. این روال تا زمانی که هر یک از داده ها به تنهایی تبدیل به یک کلاستر شوند ادامه می یابد.

بالعکس اما در روش پایین به بالا ابتدا هر یک از نقاط یک کلاستر در نظر گرفته می شود و سپس کلاستر هایی که بیشترین نزدیکی را داشته باشند با یکدیگر ادغام می شوند. این عمل تا زمانی که تنها یک کلاستر باقی بماند ادامه داده می شود.

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

– در ابتدا ماتریس مجاورتی شامل فاصله ی هر یک از نقاط از یکدیگر را تشکیل می دهیم.

– هر نقطه را یک کلاستر در نظر گرفته

– مادامی که بیش از یک کلاستر باقی مانده باشد نزدیکترین کلاستر ها با یکدیگر اداغام شوند.

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

Mean Shift بهترین در دو دنیا‌!

بنابراین سراغ الگوریتم دیگه ای به نام Mean Shift میریم که بر خلاف KMeans نیازی به مشخص کردن تعداد کلاستر های موجود نداره و همچینن بار حافظه قابل تحمل تری نسبت به روش سلسله مراتبی داره.

توی این روش

-ابتدا پهنای باند هسته (اندازه پنجره) رو مشخص می کنیم و پنجره رو روی یک نقطه قرار میدیم.

-میانگین تمام داده ها داخل پنجره را محاسبه می کنیم

-میانگین رو به عنوان مرکز جدید پنجره در نظر میگیرم.

– مراحل ۲ و ۳ رو تا زمانی که مرکز پنجره جابجا میشه انجام میدیم.

نکته مهمی که وجود داره اینه که روش بالا برای صرفا یک پنجره هست و ما برای اینکه در عمل بتونیم کلاستر های متعدد رو تشخیص بدیم باید تمام فضای داده رو با تعداد پنجره مناسب پوشش بدیم. به این کار به اصطلاح tiling یا tessellation میگن. از اونجایی که پنجره های فرضی ما دایره ای هستن برای اینکه کل فضای داده رو پوشش بدیم از یک جدول با مربع هایی با ابعاد مناسب استفاده می کنیم. و بعد به مرکز هر مربع یک دایره در نظر میگیرم. مثل تصویر زیر

tesselation

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

درامدی بر کلاسترینگ

سورس کد این پروژه و پروژه های آتی بر روی Github من در دسترس هست.

پاسخ دهید