I set di dati di machine learning possono avere milioni ma non tutti gli algoritmi di clustering sono scalabili in modo efficiente. Clustering di molti algoritmi calcolano la somiglianza tra tutte le coppie di esempi, significa che il tempo di esecuzione aumenta al quadrato del numero di esempi \(n\), indicata come \(O(n^2)\) nella notazione della complessità. \(O(n^2)\) gli algoritmi non sono per i set di dati con milioni di esempi.
L'algoritmo k-means ha un complessità di \(O(n)\), il che significa che l'algoritmo scala in modo lineare con \(n\). Questo algoritmo sarà il fulcro di questo corso.
Tipi di clustering
Per un elenco esaustivo dei diversi approcci al clustering, vedi Un sondaggio completo sugli algoritmi di clustering Xu, D. & Tian, Y. Anna Dati. Sci (2015) 2: 165. Ogni approccio è il più adatto a di una particolare distribuzione di dati. Questo corso illustra brevemente quattro comuni approcci.
Clustering basato su centroidi
Il centroid di un cluster è il media aritmetica di tutti i punti in un cluster Kubernetes. Il clustering basato su Centroid organizza i dati in categorie non gerarchiche cluster. Gli algoritmi di clustering basati su centroidi sono efficienti ma sensibili le condizioni iniziali e gli outlier. Tra questi, K-means è il ampiamente utilizzato. Richiede che gli utenti definiscano il numero di centroidi, k e funziona bene con cluster di dimensioni all'incirca uguali.
Clustering basato sulla densità
Il clustering basato sulla densità connette aree contigue ad alta densità di esempio in cluster. Ciò consente di scoprire un numero qualsiasi di cluster di qualsiasi forma. I valori anomali non vengono assegnati ai cluster. Questi algoritmi hanno difficoltà cluster di densità diversa e dati con dimensioni elevate.
Clustering basato sulla distribuzione
Questo approccio di clustering presuppone che i dati siano composti da dati distribuibili, come Distribuzioni gaussiane: Nella Figura 3, l'algoritmo basato sulla distribuzione raggruppa i dati in tre distribuibili. Con l'aumento della distanza dal centro di distribuzione, la probabilità che un punto appartenga alla distribuzione diminuisce. Spettacolo delle band che diminuiscono di probabilità. Quando non puoi presumere che un particolare distribuzione dei dati sottostante, dovresti utilizzare un algoritmo diverso.
Clustering gerarchico
Il clustering gerarchico crea una struttura di cluster. Clustering gerarchico, non sorprende che sia particolarmente adatto a dati gerarchici, come le tassonomie. Consulta Confronto di 61 genomi di Escherichia coli sequenziati di Oksana Lukjancenko, Trudy Wassenaar e Dave Ussery per un esempio. È possibile scegliere un numero qualsiasi di cluster tagliando l'albero al livello giusto.
