مجموعه داده‌های یادگیری ماشینی می‌توانند میلیون‌ها مثال داشته باشند، اما همه الگوریتم‌های خوشه‌بندی به طور موثر مقیاس نمی‌شوند. بسیاری از الگوریتم‌های خوشه‌بندی شباهت بین همه جفت‌های مثال را محاسبه می‌کنند، به این معنی که زمان اجرای آنها با مجذور تعداد نمونه‌ها \(n\)افزایش می‌یابد که در نماد پیچیدگی با \(O(n^2)\) نشان داده می‌شود. الگوریتم‌های \(O(n^2)\) برای مجموعه‌های داده با میلیون‌ها مثال کاربردی نیستند.
الگوریتم k-means دارای پیچیدگی \(O(n)\)است، به این معنی که الگوریتم به صورت خطی با \(n\)مقیاس می شود. این الگوریتم تمرکز این دوره خواهد بود.
انواع خوشه بندی
برای فهرستی جامع از رویکردهای مختلف خوشه‌بندی، به بررسی جامع الگوریتم‌های خوشه‌بندی Xu, D. & Tian, Y. Ann مراجعه کنید. داده ها. علمی (2015) 2: 165. هر رویکرد به بهترین وجه برای یک توزیع داده خاص مناسب است. این دوره به طور خلاصه چهار رویکرد رایج را مورد بحث قرار می دهد.
خوشه بندی مبتنی بر مرکز
مرکز یک خوشه، میانگین حسابی تمام نقاط خوشه است. خوشه بندی مبتنی بر مرکز داده ها را در خوشه های غیر سلسله مراتبی سازماندهی می کند. الگوریتم‌های خوشه‌بندی مبتنی بر مرکز، کارآمد هستند، اما به شرایط اولیه و نقاط پرت حساس هستند. از این میان، k-means بیشترین استفاده را دارد. از کاربران می‌خواهد که تعداد مرکز، k را تعریف کنند و با خوشه‌هایی با اندازه تقریباً مساوی به خوبی کار می‌کند.
خوشه بندی مبتنی بر چگالی
خوشه‌بندی مبتنی بر چگالی نواحی به هم پیوسته با چگالی مثال بالا را به خوشه‌ها متصل می‌کند. این امکان کشف هر تعداد خوشه با هر شکلی را فراهم می کند. نقاط پرت به خوشه ها اختصاص داده نمی شوند. این الگوریتم ها با خوشه هایی با چگالی و داده های مختلف با ابعاد بالا مشکل دارند.
خوشه بندی مبتنی بر توزیع
این رویکرد خوشه‌بندی فرض می‌کند که داده‌ها از توزیع‌های احتمالی، مانند توزیع‌های گاوسی تشکیل شده‌اند. در شکل 3، الگوریتم مبتنی بر توزیع داده ها را در سه توزیع گاوسی خوشه بندی می کند. با افزایش فاصله از مرکز توزیع، احتمال تعلق یک نقطه به توزیع کاهش می یابد. باندها آن کاهش احتمال را نشان می دهند. وقتی از فرض توزیع زیربنای خاصی از داده ها راحت نیستید، باید از الگوریتم دیگری استفاده کنید.
خوشه بندی سلسله مراتبی
خوشه بندی سلسله مراتبی درختی از خوشه ها را ایجاد می کند. تعجب آور نیست که خوشه بندی سلسله مراتبی برای داده های سلسله مراتبی مانند طبقه بندی ها مناسب است. برای مثال به مقایسه 61 ژنوم اشرشیاکلی توالی یافته توسط Oksana Lukjancenko، Trudy Wassenaar و Dave Ussery مراجعه کنید. هر تعداد خوشه را می توان با بریدن درخت در سطح مناسب انتخاب کرد.
