Algoritmi di clustering: dall'inizio allo stato dell'arte

Non è un brutto momento per essere un Data Scientist. Le persone serie potrebbero interessarti se giri la conversazione verso "Big Data", e il resto della folla sarà incuriosito quando menzioni "Intelligenza artificiale" e "Apprendimento automatico". Persino Google pensa che tu non sia cattivo e che stai ancora meglio. Esistono molti algoritmi "intelligenti" che aiutano i data scientist a fare le loro magie. Può sembrare tutto complicato, ma se comprendiamo e organizziamo un po' gli algoritmi, non è nemmeno così difficile trovare e applicare quello di cui abbiamo bisogno.

I corsi sul data mining o sull'apprendimento automatico di solito iniziano con il clustering, perché è sia semplice che utile. È una parte importante di un'area alquanto più ampia dell'apprendimento non supervisionato, in cui i dati che vogliamo descrivere non sono etichettati. Nella maggior parte dei casi è qui che l'utente non ci ha fornito molte informazioni su quale sia l'output previsto. L'algoritmo ha solo i dati e dovrebbe fare del suo meglio. Nel nostro caso, dovrebbe eseguire il clustering, separando i dati in gruppi (cluster) che contengono punti dati simili, mentre la dissomiglianza tra i gruppi è la più alta possibile. I punti dati possono rappresentare qualsiasi cosa, come i nostri clienti. Il clustering può essere utile se, ad esempio, desideriamo raggruppare utenti simili e quindi eseguire diverse campagne di marketing su ciascun cluster.

Cluster di mezzi K

Dopo la doverosa introduzione, i corsi di Data Mining continuano sempre con K-Means; un algoritmo di clustering efficace, ampiamente utilizzato e completo. Prima di eseguirlo effettivamente, dobbiamo definire una funzione di distanza tra punti dati (ad esempio, distanza euclidea se vogliamo raggruppare punti nello spazio), e dobbiamo impostare il numero di cluster che vogliamo (k).

L'algoritmo inizia selezionando k punti come centroidi di partenza ("centri" di cluster). Possiamo semplicemente selezionare qualsiasi k punti casuali, oppure possiamo usare qualche altro approccio, ma scegliere punti casuali è un buon inizio. Quindi, ripetiamo in modo iterativo due passaggi:

1. Passaggio di assegnazione: ciascuno degli m punti del nostro set di dati viene assegnato a un cluster rappresentato dal più vicino dei k centroidi. Per ogni punto, calcoliamo le distanze da ciascun baricentro e scegliamo semplicemente quello meno distante.

2. Fase di aggiornamento: per ogni cluster, viene calcolato un nuovo baricentro come media di tutti i punti del cluster. Dal passaggio precedente, abbiamo una serie di punti assegnati a un cluster. Ora, per ciascuno di questi insiemi, calcoliamo una media che dichiariamo un nuovo baricentro del cluster.

Dopo ogni iterazione, i centroidi si muovono lentamente e la distanza totale da ciascun punto al centroide assegnato diventa sempre più bassa. I due passaggi vengono alternati fino alla convergenza, ovvero fino a quando non ci sono più modifiche nell'assegnazione dei cluster. Dopo un certo numero di iterazioni, lo stesso insieme di punti verrà assegnato a ciascun centroide, portando quindi di nuovo agli stessi centroidi. K-Means è garantito per convergere verso un ottimo locale. Tuttavia, questa non deve essere necessariamente la migliore soluzione complessiva (ottimo globale).

Il risultato finale del clustering può dipendere dalla selezione dei centroidi iniziali, quindi è stata data molta attenzione a questo problema. Una soluzione semplice è eseguire K-Means un paio di volte con assegnazioni iniziali casuali. Possiamo quindi selezionare il miglior risultato prendendo quello con la somma minima delle distanze da ciascun punto al suo cluster, il valore di errore che stiamo cercando di minimizzare in primo luogo.

Altri approcci alla selezione dei punti iniziali possono basarsi sulla selezione di punti distanti. Questo può portare a risultati migliori, ma potremmo avere un problema con i valori anomali, quei rari punti soli che sono semplicemente "off" che potrebbero essere solo alcuni errori. Dal momento che sono lontani da qualsiasi cluster significativo, ciascuno di questi punti potrebbe finire per essere il proprio "cluster". Un buon equilibrio è la variante K-Means++ [Arthur e Vassilvitskii, 2007], la cui inizializzazione sceglierà comunque punti casuali, ma con probabilità proporzionale alla distanza quadrata dai centroidi precedentemente assegnati. I punti più lontani avranno una maggiore probabilità di essere selezionati come centroidi iniziali. Di conseguenza, se c'è un gruppo di punti, anche la probabilità che un punto del gruppo venga selezionato aumenta man mano che le loro probabilità si sommano, risolvendo il problema anomalo che abbiamo menzionato.

K-Means++ è anche l'inizializzazione predefinita per l'implementazione di K-Means di Scikit-learn di Python. Se stai usando Python, questa potrebbe essere la tua libreria preferita. Per Java, la libreria Weka potrebbe essere un buon inizio:

Giava (Weka)

 // Load some data Instances data = DataSource.read("data.arff"); // Create the model SimpleKMeans kMeans = new SimpleKMeans(); // We want three clusters kMeans.setNumClusters(3); // Run K-Means kMeans.buildClusterer(data); // Print the centroids Instances centroids = kMeans.getClusterCentroids(); for (Instance centroid: centroids) { System.out.println(centroid); } // Print cluster membership for each instance for (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point)); }

Python (Scikit-impara)

 > >> from sklearn import cluster, datasets > >> iris = datasets.loadiris() > >> Xiris = iris.data > >> yiris = iris.target > >> kmeans = cluster.KMeans(nclusters=3) > >> kmeans.fit(Xiris) KMeans(copy_x=True, init='k-means++', ... > >> print(kmeans.labels[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

Nell'esempio Python sopra, abbiamo utilizzato un set di dati di esempio standard "Iris", che contiene le dimensioni del petalo del fiore e del sepalo per tre diverse specie di iris. Li abbiamo raggruppati in tre gruppi e abbiamo confrontato i gruppi ottenuti con le specie effettive (bersaglio), per vedere che corrispondevano perfettamente.

In questo caso, sapevamo che c'erano tre diversi cluster (specie) e K-Means riconosceva correttamente quali vanno insieme. Ma come scegliamo un buon numero di cluster k in generale? Questo tipo di domande sono abbastanza comuni in Machine Learning. Se richiediamo più cluster, questi saranno più piccoli e quindi l'errore totale (totale delle distanze dai punti ai cluster assegnati) sarà inferiore. Quindi, è una buona idea impostare una k più grande? Possiamo concludere con k = m, cioè ogni punto è il proprio baricentro, con ogni cluster che ha un solo punto. Sì, l'errore totale è 0, ma non abbiamo ottenuto una descrizione più semplice dei nostri dati, né è abbastanza generale da coprire alcuni nuovi punti che potrebbero apparire. Questo si chiama overfitting e non lo vogliamo.

Un modo per affrontare questo problema consiste nell'includere alcune penalità per un numero maggiore di cluster. Quindi, ora stiamo cercando di ridurre al minimo non solo l'errore, ma anche l' errore + penalità . L'errore convergerà semplicemente verso zero man mano che aumenteremo il numero di cluster, ma la penalità aumenterà. In alcuni punti, il guadagno derivante dall'aggiunta di un altro cluster sarà inferiore alla penalità introdotta e avremo il risultato ottimale. Una soluzione che utilizza il Bayesian Information Criterion (BIC) per questo scopo è chiamata X-Means [Pelleg and Moore, 2000].

Un'altra cosa che dobbiamo definire correttamente è la funzione distanza. A volte è un compito semplice, logico data la natura dei dati. Per i punti nello spazio, la distanza euclidea è una soluzione ovvia, ma può essere complicata per caratteristiche di "unità" diverse, per variabili discrete, ecc. Ciò potrebbe richiedere molte conoscenze di dominio. Oppure possiamo chiamare Machine Learning per chiedere aiuto. Possiamo effettivamente provare ad imparare la funzione della distanza. Se abbiamo un insieme di punti di addestramento di cui sappiamo come dovrebbero essere raggruppati (cioè punti etichettati con i loro gruppi), possiamo utilizzare tecniche di apprendimento supervisionato per trovare una buona funzione e quindi applicarlo al nostro insieme di obiettivi che non è ancora raggruppato .

Il metodo utilizzato in K-Means, con i suoi due passaggi alternati, ricorda un metodo Expectation–Maximization (EM). In realtà, può essere considerata una versione molto semplice di EM. Tuttavia, non dovrebbe essere confuso con il più elaborato algoritmo di clustering EM anche se condivide alcuni degli stessi principi.

Cluster EM

Quindi, con il clustering K-Means, ogni punto è assegnato a un solo cluster e un cluster è descritto solo dal suo centroide. Questo non è troppo flessibile, poiché potremmo avere problemi con i cluster che si sovrappongono o quelli che non sono di forma circolare. Con EM Clustering, ora possiamo fare un ulteriore passo avanti e descrivere ciascun cluster in base al suo centroide (media), covarianza (in modo da poter avere cluster ellittici) e peso (la dimensione del cluster). La probabilità che un punto appartenga a un cluster è ora data da una distribuzione di probabilità gaussiana multivariata (multivariata - a seconda di più variabili). Ciò significa anche che possiamo calcolare la probabilità che un punto sia sotto una 'campana' gaussiana, cioè la probabilità che un punto appartenga a un ammasso.

Iniziamo ora la procedura EM calcolando, per ogni punto, le probabilità che esso appartenga a ciascuno dei cluster correnti (che, ancora, possono essere creati casualmente all'inizio). Questo è il passo E. Se un cluster è davvero un buon candidato per un punto, avrà una probabilità vicina a uno. Tuttavia, due o più cluster possono essere candidati accettabili, quindi il punto ha una distribuzione di probabilità sui cluster. Questa proprietà dell'algoritmo, di punti non appartenenti ad un cluster, è chiamata “soft clustering”.

Il passo M ora ricalcola i parametri di ciascun cluster, utilizzando le assegnazioni di punti al precedente insieme di cluster. Per calcolare la nuova media, covarianza e peso di un cluster, ogni dato di punto viene ponderato in base alla sua probabilità di appartenenza al cluster, come calcolato nel passaggio precedente.

L'alternanza di questi due passaggi aumenterà la probabilità logaritmica totale finché non converge. Anche in questo caso, il massimo può essere locale, quindi possiamo eseguire l'algoritmo più volte per ottenere cluster migliori.

Se ora vogliamo determinare un singolo cluster per ogni punto, possiamo semplicemente scegliere quello più probabile. Avendo un modello di probabilità, possiamo usarlo anche per generare dati simili, cioè per campionare più punti che sono simili ai dati che abbiamo osservato.

Propagazione di affinità

Affinity Propagation (AP) è stato pubblicato da Frey e Dueck nel 2007 e sta diventando sempre più popolare grazie alla sua semplicità, applicabilità generale e prestazioni. Sta cambiando il suo stato da stato dell'arte a standard de facto.

Gli svantaggi principali di K-Means e algoritmi simili sono la necessità di selezionare il numero di cluster e la scelta dell'insieme iniziale di punti. Affinity Propagation, invece, prende come input le misure di somiglianza tra coppie di punti dati e considera contemporaneamente tutti i punti dati come potenziali esempi. I messaggi di valore reale vengono scambiati tra punti dati fino a quando non emerge gradualmente un insieme di alta qualità di esempi e cluster corrispondenti.

Come input, l'algoritmo ci richiede di fornire due set di dati:

1. Somiglianze tra punti dati, che rappresentano quanto sia adatto un punto per essere l'esempio di un altro. Se non c'è somiglianza tra due punti, poiché non possono appartenere allo stesso cluster, questa somiglianza può essere omessa o impostata su -Infinity a seconda dell'implementazione.

2. Preferenze, che rappresentano l'idoneità di ciascun punto dati a essere un esempio. Potremmo avere alcune informazioni a priori su quali punti potrebbero essere favoriti per questo ruolo, e quindi possiamo rappresentarlo attraverso le preferenze.

Sia le somiglianze che le preferenze sono spesso rappresentate attraverso un'unica matrice, dove i valori sulla diagonale principale rappresentano le preferenze. La rappresentazione della matrice è utile per set di dati densi. Laddove le connessioni tra punti sono scarse, è più pratico non memorizzare l'intera matrice nxn in memoria, ma mantenere invece un elenco di somiglianze con i punti collegati. Dietro le quinte, "scambiare messaggi tra punti" è la stessa cosa che manipolare le matrici, ed è solo una questione di prospettiva e implementazione.

L'algoritmo esegue quindi un certo numero di iterazioni, finché non converge. Ogni iterazione ha due passaggi per il passaggio dei messaggi:

1. Calcolo delle responsabilità: la responsabilità r(i, k) riflette l'evidenza accumulata di quanto sia adatto il punto k per fungere da esempio per il punto i, tenendo conto di altri potenziali esempi per il punto i. La responsabilità viene inviata dal punto dati i al punto esemplare candidato k.

2. Calcolo delle disponibilità: la disponibilità a(i, k) riflette l'evidenza accumulata su quanto sarebbe appropriato per il punto i scegliere il punto k come suo esempio, tenendo conto del supporto di altri punti che il punto k dovrebbe essere un esempio. La disponibilità viene inviata dal punto esemplare candidato k al punto i.

Per calcolare le responsabilità, l'algoritmo utilizza le somiglianze e le disponibilità originali calcolate nell'iterazione precedente (inizialmente tutte le disponibilità sono impostate a zero). Le responsabilità sono impostate sulla somiglianza di input tra il punto i e il punto k come esempio, meno la più grande somma di similarità e disponibilità tra il punto i e altri esempi candidati. La logica alla base del calcolo di quanto sia adatto un punto per un esemplare è che è più favorito se la preferenza a priori iniziale era più alta, ma la responsabilità diminuisce quando c'è un punto simile che si considera un buon candidato, quindi c'è un ' concorrenza' tra i due finché uno non viene deciso in qualche iterazione.

Il calcolo delle disponibilità, quindi, utilizza le responsabilità calcolate come prova se ogni candidato sarebbe un buon esemplare. La disponibilità a(i, k) è impostata sull'auto-responsabilità r(k, k) più la somma delle responsabilità positive che il candidato esemplare k riceve da altri punti.

Infine, possiamo avere diversi criteri di arresto per terminare la procedura, ad esempio quando le modifiche ai valori scendono al di sotto di una certa soglia o viene raggiunto il numero massimo di iterazioni. In qualsiasi momento attraverso la procedura di Affinity Propagation, sommando le matrici Responsabilità (r) e Disponibilità (a) ci fornisce le informazioni di clustering di cui abbiamo bisogno: per il punto i, il k con massimo r(i, k) + a(i, k) rappresenta il punto sono esemplare. Oppure, se abbiamo solo bisogno dell'insieme di esempi, possiamo scansionare la diagonale principale. Se r(i, i) + a(i, i) > 0, il punto i è un esempio.

Abbiamo visto che con K-Means e algoritmi simili, decidere il numero di cluster può essere complicato. Con AP, non è necessario specificarlo in modo esplicito, ma potrebbe comunque essere necessario un po 'di ottimizzazione se otteniamo più o meno cluster di quelli che potremmo trovare ottimali. Per fortuna, solo regolando le preferenze possiamo abbassare o aumentare il numero di cluster. Impostare le preferenze su un valore più alto porterà a più cluster, poiché ogni punto è "più certo" della sua idoneità a essere un esempio ed è quindi più difficile da "battere" e includerlo sotto il "dominio" di qualche altro punto. Al contrario, l'impostazione di preferenze più basse comporterà un minor numero di cluster; come se dicessero "no, no, per favore, sei un esempio migliore, mi unirò al tuo gruppo". Come regola generale, possiamo impostare tutte le preferenze sulla somiglianza mediana per un numero medio-alto di cluster, o sulla somiglianza più bassa per un numero moderato di cluster. Tuttavia, potrebbero essere necessarie un paio di corse con le preferenze di regolazione per ottenere il risultato che si adatta esattamente alle nostre esigenze.

Vale anche la pena menzionare la propagazione dell'affinità gerarchica, come variante dell'algoritmo che si occupa della complessità quadratica suddividendo il set di dati in un paio di sottoinsiemi, raggruppandoli separatamente e quindi eseguendo il secondo livello di clustering.

Alla fine…

C'è un'intera gamma di algoritmi di clustering, ognuno con i suoi pro e contro riguardo al tipo di dati che utilizza, complessità temporale, punti deboli e così via. Per citare altri algoritmi, ad esempio c'è il clustering agglomerato gerarchico (o Linkage Clustering), utile quando non abbiamo necessariamente cluster circolari (o ipersferici) e non conosciamo il numero di cluster in anticipo. Inizia con ogni punto che è un cluster separato e funziona unendo due cluster più vicini in ogni passaggio fino a quando tutto è in un grande cluster.

Con il raggruppamento agglomerato gerarchico, possiamo facilmente decidere il numero di cluster in seguito tagliando il dendrogramma (diagramma ad albero) orizzontalmente dove riteniamo opportuno. È anche ripetibile (dà sempre la stessa risposta per lo stesso set di dati), ma è anche di complessità superiore (quadratica).

Quindi, anche DBSCAN (Density-Based Spatial Clustering of Applications with Noise) è un algoritmo degno di nota. Raggruppa punti che sono strettamente impacchettati, espandendo gli ammassi in qualsiasi direzione in cui ci sono punti vicini, trattando così forme diverse di ammassi.

Questi algoritmi meritano un articolo a parte e possiamo esplorarli in un post separato in seguito.

Ci vuole esperienza con alcuni tentativi ed errori per sapere quando utilizzare un algoritmo o l'altro. Fortunatamente, abbiamo una gamma di implementazioni in diversi linguaggi di programmazione, quindi provarli richiede solo un po' di volontà di giocare.