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

زمینه

ما هر روز تقریبا 2. 5 بایت 5 میلیارد بایت از داده ها تولید می کنیم. این داده ها اشکال شخصیت ها ، اعداد ، متن ، تصویر ، صدا و غیره را به خود اختصاص می دهند. جای تعجب آور نیست که بیشتر این داده ها بدون برچسب و بینش های مفید در زیر کوه داده ها دفن می شوند. خوشه بندی یک روش یادگیری بدون نظارت است که به طور گسترده ای برای یافتن گروه هایی از نقاط داده (به نام خوشه ها) با خصوصیات مشابه بدون نیاز به داده های دارای برچسب موجود استفاده می شود.

با کمک روشهای خوشه بندی ، می توانیم داده های خام را به بینش های عملی تبدیل کنیم. به عنوان مثال ، ما می توانیم پیامهایی را که به اشتراک می گذارند یکسان ، تصاویر گروهی که متعلق به همان شی هستند ، به اشتراک بگذاریم ، مشتریان را با رفتارهای مشابه در همان گروه طبقه بندی کنیم. در این مقاله ، ما می خواهیم در مورد متداول ترین روش خوشه بندی صحبت کنیم: خوشه بندی K-.

شماره 1: K-Means چیست؟

به زبان ساده ، هدف K- معنی قرار دادن نقاط داده با خصوصیات مشابه در همان خوشه (یعنی انسجام داخلی) و نقاط داده جداگانه با خصوصیات مختلف در خوشه های مختلف (یعنی جداسازی خارجی) است.

از نظر فنی ، ما برای تعیین کمیت انسجام داخلی و جداسازی خارجی به فرمول های ریاضی نیاز داریم.

• واریانس داخل گروه (a. k. a. ، عملکرد خطای مربع یا جمع مربعات موجود در (SSW) یا مجموع خطای مربع (SSE)) برای تعیین کمیت انسجام داخلی استفاده می شود. این به عنوان مجموع فاصله مربع بین نقطه متوسط (به نام سانتروئید) و هر نقطه از خوشه تعریف شده است. هرچه مقدار کوچکتر باشد ، خوشه بندی بهتر است.

• از واریانس بین خوشه ای (a. k. a ، تعداد مربعات بین (SSB)) برای تعیین کمیت جداسازی خارجی استفاده می شود. این به عنوان مجموع فاصله مربع بین میانگین نقطه جهانی و هر سانتروئید تعریف شده است. هرچه ارزش بزرگتر باشد ، خوشه بندی بهتر است.

در عمل ، ما فقط باید واریانس درون خوشه ای را به حداقل برسانیم زیرا به حداقل رساندن SSW (مبالغ درون خوشه ای مربع) لزوماً SSB را به حداکثر می رساند (مبالغ بین خوشه مربع)

بیایید از یک مثال ساده برای اثبات آن استفاده کنیم. در مثال زیر ، ما می خواهیم بر اساس مقادیر نمره خوشه هایی ایجاد کنیم. اگر ما به سادگی سه مشاهده اول را به گروه 1 و سه مشاهده آخر در گروه 2 گروه بندی کنیم. ما برای گروه 1 به طور متوسط 25 امتیاز 25 و 16 برای گروه 2 کسب کردیم. می دانیم که میانگین جهانی (20. 5) همیشه بدون در نظر گرفتن یکسان استاز نحوه ایجاد خوشه ها. بنابراین SST (مجموع فاصله مربع بین هر نقطه و میانگین جهانی) نیز همیشه یکسان خواهد بود. از نظر ریاضی ، اثبات SST = SSW + SSB دشوار نیست. بنابراین ، یافتن خوشه هایی که SSW را به حداقل می رساند ، به طور غیرمستقیم SSB را به حداکثر می رساند.

شماره 2: خوشه بندی K-Mean چگونه کار می کند؟

مرحله 1: با انتخاب تصادفی نقاط شروع K به طور تصادفی ، سانتروئیدهای خوشه ای را آغاز کنید

مرحله 2: هر نقطه داده را به نزدیکترین سانتروئید اختصاص دهید. محاسبه فاصله متداول برای خوشه بندی k-mean فاصله اقلیدسی ، یک مقدار مقیاس است که فاصله بین دو نقطه داده را اندازه گیری می کند.

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

مرحله 4: مراحل 2-3 (اختصاص هر نقطه داده به سانتروئیدهای جدید و به روزرسانی سانتروئیدهای خوشه ای) را تکرار کنید تا یکی از شرایط توقف برآورده شود.

• Centroids به روز شده مانند مواردی که از تکرار قبلی است باقی می مانند (این یک وضعیت ایده آل است ، اما در عمل ممکن است خیلی وقت گیر باشد)
• SSE حداقل x ٪ بهبود نیاورد
• حداکثر تعداد تکرارها به دست آمده است (حداکثر تکرار را با عاقلانه انتخاب کنید ، در غیر این صورت ، ما خوشه های ضعیفی خواهیم داشت.)

شماره 3: چگونه می توان داده های خام را برای K-Means پیش بینی کرد؟

K-Means از اندازه گیری های مبتنی بر فاصله (به عنوان مثال ، فاصله اقلیدسی) برای محاسبه چگونگی مشابه هر نقطه داده با سانتروئیدها با استفاده از مقادیر از تمام ویژگی ها استفاده می کند. این ویژگی ها معمولاً در واحدهای غیرقابل مقایسه مقادیر می گیرند (به عنوان مثال ، ارز به دلار ، وزن در کیلوگرم ، درجه حرارت در فارنهایت). به منظور ایجاد یک نتیجه عادلانه ، توصیه می شود داده های خام را استاندارد سازی کنید. ما می توانیم داده های خام را تغییر دهیم تا میانگین صفر و انحراف استاندارد از آن داشته باشیم تا تمام ویژگی ها دارای وزن برابر باشند.

شماره 4: چگونه می توان مقدار K را در k-means انتخاب کرد؟

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

روش آرنج: از SSE (a. k. a. ، اینرسی خوشه ای) برای ارزیابی خوبی های تقسیم استفاده می کند. سپس ما برای مقادیر K از 2 تا N یک طرح آرنج SSE ایجاد می کنیم (می توانید ارزش N را برای تحقیقات خود تعیین کنید). با افزایش K ، SSE مربوطه کاهش می یابد. ما تجارت بین K و SSE را مشاهده خواهیم کرد (ما می خواهیم SSE در حالی که K را با ارزش معقول نگه می دارد کم باشد). ما به طور معمول مقدار بهینه K را انتخاب می کنیم وقتی می بینیم SSE شروع به صاف شدن می کند و شکل آرنج را تشکیل می دهد.

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

S (i) ضریب شباهت برای یک نقطه داده معین است. A (i) میانگین فاصله بین این نقطه داده داده شده و سایر نقاط داده در همان خوشه است. B (i) میانگین فاصله بین این نقطه داده داده شده و تمام نقاط داده از نزدیکترین خوشه است. S (i) می تواند ا ز-1 تا 1 باشد.

• اگر s (i) = 1 ، به این معنی است که این نقطه داده نزدیک به نقاط در همان خوشه و دور از خوشه همسایه است.
• اگر s (i) = 0 باشد ، به این معنی است که این نقطه داده در نزدیکی مرز خوشه آن است.
• اگر s (i) = -1 ، به این معنی است که این نقطه داده به خوشه اشتباه اختصاص داده می شود.

ضریب نهایی شبح به عنوان ضریب میانگین شبح در تمام نقاط داده محاسبه می شود. سپس ضرایب شباهت را برای مقادیر K از 2 تا N. محاسبه می کنیم. هرچه ضرایب شباهت بالاتر باشد ، ممکن است خوشه بندی بهتر باشد.

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

D (i ، j) یک شاخص دیویس-بولدین برای یک جفت خوشه معین (به عنوان مثال ، خوشه های I و J) است. D (i) و D (j) به ترتیب فاصله بین هر نقطه و سانتروئید آن در خوشه I و خوشه J به ترتیب است. D (I ، J) فاصله بین سانتروئیدهای خوشه های I و J است.

برای یک خوشه معین ، ما شاخص دیویس-بولدین را بین خود و سایر خوشه ها محاسبه خواهیم کرد. سپس ما حداکثر شاخص دیویس-بولدین را برای این خوشه می گیریم. در پایان ، ما شاخص نهایی دیویس-بولدین را به عنوان میانگین این مقادیر حداکثر محاسبه می کنیم. سپس ما شاخص دیویس-بولدین را برای مقادیر K از 2 تا N. محاسبه می کنیم. هرچه شاخص دیویس-بولدین کوچکتر باشد ، هر چه این خوشه ها دورتر باشند ، خوشه بندی بهتر است.

شماره 5: چگونه می توان نقاط شروع را برای k-means انتخاب کرد؟

حتی اگر مقدار K بهینه را انتخاب کنیم ، روش K- میانگین لزوماً خوشه های بهینه تولید نمی کند. خوشه های حاصل ممکن است بر اساس نقاط مختلف شروع متفاوت باشد زیرا الگوریتم K- میانگین احتمالاً در یک بهینه محلی گیر می کند و هرگز به بهینه جهانی همگرا نمی شود. بنابراین ، بسیار توصیه می شود K-Means را با مجموعه های تصادفی مختلف از نقاط شروع اجرا کنید و بر اساس سه روش ارزیابی ذکر شده در بالا ، بهترین نتیجه را انتخاب کنید.

یک روش اولیه سازی پیشرفته ، مانند K-Means ++ وجود دارد که به آن اجازه می دهد تا مسئله گیر شدن در یک بهینه محلی ضعیف و بهبود کیفیت خوشه بندی را برطرف کند. شهود ساده است. ما سانتروئیدهای اولیه را انتخاب خواهیم کرد که از یکدیگر دور هستند به طوری که احتمالاً امتیاز را از خوشه های مختلف انتخاب می کند. K-Means ++ را می توان در مراحل زیر اجرا کرد.

• مرحله 1: ما به طور تصادفی یک نقطه داده را به عنوان اولین سانتروئید انتخاب می کنیم.
• مرحله 2: ما فاصله بین نقاط باقی مانده را با نزدیکترین سانتروئید محاسبه می کنیم.
• مرحله 3: ما سانتروئید بعدی را به گونه ای انتخاب می کنیم که احتمال انتخاب یک نقطه معین به عنوان سانتروئید متناسب با فاصله بین این نقطه معین و نزدیکترین سانتروئید انتخاب شده آن باشد. به عبارت دیگر ، هرچه نقطه دورتر از سانتروئیدهای منتخب دور باشد ، احتمال آن به عنوان سانتروئید بعدی انتخاب می شود.
• مراحل 2-3 را تکرار کنید تا سانتروئیدهای K انتخاب شوند.

شماره 6: چگونه می توان خوشه های K-Means را در پایتون پیاده سازی کرد؟

در مثال زیر ، من خوشه بندی K-Means را در مجموعه داده های IRIS در پایتون پیاده سازی می کنم. مجموعه داده های Iris شامل 4 متغیر مشخصه (به عنوان مثال ، "طول سپاه" ، "عرض سپال" ، "طول گلبرگ" ، "عرض گلبرگ") و 1 متغیر است که گونه های گل عنبیه را توصیف می کند (به عنوان مثال ، setosa ، versicolor ، virginica)واد

در شکل 1 می توانیم جداسازی نقاط داده را مشاهده کنیم. ما امیدواریم که بتوانیم پس از استفاده از خوشه بندی K- معنی ، نتایج را به همان اندازه نزدیک شکل 2 بدست آوریم.

ما از الگوریتم "Kmeans" از کتابخانه "Sklearn" در پایتون استفاده خواهیم کرد."n_clusters" تعداد خوشه های شکل را نشان می دهد."max_iter" حداکثر تکرارهای انجام شده در یک اجرا را نشان می دهد."N_INIT" تعداد دفعاتی را که K-Means با مجموعه های مختلف نقاط شروع اجرا می کند ، نشان می دهد. init = "تصادفی | k-means ++" نشان می دهد که آیا روش اولیه سازی تصادفی یا اولیه سازی k-means ++ استفاده شده است."Random_State" برای اطمینان از نتیجه قابل تکرار است.

برای محاسبه SSE ، می توانیم از ". inertia_" از خروجی K- معنی استفاده کنیم."Davies_Bouldin_Score" و "silhouette_score" به ترتیب برای محاسبه شاخص دیویس-بولدین و نمره شبح استفاده می شوند.

روش آرنج: در شکل 3 ، ما یک طرح SSE با تعداد خوشه ها داریم. این طرح نشان می دهد که آرنج با مقدار K در حدود 3-5 تشکیل شده است. بعد از K = 5 ، SSE به آرامی کاهش می یابد.

تجزیه و تحلیل silhouette: در شکل 4 ، ما یک طرح از شاخص شبح با تعداد خوشه ها داریم. این طرح نشان می دهد که شاخص سیلوی بالا در مقدار K پایین تر ظاهر می شود (به عنوان مثال ، 2 ، 3).

شاخص دیویس بولدین: در شکل 5 ، ما از فهرست دیویس-بولدین با تعداد خوشه ها استفاده می کنیم. این طرح همچنین نشان می دهد که شاخص پایین دیویس-بولدین با مقدار K پایین تر ظاهر می شود (به عنوان مثال ، 2 ، 3).

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

• شاخص متوسط شبح بالا است.
• خوشه ها تقریباً متعادل هستند ، یعنی خوشه ها تقریباً همان تعداد امتیاز را دارند.
• بیشتر نقاط دارای ضرایب شباهت بالاتری نسبت به شاخص متوسط شبح هستند.

در شکل 6 ، k = 2 ، 3 شاخص شبح نسبتاً بالاتری دارند. اما K = 3 خوشه های متعادل تری دارد. بنابراین ، 3 به احتمال زیاد مقدار بهینه K است.

بر اساس تمام معیارهای مختلف ، به نظر می رسد 3 مقدار بهینه K برای خوشه بندی K-Means است. در آخر ، بیایید خروجی K-Means را با استفاده از K = 3 تولید کنیم. در شکل 7 ، خوشه های پیش بینی شده بسیار دقیق به نظر می رسند ، با توجه به اینکه K-Means از داده های آموزشی از پیش برچسب استفاده نمی کند.

شماره 7: مزایا و اشکالات K- معنی چیست؟

K- میانگین رایج ترین الگوریتم خوشه بندی است زیرا اجرای و تفسیر آن بسیار آسان است. فقط یک پارامتر بیش از حد (مقدار K) برای تنظیم وجود دارد. این ابزاری کارآمد است که می تواند تقریباً در همه انواع مختلف داده ها اعمال شود.

با این حال ، K-Means اشکالاتی آشکار دارد. فرض می کند

• خوشه های مختلف دارای سانتروئیدهای مختلفی هستند که از یکدیگر دور هستند.
• اگر نقطه (الف) دورتر از یک سانتروئید معین از نقطه (b) باشد ، سپس نقطه (الف) کمتر به این خوشه داده شده نسبت به نقطه (b) تعلق دارد.

در مثال اول شکل 8 ، دایره داخلی باید متعلق به یک خوشه باشد و دایره بیرونی باید به یک خوشه دیگر تعلق داشته باشد. اما K-Means نتوانست نقاط را به درستی جمع کند زیرا نمی تواند بر مشکل سانتروئیدهای همپوشانی غلبه کند.

در مثال دوم ، دو محافل نیمی باید متعلق به دو خوشه مجزا باشند ، K-Mean دوباره در شناسایی الگوهای آشکار شکست خورد.

داده های زندگی واقعی تقریباً همیشه پیچیده است زیرا آنها شامل سر و صدا و ناهنجاری هستند. اگرچه خوشه بندی K-Mean ابزاری قدرتمند است ، اما ما نیز باید از محدودیت های آن آگاه باشیم.

از خواندن شما متشکرم

اگر از این مقاله لذت می برید و می خواهید یک قهوه برای من بخرید ، لطفاً اینجا را کلیک کنید.

برای باز کردن دسترسی کامل به مقالات من می توانید برای عضویت در عضویت ثبت نام کنید و دسترسی نامحدودی به همه چیز در رسانه داشته باشید. لطفاً اگر می خواهید هر زمان که مقاله جدیدی ارسال کنم ، یک اعلان ایمیل دریافت کنید.