Decision tree for classification is essentially Boolean function approximator which is usually equivalent to a MLP neural network. Thus the usual Gini index, entropy based uncertainty reduction methods to select and order test attributes is akin to optimize MLP parameters based on the same training set. If the size of your training set is relatively small compared to your future test set, they both face the same common overfitting issue. But nonetheless you can always convert to its equivalent MLP form for “optimality”.
If you stick with decision tree method there’s no rigorous mathematical proof for your hoped "globally optimal" tree if your training set is relatively small or incomplete w.r.t your test set, and usually Gini index metric is more efficient to compute in most cases unless in some highly unbalanced data sets where one of the classification category is relatively unlikely and entropy formula can amplify attributes of such rare category. You may further read this 2004 paper summarizing theoretical optimality comparison between Gini index and Information Gain metrics for decision tree induction with the conclusion:
Based on these characterizations we were able to
analyze the frequency of agreement/disagreement of the Gini Index function and the Information Gain function. We found that they disagree only in 2% of all cases, which explains why most previously published empirical results concluded that it is not possible to decide which one of the two tests performs better... Based on the gained deeper insights on the split process we are currently working on a system, which will select the optimal criterion based on a user defined optimality criterion. Preliminary results can be found in [20].
And in the mentioned reference therein about their proposed family of split functions the authors also confirmed:
The tests have shown that the two popular functions are very sensitive to the variation of the training set sizes and therefore the quality of the inferred trees is highly dependent on the training set size. At the same time however, we were able to show that the simplest members of the introduced family of split functions behave in a very predictable way and, furthermore, the created trees were superior to the trees inferred using the Gini Index or the Information Gain based on our evaluation criteria.
One common approach in such case is using the idea of cross validating your existing training set, to divide it into multiple equal-sized subsets. Then for each subset to train your tree based on your chosen metric using the remaining sets and calculate some error rate using the said subset as test set. Finally to average all the error rates and you can get some idea of the degree of your “global optimality” for your specific candidate tree. Of course if you have several similarly performed trees which are all more or less uncorrelated, you can always use ensemble idea to do voting such as random forest.
