# A Machine Learning Approach to Algorithm Selection for Exact Computation of Treewidth
## 5 Analysis
Since removing features seemed to provide us with little insight, we attempted another approach--removing all features except for a small number of designated features. Then we repeated the same procedure--we retrained the model on the reduced dataset and measured its accuracy against the original model. Again, we did 10-fold cross-validation a multitude of times. We began by only selecting one feature to retain, repeating the training 50 times. The feature **minimum degree** emerged as a clear winner, having **72%** accuracy. We highlight the fact that by removing three features at a time, we only managed to lower the accuracy to about **74.5%**, while a model with only one feature successfully reached **72%**. Next, we selected pairs of features to keep and did 10-fold cross-validation 50 times. 7 sets of features performed at least as well as the original model. All of them contained **variation** and/or **maximum degree**. Finally, we selected sets of 3 features to keep and did 10-fold cross-validation 5 times. More than 50 sets of features performed at least as well as the original model. Notably, despite the previously demonstrated importance of **variation**, **minimum degree** and **maximum degree**, adding all three of them produced results that were around the middle of the pack at **74.5%**. However, a large majority of the best results contained at least one or more often two of those features. All experiments also showed models that surpassed the performance of the benchmark model, reaching **78.5%** by only adding **mean**, **variation** and **maximum degree**--compared to **76.5%** for the original model. Naturally, we view such results with caution. They could well be the result of chance, especially seeing as how we use no validation set--however, another possibility is that the classifiers can be more efficiently trained on smaller subsets of features. The frequency with which the features **variation**, **minimum degree** and **maximum degree** appear in our analysis indicates that they carry some critically important signal that the classifier needs in order to be accurate. However, it appears that one or two of the features are sufficient to reproduce the signal and adding the third one does not help much. We also attempted to determine feature importance by examining the Decision Tree model that was built for Dataset B (Figure 3). Our analysis ignores nodes that offer under 50% accuracy and nodes that contain very few (less than four) samples, as those are deemed not to bring a significant amount of insight to the analysis. The very first split in the model already provides a dramatic improvement in accuracy. Its left branch is heavily dominated by **tdlib**--after that split alone, selecting **tdlib** would be the correct choice about 70% of the time. On the right side of the split, a similar situation is observed with **tamaki** being the correct choice about 72% of the time. This shows that the first split, which sends to the left graphs where the first quartile of the degree distribution is smaller than or equal to 4.5, is very important for solvers' performance. The first quartile being low is an indicator for a small or sparse graph and according to the model, **tdlib**'s performance on those is better, while **tamaki** seems to cope better with larger or denser graphs. There are two paths that lead to **Jdrasil** being the correct label, both of which require that the variation coefficient feature is higher than a certain threshold, which is quite high (0.603 and 0.866). This leads us to believe that **Jdrasil** performs well on graphs where there is significant variation in the degree of all vertices. One of these paths also requires the graph to have more than 2184 edges or otherwise **tdlib** is selected instead. This again indicates that **tdlib** is better at solving smaller or sparser graphs, while **Jdrasil** can deal with variability in larger graphs too.