# Towards Understanding Clustering Problems and Algorithms: An Instance Space Analysis
## 4 Building an Instance Space from Artificial Datasets
### Footprint Analysis and Algorithm Portfolio  
One of the most relevant and characteristic results of ISA is the presentation of the regions of the instance space in which the algorithms perform well, that is, the footprints of the algorithm, supporting objective evaluation of algorithmic power and highlighting its strengths and weaknesses. According to [PERSON] et al. (2018), the algorithm that generates the footprints uses a combination of two approaches that were used in previous works. In its first step, the algorithm measures the Euclidian distances between two instances, and marks one of them for elimination if the distance is less than a threshold, \(\alpha\). This is done to avoid numerical instability with the triangulation algorithm, which is applied as the second step. As a third step, the algorithm finds the concave hull, by removing any triangle with  
\begin{table}
\begin{tabular}{l r r r r r r r r} \hline \hline
**Algorithm** & **Avg. Perf. ** & **SD Perf. ** & **Prob. Good** & **CV Accuracy** & **CV Precision** & **CV Recall** & \(C\) & \(\gamma\) \\ \hline KME & 0.55 & 0.18 & 0.62 & 74.70 & 75.90 & 86.30 & 206.99 & 1.34 \\ KMD & 0.52 & 0.20 & 0.59 & 78.70 & 78.90 & 87.60 & 3.82 & 0.28 \\ KMO & 0.40  
edges larger than another threshold, \(\beta\). As a fourth and final step, the algorithm calculates the density and purity of each triangle in the concave hull. The density, as the number of instances per area unit, and purity, as the number of instances of good performance (considering an avg_rank performance metric of at least 0.50) per number of instances of the region. If a triangle does not fulfill the density and purity limits, it is removed from the hull. When areas of two or more algorithms overlap, the purity measure is used to determine which algorithm should predominate. While we are not able to experiment with these default parameters, we can confirm that the resulting footprints make visual sense, and the parameters appear to behave in the intended manner, for our application, as well as all for the MATILDA library case studies. Changes to these parameters would merely affect the formation of footprints and the calculation of their areas, which is not a core requirement for gaining the visual insights we seek. Figure 6 shows the footprints of the algorithms in the instance space. An interesting aspect to be observed is that all hierarchical algorithms perform well in the ellipsoidal datasets (center-left region), which are more complex in terms of some basic characteristics such as number of attributes and clusters. This was not observed for any of the partitional algorithms. We can also observe that the CC algorithm has the largest footprint in terms of coverage area across the instance space. On the other hand, the KMO algorithm has the smallest footprint area \(\Delta\). Some other interesting observations from Figure 6 are:  
* there is a large variation on the partitional algorithms' performances, although all of them algorithms tended to present better results for datasets towards the bottom-right of the instance space, with exception from a small area in the case of KME. KMO and MBK present a large area of bad performance. The FCM variant is able to handle better a larger portion of the datasets;
* the hierarchical clustering variants tended to present bad results for some datasets of the G2 group;
* the WM algorithm presents a performance mostly complementary to that of the partitional algorithms. Table 5 presents the results for the footprint analysis. The areas \(\Delta\), as well as their density \(\rho\) and purity \(\phi\) measures, are detailed. Usually, the obtainment of large normalized areas (30% onwards) with density about one and purity above 70-80% is evidence that the algorithm is strong in the instance space. The CC algorithm showed the best performance (\(\Delta=0.87\)), followed by the SL (\(\Delta=0.82\)) and FCM (\(\Delta=0.82\)). CC performed well on ellipsoidal, multiple shapes and Gaussian datasets, with the exception of a region formed by G2 datasets.