WMR 20 - Clustering

Olte a raggruppare i vari elementi in clusters, potrei anche essere interessati a scoprire delle possibili gerarchie tra i vari clusters.

Consideriamo ad esempio la seguente struttura alborea, chiamata dendrogramma, che rappresenta tassonomia degli animali

Questo tipo di struttura può essere costruita utilizzando in modo ricorsivo tecniche di clustering.

I metodi di direct clustering necessitano di specificare il numero di cluster desiderati \(k\) e i punti da clusterizzare.

È anche necessario definire una clustering evaluation function, che assegna un numero reale che misura la "qualità" di ciascun clustering.

La qualità di un clustering dipende da vari aspetti, tra cui troviamo i seguenti:

• Clustering algorithm:

  • Single Link Agglomerative Clustering.

  • K-Means

  • ...

• Distance (similarity or dissimilarity) function.

• Clustering quality:

  • Inter-clusters distance (to maximize).

  • Intra-clusters distance (to minimize)

Gli algoritmi di clustering gerarchici possono essere di due tipi:

• Agglomerative (bottom-up): inizialmente ciascun esempio rappresenta un cluster separato, e in modo iterativo questi clusters sono combinati tra loro per formare clusters più grandi.

• Divisive (partitional, top-down): Inizialmente tutti gli esempi formano un singolo grande cluster, la radice, e in modo ricorsivo i clusters sono divisi tra loro in un insieme di clusters-child.

Utilizzando il link link si può cadere in un fenomeno noto come il chaining effect, in cui essenzialmente fondo tutti i clusters, uno alla volta, in un singolo cluster che diventa sempre più grande.

Il complete link è molo sensibile alla presena di outliers

Nella prima iterazione tutti i metodi HAC devono calcolare la similarità per ogni coppia di \(n\) punti individuali, il costo computazionale è quindi di \(O(n^2)\). Nei successivi \(n-1\) iterazioni di marging, bisogna comunque calcolare la distanza tra tutti i cluster esistenti.

Questo significa che per avere una overall performance di \(O(n^2)\), il calcolo della similarità deve essere fatto in tempo costante. Esistono però dei trucchi per rendere più efficiente il calcolo della similarità

Supponiamo di lavorare in uno spazio normalizzato, e consideriamo la cosine similarity come misura di similarità.

\[\text{cos(x, y)} = \frac{x \cdot y}{||x||_2 \cdot ||y||_2}\]

Se mantengo per ogni cluster la somma dei vettori

\[\overline{s}(c_j) = \sum\limits_{\overline{x} \in C_j} \overline{x}\]

il calcolo della similarità tra cluster diventa costante, in quanto la posso calcolare come segue

\[\text{sim}(C_i, C_j) = \frac{\Big(\overline{s}(C_i) + \overline{s}(C_j) \Big) \cdot \Big(\overline{s}(C_i) + \overline{s}(C_j) \Big) - (|C_i| + |C_j|)}{(|C_i| + |C_j|)(|C_i| + |C_j| - 1)}\]

Un esempio di algoritmo di clustering non gerarchico è il K-Means, che funziona nel seguente modo.

Siano \(d\) la misura di distanza tra le varie istanze. Inizialmente si selezionano \(k\) random istances \(\{s_1, s_2, \ldots, s_k\}\) come seeds, e si esegue il seguente codice fino a soddisfare il criterio di convergenza:

Until clustering converges:
  For each instance x_i:
     Assign x_i to the cluster c_j such that d(x_i, s_j) is minimal
  # update centroid of each cluster     
  For each cluster c_j
    s_j = \mu(c_j) 

Generalmente i centroidi sono dei punti virtuali e sono calcolati tramite la media. Quando però non possiamo calcolare la media l'idea è quella di utilizzare il medoide, ovvero il punto preso dai punti di training che si avvicina il più possibile a tutti gli altri dello stesso cluster.

Il criterio di convergenza del K-Means è basato su quanti riassegnamenti ho dei vari punti ai vari clusters. Ad esempio mi potrei fermare quando non faccio cambiare cluster a nessun punto, oppure in modo rilassato quando faccio cambiare cluster solamente ad un punto.

L'algoritmo K-Means garantisce che alla terminazione ho minimizzato la summa dello squared error (SSE), che nel caso in cui sto considerando delle distanze ottengo

\[\text{SSE} = \sum\limits_{j = 1}^k \sum\limits_{x \in C_j} \text{dis}(x, m_j)^2\]

dove \(m_J\) è il centroide del cluster \(C_j\).

Il caviat di questo risultato è che il minimo menzionato non è un minimo globale, ma solo locale, e dipende dal punto da cui parto.

Modifica del tipico K-Means con la possibilità di aggiungere/rimuovere clusters durante l'esecuzione.

Segue lo speudocodice:

Let \sigma and \tau be two different thresholds
Let d be the distance measure
Select k random seeds {s_1, \ldots, s_k}
Until clustering converges
  For each instance x_i
     Assign x_i to cluster c_j such that d(x_i, s_j) is minimize but less than \sigma
     Else create new seed with instance x_i (new cluster, k increases)
     
  For each cluster pair c_i, c_j such that i \neq j:
     If d(s_i, s_j) is less than \tau, merge c_i and c_j (k decreases)

Quando si parla di interval-scaled attribute si sta parlando di attributi il cui valore è racchiuso in un intervallo della retta reale.

Sia \(f\) un attributo. Esistono due approcci principali per standardizzare questo tipo di attributi, che sono:

• Range:

  \[\text{range}(x_{i,f}) = \frac{x_{i,f} - \text{min}(f)}{\text{max}(f) - \text{min}(f)}\]

• Z-score: L'idea è quella di trasformare i valori degli attributi in modo tale da avere una media di \(0\) e una mean absolute deviation di \(1\).

  \[\begin{split} s_f &= \frac{1}{n}\Big( |x_{1,f} - m_f | + | x_{2,f} - m_f | + \ldots + | x_{n,f} - m_f | \Big) \\ m_f &= \frac{1}{n}\Big(x_{1,f} + x_{2,f} + \ldots + x_{n,f} \Big)\\ z(x_{i,f}) &= \frac{x_{i,f} - m_f}{s_f} \end{split}\]

Se abbiamo a disposizione dei dati etichettati (per la classificazione), possiamo assumere che ciascun cluster è una classe, calcolare la confusion matrix, e calcolare le solite varie metriche tra cui Precision, Recall, F-score.

Possiamo stimare \(P_i(C_j)\), ovvero la proporzione di data points appartenenti alla classe \(C_j\) nel cluster \(i\)

\[P_i(C_j) = \frac{| C_j \cap D_i |}{|D_i|}\]