Selecting Representative Data Sets

1.1. Basic notations

In this section we set up basic notation and definitions used in the document.

A population is a set of all existing feature vectors (features). By Swe denote a sample set defined as a subset of a population collected during some process in order to obtain instances that can represent the population.

According to the previous definition the term representativeness is closely related. We can define a representative setS*as a special subset of an original dataset S, which satisfies three main characteristics [72]:

1. It is significantly smaller in size compared to the original dataset.

2. It captures the most of information from the original dataset compared to any subset of the same size.

3. It has low redundancy among the representatives it contains.

A training set is in the idealized case a representative set of a population. Any of mentioned methods is not needed if we have representative subset of the population. But we never have itin practise. We usually have a random sample set of the population and we use various methods to make it as representative as possible. We will denote a training set by R.

In order to define a representative set we can define a minimal consistent subset of a training set. Given a training set R, we want to obtain a subset R*⊁Rsuch that R*is the smallest set of instances such that Acc(R*)≄Acc(R), where Acc(X)denotes the classification accuracy obtained using Xas a training set [71].

Sets used for an evaluation of a model are the validation set V, usually used for a model selection, and the testing set T, used for model assessment.

2.1. Evaluation methods

During building a model, we need to evaluate its performance in order to validate or assess it as we mention earlier. There are more methods how to check our model, but not all are usually sufficient or applicable in all situations. We should always choose the most appropriate and reliable method for our purpose. Some of common evaluation methods are [83]:

A comparison of the model with a physical theory is the first and probably the easiest way how to check our model. For example, if our model predicts a negative quantity or parameters outside of a possible range, it points to a poorly estimated model. However, a comparison with a physical theory is not always possible nor sufficient as a quality indicator.

Sometimes a theoretical model exists, but may be to complicated for a practical use. In this case, the theoretical model could be used for a comparison or evaluation of the accuracy of the built model.

The use of data collected in an independent experiment is the best and the most preferred way for a model evaluation. It is the only way that gives us a real estimate of the model performance on new data. Only new collected data can reveal a bias in a previous sampling process. This is the easiest way if we can easily repeat the experiment and sampling process. Unfortunately, there are situations when we are not capable to collect new independent data for this purpose either due to a high cost of the experiment or another unrepeatability of the process.

The use the same data for evaluation and for a model building usually leads to an optimistic estimation of real performance due to a positive bias. This is not recommended method and if there is another way it could not be used for the model evaluation at all.

A reserve part of the learning data is in practise the most common way how to deal with the absence of an independent dataset for model evaluation. As the reserve part selection from the data is usually not a simple task, many methods were invented. Their usage depends on a particular domain. Splitting the data is wished to have the same effect as having two independent datasets. However, this is not true, only newly collected data can point out the bias in the training dataset.

2.1.1. Evaluation measures

For evaluating a classifier or predictor there is a large variation of performance measures. However, a measure, good for evaluating a model in a particular domain, could be inappropriate in another domain and vice versa. The choice of an evaluation measure depends on the domain of use and the given problem. Moreover, different measures are used for classification and regression problems. The measures below are shortly described basics for the model evaluation. For more details see [46, 100].

Measures for classification evaluation

The basis for analysing classifier performance is a confusion matrix. The confusion matrix describes how well a classifier can recognize different classes. For cclasses, the confusion matrix is an n×ntable, which (i,j)th entry indicates the count of instances of the class iclassified as j. It means that correctly classified instances are on the main diagonal of the confusion matrix. The simplest and the most common form of the confusion matrix is a two-classes matrix as it is shown in the table 1. Given two classes, we usually use a special terminology describing members of the confusion matrix. Terms Positive and Negative refer to the classes. True Positives are positive instances that were correctly classified, True Negatives are also correctly classified instances but of the negative class. On the contrary, False Positives are incorrectly classified positive instances and False Negatives are incorrectly classified negative instances. TPTrue PositivesTNTrue NegativesFPFalse PositivesFNFalse Negatives

The first and the most commonly used measure is the accuracy denoted as Acc(X). The accuracy of a classifier on a given set is the percentage of correctly classified instances. We can define the accuracy as

Acc(X)=correctlyclassifiedinstancesallinstancesE1

or in a two-classes case

Acc(X)=TP+TNTP+TN+FP+FN.E2

In order of having defined the accuracy, we can define the error rate of a classifier as

Err(X)=1-Acc(X),E3

which is the percentage of incorrectly classified instances.

If costs of making a wrong classification are known, we can assign different cost or benefit to each correct classification. This simple method is known as costs and benefits or risks and gains. The cost matrix has then the structure shown in Figure 2, where ϙijcorresponds to the cost of classifying the instance of class ito class j. Correctly classified instances have usually a zero cost (ϙii=ϙjj=0). Given a cost matrix, we can calculate the cost of a particular learned model on a given test set by summing relevant elements of the cost matrix accordingly to the model’s prediction [100]. Here, the cost matrix is used as a measure, the costs are ignored during the classification. When a cost matrix is taken into account during learning a classification model, we speak about a cost-sensitive learning, which is mentioned in section 5 in the context of class balancing.

Using the accuracy measure fails in cases, when classes are significantly imbalanced (The class imbalanced problem is discussed in section 5 ). Good examples could be medical data, where we can have a lot of negative instances (for example 98%) and just a few (2%) of positive instances. It gives an impressive 98%accuracy, when we simply classify all instances as negative, which is absolutely unacceptable for medical purposes. The reason for this is that the contribution of a class to the overall accuracy rate is a function of its cardinality, with the effect that rare positives have an almost insignificant impact on the performance measure [22].

Alternatives for the accuracy measure are:

Sensitivity (also called True Positive Rate or Recall) - the percentage of truly positive instances that were classified as positive,

sensitivity=TPTP+FN.E4

Specificity (also called True Negative Rate) - the percentage of truly negative instances that were classified as negative,

specificity=TNTN+FP.E5

Precision - the percentage of positively classified instances that are truly positive,

precision=TPTP+FP.E6

It can be shown that the accuracy is a function of the sensitivity and specificity:

accuracy=sensitivity⋄TP+FNTP+TN+FP+FN+specificity⋄TN+FPTP+TN+FP+FN.E7

F-measure combines precision and recall. It is generally defined as

Fϐ=(1+ϐ2)precision⋄recallϐ2⋄precision+⋄recallE8

where ϐspecifies the relative importance of precision and recall. The F-measure can be interpreted as a weighted average of the precision and recall. A disadvantage of this measure is that it does not take the true negative rate into account. Another measure, that overcomes disadvantages of the accuracy on imbalanced datasets is the geometric mean of class accuracies. For the two-classes case it is defined as

gm=TPTP+FN⋄TNTN+FP=sensitivity⋄specificityE9

The geometric mean puts all classes on an equal footing, unfortunately there is no way to overweight any class [22].

The evaluation measure should be appropriate to the domain of use. If is it possible, usually the best way to write a report is to provide the whole confusion matrix. The reader than can calculate the measure which he is most interested in.

Measures for regression evaluation

The measures described above are mainly used for classification problems rather than for regression problems. For regression problems more appropriate error measures are used. They are focused on how close is the actual model to the ideal model instead of looking if the predicted value is correct or incorrect. The difference between known value yand predicted value f(xi)is measured by so called loss functions. Commonly used loss functions (errors) are described bellow.

The square loss is one of the most common measures used for regression purposes, is it defined as

l(yi,f(xi))=(yi-f(xi))2E10

A disadvantage of this measure is its sensitivity to outliers (because squaring of the error scales the loss quadratically). Therefore, data should be filtered for outliers before using of this measure. Another measure commonly used in regression is the absolute loss, defined as

l(yi,f(xi))=|yi-f(xi)|E11

It avoids the problem of outliers by scaling the loss linearly. Closely similar measure to the absolute loss is the ϓ-insensitive loss. The difference between both is that this measure does not penalize errors within some defined range ϓ. It is defined as

l(yi,f(xi))=max(|y-f(x)|-ϓ,0)E12

The average of the loss over the dataset is called generalization error or error rate. On the basis of the loss functions described above we can define the mean absolute error and mean squared error as

MAE=1n∐i=1n‎|yi-f(xi)|E13

and

MSE=1n∐i=1n‎(yi-f(xi))2E14

, respectively. Often used measure is also the root mean squared error

RMSE=1n∐i=1n‎(yi-f(xi))2E15

, which has the same scale as the quantity being estimated. As well as the squared loss the mean squared error is sensitive to outliers, while the mean absolute error is not. When a relative measure is more appropriate, we can use the relative absolute error

RAE=∐i=1n‎|yi-f(xi)|∐i=1n‎|yi-ỵ|E16

or the relative squared error

RSE=∐i=1n‎(yi-f(xi))2∐i=1n‎(yi-ỵ)E17

where

ỵ=1n∐i=1n‎yiE18

.

2.1.2.Bias. and variance

With the most important performance measure - the mean square error, the bias, variance and bias/variance dilemma is directly related. They are described thoroughly in [?]. Due the importance of these characteristics, it is in place to describe them more in detail.

With given statistical model characterized by parameter vector ϖwe define estimator ϖ̠of this model (classification or regression model in our case) as a function of nobservations of xand we denote it as

ϖ̠=ϖ̠(x1,‧,xN)E19

The MSE is equal to the sum of the variance and the squared bias of the estimate, formally

MSE(ϖ̠)=Var(ϖ̠)+Bias(ϖ̠)2E20

Thus either bias or variance can contribute to poor performance of the estimator.

The bias of an estimator is defined as a difference between the expected value of the method and the true value of the parameter, formally

Bias(ϖ̠)=E[ϖ̠]-ϖ=E[ϖ̠-ϖ]E21

In another words the bias says whether the estimator is correct on average. If the bias is equal to zero, the estimator is said to be unbiased. The estimator can be biased for many reasons, but the most common source of an optimistic bias is using of the training data (or not independent data from the training data) to estimate predictive performance.

The variance gives us an interval within which the error appears. For an unbiased estimator the MSE is equal to the variance. It means that even though an estimator is unbiased it still may have large MSE if the variance is large.

Since the MSE can be decomposed into a sum of the bias and variance, both characteristics need to be minimized to achieve good predictive performance. It is common to trade-off some increase in the bias for a larger decrease in the variance [41].

2.3. Dataset comparison

In some cases we need to compare two datasets, if they have the same distributions. For example if we split the original dataset into a training and a testing set, we expect that a representative sample will be in each subset and distributions of the sets will be the same (with a specific tolerance of deviation). If we assess splitting algorithms, one of the criteria will be the capability of the algorithm to divide the original dataset into the two identically distributed subsets.

For comparing datasets distributions we should use a statistical test under the null hypothesis that distributions of the datasets are the same. These tests are usually called goodness-of-fit tests and they are widely described in literature [2, 8, 59, 85]. For an univariate case we can compare distributions relatively easily using one of the numerous graphical or statistical tests e.g. histograms, PP and QQ plots, the Chi-square test for a dicrete multinominal distribution or the Kolmogorov-Smirnov non-parametric test. For more details see [87].

A multivariate case is more complicated because generalization to more dimensions is not so straightforward. Generalization of the most cited goodness-of-fit test, the Kolmogorov-Smirnov test, is in [10, 35, 54].

In the case of comparing two subsets of one set, we use a naive approach for their comparison. We suppose that two sets are approximately the same, based on comparing basic multivariate data characteristic. We believe, that for our purpose the naive approach is sufficient. Advantages of this approach are its simplicity and a low computational complexity in comparison with the goodness-of-fit tests. A description of commonly used multivariate data characteristics follows.

The first characteristic is the mean vector. Let xrepresent a random vector of pvariables, and xi=(xi1,xi2,‧,xip)denote the i-th instance in the sample set, the sample mean error is defined as

where nis the number of observations. Thus x̣iis the mean of the i-th variable on the nobservations. The mean of xover all possible instances in the population is called population mean vector and is defined as a vector of expected values of each variable, formally

Therefore, x̣is an estimate of Ϛ.

Second characteristic is the covariance matrix. Let sjk=1n-1∐i=1n‎(xij-x̣j)(xik-x̣k)be a sample covariance between j-th and k-th variable. We define the sample covariance matrix as

Because sjk=skj, the covariance matrix is symmetric and there are variances sj2, the squares of standard deviations sj, on the diagonal of the matrix. Therefore, the covariance matrix is also called variance-covariance matrix. As for the mean, the covariance matrix over whole population is called population covariance matrix and is defined as

where

The covariance matrix contains p×pvalues corresponding to all pairs of variables and their covariances. The covariance matrix could be inconvenient in some cases and therefore it can be desired to have one single number as an overall characteristic. One measure summarising the covariance matrix is called generalized sample variance and is defined as the determinant of the covariance matrix

The geometric interpretation of the generalized sample variance is a p-dimensional hyperellipsoid centered at x̣.

More details about the multivariate data characteristic can be found in [77].

3.1. Data splitting strategies

When only one dataset is given, several possible ways how to use available data come into consideration to perform tasks described in section 2 (training, validation, testing). We can split available data into two or more parts and use each to perform a particular task. Common practise is to split data into two or three sets:

Training set - a set used for learning and estimating parameters of the model.

Validation set - a set used to evaluate the model, usually for model selection.

Testing set - a set of examples used to assess the predictive performance of the model.

Let us define following data splitting strategies according to how data used in a process of model building are available.

The null strategy (Strategy 0) is when all available data are used for all tasks. Training, selecting and making an assessment on the same data usually leads to over-fitting of the model and to an over-optimistic estimate of the predictive accuracy. The error estimated on the same set as the model was trained is known as re-substitution error.

The strategy motivated by the arrival of new data (Strategy 1) uses one set for training and the second set, containing the first set and newly collected data, for the assessment. Merging new collected data with the old data loses the independence of model selection and assessment, which can lead to an over-optimistic estimate of the performance of the model.

The most commonly used strategy is to split data into two sets, a training set and a testing set. The training set (also called the estimation set) is used to estimate the parameters of the model and also for model selection (validation). The testing set is then used to assess the prediction performance of the model (Strategy 2).

Another strategy (Strategy 3) which splits data into two sets uses one set for learning and the second for model selection and to assess its predictive performance.

The use an independent set for each task is generally recommended. This strategy (Strategy 4) splits available data into three sets.

3.2. Data splitting algorithms

Many data splitting algorithms were proposed. Quality and complexity of algorithms differ and not any approach is superior in general. Data splitting methods and algorithms and their comparison can be found in literature [15, 68, 83, 86]. Some of commonly used algorithms are described bellow.

The holdout method described in [67] is the simplest method that takes an original dataset and splits it randomly into two sets. Common practise is to use one third for testing and the rest for training or half to half. Assuming that the performance of the model increases with the count of seen instances and decreases with the count of left instances apart of the training leads to higher bias and decreases the performance. In other words, both subsets might have different distributions. Moreover, if a dataset is not large enough, and it is usually not, the holdout method is inefficient in the use of data. For example in a classification problem one or more classes might be missing in one of the subsets, which leads to poor estimation of the model as well as to its evaluation. In deal with this some advanced versions use so called stratification. Stratified sampling is a probability sampling, where an original dataset is divided into non-overlapping groups called strata, and instances are selected from each strata proportionally to the appropriate probability. It ensures that each class is represented with the same frequency in both subsets. But it still does not prevent inception of the bias in training and testing sets. For better reliability of the error estimation, the methods are repeated and the resulting accuracy is calculated as an average over all iterations. It can positively reduce the bias. The Repeated holdout method is also known as Monte Carlo Cross-validation, Random Sub-sampling or Repeated Evaluation Sets.

The most popular resampling method is Cross-validation. In k-fold cross-validation, the original data set is splitted into kdisjoint folds of the same size, where kis a parameter of the method. In each from kturns one fold is used for evaluation and the remaining k-1folds for model learning as shown in Figure 4. As in the repeated holdout method, the resulting accuracy is the average of all turns. As well as holdout method, k-fold cross-validation suffers on a pessimistic bias, when kis small. Increasing the count of folds reduces the bias, but increases the variance of the estimation [41]. Experiments have shown that good results across different domains have the k-fold cross-validation method with ten folds [40], but in general kis unfixed. The k-fold cross-validation is very similar to the repeated holdout method with advantage that all the instances of the original data set are used for learning the model and even for evaluation.

Leave-one-out cross-validation (LOOCV) is the special case of the k-fold cross-validation in which k=n, where nis the size of the original dataset. All test sets have always only one instance. This method makes the best use of data and does not involve any random sub-sampling. According to this, the LOOCV gives nearly unbiased estimates of a model performance but usually with large variability. However, this method is extremely computationally expensive, that makes it often inapplicable.

The Bootstrap method was introduced in [89]. The main idea of the method is described as follows. Given a dataset Sof size n, generate Bbootstrap samples by uniform sampling (with replacement), ninstances from the dataset. Notice that sampling with replacement allows to select the same instance more than once. After re-sampling, estimate parameters of a model on each bootstrap sample and than estimate a prediction performance of the model on the original dataset. The overall prediction error is given by averaging these Bestimates. Process is schematically shown in Figure 5.

The most known and commonly used approach is the.632 bootstrap. The number 0.632 in the name means the expected fraction of distinct instances of the original dataset appeared in the training set. Each instance has a probability of 1/nto being selected from ninstances ((1-1/n) to not being selected). It gives the probability of (1-1/n)n≇e-1≇0.368not to be selected after nsamples. In other words, we expect that 63.2%instances of the original dataset will be selected for training and 36.8%remaining instances will be used for testing. The.632 bootstrap estimate is defined as

where Acc(Bi)Bi'is the accuracy of the model built with bootstrap sample Bias the training set and applied to the test set Bi'and Acc(Bi)Tis the accuracy of the same model applied to the original dataset. Comparison of the bootstrap with other methods can be found in literature [5, 13, 48, 56, 89]. The results show that 0.632 bootstrap estimates have usually low variability but with a large bias in comparison with the cross-validation that gives approximately unbiased estimates, but with a high variability. It is also reported that the 0.632 bootstrap works best for small datasets. Some experiments showed that the.632 bootstrap fails in some cases, for more details see [3, 5, 11, 56].

Kennard-Stone’s algorithm (CADEX) [25, 55] is used for splitting data sets into two distinct subsets which cover approximately the same region of the factor space defined by the original dataset. Instead of measuring coverage by an explicit criterion, the algorithm follows two guidelines. The first one is that no instance from one set should be too far from any instance of the other set, and the second one is that the coverage should start on the boundary of the factor space. The instances are chosen sequentially and the aim is to select the instances in each iteration to get uniformly distributed instances over the space defined by original dataset. The algorithm works as follows. Let Pbe the subset of already selected instances and let Qbe the dataset equal to Tat the beginning. We define Dist(p,q)as the distance from instance p∇Pto instance q∇Qand βq(P)will be the minimal distance from instance qover the set of already selected instances in P.

The algorithm starts with adding two most distant instances from Qto P(it is not necessary to select the most distant instances, they can be any instances, but accordingly to the idea of coverage, we usually choose two most distant instances). In each iteration the algorithm selects an instance from the remaining instances in the set Qusing the criterion

In other words, for each instance remaining in the data set Qfind the smallest distances to already selected instances in Pand choose the one with the maximal distance among these smallest distances. The process is repeat until enough objects are selected. First iteration of the algorithm is shown in Figure 6(a) and in Figure 6(b) is final result with area covered by each set. Since the algorithm uses distances it is sensitive to the used metrics and eventual outliers. For classification purposes subsets should be selected from the individual classes [24]. Improved version of CADEX named DUPLEX is described in [83].

Other methods can be considered when we take into account the following assumption. We suppose that two sets Pand Qformed by splitting the original dataset Sare as similar as possible when sum of distances of all pairs (one instance from the pair is from Pand the other from Q) are minimized. Formally

To find the optimal splitting to the two sets is computationally very expensive. Two heuristic approaches come to mind. The first is a method based on the Nearest neighbour rule. This simple method splits original datasets into two or more datasets by finding the nearest instance (nearest neighbour) of randomly chosen instance and putting each instance into a different subset. The second heuristics finds the closest pair (described in [88]) of instances in Sand put one instance into Pand the second instance into Q. This is repeated until the set Tis empty. The result of these algorithms are two disjoint subsets of the original dataset. The question is how properly will this heuristics work in practice.

4.1. Wrapper methods

The first published instance selection algorithm is probably Condensed Nearest Neighbour (CNN) [23]. It is an incremental method starting with new set Rwhich includes one instance per class chosen randomly from S. In the next step the method classifies Susing Ras a training set. After the classification, each wrongly classified instance from Sis added to R(absorbed). CNN selects instances near the decision border as shown in Figure 9. Unfortunately, due to this procedure the CNN can select noise instances. Moreover, performance of the CNN is not good [43, 49]. CNNCondensed Nearest Neighbour

Reduced Nearest Neighbour (RNN) is a modification of the CNN introduced by [39]. The RNN is a decremental method that starts with R=Sand removes all instances that do not decrease the predictive performance of a model trained using S.

Selective Nearest Neighbour (SNN) [79] is based on the CNN. It finds a subset R⊁Ssatisfying that all instances are nearer to the nearest neighbour of the same class in Rthan to any neighbour of the other class in S.

Generalized Condensed Nearest Neighbour (GCNN)[21] is another instance selection decision rule based on the CNN. The GCNN works the same way as the CNN, but it also defines the following absorption criterion: instance xis absorbed if ∤x-q∤-∤x-p∤>ϒ, where pis the nearest neighbour of the same class as xand qis the nearest neighbour belonging to a different class than x.

Edited Nearest Neighbour (ENN) described in [98] is a decremental algorithm starting with R=S. The ENN removes a given instance from Rif its class does not agree with the majority class of its neighbourhoods. ENN uses k-NN rule, usually with k=3, to decide about the majority class, all instances misclassified by 3-NN are discarded as shown in Figure 8. An extension that runs the ENN repeatedly until no change is made in Ris known as Repeated ENN (RENN). Another modification of the ENN is All k-NN published by [90] It is an iterative method that runs the ENN repeatedly for all k(k=1,2,‧,l). In each iteration misclassified instances are discarded. Another methods based on the ENN are Multiedit and Editing by Estimating Conditional Class Probabilities described in [27] and [92], respectively.

Instance Based (IB1-3) methods were proposed in [1]. The IB2 selects the instances misclassified by the IB1 (the IB1 is the same as the 1-NN algorithm). It is quite similar to the CNN, but the IB2 does not include one instance per class and does not repeat the process after the first pass through a training set like the CNN. The last version, the IB3, is an incremental algorithm extending the IB2. the IB3 uses a significance test and accepts an instance only if its accuracy is statistically significantly greater than the frequency of its class. Similarly, an instance is rejected if its accuracy is statistically significantly lower than the frequency of its class. Confidence intervals are used to determine the impact of the instance (0.9 to accept, 0.7 to reject).

Decremental Reduction Optimization Procedures (DROP1-5) are instance selection algorithms presented in [99]. These methods use an associate that can be defined by function Associates(x)that collects all instances that have xas one of its neighbours. The DROP1 method removes instances from Rthat do not change a classification of its associates. The DROP2 is the same as the DROP1 but the associates are taken from the original sample set Sinstead of considering only instances remaining in Ras the DROP1 method. The DROP3 and DROP4 methods run a noise filter first and then apply the DROP2 method. The DROP5 method is another version of the DROP2 extended of discarding the nearest opposite class instances.

Iterative Case Filtering (ICF) are described in [14]. They define LocalSet(x)as a set of cases contained in the largest hypersphere centred at xsuch that only cases in the same class as xare contained in the hypersphere. They defined property Adaptable(x,x')as ⇿x∇LocalSet(x'). It means that instance xcan be adapted to x'. Moreover they define two properties based on the adaptable property called reachability and coverage and defined as follows.

The algorithm is based on these two properties. At first, the ICF uses the ENN to filter noise instances then the ICF repeatedly computes defined instance properties and in each iteration removes instances that have |Reachability(x)|>|Coverage(x)|. The process is repeated until no progress is observed. Another method based on the same properties, the reachability and coverage, was proposed in [104].

Many other methods were proposed in literature. Some of them are based on evolutionary algorithms (EA)[38, 64, 84, 91], other methods use the support vector machine (SVM) [9, 17, 61, 62] or tabu search (TS) [18, 42, 103].

4.2. Filter methods

The Pattern by Ordered Projections (POP) method [78] is a heuristic approach to find representative patterns. The main idea of the algorithm is to select only some border instances and eliminate the instances that are not on the boundaries of the regions to which they belong. It uses the function weakness(x), which is defined as the number of times that example xdoes not represent a border in a partition for every partitions obtained from ordered projected sequences of each attribute, for discarding irrelevant instances that have weaknesses equal to the number of attributes of data set. The weakness of an instance is computed by increasing the weakness for each attribute, where the instance is not near to another instance with different class.

Another method based on finding border instances is the Pair Opposite Class-Nearest Neighbour (POC-NN) [75]. The POC-NN calculates the mean of all instances in each class and finds a border instance pb1belonging to the class C1as an instance that is the nearest instance to m2, which is the mean of class C2. The same way it finds other border instances.

The Maxdiff kd trees described in [69] is a method based on kd trees [37]. The algorithm builds a binary tree from an original data set. All instances are in the root node and child’s nodes are constructed by splitting the node by a pivot, which is a feature with the maximum difference between consecutively ordered values. The process is repeated until no node can be split. Leaves of the tree are the output condensed set.

Several methods are based on clustering. They split an original dataset into nclusters and centres of the clusters are selected as instances [9, 16, 65]. Some extensions were proposed. The Generalized-Modified Chang algorithm (GCM) merges the nearest clusters with the same class and uses centres of the merged clusters. The Nearest Sub-class Classifier method (NSB) [93] selects more instances (centres) for each class using the Maximum Variance Cluster algorithm [94]. Another method is based on clustering. The Object Selection by Clustering (OSC) [4] selects border instances in heterogeneous clusters and some interior instances in homogeneous clusters.

Some prototype filtering methods were proposed in the literature. The first described is Weighting prototype (WS)[73] method. The WS method assigns a weight to each prototype (⇿x∇T) and selects only those with a larger weight than a certain threshold. The WS method uses a gradient descent algorithm for computing weights of instances. WSWeighting prototypeAnother published prototype method is Prototype Selection by Relevance (PSR)[70]. The PSR computes the relevance of each instance in T. The most similar instances in the same class are the most relevant. The PSR selects a user defined portion of relevant instances in the class and the most similar instances belonging to the different class - the border instances.

5.1. Data-level methods

The aim of these methods is to change distributions of classes by increasing the number of instances of the minority class (over-sampling), decreasing the number of instances of the majority class (under-sampling), by combinations of these methods or using other advanced sampling ways.

5.1.2. Over-sampling

The random over-sampling is a naive method, that balances class distributions by replication, at random, instances of the minority class. Two disadvantages of this method were described in literature. The first one, the instance replication increases likelihood of the over-fitting [19] and the second, enlarging the training set by the over-sampling can lead to a longer learning phase and a model response [60], mainly for lazy learners.

The most known over-sampling method is Synthetic Minority Over-sampling Technique (SMOTE) [19]. The SMOTE does not over-sample with replacement, instead, it generates "synthetic" instances of the minority class. The minority class is over-sampled by taking each instance of the minority class and its nearest neighbour and placing the "synthetic" instance, at random, along the line joining these instances (Figure 11). This approach avoids over-fitting and causes that a classifier creates larger and less specific decision regions, rather than smaller and more specific ones. The method based on the SMOTE reported better experimental results in TP-rate and F-measure [45], the Borderline_SMOTE. It over-samples only the borderline instances of the minority class.

5.2. Algorithm level methods

Another approach to deal with imbalanced datasets modifies a classifier or a learning process rather than changing distributions of datasets by discarding or replicating instances. These methods are mainly based on overweighting the minority class, discriminating the majority class, penalization for misclassification or biasing the learning algorithm. A short description of published methods follows.

5.3. Ensemble learning methods

Ensemble methods are methods, which use a combination of methods with the aim to achieve better results. Two most known ensemble methods are bagging and boosting. The bagging (Bootstrap aggregating) proposed in [12] initially generates Bbootstrap sets of the original dataset and then builds a classification or regression model using each bootstrap set. Predicted values of these models are combined to predict the final result. In classification tasks it works as follows. Each model has one vote to predict a class, the bagged classifier counts the votes and assigns the class with the most votes. For regression tasks, the predicted value is computed as the average of values predicted by each model.

The boosting, firstly described in [80], is based on the idea a powerful model is created using a set of weak models. The method is quite similar to the bagging. Like the bagging the boosting uses voting for a classification task or averaging for a regression task to predict the output value. However, the boosting is an iterative method. In each iteration a newly built model is influenced by the performance of those built previously. By assigning greater weights to the instances that were misclassified in previous iterations the model pays more attention on these instances.

Another in comparison with bagging and boosting less widely used method is stacking proposed in [101]. In the stacking method the original dataset is splitted into two disjoint sets, a training set and a validation set. Several base models are learned on the training set and then applied to the validation set. Using predictions from the validation set as inputs and correct values as the outputs, a higher level model is build. In comparison with the bagging and boosting, the stacking can be used to combine different types of models.

Ensemble methods such the bagging, boosting and stacking often outperform another methods. Therefore, they have been widely studied in recent years and lot of approaches have been proposed. The earlier mentioned Adaboost [36] and AdaCost [34] are other methods that use the boosting are RareBoost [53] or SMOTEBoost [20]. A method combining the bagging and stacking to identify the best combination of classifiers is used in [74]. Three agents (Naive Bayes, C4.5, 5-NN) are combined in the approach proposed in [58]. There are many other methods utilizing the mentioned approaches.