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