# Towards Understanding Clustering Problems and Algorithms: An Instance Space Analysis
## 5 Plotting Real Datasets in Instance Space
### Performance Prediction, Footprint Analysis and Algorithm Portfolio  
Table 6 shows the results for each algorithm, plus the results of an idealized oracle that always picks the right algorithm, and our selector that combines the decisions made by the 10 SVMs (one per clustering algorithm). The columns of this table have the same interpretation as those in Table 4. CC presented the best performance on average (probability of good 0.86), while MBK was the worst (probability of good 0.39). The results also confirm what was obtained previously regarding the best average performance of the hierarchical algorithms. The AL algorithm obtained an average performance lower than that achieved by the best algorithm (probability of good 0.76). However, it was the best algorithm regarding the results of the cross-validation measures (accuracy, precision and recall). The Selector is successful since it has a probability of 0.95 of selecting an algorithm with good performance--better than always selecting the best on-average algorithm CC. The results show that the Selector has better performance, both in terms of precision and average ranking than using always CC, which is the best performing algorithm. However, the difference in the performance to the Oracle, the low CV performance for the KMO algorithm and a relatively low CV. Recall again indicate that the Selector could be further improved. Through the analysis of Figures 9 and 10, we can verify that partitional algorithms good results are directly related to ratio_pca, low_dist and avg_abs_cor. On the other hand, their weaknesses are related to perc_out. Regarding hierarchical algorithms, perc_out has a direct relationship with good performance, while avg_abs_cor and low_dist show the most difficult instances. We can conclude 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. The insertion of the real datasets, therefore, maintained the main findings verified in the preliminary analysis. Figure 10 shows that all hierarchical algorithms perform well in the ellipsoidal datasets (lower region), as found in the analysis restricted to artificial datasets. This was not observed for partitional algorithms, with the exception of KMO. We see in Table 7, which presents the area \(\Delta\), density \(\rho\), and purity \(\phi\) of the algorithms' footprints, that the AL 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. An interesting finding is that the hierarchical algorithms performed well when applied to real datasets, in contrast to the partitional algorithms. Nonetheless, we must keep in mind that the real datasets used are originally from classification and not clustering problems and this may have affected some of the results. \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** & \(\mathbf{C}\) & \(\mathbf{\gamma}\) \\ \hline KME & 0.59 & 0.18 & 0.69 & 80.80 & 85.00 & 87.70 & 33.38 & 0.52 \\ KMD & 0.51 & 0.19 & 0.55 & 69.10 & 75.90 & 63.60 & 4.89 & 2.13 \\ KMO & 0.44 & 0.18 & 0.40 & 58.10 & 36.50 & 8.00 & 0.01 & 3.00 \\ MBK & 0.45 & 0.18 & 0.39 & 71.00 & 91.90 & 28.80 & 2.78 & 0.93 \\ FCM & 0.58 & 0.21 & 0.69 & 77.50 & 82.40 & 85.70 & 19.67 & 2.36 \\ SL & 0.63 & 0.15 & 0.85 & 84.60 & 85.60 & 98.60 & 59.20 & 1.88 \\ CL & 0.55 & 0.18 & 0.67 & 77.00 & 84.80 & 80.20 & 7.01 & 0.69 \\ AL & 0.61 & 0.17 & 0.76 & 99.80 & 99.80 & 100.00 & 0.38 & 0.00 \\ WM & 0.58 & 0.18 & 0.64 & 71.60 & 69.80 & 98.40 & 998.90 & 0.48 \\ CC & 0.64 & 0.16 & 0.86 & 89.80 & 89.80 & 99.40 & 2.16 & 0.92 \\ \hline Oracle & 0.81 & 0.09 & 1.00 & - & - & - & - & - \\ Selector & 0.66 & 0.13 & 0.95 & - & 95.30 & 48.80 & - & - \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Results of SVM prediction models after inclusion of real datasets, where Avg. Perf.