# Towards Understanding Clustering Problems and Algorithms: An Instance Space Analysis
## 4 Building an Instance Space from Artificial Datasets
### Feature Selection and Projection in the Instance Space  
Ten meta-features were selected from the feature space \(F\) by MATILDA to be employed in the ISA analysis. Equation (5) presents the projection matrix that allows the transformation of instances from the 10D feature space to the 2D instance space. We can notice the presence of meta-features from all categories except from Network Centrality presented in Table 1, stressing the need for considering multiple views in order to properly characterize the structure of diverse datasets. Although no network centrality measures are present in the final set of meta-features chosen, the clust_coef meta-feature is also extracted from a proximity graph built from data. \[\left[ \begin{array}{c}Z_{1}\\ Z_{2}\end{array} \right]=\left[ \begin{array}{ccc}-0.124&0.495\\ -0.572&0.026\\ -0.147&-0.049\\ -0.231&0.152\\ 0.435&-0.025\\ 0.505&-0.186\\ 0.154&-0.266\\ 0.205&0.254\\ 0.131&-0.312\\ 0.007&-0.226\end{array} \right]^{\top}\left[ \begin{array}{c}\texttt{ratio\_ex\_tr} \\ \texttt{skewness}\\ \texttt{kurtosis}\\ \texttt{per\_out}\\ \texttt{ratio\_pca}\\ \texttt{avg\_abs\_cor}\\ \texttt{low\_dist}\\ \texttt{clust\_coef}\\ \texttt{intr\_dim}\\ \texttt{avg\_nnd}\end{array} \right] \tag{5}\]  
Figure 4 illustrates the characteristics of the 380 datasets projected in the generated instance space colored according to group (namely ellipsoidal, Gaussian and multiple shapes), number of examples, number of attributes and number of clusters defined as ground truth in the original datasets. There is a clear distinction between dataset groups. The ellipsoidal and multiply shaped datasets are spread in different regions of the instance space. Gaussian datasets occupy a region below them, with some degree of overlap. Among the Gaussian datasets, there is a set that is uniformly arranged in the lower region of the instance space. Those are the G2 datasets [42] that have the same number of observations  
Figure 3: Average performance ranking of the algorithms for ellipsoidal datasets. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Algorithm** & **Mean** & **Std** & **Rank** \\ \hline CC & 0.638 & 0.181 & 1 \\ AL & 0.629 & 0.174 & 2 \\ SL & 0.613 & 0.157 & 3 \\ FCM & 0.559 & 0.220 & 4 \\ KME & 0.551 & 0.177 & 5 \\ CL & 0.539 & 0.186 & 6 \\ WM & 0.522 & 0.209 & 7 \\ KMD & 0.521 & 0.203 & 8 \\ MBK & 0.476 & 0.182 & 9 \\ KMO & 0.403 & 0.193 & 10 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Mean, standard deviation and rank of each clustering algorithm. (\(n=2048\)), the same number of clusters (k = 2) and the number of attributes ranging from 2 to 1024. They also have an overlap parameter varying from 0 to 100. These datasets model each cluster as a separate Gaussian, which may or not overlap depending on the spread of their distributions. We can see from the figure that the numbers of examples, attributes and clusters also are decisive in the distribution of datasets across the instance space. These characteristics were not directly used to project the instances, although the number of examples and attributes are used to compute some of the dimensionality measures. Datasets with more input attributes are concentrated in the bottom of the instance space, and their dimensionalities reduce towards the upper right quadrant of the projected space. For the number of clusters, although there are some mixed results, in general datasets with a lower number of clusters are concentrated towards the right of the instance space. Concerning the number of examples, datasets with fewer examples mostly have a \(z_{2}\) coordinate larger than zero. The distribution of the selected meta-features in the instance space is shown by Figure 5. All values were scaled to [0, 1]. In this case, the following observations can be drawn:  
Figure 4: Characteristics of the datasets projected in the instance space, color coded according to (**a**) distribution of the datasets by groups, (**b**) number of examples, (**c**) number of attributes and (**d**) number of clusters represented by ground truth.