# EvoSplit: An Evolutionary Approach to Split a Multi-Label Data Set into Disjoint Subsets
## 2 Related Works  
The first approach to apply stratification to multi-label data sets was proposed by [PERSON] et al. (2012). They proposed a greedy algorithm, Iterative Stratification (IS), that assigns iteratively examples from the original data set to each subset. The algorithm starts by taking the label with fewer examples in the data set. Those examples are, then, iteratively distributed among the different subsets based on the expected proportion of that label in each subset, i.e., an example is assigned to the subset that deviates more from the expected proportion. This process is repeated for each label until all the examples in the data set are distributed. [PERSON] et al. compared their approach against a random splitting using different measures. Following the notation presented in ([PERSON] and [PERSON], 2012), let's consider a data set, \(D\), annotated with a set of labels, \(L=\lambda_{1},\ldots,\lambda_{q}\), a desired number \(k\) of disjoints subsets \(S_{1},\ldots,S_{k}\) of \(D\), and a desired proportion of examples \(r_{1},\ldots,r_{k}\) in each of these subsets. The desired number of examples at each subset \(S_{j}\) is denoted as \(c_{j}\) and is equal to \(r_{j}\cdot|D|\). The subsets of \(D\) and \(S_{j}\) that contain positive examples of label \(\lambda_{i}\) are denoted \(D_{i}\) and \(S_{j}^{i}\) respectively. \begin{table}
\begin{tabular}{l c c c c c c c c c c c} \hline \hline  & \multicolumn{3}{c}{**Max**} & \multicolumn{3}{c}{**Max**} & \multicolumn{3}{c}{**Max**} & \multicolumn{3}{c}{**Olv**} & \multicolumn{1}{c}{**TCS**} & **avgIR** & \multicolumn{1}{c}{**SCUMBLE**} \\  & **m** & **q** & **Labels** & **Frequency** & **Card** & **Dens** & **Div** & **PDiv** & **TCS** & **avgIR** & **SCUMBLE** \\ \hline  
penImages**([PERSON] and [PERSON], 2012) & 6,941,550 & 1345 & 91 & 0.50 & 8.79 & 0.007 & 885,489 & 0.13 & \(8.3\times 10^{15}\) & 3015.02 & 0.42 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Imbalance measures of different multi-label data sets: size of data set (m), number of labels (q), max number of labels in an example of the data set (Max Labels), maximum frequency of a label in the data set (Max Frequency), label cardinality (Card), label density (Dens), label diversity (Div), normalized label diversity (PDiv), theoretical complexity score (TCS), average imbalance ratio per label (avgIR), and SCUMBLE. Well-known multi-label data sets (top) have smaller size and lower complexity than data sets currently used in computer vision applications (bottom). Data sets are ordered by theoretical complexity score. These data sets will be used in the validation of the different methods presented in this paper. The Label Distribution (\(LD\)) measure [12] (Equation (8)) evaluates the extent to which the distribution of positive and negative examples of each label in each subset follows the distribution of that label in the whole data set. For each label \(\lambda_{i}\), the measure computes the absolute difference between the ratio of positive to negative examples in each subset \(S_{j}\) with the ratio of positive to negative examples in the whole data set \(D\), and then averages the results across all labels. This measure is calculated as:  
\[LD=\frac{1}{q}\sum_{i=1}^{q}\left(\frac{1}{k}\sum_{j=1}^{k}\left|\frac{\left|S_ {j}^{i}\right|}{\left|S_{j}\right|-\left|S_{j}^{i}\right|}-\frac{\left|D^{i} \right|}{\left|D\right|-\left|D^{i}\right|}\right|\right) \tag{8}\]  
The Examples Distribution (\(ED\)) measure (Equation (9)) evaluates the extent to which the final number of examples in each subset \(S_{j}\) deviates from the desired/expected number of examples in that subset. \[ED=\frac{1}{k}\sum_{j=1}^{k}\left|\left|S_{j}\right|-c_{j}\right| \tag{9}\]  
Other measures are the number of folds that contain at least one label with zero positive examples (\(FZ\)), and the number of fold-label pairs with zero positive examples (\(FLZ\)). Using these measures, [PERSON] et al.