L'algoritmo può iniziare con ogni punto nel proprio cluster e unirli progressivamente (clustering agglomerativo), oppure iniziare con tutti i punti in un unico cluster e suddividerli ricorsivamente in cluster più piccoli (clustering divisivo).

Poiché il clustering agglomerativo è l'approccio più comunemente utilizzato, ci concentreremo su questo.

Il tipo più comune di clustering gerarchico è l'approccio dal basso verso l'alto. L'algoritmo è il seguente:

1. Inizializzazione: ogni punto dati è considerato come un singolo cluster;

2. Calcolo della matrice di prossimità: calcolare la distanza tra ogni coppia di cluster;

3. Unione dei cluster: i due cluster più vicini vengono uniti in un unico cluster;

4. Aggiornamento della matrice di prossimità: ricalcolare le distanze tra il nuovo cluster e tutti i cluster rimanenti;

5. Ripetizione: i passaggi 3 e 4 vengono ripetuti fino a quando tutti i punti dati sono uniti in un unico cluster.

Tipi di collegamento

La prossimità tra due cluster è definita dal tipo di collegamento. I metodi di collegamento più comuni utilizzati nel clustering gerarchico sono:

• Collegamento singolo: la distanza tra i due punti più vicini nei due cluster;

• Collegamento completo: la distanza tra i due punti più distanti nei due cluster;

• Collegamento medio: la distanza media tra tutte le coppie di punti nei due cluster;

• Metodo di Ward: minimizza l'aumento della varianza totale all'interno del cluster durante l'unione di due cluster.

La scelta del metodo di collegamento può influenzare la forma e la struttura dei cluster risultanti. La sperimentazione e la conoscenza del dominio sono spesso utili per selezionare il metodo migliore per i propri dati.

Dendrogramma

I risultati del clustering gerarchico sono spesso visualizzati utilizzando un dendrogramma.