Single-linkage clustering for optimal classification in piecewise affine regression

When performing regression with piecewise affine maps, the most challenging task is to classify the data points, i.e. to correctly attribute a data point to the affine submodel that most likely generated it. In this paper, we consider a regression scheme similar to the one proposed in (Ferrari-Trecate et al., 2001,2003) that reduces the classification step to a clustering problem in presence of outliers. However, instead of the K-means procedure adopted in (Ferrari-Trecate et al., 2001,2003), we propose the use of single-linkage clustering that estimates automatically the number of submodels composing the piecewise affine map. Moreover we prove that, under mild assumptions on the data set, single-linkage clustering can guarantee optimal classification in presence of bounded noise.