پنج الگوریتم خوشهبندی برتر که متخصصین علوم داده باید بدانند
خوشهبندی یکی از تکنیکهای یادگیری ماشین است که به گروهبندی نقطه دادهها میپردازد. چنانچه مجموعهای از نقطهدادهها داشته باشیم، میتوانیم با اجرای یکی از انواع الگوریتم خوشهبندی، هر یک از نقطهدادهها را در یک خوشه یا گروه خاص جای دهیم و آنها را گروهبندی کنیم.
به لحاظ تئوری نقطهدادههایی که در یک گروه قرار دارند باید ویژگیها و خصوصیتهای مشابهی داشته باشند و در مقابل نقطهدادههایی که در گروههای جداگانه قرار دارند ویژگیهای متفاوتی خواهند داشت. خوشهبندی یکی از متدهای یادگیری بدوننظارت است و به طور گسترده در تحلیل دادههای آماری بسیاری از رشتهها مورد استفاده قرار میگیرد.
به طور کلی در حوزه علوم داده و تحلیل خوشهبندی Clustering analysis، یکی از الگوریتمهای خوشهبندی بر روی دادهها اجرا میشود و دادهها را گروهبندی میکند و متخصصین علوم داده با بررسی و مطالعه هر یک از این گروهها و دادههایی که در آنها قرار گرفته، میتوانند اطلاعات ارزشمندی راجع به دادهها کسب کنند. در این نوشتار به مطالعه و معرفی پنج الگوریتم محبوب خوشهبندی میپردازیم که تمامی متخصصین علوم داده باید با آنها آشنایی داشته باشند و مزایا و معایب استفاده و اجرای هر یک از آنها را بدانند.
الگوریتمخوشه بندی K میانگین (K-means)
شاید بتوان گفت الگوریتمخوشه بندی k میانگین، مشهورترین الگوریتمخوشه بندی است. در بسیاری از کلاسهای مقدماتی علوم داده و یادگیری ماشین این الگوریتم آموزش داده میشود. درک و همچنین کدنویسی این الگوریتم بسیار آسان است. به تصویر مقابل توجه کنید:
- برای اجرای این الگوریتم ابتدا باید تعداد کلاسها/گروهها را مشخص کنیم و به صورت تصادفی نقاط مرکزی آنها را مقداردهی میکنیم. برای اینکه بدانیم از چه تعداد کلاس باید استفاده کنیم بهتر است نگاهی به دادهها بیندازیم و تعداد گروههایی که با یکدیگر تفاوت دارند را مشخص کنیم. نقاط مرکزی، بردارهایی هستند که طول آنها با بردارهای نقطهدادهها برابر است و در تصویر فوق با “X” نشان داده شدهاند.
- برای طبقهبندی هر نقطه داده، فاصله هر نقطهداده تا مراکز گروهها محاسبه میشود و سپس هر نقطهداده در گروهی جای میگیرد که به مرکز آن نزدیکتر است.
- سپس بر مبنای نقطهدادههایی که طبقهبندی شدهاند و محاسبه میانگین تمامی بردارهای موجود در گروه، مرکز گروه را مجدداً محاسبه میکنیم.
- این مراحل را برای تعداد مشخصی تکرار (Iteration) و یا تا زمانیکه مراکز گروهها دیگر بین تکرارها تغییر زیادی نکنند، تکرار میکنیم. همچنین میتوانید چندین دفعه به صورت تصادفی مراکز گروهها را مقداردهی کنید و سپس اجرایی که بهترین نتایج را به همراه دارد انتخاب کنید.
تنها کاری که در این الگوریتم انجام میدهیم محاسبه فاصله میان هر نقطهداده تا مراکز گروه است و به همین دلیل این الگوریتم سریع است و پیچیدگی linear complexity آن به صورت خطی و برابر با O(n) است.
البته الگوریتم k میانگین دو نقطه ضعف هم دارد. اول اینکه در این الگوریتم باید تعداد گروهها/ کلاسهای موجود را مشخص کنیم. تعیین کردن تعداد کلاسها/گروهها گاهی اوقات دشوار است و زمانی که یک الگوریتم خوشهبندی داریم انتظار داریم الگوریتم این کار را برای ما انجام دهد، چراکه هدف ابتدایی تمامی الگوریتمها این است که به ما کمک کنند بینشی راجع به دادهها کسب کنیم. علاوه بر این، الگوریتم k میانگین به صورت تصادفی مراکز خوشه را انتخاب میکند و از این طریق اجرا و آغاز میشود و به همین دلیل ممکن است با هر بار اجرای الگوریتم، خوشهبندیهای متفاوتی ایجاد شود. در این حالت ممکن است خوشهبندیها تکرارپذیر نباشند و انسجام نداشته باشند. سایر الگوریتمهای خوشهبندی انسجام بیشتری دارند.
الگوریتم k میانه یکی دیگر از الگوریتمهای خوشهبندی است که شباهت زیادی به الگوریتم k میانگین دارد، با این تفاوت که در الگوریتم k میانه، به جای اینکه از میانگین برای محاسبه مجدد نقاط مرکزی گروه استفاده شود، از بردار میانه Median vector گروه استفاده میکنیم. حساسیت این الگوریتم به دادههای پرت کمتر است (به این دلیل که در این متد از میانه استفاده میشود) اما از آنجاییکه در زمان محاسبه بردار میانه، در هر تکرار، عملیات دستهبندی باید انجام شود، عملکرد آن در دیتاستهای بزرگتر کندتر است.
الگوریتم خوشهبندی Mean-Shift
الگوریتم خوشهبندی Mean-shift یک الگوریتم پنجره لغزان Sliding window است و سعی میکند نواحی متراکم نقطهدادهها را پیدا کند. این الگوریتم مبتنی بر مرکز خوشه Centroid است؛ به عبارت دیگر هدف این الگوریتم این است که نقاط مرکزی هر یک از گروهها/کلاسها را مکانیابی کند. الگوریتم Mean-shift برای انجام این کار کاندیداهای نقاط مرکزی را بهروزرسانی میکند و آنها را به عنوان میانگین نقاطی در نظر میگیرد که در پنجره لغزان وجود دارند. سپس این پنجرههای کاندیدا در مرحله پس پردازش فیلتر میشوند تا کپیهای مشابه Near-duplicates را از بین ببرند و مجموعهای از نقاط مرکزی و گروههای مرتبط با آنها ایجاد کنند. به تصویر زیر توجه کنید:
- برای توضیح الگوریتم خوشهبندی Mean-Shift، مجموعهای از نقاط را در یک فضای دو بعدی مشابه تصویر فوق در نظر میگیریم. کار خود را با یک پنجره لغزان دایرهای که در مرکز نقطه C ( که به صورت تصادفی انتخاب شده است) قرار گرفته آغاز میکنیم و شعاع r را به عنوان کرنل در نظر میگیریم. Mean-Shift یک الگوریتم تپهنوردی Hill-climbing است که به طور مکرر در هر مرحله این کرنل را به ناحیهای با تراکم بالاتر منتقل میکند تا به همگرایی برسد.
- در هر تکرار، پنجره لغزان، نقاط مرکزی را به میانگین نقاط موجود در پنجره تبدیل میکند و از این طریق به سمت نواحی با تراکم بالاتر حرکت میکند. میزان تراکم پنجره لغزان به تعداد نقاطی بستگی دارد که درون آن وجود دارند. بدیهی است با تغییر میانگین نقاط موجود در پنجره، پنجره لغزان به صورت تدریجی به سمت نواحی با تراکم بالاتر حرکت میکند.
- تا زمانیکه هیچ جهتی وجود نداشته باشد که در آن بتوانیم نقاط بیشتری در کرنل جای دهیم، به تغییر و حرکت دادن پنجره لغزان مطابق با میانگین ادامه میدهیم. به تصویر فوق نگاه کنید؛ تا زمانی که دیگر نتوانیم تراکم ( تعداد نقاط موجود در پنجره) را افزایش دهیم، به جابهجا کردن دایره ادامه میدهیم.
- مراحل یک تا سه برای تعداد زیادی پنجره لغزان تکرار میشود تا زمانیکه تمامی نقاط در یک پنجره قرار بگیرند. زمانیکه چندین پنجره لغزان با هم همپوشانی پیدا کردند، پنجرهای که بیشترین تعداد نقطه در آن قرار دارد حفظ میشود. سپس نقطهدادهها مطابق پنجرههای لغزانی که در آن قرار دارند، خوشهبندی میشوند.
در تصویر مقابل این فرایند به طور کامل به همراه تمامی پنجرههای لغزان نشان داده شده است. هر نقطه سیاه نشاندهنده مرکز خوشه یک پنجره لغزان است و هر نقطه خاکستری نشاندهنده یک نقطهداده است.
بر خلاف الگوریتم خوشهبندی k میانگین، در این الگوریتم لازم نیست تعداد خوشهها را مشخص کنیم چراکه الگوریتم Mean-Shift به صورت خودکار این کار را انجام میدهد که مزیت بزرگی برای این الگوریتم به حساب میآید. این واقعیت که مراکز خوشهها به سوی نقاطی با بالاترین تراکم همگرایی پیدا میکنند، موضوعی مطلوب و خوشایند است چراکه به درک و شناخت دادهها کمک میکند. نقطه ضعف این الگوریتم این است که انتخاب اندازه پنجره/ شعاع r ممکن است دشوار باشد.
الگوریتم خوشهبندی مکانی داده های دارای نویز بر مبنای چگالی (DBSCAN)
DBSCAN یکی دیگر از الگوریتمهای خوشهبندی است؛ این الگوریتم بر مبنای چگالی کار میکند و مشابه الگوریتم Mean-Shift است اما دو مزیت بزرگ دارد. به تصویر مقابل توجه کنید:
- الگوریتم DBSCAN با نقطه دلخواهی که مشاهده نشده، آغاز میشود. همسایگی این نقطه دلخواه با استفاده از فاصله اپسیلون استخراج میشود ( تمامی نقاطی که در فاصله قرار دارند، نقاط همسایه محسوب میشوند).
- در صورت وجود نقطهدادههای کافی ( مطابق با minpoints) در این همسایگی، عملیات خوشهبندی آغاز میشود و نقطهدادههای موجود، اولین نقطههای خوشه خواهند بود. اگر غیر از این باشد، نقطه، نویز برچسبگذاری میشود ( ممکن است این نقطه نویزی به بخشی از خوشه تبدیل شود). در هر دو حالت، این نقطه با عنوان «مشاهده شده» برچسبگذاری میشود.
- نقاطی که در فاصله همسایگی اولین نقطه موجود در خوشه قرار دارند، بخشی از خوشه را تشکیل میدهند. این فرایند ( تمامی نقاطی که در همسایگی قرار دارند؛ در همان خوشه جای میگیرند) برای تمامی نقاط جدید که به تازگی به گروه خوشه اضافه شدهاند، تکرار میشود.
- مراحل 2 و 3 تا زمانیکه تمامی نقاط موجود در خوشه مشخص شوند، تکرار میشود؛ به عبارت دیگر این دو مرحله تا زمانیکه تمامی نقاط موجود در همسایگی خوشه بازدید و برچسبگذاری شوند، تکرار میشوند.
- پس از اتمام فرایند خوشهبندی در خوشه کنونی، یک نقطه جدید که بازدید نشده، استخراج و پردازش میشود و خوشه و یا نویز دیگری شناسایی میشود و تا زمانیکه تمامی نقاط با عنوان «بازدید شده» برچسبگذاری نشوند، این فرایند تکرار میشود. در پایان این فرایند تمامی نقاط با عنوان «بازدید شده» برچسبگذاری شدهاند و در نتیجه مشخص میشود چه نقاطی به خوشه و چه نقاطی به نویز تعلق دارند.
الگوریتم DBSCAN مزایایی دارد. اول اینکه در این الگوریتم لازم نیست از قبل تعداد خوشهها را مشخص کنیم. علاوه بر این، بر خلاف الگوریتم Mean-Shift که حتی اگر نقطهداده بسیار متفاوت باشد، دادههای پرت را در خوشه جای میدهد، این الگوریتم دادههای پرت را نویز در نظر میگیرد. همچنین این الگوریتم میتواند خوشههایی که سایز دلخواهی دارند و یا به دلخواه ایجاد شدهاند را شناسایی کند.
اصلیترین نقطهضعف الگوریتم DBSCAN در این است که بر خلاف سایر الگوریتمهای خوشهبندی، زمانیکه خوشهها چگالی متفاوتی داشته باشند، عملکرد خوبی ندارد. دلیل عملکرد ضعیف این الگوریتم در اینگونه موارد این است که زمانیکه چگالی خوشهها متفاوت باشد، آستانه فاصله و minpointها برای تشخیص نقاط همسایه از خوشهای به خوشه دیگر متفاوت خواهد بود. علاوه بر این، در مواجهه با دادههایی با ابعاد بالا نیز این نقطه ضعف نمایان میشود چرا که در این حالت تخمین آستانه فاصله دشوار است.
خوشهبندی بیشینهسازی انتظار با استفاده از مدلهای مخلوط گوسی
یکی از اصلیترین ایرادات الگوریتم k میانگین این است که از میانگین به عنوان مرکز خوشه استفاده میکند. در تصویر زیر به خوبی نشان داده شده چرا استفاده از این مقدار مناسب نیست. با نگاه کردن به سمت چپ تصویر متوجه میشویم که دو خوشه دایرهای با شعاع متفاوت وجود دارد که در مرکز همان میانگین قرار گرفتهاند. به دلیل اینکه میانگین خوشهها بسیار به هم نزدیک هستند، الگوریتم k عملکرد خوبی ندارد. علاوه بر این، زمانیکه خوشهها دایرهای نیستند و باز هم به دلیل اینکه از میانگین به عنوان مرکز خوشه استفاده میشود، الگوریتم k میانگین عملکرد خوبی ندارد.
مدلهای مخلوط گوسی Gaussian mixture models انعطافپذیری بیشتری نسبت به الگوریتم k میانگین دارند. هنگام استفاده از GMMها فرض بر این است که توزیع نقطهدادهها گوسی است. در این حالت دو پارامتر برای توصیف شکل خوشهها داریم؛ میانگین و انحراف از معیار. اگر نمونهای دو بعدی داشته باشیم، استفاده از این دو پارامتر به این معنا است که شکل خوشهها میتواند بیضی شکل باشد ( به این دلیل که در جهت x و همچنین y یک انحراف از معیار داریم). در نتیجه توزیع هر خوشه به سمت توزیع گوسی میل میکند.
[irp posts=”4440″]
به منظور پیدا کردن پارامترهای گوسی برای هر یک از خوشهها ( میانگین و انحراف از معیار) از یک الگوریتم بهینهسازی موسوم به الگوریتم بیشینهسازی انتظار (EM) استفاده میکنیم. به تصویر مقابل توجه کنید که در آن منحنیهای گوسی در خوشهها جای میگیرند. سپس میتوانیم عملیات خوشهبندی بیشینهسازی انتظار Expectation-maximization (EM) را با استفاده از GMMها اجرا نماییم.
- ابتدا تعداد خوشهها را انتخاب میکنیم (همانند کاری که k میانگین انجام میدهد) و به صورت تصادفی پارامترهای توزیع گوسی را برای هر یک از خوشهها مقداردهی میکنیم. شما میتوانید با نگاه کردن به دادهها، پارامترهای ابتدایی را تخمین بزنید. البته همانگونه که در تصویر فوق مشاهده میکنید، انجام این کار ضروری نیست، چراکه عملکرد منحنیهای گوسی در ابتدا بسیار ضعیف است اما به سرعت بهینه میشوند.
- با توجه به توزیعهای گوسی هر یک از خوشهها، احتمال قرار گرفتن هر نقطهداده را در یک خوشه مشخص محاسبه میکنیم. هر چه نقطهای به مرکز گوسی نزدیکتر باشد، احتمال اینکه به آن خوشه تعلق داشته باشد، بیشتر است. از آنجاییکه در توزیع گوسی فرض بر این است که اکثر دادهها نزدیک به مرکز خوشه قرار میگیرند، تشخیص اینکه هر نقطهداده به کدام خوشه تعلق دارد، آسانتر است.
- بر مبنای این احتمالات، مجموعه جدیدی از پارامترها برای توزیعهای گوسی محاسبه میکنیم و از این طریق احتمال نقطهدادههای موجود در خوشهها را به حداکثر میرسانیم. پارامترهای جدید را با استفاده از مجموع وزنی موقعیت نقطه دادهها محاسبه میکنیم که در آن وزنها، احتمال تعلق داشتن نقطهدادهها به همان خوشه هستند. برای آنکه این حالت را به صورت تصویری توضیح دهیم، بهتر است به تصویر فوق، به ویژه خوشههای زرد رنگ نگاهی بیندازید. توزیع به صورت تصادفی در اولین تکرار آغاز میشود اما همانگونه که در تصویر فوق مشاهده میکنید، اکثر نقاط زرد رنگ در سمت راست توزیع قرار دارند. در نتیجه میانگین توزیع به سمت همان مجموعه نقطهها میل میکند. علاوه بر این، همانگونه که در تصویر فوق مشاهده میکنید، اکثر نقطهها در قسمت « بالا سمت راست تا پایین سمت چپ» قرار گرفتهاند. بنابراین، انحراف از معیار تغییر میکند تا شکلی بیضی ایجاد کند که متناسب با این نقاط باشد و مجموعی که به وسیله احتمالات وزندهی شده است را به حداکثر برساند.
- تا زمان رسیدن به همگرایی، زمانیکه دیگر توزیعها از تکراری به تکرار دیگر، تغییر نکنند، مرحله 2 و 3 به صورت مکرر تکرار میشوند.
استفاده از GMMها دو مزیت بزرگ دارد. اول اینکه GMMها ( در مقایسه با k میانگین) به لحاظ کوواریانس خوشه، انعطافپذیری بیشتری دارند؛ به دلیل استفاده از پارامتر انحراف از معیار، شکل خوشهها به جای اینکه فقط به دایره محدود باشد، میتوانند بیضی شکل باشند. الگوریتم k میانگین مورد خاصی از GMM است که در آن کوواریانس هر یک از خوشهها به همراه تمامی ابعاد به 0 نزدیک میشود. دوم، به دلیل اینکه GMMها از احتمالات استفاده میکنند، به ازای هر نقطهداده میتوانند چندین خوشه داشته باشند. در نتیجه اگر یک نقطهداده در مرکز دو خوشه که همپوشانی دارند، قرار داشته باشد، با فرض اینکه این نقطهداده x درصد به کلاس 1 و y درصد به کلاس 2 تعلق دارد، به سادگی میتوانیم کلاس آن نقطه را مشخص کنیم. به عبارت دیگر GMMها از عضویت مختلط Mixed membership پشتیبانی میکنند.
الگوریتم خوشهبندی سلسله مراتبی تجمعی
الگوریتمهای خوشهبندی سلسله مراتبی به دو دسته تقسیم میشوند: بالا به پایین یا پایین به بالا. الگوریتمهای پایین به بالا هر یک از نقطهدادهها را یک خوشه واحد در نظر میگیرند و سپس به صورت پیاپی هر خوشه را با یک خوشه دیگر ادغام میکنند (یا تجمیع میکنند) تا زمانیکه یک خوشه واحد ایجاد شود که تمامی نقطهدادهها را در خود جای دهد. خوشهبندی سلسله مراتبی پایین به بالا، خوشهبندی سلسله مراتبی تجمعی Agglomerative hierarchical clustering یا HAC نامیده میشوند. سلسله مراتب خوشهها به صورت یک درخت (یا دندروگرام) نشان داده میشود. ریشه درخت خوشهای است که تمامی نمونهها را جمع میکند و در مقابل برگهای این درخت خوشههایی هستند که فقط یک نمونه دارند. به تصویر مقابل نگاه کنید:
- در ابتدا هر یک از نقطهدادهها را یک خوشه در نظر میگیریم؛ برای مثال اگر X نقطهداده در دیتاست وجود داشته باشد، X خوشه خواهیم داشت. سپس معیاری برای فاصله انتخاب میکنیم که فاصله بین دو خوشه را اندازهگیری کند. برای مثال، از پیوند میانگین Average linkage استفاده خواهیم کرد که فاصله میان دو خوشه را میانگین فاصله میان نقطهدادههای موجود در اولین خوشه و نقطهدادههای موجود در دومین در نظر میگیرد.
- در هر تکرار، دو خوشه را با یکدیگر ادغام میکنیم تا یک خوشه واحد ایجاد شود. سپس دو خوشهای که قرار است با یکدیگر ادغام شوند را به عنوان خوشههایی با کوچکترین پیوند میانگین انتخاب میکنیم. به عبارت دیگر، بر مبنای معیاری که برای فاصله انتخاب کردهایم، این دو خوشه کمترین فاصله را با یکدیگر دارند و در نتیجه بیشترین شباهت را با یکدیگر دارند و باید با هم ترکیب شوند.
- تا زمانیکه به ریشه درخت برسیم، مرحله دوم تکرار میشود. به عبارت دیگر فقط یک خوشه داریم که تمامی نقطهدادهها در آن جای گرفتهاند. در این حالت با تعیین اینکه زمان پایان گرفتن ترکیب یک خوشه با خوشه دیگر (زمانی که ساختن درخت را متوقف میکنیم) تعداد خوشههایی که نیاز داریم را انتخاب میکنیم.
در خوشهبندی سلسله مراتبی نیازی به تعیین تعداد خوشه ها نیست و به دلیل اینکه در حال ساخت درختی هستیم، میتوانیم خوشههایی که ظاهر بهتری دارند را انتخاب کنیم. علاوه بر این، این الگوریتم در انتخاب معیاری برای اندازهگیری فاصله انعطافپذیری دارد، چرا که تمامی آنها در این الگوریتم عملکرد یکسانی دارند، برخلاف سایر الگوریتمهای خوشهبندی که در آنها انتخاب معیار برای اندازهگیری فاصله بسیار حساس و حیاتی است. یکی از موارد کاربرد الگوریتم خوشهبندی سلسله مراتبی زمانی است که دادههای اصلی ساختاری سلسله مراتبی دارند و شما میخواهید این ساختار سلسله مراتبی را حفظ کنید، سایر الگوریتمهای خوشهبندی قادر به انجام این کار نیستند. خوشهبندی سلسله مراتبی معایبی همچون کارایی پایین هم دارد، چراکه برخلاف پیچیدگی زمانی k میانگین و GMM، پیچیدگی زمانی آن برابر با است.
نتیجهگیری
در این نوشتار به معرفی 5 الگوریتم برتر خوشهبندی پرداختیم که تمامی متخصصین علوم داده باید با آنها آشنایی داشته باشند! این نوشتار را با ارائه تصویری که در آن نحوه عملکرد خوب (به دلیل استفاده از Scikit Learn) این 5 الگوریتم و الگوریتمهای دیگر نشان داده شده است به پایان میرسانیم. مقایسه عملکرد الگوریتمهای مختلف در مواجهه با دادهها گوناگون جالب است.