How Much Distribution Shift Can a Clustering Withstand? Exact Split and Merge Certificates for Structured Transports
Organizations: Department of Mechanical Science and Engineering and Coordinated Science Laboratory, University of Illinois Urbana-Champaign, Urbana, IL, USA · Department of Mechanical and Aerospace Engineering, University of California, Los Angeles, Los Angeles, CA, USA
Abstract
In clustering, the distribution of the population being clustered is often uncertain or changes over time, so the true distribution may shift away from the nominal distribution used to form the clustering. Once the clustering is committed and each member is assigned to a cluster, such shifts may change the distribution of each cluster. They can make a cluster too spread out for one representative at a given resolution, motivating a split, or bring distinct clusters close enough to share a representative at that resolution, motivating a merge. We make these split and merge events precise using a local stability criterion built on the phase-transition analysis in deterministic annealing. This notion of stability enables us to quantify how robust a clustering is against such events. Furthermore, motivated by applications in which uncertainty and population change are structured, we study shifts whose displacements are restricted to a prescribed subspace. The smallest structured shifts that reach the respective thresholds define the split and merge radii, for which we obtain exact semidefinite programming (SDP) reformulations. The split SDP has only two scalar decision variables. These convex reformulations enable us to combine the radii into a robustness certificate for the full clustering that gives the size of the smallest structured shift that reaches any monitored split or merge threshold.
Figures & tables
| Unrestricted | Horizontal | Vertical | ||||
|---|---|---|---|---|---|---|
| Dataset | Event | Event | Event | |||
| S1 | Merge | 12.08 | Merge | 23.38 | Merge | 13.12 |
| S2 | Merge | 12.16 | Merge | 16.69 | Merge | 15.49 |
| S3 | Split | 7.23 | Split | 8.96 | Split | 8.54 |
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
| Unrestricted | Horizontal | Vertical | |||||
|---|---|---|---|---|---|---|---|
| Dataset | Weighting | Event | Radius | Event | Radius | Event | Radius |
| S1 | Unweighted | Split | 115.56 | Split | 115.92 | Split | 122.59 |
| Mass-weighted | Split | 29.44 | Split | 29.60 | Split | 31.97 | |
| S2 | Unweighted | Split | 75.42 | Split | 79.78 | Split | 86.40 |
| Mass-weighted | Split | 19.52 | Split | 20.65 | Split | 22.36 | |
| S3 | Unweighted | Split | 28.80 | Split | 35.68 | Split | 34.02 |
| Unrestricted | Horizontal | Vertical | |||||
| Dataset | Weighting | Event | Radius | Event | Radius | Event | Radius |
| S1 | Unweighted | Merge | 32.78 | Merge | 64.61 | Merge | 35.60 |
| Mass-weighted | Merge | 12.08 | Merge | 23.38 | Merge | 13.12 | |
| Feasible pairs | |||||||
| S2 | Unweighted | Merge | 33.36 | Merge | 45.76 | Merge | 43.34 |
| Mass-weighted | Merge | 12.16 | Merge | 16.69 | Merge | 15.49 | |
| Splits | Merges | |||||||
|---|---|---|---|---|---|---|---|---|
| Dataset | Weighting | Rank | Event | Radius | Ratio | Event | Radius | Ratio |
| S1 | Unweighted | 1 | Split | 115.56 | 1.0000 | Merge | 32.78 | 1.0000 |
| 2 | Split | 115.59 | 1.0002 | Merge | 39.13 | 1.1939 | ||
| 3 | Split | 120.79 | 1.0453 | Merge | 48.91 | 1.4921 | ||
| Mass-weighted | 1 | Split | 29.44 | 1.0000 | Merge | 12.08 | 1.0000 | |
| 2 | Split | 30.14 | 1.0236 | Merge | 14.03 | 1.1618 | ||
| Weighted split | Weighted merge | Attaining event | Feasible merges | ||
|---|---|---|---|---|---|
| 10 | 0.053610 | 0.053610 | Split | 0/120 | |
| 30 | 0.052094 | 0.052094 | Split | 0/120 | |
| 50 | 0.051143 | 0.051143 | Split | 0/120 | |
| 55 | 0.050981 | 0.168348 | 0.050981 | Split | 20/120 |
| 60 | 0.050951 | 0.145684 | 0.050951 | Split | 96/120 |
| 64 | 0.050749 | 0.132986 | 0.050749 | Split | 120/120 |
Clustering
Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.
See all 378 papers