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~\cite{FMLMa01,FMLM03} that reduces the classification step to a clustering problem in presence of outliers. However, instead of the K-means procedure adopted in~\cite{FMLMa01,FMLM03}, we propose the use of single-linkage clustering that estimates automatically the number of submodels composing the piecewise affine map. %on the basis of a threshold whose proper value depends on the %distance between model coefficients and outliers. Moreover we prove that, under mild assumptions on the data set, single-linkage clustering can guarantee optimal classification in presence of bounded noise.