Metodi partizionali

I metodi partizionali sono caratterizzati da un procedimento con lo scopo di ripartire direttamente le 𝑛 unità in 𝑔 gruppi prefissati, producendo una sola partizione finale delle unità. Tutto ciò avviene attraverso una procedura iterativa, in cui ad ogni passo viene rimessa in discussione la partizione ottenuta e le unità vengono riallocate. Difatti, l’assegnazione di un’unità a un gruppo non è irrevocabile. A differenza dei metodi gerarchici, che spesso richiedono un’eccessiva onerosità in termini di calcoli, i metodi partizionali riducono il costo computazionale fissando a priori il numero di gruppi. In questo modo è richiesta la valutazione solamente di un numero accettabile di possibili partizioni alternative. Inoltre, mentre i processi gerarchici ricercano l’ottima partizione in assoluto, quelli partizionali intendono raggiungere una soluzione soddisfacente basandosi sull’ottimizzazione di una funzione obiettivo prestabilita. L’inizializzazione della procedura avviene fissando il numero di gruppi da considerare e indicando i valori dei centri iniziali dei gruppi da cui partire nella fase di aggregazione. Anche in questa tipologia di metodi esistono diversi algoritmi, che differiscono per i seguenti aspetti:

1) come sono stabiliti i centri di partenza;

2) come le unità vengono assegnate ai diversi centri; 3) come le unità vengono riassegnate a differenti gruppi.

In genere, data la partizione iniziale, il metodo tende a migliorarla in funzione del criterio obiettivo stabilito, che di solito consiste nel minimizzare la varianza (o generalmente diversità) interna. Le procedure non gerarchiche sono suddivise fondamentalmente in quattro fasi.

• Inizializzazione: si fissa il numero di gruppi in cui raggruppare le unità e si scelgono i centri provvisori che producono la prima partizione temporanea. Tale aggregazione avviene sulla

129

base della minima distanza tra unità e questi centri; ogni unità viene aggregata al gruppo più vicino, calcolando la minor distanza tra unità e centro.

• Determinazione dei nuovi centri: vengono calcolati i baricentri dei gruppi ottenuti attraverso il processo di aggregazione avvenuto nella fase precedente. I baricentri appena calcolati vengono scelti come nuovi centri provvisori.

• Individuazione della nuova partizione: viene ripetuto il processo di allocazione delle unità ai gruppi sulla base della distanza minima dai nuovi centri trovati. Si ripete la partizione con la precedente fase.

• Arresto: quando il procedimento di riallocazione non modifica la composizione dei gruppi, la procedura si ferma in quanto non è possibile ottenere una partizione più soddisfacente. Il metodo k-means (o delle k-medie) rappresenta l’algoritmo partizionale di uso più comune. Esso segue le fasi generali di una procedura non gerarchica con qualche piccola variante che consente di ottenere più rapidamente la partizione ottimale. Nella procedura classica, i centri sono ricalcolati solo al termine della procedura di assegnazione delle unità ai diversi gruppi in base alla distanza minima. Nell’algoritmo k-means, invece, ogni volta che un’unità viene assegnata ad un gruppo, viene immediatamente ricalcolato il baricentro di quest’ultimo e pure quello del gruppo a cui l’unità apparteneva. Questa variante implica un “assestamento” dei centri che avviene ad ogni singola assegnazione e non al termine di ogni fase della procedura. Tutto ciò consente di raggiungere la convergenza del metodo con un minor numero di iterazioni rispetto alle soluzioni classiche. Per ridurre i tempi di calcolo, l’interruzione della procedura viene prevista nei casi di:

- convergenza dell’algoritmo;

- distanza tra ciascun centro ricalcolato e il corrispondente centro precedente non supera una soglia prefissata;

- raggiungimento del limite massimo di iterazioni stabilite.

In termini di qualità delle soluzioni, il metodo k-means non garantisce il raggiungimento dell’ottimo globale ma può convergere ad un ottimo locale. La qualità della soluzione finale dipende per lo più dall’insieme dei centri provvisori e si può ottenere un risultato finale ben

130

peggiore dell’ottimo globale. Al variare dei centri di partenza, è possibile ottenere partizioni finali differenti. Inoltre, questo metodo risulta particolarmente sensibile a dati rumorosi e outliers. Un altro metodo partizionale diffuso è l’algoritmo k-medoids o PAM (partition around medoids), correlato all’algoritmo k-means. Mentre nel metodo k-means il centro di un gruppo è un punto “artificiale” poiché rappresenta la media dei valori di tutte le unità presenti nel gruppo, nel metodo k-medoids viene usato come centro l’unità collocata più centralmente tra quelle appartenenti al gruppo. Un medoid viene dunque definito come un’unità di un cluster la cui dissimilarità media rispetto alle altre unità del cluster è minima; in tal modo essa rappresenta il punto più centrale di un dato gruppo. È possibile applicare questo algoritmo anche se la tipologia di dati non permette di calcolare la media, come le variabili categoriali. Inoltre, rappresenta un metodo più robusto in presenza di outliers. La procedura in questo caso inizia con la scelta arbitraria dei 𝑘 medoids dalle unità da raggruppare e la successiva assegnazione delle rimanenti unità al medoid più vicino (o simile). Lo step seguente consiste nella valutazione della sostituzione di ognuno dei medoids con un’unità non-medoid. Si effettua la sostituzione solamente se essa porta ad ottenere un clustering migliore, altrimenti la partizione resta invariata. Per valutare la qualità della partizione viene spesso usato l’errore assoluto, definito come:

𝐸𝑟𝑟 = ∑ ∑ 𝑑(𝑝, 𝑚𝑖) 𝑝∈𝐶𝑖

𝑘 𝑖=1

dove 𝐶𝑖 è il gruppo 𝑖-esimo, 𝑚𝑖 è il medoid rappresentativo di 𝐶𝑖 e 𝑑 è una misura di distanza.

Se l’unità 𝑖 è un medoid che viene sostituito con il nuovo medoid ℎ, l’errore assoluta varia. Questa variazione è rappresentata in formula come:

𝑇𝑖ℎ = ∑ 𝐶𝑗𝑖ℎ 𝑛 𝑗=1

dove 𝑛 è il numero di unità e 𝐶𝑗𝑖ℎ è la componente dell’errore relativo all’unità 𝑗.

131

1. L’unità j passa dal gruppo del vecchio medoid i al gruppo del nuovo medoid h. L’unità j è più distante dal medoid t che dal nuovo medoid h, cioè: 𝑑(𝑗, ℎ) < 𝑑(𝑗, 𝑡). In questo caso la variazione può essere sia positiva che negativa. La formula risulta essere:

𝐶_𝑗𝑖ℎ = 𝑑(𝑗, ℎ) − 𝑑(𝑗, 𝑖)

2. L’unità j resta assegnata all’altro medoid t. In questo scenario la variazione è nulla, ossia: 𝐶_𝑗𝑖ℎ = 0

3. L’unità j passa dal gruppo del vecchio medoid i al gruppo dell’altro medoid t. L’unità j è più vicina al medoid t che al nuovo medoid h, cioè: 𝑑(𝑗, ℎ) ≥ 𝑑(𝑗, 𝑡). In questa situazione la variazione è sempre non negativa. In formula:

𝐶𝑗𝑖ℎ = 𝑑(𝑗, 𝑡) − 𝑑(𝑗, 𝑖)

4. L’unità j passa dal gruppo dell’altro medoid t al gruppo del nuovo medoid h. L’unità j è più vicina al nuovo medoid h che all’altro medoid t, cioè: 𝑑(𝑗, ℎ) < 𝑑(𝑗, 𝑡) < 𝑑(𝑗, 𝑖). Questa variazione risulta sempre negativa e risulta:

𝐶𝑗𝑖ℎ = 𝑑(𝑗, ℎ) − 𝑑(𝑗, 𝑡)

L’obiettivo per migliorare la partizione è quello di minimizzare la variazione dell’errore nel passaggio da un medoid ad un altro e sostituirli nel caso che essa sia negativa.