# Towards Understanding Clustering Problems and Algorithms: An Instance Space Analysis
## 1 Introduction
Since there are multiple clusters' definitions, the selection of the clustering algorithms to be evaluated must be careful and include representatives with different biases, which we also tried to fulfill, despite focusing on popular partitional and hierarchical clustering algorithms. Finally, the lack of an expected response hampers the evaluation of the clustering algorithms' results. There are various clustering validation indexes which can be used in this evaluation, but each one of them has a bias towards one particular cluster definition, which may favor some algorithms to the detriment of others. Therefore, we have combined multiple validation indexes in order to better assess the algorithms' performances. The remainder of this paper is organized as follows: In Section 2, we present a theoretical summary and previous studies on meta-learning and ISA. In Section 3, we describe the methodology of  
[PERSON] et al. [8] have extended [PERSON]'s framework to propose a methodology known as Instance Space Analysis. Initially, the methodology was used to evaluate the suitability of algorithms for graph colouring problems, and later generalized to ML classification algorithms [5] and other problems [6; 7; 14]. According to Figure 2, the framework is composed of several steps. In the center, \(I\) contains a subset of the problem space \(P\) for which computational results are available. In ML, this subset is usually formed by datasets collected from benchmark repositories. The feature space \(F\) contains multiple measures that can be used to characterize the properties of the instances in \(I\). The algorithm space \(A\) is composed of a portfolio of algorithms that can be used to solve the instances. The performance space \(Y\) measures the performance of the algorithms in \(A\), when evaluated on the solution of the instances in \(I\). Through a computational process, for all instances in \(I\) and all algorithms in \(A\), a meta-dataset containing an ordered quadruple \((I,F,A,Y)\) is composed. One can then learn, through regression or another appropriate supervised learning method, the relationship between the features in \(F\) and the performance \(Y\) of the algorithms. This was the challenge of the Algorithm Selection Problem described by [PERSON] [13] and shown in the inner box in Figure 2.  
ISA methodology extends [PERSON]'s framework to achieve more insights than mere algorithm selection. A 2D projection which captures relationships between the features values \(F\) and the performance measures \(Y\) can be generated. In this space, one may visualize the level of difficulty of different instances, the performance of different algorithms across the space and the relationship to instance features. The ultimate goal is more than automated algorithm selection, but greater insights into the strengths and weaknesses of algorithms, and explanations of how instance characteristics affect performance and reliability. Once the meta-data has been generated, the construction of the instance space involves a feature selection step in order to keep only the most informative meta-features and then projection of the instances into a 2D plane. Both of these steps require the solution of optimization problems: (i) to find the optimal subset of features that best explain variations in algorithm performance and \"easy-to-hard\" phase transitions; and (ii) to find the optimal linear transformation matrix from the selected feature space to 2D such that the distribution of algorithm performance and features in the 2D space exhibit strong linear trends for maximal visual interpretability. Figure 1: [PERSON]’s algorithm selection framework. The result is a projection of the instances into a 2D instance space that aims to elicit insights into why some algorithms might be more or less suited to certain types of instances. An ML model is applied to the instances in this space to learn algorithm \"goodness\".