FastMap e Multiscaling

Traduzione e Integrazione delle Lezioni a cura di Sandro Gallo

Home BFR e k-means Birch*

Spesso il clustering in spazi metrici non euclidei è difficile.
Per ovviare a questo problema si può immergere uno spazio metrico in uno spazio euclideo in modo da minimizzare la distorsione. Dati due spazi (X,d), (X,d'), una immersione è una funzione f:X-->X' e la distorsione è
Dis(f) = Esp(f) * Contr(f) dove
image not found
è l'espansione,
image not found
è la contrazione.
Le nostre immersioni saranno in spazi euclidei, nonostante non è possibile immergere tutti gli spazi metrici.
Il multiscaling è un metodo di immersione di uno spazio metrico in uno euclideo ad alta dimensione n. Immerge in uno spazio di dimensione k <<n simulando l'alta dimensionalità. L'algoritmo procede così:

  1. Metti n punti random in Rk .
  2. Consideriamo come errore l'energia di un sistema di molle ciascuna di lunghezza D(x,y) tra x e y. L'energia delle molle è il quadrato della differenza tra l'attuale lunghezza e D(x,y).
  3. Visita ogni punto e cerca di porlo in una posizione che minimizzi l'energia totale delle molle. Questo implicherà spostare tutti gli altri punti.
  4. Procedi così fino a trovare un minimo locale che si spera sia anche globale.
Il multiscaling quindi costa almeno O(n2). Fastmap risolve il problema dei costi creando k pseudo-assi che servono a porre gli n punti nello spazio k-dimensionale in tempo O(nk).
Fastmap sceglie k coppie di punti (ai, bi) come estremi dei k assi e calcola la proiezione x di ogni altro punto sugli assi mediante la sola distanza, sfruttando Pitagora. La formula è la seguente:
image not found
Avendo scelto (a,b) come estremi di un asse, parte delle distanze tra due punti c e d è conteggiata dalla proiezione di c e d sull'asse ab, e il resto della distanza è nelle altre dimensioni.
Se le proiezioni di c e d sono x e y, rispettivamente, in futuro quando scegliamo altri assi la distanza Dcurrent(c,d) dovrebbe essere collegata alla distanza data tramite image not found
Fastmap computa per ogni punto c, k proiezioni c1, c2, ..., ck sui k pseudo-assi che sono determinati dalle coppie (a1, b1), (a2, b2), ...(ak, bk).
L'algoritmo procede così:
for i = 2, ..., k do:
  1. Usando Dcurrent scegli ai, bi come segue:
    1. Sia c random
    2. ai il più lontano da c secondo Dcurrent
    3. bi il più lontano da ai e da c
  2. Per ogni x, calcola xi con Pitagora
  3. Aggiorna la definizione di Dcurrent secondo la formula
    image not found
Fastmap nel clustering serve a mappare n punti in k dimensioni in O(nk), dopodichè si può usare un qualche algoritmo di clustering su spazi euclidei.
Un ulteriore miglioramento consiste nell'usare lo spazio euclideo solo per stimare i clustroidi, mentre le distanze vengono calcolate rispetto allo spazio metrico originale.

Home BFR e k-means Birch*