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.
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.
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.
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.
