# Towards Understanding Clustering Problems and Algorithms: An Instance Space Analysis
## 6 Conclusions  
In this paper, we have performed the first instance space analysis of the performance of well-known clustering algorithms on a representative sample of clustering datasets. We considered a new set of features that aim to reveal the presence of different types of structures in a dataset. We defined as performance measure a combined ranking of the performance of the algorithms as measured by internal validation indexes of different biases. One of the limitations of this study resides in the need to pre-define the number of clusters to be used as a parameter in the clustering algorithms. We opted to monitor a Silhouette metric in the evaluation of the clustering algorithms' results. It is also important to comment that the adequate definition of the good performance threshold plays a major role in the generation of an instance space that discriminates the algorithms' performances. We have experimentally varied the values of the most sensitive parameters in order to obtain consistent and robust insights about the distribution of the instances in the space and to reveal subtleties on algorithmic performance. An interesting finding was the good performance of the hierarchical algorithms in relation to the partitional algorithms when applied to ellipsoidal datasets. It should also be noted that, for the instances under study, the partitional and hierarchical algorithms in general tend to present inverse behaviors in relation to performance across the instance space. Partitional algorithms had their strengths evidenced by measures of dimensionality and neighborhood-based measures. Its weaknesses were revealed by measures of density. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Algorithm** & \(\Delta\) & \(\rho\) & \(\phi\) \\ \hline KME & 0.65 & 1.13 & 0.92 \\ KMD & 0.50 & 0.88 & 1.00 \\ KMO & 0.02 & 1.83 & 1.00 \\ MBK & 0.09 & 1.18 & 1.00 \\ FCM & 0.61 & 1.15 & 1.00 \\ SL & 0.96 & 1.03 & 1.00 \\ CL & 0.58 & 1.03 & 0.95 \\ AL & 1.01 & 0.96 & 0.79 \\ WM & 0.83 & 1.07 & 0.95 \\ CC & 0.94 & 1.01 & 1.00 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Footprint analysis of the algorithms after the inclusion of real datasets, where \(\Delta\) is the area, \(\rho\) is the density and \(\phi\) is the purity. Figure 11: Footprints of the algorithm portfolio predicted by SVM after the inclusion of real datasets. The opposite occurred for hierarchical algorithms. Different behaviors were observed when the analysis was segregated into groups of datasets. In general, hierarchical algorithms tend to perform better in more complex datasets. Finally, we can conclude that the inclusion of real datasets employed in related work maintained the essence of the results achieved when considering only artificial datasets, showing consistency in the methodology used. However, the main finding of this work is the observation that ISA goes further and indicates, in addition to the best algorithm for a given instance, which algorithm would be recommended for an instance whose characteristics lie in a certain region of the instance space. We can conclude, therefore, that ISA offers a unique perspective in relation to the methodologies of clustering analysis widely used in the literature. In future works, we will expand the feature space, aiming for a more accurate and comprehensive characterization of clustering datasets. The results of the MATILDA's feature selection showed that measures based on network centrality were not relevant in this process and this should be better investigated. Some characterization measures based on distance and entropy will be added to the study too, as well as other clustering algorithms. Some algorithms with different characteristics are already being tested, such as Affinity Propagation, Spectral Clustering, Bagged Clustering and model-based algorithms. Finally, a method will be developed to generate clustering datasets at controlled locations of the instance space. This is a natural follow-up in research using the ISA framework.