Mapper is an unsupervised machine learning algorithm generalising the notion of clustering to obtain a geometric description of a dataset. The procedure splits the data into possibly overlapping bins which are then clustered. The output of the algorithm is a graph where nodes represent clusters and edges represent the sharing of data points between two clusters. However, several parameters must be selected before applying Mapper and the resulting graph may vary dramatically with the choice of parameters. We define an intrinsic notion of Mapper instability that measures the variability of the output as a function of the choice of parameters required to construct a Mapper output. Our results and discussion are general and apply to all Mapper-type algorithms. We derive theoretical results that provide estimates for the instability and suggest practical ways to control it. We provide also experiments to illustrate our results and in particular we demonstrate that a reliable candidate Mapper output can be identified as a local minimum of instability regarded as a function of Mapper input parameters.
This paper is organised as follows. In , we discuss some related work and its connections to the current paper. In , we give background on clustering stability required for the remainder of the paper. This allows us in to set out how the ideas of Ben-David and von Luxburg @cite_43 can be generalised to the Mapper setting. In particular, we introduce Mapper functions in Definition , which provide a new way of expressing Mapper outputs. Crucially, this is used to define a similarity metric between Mapper functions, @math in Definition . The Distance @math captures the structure of the whole Mapper output and leads to the definition of our notion of instability of Mapper (Definition ) with respect to a large class of clustering procedures. In we present an algorithm allowing us to experimentally obtain values of instability. This leads in section in to interesting experimental results which suggest that regions of relatively high instability correspond to structural changes in the Mapper output. Hence local minima of the instability function with respect to parameter choices are good candidates for parameter selection allowing us to study Mapper through variations of all the parameters.
@cite_43
1516452477
In this paper, we investigate stability-based methods for cluster model selection, in particular to select the number K of clusters. The scenario under consideration is that clustering is performed by minimizing a certain clustering quality function, and that a unique global minimizer exists. On the one hand we show that stability can be upper bounded by certain properties of the optimal clustering, namely by the mass in a small tube around the cluster boundaries. On the other hand, we provide counterexamples which show that a reverse statement is not true in general. Finally, we give some examples and arguments why, from a theoretic point of view, using clustering stability in a high sample setting can be problematic. It can be seen that distribution-free guarantees bounding the difference between the finite sample stability and the “true stability” cannot exist, unless one makes strong assumptions on the underlying distribution.