BFR e k-means

Traduzione e Integrazione delle Lezioni a cura di Sandro Gallo

Home Clustering Fastmap e Multiscaling

Il k-means è un algoritmo di clustering su Ram che sceglie k punti a caso o usando qualche proprietà, ad esempio prendendo i punti sufficientemente lontani tra di loro.
Questi k punti sono i centroidi. Quindi assegna i punti rimanenti al centroide più vicino, ricalcola i centroidi dei cluster ottenuti e riassegna i punti.
L'algoritmo prosegue finchè i cluster ottenuti non variano più.
L'algoritmo BFR è basato su k-means e funziona meglio se i punti sono distribuiti normalmente attorno ad altri punti, magari con deviazioni standard differenti su ogni dimensione. L'algoritmo lavora su spazi euclidei. I punti vengono divisi in tre insiemi:

1. DS, discard set: cioè i punti che fanno effettivamente parte del cluster tanto da associare ad essi delle statistiche.
2. CS, compression set: cioè punti sufficientemente vicini tra di loro per assegnare delle statistiche, ma non abbastanza vicini ai centroidi per far parte dei DS.
3. RS, retained set: i punti isolati.

1. N, cardinalità dell'insieme.
2. SUM, vettore delle somme SUMi delle coordinate su ciascuna dimensione.
3. SUMSQ, vettore delle somme SUMSQi dei quadrati delle coordinate in ciascuna dimensione i.

1. Con il primo carico di punti nella Ram, BFR seleziona i k centroidi con qualche algoritmo su Ram. L'intera Ram piena di punti viene trattata come nei passi successivi.
2. Determina i punti sufficientemente vicini ad un centroide da essere assegnati a un DS, quindi calcola le statistiche e aggiorna quelle precedenti. Per calcolare se un punto è sufficientemente vicino ad un centroide BFR suggerisce due modi:
   1. Scelta una soglia s, calcola il raggio di Mahalanobis e seleziona i punti che hanno il raggio inferiore alla soglia. Il raggio di Mahalanobis è la distanza di un punto dal centroide scalata mediante la deviazione standard si. Più precisamente, sia mi la media nella i-esima dimensione, il raggio di Mahalanobis del punto y = [y1, y2, ..., yk] è
      
   2. Basandosi sul numero di punti nei vari DS, domanda se è probabile (95%) che il centroide più vicino si sposterà lontano da y, e un altro centroide si sposterà sufficientemente vicino a y da diventare più vicino del primo. Se invece ciò è improbabile (<=5%) per cui il centroide attualmente più vicino rimarrà tale, allora assegna y a questo DS e mettilo nel cluster del centroide ad esso più vicino
3. Aggiorna le statistiche per ogni cluster modificato nei DS.
4. Clusterizza nella RAM punti non in DS compresi quelli di RS dei passi precedenti. Se troviamo un sottocluster, cioè un insieme di punti la cui varianza è al di sotto di una certa soglia, assegniamo questi punti ai CS e sostituiamo i punti con le statistiche.
5. Prova a fondere un nuovo sottocluster con uno vecchio purchè la varianza del sottocluster ottenuto sia al di sotto di una certa soglia.
6. Se siamo all'ultimo round assegna gli elementi dei CS e degli RS al più vicino cluster di DS anche se abbastanza lontano.

Home Clustering Fastmap e Multiscaling