Vediamo rapidamente i tipi di algoritmi di clustering e quando scegliere ogni tipo.
Quando scegli un algoritmo di clustering, valuta se è in grado di scalare il tuo set di dati. I set di dati nel machine learning possono avere milioni di esempi, ma non tutti gli algoritmi di clustering scalano in modo efficiente. Molti algoritmi di clustering funzionano considerando la somiglianza tra tutte le coppie di esempi. Ciò significa che il loro runtime aumenta come il quadrato del numero di esempi \(n\), indicato come \(O(n^2)\) nella notazione della complessità. \(O(n^2)\) gli algoritmi non sono pratici quando il numero di esempi è in milioni. Questo corso è incentrato sull'algoritmo k-means, che ha una complessità di \(O(n)\), ovvero l'algoritmo scala in modo lineare con \(n\).
Tipi di clustering
Esistono diversi approcci al clustering. Per un elenco completo, consulta Un sondaggio completo sugli algoritmi di clustering Xu, D. e Tian, Y. Ind. dati. Sci. (2015) 2: 165. Ciascun approccio è più adatto a una particolare distribuzione di dati. Di seguito è riportata una breve discussione di quattro approcci comuni, incentrata sul clustering basato su centroidi utilizzando k-mean.
Clustering centroid
Il clustering basato su centroid organizza i dati in cluster non gerarchici, in contrasto con il clustering gerarchico definito di seguito. k-means è l'algoritmo di clustering più utilizzato basato sul centroide. Gli algoritmi basati su centroidi sono efficienti, ma sensibili alle condizioni iniziali e alle anomalie. Questo corso è incentrato sui k-means, in quanto si tratta di un algoritmo di clustering efficiente, efficace e semplice.
Cluster basato sulla densità
I cluster basati sulla densità collegano le aree ad alta densità di esempio in cluster. Ciò consente distribuzioni di forma arbitraria, purché sia possibile connettere aree densa. Questi algoritmi hanno difficoltà con i dati con densità diverse e dimensioni elevate. Inoltre, secondo la progettazione, questi algoritmi non assegnano i valori anomali ai cluster.
Cluster basato sulla distribuzione
Questo approccio di clustering presuppone che i dati siano composti da distribuzioni, ad esempio Distribuzioni gaussiane. Nella Figura 3, l'algoritmo basato sulla distribuzione raggruppa i dati in tre distribuzioni di Gauss. All'aumentare della distanza dal centro della distribuzione, la probabilità che un punto appartenga alla distribuzione diminuisce. Le bande mostrano una diminuzione della probabilità. Se non conosci il tipo di distribuzione nei tuoi dati, devi utilizzare un algoritmo diverso.
Cluster gerarchico
Il clustering gerarchico crea una struttura ad albero di cluster. Il clustering gerarchico, invece, non sorprende che sia adatto a dati gerarchici, come le tassonomie. Per un esempio, consulta il confronto di 61 genomi di Escherichia coli in sequenza di Oksana Lukjancenko, Trudy Wassenaar e Dave Ussery. Inoltre, un altro vantaggio è che si può scegliere un numero qualsiasi di cluster tagliando l'albero al livello giusto.
