4
Predicting Online Ad Click-Through with Tree-Based Algorithms
We built a face image classifier in the previous chapter. In this chapter and the next, we will be solving one of the most data-driven problems in digital advertising: ad click-through prediction—given a user and the page they are visiting, this predicts how likely it is that they will click on a given ad. We will focus on learning tree-based algorithms (including decision tree, random forest, and boosted trees) and utilize them to tackle this billion-dollar problem. We will be exploring decision trees from the root to the leaves, as well as the aggregated version, a forest of trees. This won't be a theory-only chapter, as there are a lot of hand calculations and implementations of tree models from scratch included. We will be using scikit-learn and XGBoost, a popular Python package for tree-based algorithms.
We will cover the following topics in this chapter:
- Two types of features: numerical and categorical
- The mechanics of a decision tree classifier
- The implementation of decision tree
- Ad click-through predictions
- The ensemble method and bagging technique
- The mechanics of random forest
- Click-through predictions with random forest
- The gradient boosted trees (GBT) model
- The implementation of GBT using XGBoost
A brief overview of ad click-through prediction
Online display advertising is a multibillion-dollar industry. It comes in different formats, including banner ads composed of text, images, and flash, and rich media such as audio and video. Advertisers, or their agencies, place ads on a variety of websites, and even mobile apps, across the Internet in order to reach potential customers and deliver an advertising message.
Online display advertising has served as one of the greatest examples of machine learning utilization. Obviously, advertisers and consumers are keenly interested in well-targeted ads. In the last 20 years, the industry has relied heavily on the ability of machine learning models to predict the effectiveness of ad targeting: how likely it is that an audience of a certain age group will be interested in this product, that customers with a certain household income will purchase this product after seeing the ad, that frequent sports site visitors will spend more time reading this ad, and so on. The most common measurement of effectiveness is the click-through rate (CTR), which is the ratio of clicks on a specific ad to its total number of views. The higher the CTR in general, the better targeted an ad is, and the more successful an online advertising campaign is.
Click-through prediction entails both the promises and challenges of machine learning. It mainly involves the binary classification of whether a given ad on a given page (or app) will be clicked on by a given user, with predictive features from the following three aspects:
- Ad content and information (category, position, text, format, and so on)
- Page content and publisher information (category, context, domain, and so on)
- User information (age, gender, location, income, interests, search history, browsing history, device, and so on)
Suppose we, as an agency, are operating ads on behalf of several advertisers, and our job is to place the right ads for the right audience. Let's say that we have an existing dataset in hand (the following small chunk is an example; the number of predictive features can easily go into the thousands in reality) taken from millions of records of campaigns run a month ago, and we need to develop a classification model to learn and predict future ad placement outcomes:
Figure 4.1: Ad samples for training and prediction
As you can see in Figure 4.1, the features are mostly categorical. In fact, data can be either numerical or categorical. Let's explore this in more detail in the next section.
Getting started with two types of data – numerical and categorical
At first glance, the features in the preceding dataset are categorical, for example, male or female, one of four age groups, one of the predefined site categories, or whether the user is interested in sports. Such data is different from the numerical feature data we have worked with until now.
Categorical (also called qualitative) features represent characteristics, distinct groups, and a countable number of options. Categorical features may or may not have a logical order. For example, household income from low to medium to high is an ordinal feature, while the category of an ad is not ordinal.
Numerical (also called quantitative) features, on the other hand, have mathematical meaning as a measurement and, of course, are ordered. For instance, term frequency and the tf-idf variant are discrete and continuous numerical features, respectively; the cardiotocography dataset (https://archive.ics.uci.edu/ml/datasets/Cardiotocography) from the last chapter contains both discrete (such as the number of accelerations per second or the number of fetal movements per second) and continuous (such as the mean value of long-term variability) numerical features.
Categorical features can also take on numerical values. For example, 1 to 12 can represent months of the year, and 1 and 0 can indicate male and female. Still, these values do not have mathematical implications.
Of the two classification algorithms that you learned previously, Naïve Bayes and SVM, the Naïve Bayes classifier works for both numerical and categorical features as the likelihoods, P(x | y) or P(feature | class), are calculated in the same way, while SVM requires features to be numerical in order to compute and maximize the distance margins.
Now, we are thinking of predicting click-through using Naïve Bayes and trying to explain the model to our advertising clients. However, our clients may find it difficult to understand the prior and the likelihood of individual attributes and their multiplication. Is there a classifier that is easy to interpret and explain to clients, and that is able to directly handle categorical data? Decision trees are the answer!
Exploring a decision tree from the root to the leaves
A decision tree is a tree-like graph, that is, a sequential diagram illustrating all of the possible decision alternatives and their corresponding outcomes. Starting from the root of a tree, every internal node represents the basis on which a decision is made. Each branch of a node represents how a choice may lead to the next nodes. And, finally, each terminal node, the leaf, represents the outcome produced.
For example, we have just made a couple of decisions that brought us to the point of using a decision tree to solve our advertising problem:
Figure 4.2: Using a decision tree to find the right algorithm
The first condition, or the root, is whether the feature type is numerical or categorical. Ad clickstream data contains mostly categorical features, so it goes to the right branch. In the next node, our work needs to be interpretable by non-technical clients. So, it goes to the right branch and reaches the leaf for choosing the decision tree classifier.
You can also look at paths and see what kinds of problems they can fit in. A decision tree classifier operates in the form of a decision tree. It maps observations to class assignments (symbolized as leaf nodes) through a series of tests (represented as internal nodes) based on feature values and corresponding conditions (represented as branches). In each node, a question regarding the values and characteristics of a feature is asked; depending on the answer to the question, the observations are split into subsets. Sequential tests are conducted until a conclusion about the observations' target label is reached. The paths from the root to the end leaves represent the decision-making process and the classification rules.
In a more simplified scenario, as shown in Figure 4.3, where we want to predict Click or No click on a self-driven car ad, we can manually construct a decision tree classifier that works for an available dataset. For example, if a user is interested in technology and has a car, they will tend to click on the ad; a person outside of this subset, for instance, a high-income woman, is unlikely to click on the ad. We then use the trained tree to predict two new inputs, whose results are Click and No click, respectively:
Figure 4.3: Predicting Click/No Click with a trained decision tree
After a decision tree has been constructed, classifying a new sample is straightforward, as you just saw: starting from the root, apply the test condition and follow the branch accordingly until a leaf node is reached, and the class label associated will be assigned to the new sample.
So, how can we build an appropriate decision tree?
Constructing a decision tree
A decision tree is constructed by partitioning the training samples into successive subsets. The partitioning process is repeated in a recursive fashion on each subset. For each partitioning at a node, a condition test is conducted based on the value of a feature of the subset. When the subset shares the same class label, or when no further splitting can improve the class purity of this subset, recursive partitioning on this node is finished.
Theoretically, to partition a feature (numerical or categorical) with n different values, there are n different methods of binary splitting (Yes or No to the condition test, as illustrated in Figure 4.4), not to mention other ways of splitting (for example, three- and four-way splitting in Figure 4.4):
Figure 4.4: Examples of binary splitting and multiway splitting
Without considering the order of features that partitioning is taking place on, there are already nm possible trees for an m-dimensional dataset.
Many algorithms have been developed to efficiently construct an accurate decision tree. Popular ones include the following:
- Iterative Dichotomiser 3 (ID3): This algorithm uses a greedy search in a top-down manner by selecting the best attribute to split the dataset on with each iteration without backtracking.
- C4.5: This is an improved version of ID3 that introduces backtracking. It traverses the constructed tree and replaces the branches with leaf nodes if purity is improved this way.
- Classification and Regression Tree (CART): This constructs the tree using binary splitting, which we will discuss in more detail shortly.
- Chi-squared Automatic Interaction Detector (CHAID): This algorithm is often used in direct marketing. It involves complicated statistical concepts, but basically, it determines the optimal way of merging predictive variables in order to best explain the outcome.
The basic idea of these algorithms is to grow the tree greedily by making a series of local optimizations when choosing the most significant feature to use to partition the data. The dataset is then split based on the optimal value of that feature. We will discuss the measurement of a significant feature and the optimal splitting value of a feature in the next section.
First, we will study the CART algorithm in more detail, and we will implement it as the most notable decision tree algorithm after that. It constructs the tree using binary splitting and grows each node into left and right children. In each partition, it greedily searches for the most significant combination of a feature and its value; all different possible combinations are tried and tested using a measurement function. With the selected feature and value as a splitting point, the algorithm then divides the dataset as follows:
- Samples with the feature of this value (for a categorical feature) or a greater value (for a numerical feature) become the right child
- The remaining samples become the left child
This partitioning process repeats and recursively divides up the input samples into two subgroups. When the dataset becomes unmixed, the splitting process stops at a subgroup where either of the following two criteria is met:
- The minimum number of samples for a new node: When the number of samples is not greater than the minimum number of samples required for a further split, the partitioning stops in order to prevent the tree from excessively tailoring to the training set and, as a result, overfitting.
- The maximum depth of the tree: A node stops growing when its depth, which is defined as the number of partitions taking place from the top down, starting from the root node and ending in a terminal node, is not less than the maximum tree depth. Deeper trees are more specific to the training set and can lead to overfitting.
A node with no branches becomes a leaf, and the dominant class of samples at this node is the prediction. Once all splitting processes finish, the tree is constructed and is portrayed with the assigned labels at the terminal nodes and the splitting points (feature + value) at all the internal nodes above.
We will implement the CART decision tree algorithm from scratch after studying the metrics of selecting the optimal splitting feature and value, as promised.
The metrics for measuring a split
When selecting the best combination of a feature and a value as the splitting point, two criteria, such as Gini Impurity and Information Gain, can be used to measure the quality of separation.
Gini Impurity
Gini Impurity, as its name implies, measures the impurity rate of the class distribution of data points, or the class mixture rate. For a dataset with K classes, suppose that data from class k(1 ≤ k ≤ K) takes up a fraction fk(0 ≤ fk ≤ 1) of the entire dataset; then the Gini Impurity of this dataset is written as follows:
A lower Gini Impurity indicates a purer dataset. For example, when the dataset contains only one class, say, the fraction of this class is 1 and that of the others is 0, its Gini Impurity becomes 1 – (12 + 02) = 0. In another example, a dataset records a large number of coin flips, and heads and tails each take up half of the samples. The Gini Impurity is 1 – (0.52 + 0.52) = 0.5.
In binary cases, Gini Impurity, under different values of the positive class fraction, can be visualized by the following code blocks:
>>> import matplotlib.pyplot as plt
>>> import numpy as np
The fraction of the positive class varies from 0 to 1:
>>> pos_fraction = np.linspace(0.00, 1.00, 1000)
The Gini Impurity is calculated accordingly, followed by the plot of Gini Impurity versus Positive fraction:
>>> gini = 1 – pos_fraction**2 – (1-pos_fraction)**2
Here, 1-pos_fraction is the negative fraction:
>>> plt.plot(pos_fraction, gini)
>>> plt.ylim(0, 1)
>>> plt.xlabel('Positive fraction')
>>> plt.ylabel('Gini Impurity')
>>> plt.show()
Refer to Figure 4.5 for the end result:
Figure 4.5: Gini Impurity versus positive fraction
As you can see, in binary cases, if the positive fraction is 50%, the impurity will be the highest at 0.5; if the positive fraction is 100% or 0%, it will reach 0 impurity.
Given the labels of a dataset, we can implement the Gini Impurity calculation function as follows:
>>> def gini_impurity(labels):
... # When the set is empty, it is also pure
... if not labels:
... return 0
... # Count the occurrences of each label
... counts = np.unique(labels, return_counts=True)[1]
... fractions = counts / float(len(labels))
... return 1 - np.sum(fractions ** 2)
Test it out with some examples:
>>> print(f'{gini_impurity([1, 1, 0, 1, 0]):.4f}')
0.4800
>>> print(f'{gini_impurity([1, 1, 0, 1, 0, 0]):.4f}')
0.5000
>>> print(f'{gini_impurity([1, 1, 1, 1]):.4f}')
0.0000
In order to evaluate the quality of a split, we simply add up the Gini Impurity of all resulting subgroups, combining the proportions of each subgroup as corresponding weight factors. And again, the smaller the weighted sum of the Gini Impurity, the better the split.
Take a look at the following self-driving car ad example. Here, we split the data based on a user's gender and interest in technology, respectively:
Figure 4.6: Splitting the data based on gender or interest in tech
The weighted Gini Impurity of the first split can be calculated as follows:
The second split is as follows:
Therefore, splitting data based on the user's interest in technology is a better strategy than gender.
Information Gain
Another metric, Information Gain, measures the improvement of purity after splitting or, in other words, the reduction of uncertainty due to a split. Higher Information Gain implies better splitting. We obtain the Information Gain of a split by comparing the entropy before and after the split.
Entropy is a probabilistic measure of uncertainty. Given a K-class dataset, and fk (0 ≤ fk ≤ 1) denoted as the fraction of data from class k (1 ≤ k ≤ K), the entropy of the dataset is defined as follows:
Lower entropy implies a purer dataset with less ambiguity. In a perfect case, where the dataset contains only one class, the entropy is 
. In the coin flip example, the entropy becomes 
.
Similarly, we can visualize how entropy changes with different values of the positive class' fraction in binary cases using the following lines of code:
>>> pos_fraction = np.linspace(0.00, 1.00, 1000)
>>> ent = - (pos_fraction * np.log2(pos_fraction) +
... (1 - pos_fraction) * np.log2(1 - pos_fraction))
>>> plt.plot(pos_fraction, ent)
>>> plt.xlabel('Positive fraction')
>>> plt.ylabel('Entropy')
>>> plt.ylim(0, 1)
>>> plt.show()
This will give us the following output:
Figure 4.7: Entropy versus positive fraction
As you can see, in binary cases, if the positive fraction is 50%, the entropy will be the highest at 1; if the positive fraction is 100% or 0%, it will reach 0 entropy.
Given the labels of a dataset, the entropy calculation function can be implemented as follows:
>>> def entropy(labels):
... if not labels:
... return 0
... counts = np.unique(labels, return_counts=True)[1]
... fractions = counts / float(len(labels))
... return - np.sum(fractions * np.log2(fractions))
Test it out with some examples:
>>> print(f'{entropy([1, 1, 0, 1, 0]):.4f}')
0.9710
>>> print(f'{entropy([1, 1, 0, 1, 0, 0]):.4f}')
1.0000
>>> print(f'{entropy([1, 1, 1, 1]):.4f}')
-0.0000
Now that you have fully understood entropy, we can look into how Information Gain measures how much uncertainty was reduced after splitting, which is defined as the difference in entropy before a split (parent) and after a split (children):
Entropy after a split is calculated as the weighted sum of the entropy of each child, which is similar to the weighted Gini Impurity.
During the process of constructing a node at a tree, our goal is to search for the splitting point where the maximum Information Gain is obtained. As the entropy of the parent node is unchanged, we just need to measure the entropy of the resulting children due to a split. The best split is the one with the lowest entropy of its resulting children.
To understand this better, let's look at the self-driving car ad example again.
For the first option, the entropy after the split can be calculated as follows:
The second way of splitting is as follows:
For exploration purposes, we can also calculate the InformationGain by:
According to the Information Gain = entropy-based evaluation, the second split is preferable, which is the conclusion of the Gini Impurity criterion.
In general, the choice of two metrics, Gini Impurity and Information Gain, has little effect on the performance of the trained decision tree. They both measure the weighted impurity of the children after a split. We can combine them into one function to calculate the weighted impurity:
>>> criterion_function = {'gini': gini_impurity,
... 'entropy': entropy}
>>> def weighted_impurity(groups, criterion='gini'):
... """
... Calculate weighted impurity of children after a split
... @param groups: list of children, and a child consists a
... list of class labels
... @param criterion: metric to measure the quality of a split,
... 'gini' for Gini Impurity or 'entropy' for
... Information Gain
... @return: float, weighted impurity
... """
... total = sum(len(group) for group in groups)
... weighted_sum = 0.0
... for group in groups:
... weighted_sum += len(group) / float(total) *
... criterion_function[criterion](group)
... return weighted_sum
Test it with the example we just hand-calculated, as follows:
>>> children_1 = [[1, 0, 1], [0, 1]]
>>> children_2 = [[1, 1], [0, 0, 1]]
>>> print(f"Entropy of #1 split: {weighted_impurity(children_1,
... 'entropy'):.4f}")
Entropy of #1 split: 0.9510
>>> print(f"Entropy of #2 split: {weighted_impurity(children_2,
... 'entropy'):.4f}")
Entropy of #2 split: 0.5510
Now that you have a solid understanding of partitioning evaluation metrics, let's implement the CART tree algorithm from scratch in the next section.
Implementing a decision tree from scratch
We develop the CART tree algorithm by hand on a toy dataset as follows:
Figure 4.8: An example of ad data
To begin with, we decide on the first splitting point, the root, by trying out all possible values for each of the two features. We utilize the weighted_impurity function we just defined to calculate the weighted Gini Impurity for each possible combination, as follows:
Gini(interest, tech) = weighted_impurity([[1, 1, 0],
[0, 0, 0, 1]]) = 0.405
Here, if we partition according to whether the user interest is tech, we have the 1st, 5th, and 6th samples for one group and the remaining samples for another group. Then the classes for the first group are [1, 1, 0], and the classes for the second group are [0, 0, 0, 1]:
Gini(interest, Fashion) = weighted_impurity([[0, 0],
[1, 0, 1, 0, 1]]) = 0.343
Here, if we partition according to whether the user's interest is fashion, we have the 2nd and 3rd samples for one group and the remaining samples for another group. Then the classes for the first group are [0, 0], and the classes for the second group are [1, 0, 1, 0, 1]:
Gini(interest, Sports) = weighted_impurity([[0, 1],
[1, 0, 0, 1, 0]]) = 0.486
Gini(occupation, professional) = weighted_impurity([[0, 0, 1, 0],
[1, 0, 1]]) = 0.405
Gini(occupation, student) = weighted_impurity([[0, 0, 1, 0],
[1, 0, 1]]) = 0.405
Gini(occupation, retired) = weighted_impurity([[1, 0, 0, 0, 1, 1],
[1]]) = 0.429
The root goes to the user interest feature with the fashion value, as this combination achieves the lowest weighted impurity or the highest Information Gain. We can now build the first level of the tree, as follows:
Figure 4.9: Partitioning the data according to is interested in fashion?
If we are satisfied with a one-level-deep tree, we can stop here by assigning the right branch label 0 and the left branch label 1 as the majority class.
Alternatively, we can go further down the road, constructing the second level from the left branch (the right branch cannot be split further):
Gini(interest, tech) = weighted_impurity([[0, 1],
[1, 1, 0]]) = 0.467
Gini(interest, Sports) = weighted_impurity([[1, 1, 0],
[0, 1]]) = 0.467
Gini(occupation, professional) = weighted_impurity([[0, 1, 0],
[1, 1]]) = 0.267
Gini(occupation, student) = weighted_impurity([[1, 0, 1],
[0, 1]]) = 0.467
Gini(occupation, retired) = weighted_impurity([[1, 0, 1, 1],
[0]]) = 0.300
With the second splitting point specified by (occupation, professional) with the lowest Gini Impurity, our tree becomes this:
Figure 4.10: Further partitioning of the data according to "is occupation professional?"
We can repeat the splitting process as long as the tree does not exceed the maximum depth and the node contains enough samples.
Now that the process of the tree construction has been made clear, it is time for coding.
We start with the criterion of the best splitting point; the calculation of the weighted impurity of two potential children is what we defined previously, while that of two metrics is slightly different. The inputs now become NumPy arrays for computational efficiency. For Gini Impurity, we have the following:
>>> def gini_impurity_np(labels):
... # When the set is empty, it is also pure
... if labels.size == 0:
... return 0
... # Count the occurrences of each label
... counts = np.unique(labels, return_counts=True)[1]
... fractions = counts / float(len(labels))
... return 1 - np.sum(fractions ** 2)
For entropy, we have the following:
>>> def entropy_np(labels):
... # When the set is empty, it is also pure
... if labels.size == 0:
... return 0
... counts = np.unique(labels, return_counts=True)[1]
... fractions = counts / float(len(labels))
... return - np.sum(fractions * np.log2(fractions))
Also, we update the weighted_impurity function, as follows:
>>> def weighted_impurity(groups, criterion='gini'):
... """
... Calculate weighted impurity of children after a split
... @param groups: list of children, and a child consists a list
... of class labels
... @param criterion: metric to measure the quality of a split,
... 'gini' for Gini Impurity or
... 'entropy' for Information Gain
... @return: float, weighted impurity
... """
... total = sum(len(group) for group in groups)
... weighted_sum = 0.0
... for group in groups:
... weighted_sum += len(group) / float(total) *
... criterion_function_np[criterion](group)
... return weighted_sum
Next, we define a utility function to split a node into left and right children based on a feature and a value:
>>> def split_node(X, y, index, value):
... """
... Split dataset X, y based on a feature and a value
... @param X: numpy.ndarray, dataset feature
... @param y: numpy.ndarray, dataset target
... @param index: int, index of the feature used for splitting
... @param value: value of the feature used for splitting
... @return: list, list, left and right child, a child is in
... the format of [X, y]
... """
... x_index = X[:, index]
... # if this feature is numerical
... if X[0, index].dtype.kind in ['i', 'f']:
... mask = x_index >= value
... # if this feature is categorical
... else:
... mask = x_index == value
... # split into left and right child
... left = [X[~mask, :], y[~mask]]
... right = [X[mask, :], y[mask]]
... return left, right
We check whether the feature is numerical or categorical and split the data accordingly.
With the splitting measurement and generation functions available, we now define the greedy search function, which tries out all possible splits and returns the best one given a selection criterion, along with the resulting children:
>>> def get_best_split(X, y, criterion):
... """
... Obtain the best splitting point and resulting children for
... the dataset X, y
... @param X: numpy.ndarray, dataset feature
... @param y: numpy.ndarray, dataset target
... @param criterion: gini or entropy
... @return: dict {index: index of the feature, value: feature
... value, children: left and right children}
... """
... best_index, best_value, best_score, children =
... None, None, 1, None
... for index in range(len(X[0])):
... for value in np.sort(np.unique(X[:, index])):
... groups = split_node(X, y, index, value)
... impurity = weighted_impurity(
... [groups[0][1], groups[1][1]], criterion)
... if impurity < best_score:
... best_index, best_value, best_score, children =
... index, value, impurity, groups
... return {'index': best_index, 'value': best_value,
... 'children': children}
The selection and splitting process occurs in a recursive manner on each of the subsequent children. When a stopping criterion is met, the process stops at a node, and the major label is assigned to this leaf node:
>>> def get_leaf(labels):
... # Obtain the leaf as the majority of the labels
... return np.bincount(labels).argmax()
And, finally, the recursive function links all of them together:
- It assigns a leaf node if one of two child nodes is empty.
- It assigns a leaf node if the current branch depth exceeds the maximum depth allowed.
- It assigns a leaf node if the node does not contain sufficient samples required for a further split.
- Otherwise, it proceeds with a further split with the optimal splitting point.
This is done with the following function:
>>> def split(node, max_depth, min_size, depth, criterion):
... """
... Split children of a node to construct new nodes or assign
... them terminals
... @param node: dict, with children info
... @param max_depth: int, maximal depth of the tree
... @param min_size: int, minimal samples required to further
... split a child
... @param depth: int, current depth of the node
... @param criterion: gini or entropy
... """
... left, right = node['children']
... del (node['children'])
... if left[1].size == 0:
... node['right'] = get_leaf(right[1])
... return
... if right[1].size == 0:
... node['left'] = get_leaf(left[1])
... return
... # Check if the current depth exceeds the maximal depth
... if depth >= max_depth:
... node['left'], node['right'] =
... get_leaf(left[1]), get_leaf(right[1])
... return
... # Check if the left child has enough samples
... if left[1].size <= min_size:
... node['left'] = get_leaf(left[1])
... else:
... # It has enough samples, we further split it
... result = get_best_split(left[0], left[1], criterion)
... result_left, result_right = result['children']
... if result_left[1].size == 0:
... node['left'] = get_leaf(result_right[1])
... elif result_right[1].size == 0:
... node['left'] = get_leaf(result_left[1])
... else:
... node['left'] = result
... split(node['left'], max_depth, min_size,
... depth + 1, criterion)
... # Check if the right child has enough samples
... if right[1].size <= min_size:
... node['right'] = get_leaf(right[1])
... else:
... # It has enough samples, we further split it
... result = get_best_split(right[0], right[1], criterion)
... result_left, result_right = result['children']
... if result_left[1].size == 0:
... node['right'] = get_leaf(result_right[1])
... elif result_right[1].size == 0:
... node['right'] = get_leaf(result_left[1])
... else:
... node['right'] = result
... split(node['right'], max_depth, min_size,
... depth + 1, criterion)
Finally, the entry point of the tree's construction is as follows:
>>> def train_tree(X_train, y_train, max_depth, min_size,
... criterion='gini'):
... """
... Construction of a tree starts here
... @param X_train: list of training samples (feature)
... @param y_train: list of training samples (target)
... @param max_depth: int, maximal depth of the tree
... @param min_size: int, minimal samples required to further
split a child
... @param criterion: gini or entropy
... """
... X = np.array(X_train)
... y = np.array(y_train)
... root = get_best_split(X, y, criterion)
... split(root, max_depth, min_size, 1, criterion)
... return root
Now, let's test it with the preceding hand-calculated example:
>>> X_train = [['tech', 'professional'],
... ['fashion', 'student'],
... ['fashion', 'professional'],
... ['sports', 'student'],
... ['tech', 'student'],
... ['tech', 'retired'],
... ['sports', 'professional']]
>>> y_train = [1, 0, 0, 0, 1, 0, 1]
>>> tree = train_tree(X_train, y_train, 2, 2)
To verify that the resulting tree from the model is identical to what we constructed by hand, we write a function displaying the tree:
>>> CONDITION = {'numerical': {'yes': '>=', 'no': '<'},
... 'categorical': {'yes': 'is', 'no': 'is not'}}
>>> def visualize_tree(node, depth=0):
... if isinstance(node, dict):
... if node['value'].dtype.kind in ['i', 'f']:
... condition = CONDITION['numerical']
... else:
... condition = CONDITION['categorical']
... print('{}|- X{} {} {}'.format(depth * ' ',
... node['index'] + 1, condition['no'], node['value']))
... if 'left' in node:
... visualize_tree(node['left'], depth + 1)
... print('{}|- X{} {} {}'.format(depth * ' ',
... node['index'] + 1, condition['yes'], node['value']))
... if 'right' in node:
... visualize_tree(node['right'], depth + 1)
... else:
... print(f"{depth * ' '}[{node}]")
>>> visualize_tree(tree)
|- X1 is not fashion
|- X2 is not professional
[0]
|- X2 is professional
[1]
|- X1 is fashion
[0]
We can test it with a numerical example, as follows:
>>> X_train_n = [[6, 7],
... [2, 4],
... [7, 2],
... [3, 6],
... [4, 7],
... [5, 2],
... [1, 6],
... [2, 0],
... [6, 3],
... [4, 1]]
>>> y_train_n = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
>>> tree = train_tree(X_train_n, y_train_n, 2, 2)
>>> visualize_tree(tree)
|- X2 < 4
|- X1 < 7
[1]
|- X1 >= 7
[0]
|- X2 >= 4
|- X1 < 2
[1]
|- X1 >= 2
[0]
The resulting trees from our decision tree model are the same as those we hand-crafted.
Now that you have a more solid understanding of decision trees after implementing one from scratch, we can move on with implementing a decision tree with scikit-learn.
Implementing a decision tree with scikit-learn
Here, we use the decision tree module (https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html), which is already well developed and optimized:
>>> from sklearn.tree import DecisionTreeClassifier
>>> tree_sk = DecisionTreeClassifier(criterion='gini',
... max_depth=2, min_samples_split=2)
>>> tree_sk.fit(X_train_n, y_train_n)
To visualize the tree we just built, we utilize the built-in export_graphviz function, as follows:
>>> export_graphviz(tree_sk, out_file='tree.dot',
... feature_names=['X1', 'X2'], impurity=False,
... filled=True, class_names=['0', '1'])
Running this will generate a file called tree.dot, which can be converted into a PNG image file using Graphviz (the introduction and installation instructions can be found at http://www.graphviz.org) by running the following command in the terminal:
dot -Tpng tree.dot -o tree.png
Refer to Figure 4.11 for the result:
Figure 4.11: Tree visualization
The generated tree is essentially the same as the one we had before.
I know you can't wait to employ a decision tree to predict ad click-through. Let's move on to the next section.
Predicting ad click-through with a decision tree
After several examples, it is now time to predict ad click-through using the decision tree algorithm you have just thoroughly learned about and practiced. We will use the dataset from a Kaggle machine learning competition, Click-Through Rate Prediction (https://www.kaggle.com/c/avazu-ctr-prediction). The dataset can be downloaded from https://www.kaggle.com/c/avazu-ctr-prediction/data.
Only the train.gz file contains labeled samples, so we only need to download this and unzip it (it will take a while). In this chapter, we will focus on only the first 300,000 samples from the train file unzipped from train.gz.
The fields in the raw file are as follows:
Figure 4.12: Description and example values of the dataset
We take a glance at the head of the file by running the following command:
head train | sed 's/,,/, ,/g;s/,,/, ,/g' | column -s, -t
Rather than a simple head train, the output is cleaner as all the columns are aligned:
Figure 4.13: The first few rows of the data
Don't be scared by the anonymized and hashed values. They are categorical features, and each possible value of them corresponds to a real and meaningful value, but it is presented this way due to privacy policy. Possibly, C1 means user gender, and 1005 and 1002 represent male and female, respectively.
Now, let's start by reading the dataset using pandas. That's right, pandas is extremely good at handling data in a tabular format:
>>> import pandas as pd
>>> n_rows = 300000
>>> df = pd.read_csv("train.csv", nrows=n_rows)
The first 300,000 lines of the file are loaded and stored in a DataFrame. Take a quick look at the first five rows of the DataFrame:
>>> print(df.head(5))
id click hour C1 banner_pos site_id ... C16 C17 C18 C19 C20 C21
0 1.000009e+18 0 14102100 1005 0 1fbe01fe ... 50 1722 0 35 -1 79
1 1.000017e+19 0 14102100 1005 0 1fbe01fe ... 50 1722 0 35 100084 79
2 1.000037e+19 0 14102100 1005 0 1fbe01fe ... 50 1722 0 35 100084 79
3 1.000064e+19 0 14102100 1005 0 1fbe01fe ... 50 1722 0 35 100084 79
4 1.000068e+19 0 14102100 1005 1 fe8cc448 ... 50 2161 0 35 -1 157
The target variable is the click column:
>>> Y = df['click'].values
For the remaining columns, there are several columns that should be removed from the features (id, hour, device_id, and device_ip) as they do not contain much useful information:
>>> X = df.drop(['click', 'id', 'hour', 'device_id', 'device_ip'],
axis=1).values
>>> print(X.shape)
(300000, 19)
Each sample has 19 predictive attributes.
Next, we need to split the data into training and testing sets. Normally, we do this by randomly picking samples. However, in our case, the samples are in chronological order, as indicated in the hour field. Obviously, we cannot use future samples to predict the past ones. Hence, we take the first 90% as training samples and the rest as testing samples:
>>> n_train = int(n_rows * 0.9)
>>> X_train = X[:n_train]
>>> Y_train = Y[:n_train]
>>> X_test = X[n_train:]
>>> Y_test = Y[n_train:]
As mentioned earlier, decision tree models can take in categorical features. However, because the tree-based algorithms in scikit-learn (the current version is 0.22.0 as of 2020) only allow numeric input, we need to transform the categorical features into numerical ones. But note that, in general, we do not need to do this; for example, the decision tree classifier we developed from scratch earlier can directly take in categorical features.
We will now transform string-based categorical features into one-hot encoded vectors using the OneHotEncoder module from scikit-learn. One-hot encoding was briefly mentioned in Chapter 1, Getting Started with Machine Learning and Python. To recap, it basically converts a categorical feature with k possible values into k binary features. For example, the site category feature with three possible values, news, education, and sports, will be encoded into three binary features, such as is_news, is_education, and is_sports, whose values are either 1 or 0.
We initialize a OneHotEncoder object as follows:
>>> from sklearn.preprocessing import OneHotEncoder
>>> enc = OneHotEncoder(handle_unknown='ignore')
We fit it on the training set as follows:
>>> X_train_enc = enc.fit_transform(X_train)
>>> X_train_enc[0]
<1x8385 sparse matrix of type '<class 'numpy.float64'>'
with 19 stored elements in Compressed Sparse Row format>
>>> print(X_train_enc[0])
(0, 2) 1.0
(0, 6) 1.0
(0, 30) 1.0
(0, 1471) 1.0
(0, 2743) 1.0
(0, 3878) 1.0
(0, 4000) 1.0
(0, 4048) 1.0
(0, 6663) 1.0
(0, 7491) 1.0
(0, 7494) 1.0
(0, 7861) 1.0
(0, 8004) 1.
(0, 8008) 1.0
(0, 8085) 1.0
(0, 8158) 1.0
(0, 8163) 1.0
(0, 8202) 1.0
(0, 8383) 1.0
Each converted sample is a sparse vector.
We transform the testing set using the trained one-hot encoder as follows:
>>> X_test_enc = enc.transform(X_test)
Remember, we specified the handle_unknown='ignore' parameter in the one-hot encoder earlier. This is to prevent errors due to any unseen categorical values. To use the previous site category example, if there is a sample with the value movie, all of the three converted binary features (is_news, is_education, and is_sports) become 0. If we do not specify ignore, an error will be raised.
Next, we will train a decision tree model using grid search, which you learned about in Chapter 3, Recognizing Faces with Support Vector Machine. For demonstration purposes, we will only tweak the max_depth hyperparameter. Other hyperparameters, such as min_samples_split and class_weight, are also highly recommended. The classification metric should be AUC of ROC, as it is an imbalanced binary case (only 51,211 out of 300,000 training samples are clicks, which is a 17% positive CTR; I encourage you to figure out the class distribution yourself):
>>> from sklearn.tree import DecisionTreeClassifier
>>> parameters = {'max_depth': [3, 10, None]}
We pick three options for the maximal depth, 3, 10, and unbounded. We initialize a decision tree model with Gini Impurity as the metric and 30 as the minimum number of samples required to split further:
>>> decision_tree = DecisionTreeClassifier(criterion='gini',
... min_samples_split=30)
>>> from sklearn.model_selection import GridSearchCV
As for grid search, we use three-fold (as there are enough training samples) cross-validation and select the best performing hyperparameter measured by AUC:
>>> grid_search = GridSearchCV(decision_tree, parameters,
... n_jobs=-1, cv=3, scoring='roc_auc')
Note n_jobs=-1 means that we use all of the available CPU processors:
>>> grid_search.fit(X_train, y_train)
>>> print(grid_search.best_params_)
{'max_depth': 10}
We use the model with the optimal parameter to predict any future test cases as follows:
>>> decision_tree_best = grid_search.bestestimator
>>> pos_prob = decision_tree_best.predict_proba(X_test)[:, 1]
>>> from sklearn.metrics import roc_auc_score
>>> print(f'The ROC AUC on testing set is: {roc_auc_score(Y_test,
... pos_prob):.3f}')
The ROC AUC on testing set is: 0.719
The AUC we can achieve with the optimal decision tree model is 0.72. This does not seem to be very high, but click-through involves many intricate human factors, which is why predicting it is not an easy task. Although we can further optimize the hyperparameters, an AUC of 0.72 is actually pretty good. Randomly selecting 17% of the samples to be clicked on will generate an AUC of 0.496:
>>> pos_prob = np.zeros(len(Y_test))
>>> click_index = np.random.choice(len(Y_test),
... int(len(Y_test) * 51211.0/300000),
... replace=False)
>>> pos_prob[click_index] = 1
>>> print(f'The ROC AUC on testing set is: {roc_auc_score(Y_test,
... pos_prob):.3f}')
The ROC AUC on testing set is: 0.496
Looking back, we can see that a decision tree is a sequence of greedy searches for the best splitting point at each step, based on the training dataset. However, this tends to cause overfitting as it is likely that the optimal points only work well for the training samples. Fortunately, ensembling is the technique to correct this, and random forest is an ensemble tree model that usually outperforms a simple decision tree.
Ensembling decision trees – random forest
The ensemble technique of bagging (which stands for bootstrap aggregating), which I briefly mentioned in Chapter 1, Getting Started with Machine Learning and Python, can effectively overcome overfitting. To recap, different sets of training samples are randomly drawn with replacement from the original training data; each resulting set is used to fit an individual classification model. The results of these separately trained models are then combined together through a majority vote to make the final decision.
Tree bagging, as described in the preceding paragraph, reduces the high variance that a decision tree model suffers from and, hence, in general, performs better than a single tree. However, in some cases, where one or more features are strong indicators, individual trees are constructed largely based on these features and, as a result, become highly correlated. Aggregating multiple correlated trees will not make much difference. To force each tree to become uncorrelated, random forest only considers a random subset of the features when searching for the best splitting point at each node. Individual trees are now trained based on different sequential sets of features, which guarantees more diversity and better performance. Random forest is a variant of the tree bagging model with additional feature-based bagging.
To employ random forest in our click-through prediction project, we can use the package from scikit-learn. Similarly to the way we implemented the decision tree in the preceding section, we only tweak the max_depth parameter:
>>> from sklearn.ensemble import RandomForestClassifier
>>> random_forest = RandomForestClassifier(n_estimators=100,
... criterion='gini', min_samples_split=30,
... n_jobs=-1)
Besides max_depth, min_samples_split, and class_weight, which are important hyperparameters related to a single decision tree, hyperparameters that are related to a random forest (a set of trees) such as n_estimators are also highly recommended. We fine-tune the max_depth as follows:
>>> grid_search = GridSearchCV(random_forest, parameters,
... n_jobs=-1, cv=3, scoring='roc_auc')
>>> grid_search.fit(X_train, y_train)
>>> print(grid_search.best_params_)
{'max_depth': None}
We use the model with the optimal parameter None for max_depth (the nodes are expanded until another stopping criterion is met) to predict any future unseen cases:
>>> random_forest_best = grid_search.bestestimator
>>> pos_prob = random_forest_best.predict_proba(X_test)[:, 1]
>>> print('The ROC AUC on testing set is:
... {0:.3f}'.format(roc_auc_score(y_test, pos_prob)))
The ROC AUC on testing set is: 0.759
It turns out that the random forest model gives a substantial lift to the performance.
Let's summarize several critical hyperparameters to tune:
max_depth: This is the deepest individual tree. It tends to overfit if it is too deep or underfit if it is too shallow.min_samples_split: This hyperparameter represents the minimum number of samples required for further splitting at a node. Too small a value tends to cause overfitting, while too large a value is likely to introduce underfitting.10,30, and50might be good options to start with.
The preceding two hyperparameters are generally related to individual decision trees. The following two parameters are more related to a random forest or collection of trees:
max_features: This parameter represents the number of features to consider for each best splitting point search. Typically, for an m-dimensional dataset,
(rounded) is a recommended value for max_features. This can be specified asmax_features="sqrt"in scikit-learn. Other options includelog2, 20%, and 50% of the original features.n_estimators: This parameter represents the number of trees considered for majority voting. Generally speaking, the more trees, the better the performance but the longer the computation time. It is usually set as100,200,500, and so on.
Next, we'll discuss gradient boosted trees.
Ensembling decision trees – gradient boosted trees
Boosting, which is another ensemble technique, takes an iterative approach instead of combining multiple learners in parallel. In boosted trees, individual trees are no longer trained separately. Specifically, in gradient boosted trees (GBT) (also called gradient boosting machines), individual trees are trained in succession where a tree aims to correct the errors made by the previous tree. The following two diagrams illustrate the difference between random forest and GBT:
Random forest builds each tree independently using a different subset of the dataset, and then combines the results at the end by majority votes or averaging:
Figure 4.14: The random forest workflow
The GBT model builds one tree at a time and combines the results along the way:
Figure 4.15: The GBT workflow
We will use the XGBoost package (https://xgboost.readthedocs.io/en/latest/) to implement GBT. We first install the XGBoost Python API via the following command:
pip install xgboost
If you run into a problem, please install or upgrade CMake, as follows:
pip install CMake
Let's now take a look at the following steps. You will see how we predict clicks using GBT:
- First, we transform the label variable into two dimensions, which means 0 will become [1, 0] and 1 will become [0, 1]:
>>> from sklearn.preprocessing import LabelEncoder >>> le = LabelEncoder() >>> Y_train_enc = le.fit_transform(Y_train) - We import XGBoost and initialize a GBT model:
>>> import xgboost as xgb >>> model = xgb.XGBClassifier(learning_rate=0.1, max_depth=10, ... n_estimators=1000)We set the learning rate to 0.1, which determines how fast or slow we want to proceed with learning in each step (in each tree, in GBT). We will discuss the learning rate in more detail in Chapter 5, Predicting Online Ad Click-Through with Logistic Regression.
max_depthfor individual trees is set to 10. Additionally, 1,000 trees will be trained in sequence in our GBT model. - Next, we train the GBT model on the training set we prepared previously:
>>> model.fit(X_train_enc, Y_train) - We use the trained model to make predictions on the testing set and calculate the ROC AUC accordingly:
>>> pos_prob = model.predict_proba(X_test_enc)[:, 1] >>> print(f'The ROC AUC on testing set is: {roc_auc_score(Y_test, pos_prob):.3f}') The ROC AUC on testing set is: 0.771
We are able to achieve 0.77 AUC using the XGBoost GBT model.
In this section, you learned about another type of tree ensembling, GBT, and applied it to our ad click-through prediction.
Summary
In this chapter, we started with an introduction to a typical machine learning problem, online ad click-through prediction, and its inherent challenges, including categorical features. We then looked at tree-based algorithms that can take in both numerical and categorical features.
Next, we had an in-depth discussion about the decision tree algorithm: its mechanics, its different types, how to construct a tree, and two metrics (Gini Impurity and entropy) that measure the effectiveness of a split at a node. After constructing a tree by hand, we implemented the algorithm from scratch.
You also learned how to use the decision tree package from scikit-learn and applied it to predict the CTR. We continued to improve performance by adopting the feature-based random forest bagging algorithm. Finally, the chapter ended with several ways in which to tune a random forest model, along with a bonus section in which we implemented a GBT model with XGBoost. Bagging and boosting are two approaches to model ensembling that can improve learning performance.
More practice is always good for honing your skills. I recommend that you complete the following exercises before moving on to the next chapter, where we will solve ad click-through prediction using another algorithm: logistic regression.
Exercises
- In the decision tree click-through prediction project, can you also tweak other hyperparameters, such as
min_samples_splitandclass_weight? What is the highest AUC you are able to achieve? - In the random forest-based click-through prediction project, can you also tweak other hyperparameters, such as
min_samples_split,max_features, andn_estimators, in scikit-learn? What is the highest AUC you are able to achieve? - In the GBT-based click-through prediction project, what hyperparameters can you tweak? What is the highest AUC you are able to achieve? You can read https://xgboost.readthedocs.io/en/latest/python/python_api.html#module-xgboost.sklearn to figure it out.