---

Clustering in a metric space.

---

• We are given:

  • data points: x1,x2,x3,...

  • distances: D(x1,x2),...

• A cluster has:

  • diameter: max D(x,y)

  • centroid: center of mass (assuming Euclidean space)

• Goal of clustering:

  • reasonable number of clusters

  • small diameter/small mean square distance to centroid

  • complete coverage

  • disjoint (???)

---

Slide 10 of 15

15 Oct 1998

lm@bitmover.com