Clustering

Description:

• Goal. Given a set U of n objects labeled $p_1,...,p_n$, partition into clusters so that objects in different clusters are far apart

k-clustering.

• Divide objects into k non-empty groups.
• Distance function. Numeric value specifying “closeness” of two objects.
  • $d(pi,pj)=0⟺pi=p$j [ identity of indiscernibles ]
  • $d(pi,pj)\ge 0$ [ non-negativity ]
  • $d(pi,pj)=d(pi,pj)$ [ symmetry ]
• Spacing. Min distance between any pair of points in different clusters.
• Goal. Given an integer k, find a k-clustering of maximum spacing.