Welcome to the cop-kmeans demo applet! This demo allows you to specify any number of two-dimensional points and an optional set of constraints and then cluster the points to see how the constraints affect the resulting clusters. It uses a modified version of the k-means clustering algorithm that accommodates any specified pairwise constraints. See below for instructions.

Warning: If you over-constrain the problem (so that it isn't possible to find k clusters), nothing happens when you click "Cluster it!".

Instructions:

1. Left-click to place points.
2. Move the slider to select a value for k (number of clusters).
3. [Cluster it!] displays the output for the given number of clusters. Each point is connected by a green line to the center of its cluster. In addition, if constraints are specified, the closure is shown.

1. Middle-click and drag to connect two points with a must-link constraint (blue line).
2. Right-click and drag to connect two points with a cannot-link constraint (red line).
3. [Clear all] wipes the data area clean.
4. [Clear constraints] removes all constraints but retains the data points.
5. [Show closure] displays the transitive closure of the specified constraints.

For more information:

• ... on constrained k-means clustering, see Constrained K-means Clustering with Background Knowledge (ps, 8 pages, 225k), by Kiri Wagstaff, Claire Cardie, Seth Rogers, and Stefan Schroedl. ICML 2001.
• ... on a modified version of COBWEB that can use constraints, see Clustering with Instance-level Constraints (ps, 8 pages, 224k), by Kiri Wagstaff and Claire Cardie. ICML 2000.