Birch*

Traduzione e Integrazione delle Lezioni a cura di Sandro Gallo

Home Fastmap e Multiscaling Cure

Birch è l'acronimo di balanced iterative reducing and clustering using hierarchy. È una tecnica di clustering per database di grandi dimensioni, che usa un approccio gerarchico e clusterizza usando le caratteristiche del cluster invece dei punti.
In più sfrutta una struttura dati chiamata CF*-tree, un albero bilanciato i cui nodi corrispondono a blocchi del disco. Lo spazio metrico su cui agisce Birch* non deve essere necessariamente euclideo.
In generale un approccio gerarchico clusterizza nel seguente modo:

1. Inizia con n cluster fatti dai singoli punti.
2. Ripetutamente seleziona i due cluster più vicini da fondere rispetto ad una certa misura di distanza.
3. Concludi quando il clustering diventa buono cioè:
   1. O sfruttando un approccio k-means si generano k cluster,
   2. Oppure quando ogni possibile merging di cluster violerebbe qualche vincolo di compattezza.

1. La distanza tra i centroidi/clustroidi.
2. La distanza media tra i nodi nei due cluster.
3. Oppure la distanza minima o massima.

1. Nelle foglie mettiamo le caratteristiche dei cluster:
   1. N = cardinalità del cluster
   2. il clustroide, cioè il punto che minimizza la
      
   3. Sia p una costante fissata, i p punti X'i del cluster più vicino a con le loro
      
      per i = 1, ..., p
   4. I p punti Xi” del cluster più lontani da e le loro
      
      per i=1, ..., p.

• Nei nodi interni mettiamo campioni dei clustroidi dei cluster rappresentati dai discendenti del dato nodo. Questi serviranno, nell'inserimento di un nuovo punto, a discendere lungo l'albero per trovare il cluster dove inserirlo.
• L'algoritmo ha una prima fase di inizializzazione nella quale si prende un campione di punti che si sistema nel CF*-tree costruendo i primi cluster.
  Quindi ogni volta che si deve aggiungere un punto si cerca il cluster dove inserirlo usando i clustroidi lungo un cammino. Se il punto viene assorbito dal cluster, si aggiornano tutte le statistiche aggiungendo il quadrato della distanza di da ciascuno dei 2p+1 punti. Quindi si stima la distanza di come:
  
  dove r è una stima di
  .
  Questo perchè la scomposizione di un segmento XY genera due segmenti
  
  perpendicolari per fenomeni di alta dimensionalità. A questo punto dovremo verificare se il clustroide è cambiato o meno cercando il punto con
  
  minima per i = 1, ..., 2p+1.
  Se il punto non è assorbito dal cluster, cioè se il raggio del clustroide supera una data soglia, allora dovremo spezzare il cluster in due, così aumenterà il numero di foglie di una unità. Questo spezzamento potrà causare altri spezzamenti a catena per riaggiustare tutto l'albero.
  Se i cluster si spezzettano troppo potrà essere necessario fonderli attraverso l'albero e aumentare la soglia. Per fondere due cluster Ci, Cj senza caricare tutti i punti in memoria, dobbiamo stimare la
  .
  Supponiamo che allora:
  .
  Trovato il nuovo clustroide, calcolo le
  
  stimandole come sopra.

Home Fastmap e Multiscaling Cure