Building a Decision Tree From Scratch — Understanding the Internal Working of it

In the third installment of his 'ML from scratch' series, the author builds a decision tree classifier using only NumPy, explaining the internal workings from concept to code. The algorithm recursively splits data by selecting the feature-threshold pair that maximizes information gain, measured via entropy reduction, until groups are pure or further splitting is unjustified. The post includes worked examples of entropy and information gain calculations, along with Python implementations.

This is the third entry in my “ML from scratch” series, after KNN and Gaussian Naive Bayes. This time: a decision tree classifier, built with nothing but NumPy, broken down from the concept all the way to individual lines of code. A decision tree is a model that makes predictions by asking a sequence of yes/no questions about the input’s features. Each question narrows down the possibilities until you arrive at an answer. Structurally, it’s a binary tree: To classify a new sample, you start at the root, answer the question at each node, follow the corresponding branch left if true, right if false , and repeat until you land on a leaf. Whatever label that leaf holds is the prediction. That’s it structurally. The interesting part — and the part that actually needs an algorithm — is how the tree decides which questions to ask, and in what order. Training a decision tree means building this tree of questions from data, one node at a time, top-down. At the root, you have your entire training set, with a mix of classes. The goal is to find one question — one feature, threshold pair — that splits the data into two groups that are, as much as possible, more homogeneous than the group you started with. Ideally, one side ends up mostly class A, the other mostly class B. Once you’ve picked that first question and split the data, you don’t stop — you treat each of the two resulting groups as its own smaller problem, and repeat the same process on each: find the best question to split that group further. This continues recursively, each split producing two more smaller groups to potentially split again. The recursion stops when further splitting stops making sense — a group is already pure all one class , you’ve split enough times already, or there aren’t enough samples left to justify splitting further. At that point, the group becomes a leaf, and the leaf’s prediction is simply the majority class within it. So the whole algorithm is really just two ideas layered together: Everything else is implementation detail. The next section covers idea 1 — how “good” gets defined mathematically. To score a split, we need a way to measure how mixed up impure a set of labels is — and how much a candidate split reduces that impurity. Decision trees commonly use entropy for the first part and information gain for the second. Entropy measures the disorder in a set of labels: E S = -Σ p x · log p x Where p x is the proportion of class x in set S, summed over all classes present. Worked example. A node with 10 samples: 6 of class 0, 4 of class 1. p 0 = 6/10 = 0.6p 1 = 4/10 = 0.4 E = - 0.6 · log 0.6 + 0.4 · log 0.4 = - 0.6 · -0.511 + 0.4 · -0.916 = - -0.3065 + -0.3665 = 0.673 Compare that to a pure node — 10 samples, all class 0: p 0 = 1.0E = - 1.0 · log 1.0 = - 1.0 · 0 = 0 Entropy of 0 means no disorder at all — nothing left to gain from splitting further. Entropy is at its maximum when classes are perfectly balanced, and shrinks toward 0 as one class comes to dominate the set. In code: python def entropy self, y : hist = np.bincount y ps = hist / len y return -np.sum p np.log p for p in ps if p 0 Entropy alone tells you how mixed a single set is. To evaluate a split , you compare the parent’s entropy against a weighted average of the two children’s entropy: IG = E parent - n left/n · E left + n right/n · E right Weighting by n left/n and n right/n matters: a split that carves off a large, pure group and leaves a small, mixed remainder should score differently than one that produces two medium, moderately-mixed groups. Weighting by size accounts for that. Worked example , continuing the 10-sample node parent entropy E = 0.673 . Suppose a candidate split sends 5 samples left all class 0 and 5 right 1 class-0, 4 class-1 : E left = 0 pure E right = - 0.2·log 0.2 + 0.8·log 0.8 = - 0.2· -1.609 + 0.8· -0.223 = - -0.322 + -0.179 = 0.500 Weighted child entropy = 5/10 ·0 + 5/10 ·0.500 = 0.250 IG = 0.673 - 0.250 = 0.423 That’s a strong split — it fully isolated a pure group. A weak split, where the class ratio barely changes on either side, produces an IG close to 0. In code: python def information gain self, y, X column, threshold : parent entropy = self. entropy y left idxs, right idxs = self. split X column, threshold if len left idxs == 0 or len right idxs == 0: return 0 n = len y n l, n r = len left idxs , len right idxs e l, e r = self. entropy y left idxs , self. entropy y right idxs child entropy = n l/n e l + n r/n e r return parent entropy - child entropy With a way to score any single candidate split, finding the best split at a node is a search: try every feature, and for each feature, try every value that appears in that feature’s column as a candidate threshold, keeping whichever feature, threshold pair produced the highest information gain. best split X, y = argmax over all feature, threshold of IG y, X :, feature , threshold Only unique observed values need to be tried as thresholds — any value strictly between two consecutive observed values produces an identical split, so there’s no benefit to checking a finer-grained range. python class Node: def init self, feature=None, threshold=None, left=None, right=None, , value=None : self.feature = feature self.threshold = threshold self.right = right self.left = left self.value = value python def is leaf node self : return self.value is not None Node is deliberately dual-purpose — the same class represents both internal nodes and leaves, distinguished only by which fields are set: value is keyword-only the forces this specifically so it can't be passed positionally by accident and confused with left/right — leaves and internal nodes are constructed with visually distinct calls: Node value=leaf value vs. Node best feature, best threshold, left, right . is leaf node checks self.value is not None — which works because internal nodes never set value, and leaves never set anything else. This one check is what predict uses to decide whether to stop traversing or keep going. python def init self, min samples split=2, max depth=100, n features=None : self.min samples split = min samples split self.max depth = max depth self.n features = n features self.root = None Three hyperparameters, all controlling when the tree stops growing directly or indirectly , plus self.root, which starts empty and gets filled in by fit. python def fit self, X, y : self.n features = X.shape 1 if not self.n features else min X.shape 1 , self.n features self.root = self.grow tree X, y The entry point. The first line resolves n features into an actual number: if none was specified, use every feature in X; if one was specified, use whichever is smaller — the requested count or the number of features actually available so you can't accidentally ask for more features than exist . The second line kicks off recursive tree-building and stores the resulting root node. python def grow tree self, X, y, depth=0 : n samples, n feats = X.shape n labels = len np.unique y if depth = self.max depth or n labels == 1 or n samples < self.min samples split: leaf value = self.most common label y return Node value=leaf value feat idxs = np.random.choice n feats, self.n features, replace=False best feature, best threshold = self.best split X, y, feat idxs left idxs, right idxs = self. split X :, best feature , best threshold left = self.grow tree X left idxs, : , y left idxs , depth + 1 right = self.grow tree X right idxs, : , y right idxs , depth + 1 return Node best feature, best threshold, left, right Each call handles one node, given the slice of data X, y that reached it and how deep it is depth . Stopping check first. The if condition covers the three ways a node becomes a leaf: it's too deep depth = max depth , it's already pure n labels == 1 , or it has too few samples to keep splitting n samples < min samples split . If any is true, skip straight to most common label y and return a leaf — no point searching for a split that won't be used. Otherwise, split and recurse. np.random.choice n feats, self.n features, replace=False picks which features this node is even allowed to consider — all of them by default, a random subset if n features was restricted. best split searches those features for the best feature, threshold pair. split then partitions the actual data into left idxs/right idxs based on that choice. The two recursive calls — self.grow tree X left idxs, : , y left idxs , depth + 1 and the equivalent for right — are where the "repeat the whole process on each smaller group" idea from earlier actually happens in code. Each call returns a fully built subtree root node of that subtree , and the final line wires both of those subtrees into a new internal Node, which is what gets returned up to this call's caller. That's how depth-first construction bubbles all the way back up to a single root. python def best split self, X, y, feat idxs : best gain = -1 split idx, split threshold = None, None for feat idx in feat idxs: X column = X :, feat idx thresholds = np.unique X column for thr in thresholds: gain = self. information gain y, X column, thr if gain best gain: best gain = gain split idx = feat idx split threshold = thr return split idx, split threshold A brute-force search, directly implementing the argmax from the methodology section. The outer loop goes feature by feature; the inner loop goes threshold by threshold every unique value observed in that feature's column . For every feature, threshold pair, information gain scores it, and best gain/split idx/split threshold track the best one seen so far. best gain starts at -1 specifically because information gain is always ≥ 0 — so the very first real split evaluated is guaranteed to beat the initial placeholder and get recorded. python def information gain self, y, X column, threshold : parent entropy = self. entropy y left idxs, right idxs = self. split X column, threshold python def split self, X column, split thresh : left idxs = np.argwhere X column <= split thresh .flatten right idxs = np.argwhere X column split thresh .flatten return left idxs, right idxs These two are the direct code form of the entropy/information-gain formulas covered above — split produces the two index arrays for "at or below the threshold" vs. "above it" using np.argwhere and a boolean comparison; information gain uses those indices to compute each side's entropy and combine them into the weighted score. The one piece of defensive logic — if len left idxs == 0 or len right idxs == 0: return 0 — handles a threshold that doesn't actually separate anything every sample lands on one side , which would otherwise divide by an empty array when computing that side's entropy. python def entropy self, y : hist = np.bincount y ps = hist / len y return -np.sum p np.log p for p in ps if p 0 python def most common label self, y : counter = Counter y return counter.most common 1 0 0 entropy is the formula from the methodology section, translated line for line: np.bincount y counts samples per class, dividing by len y turns those into proportions, and the list comprehension sums p · log p over every class with p 0 skipping zero-count classes, since log 0 is undefined and they contribute nothing anyway . most common label is what a leaf actually predicts: Counter y .most common 1 returns the single most frequent label in y as a label, count tuple, and 0 0 pulls out just the label. python def predict self, X : return np.array self. traverse tree x, self.root for x in X python def traverse tree self, x, node : if node.is leaf node : return node.value if x node.feature <= node.threshold: return self. traverse tree x, node.left return self. traverse tree x, node.right predict just runs traverse tree on every row of X and collects the results into an array. traverse tree is the inference-time mirror of the "start at the root, answer the question, follow the branch" description from the intro: check if the current node is a leaf if so, return its stored label — done ; otherwise, compare x node.feature against node.threshold and recurse into node.left or node.right accordingly. No computation happens here — training already decided every question in advance, so prediction is pure traversal, taking O depth steps per sample regardless of how large the training set was. Trained and evaluated on sklearn.datasets.load breast cancer 80/20 split, random state=1234, default hyperparameters : Accuracy: 94% That’s competitive with sklearn’s own DecisionTreeClassifier on the same split — expected, since the underlying math is identical. sklearn's version is faster thanks to more optimized split-finding, and supports additional criteria Gini impurity and pruning options this implementation doesn't. To go beyond the raw accuracy number, I added a few visualizations: a confusion matrix to see where the errors landed, a feature-importance chart based on how often each feature was used to split which features the tree actually relied on , and a PCA projection of the test set colored by correct vs. incorrect predictions, to check whether misclassifications clustered in any particular region of the data. The natural extension from here is a Random Forest — since n features subsampling is already built in, most of the ensemble machinery is really just: train many of these trees on bootstrapped samples of the data, and aggregate their predictions by majority vote. That's next in this series. Complete Code of Decision Tree implementation is available on my GitHub. GitHub link — https://github.com/Archan47/Machine-Learning-Algorithms-From-Scratch https://github.com/Archan47/Machine-Learning-Algorithms-From-Scratch Code for this and the rest of the “ML from scratch” series is on GitHub. Building a Decision Tree From Scratch — Understanding the Internal Working of it https://pub.towardsai.net/building-a-decision-tree-from-scratch-understanding-the-internal-working-of-it-abd23e06dc6e was originally published in Towards AI https://pub.towardsai.net on Medium, where people are continuing the conversation by highlighting and responding to this story.