Rappresentazioni, distanze e metodi di clustering

Rappresentazioni in clustering

• rappresentazione esterna: per ogni entità, l’informazione è data dalla relazione tra essa e un’altra.
• rappresentazione interna: ogni entità è identificata da un vettore di numeri.

Raggruppare vettori simili conoscendo la rappresentazione interna è molto facile, basta calcolare la distanza euclidea. Fanno eccezione i casi in cui l’input non può essere normalizzato.

Alcuni esempi di distanza:

• Distanza euclidea:

  $${𝛿}_{𝐸\left(𝑥,𝑦\right)}=\Vert 𝑦-𝑥\Vert =\sqrt{\sum _{𝑖=1}^{𝑛}{\left({𝑥}_{𝑖}-{𝑦}_{𝑖}\right)}^2}$$

• Norma di Manhattan: distanza misurata solo muovendosi in verticale o in orizzontale:

  $${𝑑}_{𝑖,𝑗}^{\text{Manhattan}}={\Vert {𝑥}_{𝑖}-{𝑥}_{𝑗}\Vert }_1=\sum _{𝑘=1}^{𝑛}\left|{𝑥}_{𝑖,𝑘}-{𝑥}_{𝑗,𝑘}\right|$$

• Angolo del prodotto scalare:

  $$cos\left(𝜃\right)=\frac{𝑥\cdot 𝑦}{\Vert 𝑥\Vert \Vert 𝑦\Vert }$$

Può essere utile normalizzare le componenti dei vettori quando si calcola la distanza euclidea, ad esempio dividendo ogni componente per il suo intervallo di variazione:

$${𝛿}_{\text{norm}}\left(𝒙,𝒚\right)=\sqrt{\sum _{𝑖=1}^{𝑛}{\left(\frac{{𝑥}_{𝑖}-{𝑦}_{𝑖}}{{max}_{𝑖}-{min}_{𝑖}}\right)}^2}$$

dove ${max}_{𝑖}$ e ${min}_{𝑖}$ sono i valori massimo e minimo della componente $𝑖$-esima nell’insieme di dati.

Queste misure di distanza, essendo basate sulle relazioni tra coppie di entità, costituiscono invece una rappresentazione esterna.

Hard e soft clustering

• Hard clustering: gli insiemi di partizione sono disgiunti, l’obiettivo è quello di minimizzare le dissimilarità tra elementi dello stesso sottoinsieme e di massimizzare la distanza tra elementi di insiemi diversi.
• Soft clustering: l’appartenenza ad una certa classe è espressa da un numero, quindi i confini tra i sottoinsiemi si sovrappongono parzialmente.

K-means

L’algoritmo di k-means è un algoritmo partizionale: partiziona l’insieme di dati in $𝑘$ sottoinsiemi disgiunti a partire da un insieme di prototipi iniziali.

Per ogni cluster, il prototipo (di solito la media delle componenti) viene calcolato minimizzando l’errore di quantizzazione.

$$𝐸=\sum _{𝑑}{\Vert {𝑥}_{𝑑}-{𝑝}_{𝑐\left(𝑑\right)}\Vert }^2$$

1. si sceglie il numero di cluster ($𝑘$);
2. si generano in maniera casuale $𝑘$ prototipi;

3. si ripete finché non viene soddisfatto un criterio di arresto:

   • si assegna ogni punto al cluster il cui prototipo è più vicino;
   • si sposta il prototipo nella posizione data dalla media dei punti che gli appartengono;

Soft clustering

In alcuni casi, l’assegnamento di un’entità ad un cluster non è netto ma dipende da una probabilità:

Il valore di appartenenza ad un certo cluster può essere dato da:

$$\text{membership}\left(𝑥,𝑐\right)=\frac{{𝑒}^{-𝛿\left(𝑥,{𝑝}_{𝑐}\right)}}{{\sum }_{𝑐}{𝑒}^{-𝛿\left(𝑥,{𝑝}_{𝑐}\right)}}$$

L’aggiornamento dei centroidi può essere eseguito in modo leggermente diverso. Il centroide viene ‘tirato’ da ogni entità di una distanza proporzionale al grado di membership e alla learning rate $𝑛$. Il contributo di una singola entità è:

$$\mathrm{\Delta }{𝑝}_{𝑐}=𝑛\text{membership}\left(𝑥,𝑐\right)\left(𝑥-{𝑝}_{𝑐}\right)$$$${𝑝}_{{𝑐}_{\text{next}}}={𝑝}_{𝑐}+\mathrm{\Delta }{𝑝}_{𝑐}$$

Ci sono due versioni leggermente differenti:

• online update: ogni volta che si osserva un’entità, si sposta immediatamente il centroide;
• batch update: prima si trovano tutte le entità appartenenti al cluster, poi si sposta il centroide con la somma di tutti i contributi;