# EvoSplit: An Evolutionary Approach to Split a Multi-Label Data Set into Disjoint Subsets
## 1 Introduction  
Supervised learning is the machine learning task of learning a function that maps an input to an output based on example input-output pairs [1]. An inducer receives a set of labeled examples as training data and makes predictions for unseen inputs [2, 3]. Traditionally, each example is associated with a single label. However, in some problems an example might be associated with multiple labels. Multi-label machine learning has received significant attention in fields such as text categorization [4], image classification [5], health risk prediction [6], or electricity load monitoring [7], among others. In computer vision in particular, there are more and more applications and available data sets that involve multi-label learning [8, 9, 10]. Formally [11], suppose \(X=\mathbb{R}^{d}\) (or \(\mathbb{Z}^{d}\)) denotes the \(d\)-dimension instance space, and \(Y=\{y_{1},y_{2},\ldots,y_{q}\}\) denotes the label space with \(q\) possible class labels. The task of multi-label learning is to learn a function \(h:X\to 2^{Y}\) from the multi-label training set \(D=\{(x_{i},Y_{i})|1\leq i\leq m\}\). For each multi-label example \((x_{i},Y_{i}),x_{i}\in X\) is a \(d\)-dimensional feature vector \((x_{i1},x_{i2},\ldots,x_{id})\) and \(Y_{i}\subseteq Y\) is the set of labels associated with \(x_{i}\). For any unseen instance \(x\in X\), the multi-label classifier \(C(\cdot)\) predicts \(C(x)\subseteq Y\) as the set of proper labels for \(x\). In supervised learning, experiments typically involve a first step of distributing the examples of a data set into two or more disjoint subsets [12]. If a large amount of training data is available, the holdout method [3] is used to distribute the examples into two mutually exclusive subsets called training set and test set, or holdout set. Sometimes the training set is also divided into two disjoint subsets to create a validation set. When training data is limited, \(k\)-fold cross-validation is used, which splits the data set into \(k\) disjoint subsets of approximately equal size. In single-label data sets, those disjoint subsets are built by distributing equally and randomly the examples in the original data set belonging to the different class labels. However, splitting a multi-label data set is not straightforward, as an over-represented class in one subset will be an under-represented in the other/s [3]. Furthermore [12], random distribution of multi-label training examples into subsets suffers from the following practical problem: it can lead to test subsets lacking even just one example of a rare label, which in turn causes calculation problems for a number of multi-label evaluation measures. The typical way these problems get by-passed in the literature is through complete removal of rare labels. This, however, implies that the performance of the learning systems on rare labels is unimportant, which is seldom true. As mentioned by [13], multi-label classification usually follows predetermined train/test splits set by data set providers, without the analysis in terms of how well the examples are distributed into those train/test splits. Therefore, a method called stratification [3] or stratified sampling [12] was developed, in which a data set is split so that the proportion of examples of each class label in each subset is approximately equal to that in the complete data set. Stratification improves upon standard cross-validation both in terms of bias and variance, when compared to regular cross-validation [3]. The data used for learning a classifier is often imbalanced [14,15]. Thus, the class labels assigned to each instance are not equally represented. Traditionally, imbalanced classification has been faced through techniques such as resampling, cost-sensitive learning, and algorithmic-specific adaptations [16,17]. In deep learning, data augmentation is a technique that has been successful in order to address imbalanced data sets [18,19].