با مجموعه‌ها، منظم بمانید ذخیره و طبقه‌بندی محتوا براساس اولویت‌های شما.
مجموعه داده‌های یادگیری ماشینی می‌توانند میلیون‌ها مثال داشته باشند، اما همه الگوریتم‌های خوشه‌بندی به طور موثر مقیاس نمی‌شوند. بسیاری از الگوریتم های خوشه بندی شباهت بین همه جفت مثال ها را محاسبه می کنند، به این معنی که زمان اجرا آنها با مجذور تعداد نمونه ها افزایش می یابد. \(n\)، نشان داده شده است \(O(n^2)\) در نماد پیچیدگی \(O(n^2)\) الگوریتم‌ها برای مجموعه‌های داده با میلیون‌ها مثال کاربردی نیستند.
الگوریتم k-means دارای پیچیدگی است \(O(n)\)، به این معنی که الگوریتم به صورت خطی با \(n\). این الگوریتم تمرکز این دوره خواهد بود.
انواع خوشه بندی
برای فهرستی جامع از رویکردهای مختلف خوشه‌بندی، به بررسی جامع الگوریتم‌های خوشه‌بندی Xu, D. & Tian, Y. Ann مراجعه کنید. داده ها علمی (2015) 2: 165. هر رویکرد به بهترین وجه برای یک توزیع داده خاص مناسب است. این دوره به طور خلاصه چهار رویکرد رایج را مورد بحث قرار می دهد.
خوشه بندی مبتنی بر مرکز
مرکز یک خوشه، میانگین حسابی تمام نقاط خوشه است. خوشه بندی مبتنی بر مرکز داده ها را در خوشه های غیر سلسله مراتبی سازماندهی می کند. الگوریتم‌های خوشه‌بندی مبتنی بر مرکز، کارآمد هستند، اما به شرایط اولیه و نقاط پرت حساس هستند. از این میان، k-means بیشترین استفاده را دارد. از کاربران می‌خواهد که تعداد مرکز، k را تعریف کنند و با خوشه‌هایی با اندازه تقریباً مساوی به خوبی کار می‌کند.
شکل 1: نمونه ای از خوشه بندی مبتنی بر مرکز.
خوشه بندی مبتنی بر چگالی
خوشه‌بندی مبتنی بر چگالی نواحی به هم پیوسته با چگالی مثال بالا را به خوشه‌ها متصل می‌کند. این امکان کشف هر تعداد خوشه با هر شکلی را فراهم می کند. نقاط پرت به خوشه ها اختصاص داده نمی شوند. این الگوریتم ها با خوشه هایی با چگالی و داده های مختلف با ابعاد بالا مشکل دارند.
شکل 2: نمونه ای از خوشه بندی مبتنی بر چگالی.
خوشه بندی مبتنی بر توزیع
این رویکرد خوشه‌بندی فرض می‌کند که داده‌ها از توزیع‌های احتمالی، مانند توزیع‌های گاوسی تشکیل شده‌اند. در شکل 3، الگوریتم مبتنی بر توزیع داده ها را در سه توزیع گاوسی خوشه بندی می کند. با افزایش فاصله از مرکز توزیع، احتمال تعلق یک نقطه به توزیع کاهش می یابد. باندها آن کاهش احتمال را نشان می دهند. وقتی از فرض توزیع زیربنای خاصی از داده ها راحت نیستید، باید از الگوریتم دیگری استفاده کنید.
شکل 3: نمونه ای از خوشه بندی مبتنی بر توزیع.
خوشه بندی سلسله مراتبی
خوشه بندی سلسله مراتبی درختی از خوشه ها را ایجاد می کند. جای تعجب نیست که خوشه بندی سلسله مراتبی برای داده های سلسله مراتبی مانند طبقه بندی ها مناسب است. برای مثال به مقایسه 61 ژنوم اشرشیاکلی توالی یافته توسط Oksana Lukjancenko، Trudy Wassenaar و Dave Ussery مراجعه کنید. هر تعداد خوشه را می توان با بریدن درخت در سطح مناسب انتخاب کرد.
شکل 4: نمونه ای از درخت سلسله مراتبی که حیوانات را خوشه بندی می کند.
تاریخ آخرین بهروزرسانی 2025-06-09 بهوقت ساعت هماهنگ جهانی.
[null,null,["تاریخ آخرین بهروزرسانی 2025-06-09 بهوقت ساعت هماهنگ جهانی."],[[["\u003cp\u003eMany clustering algorithms have a complexity of O(n^2), making them impractical for large datasets, while the k-means algorithm scales linearly with a complexity of O(n).\u003c/p\u003e\n"],["\u003cp\u003eClustering approaches include centroid-based, density-based, distribution-based, and hierarchical clustering, each suited for different data distributions and structures.\u003c/p\u003e\n"],["\u003cp\u003eCentroid-based clustering, particularly k-means, is efficient for grouping data into non-hierarchical clusters based on the mean of data points, but is sensitive to initial conditions and outliers.\u003c/p\u003e\n"],["\u003cp\u003eDensity-based clustering connects areas of high data density, effectively discovering clusters of varying shapes, but struggles with clusters of differing densities and high-dimensional data.\u003c/p\u003e\n"],["\u003cp\u003eDistribution-based clustering assumes data follows specific distributions (e.g., Gaussian), assigning points based on probability, while hierarchical clustering creates a tree of clusters, suitable for hierarchical data.\u003c/p\u003e\n"]]],[],null,["Machine learning datasets can have millions of\nexamples, but not all clustering algorithms scale efficiently. Many clustering\nalgorithms compute the similarity between all pairs of examples, which\nmeans their runtime increases as the square of the number of examples \\\\(n\\\\),\ndenoted as \\\\(O(n\\^2)\\\\) in complexity notation. \\\\(O(n\\^2)\\\\) algorithms are not\npractical for datasets with millions of examples.\n\nThe [**k-means algorithm**](/machine-learning/glossary#k-means) has a\ncomplexity of \\\\(O(n)\\\\), meaning that the algorithm scales linearly with \\\\(n\\\\).\nThis algorithm will be the focus of this course.\n\nTypes of clustering\n\nFor an exhaustive list of different approaches to clustering, see\n[A Comprehensive Survey of Clustering Algorithms](https://link.springer.com/article/10.1007/s40745-015-0040-1)\nXu, D. \\& Tian, Y. Ann. Data. Sci. (2015) 2: 165. Each approach is best suited to\na particular data distribution. This course briefly discusses four common\napproaches.\n\nCentroid-based clustering\n\nThe [**centroid**](/machine-learning/glossary#centroid) of a cluster is the\narithmetic mean of all the points in the\ncluster. **Centroid-based clustering** organizes the data into non-hierarchical\nclusters. Centroid-based clustering algorithms are efficient but sensitive to\ninitial conditions and outliers. Of these, k-means is the most\nwidely used. It requires users to define the number of centroids, *k*, and\nworks well with clusters of roughly equal size.\n**Figure 1: Example of centroid-based clustering.**\n\nDensity-based clustering\n\nDensity-based clustering connects contiguous areas of high example density into\nclusters. This allows for the discovery of any number of clusters of any shape.\nOutliers are not assigned to clusters. These algorithms have difficulty with\nclusters of different density and data with high dimensions.\n**Figure 2: Example of density-based clustering.**\n\nDistribution-based clustering\n\nThis clustering approach assumes data is composed of probabilistic\ndistributions, such as\n[**Gaussian distributions**](https://wikipedia.org/wiki/Normal_distribution). In\nFigure 3, the distribution-based algorithm clusters data into three Gaussian\ndistributions. As distance from the distribution's center increases, the\nprobability that a point belongs to the distribution decreases. The bands show\nthat decrease in probability. When you're not comfortable assuming a particular\nunderlying distribution of the data, you should use a different algorithm.\n**Figure 3: Example of distribution-based clustering.**\n\nHierarchical clustering\n\n**Hierarchical clustering** creates a tree of clusters. Hierarchical clustering,\nnot surprisingly, is well suited to hierarchical data, such as taxonomies. See\n[*Comparison of 61 Sequenced Escherichia coli Genomes*](https://www.researchgate.net/figure/Pan-genome-clustering-of-E-coli-black-and-related-species-colored-based-on-the_fig1_45152238)\nby Oksana Lukjancenko, Trudy Wassenaar \\& Dave Ussery for an example.\nAny number of clusters can be chosen by cutting the tree at the right level.\n**Figure 4: Example of a hierarchical tree clustering animals.** **Key terms:**\n|\n| - [k-means algorithm](/machine-learning/glossary#k-means)\n| - [centroid](/machine-learning/glossary#centroid)\n| - [Gaussian distributions](/machine-learning/glossary#Normal_distribution)"]]
