Data Structures & Algorithms

• Name: Rowan Lowden
• Semester: Summer 2025
• Topic: Decision Tree Analysis

Introduction/Overview

In this report, I examine decision tree algorithms, a broad class of supervised learning methods used in machine learning. Decision trees represent models as hierarchical structures, where data is recursively partitioned into smaller subsets based on measures of split quality. They are widely applied to both classification and regression tasks due to their simplicity, interpretability, and ability to handle both categorical and numerical data¹. A decision tree consists of a root node, branches, internal decision nodes, and leaf (terminal) nodes. The root node has no incoming branches, only outgoing branches leading to decision nodes that apply specific conditions to split the data into increasingly homogeneous subsets until a terminal node is reached².

Classification and Regression Trees (CART) are a specific implementation of decision tree algorithms designed for both classification and regression problems. In classification, CART predicts categorical outcomes, for example, determining whether a mushroom is edible or poisonous based on attributes such as color, size, and odor³. In regression, it predicts continuous values, such as estimating house prices from features like square footage and location⁴. The algorithm recursively selects the most informative feature at each node using a predefined criterion (Gini impurity for classification, variance reduction for regression) to optimize split quality⁵. One of CART’s key advantages is its interpretability; its explicit, rule-based structure makes it possible to trace each decision path, making it especially valuable in applications ranging from medical diagnosis to economic forecasting and weather prediction, etc ⁶.

This report provides a focused analysis of decision tree algorithms, covering their historical development, theoretical foundations, practical implementations, and empirical performance. It begins with a brief history and survey of real-world applications, followed by an explanation of data-splitting criteria and an analysis of computational complexity using CART pseudocode. The implementation section compares two approaches: a scikit-learn DecisionTreeClassifier and a custom CART algorithm applied to three datasets. An empirical analysis evaluates model accuracy and scalability across varying dataset sizes and feature counts. The report concludes with a sumamry including key and implementation challenges.

Algorithm Development

Decision Trees have a rich history in machine learning, with origins dating back to the 1960s. One of the earliest methods, Hunt’s Algorithm, was developed to model human inductive learning, replicating how people make decisions based on prior experiences. Introduced by J. Hunt and colleagues, this work laid the foundation for modern decision tree methods. ⁷

In 1986, Ross Quinlan introduced the ID3 algorithm, which used information gain to split data at each node, pioneering recursive binary splitting for classification. ³ Quinlan later improved this approach with the C4.5 algorithm in 1993, adding pruning to reduce overfitting, handling both continuous and discrete attributes, and using gain ratio for more accurate splits.⁵ Around the same time, Breiman et al. developed the CART (Classification and Regression Trees) algorithm, which employed Gini Impurity for classification and Mean Squared Error for regression. ⁴

Today, Decision Trees remain a cornerstone of machine learning and have inspired powerful ensemble methods such as Random Forests and Gradient Boosting, which combine multiple trees to enhance predictive accuracy and robustness. ⁶.

Application

Decision trees are widely used across scientific fields beyond computer science due to their ability to identify key predictive variables. They are especially valuable in high-stakes domains such as healthcare, environmental monitoring, and resource management, where transparency and trust in model outputs are critical ^{8 9 10}. By producing rule-based decisions and highlighting the most influential features, decision trees not only deliver accurate predictions but also explain the reasoning behind them which enable insight driven interventions. Below I summarize 3 recent research studies I found interesting that utlized decision tree models.

The first study, by Lu & Ma (2020), developed two decision-tree-based models for short-term water quality predictions in Oregon’s Tualatin River. Using hourly environmental data such as temperature, dissolved oxygen, pH, conductivity, turbidity, fluorescence, they applied CEEMDAN for data cleaning before training Random Forest and Gradient Boosting models. Compared with conventional baselines, their hybrid decision tree model achieved stable, accurate forecasts, enabling proactive management actions such as anticipating low-oxygen events or turbidity spikes ¹¹.

The second study, by Elhazmi et al. (2022), addressed the urgent need for ICU triage tools during the COVID-19 pandemic. Conducted across 14 hospitals in Saudi Arabia, the study trained a C4.5 decision tree on clinical data from 1,468 critically ill patients to predict 28-day mortality. The model incorporated variables such as intubation status, vasopressor use, oxygenation ratio, age, and gender, achieving 73.1% accuracy. Its transparent, rule-based structure allowed clinicians to quickly assess patient risk at the bedside, offering clear interpretability compared to traditional logistic regression ¹².

The third study, by Hajihosseinlou, Asghari, and Shirvani (2023), applied Light Gradient Boosting Machine (LightGBM) to mineral exploration in Iran’s Varcheh district. Analyzing geological, geochemical, and remote sensing data, the model achieved 92% precision in identifying known mineral deposits within 10% of the mapped area. The decision-tree-based approach significantly reduced exploration costs by focusing efforts on high-prospect zones, demonstrating its value in economic geology ¹³.

From forecasting river conditions to ICU triage and mineral exploration, decision trees demonstrate versatility, strong predictive power, and clear interpretability. Their capacity to handle diverse data types, model complex relationships, and provide actionable rules makes them an indispensable tool for both scientific research and real-world decision-making.

Theoretical Analysis

Splitting Data: Entropy, Information Gain, and Gini Impurity

To understand the performance of decision tree algorithms such as CART, it is important to examine how they determine the best feature to split the dataset at each step. The goal of any decision tree is to create splits that produce increasingly homogeneous subsets, improving classification or regression accuracy. Different decision tree algorithms use different measures to guide these splits. ID3 and C4.5 use entropy and information gain, while CART, the focus of this project, uses Gini Impurity for classification.

Entropy measures the amount of disorder in a dataset and is fundamental to information theory. It is calculated as:

$$ \text{Entropy}(S) = - \sum_{c \in C} p(c) \log_2 p(c) $$

• $S$ is the dataset
• $c$ is the classes in the set $S$.
• $p(c)$ represents the proportion of data points that belong to class $c$

Calcuated entropy values fall between 0 and 1 with low entropy or disorder in a set equaling 0 and if a set has samples of half one class and half another the entropy will be the highest at 1. In order to find the optimal split, the decision tree algorithm will find the best feature to split the dataset with the smallest amount of entropy.

Information gain measures the reduction in entropy after a dataset is split on a feature. If an attribute has high information gain it will produce the best split which means it is excelling at classifying the training data according to the target classification. It is represented by the following formula:

$$ \text{Information Gain}(S, a) = \text{Entropy}(S) - \sum_{v \in \text{Values}(a)} \frac{|S_v|}{|S|} \cdot \text{Entropy}(S_v) $$

• $a$ represents attribute being split
• Entropy$(S)$ is the entropy dataset
• $\frac{|S_v|}{|S|}$ is the proportion of the subset with a specific attrbution to the entire dataset.

For example, if we consider a dataset with 100 mushroom samples and 60 are edible while 40 are poisonous, the entropy is:

$$ \text{Entropy}(S) = -0.6 \log_2(0.6) - 0.4 \log_2(0.4) = 0.970 $$

If the algorithm splits the data on odor. If 30 mushrooms have a foul odor and all of them are poisonious (entropy = 0) and the remaining 70 have mixed classification (60 edible and 10 poisonous), the entropy would be calcauted as followed

$$ \text{Entropy}(S_{\text{odor} \neq \text{foul}}) = -\left(\frac{60}{70}\right) \log_2 \left(\frac{60}{70}\right) - \left(\frac{10}{70}\right) \log_2 \left(\frac{10}{70}\right) $$

$$ \text{Entropy} = -0.857 \log_2(0.857) - 0.143 \log_2(0.143) \approx 0.863 $$

With an the entropy caculations of 0 and 0.863. The calculated information gain from splitting on the odor feature would be:

$$ \text{Gain}(S, \text{odor}) = \text{Entropy}(S) - \left( \frac{30}{100} \cdot 0 \right) - \left( \frac{70}{100} \cdot 0.863 \right) $$

$$ \text{Gain}(S, \text{odor}) = 0.970 - 0 - 0.604 = 0.366 $$

This means that splitting by odor is a significant reduction in entropy and reduces the impurity, therefore the decision tree algorithm would likely select this as the first feature to split on.

Gini impurity, used by CART, is a probability calculation signifiying if a random data point is incorrectly classificed in a dataset. Similar to entropy, if a set $S$ is pure and all one class (edible) then the gini impurity would be 0. Unlike entropy, the gini impurity maximum depends on the number of classes. If there are 2 classes, like the mushroom example, the maximum gini impurity is 0.5. The formula for gini imputiy is as follows:

$$ \text{Gini}(S) = 1 - \sum_{c \in C} \left(p(c)\right)^2 $$

• $C$ is the set of classes
• $p(c)$ is the probability of a datapoint bellonging to class $C$.
• $\sum_{c \in C}$ the sum of $c$ within $C$

Entropy and Gini Impurity are both measures of impurity used by decision tree algorithms to decide where to split the data. Entropy is based on information theory and involves logarithmic calculations, while Gini Impurity is simpler and faster to compute, measuring the probability of misclassification. The DecisionTreeClassifier in scikit-learn defaults to using Gini Impurity because it is computationally efficient and typically results in similar split decisions as entropy.

Understanding how decision trees choose splits using entropy, information gain, and Gini impurity provides valuable insight into the logic behind the algorithm. These measures ensure the model reduces impurity at each step, gradually organizing the dataset into more homogenous subsets. By visualizing and calculating these values in examples like the mushroom dataset, we gain a clearer picture of how the algorithm operates under the hood. This foundation helps contextualize later analysis of runtime complexity, scalability, and model performance across different dataset.

Time and Complexity: Big O

Understanding the time and space complexity of the CART Decision Tree algorithm is essential for evaluating its scalability and performance. CART builds decision trees using a recursive, top-down, divide-and-conquer approach, classifying input data based on feature values. At each internal node, the algorithm uses a greedy search to find the feature and threshold that yield the greatest reduction in impurity, measured with Gini Impurity as described earlier. ²

The training time of a decision tree depends on the number of samples $n$, the number of features $m$, and the depth of the tree. The table below summarizes the theoretical time and space complexities for the best, average, and worst cases considered in this report. A detailed explanation and pseudocode follow.

Case	Time Complexity	Space Used
Best	$O(n \cdot m \cdot \log n)$	$O(n)$
Average	$O(n \cdot m \cdot \log n)$	$O(n)$
Worst	$O(n^2 \cdot m)$	$O(n)$

Pseudocode: CART Algorithm

To better understand where the logarithmic depth and nested evaluations come from, consider the following simplified pseudocode for growing a binary decision tree using the CART algorithm: ¹⁴:

Initialize active_nodes = { root containing all samples }
depth = 0

while active_nodes is not empty:
    next_active_nodes = {}

    for each node in active_nodes:
        if stopping_condition(node):
            make_leaf(node)
        else
            (best_feature, threshold) = find_best_split(node.data) //gini impurity
            (left_data, right_data) = split(node.data, best_feature, threshold)
            create left_child, right_child
            assign data
            add left_child and right_child to next_active_nodes

    active_nodes = next_active_nodes
    depth = depth + 1
end while

The recursion depth of the tree corresponds to the number of iterations of the outer while loop not being empty and depends on how balanced the splits are. In the best and average cases, the dataset is split evenly at each step, leading to a balanced binary tree with a depth proportional to $logn$ In the worst case, where splits are highly unbalanced and a split removes only one sample, the depth can grow to $n$. This depth is important because it determines the number of times the algorithm must descend into child nodes during training.

Within each iteration of the while loop, the inner for loop calls find_best_split(node.data) for each active_node at the current depth. This function evaluates all features to determine the optimal split, which may require sorting or scanning through the data at that node. If sorting is nessecary the implementation will require $O(n \log n)$ operations per feature or $O(n)$ if only scanning is performed. Because every node at a given depth collectively processes the entire dataset, the total amount of work across all levels in a balanced tree sums to $O(n \cdot m \cdot \log n)$.⁴

In the worst-case scenario, where the tree becomes a chain of nodes, the number of node evaluations grows quadratically, resulting in a time complexity of $O(n^2 \cdot m)$. Practical implementations, such as scikit-learn’s CART-based DecisionTreeClassifier, typically use stopping conditions such as maximum depth or minimum samples per split to prevent such inefficient growth. ⁴

The space complexity of a decision tree is $O(n)$ across all cases. This is because a binary tree with $n$ samples can have at most $2n - 1$ nodes, and each node stores a small, constant amount of information such as the split feature, threshold, and label distribution. While deeper trees require more internal nodes, the total memory required still scales linearly with the size of the dataset. ³

Proof of Correctness: Loop of Invariant

Loop Invariant: At the start of each iteration of the while loop at depth d:

1. Every node in active_nodes contains samples that match its path of previous splits.
2. All samples appear in exactly one node, they are never duplicated or lost.
3. For all nodes still in active_nodes, if it terminated right now, it would be labeled based on the current samples the node contains.
4. A node already marked as a leaf has a final classification label which match all other samples in the node.

Initialization: At depth = 0, before the first loop iteration, active_nodes = {root}, which contains all samples of the given dataset. No splits have occured, so the invariant holds.

Maintenance: Assume the invariant holds at the start of each iteration. For each node in active_nodes, if the stopping condition is met, a leaf node is created and a label is assigned without altering the data, so the invariant holds. If the node is split, split(node.data, best_feature, threshold partitions the node’s samples into left_data and right_data without duplication or loss of data. Each child node inherits exactly one subset of data and replaces the parent in active_nodes. Their data still matches the path of splits leading to them. Existing leaves remain correct and the invariant still holds for the next iteration.

Termination: The loop ends when active_nodes is empty. By the invariant, every sample has followed a unique path from the root to exactly one leaf, and no sample is misassigned. Therefore, the algorithm correctly represents the tree's partitioning and can classify any sample consistently.

Implementation

For this project, I used Python due to its robust ecosystem of machine learning libraries. I relied on pandas and numpy for data preprocessing, matplotlib for tree visualzation, excel for graphing, scikit-learn for implementing one version of the Decision Tree algorithm, and a second implmentation of CART algorithm from scratch. This includes training the model and evaluating performance. I worked with 3 datasets from Kaggle:

• Mushroom dataset (~8000 samples, 22 features) ¹⁵
• Iris dataset (100,000 samples, 4 features) ¹⁶
• Clinical diabetes dataset (100,000 samples, 16 features) ¹⁷

I began with the mushroom dataset, but due to its smaller size, I added larger datasets to better explore the algorithm's runtime and scalability as well as exploring what it means to have different number of features for classification.

DecsionTreeClassifer (sci-kit learn)

To build and train the model, I used scikit-learn’s built-in DecisionTreeClassifier, a common implementation of the CART (Classification and Regression Tree) algorithm. After researching popular workflows, I found this method was widely used in machine learning tasks. I used functions such as train_test_split() to split data, and accuracy_score() and classification_report() to evaluate how well the model performed on the test set. ¹⁸ These tools allowed me to quickly understand the model's performance and adjust parameters when necessary. The decision tree algorithm provided an interpretable model that could accurately classify data with high reliability (accuracy values available in the empirical analysis). ¹⁹

A key challenge was learning how to structure the machine learning workflow, especially understanding how to encode categorical features, split data correctly, and interpret performance metrics. Sklearn’s built-in tools made it easier to get reliable results quickly and focus on understanding how decision trees work under the hood. This project gave me hands-on experience applying a decision tree algorithm across datasets of varying size and complexity using a professional workflow.

Below I walk through my code to show my a implmented these built in tools to learn and analyze decision tree algorithm.

def split_data(X, y, test_size=0.2):
    return train_test_split(X, y, test_size=test_size, random_state=42)

This function splits the feature set (X) and labels (y) into training and testing subsets. It uses an 80/20 split by default and sets a fixed random_state to ensure reproducible results.

def train_decision_tree(X_train, y_train):
    clf = DecisionTreeClassifier(random_state=42)
    clf.fit(X_train, y_train)
    return clf 

This function creates and trains a scikit-learn DecisionTreeClassifier on the training data. The random_state is set for reproducibility. The .fit() method builds the tree by recursively splitting the dataset based on feature values to reduce Gini impurity.

After training the model using DecisionTreeClassifier, I visualized a simplified tree by setting a max_depth of 5 and classified the mushroom dataset. A depth of 5, makes the tree small enough to interpret while still showing how the model selects features and splits based on them. Each node displays the splitting condition, number of samples, Gini impurity, and the predicted class.

This visual shows how the decision tree identifies patterns in the data. For example, in the mushroom dataset, the model may split first on odor, which has high predictive value, followed by stalk, qualties of the cap, or other important features. The darker the color the more confident the model is in the predicition while the lighter color has more mized samples (edible and poisinous) and a higher Gini impurity. The blue node predicts poisonous while the orange predicts edible mushrooms.

def evaluate_model(model, X_test, y_test):
    y_pred = model.predict(X_test)
    accuracy = accuracy_score(y_test, y_pred)
    print(f"Accuracy: {accuracy}")
    print("Classification Report:")
    print(classification_report(y_test, y_pred))
    return accuracy

This function uses the trained model to predict labels on the test set, then evaluates its performance using accuracy_score and classification_report. It prints and returns the overall accuracy, and displays precision, recall, and F1-score for each class.

def time_model_training(X, y, sample_sizes):
    results = []

    for size in sample_sizes: #loop through the sample sizes
        #sample of the data
        X_sample = X[:size]
        y_sample = y[:size]

        #split into the train and test sets
        X_train, X_test, y_train, y_test = train_test_split(X_sample, y_sample, test_size=0.2, random_state=42)
        
        #train and time the model
        start = time.time()
        model = train_decision_tree(X_train, y_train)
        end = time.time()
        
        #evalulate the model with accuracy score
        accuracy = evaluate_model(model, X_test, y_test)

        #timing 
        duration = end - start
        #save results
        results.append((size, accuracy, duration))

    return results

This function evaluates how the model’s training time and accuracy change as the dataset grows. For each sample size, it splits the data, trains the model, records how long training takes, evaluates accuracy, and stores the results for empirical analysis.

CART Algorithm (from scratch)

You can find the original code for this in CART and Main. I used the following sourcees to help me with this. ^{20 18}

Although I did not initially plan to implement two versions of the decision tree algorithm, starting with scikit-learn’s built-in DecisionTreeClassifier gave me a strong foundational understanding of the workflow, key parameters, and performance evaluation. This baseline experience made it much easier to translate the theory into code when I later implemented the CART (Classification and Regression Tree) algorithm from scratch in Python. My custom version uses its own Node structure and recursive tree-building logic to split datasets based on Gini impurity. Unlike the scikit-learn implementation, which abstracts away these details, my version explicitly handles each step: choosing the best split, partitioning the data, and assigning labels to leaf nodes.

The foundation of my implementation is the Node class, which represents both decision and leaf nodes:

""" Defines the Node class for the Decision Tree. Either a decision node or a leaf node."""
class Node:
    def __init__(self, feature=None, threshold=None, left=None, right=None, *, value=None):
        self.feature = feature          # index of feature to split on
        self.threshold = threshold      # value of the split
        self.left = left                # left subtree/child
        self.right = right              # right subtree/child
        self.value = value              # class label if it's a leaf
        
    # If value is not None and has no children, this is a leaf node
    def is_leaf_node(self):
        return self.value is not None

Each node stores the feature index and threshold used for splitting, references to left and right child nodes, and a value if the node is a leaf. Internal nodes direct the flow of data down the tree, while leaf nodes hold the final class label.

The training process begins with the fit() method, which calls the recursive _build_tree() fucntion. This function is responsible for creating the tree by splitting the dataset until stopping criteria are met:

def fit(self, X, y):
    self.root = self._build_tree(X, y)

 def _build_tree(self, X, y, depth=0): 
        num_samples, num_features = X.shape # Get the number of samples and features
        num_labels = len(np.unique(y)) # countsof unique labels in dataset

        # stopping criteria to make a leaf node
        # If max depth is reached, or if all samples belong to the same class, etc
        if (depth >= self.max_depth or num_labels == 1 or num_samples < self.min_samples_split):
            leaf_value = self._most_common_label(y)
            return Node(value=leaf_value)

        # Find the best feature and threshold to split on based on GIni impurity
        best_feat, best_thresh = self._best_split(X, y)
        if best_feat is None:
            return Node(value=self._most_common_label(y))

        # Create a decision node with the best feature and threshold
        left_idxs = X[:, best_feat] < best_thresh
        right_idxs = ~left_idxs # Get the indices for left and right splits

        # Recursively build the left and right subtrees
        left = self._build_tree(X[left_idxs], y[left_idxs], depth + 1)
        right = self._build_tree(X[right_idxs], y[right_idxs], depth + 1)
        # Return a new Node with the best feature and threshold, and the left/right subtrees
        return Node(feature=best_feat, threshold=best_thresh, left=left, right=right)

At each node, _build_tree() determines whether further splitting is possible based on tree depth, sample size, or class purity. If so, it finds the best split and recursively builds the left and right subtrees. If not, it creates a leaf with the most common class label for that subset.

Selecting the best split is done in _best_split(), which examines all feature–threshold combinations and calculates their Gini gain:

    """ Finds the best feature and threshold to split the data based on Gini impurity. """
    def _best_split(self, X, y):
        best_gain = -1 # Initialize best gain to a low value so any will be better
        best_feat, best_thresh = None, None

        for feature_index in range(X.shape[1]):
            thresholds = np.unique(X[:, feature_index])
            #test each threshold for the current feature
            for threshold in thresholds:
                # Create left and right splits based on the threshold
                left_idxs = X[:, feature_index] < threshold
                right_idxs = ~left_idxs

                # If either split is empty, skip this threshold
                if len(y[left_idxs]) == 0 or len(y[right_idxs]) == 0:
                    continue

                # Calculate the Gini gain from this split
                gain = self._gini_gain(y, y[left_idxs], y[right_idxs])

                # If this gain is better than the best found so far, update best values
                if gain > best_gain:
                    best_gain = gain
                    best_feat = feature_index
                    best_thresh = threshold

        return best_feat, best_thresh

This method evaluates each possible split and chooses the one that produces the largest reduction in impurity. While this approach is very computationally expensive by testing all option, it ensures that the split chosen is optimal for the current node.

The impurity of a set and the gain from splitting it are calculated using _gini() and _gini_gain():

   """ Calculates the Gini impurity for a set of labels (y). """
    def _gini(self, y):
        counts = np.bincount(y) # Count occurrences of each class label
        probs = counts / len(y) # Calculate probabilities of each class
        return 1 - np.sum(probs ** 2) #gini formula

    """ Calculates the Gini gain from a split. How much the Gini impurity is reduced by splitting the data from parent to child. """
    def _gini_gain(self, parent, left, right):
        weight_left = len(left) / len(parent) #proportion of samples in left split
        weight_right = len(right) / len(parent) #proportion of samples in right split
        return self._gini(parent) - (weight_left * self._gini(left) + weight_right * self._gini(right))

The Gini impurity measures how mixed the classes are in a node, and the gain measures how much a split reduces impurity, weighted by the size of the child nodes.

Once the tree is trained, predictions are made by starting at the root and following split conditions down to a leaf. This is handled by predict() and _traverse_tree():

    """ Predicts the class labels for a set of samples. Uses the trained tree to make predictions. """
    def predict(self, X): # X is a 2D NumPy array of samples, collects predicitions to compare with true labels
        return np.array([self._traverse_tree(x, self.root) for x in X])

    """ Traverses the tree to make a prediction for a single sample for the predict fucntion. """
    def _traverse_tree(self, x, node):
        if node.is_leaf_node():  # If it's a leaf node, return the class 
            return node.value
        if x[node.feature] < node.threshold: # if the feature value is less than the threshold, go left
            return self._traverse_tree(x, node.left)
        else: # if the feature value is greater than or equal to the threshold, go right
            return self._traverse_tree(x, node.right)

For each sample, the traversal logic checks the relevant feature against the node’s threshold, then moves left or right accordingly until a leaf is reached. The label stored at that leaf becomes the prediction. This is helpful for calculating the accuracy score using the built in sci-kit learn tool.

This from-scratch CART implementation mirrors the theoretical process of decision tree construction: recursively partitioning the feature space to maximize class separation at each step. It also made the algorithm’s trade-offs more tangible for me to understand. For example, the impact of maximum depth, number of features, and the computational cost of evaluating all possible thresholds.

Empirical Analysis

To evaluate the performance of the Decision Tree classification algorithm, I conducted experiments using three datasets from Kaggle: a Mushroom dataset (~8,000 samples, 23 features) ¹⁵, a Iris dataset (100,000 samples, 4 features) ¹⁶, and a clinical diabetes dataset (100,000, 16 features) ¹⁷. The classification tasks involved predicting whether a mushroom is edible or poisonous, identifying an iris species, and determining whether an individual has diabetes. This section provides empirical results of runtime behavior across varying sample sizes and different CART implmentations, highlights scalability trends, and supports the algorithm's theoretical $O(n \cdot \log(n))$ time complexity. I also report classification accuracy using Python’s built-in accuracy_score function to assess model effectiveness.

All data used to make the following graphs is in the attached excel workbook.

Final Research Paper Workbook

Small-n Runtime Behavior

To evaluate the time complexity of the Decision Tree algorithm, I measured training time as the number of input samples increased across three datasets. The first set of graphs focus on smaller sample sizes (n ≤ 8000), highlighting early runtime behavior and variability between datasets.

This graph shows the small-n runtime behavior (n ≤ 8000) for the scikit-learn implementation. All three datasets exhibit roughly linear scaling in this range, with the Iris dataset consistently training the fastest due to its low feature count of 4. The Mushroom and Diabetes datasets take slightly longer, with the Diabetes dataset showing a steady increase in runtime proportional to n, likely due to its higher dimensionality of 16 features. Minor fluctuations in the curves can be attributed to system variability and caching effects at small sample sizes.

This graph also shows runtime behavior for small-n, but for the custom CART implementation. Compared to scikit-learn, the custom algorithm exhibits significantly higher runtimes, especially for the Diabetes dataset, which grows rapidly even at small n due to its 16 features and less optimized split-finding method. The Iris and Mushroom datasets remain much faster, with runtimes under 0.5 seconds, though still slower than the scikit-learn implementation. The pronounced spikes and variability in the Diabetes curve suggest additional overhead from repeated feature evaluations and lack of algorithmic optimizations present in scikit-learn.

Large-n Runtime Behavior

The second graph extends this analysis to larger datasets (up to 100,000 samples) using the Iris and Diabetes data to examine scalability and validate the expected quasi-linear growth pattern of $O(n \cdot log n)$.

This graph shows the runtime behavior for large input sizes up to 100,000 samples, using the scikit-learn CART implementation. Both datasets show smooth, predictable increases in runtime, with the Diabetes dataset increasing more steeply because it has more features (16) compared to Iris (4). Even at the largest input size, runtimes stay under one second, showing that the scikit-learn version is highly efficient and scales well.

This graph also shows the runtime behavior for large input sizes, but using the custom CART implementation. The Iris dataset remains consistently low in runtime due to having only four features, but the Diabetes dataset increases sharply, exceeding 50 seconds at the largest input size. This steep growth reflects the less optimized splitting strategy in the custom implementation, which becomes significantly slower as the number of features and samples increases.

Implmentation Comparision: Scikit learn vs Custom

The following figures compare the runtime performance of the same dataset when processed with two different implementations of the CART algorithm: Scikit-learn’s optimized version and a custom implementation. These side-by-side results illustrate the significant difference in scalability and execution time, particularly as input sizes grow.

For the Iris dataset, both algorithms show increasing runtime as the number of samples grows, but the custom CART is consistently slower. While Scikit-learn processes 100,000 samples in under 0.25 seconds, the custom implementation takes over 2.5 seconds, indicating significantly less efficient scaling.

The performance gap is even more pronounced with the Diabetes dataset. Scikit-learn completes training in under 1 second for the largest input size, whereas the custom CART exceeds 55 seconds. This suggests that the custom algorithm has much higher computational overhead and does not scale efficiently for larger datasets.

Runtime Complexity: Measured vs. Theoretical Growth

To compare measured runtimes against theoretical growth rates, I plotted execution times for both implementations alongside $O(n log n)$ and $O(n^2)$ trendlines. These plots give a visual sense of how the algorithms scale as input size increases. For both the Scikit-learn and custom CART implementations, the measured data follows a path that could reasonably match either $O(n log n)$ or $O(n^2)$ over parts of the range, especially at larger input sizes.

The measured runtimes (blue) fall between the $O(n^2)$ (orange) and $O(n log n)$ (green) curves, following $O(n log n)$ more closely in the midrange but converging toward $O(n^2)$ at higher $n$. This suggests the growth rate is not purely quadratic or logarithmic-linear, likely due to implementation-specific overhead in functions like best_split.

The measured runtimes (blue) also track between $O(n log n)$ (green) and $O(n^2)$ (orange), leaning more toward $O(n log n)$ for most input sizes but showing slight deviations as $n$ increases. While the scaling efficiency is strong, the results do not perfectly match a single complexity class, likely due to real-world optimizations and dataset characteristics.

When plotting the theoretical $O(n log n)$ and $O(n^2)$ trendlines, the constant factor was calculated using the runtime at n = 100,000. This means the curves are anchored to match performance at that single point, which can skew their fit for smaller input sizes. As a result, the trendlines may not perfectly represent scaling behavior across the full range of $n$, especially if runtime growth is affected by fixed overhead or other factors not captured in the model.

Ratio Table

However, visual trendlines can be misleading, as both curves can look similar depending on the scale. To get a clearer answer, I created ratio tables by dividing the measured time by $n^2$ and by $n log n$ for each dataset. If the ratio stays relatively constant for one complexity, it suggests that complexity is the better fit. For Scikit-learn, the (time / n log n) ratio stayed more stable than the (time / n^2) ratio, which points to growth closer to $O(n log n)$. The custom CART ratios were also more consistent for $O(n log n)$, despite having much higher runtimes due to the unoptimized best_split function scanning every possible threshold.

Ratio Table Diabetes Dataset: Scikit Learn implmentation

$n$	Seconds	Time / $n^2$	Time / $(n log n)$
500	0.0045	1.80E-08	1.00E-06
1000	0.0065	6.50E-09	6.52E-07
2000	0.0080	2.00E-09	3.65E-07
5000	0.0198	7.92E-10	3.22E-07
10000	0.0363	3.63E-10	2.73E-07
15000	0.0535	2.38E-10	2.57E-07
20000	0.0724	1.81E-10	2.53E-07
30000	0.1262	1.40E-10	2.83E-07
40000	0.1866	1.17E-10	3.05E-07
50000	0.2864	1.15E-10	3.67E-07
60000	0.3175	8.82E-11	3.33E-07
70000	0.4056	8.28E-11	3.60E-07
80000	0.5502	8.60E-11	4.22E-07
90000	0.6943	8.57E-11	4.69E-07
100000	0.8698	8.70E-11	5.24E-07

In this table for the Scikit-Learn implementation the (Time / (n log n)) column stays relatively consistent across different input sizes, suggesting that the observed performance aligns more closely with $n log n$ complexity. In contrast, the (Time / $n^2$) column drops sharply as $n$ increases, indicating that quadratic growth is not as good of a fit. This analysis supports the expectation that Scikit-Learn’s optimized decision tree implementation achieves near $n log n$ scaling, even on a dataset with 16 features such as the diabetes dataset.

Ratio Table Diabetes Dataset: custom CART implmentation

$n$	Seconds	Time / $n^2$	Time / $(n log n)$
500	0.2504	1.00E-06	5.57E-05
1000	0.4579	4.58E-07	4.59E-05
2000	0.6490	1.62E-07	2.96E-05
5000	1.7008	6.80E-08	2.77E-05
10000	3.5840	3.58E-08	2.70E-05
15000	5.8500	2.60E-08	2.81E-05
20000	7.5700	1.89E-08	2.64E-05
30000	11.0500	1.23E-08	2.48E-05
40000	16.9500	1.06E-08	2.77E-05
50000	23.2300	9.29E-09	2.98E-05
60000	29.7400	8.26E-09	3.12E-05
70000	37.0400	7.56E-09	3.28E-05
80000	44.8000	7.00E-09	3.43E-05
90000	45.3390	5.59E-09	3.06E-05
100000	55.5700	5.56E-09	3.35E-05

In this ratio table for the custom CART implementation, it shows a similar trend compared to the Scikit-Learn table. The (time / $(n log n)$ column stays relatively flat across increasing input sizes, which suggests the runtime is growing more closely with $n log n$ complexity. The (time / $( n^2)$) column decreases steadily, meaning the performance does not match the growth of quadratic complexity. You can also see the runtime in seconds which supports the observation that the exhaustive threshold scanning in the best_split function introduces significant overhead, making the algorithm scale worse on larger datasets.

Accuracy Score

In this analysis, I used the accuracy_score function from the scikit-learn library to evaluate the performance of the CART algorithm. This function calculates the ratio of correct predictions to the total number of predictions made, basically it measures how often the classifier was right. The score ranges from 0 to 1.0, where 1.0 represents perfect accuracy, values above 0.90 are considered great, 0.80–0.89 good, and anything below 0.70 often indicates poor performance.

Because the same accuracy_score function was applied to predictions from both the scikit-learn CART and the custom CART implementations, and both were designed to use the same splitting criteria, the accuracy results were nearly identical across datasets. Any small differences would stem from variations in implementation details (such as handling of ties or stopping conditions) rather than from the scoring method itself.

Several factors can influence a decision tree’s accuracy, including the quality and relevance of features, the balance of class labels, the size of the dataset, and tree depth. Since the datasets used in this project are relatively balanced and vary in size and feature count, accuracy served as a reliable and interpretable metric for comparing model performance across sample sizes. ¹⁹

This graph displays classification accuracy as input size increases up to 100,000 samples for the diabetes and iris datasets. Accuracy for both models stabilizes at larger sample sizes, with the diabetes classifier maintaining strong performance around 94–95%, and the iris classifier settling near 91%. The initial volatility smooths out as the model sees more data, indicating better generalization and reduced sensitivity to training variation. These results support the idea that Decision Trees benefit from larger datasets, particularly when working with more complex or less separable features like those in the iris dataset.

This graph shows classification accuracy for the custom CART implementation as input size grows to 100,000 samples. The diabetes dataset consistently achieves high accuracy between 96–97% across all sample sizes, showing minimal variation after the initial increase. The iris dataset stabilizes around 93–94%, slightly outperforming the scikit-learn implementation for the same task. These results indicate that while the custom CART implementation matches or exceeds the accuracy levels of the optimized library version, the primary trade-off lies in the significantly longer runtimes observed in earlier runtime comparisons.

Across both implementations, classification accuracy remains high and stable once sample sizes reach the upper range, with only minor fluctuations. The custom CART generally matches or slightly exceeds the accuracy of scikit-learn’s implementation, particularly for the iris dataset. However, given the substantial runtime differences observed earlier, the marginal accuracy gains from the custom approach may not justify the performance cost for large-scale applications. These findings highlight a common trade-off in algorithm design between execution efficiency and potential accuracy improvements.

Summary

This project focused on implementing and analyzing the CART Decision Tree algorithm, a foundational supervised machine learning method used for both classification and regression tasks. I chose this topic because of its widespread use in machine learning and scientific research, as well as my interest in understanding its inner workings. My goal was to explore how decision trees operate internally,specifically, how they use impurity measures to determine optimal splits and to evaluate their performance across different datasets. To do this, I implemented two versions of the model in Python: one using the scikit-learn library, which provided a clear and accessible baseline, and another custom implementation of the CART algorithm built from scratch. I then tested both models on three Kaggle datasets: mushroom, iris, and diabetes. They varied in sample size and feature complexity to compare their behavior and performance.

For smaller input sizes (n ≤ 8,000), both implementations showed relatively modest runtimes, though my custom CART was noticeably slower, especially on datasets with more features and complex decision boundaries. This difference became much more pronounced in the large-n experiments (n up to 100,000), where scikit-learn maintained sub-second runtimes for most cases, while my custom implementation scaled poorly reaching over 50 seconds for the largest diabetes dataset. The main bottleneck appears to be in my best_split function, which exhaustively scanned all thresholds for every feature at each node. While correct in functionality, this approach has high computational overhead compared to scikit-learn’s optimized methods.

Although decision tree training is theoretically $O(n log n)$, my results suggest mixed scaling behavior. The ratio tables showed relatively stable values for time/(n log n) in smaller and mid-sized datasets, which points toward near $O(n log n)$ growth in that range. However, in the large-n experiments, the runtime curves shifted toward a more quadratic like pattern, likely caused by the cumulative effect of threshold scanning overhead in my implementation. Additionally, the theoretical curves in the trendline graphs were anchored using the runtime at n = 100,000 to calculate constant factors, which can skew how well they fit smaller input sizes making the exact complexity classification less certain.

The datasets themselves represented different levels of complexity. The mushroom dataset, though large in the small-n experiments, is relatively simple in structure, leading to consistently high accuracy. The iris dataset has fewer features but presents overlapping class boundaries, making classification more challenging. The diabetes dataset, with its higher dimensionality and mixed feature types, proved the most computationally expensive for my custom CART, highlighting how feature count and complexity can strongly influence training time.

Accuracy results showed that both implementations performed well overall, with minimal differences between scikit-learn and my custom CART. This was expected, as both followed the same decision tree logic, used identical stopping conditions, and were evaluated using the same accuracy_score function. In both small-n and large-n settings, accuracy stabilized quickly after initial fluctuations, with the diabetes dataset consistently around 94–96% and iris between 90–92%, reflecting the impact of dataset separability and feature quality on model performance.

Beyond the empirical results, this project was my introduction to implementing a machine learning algorithm from scratch. I developed a much deeper understanding of the CART decision-making process, particularly how impurity measures drive feature selection and how computational trade-offs emerge from design choices. I improved my proficiency with Python libraries such as pandas, NumPy, Matplotlib, and scikit-learn, while also learning how to adapt to multiple dataset formats and feature types. I also learned the value of performance benchmarking to identify bottlenecks and how real-world implementations optimize these steps. Moving forward, I plan to refine my CART implementation by reducing threshold scanning overhead, exploring sorting-based split selection, and experimenting with pruning methods to improve both runtime efficiency and generalization.

References

Footnotes

1. GeeksforGeeks. Supervised Machine Learning. GeeksforGeeks. Retrieved from https://www.geeksforgeeks.org/machine-learning/supervised-machine-learning/ ↩

2. IBM. 2023. What is a Decision Tree? IBM. https://www.ibm.com/think/topics/decision-trees (accessed July 25, 2025). ↩ ↩²

3. Quinlan, J.R. 1986. Induction of decision trees. Machine Learning, 1(1), 81-106. Springer. DOI: 10.1007/BF00116251. ↩ ↩² ↩³

4. Breiman, L., Friedman, J.H., Olshen, R.A., and Stone, C.J. 1986. Classification and regression trees. Wadsworth & Brooks/Cole. ISBN 0-534-98099-8. ↩ ↩² ↩³ ↩⁴

5. Quinlan, J.R. 1993. C4.5: Programs for machine learning. Morgan Kaufmann Publishers. ISBN: 1-55860-238-0. ↩ ↩²

6. Breiman, L. 2001. Random forests. Machine Learning, 45(1), 5-32. DOI: 10.1023/A:1010933404324. ↩ ↩²

7. Hunt, E.B., Marin, J., & Stone, P.J. 1966. Experiments in Inductive Inference. Psychological Review, 73(3), 131-161. https://sso.apa.org/apasso/idm/login?CheckAccess=1&UID=1966-12300-001&ERIGHTS_TARGET=https%3A%2F%2Fpsycnet.apa.org%2FdoiLanding%3Fdoi%3D10.1037%252Fh0023706 ↩

8. Meshram, S. and Naik, D. 2023. Review on Decision Tree Algorithm in Healthcare Applications. International Journal of Advanced Research in Computer and Communication Engineering. https://www.researchgate.net/publication/382748363 ↩

9. Alirezaei, M., Asadi, M., and Azizi, M. 2022. Decision Tree Applications in Energy Policy and Planning: A Review. Energies 15, 7 (2022), 2420. DOI: 10.3390/en15072420. ↩

10. Sharma, S. and Singh, A. 2024. Interpretable Machine Learning Techniques: A Systematic Review with a Focus on Decision Trees. Applied Sciences 14, 19 (2024), 8884. DOI: 10.3390/app14198884 ↩

11. H. Lu and X. Ma. 2020. Hybrid decision tree-based models for short-term water quality prediction. Chemosphere 248 (2020), 125988. DOI: https://doi.org/10.1016/j.chemosphere.2020.125988 ↩

12. A. Elhazmi, M. Alshehri, A. Almutairi, A. Alsalemi, G. Almekhlafi, A. Alamri, A. Alharthi, M. Alfayez, et al. 2022. Predicting mortality in critically ill COVID-19 patients using decision tree models: Multicenter cohort study. Journal of Infection and Public Health 15, 6 (2022), 654–661. DOI: https://doi.org/10.1016/j.jiph.2022.03.003 ↩

13. S. Hajihosseinlou, O. Asghari, and H. Shirvani. 2023. Application of Light Gradient Boosting Machine (LightGBM) in prospectivity modeling of Mississippi Valley-type Pb–Zn deposits in the Varcheh district, Iran. Natural Resources Research 32, 1 (2023), 487–506. DOI: https://doi.org/10.1007/s11053-022-10007-7 ↩

14. GeeksforGeeks. 2023. CART (Classification and Regression Tree) in Machine Learning. GeeksforGeeks. https://www.geeksforgeeks.org/machine-learning/cart-classification-and-regression-tree-in-machine-learning/ (accessed Aug. 4, 2025). ↩

15. UCI Machine Learning Repository (UCIML). 2025. Mushroom Classification Dataset. Kaggle. Retrieved August 6, 2025 from https://www.kaggle.com/datasets/uciml/mushroom-classification ↩ ↩²

16. Ifeanyi Idiaye. 2024. Scaled Iris Dataset – 100k Rows. Kaggle. Retrieved August 6, 2025 from https://www.kaggle.com/datasets/idiaye/scaled-iris-dataset-100k-rows ↩ ↩²

17. Priyam Choksi. 2024. Comprehensive Diabetes Clinical Dataset (100 k rows). Kaggle. Retrieved August 6, 2025 from https://www.kaggle.com/datasets/priyamchoksi/100000-diabetes-clinical-dataset ↩ ↩²

18. GeeksforGeeks. 2025. Implementing CART (Classification And Regression Tree) in Python. GeeksforGeeks Article. Retrieved August 11, 2025, from https://www.geeksforgeeks.org/machine-learning/implementing-cart-classification-and-regression-tree-in-python/ ↩ ↩²

19. GeeksforGeeks. 2022. Scikit-learn: Classification Metrics. GeeksforGeeks. Retrieved August 6, 2025 from https://www.geeksforgeeks.org/machine-learning/sklearn-classification-metrics/ ↩ ↩²

20. Egazakharenko, E. 2024. Decision Tree (CART) from Scratch: Full Tutorial. Kaggle Notebook. Retrieved August 11, 2025, from https://www.kaggle.com/code/egazakharenko/decision-tree-cart-from-scratch-full-tutorial ↩