7
$\begingroup$

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:

enter image description here

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:

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:

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ The 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$
    – Sextus Empiricus
    Nov 3, 2021 at 14:25
  • $\begingroup$ @ Sextus Empiricus : Thank you for your reply! I will look more into this - I am interested in finding out about "rule based" and "tree based" statistical models, that specifically "output a set of interpretable decision rules". I think the "step function" that you have cited is more for model comparison? I will keep reading about this - thank you for your reply! $\endgroup$
    – stats_noob
    Nov 3, 2021 at 17:33

1 Answer 1

Reset to default
1
$\begingroup$

Rule-based classifier cannot by greedy by definition, IMHO, since they involve only 1 "node". Hence, any rule-based classifier should fulfil what you need. Then, it depends what are your data/task. For classification I would suggest arulesCBA as the first choice to try: https://cran.r-project.org/web/packages/arulesCBA/index.html

Personally, I have very good experience with Sirus (2class classification but very stable results, no problem with minority-class prediction): https://cran.r-project.org/web/packages/sirus/index.html Best!

Improve this answer
$\endgroup$
1
  • $\begingroup$ @ Zdenek: Thank you! I will check this out! $\endgroup$
    – stats_noob
    Aug 29, 2022 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.