# Towards Understanding Clustering Problems and Algorithms: An Instance Space Analysis
## 3 Methodology of Instance Space Analysis for Clustering
### Steps for Generating a 2D Instance Space for Clustering
K-means clustering is used to identify groups of similar features, with the number of groups defined by a Silhouette measure. K is a parameter that corresponds to a maximum number of clusters in the feature selection step. According to Appendix A, values were tested in the range 6-10. The value 10 was defined based on the tests. To select one feature per group, the algorithm first projects the subset of selected features into two dimensions using Principal Components Analysis (PCA) and Random Forests are used to predict whether an instance is easy or not for a given algorithm. Instances are labeled as easy or hard according to the performance threshold adopted for defining a good performance. In this work, we employed a threshold of 0.5, so that an instance for which an average ranking performance below 0.5 is achieved is classified as hard; otherwise, it is considered easy. Then, the subset of features that results in the most accurate Random Forest models is selected. This routine can be computationally intensive, since it tests all possible feature combinations if they are less than 1000 or uses the combination of a Genetic Algorithm and a look-up table otherwise. Next, the main step for the generation of the instance space is the projection model. This algorithm was idealized as an optimization problem. It is a procedure of dimensionality reduction that projects the instances in a 2D space so that a linear trend is observed between the selected meta-features and the performance of the algorithms under analysis. The choice of projection to 2D is an experimental decision and any such dimensionality reduction produces a loss of information. Nevertheless, the use of 2D projection allows for visualizing better the distribution of the selected meta-features along the instance space and also of the algorithms' performances variations. The 2D projection facilitates the computational requirements to establish the algorithm footprints too, corresponding to areaswhere the algorithms perform well. According to [PERSON] et al. (2018), given a (meta-)feature matrix \(\mathbf{F}=[\mathbf{f}_{1}\ \mathbf{f}_{2}\ \cdots\ \mathbf{f}_{3}]\in\mathbb{R}^{m \times n}\) and algorithm performance vector \(\mathbf{y}\in\mathbb{R}^{n}\) (which can also be generalized to a matrix containing multiple evaluations), where \(m\) is the number of features and \(n\) is the number of problem instances, we achieve an ideal projection of the instances if we can find \(\mathbf{A}_{\mathbf{r}}\in\mathbb{R}^{2\times m}\), \(\mathbf{B}_{\mathbf{r}}\in\mathbb{R}^{m\times 2}\) and \(\mathbf{c}_{\mathbf{r}}\in\mathbb{R}^{2}\) which minimizes the approximation error  
\[||\mathbf{F}-\mathbf{\hat{f}}||_{F}^{2}+||\mathbf{y}^{\top}-\mathbf{\hat{y}}^ {\top}||_{F}^{2} \tag{1}\]  
such that  
\[\mathbf{Z}=\mathbf{A}_{\mathbf{r}}\mathbf{F} \tag{2}\] \[\mathbf{\hat{f}}=\mathbf{B}_{\mathbf{r}}\mathbf{Z}\] (3) \[\mathbf{\hat{y}}^{\top}=\mathbf{c}_{\mathbf{r}}{}^{\top}\mathbf{Z}. \tag{4}\]  
The problem was solved numerically by MATILDA using BIPOP-CMA-ES (Bi-population Covariance Matrix Adaptation Evolution Strategy) ([PERSON], 2018). The next step was the use of a supervised learning meta-model for algorithm selection. MATILDA trains a series of SVM models that predict whether an algorithm will perform well or not for a given instance, given a threshold of good and bad performance, which was set as 0.5 in this work. SVMs are trained using the selected meta-features as inputs and the performance measurement of each algorithm as output. The implementation of SVM uses a Gaussian kernel. Their hyper-parameters are tuned by Bayesian Optimization. The model uses a stratified k-fold cross-validation technique and gives a probability for each instance of belonging to a given class by fitting a posterior probability model (\(k=5\) by default). A central concept in ISA are the footprints, which represent the areas in the instance space where an algorithm is expected to perform well.