Clustering

In entrambi i tipi di clustering gerarchico sono necessarie funzioni per selezionare la coppia di cluster da fondere ("agglomerativo"), oppure il cluster da dividere ("divisivo").

Nel primo caso, sono necessarie funzioni che misurino la similarità (o, indistintamente, la distanza) tra due cluster, in modo da fondere quelli più simili. Le funzioni utilizzate nel caso agglomerativo sono:

• Single-link proximity

  

Calcola la distanza tra i due cluster come la distanza minima tra elementi appartenenti a cluster diversi:

${\displaystyle D(C_{i},C_{j})=\min _{x\in C_{i},y\in C_{j}}d(x,y).}$

• Average-link proximity

Questa funzione calcola la distanza tra i due cluster come la media delle distanze tra i singoli elementi:

${\displaystyle D(C_{i},C_{j})={\frac {1}{|C_{i}||C_{j}|}}\sum _{x\in C_{i},y\in C_{j}}d(x,y).}$

• Complete-link proximity

Questa funzione calcola la distanza tra i due cluster come la distanza massima tra elementi appartenenti ai due cluster:

${\displaystyle D(C_{i},C_{j})=\max _{x\in C_{i},y\in C_{j}}d(x,y).}$

• Distanza tra centroidi

La distanza tra i due cluster coincide con la distanza calcolata tra i centroidi (o medioidi):

${\displaystyle D(C_{i},C_{j})=d({\hat {c_{i}}},{\hat {c_{j}}}).}$

• Indice di Dunn

L'indice di Dunn mira a identificare cluster densi e ben separati. È definito come il rapporto tra la minima distanza inter-cluster e la massima distanza intra-cluster. Per ogni partizione del cluster, l'indice di Dunn può essere calcolato con la seguente formula:^[1]

${\displaystyle D(C_{i},C_{j})={\frac {\min _{1\leq i<j\leq n}d(i,j)}{\max _{1\leq k\leq n}d^{\prime }(k)}},}$

dove ${\displaystyle d(i,j)}$ rappresenta la distanza tra i cluster ${\displaystyle i}$ e ${\displaystyle j}$ e ${\displaystyle d'(k)}$ misura la distanza intra-cluster del cluster ${\displaystyle k}$. La distanza inter-cluster ${\displaystyle d(i,j)}$ tra due cluster può essere una qualsiasi misura di distanza, come la distanza tra i centroidi dei cluster. Allo stesso modo, la distanza intra-cluster ${\displaystyle d'(k)}$ può essere misurata in vari modi, come la distanza massima tra qualsiasi coppia di elementi nel cluster ${\displaystyle k}$. Poiché il criterio interno cerca cluster con un'alta somiglianza intra-cluster e una bassa somiglianza inter-cluster, gli algoritmi che producono cluster con un alto indice di Dunn sono più desiderabili^[2].

Nei casi precedenti, ${\displaystyle d(x,y)}$ indica una qualsiasi funzione distanza su uno spazio metrico.

Invece nel clustering divisivo è necessario individuare il cluster da suddividere in due sottogruppi. Per questa ragione sono necessarie funzioni che misurino la compattezza del cluster, la densità o la sparsità dei punti assegnati ad un cluster. Le funzioni normalmente utilizzate nel caso divisivo sono:

• Average internal similarity

Questa funzione valuta la similarità media tra i documenti interni ad un cluster: più sono tra loro dissimili (valori bassi di similarità), più il cluster è da suddividere in sottogruppi:

${\displaystyle D(C_{i})={\frac {1}{|C_{i}|(|C_{i}|-1)}}\sum _{x,y\in C_{i},x\neq y}d(x,y).}$

• Maximum internal distance

Questa funzione valuta la distanza massima tra due punti interni ad un cluster. Tale valore è noto anche come 'diametro del cluster': più tale valore è basso, più il cluster è compatto:

${\displaystyle D(C_{i})=\max _{x,y\in C_{i}}d(x,y).}$