# Towards Understanding Clustering Problems and Algorithms: An Instance Space Analysis
## 3 Methodology of Instance Space Analysis for Clustering
### Meta-Data
\begin{table}
\begin{tabular}{l l l l} \hline \hline
**Meta-Feature** & **Description** & **Asymp.** & **Reference** \\ \hline (1) Distribution-based: & & & \\ multi\_norm & Multivariate normality & \(O(m\cdot n+n^{2})\) & [17] \\ skewness & Multivariate normality skewness & \(O(m\cdot n+n^{2})\) & [43] \\ kurtosis & Multivariate normality kurtosis & \(O(m\cdot n+n^{2})\) & [43] \\ \hline (2) Neighborhood-based: & & & \\ avg\_nnd & Average nearest neighbor degree & \(O(m\cdot n^{2})\) & [44] \\ contrast & Contrast & \(O(n^{2})\) & [45] \\ high\_dist & Percentage of points of high distance & \(O(n^{2})\) & [10] \\ low\_dist & Percentage of points of low distance & \(O(n^{2})\) & [10] \\ \hline (3) Density: & & & \\ clust\_coef & Clustering coefficient & \(O(m\cdot n^{2})\) & [46] \\ net\_dens & Network density & \(O(m\cdot n^{2})\) & [46] \\ perc\_out & Percentage of outliers & \(O(n^{2})\) & [17] \\ \hline (4) Dimensionality: & & & \\ number\_ex & \(\log_{10}\) number of examples & \(O(n)\) & [17] \\ number\_ftr & \(\log_{10}\) number of attributes & \(O(m)\) & [18] \\ ratio\_ex\_ftr & Ratio number of examples to attributes & \(O(m+n)\) & [47] \\ avg\_abs\_cor & Average absolute correlation & \(O(n)\) & [20] \\ intr\_dim & Intrinsic dimensionality & \(O(n^{2})\) & [45] \\ avg\_pca & Average number of points per PCA dimension & \(O(m^{2}\cdot n+m^{3})\) & [46] \\ ratio\_pca & Ratio PCA to the original dimension & \(O(m^{2}\cdot n+m^{3})\) & [46] \\ \hline (5) Network centrality: & & & \\ power\_cent & Bonacich power centrality & \(O(n^{3})\) & [48] \\ eigen\_cent & Eigenvalue centrality of minimum spanning tree & \(O(n^{2})\) & [48] \\ hub\_score & [PERSON]’s hub centrality & \(O(n^{3})\) & [49] \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Meta-features classified by the main properties they measure. In the Asymp. column, \(n\) stands for the number of data items a dataset has and \(m\) corresponds to its number of input features. percentage of points of high distance corresponds to the proportion of points with a distance greater than the mean distance plus its standard deviation. Conversely, the percentage of points of low distance corresponds to the proportion of points with a distance lower than the mean distance minus its standard deviation. Some meta-features listed in Table 1 have already been used in previous work to characterize test instances in clustering problems [10; 17; 18; 20; 44; 45; 47]. We have also included some meta-features that have been used in classification problems that can be directly or easily adapted to characterize clustering problems [46]. As a contribution of this work, we have proposed using multivariate normality skewness and kurtosis measures [43] and a meta-feature group based on well-known network centrality measures [48; 49]. The hypothesis is that the measurement of the importance of the vertices of a graph generated from the dataset reflects the structure of the clusters in such a way that it is possible to discriminate instances according to the underlying network complexity. For evaluating the clustering algorithms' performance and compose the set \(Y\), we have employed a set of internal validation measures, which use information inherent to the data structure to assess the quality of the clusters [50; 51; 52; 53; 54; 55; 56; 57; 58]. There are numerous measures in the literature, each with a specific bias. The measures used in this work are classified in six groups, as shown in Table 2[58]. We included representatives from different categories as defined in the related literature, so that the ability of the algorithms to recover different structures from a dataset can be assessed. Their code was implemented in R, using the following packages: clusterCrit, clValid and fpc and are also available in supplementary material. As a result of this step, we have a meta-dataset composed of 380 instances (clustering datasets), described by 20 meta-features and the performances of 10 clustering algorithms according to 12 clustering validation indexes.