Clustering
Traduzione e Integrazione
delle Lezioni a cura di Sandro Gallo
Home Book and Authors From Sergei Brin
BFR e k-means
È la ricerca di gruppi di oggetti tali che gli elementi
di un gruppo sono simili o in relazione e quelli di gruppi
differenti non lo sono.
Cioè le distanze dentro un cluster sono minimizzate,
mentre quelle tra cluster sono massimizzate.
Una distanza in uno spazio metrico M è una funzione
D:MxM-->R+ tale che:
- D(x,y) = 0 se e solo se x = y
- D(x,y) = D(y,x)
- D(x,y)<=D(x,z)+D(z,y)
Le metriche più usate sono:
L2:
L1:
Se lo spazio metrico è non euclideo il clustering è
più complesso. In più in alte dimensioni le
distanze relative tra i punti sono molto vicine alla media e i
vettori sono tutti quasi ortogonali.
Abbiamo studiato due categorie di clustering, quello basato su
centroide e quello gerarchico: il primo cerca i punti centrali di
ogni cluster ed assegna punti al cluster del centroide più
vicino; il secondo aggrega ripetutamente dei sottocluster. I
metodi di clustering studiati trattano una gran quantità
di dati che non entra memoria e sono: BFR, FastMap, Birch*, Cure,
Antipole Clustering.
Home Book and Authors From Sergei Brin
BFR e k-means