Mantieni tutto organizzato con le raccolte Salva e classifica i contenuti in base alle tue preferenze.
I set di dati di machine learning possono contenere milioni di esempi, ma non tutti gli algoritmi di clustering sono scalabili in modo efficiente. Molti algoritmi di clustering calcolano la somiglianza tra tutte le coppie di esempi, il che significa che il loro tempo di esecuzione aumenta in base al quadrato del numero di esempi \(n\), indicato come \(O(n^2)\) nella notazione della complessità.Gli algoritmi \(O(n^2)\) non sono pratici per i set di dati con milioni di esempi.
L'algoritmo k-means ha una complessità di \(O(n)\), il che significa che l'algoritmo si espande in modo lineare con \(n\). Questo algoritmo sarà l'argomento centrale di questo corso.
Tipi di clustering
Per un elenco esaustivo dei diversi approcci al clustering, consulta A Comprehensive Survey of Clustering Algorithms Xu, D. e Tian, Y. Ann. Data. Sci. (2015) 2: 165. Ogni approccio è più adatto a una determinata distribuzione dei dati. Questo corso illustra brevemente quattro approcci comuni.
Clustering basato su centroidi
Il centroide di un cluster è la media aritmetica di tutti i punti del cluster. Il clustering basato su centroidi organizza i dati in cluster non gerarchici. Gli algoritmi di clustering basati su centroidi sono efficienti, ma sensibili alle condizioni iniziali e agli outlier. Di questi, k-means è il più utilizzato. Richiede agli utenti di definire il numero di centroidi, k, e funziona bene con cluster di dimensioni approssimativamente uguali.
Figura 1: esempio di raggruppamento basato su centroidi.
Clustering basato sulla densità
Il clustering basato sulla densità collega aree contigue con una densità elevata di esempi in cluster. Ciò consente di scoprire un numero qualsiasi di cluster di qualsiasi forma. Gli outlier non vengono assegnati ai cluster. Questi algoritmi hanno difficoltà con i cluster di densità diverse e con i dati con dimensioni elevate.
Figura 2: esempio di clustering basato sulla densità.
Raggruppamento basato sulla distribuzione
Questo approccio di clustering presuppone che i dati siano costituiti da distribuzioni probabilistiche, come le distribuzioni Gaussiane. Nella Figura 3, l'algoritmo basato sulla distribuzione raggruppa i dati in tre distribuzioni gaussiane. All'aumentare della distanza dal centro della distribuzione, la probabilità che un punto appartenga alla distribuzione diminuisce. Le bande mostrano questa diminuzione di probabilità. Se non ti senti a tuo agio nell'assumere una determinata distribuzione di fondo dei dati, devi utilizzare un algoritmo diverso.
Figura 3: esempio di raggruppamento basato sulla distribuzione.
Clustering gerarchico
L'aggregazione gerarchica crea un albero di cluster. Non sorprende che il clustering gerarchico sia adatto ai dati gerarchici, come le tassonomie. Per un esempio, consulta Comparison of 61 Sequenced Escherichia coli Genomes di Oksana Lukjancenko, Trudy Wassenaar e Dave Ussery. È possibile scegliere un numero qualsiasi di cluster tagliando l'albero al livello giusto.
Figura 4: esempio di albero gerarchico che raggruppa gli animali.
[[["Facile da capire","easyToUnderstand","thumb-up"],["Il problema è stato risolto","solvedMyProblem","thumb-up"],["Altra","otherUp","thumb-up"]],[["Mancano le informazioni di cui ho bisogno","missingTheInformationINeed","thumb-down"],["Troppo complicato/troppi passaggi","tooComplicatedTooManySteps","thumb-down"],["Obsoleti","outOfDate","thumb-down"],["Problema di traduzione","translationIssue","thumb-down"],["Problema relativo a esempi/codice","samplesCodeIssue","thumb-down"],["Altra","otherDown","thumb-down"]],["Ultimo aggiornamento 2025-06-09 UTC."],[[["\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)"]]
