# 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  
The instance space is produced using the Matlab toolkit MATILDA (acronym for Melbourne Algorithm Test Instance Library with Data Analytics). MATILDA has been developed to be used in the analysis of optimization and ML problems (see [[https://matilda.unimelb.edu.au](https://matilda.unimelb.edu.au)]([https://matilda.unimelb.edu.au](https://matilda.unimelb.edu.au)) for a library of case studies, last accessed on 18 March 2021). A \begin{table}
\begin{tabular}{l l l} \hline \hline
**Acronym** & **Performance Measure** & **Reference** \\ \hline \multicolumn{3}{l}{(1) Compactness or Homogeneity:} \\ BH & Ball-Hall & [50] \\ \hline \multicolumn{3}{l}{(2) Connectedness:} \\ C & Connectivity & [58] \\ \hline \multicolumn{3}{l}{(3) Separation:} \\ RL & Ratkowsky–Lance & [54] \\ \hline \multicolumn{3}{l}{(4) Combinations:} \\ CH & Calinski–Harabasz & [51] \\ DB & Davies–Bouldin & [55] \\ D & Dunn & [52] \\ SD & SD & [56] \\ \hline \multicolumn{3}{l}{(5) Stability:} \\ APN & Average proportion of non-overlap & [57] \\ AD & Average distance & [57] \\ ADM & Average distance between means & [57] \\ FOM & Figure of merit & [57] \\ \hline \multicolumn{3}{l}{(6) Compliance between a partitioning and distance information:} \\ HUB & Pearson correlation version of [PERSON]’s statistic & [53] \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Performance measures classified by properties. more detailed description of the methodology can be found in [PERSON] et al. [5]. The tool consists of a data pipeline that integrates a pre-processing stage, four main steps and a post-processing stage. A preliminary and relevant step to build an instance space is the consolidation of metadata. These are composed by the mentioned meta-features and performance measures of the algorithms under analysis. These actions are common in all kinds of problems, but in clustering some specific aspects had to be observed. The first is the need to determine an optimal number of clusters for each dataset. Considering the unsupervised nature of clustering problems, the number of clusters each dataset has is not known a priori. Therefore, we let the data structure speak for itself and the number of clusters is found according to the clustering algorithms' results. We use the Silhouette Method [59] from the R language's NbClust package to determine the number of clusters to be adopted for each dataset and clustering algorithm uniformly. It does not have the same bias of the internal validation criteria taken as performance measures. The inclusion of a new instance with or without information about the number of clusters must follow the same procedure. Another aspect is the definition of a performance measurement. In this work, we chose to use internal validation measures because we did not want to consider the ground truths of the datasets. We know that there are countless measures and that each one has a specific bias and can favor a class of algorithms over others. To reduce this problem, we decided to select and combine measures adopting different clustering criteria. We grouped them into six groups according to Table 2. Each measure, or group of measures, has its own properties. To consider different biases, we aggregated them into a single value based on an average ranking of performance across the algorithm portfolio, in order to smooth or compensate their individual influence on algorithms which employ similar clustering criteria. The first stage of the framework is the pre-processing of the meta-dataset. In this stage, the data were normalized using the Box-Cox and Z transformations. Next, a feature selection process is performed in order to find a subset of meta-features that are more related to the clustering algorithms' performances, allowing for obtaining smoother 2D projections relating the properties of the instances and the performance of the clustering algorithms. MATILDA's automated feature selection process defines the Pearson correlation coefficient as a similarity metric between features.