<jupyter_start><jupyter_text>CS4618: Artificial Intelligence IDecision Trees and Random Forests    Derek Bridge    School of Computer Science and Information Technology    University College Cork Initialization$\newcommand{\Set}[1]{\{1\}}$ $\newcommand{\Tuple}[1]{\langle1\rangle}$ $\newcommand{\v}[1]{\pmb{1}}$ $\newcommand{\cv}[1]{\begin{bmatrix}1\end{bmatrix}}$ $\newcommand{\rv}[1]{[1]}$ $\DeclareMathOperator{\argmax}{arg\,max}$ $\DeclareMathOperator{\argmin}{arg\,min}$ $\DeclareMathOperator{\dist}{dist}$$\DeclareMathOperator{\abs}{abs}$<jupyter_code>%load_ext autoreload
%autoreload 2
%matplotlib inline
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

from sklearn.tree import plot_tree

from sklearn.preprocessing import LabelEncoder

from sklearn.tree import DecisionTreeClassifier
from sklearn.tree import DecisionTreeRegressor

from sklearn.ensemble import RandomForestClassifier<jupyter_output><empty_output><jupyter_text>Acknowledgement        The random forest diagram is based on one in A. G&eacute;ron: Hands-On Machine Learning with Scikit-Learn, Keras &amp;, TensorFlow (2nd edn), O'Reilly, 2019.     Decision Trees    Decision Trees are very popular in Machine Learning.    They can be used for regression and for classification.    In the case of classification, they can be used for binary classification or for multiclass        classification (so you don't need one-versus-rest or one-versus-all).        They are more complex than linear models and so can better fit complex datasets.        Many people claim that they produce interpretable models &mdash; see later in this lecture.    Random Forests are another popular model in Machine Learning, and they contain        Decision Trees &mdash; see later in this lecture.     Decision Trees for the CS1109 Dataset<jupyter_code># Use pandas to read the CSV file into a DataFrame
cs1109_df = pd.read_csv("../datasets/dataset_cs1109.csv")
# The features
cs1109_features = ["lect", "lab", "cao"]

# Extract the features
cs1109_X = cs1109_df[cs1109_features].values

# Target values, encoded and converted to a 1D numpy array
label_encoder = LabelEncoder()
cs1109_y = label_encoder.fit_transform(cs1109_df["outcome"])
# Create the Decision Tree object
tree_classifier = DecisionTreeClassifier(max_depth=3)

# Fit the model. Note that scaling of the data is not needed.
tree_classifier.fit(cs1109_X, cs1109_y)
# Draw it
fig = plt.figure(figsize=(20,8))
plot = plot_tree(tree_classifier, feature_names=cs1109_df.columns, class_names=["fail", "pass"], fontsize=12)
plt.show()<jupyter_output><empty_output><jupyter_text>Classification using a Decision Tree    Do you remember Craig?                    He attended 60% of lectures, 25% of labs and has 500 CAO points.                What does the Decision Tree predict?                    Start at the root: is Craig's lab attendance &le; 83%?            Yes, so move left: is his lab attendance &le; 62%?            Yes, so move left: is his lecture attendance &le; 87.5%?            Yes, so move left: he fails.                What about Chiyo?<jupyter_code>students = np.array([[60, 25, 500],[80, 90, 350]])
label_encoder.inverse_transform(tree_classifier.predict(students))<jupyter_output><empty_output><jupyter_text>Reading the nodes of the tree (not important in CS4618)    samples: how many training examples the node applies to.                    E.g. 149 training examples have lab attendance &le; 83%.                value: how many training examples of each class this node applies to.                    E.g. [45, 104] means this node applies to 45 people who failed and 104 who passed.                gini: is the Gini impurity of a node (with values in $[0.0, 0.5]$):                    it measures how often an example would be incorrectly labeled if it was randomly labeled                 according to the distribution of labels for this node;                        e.g. gini of 0 means no impurity: all examples that this node applies to belong to the                 same class;                        Google the formula, if interested (and make sure you're reading about Gini Impurity or the                Gini index, not the Gini coefficient!).                         Depth of a Decision Tree    max_depth is a hyperparameter.    Increasiing max_depth increases complexity.    It follows that increasing max_depth too much will result in overfitting.    If there is no constraint on tree depth, then branches will be grown until all leaves are pure.     Decision Trees for the Cork Property Prices Dataset     Let's quickly see a Decison Tree for regression.<jupyter_code># Use pandas to read the CSV file into a DataFrame
cork_df = pd.read_csv("../datasets/dataset_corkA.csv")
# The features
cork_features = ["flarea", "bdrms", "bthrms"]

# Extract the features
cork_X = cork_df[cork_features].values

# Target values, converted to a 1D numpy array
cork_y = cork_df["price"].values
# Create the Decision Tree object
tree_regressor = DecisionTreeRegressor(max_depth=3)

# Fit the model. Note that scaling of the data is not needed.
tree_regressor.fit(cork_X, cork_y)
# Draw it
fig = plt.figure(figsize=(20,8))
plot = plot_tree(tree_regressor, feature_names=cork_df.columns, fontsize=12)
plt.show()<jupyter_output><empty_output><jupyter_text>Regression using a Decision Tree    Are you still trying to sell your house?                    126 square metres of floor area, 3 bedrooms, 1 bathroom                What does the Decision Tree predict?                    Start at the root and follow the decisions down to a leaf.            At any node, value is the prediction and is simply the mean target values of                 the training examples that the node applies to.                         Learning a Decision Tree    scikit-learn uses the CART Algorithm  (Classification and Regression Tree). We        will describe this, but only in high-level terms.                    It only produces binary trees (hence yes/no questions in                non-leaf nodes);                        it is recursive; and            it is greedy.                There are other algorithms (e.g. ID3, which can produce non-binary trees) and all sorts of        variants (e.g. C4.5 is like CART but uses entropy in place of Gini), including ones that        can directly handle nominal-valued features and missing values, which we will not study.        Below, we show the CART Algorithm for classification.                    For regression, the only difference is the loss function: in place of Gini it uses the                mean squared error between the $y$-values of the training examples and their mean.                            Note we do not need to scale the data before using this algorithm. The CART Training Algorithm    For each feature $x_i$ and each value $v$, split the dataset into two:                    $X_{\mathit{left}}$ are the examples in $X$ for which $x_i \leq v$            $X_{\mathit{right}}$ are the examples in $X$ for which $x_i > v$                and calculate the CART loss function:         $\frac{|X_{\mathit{left}}|}{|X|}\mbox{Gini}(X_{\mathit{left}}) +          \frac{|X_{\mathit{right}}|}{|X|}\mbox{Gini}(X_{\mathit{right}})$        From the above, choose the feature $x_i$ and  value $v$ with lowest loss    If a stopping criterion has been reached (e.g. maximum depth or if no split reduces impurity) then                    return                Else                    Recursively call CART on $X_{\mathit{left}}$            Recursively call CART on $X_{\mathit{right}}$             Discussion: Efficiency    Learning is $O(mn \log_2 m)$ for the basic CART algorithm above.                    Of course, hyperparameters such as a maximum depth can speed-up learning.                Prediction is roughly $O(\log_2 m)$ (which is the depth of tree, assuming the tree is        balanced, which it often, approximately, is). This is fast!     Discussion: Parametric learning vs. non-parametric learning    Parametric learning: the number of parameters is known prior to training and is not affected by        $m$ the number of examples in the training set.                    E.g. Linear Regression the number of parameters is $n + 1$            E.g. Polynomial Regression the number of parameters is $\frac{(n+d)!}{d!n!}$                Non-parametric learning: the number of parameters is not known in advance and may grow with        the size of the training set.                    E.g. For Decision Trees, in some sense, the nodes are the parameters: the structure of the                model (tree) may grow to accommodate the complexity of the training data.                        E.g. For kNN, in some sense, the neighbours are the parameters and the more training examples                there are, the more different possible sets of neighbours there are.                This does not mean that non-parametric models will have lower validation error.                     Unconstrained, they are prone to overfitting.            So we want to impose some constraints on the CART algorithm to restrict the shape                of the Decision Tree (such as maximum depth and others).                        Similarly, we avoid smal values for $k$ in KNN.             Discussion: Interpretability    The model is intrepretable:                     we can display the tree and people can see what has been learned.                An individual prediction is explainable:                    we can display the path through the tree.                <!--    We might discuss this further in a later lecture.    --> Ensembles    We can combine models into what is called an ensemble.                    The ensemble often out-performs the individual models that it contains.                                    The wisdom of the crowd.                                                                Ensembles can turn weak learners into strong learners.                    Weak learners: one that are doing only slightly better than random.            Strong learners: ones with much higher accuracy/lower error than chance.                If this is to happen, there needs to be diversity among the individual models. Various approaches    The simplest approach, e.g. for classification:                    Train several different classifiers (e.g. Logistic Regression, Decision Tree, others);            At prediction time, each model classifies the example;            They vote on the result.                If you want to try this: VotingClassifier in scikit-learn.        But the main ways of building ensembles are:                     bagging (e.g. Random Forests below)            boosting (not covered)            stacking (not covered)                They are general techniques, applicable to both regression and classification.     Random Forests    Random Forests use bagging.    Bagging ('bootstrap aggregating'):                    Train several models of the same kind (e.g. several Decision Tree classifiers).            But do so on different random subsamples of the training set (chosen with replacement).                        To make a prediction for a new example:                    Classification: take a vote.            Regression: compute their mean.               How many trees in a forest?    The number of Decision Trees to use in the ensemble is a hyperparameter!    To some extent, 'the more, the merrier':                     Predictions typically become more reliable as the ensemble gets larger.            Seldom is the accuracy of the ensemble lower than the accuracy of any of its members                &mdash; but this is not guaranteed                        In practice, you can either guess how many to use or                 choose its value using grid search or randomized search.                               If you want to try bagging in scikit-learn there are BaggingClassifier          and BaggingRegressor classes.         But if you want to try bagging for Decision Trees, i.e. a random forest, there is a convenience class         RandomForest.                    The number of trees (n_estimators) and the depth of those trees                 (max_depth) are among many hyperparameters.                            scikit-learn's Random Forests increase diversity                    Not only do they train on different random subsamples of the training set&hellip;            But also, when building the model, they don't select the best feature for splitting; they                select among a random subset of the features.                         You will get different models every time unless you seed the random state.<jupyter_code># Create the Random Forest object
forest_classifier = RandomForestClassifier(n_estimators=30, max_depth=3, random_state=2)

# Fit the model. Note that scaling of the data is not needed.
forest_classifier.fit(cs1109_X, cs1109_y)
label_encoder.inverse_transform(forest_classifier.predict(students))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.06111793611793612, 'fraction_numerical': 0.012054668304668305, 'mean_word_length': 2.5782967032967035, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '279571', 'license': 'MIT', 'n_tokens_mistral': 3343, 'n_tokens_neox': 3055, 'n_words': 1525, 'path': 'ai1/lectures/AI1_15_decision_trees.ipynb', 'repo_name': 'derekgbridge/artificial_intelligence', 'size': '13024'}