2.1.1 Filter methods

Filter models rely on the characteristics of the data without using any classification method (Liu and Motoda 2007). Typically, features are ranked and the highest ranked ones are selected. This can be done in two ways: univariate or multivariate. In the univariate scheme, each feature is ranked independently from others whereas all features are considered simultaneously in the multivariate approach. Several criteria have been applied to rank data. Among them, we can cite: quality (Fisher score (Duda, Hart, and Stork 2012; Gu, Li, and Han 2012)), independency (Chi-squared (Bonaccorso 2017)), redundancy (information gain (Roobaert, Karakoulas, and Chawla 2006)) or separation of class instances (ReliefF (Kira and Rendell 1992)).

Since filter models are easy to understand and implement, it is a popular technique. However, features are selected independently from classification and thus, filter models totally ignore the effects of the selected subset on the performance of the classification algorithm (Hall and Smith 1999).

2.1.2 Wrapper methods

Wrapper models were developed to overcome the limitation of filter models. The subset evaluation is performed by integrating the classifier. Hence, the subset is adapted to the inherent particularities and bias of a predefined classifier (Tang, Alelyani, and Liu 2014). To find the best subset, a wide range of search strategies exists including hill-climbing, best-first, branch-and-bound, and genetic algorithms (Guyon and Elisseeff 2003). Two other popular methods are forward selection and backward elimination where features are respectively added or removed one by one.

Wrapper models provide better predictive performances than filter models (Kohavi and John 1997). Nevertheless, they are more computationally expensive than filter models.

2.2.1 Principal Component Analysis

Principal Component Analysis is a well-known technique of data transformation (Jolliffe 2011). In its standard formulation, it finds the most discriminant projection of the original feature set by maximizing the variance between data points. In practice, the eigenvectors of the covariance matrix, calculated from the original feature set, are computed. Then, the ones with the largest eigenvalues (principal components) are used to reconstruct a part of the variance of the original dataset.

After that, there are two ways of using principal components regarding the objective of the analysis. The first one is data visualization. In that case, only two or three principal components, carying most of the variance, will be retrieved in order to plot the data in a two to three dimensional graph. This way, further analyses can be conducted regarding the distribution of data within the objective of class separation. Another purpose of PCA is to feed machine learning algorithms for classification purpose. With PCA, the reduction of dimension can be regulated by the total variance wanted for the feature subset. In other words, the number of principal components that are kept depends on the percent of variance information wanted by the user.

The main limitation of PCA is that there is no guarantee that a small number of principal components with the highest variance will contain the information needed for the classification (Neal and Zhang 2006). Hence, relevant information can be lost and the resulting projected features \bm{Z} can lead to weak classification performances. Additionally, PCA is only suited for quantitative set of feature. Other factor methods exists. Among them we can cite Multiple correspondence analysis (Le Roux and Rouanet 2010) for qualitative feature set and factor analysis of mixed data for mixed feature set (Escofier and Pagès 2008). Moreover, a version of PCA, called kernel PCA, has been proposed to make non-linear projections (Schölkopf, Smola, and Müller 1997). Briefly, an initial step is first performed to find a particular space where the dataset becomes linearly separable (Bonaccorso 2017).

2.2.2 Linear Discriminant Analysis

Contrary to PCA, in Linear Discriminant Analysis, labels are integrated in the process of dimension reduction. LDA finds the most discriminant projection by maximizing between-class distance and minimizing the within-class distance (Balakrishnama and Ganapathiraju 1998).

In practice, the eigenvectors of the between-class and within-class covariance matrices are computed and the best projection is found using Fisher’s criterion.

A comparative example between PCA and LDA is given by Figure 5. For a two-class data example, the resulting axis that preserves the variance on the whole data set (PCA) and the one that preserves the distance between both classes (LDA) are drawn. We can see, on each axis, the resulting data projection. LDA offers, in that case, a better projection for discriminating purpose. In fact, besides dimensionality reduction, LDA can also be used for classification (see Section 3.1.3).

3.1.1 Perceptron

The most basic linear model is the perceptron (Rosenblatt 1958), depicted in Figure 7.

In this example, the perceptron output decision y_i, which can either be -1 or +1, is computed for each sample i as: y_i = f(w_1x_{i1} + w_2x_{i2}) where f is a step function, also called threshold or activation function. This can be generalized for a larger dimension p by: \label{linearEquation} Y = f(W^T\bm{X}+b) where W is the weight vector defined as W = \left\{ w_1, w_2, \ldots, w_p \right\} and b is the bias.

To summarize, to make a prediction, the perceptron computes two quantities. First, the weighted sum of the input features is calculated. Then, this sum is thresholded by the function f in order to retrieve a prediction equal to -1 or +1.

During the training phase, W is firstly randomly initialized. Then, weights are settled by considering all the samples of the training set and looking at the output decision (Shiffman 2012). It is performed in three steps which are repeated until all training samples are correctly classified:

1. Make a prediction for an input sample;

2. Compute the error \epsilon between the prediction and real label;

3. Adjust the new vector of weights W' accordingly to the error, such as: W' = W + \Delta W

where \Delta W = \epsilon x \eta x X_i, with \eta, called the learning rate⁴ and X_i, the input features of the sample.

So far, we presented a two-class classification approach. In case of multiclass problems, several perceptrons can be trained in order to predict each class versus all others (one-versus-the-rest).

The power of perceptron classifiers resides in the fact that if a linear boundary exists to discriminate classes, the model will converge perfectly. However, in most classification problems, an overlap exists between classes and perceptron models will necessary present misclassification.

3.1.2 Logistic Regression

Logistic Regression (LR) is quite similar to perceptron except that instead of a class prediction, it returns a probability of belonging to the positive class. Hence, in some cases, it may be more robust to class overlap. To compare between perceptron and logistic regression lets restart from Equation ([linearEquation]). In logistic regression, b is commonly renamed w_0, the model intercept. Then, for each sample, a score S(X_i) is computed as: S(X_i) = f(W^TX_i+w_0)

In logistic regression, f is fixed and is called the logistic (or sigmoid) function. The sigmoid function, depicted by Figure 8, is used to associate each score to a probability bounded between 0 and 1, such as: P(Y_i) = f(S(X_i))

After that, a cut-off value is usually applied on the probability to obtain the class output.

In the learning phase, the vector of weights W has to be estimated. Here, the best W is the one that maximizes the conditional probabilities P(Y|\bm{X}, W) on the training set. This is commonly done by Maximum Likelihood Estimation (MLE), based on the assumption that weights are normally distributed (Czepiel 2002).

Logistic regression is usually applied for binary classification. However, as well as perceptron, it is possible to extend it to multiclass problems by training several one-versus-the-rest LR classifiers.

3.1.3 Linear Discriminant Analysis

As mentioned in Section 2.2.2, Linear Discriminant Analysis can be used for feature extraction. It can also be applied for classification purpose. Contrary to previous linear methods, LDA is more suited for multiclass analysis (Rao 1948). We saw that LDA aims to find the best projection by maximizing the mean between-class distances while minimizing the within-class variance. For multiclass problems, a initial step is added to compute the overall mean (= center) of the data. Then, it is the distance between each class and this center that is maximized while minimizing the within-class variance.

In this way, distributions (means and variance) of each class are estimated. Thus, by the use of Bayes’ theorem, the probability of a sample to belong to each class can be estimated. For future predictions, the class associated with the higher probability will be returned.

Nevertheless, LDA presents two main limitations. The first one is due to the number of samples for each class in the training set. If a class is under-represented, the estimated distribution for this class will be corrupted. Secondly, as previous methods, LDA is more suitable on linearly separable multiclass problems.

3.2.1 K-Nearest Neighbors

K-Nearest Neighbors is a basic method used for classification. Basically, it computes all the distances between a new sample and the ones of the training set. Then, the majority class of its neighbors is assigned to it. The number of neighbors that contributes to the vote is determined by k.

An example of KNN classification, with k=3, is given by Figure 9. In this example, the class of a new sample (in blue) is sought. The distance with all others points of the learning set is computed. Labels of the 3 nearest neigbours are checked. With two neighbors belonging to class "Black" and one to class "Orange", the new sample is classified as a "Black" sample.

Although Hamming, Manhattan or Minkowski distances can be used, KNN classifier is commonly based on the Euclidean distance. The Euclidean distance between a sample of the training set X_{i} and a new sample X_{n}, is computed as: d(X_{i},X_{n}) = \sqrt{(x_{i1}-x_{n1})^2+(x_{i2}-x_{n2})^2+\ldots+(x_{ip}-x_{np})^2} To compute an accurate distance, it is necessary to work on homogeneous features (i.e., with the same scale). Indeed, absolute differences in features must weight the same to avoid the computation of a meaningless distance.

KNN is a popular algorithm in classification due to its simplicity. In fact, the algorithm is intuitive and easy to implement. Additionally, it can perform well for both linear and non-linear cases.

However, KNN has some drawbacks. It is easily subject to overfitting, especially when working with an imbalanced training dataset.⁵ In addition, it can require a lot of memory for future predictions since it needs the training data samples to compute distances.

3.2.2 Decision tree

Decision tree is a predictive model approach which is constructed as a tree-shaped diagram, composed by nodes, branches and leaves. It provides the statistical probability of a class to occur. An example of tree architecture, for a four classes problem and a feature set of three components, is provided in Figure 10.

The prediction for a new sample is given using a succession of small tests. Each node corresponds to a test until a leaf, giving the overall output decision, is reached. Hence, in the tree example, if a new data sample n has:

• its feature x_{n2} is superior to T_2;

• its feature x_{n1} is inferior to T_1;

• its feature x_{n3} is inferior to T_3.

Then, there is a probability of 0.9 that it belongs to class 3 and a probability of 0.1 to belong to class 1. Generally, the highest probability is retained, making "class 3" the final decision for this sample.

In the training phase, two elements are determined: the architecture (e.g., the order of the considered features, the number of nodes and leaves) and threshold for each feature. A decision tree is constructed following these steps:

1. Split the training set by thresholding a feature;

2. Compute a measure of the quality of the split;

3. Repeat Step 1 and Step 2 until all the splitting possibilities (all thresholds for all features that wasn’t used in previous nodes) are associated with a quality measurement;

4. If the split with the best quality measurement improves the classification of the previous node, it is a new node. Otherwise, the previous node was better and is turned into a leaf.

5. Repeat all the previous steps until only leaves can be reached.

To measure the quality of a split, a criterion based on impurity (e.g., Gini’s) or information gain (e.g., entropy) can be used (Dangeti 2017). In practice, it is often the Gini’s impurity that is applied: Gini = 1 - \sum_{c=1}^C P(c)^2 where C is the number of classes and P(c) is the fraction of samples of class c observed after the split. The lower is the Gini’s criterion, the better is the split.

Decision trees are easy to understand and interpret. Additionally, they require very few data preparation (such as scaling in KNN) since splits are independently made for each feature. However, they can easily lead to overfitting if the set of features is too wide. As KNN, they are also sensitive to imbalanced dataset since the number of samples in each class impacts the quality criterion.

3.2.3 Random Forests

Random Forest is a part of "ensemble methods" of machine learning. Ensemble methods are based on the assumption that diversified and independent models tend to give better classification results. Therefore, Random Forest is a combination of tree predictors (Breiman 2001). The classification result comes from the majority vote of a collection of decision trees (also called bagging). In fact, it aims to enhance the generalization by averaging multiple decision trees trained on different parts of the same training set. Figure 11 shows the workflow for a new prediction with a RF model of E trees.

In the learning phase, each tree is growing, as described in Section 3.2.2, from a randomly selected subset of the feature set. In this way, each tree is growing with different features. Indeed, if the whole feature set was used, significant features would always come first in the top nodes of splitting which would make all trees be more or less similar.

Random forest is a very popular learning method that can reach really high performances. Contrary to previous methods, it can be robust to imbalanced dataset since a prior knowledge of class occurrences can be integrated in the algorithm. However, results are difficult to interpret since it can be constructed with hundreds of trees. Additionally, sometimes, RF can overfit due to a too noisy dataset (i.e., with a lot of outliers/extreme cases).

3.2.4 Support Vector Machines

Support Vector Machines are suited for both linear and non-linear problems (Cortes and Vapnik 1995). The aim of SVM is to find the hyperplane boundary that leaves the maximum margin between two classes. Figure 12 illustrates the SVM terminology on a linear example.

In the learning phase, the basis of SVM is the perceptron. This time, the vector of weights W is estimated ensuring that the margin is maximized between the support vectors of both classes. Support vectors are the data points of both classes which are near the hyperplane. Generally, a parameter g defines the quantities of points that will be taken into account while estimating W. The highest is g, the less support vectors will be used. For multiclass problem, the one-versus-the-rest strategy is often used.

The main strength of SVM is what is commonly called the "kernel trick". The idea is to apply a transformation \phi to the dataset in order to work on a space where data are linearly separable. An example of kernel transformation is given by Figure 13.

A wide variety of kernel transformations can be used such as polynomial, radial basis function or sigmoid as well as customized kernels.

Support Vector Machines is a widely used machine learning algorithm. Contrary to RF, it is robust to extreme cases since the hyperplane boundary is computed from support vectors. The main drawback of SVM is that a lot of parameters, depending on the kernel, has to be tuned and finding the best set of parameters can be computationally expensive.

3.2.5 Multi-Layer Perceptron

Multi-Layer Perceptron (MLP) is a feedforward artificial neural network. Although a sole perceptron is limited to linear situations, Artificial Neural Networks (ANN) have been constructed in order to solve non-linear problems. There are composed by one input layer, at least one hidden layer and one output layer. Hidden layers and output layers are made up of perceptrons that are all connected from a layer to another. Figure 14 depicts an example of MLP with two hidden layers.

Predictions are made by feeding the feature set of a sample to the network. Then, perceptrons are progressively activated (or not) until reaching an output node which gives the predicted class. Contrary to the linear case, the activation function of each perceptron is non-linear. Among them, we can cite hyperbolic tangent, rectified linear unit function or sigmoid.⁶

For the learning phase, MLP uses a supervised technique called backpropagation. As for the linear case, all samples are passed through the network and weights W are updated according to the output error (Parizeau 2004). Weights of each perceptron are updated one-by-one, starting from the ones of the output layer.

Neural network is a field in expansion notably because of improvement in computing capacities. Nowadays, neural networks can be composed of a large amount of hidden layers, increasing their depth. This increase of the computing capabilities leads to an evolution of Neural Networks (e.g., Convolutional Neural Networks, Recurrent Neural Networks) to what is today commonly called deep learning. The main drawback of neural networks is that it involves a lot of parameters to tune (e.g., number of layers, number of perceptrons per layer, connections between layers). In addition, it is also subject to overfit if the training set is too small or not representative of the whole population. Although today, various complex problems can be solved with deep learning, it is important to remind that it exists alternatives (e.g.,SVM, RF) that are faster, easier to train and can provide better performances regarding the classification objective.

4.2.1 Hold-out

The hold-out method is the simplest cross-validation technique. Data is divided into two parts: the training set and the testing set, as depicted by Figure 16.

This way, the classifier is trained on the training set and can be evaluated on unseen data of the testing set. Usually, a larger part of the data is used for training. There is two different ways to divide the data: by randomly selecting a number of samples over the whole dataset or by randomly selecting a number of samples of each class, in order to ensure a representation of all classes in the training and in the testing set. This method is usually applied for small datasets.

4.2.2 k-fold cross-validation

One way to improve the hold-out strategy is to perform a k-fold cross-validation to tune the parameters and train the model. The idea is to train the model on k different data splits to ensure its robustness. For each iteration, a training set and a validation set are constructed. An example of 3-fold cross-validation is provided by Figure 17.

For better control on the classifier performances, it is also recommended to work with an additional set, that wasn’t seen during the learning phase and the tuning of the parameters. This set is called the testing set. Hence, in Figure 17, the 3-fold cross-validation step is only performed on a part of the data.

4.2.3 Leave-one-out cross-validation

Leave-one-out cross-validation (LOOCV) is the extreme k-fold validation, where k is equal to the number of samples in the training/validation dataset. An example of LOOCV is depicted by Figure 18.

Another way to perform LOOCV exists in biomedical engineering. In fact, to evaluate the capacity of classifiers to work with a new patient, a leave-one-patient-out strategy is often performed by working on all patients except one at each time. Performances for each draw indicate the generalization of the model to make future predictions for a new patient.