I have been doing some research and have been trying to find "Rule-Based" and "Tree-Based" (statistical) models that are capable of overcoming the "greedy search algorithm" used within standard decision trees (e.g. CART, C5, ID3, CHAID).
Just to summarize: The "Greedy Search Algorithm" refers to selecting "locally optimal decisions" - this has certain benefits in terms of computing cost and time, but will very likely lead to missing "globally optimal decisions". Here is an example of (the disadvantage of) greedy search:
The above picture shows a task where an algorithm is required to find the largest number ("99") in this tree structure. The "greedy algorithm" will always pick the larger number at every possible decision : In the middle picture, we see that the greedy algorithm picks "12" instead of "3" (because 12 > 3), and then picks "6" instead of "5" (because 6 > 5) - thus, the "greedy algorithm" concludes that "6" is the largest number within this tree structure. However, we can see that the largest number in this tree structure is actually "99" - but the "greedy algorithm" misses the actual largest number all together.
On the statistical modelling side, common decision tree algorithms (e.g. CART, C5, ID3, CHAID, conditional inference tree, etc.) all use the "greedy algorithm" when constructing the decision tree (e.g. choosing tree splits that optimize Entropy/Gini on the local level) - this almost surely results in any of these decision trees being sup-optimal, as a "better decision tree" (e.g. more accurate) is likely to exist, but was never considered due to greedy search (although I have not seen an exact mathematical proof for this statement). For smaller datasets with few variables and less complicated patterns (e.g. iris flower dataset), the use of the "greedy search" algorithm has not been (anecdotally) reported to significantly hinder the performance of the final decision tree - however, for larger and more complicated datasets, the "greedy search" algorithm has been suspected to produce suboptimal decision trees.
With the advent of newer machine learning and statistical models, I have been trying to research newer tree-based and rule-based models that do not suffer as much from "greedy search" : in general, "tree based" and "rule based" this is particularly useful when you would like the final statistical model be "easily explainable and interpretable" (while sacrificing predictive power). So far, here is the list of models I have come across:
Evolutionary Decision Trees: Decision Trees can be constructed using genetic/evolutionary algorithms which might result in a more comprehensive search (e.g. https://cran.r-project.org/web/packages/evtree/index.html)
CORELS: Certifiably Optimal Rules List (https://cran.r-project.org/web/packages/corels/index.html)
PRE: Prediction Ensemble Rules - said to perform at times comparable to a random forest (e.g. https://www.jstatsoft.org/article/view/v092i12)
Bayesian Rules : https://rdrr.io/cran/sbrl/
Classification Based Association Rules: https://cran.r-project.org/web/packages/arulesCBA/arulesCBA.pdf
NB Rule Mining : https://cran.r-project.org/web/packages/arulesNBMiner/index.html
Reinforcement Learning Trees: A new variable selection method is used during the construction of decision trees to "learn" important and unimportant variables within the dataset (e.g. https://cran.r-project.org/web/packages/RLT/index.html - note: I do not think it is possible to extract decision rules from these trees?)
Fuzzy Rule Mining: https://cran.r-project.org/web/packages/frbs/index.html
Evolutionary Fuzzy Rule Mining: https://cran.r-project.org/web/packages/SDEFSR/index.html, https://cran.r-project.org/web/packages/SDEFSR/vignettes/SDEFSRpackage.pdf
Evolutionary Rules: https://cran.r-project.org/web/packages/fugeR/index.html
KEEL Algorithm: https://www.researchgate.net/publication/318646414_Mining_association_rules_in_R_using_the_package_RKEEL/link/59ba64a0458515bb9c4c8b24/download
Subgroup Analysis Algorithm:** https://cran.r-project.org/web/packages/rsubgroup/rsubgroup.pdf
Extreme Rule Fit: https://cran.r-project.org/web/packages/xrf/index.html
Quantitative Rule Mining: https://cran.r-project.org/web/packages/qCBA/index.html
Recursive Rule Mining: https://cran.r-project.org/web/packages/RecAssoRules/index.html
Patient Rule Induction (PRIM): https://cran.r-project.org/web/packages/prim/index.html
This was a list of rule-based and tree-based models I was able to find, with available software implementations in the R programming language.
Question: Has anyone used any of these models before? Are there any standard rule-based and tree-based models that are currently being used for overcoming the "Greedy Search" algorithm within common decision trees? I am specifically looking for modern statistical models that provide "explainable and interpretable results" - and not "black box" models like random forest and gradient boosting. In my case, the "model rules" are paramount.
Does anyone have any suggestions?
Thanks
References:
- https://en.wikipedia.org/wiki/Greedy_algorithm
- https://cran.r-project.org/web/packages/KODAMA/vignettes/KODAMA.pdf
- https://arxiv.org/abs/1904.12847 (Globally Optimal Trees - no R package available)
- https://link.springer.com/article/10.1007/s10994-017-5633-9 (Optimal Classification Trees - no R package available)
- Multivariate Decision Trees: https://cran.r-project.org/web/packages/ROP/ROP.pdf
- Multivariate Decision Trees for Survival Data: https://cran.r-project.org/web/packages/MST/index.html
step
function in R is not greedy. It is a method to select models based on AIC. It looks like the greedy stepwise model selection (repeatedly adding parameters to the model). But, the standard option has 'both' directions and allows the removal of features as well.... So it is an example of a non-greedy algorithm and many people use it. .... Does this answer your question? $\endgroup$