Option 2: Reducing data points

We identify two main families of techniques for reducing data points: clustering and instance selection.

Below, we present a number of methodologies for each family. More techniques can be found in the review paper Olvera-López et al. 2010.

Clustering

Training data can be grouped into clusters according to certain similarity metrics. The output can then be fed to a machine learning algorithm which then will learn how to classify each cluster rather than each individual data point. There is a very large number of techniques available for clustering, we will cover here some common techniques that can be implemented with the sklearn library:

• K-means algorithm: it splits the dataset into k clusters. Each observation belongs to the cluster with the nearest mean. A less computationally expensive variant of the algorithm is the MiniBatch K-means, which uses mini-batches to reduce computation time.

• Mean-shift: it aims to discover clusters by finding which data points can act as centroids, and be the mean of the points in that cluster.

• Hierarchical clustering: It is a family of clustering algorithms that creates nested clusters. Clusters can thus be represented as a tree where the root is the set including all data points, and the leaves are composed of only one sample. The Agglomerative Clustering algorithm creates this hierarchy by successively merging pairs of clusters until all points are assigned to the same cluster.

• DBSCAN: the Density-Based Spatial Clustering of Applications with Noise divides the data into clusters according to the density. The algorithm is useful for noisy datasets as it does not require to set the number or the shape of the clusters a priori.

• Gaussian mixture model: it assumes that the data is generated from a mixture of k of unknown parameters, which are learned during training.

Instance Selection

Since not all data points are useful for the prediction task at hand, it is possible to eliminate some individuals from the dataset. Instance selection methods are divided in two groups:

1. Wrapper. Methods which select instances based on the accuracy obtained by the machine learning model.

   • Most of these methods are based on the k-NN classifier: Condensed Nearest Neighbour (Hart 1968, Angiulli 2005), Selective Nearest Neighbour rule (Ritter et al. 1975), Generalized Condensed Nearest Neighbour rule (Chien-Hsing et al. 2006), Edited Nearest Neighbour (Wilson 1972), Decremental Reduction Optimization Procedure (Wilson and Martínez 2000).

   • The SVM (Support Vector Machines) can be used not only as a classifier but also as an instance selector.

     • In the method presented in Yuangui et al. 2005, an SVM is first used to obtain the support vectors, and then a wrapper method is used to select them.

     • Another method is SV-kNNC (Support Vector k-Nearest Neighbour Clustering) (Srisawat et al. 2006). First an SVM is applied, then the k-means algorithm is used to cluster the support vectors. The data points that do not belong to homogeneous clusters are discarded.

   • Evolutionary algorithms can also be used for instance selection (Kuncheva 1995, 1997; Kuncheva and Bezdek 1998; Bezdek and Kuncheva 2001; Cano et al. 2003, García et al. 2008).

2. Filter. These methods select instances by using a separate selection function, without involving the machine learning model.

   • POP (Pattern by Ordered Projections) were introduced by Riquelme et al. 2003. This method estimates the amount of times each instance is not a border in a class. If the instance is not near instances from other classes, it is assumed that it can be safely discarded as it does not significantly affect the decision of the algorithm.

   • Paredes and Vidal 2000 and Olvera-López et al. 2008 assign weights to data points by computing their importance. In the former case the importance is estimated through gradient descent relative to nearest neighbours and enemies. In the latter case importance is given by the similarity of each data point with other instances in the same class, with most similar instances being most important.