Antipole Clustering

Traduzione e Integrazione delle Lezioni a cura di Sandro Gallo

Home Cure Sequence Matching

Definiamo 1-mediana(centroide) c di un sottoinsieme S di uno spazio metrico, come quell'elemento che minimizza la distanza media dagli altri elementi di S, cioè c in S minimizza la:
image not found
La 1-mediana di S si calcola in quattro passi:

  1. Dividi S in triple random.
  2. Per ogni tripla T seleziona la 1-mediana e butta via gli altri.
  3. Continua ricorsivamente fino ad ottenere una sola 1-mediana che è quella dell'insieme S.
Il calcolo della 1-mediana ha complessità lineare, infatti sia |S| = n = 3r, allora l'algoritmo esegue esattamentedistanze.
Dimostriamolo per induzione. CVD
Sia S un insieme di oggetti di uno spazio metrico (X,d), sia s un numero reale positivo. Un s-antipole per S è una coppia (a,b) di elementi di S tali che d(a,b)>s. Se d(a,b) è massimale, a e b si dicono poli e la loro distanza si chiama diametro. Il calcolo dell'antipole è simile al calcolo della 1-mediana:
  1. Dividi S in triple random.
  2. Per ogni tripla T seleziona i poli a e b. Se d(a,b)>s stop e l'output è la coppia (a,b).
    Altrimenti butta via il terzo elemento, cioè la 1-mediana, e vai avanti.
  3. Ripeti ricorsivamente i passi sopra fino a trovare una coppia con diametro >s . O fino a FAIL.
Anche la complessità di questo algoritmo è lineare e vengono eseguite 9n distanze, essendo n =|S|. Se il diametro del cluster ha soglia s, la dimensione di ogni cluster sarà < s. L'algoritmo di antipole clustering è il seguente:
  1. Calcola l'antipole. Se è Fail non spezzare e ritorna il cluster.
  2. Altrimenti sia (a,b) l'antipole tale che d(a,b)>s . Allora spezza in due sottoinsiemi secondo la maggiore vicinanza ad a o b.
  3. Continua ricorsivamente fino ad ottenere l'insieme finale di cluster.
Con questo metodo è possibile costruire un antipole-tree su cui fare ricerche.

Home Cure Sequence Matching