10.2.1.1. The structure of the decision tree

Decision trees use a graph structure in which each potential decision creates a new node, which results in a graph similar to a tree (Quinlan 1986). Each node has a state, and connections are based on this state. The further we descend into the structure, or down the tree, the more these states are combined.

In other words, a decision tree uses a tree structure to represent a number of possible decision paths and a result for each path. To better understand this structure, we’ll use an example that will help us predict whether a proposed service platform will interest people.

We can see in Figure 10.1 that the tree acts like a flowchart.

A decision tree is a classification algorithm that uses tree-like data structures to model decisions and results. The structure of this algorithm is as follows:

• – Nodes, or branching points, which are often called “decision nodes”. They usually represent a conditional test. These nodes are the decision or test points. Each node refers to an input variable or an attribute. Each tree starts with a root node where the most significant attribute for all the observations is located (gender, in our case).
• – The branch represents the result of each decision and connects two nodes. Depending on the nature of the variable, each branch makes it possible to visualize the decision’s state. If the variable is quantitative (numerical), we place the upper branch to the right. We may include certain components (equal, less, etc.).
• – Leaf nodes indicate the final result (interested in this service or not). They represent class labels in classification problems, or a discrete value in regression problems.

Note that the depth of a tree is the minimum number of steps required to achieve the result from the root. In our example, the “age” and “income” nodes are one step from the root, and the four nodes at the bottom are the result of all previous decisions. From the root to the leaf lie a series of decisions taken at various internal nodes.

10.2.1.2. How the algorithm works

The purpose of a decision tree is generally to build a tree T from a set of observations S. If all S observations belong to a class C, “gender: male” in our example, then the node is regarded as a leaf node and receives the label C.

However, if any S observations do not belong to the class C, or if S is not pure enough, the algorithm selects the next most informative attribute (age, etc.), and the S scores based on the values of this attribute. Therefore, the algorithm builds subtrees (T1, T2, etc.) for subsets of S, recursively, until one of the preceding criteria is fulfilled.

The first step is to select the most informative attribute. A common way to identify this attribute is to use methods based on entropy (Quinlan 1993). These methods select the most informative attribute based on:

• – entropy: shows the uncertainty of the randomness of the elements or, in other words, a measure of the impurity of an attribute. Entropy measures the homogeneity of a sample. If the sample is completely homogeneous, entropy is zero, and if it is divided equally, it means that it has an entropy equal to one. Either a class X and its label x ∈ X or P(x) the probability of x. H_x, the entropy of X is defined as follows:

• – information gain: this measures the relative change in entropy in relation to the independent attribute. It tries to estimate the information contained in each attribute. Information gain therefore measures the purity of an attribute. To build a decision tree, we must find the attribute that returns the highest information gain (that is to say, the most homogeneous branches). Information gain assigns a class for filtering on a given node of the tree. Classification is based on the entropy of the information gain in each division. The information gain of an attribute A is defined as the difference between the base entropy and the conditional entropy of the attribute:

10.2.2.1. The applications of the algorithm

Naïve Bayes is a fairly intuitive classification algorithm to understand. A classification using this algorithm assumes that the presence or absence of a particular characteristic of a class is not related to the presence or absence of other features. For example, an object can be classified according to its attributes such as shape, color, and weight.

It can be used for binary and multiclass classification problems. The main point is the idea of treating each feature independently.

The Naïve Bayes method assesses the probability of each entity independently, irrespective of any correlation, and determines the prediction based on Bayes’ theorem (Sedkaoui 2018b).

Using this method has the following advantages: simplicity and ease of understanding. Moreover, this algorithm generally performs well in terms of resources consumed, since only the probabilities of the characteristics and classes must be calculated; it is not necessary to find the coefficients as in other algorithms.

Because Naïve Bayes is easy to implement and can be run efficiently, even without prior knowledge of the data, it is one of the most popular algorithms for classification of textual data.

Besides its simplicity, this algorithm is also a good choice when CPU and memory resources are limiting factors.

This classification algorithm can be used in real-world applications such as:

• – sentiment analysis and text classification;
• – filtering unwanted messages (spam);
• – recommendation systems;
• – facial recognition;
• – fraud detection;
• – real-time predictions;
• – predicting the probability of several classes for the target variable.

Its main drawback is that each feature is treated independently, even though in most cases this cannot be accurate (Bishop 2006).

10.2.2.2. Operation of the Naïve Bayes algorithm

Naïve Bayes is a classification technique based on Bayes’ theorem that assumes independence between the predictors. That is to say, it assumes that the presence of an entity in a class is not linked to any other entity. Although these features are dependent on each other or on the existence of other features, all of these properties are independent.

This theorem can be extended to become a Naïve Bayes classifier. First, we can use the conditional independence hypothesis, which states that each attribute is conditionally independent of any other attribute given the label of class C_i:

Therefore, this assumption simplifies the calculation of P(a₁, a₂,…, a_m/ C_i).

Then, we can ignore the denominator P(a₁, a₂,…, a_m), since it appears in P(Ci/A_i) (for i = 1, 2 … n); removing the denominator will have no impact on the relative probability scores and will simplify the calculations.

Here, A_i represents the attributes or characteristics, and C' is the response variable. Now, P(Ci/A_i) becomes equal to the product of the probability distribution for each attribute X.

We are interested in finding the probability P(Ci/A_i). Now, for several values of C, we will calculate the probability for each of them.

So how do we predict the class of the response variable as a function of the different values that we obtain for P(Ci/A_i) ? We simply take the most likely or the maximum of these values. Therefore, this procedure is also known as “maximum a posteriori estimation”.

10.2.3.1. Definition of SVM

A Support Vector Machine is an algorithm that seeks to divide the hyperplane with the widest possible gap to improve resistance to noise. Like logistic regression, it is a discriminating method that focuses only on predictions.

This is a classification method, in which we include each data point in a dimensional space n (where n is the number of entities) and the value of each entity is the value of a particular coordinate. Then, the classification is done by searching the hyperplane, which clearly differentiates the two classes.

For example, if we have only two variables, such as renting an apartment or a villa on Airbnb, we must first draw the two variables in a two-dimensional space (n = 2), with each point having two coordinates called support vectors (see Figure 10.2 for more detail).

Now let’s look for a line that divides the data between the two groups of differently classified data, knowing that the distance of the nearest point for each group will be those farthest away.

So, in SVM, the goal of optimization is to maximize “the gap”. This gap represents the distance between the separating hyperplane and the nearest points of this hyperplane, called support vectors.

The question that now arises is: “How do we identify the right hyperplane?”

10.2.3.2. SVM: how it works

In Figure 10.2, the line that divides the data into two different classes is the black line, because the two closest points are farthest from that line. Then, as a function of the data’s location on one hand and the line on the other, we can classify new data.

As shown in Figure 10.3, there are several ways to separate the data. To resolve this issue, SVM seeks the best line separating the data by maximizing the orthogonal distance between the nearest points of each data category and the limit of the line.

Distances called “gaps”, and the points used to define the gap (the nearest boundary points) are called “support vectors”. Once the ideal function is determined, the algorithm is able to predict whether people prefer to rent an apartment or a villa.

This example illustrates the application of this algorithm and shows a linear hyperplane between these two classes or groups. SVM can effectively perform linear classifications and can also be configured to perform nonlinear classifications (Cristianini and Shawe-Taylor 2000).

10.2.4.1. The k-nearest neighbors (kNN)

The kNN, or k-Nearest Neighbors is an algorithm that can be used both for classification and regression. The principle of this model is to choose the k closest data points under study to predict its value (Sedkaoui 2018b). In classification or regression, the input will consist of the k closest training examples in a space.

To understand how this algorithm works, let’s consider a small visual example that will help you understand this algorithm. In Figure 10.4, we have two classes of data, red circles and black squares. It should be noted that the input is two-dimensional and the target to be classified is the shape.

Suppose now that we have a new input object whose class we want to predict. How should we proceed? Well, let’s consider the k nearest neighbors to this object and see which class contains the majority of these points in order to deduce its class.

In this example, we used 5-NN (k = 5), and we can say that the new entry belongs to the class of red circles, as its nearest neighbors contain three (3) red circles and two (2) black squares.

The principle of this algorithm is to assign a set of data to one of the class categories by calculating the distance separating it from each point in the data-set. We choose the first k elements in the series of distances and therefore choose the dominant label from among the k elements, which represents the category of the element in the data-set.

10.2.4.2. Random Forest

Random Forest is one of the most popular supervised learning algorithms. It requires virtually no preparation or data modeling and usually provides accurate results (Sedkaoui 2018a). Random forests are based on the decision trees described above.

More specifically, random forests are collections of decision trees (Breiman 2001) that produce a better forecast. This is why it is called a “forest” (or set of decision trees).

So, as the name suggests, this algorithm creates a forest and renders it somewhat random. This forest constitutes a set of decision trees, generally trained with the bagging method (Breiman 1996).

Random Forest develops several trees into a model. To classify a new object or a new entry in terms of new attributes, each tree provides a classification, and we say that this tree “votes” for this class. The forest chooses classifications with the most votes among all the trees in the forest and takes the average difference of the production of different trees.

This algorithm therefore builds several trees and combines them to get a more accurate result.

10.2.4.3. Neural networks

Neural networks are inspired by the neurons in the human nervous system. They help find complex patterns in the data. These neural networks learn a specific task as a function of the data-set (Sedkaoui 2018b).

Thanks to recently developed Deep Learning algorithms, neural networks have been developed as a method for facilitating a number of complex tasks such as image classification, voice recognition, etc.

In neural networks, we have an input layer that receives the input data and then propagates the data to the hidden layers. Finally, the output layer produces the classification result.

Each tier of the neural network is a set of interconnections between the nodes of a tier with those in the other tiers. So, neural networks consist of nodes (Figure 10.5).

So, we’ve taken the tour of the different classification algorithms. We found that each algorithm has its own properties. But to help you identify the most suitable method for a specific problem, we suggest, in Table 10.1, a list of items to consider.

Depending on the set of training data and the variables, we will opt for one of these algorithms. The goal is the same: to predict or classify new entries. For example, to determine whether a new email is spam or not.

Now let’s examine the theory behind these classification algorithms and use an example from the sharing economy to explain how these methods work in practice, while continuing to explore how Big Data analytics can be used to generate value for companies in this economy.

10.3.2.1. Decision trees

As we indicated at the beginning of this chapter, decision tree refers to types of classification algorithms that have a predefined target variable.

This algorithm is mainly used for classification but can also be applied to prediction problems with both categorical and numerical variables.

Tree models can capture non-linear relationships in sets of observations. Using a tree structure, a decision tree comprises a plurality of internal nodes, each of which corresponds to a characteristic (e.g. the number of rooms), and each decision node is a class label (e.g. the number of rooms is less than or greater than 2).

Now we’ll adjust the decision tree algorithm for our listings.csv data. But before doing this in Python, we need to import certain required libraries, such as:

• – NumPy and pandas: for manipulating data;
• – train_test_split from cross_validation: for splitting the data into a train (x_train, y_train) and a testing (x_test, y_test) set;
• – DecisionTreeClassifier: for creating a decision tree classifier;
• – Accuracy_score: for calculating precision metrics from the variables of the predicted classes.

To understand the performance of the model, we divided the data-set into a train set and a test set using the train_test_split function. The test_size parameter has a value of 0.3; this means that the test sets will account for 30% of all data, and the training data-set will represent 70% of the data.

The random_state variable is a state generator for pseudo-random numbers used for random sampling.

The decision tree algorithm used for classification problems (like the one we are currently examining) aims to create one of these decision trees in order to assign records to a defined number of categories.

Having trained the decision tree model (with the train function) to classify characteristics according to their importance, we are now able to determine what features have greater weight in the calculation of prices. The results of this classification are illustrated in Figure 10.6.

Drawing a conclusion from this model, we can see that the algorithm has identified amenities and location as the main contributors to the way in which it predicted prices. We found that the most important features were:

• – longitude;
• – host_total_listings_count;
• – latitude;
• – accomodates;
• – bedrooms;
• – bathrooms.

Other features (Elysée, etc.) concerning the apartment’s location.

The question that you may now be asking is: how do we select the criteria and values for classification? It is the intelligence of the algorithm that does it for you; the principle is simple: start with the most discriminating variables, that is to say that we must create the greatest possible level of disorder, a principle that is mathematically modeled by the entropy function (Sedkaoui 2018b).

Using the data-set, we calculated the RMSE, which is equal to 21.505. What we can see from this value is that it is very high compared to the RMSE values for the Ridge (14.832) and Lasso (15.214) regressions.

These characteristics gain more weight because they tend to be more linearly correlated. Those whose correlation coefficient was higher tended to increase apartment prices.

As can be seen in the resulting graph, the decision tree captures the general trend of the data. However, one disadvantage of this model is that it does not account for the continuity and differentiability of the desired prediction. In addition, we must make sure we select an appropriate value for the tree depth to avoid over-or under-adjusting the data.

We will use the Random Forest algorithm to process the data.

10.3.2.2. Modeling using Random Forest

We chose the Random Forest model because this model uses a blending technique that combining several models into one. This method usually reduces the variance and bias in observational data, which improves forecast accuracy.

The advantage of the Random Forest algorithm is independence between the trees, which makes it possible to parallelize processing and improve the algorithm’s performance. Every tree is different, and their grouping should make it possible to achieve a lower degree of variance than a single tree.

With regard to our example, we first used the data-set to train the model by applying the Random Forest algorithm. We then used the test data-set to test this model and proceed to validation. This allowed us to determine the most important features, which include two factors (equipment/location).

Among the features shown in Figure 10.7, we can identify a set of important variables, which include:

• – bathrooms;
• – accomodates;
• – host_total_listings_count;
• – bedrooms.

These are almost the same variables as the significant variables in our decision tree model, which shows that they are key predictors for forecasting the prices of Airbnb apartments in Paris.

We obtained an RMSE , equal to 14.775 (Table 10.2), which is lower than the RMSE values of the other models.

Note that since the price distribution is slightly skewed to the right (see Figure 9.8 in Chapter 9), we have added two basic models that could explain this bias by setting average values to 110.78 euros and median values to 80 euros.

By comparing the RMSE values, we see that the linear regression model showed the highest value for RMSE (2368.59) and that the random forest model has the smallest value (14.775). The random forest model surpasses other models in terms of predictive accuracy. Based on the RMSE test for each model, we selected the Random Forest model as the best model for predicting the price, because it has the smallest RMSE.

This model is most effective for predicting Airbnb prices because it is easier to identify important predictors. This algorithm works well with large-scale predictors and large sets of training data. However, the downside is that prediction takes too long when there is a large number of trees.

We also concluded that the most important variables for predicting prices are the variables related to location and amenities (bedroom, bathroom, location, etc.). The total number of guests as well as hospitality play a role, but all the models have shown the significance of the list of amenities, home type, and location.

Based on these findings, we want to predict price using a different algorithm: kNN, because as hosts you would surely consider all factors that affect the price of your apartment; in order to automate the data analysis process, we have been using the k nearest neighbor or kNN algorithm since we began our work.