# Towards Understanding Clustering Problems and Algorithms: An Instance Space Analysis
## 3 Methodology of Instance Space Analysis for Clustering
### Meta-Data  
An important step in the construction of meta-data are the definition of meta-features \(F\) that correspond to the characterization measures of the datasets. Table 1 lists the 20 meta-features used in this work. For each meta-feature, this table presents the main aspect it intends to measure, its acronym, description, asymptotic computational cost and reference from which the measure was extracted or based. The asymptotic cost is analyzed as a function of the number of points \(n\) each dataset has and its number of input features \(m\). Most of the measures require building a distance matrix between all data points first, which dominates the asymptotic cost. Nonetheless, one must notice that this matrix needs to be computed only once and multiple measures can be extracted from it afterwards, so that the overall cost involved in extracting all meta-features is lower than that obtained by summing up each of the individual costs. We have chosen a diverse set of meta-features for revealing different cluster structures while also allowing to draw meaningful conclusions regarding the clustering algorithm's performances. Measures already tested in related works are included along with other measures that highlight other complementary aspects. The meta-features' functions have been implemented in R, using the following packages as support: MVN and igraph. The code is available in an open access repository (see [[https://github.com/ml-research-clustering/meta-analysis](https://github.com/ml-research-clustering/meta-analysis)]([https://github.com/ml-research-clustering/meta-analysis](https://github.com/ml-research-clustering/meta-analysis)), last accessed on 18 March 2021). They were categorized in this work in five groups, according to properties they are able to extract from the datasets: distribution-based, neighborhood-based, density-based, dimensionality and network centrality. Distribution-based, neighborhood-based and density-based measures are commonly employed as clustering criteria in the literature. Compact clusters are obtained whenever one maximizes the intra-cluster similarity, whilst minimizing inter-cluster similarity. Neighborhood-based measures favor placing neighborhood data items into the same group. Density captures how the data are distributed in the input space, so that dense regions separated by sparse regions can be regarded as suitable clusters. Dimensionality can be an issue to any clustering algorithm, as datasets with few data items and a high dimensionality tend to be sparse, which prevents finding an underlying clustering structure. The network centrality measures are based on building a proximity graph from data and measuring characteristics from this structure. The measures clust_coef and net_dens from the Density category and avg_nnd from the Neighborhood-based category are also extracted from this proximity graph. The graphs were built from the adjacency matrix, based on an approximation method that uses an \(\epsilon\)-NN (nearest neighbor) function. As in related work [46], \(\epsilon\) is defined as 15% of the number of examples the dataset has. Finally, in our implementation, the