Decision Tree Learning
Tree Models & Ensembles DS practice problem on Onlearn.
Difficulty: hard.
Topics: Understanding Decision Tree Learning, Shannon Entropy, Information Gain, Gini Impurity, Depth-First Search, Leaf Node Labeling, Supervised Learning, Information Theory, Data Structures, Computational Complexity, Model Interpretability, Recursive Partitioning, Impurity Measures, Tree Pruning, Feature Selection, Categorical Encoding.
Write a Python function that implements the decision tree learning algorithm for classification. The function should use recursive binary splitting based on entropy and information gain to build a decision tree. It should take a list of examples (each example is a dict of attribute value pairs) and a list of attribute names as input, and return a nested dictionary representing the decision tree.